Well, for one thing, InnoDB doesn't keep an exact count of the exact number of records in a table, so I believe a COUNT(*) results in a full table scan (it's going to have to count the number of records in the primary key, but since that index is clustered, that's probably going to be as intensive as a full table scan).

MyISAM does keep an exact count of the number of records in a table, so COUNT(*) should be instantaneous (or near instantaneous, at least).

One thing you might try is a COUNT(x) where x is a column that is a non-primary key index and that always has a value.

I have an InnoDB table with over 300 million records on a server with an Athlon and one gig of RAM, and this works fine on it.

Does it use PRIMARY KEY to execute count(*) ? (Check explain)
If your primary key is fragmented it may be much faster to use other index to compute count which can be forced with force index clause.

---+------------+-----------+--------------+-------------+-- ---------+-------------+----------+--------+------+--------- ---+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------+------------+-----------+--------------+--------- ----+-----------+-------------+----------+--------+------+-- ----------+---------+
| history | 1 | history_1 | 1 | itemid | A | 18 | NULL | NULL | | BTREE | |
| history | 1 | history_1 | 2 | clock | A | 19762479 | NULL | NULL | | BTREE | |
+---------+------------+-----------+--------------+--------- ----+-----------+-------------+----------+--------+------+-- ----------+---------+
2 rows in set (0.93 sec)

mysql> describe history;
+--------+---------------------+------+-----+---------+----- --+
| Field | Type | Null | Key | Default | Extra |
+--------+---------------------+------+-----+---------+----- --+
| itemid | bigint(20) unsigned | NO | MUL | 0 | |
| clock | int(11) | NO | | 0 | |
| value | double(16,4) | NO | | 0.0000 | |
+--------+---------------------+------+-----+---------+----- --+

Thats the history table I'm working on.

Here are a few of the sql queries that are showing up in my slow query log:
select min(clock) from history where itemid=100000000017961;

Another table I'm seeing major problems with:
mysql> describe node_cksum;
+-----------+---------------------+------+-----+---------+-- -----+
| Field | Type | Null | Key | Default | Extra |
+-----------+---------------------+------+-----+---------+-- -----+
| cksumid | bigint(20) unsigned | NO | PRI | 0 | |
| nodeid | bigint(20) unsigned | NO | MUL | 0 | |
| tablename | varchar(64) | NO | | | |
| fieldname | varchar(64) | NO | | | |
| recordid | bigint(20) unsigned | NO | | 0 | |
| cksumtype | int(11) | NO | | 0 | |
| cksum | char(32) | NO | | | |
+-----------+---------------------+------+-----+---------+-- -----+
7 rows in set (0.00 sec)

mysql> show indexes from node_cksum;
+------------+------------+--------------------+------------ --+-------------+-----------+-------------+----------+------ --+------+------------+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+------------+------------+--------------------+------------ --+-------------+-----------+-------------+----------+------ --+------+------------+---------+
| node_cksum | 0 | PRIMARY | 1 | cksumid | A | 6776659 | NULL | NULL | | BTREE | |
| node_cksum | 1 | node_cksum_cksum_1 | 1 | nodeid | A | 18 | NULL | NULL | | BTREE | |
| node_cksum | 1 | node_cksum_cksum_1 | 2 | tablename | A | 18 | NULL | NULL | | BTREE | |
| node_cksum | 1 | node_cksum_cksum_1 | 3 | fieldname | A | 18 | NULL | NULL | | BTREE | |
| node_cksum | 1 | node_cksum_cksum_1 | 4 | recordid | A | 43440 | NULL | NULL | | BTREE | |
| node_cksum | 1 | node_cksum_cksum_1 | 5 | cksumtype | A | 43440 | NULL | NULL | | BTREE | |
+------------+------------+--------------------+------------ --+-------------+-----------+-------------+----------+------ --+------+------------+---------+
6 rows in set (1.19 sec)


query:
select curr.nodeid,curr.tablename,curr.recordid from node_cksum curr left join node_cksum prev on curr.tablename=prev.tablename and curr.recordid=prev.recordid and curr.fieldname=prev.fieldname and curr.nodeid=prev.nodeid and curr.cksumtype<>prev.cksumtype where prev.cksumid is null and curr.cksumtype=0;

This table has almost 7million records and the above query takes about 2300-3000 seconds to complete each time it is called.

I didn't write this code. In fact it comes from the zabbix monitor. I'm just trying to figure out how i can tune the system to run reasonable query responses )

Also, I ran the following
select count(itemid) from history;
trying to count an indexed item, and it's still running 15 minutes.

David