Bug #28554 Optimizer wrongly prefers index for (col = value) over (PK <= value)

Description:
In some cases optimizer wrongly assumes that index on column used in (column = value) condition is better than primary key used in (pk <= other_value) condition. For example:

mysql> explain select count(*) from market2centralinqueueobject where ordercounter <= 300000 and receivestate = 5;
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
| id | select_type | table                       | type | possible_keys       |
key         | key_len | ref   | rows | Extra                    |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | market2centralinqueueobject | ref  | PRIMARY,IDXA_status |
IDXA_status | 3       | const | 1636 | Using where; Using index |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
1 row in set (0.01 sec)

While:

mysql> select count(*) from market2centralinqueueobject where ordercounter <= 300000;
+----------+
| count(*) |
+----------+
|     1213 |
+----------+
1 row in set (0.00 sec)

mysql> select count(*) from market2centralinqueueobject where receivestate = 5;
+----------+
| count(*) |
+----------+
|     4081 |
+----------+
1 row in set (0.01 sec)

In practice this often leads to wery slow query execution on large data sets.

FORCE INDEX(PRIMARY) workaround wors, but it is not always possible/easy to change queries (that may be generated by some frontend).

How to repeat:
Create the following table:

CREATE TABLE `market2centralinqueueobject` (
   `ackId` bigint(20) default NULL,
   `businessEventId` int(11) default NULL,
   `countryNumber` smallint(6) default NULL,
   `created` varchar(26) default NULL,
   `marketNumber` smallint(6) default NULL,
   `orderCounter` bigint(20) NOT NULL default '0',
   `payload` longblob,
   `priority` smallint(6) default NULL,
   `receiveState` smallint(6) default NULL,
   `wholeId` bigint(20) default NULL,
   `zID` bigint(20) default NULL,
   PRIMARY KEY  (`orderCounter`),   
   UNIQUE KEY `ackId` (`ackId`,`marketNumber`,`countryNumber`),
   KEY `IDX_M2C_PROCESSSELECT` (`marketNumber`,`countryNumber`,`receiveState`,`priority`,`orderCounter`),
   KEY `IDXA_businessEventId` (`businessEventId`),   
   KEY `IDXA_marketNumber` (`marketNumber`),
   KEY `IDXA_status` (`receiveState`,`marketNumber`,`countryNumber`,`created`), 
   KEY `IDXA_zID` (`zID`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Populate it with some (semi-random) data (see also file with my data uploaded):

insert into market2centralinqueueobject(ordercounter, receivestate)
values(rand()*1000000, 5);

insert ignore into market2centralinqueueobject(ordercounter, receivestate) select rand()*1000000, receivestate from market2centralinqueueobject;

...

mysql> insert ignore into market2centralinqueueobject(ordercounter, receivestat
e) select rand()*1000000, receivestate from market2centralinqueueobject;
Query OK, 256 rows affected (0.15 sec)
Records: 256  Duplicates: 0  Warnings: 0

mysql> explain select count(*) from market2centralinqueueobject where ordercoun
ter <= 100 and receivestate= 5;
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
| id | select_type | table                       | type  | possible_keys       |
 key     | key_len | ref  | rows | Extra       |
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
|  1 | SIMPLE      | market2centralinqueueobject | range | PRIMARY,IDXA_status |
 PRIMARY | 8       | NULL |    1 | Using where |
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
1 row in set (0.01 sec)

OK, reasonable index is used for now, let's continue:

insert ignore into market2centralinqueueobject(ordercounter, receivestate) values(0, 3);

insert ignore into market2centralinqueueobject(ordercounter, receivestate) select rand()*1000000, receivestate from market2centralinqueueobject;

insert ignore into market2centralinqueueobject(ordercounter, receivestate) select rand()*1000000, receivestate from market2centralinqueueobject;
...

Let's stop with this number of rows:

mysql> select count(*) from market2centralinqueueobject;
+----------+
| count(*) |
+----------+
|     4089 |
+----------+
1 row in set (0.01 sec)

Now:

mysql> explain select count(*) from market2centralinqueueobject where ordercoun
ter <= 100 and receivestate= 5;        
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
| id | select_type | table                       | type  | possible_keys       |
 key     | key_len | ref  | rows | Extra       |
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
|  1 | SIMPLE      | market2centralinqueueobject | range | PRIMARY,IDXA_status |
 PRIMARY | 8       | NULL |    2 | Using where |
+----+-------------+-----------------------------+-------+---------------------+
---------+---------+------+------+-------------+
1 row in set (0.00 sec)

OK, proper index is used, but:

mysql> explain select count(*) from market2centralinqueueobject where ordercoun
ter <= 300000 and receivestate= 5;
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
| id | select_type | table                       | type | possible_keys       |
key         | key_len | ref   | rows | Extra                    |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | market2centralinqueueobject | ref  | PRIMARY,IDXA_status |
IDXA_status | 3       | const | 1636 | Using where; Using index |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
1 row in set (0.01 sec)

Now, when < 300000 is used optimizer, for some unknown reason, decided that using index that will give all rows but one is better! This is a bug, because

mysql> select count(*) from market2centralinqueueobject where ordercounter <= 300000;
+----------+
| count(*) |
+----------+
|     1213 |
+----------+
1 row in set (0.00 sec)

mysql> select count(*) from market2centralinqueueobject where receivestate= 5;
+----------+
| count(*) |
+----------+
|     4081 |
+----------+
1 row in set (0.01 sec)

optimizer used index that selects 3+ times more rows than needed! And ANALYZE does not help:

mysql> analyze table market2centralinqueueobject;
+----------------------------------+---------+----------+----------+
| Table                            | Op      | Msg_type | Msg_text |
+----------------------------------+---------+----------+----------+
| test.market2centralinqueueobject | analyze | status   | OK       |
+----------------------------------+---------+----------+----------+
1 row in set (0.03 sec)

mysql> explain select count(*) from market2centralinqueueobject where ordercoun
ter <= 300000 and receivestate= 5;
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
| id | select_type | table                       | type | possible_keys       |
key         | key_len | ref   | rows | Extra                    |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | market2centralinqueueobject | ref  | PRIMARY,IDXA_status |
IDXA_status | 3       | const | 2362 | Using where; Using index |
+----+-------------+-----------------------------+------+---------------------+-
------------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

Suggested fix:
Calculate costs properly? Use histograms? Give a preference to PRIMARY KEY, at least, for InnoDB tables?

Dump of a table used for testing

Attachment: bug28554.sql.gz (application/gzip, text), 16.92 KiB.

Investigation
-------------

With the query and the dataset provided by Valeriy I observe the following:

test_quick_select()
{
  PRIMARY: 
    E(#rows)= 1496
    cpu_cost= rows/TIME_FOR_COMPARE = 299.2
    file->read_time() = 4.45
    cost = 303.56

  IDXA_status:
    E(#rows)= 2075
    cpu_cost= 415
    get_index_only_read_time()=12.6
    cost = 427.6

  returned quick range select over PRIMARY key, cost=303.56
}

best_access_path()
{
  consider doing 'ref' scan over IDXA_status, 1 keypart. 
   - reuse the range analyzer's estimate of 2075 rows.
   - the cost is (using index tree only) 12.6 (like get_index_only_read_time
                                               in test_quick_select)
   
  consider using the quick selects. 303>59, so we decide using 'ref' access
}
  
This is how we end up choosing IDXA_status.

Correction, this line:
<<
  consider using the quick selects. 303>59, so we decide using 'ref' access
>>
is incorrect, we do not compare 303 with 59.

ref(IDXA_status) access cost:
  best_time= (tmp=12.59) + (records=2075) /(TIME_FOR_COMPARE=5)= 427.59
  best= 12.59
  best_records=2075

range(PRIMARY) access cost:
  tmp= record_count *
       (s->quick->read_time +
        (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE
       ) =
     = 1 * ( 303.56 + (1496 - 1496 * 0.75) / 5 ) = 
     = 1 * ( 303.56 + 74.75) = 378.36

comparison range vs. ref: 
  range:
    tmp + rnd_records/5 = 378.36 + 224.4 = 602.76
    (actually this is s->quick->read_time + s->found_records / TIME_FOR_COMPARE)

  ref:
    best + records/ 5 = 12.59 + 2075 / 5 = 12.59 + 415 = 427.59

That is, for the final comparisons we have those numbers:

cost(range(PRIMARY))= 
  (file->read_time(range) = 4.45)   + 
  (#rows_in_range/TIME_FOR_COMPARE = 299.2) +  
  (#rows_in_range/TIME_FOR_COMPARE = 299.2) = 

  = 602.76 
 
cost(ref(IDXA_status))=
  (index_only_read_time(range) = 12.6)  + 
  (#rows_in_range/TIME_FOR_COMPARE = 415) =

  = 427.59

Here we see that we add the same value twice for the cost(range(PRIMARY)).

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/32343

ChangeSet@1.2562, 2007-08-10 05:27:32+04:00, sergefp@mysql.com +6 -0
  BUG#28554: Optimizer wrongly prefers index for (key1=val1) over (PK<=val2)
  Make order in full/quick table scan calculation part of best_access_path():
   - Do not have costs of condition evaluation added twice for quick
     select-based scans.
   - Do take join buffering into account for quick select scans
   - Correctly use the found_constraint heuristic.
  [this is a preliminary commit]