Производительность подсчета Mysql для очень больших таблиц

У меня есть таблица с более чем 100 миллионами строк в Innodb.

Я должен знать, есть ли более 5000 строк, где внешний ключ = 1. Мне не нужно точное число.

Я провел небольшое тестирование:

SELECT COUNT(*) FROM table WHERE fk = 1=> 16 секунд
SELECT COUNT(*) FROM table WHERE fk = 1 LIMIT 5000=> 16 секунд
SELECT primary FROM table WHERE fk = 1=> 0,6 секунды

У меня будет большая сеть и время обработки, но это может быть перегрузка в 15,4 секунды!

У вас есть идея получше?

Спасибо

Редактировать: [Добавлены соответствующие комментарии OP]

Я попробовал SELECT SQL_NO_CACHE COUNT(fk) FROM table WHERE fk = 1, но это заняло 25 секунд

Mysql был настроен для Innodb с помощью Mysql Tuner.

CREATE TABLE table ( pk bigint(20) NOT NULL AUTO_INCREMENT,
fk tinyint(3) unsigned DEFAULT '0', 
PRIMARY KEY (pk), KEY idx_fk (fk) USING BTREE ) 
ENGINE=InnoDB AUTO_INCREMENT=100380914 DEFAULT CHARSET=latin1

Материалы БД:

'have_innodb', 'YES' 'ignore_builtin_innodb', 'OFF' 'innodb_adaptive_hash_index', 'ON'    
'innodb_additional_mem_pool_size', '20971520' 'innodb_autoextend_increment', '8' 
'innodb_autoinc_lock_mode', '1' 'innodb_buffer_pool_size', '25769803776' 
'innodb_checksums', 'ON' 'innodb_commit_concurrency', '0',
'innodb_concurrency_tickets', '500' 'innodb_data_file_path',
'ibdata1:10M:autoextend' 'innodb_data_home_dir', '', 'innodb_doublewrite', 'ON'     
'innodb_fast_shutdown', '1' 'innodb_file_io_threads', '4' 
'innodb_file_per_table', 'OFF', 'innodb_flush_log_at_trx_commit', '1' 
'innodb_flush_method', '' 'innodb_force_recovery', '0' 'innodb_lock_wait_timeout', '50' 
'innodb_locks_unsafe_for_binlog', 'OFF' 'innodb_log_buffer_size', '8388608' 
'innodb_log_file_size', '26214400' 'innodb_log_files_in_group', '2' 
'innodb_log_group_home_dir', './' 'innodb_max_dirty_pages_pct', '90'     
'innodb_max_purge_lag', '0' 'innodb_mirrored_log_groups', '1' 'innodb_open_files', 
'300' 'innodb_rollback_on_timeout', 'OFF' 'innodb_stats_on_metadata', 'ON' 
'innodb_support_xa', 'ON' 'innodb_sync_spin_loops', '20' 'innodb_table_locks', 'ON' 
'innodb_thread_concurrency', '8' 'innodb_thread_sleep_delay', '10000'      
'innodb_use_legacy_cardinality_algorithm', 'ON'

Обновление '15: Я использовал тот же метод до сих пор с 600 миллионами строк и 640 000 новых строк в день. Он все еще работает нормально.