Bug #19271 innodb optimizer prefers primary over secondary indexes for count(*)
Submitted: 22 Apr 2006 5:24 Modified: 18 Aug 2016 8:22
Reporter: Dan Nelson Email Updates:
Status: Duplicate Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S4 (Feature request)
Version:5.0.21-BK, 5.0.20 OS:Any
Assigned to: Assigned Account CPU Architecture:Any

[22 Apr 2006 5:24] Dan Nelson
Description:
When running a simple "SELECT COUNT(*) FROM innodb_table" query, the optimizer will choose to scan the smallest index (by key length), but because the table data is stored in the primary index, this equates to a full table scan if the optimizer decides to use it.

If the following script is run with mysql -vvv to show query timings, I get:

explain select count(*) from test use index (int_k)
+----+-------------+-------+-------+---------------+-------+---------+------+--------+-------------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref  | rows   | Extra       |
+----+-------------+-------+-------+---------------+-------+---------+------+--------+-------------+
| 1  | SIMPLE      | test  | index |               | int_k | 4       |      | 300027 | Using index |
+----+-------------+-------+-------+---------------+-------+---------+------+--------+-------------+

explain select count(*) from test
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows   | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+
| 1  | SIMPLE      | test  | index |               | PRIMARY | 4       |      | 300027 | Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+

select count(*) from test use index (int_k)
+----------+
| count(*) |
+----------+
| 300000   |
+----------+
1 row in set (0.88 sec)

select count(*) from test
+----------+
| count(*) |
+----------+
| 300000   |
+----------+
1 row in set (7.95 sec)

How to repeat:
drop table if exists test;
create table test 
(
  id int not null,
  int_k int not null,
  data1 varchar(255) not null,
  data2 varchar(255) not null,
  primary key (id),
  key (int_k)
) ENGINE=innodb;
drop procedure if exists populate;
delimiter //
create procedure populate()
begin
  declare i int;

  set i = 0;
  start transaction;
  while i < 300000 do
    insert into test (id, int_k, data1, data2) 
      values (i, i, repeat("-", 250), repeat("-", 250));
    set i = i + 1;
    if i % 1000 = 0 then
      start transaction;
    end if;
  end while;
  commit;
end;
//
delimiter ;
call populate();
drop procedure populate;
explain select count(*) from test use index (int_k);
explain select count(*) from test;
select count(*) from test use index (int_k);
select count(*) from test;

Suggested fix:
The optimizer should probably take into account that, for innodb, the effective cost of scanning a primary index is (primarylen+rowlen), and the cost of scanning a secondary index is (secondarylen+primarylen).
[22 Apr 2006 6:38] Heikki Tuuri
Dan,

remember that a secondary index is usually fragmented, and requires random disk I/O. Random disk I/O can read in about 2 MB/s. But the PRIMARY index usually is in order and can be read in with sequential I/O, which typically is 30 MB/s. Thus, scanning the PRIMARY index is a safer bet.

Since the minimum record size of InnoDB is about 20 bytes, and the fillfactor of a secondary index is typically 70 %, we can calculate that if the row length is > 15 * 1.5 * 20 = 450 bytes, then scanning the secondary index would probably be a better option.

Regards,

Heikki
[22 Apr 2006 7:04] Dan Nelson
I used a stripped-down example to demonstrate, but in the table I am having problems with (archive of the last 7 days of email for spam analysis), the table is 1gb with 100000 rows, the average rowlength is 6000, and a full table scan takes 2 minutes at 20MB/sec.  A scan of an integer secondary index takes under 5 seconds, and mysql still prefers to scan using the primary integer index.

I'm not sure that secondary indexes are any less fragmented than the primary index, unless your primary index is an auto-increment and you never delete records.  If mysql had a way of sequentially walking the primary index blocks without traversing the tree structure, that would certainly tip the performance scales toward full table scans.
[22 Apr 2006 13:16] Valeriy Kravchuk
Verified just as described on 5.0.21-BK ():

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 3 to server version: 5.0.21

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> drop table if exists test;
Query OK, 0 rows affected (0.01 sec)

mysql> create table test
    -> (
    ->   id int not null,
    ->   int_k int not null,
    ->   data1 varchar(255) not null,
    ->   data2 varchar(255) not null,
    ->   primary key (id),
    ->   key (int_k)
    -> ) ENGINE=innodb;
Query OK, 0 rows affected (0.06 sec)

mysql> drop procedure if exists populate;
Query OK, 0 rows affected, 1 warning (0.02 sec)

mysql> delimiter //
mysql> create procedure populate()
    -> begin
    ->   declare i int;
    ->
    ->   set i = 0;
    ->   start transaction;
    ->   while i < 300000 do
    ->     insert into test (id, int_k, data1, data2)
    ->       values (i, i, repeat("-", 250), repeat("-", 250));
    ->     set i = i + 1;
    ->     if i % 1000 = 0 then
    ->       start transaction;
    ->     end if;
    ->   end while;
    ->   commit;
    -> end;
    -> //
Query OK, 0 rows affected (0.01 sec)

mysql> call populate()//
Query OK, 0 rows affected (1 min 11.32 sec)

mysql> drop procedure populate//
Query OK, 0 rows affected (0.12 sec)

mysql> delimiter ;
mysql> explain select count(*) from test use index (int_k)\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
         type: index
possible_keys: NULL
          key: int_k
      key_len: 4
          ref: NULL
         rows: 300025
        Extra: Using index
1 row in set (0.08 sec)

mysql> explain select count(*) from test\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 300025
        Extra: Using index
1 row in set (0.00 sec)

mysql> select count(*) from test use index (int_k);
+----------+
| count(*) |
+----------+
|   300000 |
+----------+
1 row in set (0.32 sec)

mysql> select count(*) from test;
+----------+
| count(*) |
+----------+
|   300000 |
+----------+
1 row in set (7.52 sec)

Whatever the reason, this difference in run time in such a simple case is a real performance problem. Cost of sequential read of pages vs. random read of pages should be taken into account by the optimizer like, say, in Oracle, as well as _a total number of pages to be read_.
[2 May 2006 2:07] Heikki Tuuri
Dan, Valeri,

in the example table, the secondary index is inserted into in a perfect order! That is very unusual. Normally the secondary index would be fragmented, causing random disk I/O, and the scan would be slower than in the primary index.

I am changing this to a feature request: keep 'clustering ratio' statistics on a secondary index and do the scan there if the order is almost the same as in the primary index. I doubt this feature will ever be implemented, though.

Regards,

Heikki
[17 Jul 2010 14:52] Dan Nelson
The fix for bug 39653 also fixes this bug. "select count(*) from test" in the example now uses the secondary key.
[17 Aug 2016 21:34] Sveta Smirnova
Confirming Dan: bug fixed long ago, should be in "Closed" state.
[18 Aug 2016 8:05] MySQL Verification Team
Thank you Sveta, Dan for confirming.
Closing the bug for now as I confirmed on my end as well(confirmed with 5.5.51, 5.6.32 etc).

Regards,
Umesh
[18 Aug 2016 8:22] MySQL Verification Team
After checking internally, correcting/marking this as duplicate of Bug #39653