Mysql "SELECT COUNT(*)" 很慢，即使有 where 子句

我正试图找出如何在MySQL中优化一个非常慢的查询(这不是我设计的):

SELECT COUNT(*) FROM change_event me WHERE change_event_id > '1212281603783391';
+----------+
| COUNT(*) |
+----------+
|  3224022 |
+----------+
1 row in set (1 min 0.16 sec)

将其与完整计数进行比较:

select count(*) from change_event;
+----------+
| count(*) |
+----------+
|  6069102 |
+----------+
1 row in set (4.21 sec)

解释声明在这里对我没有帮助:

 explain SELECT COUNT(*) FROM change_event me WHERE change_event_id > '1212281603783391'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: me
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 4120213
        Extra: Using where; Using index
1 row in set (0.00 sec)

好吧，它仍然认为需要大约400万个条目才能计数，但我可以更快地计算文件中的行数！我不明白MySQL为什么要花这么长时间.

以下是表格定义:

CREATE TABLE `change_event` (
  `change_event_id` bigint(20) NOT NULL default '0',
  `timestamp` datetime NOT NULL,
  `change_type` enum('create','update','delete','noop') default NULL,
  `changed_object_type` enum('Brand','Broadcast','Episode','OnDemand') NOT NULL,
  `changed_object_id` varchar(255) default NULL,
  `changed_object_modified` datetime NOT NULL default '1000-01-01 00:00:00',
  `modified` datetime NOT NULL default '1000-01-01 00:00:00',
  `created` datetime NOT NULL default '1000-01-01 00:00:00',
  `pid` char(15) default NULL,
  `episode_pid` char(15) default NULL,
  `import_id` int(11) NOT NULL,
  `status` enum('success','failure') NOT NULL,
  `xml_diff` text,
  `node_digest` char(32) default NULL,
  PRIMARY KEY  (`change_event_id`),
  KEY `idx_change_events_changed_object_id` (`changed_object_id`),
  KEY `idx_change_events_episode_pid` (`episode_pid`),
  KEY `fk_import_id` (`import_id`),
  KEY `idx_change_event_timestamp_ce_id` (`timestamp`,`change_event_id`),
  KEY `idx_change_event_status` (`status`),
  CONSTRAINT `fk_change_event_import` FOREIGN KEY (`import_id`) REFERENCES `import` (`import_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

版本:

$ mysql --version
mysql  Ver 14.12 Distrib 5.0.37, for pc-solaris2.8 (i386) using readline 5.0

我有什么明显的遗漏吗？(是的，我已经try 过" Select 计数(更改事件id)"，但没有性能差异).