Query with simple join and ORDER BY takes thousands times longer when run with ICP

[Elena Stepanova]

Initially reported in the knowledge base: http://kb.askmonty.org/en/index-pushdown-bug-or-side-effect

The following query

SELECT SQL_NO_CACHE *
FROM A, B
WHERE b1 = a1
AND a3 = "3"
ORDER BY a2 DESC;

takes much longer when it's run with index_condition_pushdown=on (current default) than without it.
Actual values can vary depending on the machine, but as an example, on my local box on the test data it takes ~ 0.1 sec with ICP=off and 10+ sec with ICP=on.

bzr version-info
revision-id: <email address hidden>
date: 2012-05-15 08:31:07 +0300
revno: 3523

Also reproducible on MariaDB 5.5 (revno 3403) and MySQL trunk (revno 3827).

EXPLAIN:

id select_type table type possible_keys key key_len ref rows filtered Extra
1 SIMPLE A ref a3,a3_2 a3_2 2 const 2540 100.00 Using index condition; Using where
1 SIMPLE B eq_ref PRIMARY PRIMARY 4 test.A.a1 1 100.00 Using index
Warnings:
Note 1003 select sql_no_cache `test`.`A`.`a1` AS `a1`,`test`.`A`.`a2` AS `a2`,`test`.`A`.`a3` AS `a3`,`test`.`B`.`b1` AS `b1` from `test`.`A` join `test`.`B` where ((`test`.`A`.`a3` = '3') and (`test`.`B`.`b1` = `test`.`A`.`a1`)) order by `test`.`A`.`a2` desc

Full optimizer_switch:
index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=off,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=off,table_elimination=on

# Test case
# please note that the test case requires the data file A.data,
# it is attached

CREATE TABLE A (
  a1 INT(6),
  a2 DOUBLE,
  a3 ENUM('0','1','2','3'),
  KEY(a3),
  KEY(a3,a2)
) ENGINE=MyISAM;

LOAD DATA LOCAL INFILE 'A.data' INTO TABLE A;

CREATE TABLE B (
  b1 INT NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (b1)
) ENGINE=MyISAM;

INSERT INTO B VALUES
  (NULL),(NULL),(NULL),(NULL),(NULL);
INSERT INTO B SELECT NULL FROM B t2a, B t2b, B t2c;
INSERT INTO B SELECT NULL FROM B t2a, B t2b;
DELETE FROM B ORDER BY RAND() LIMIT 14000;

SELECT SQL_NO_CACHE *
FROM A, B
WHERE b1 = a1
AND a3 = "3"
ORDER BY a2 DESC;

# End of test case

[Elena Stepanova (elenst)]

The initial user's data can be found on FTP as lp-1000051.tar.gz. It's considerably bigger.

[Sergey Petrunia (sergefp)]

Preliminary investigation results:

The problem is caused by a combination of
* ref access
* Pushed Index Condition
* ORDER BY DESC
When these three are employed together, SQL layer will make the following handler calls:

-

h->ha_index_read_map( ..., HA_READ_PREFIX_LAST);
  h->index_prev();
  h->index_prev();
  ...

When we enter index_prev() call, we don't know where we should stop scanning (that is, SQL layer and join_read_prev_same() knows that we're only interested in records with t.key=const, but this information is not passed down the storage engine).

The storage engine starts walking the index in reverse direction. If all index tuples fail the index condition, it will continue walking until it reaches the start of the index.

We don't get this problem with normal index scans, because they make these calls:
h->index_read_map(...)
  h->index_next_same();
  h->index_next_same();
  ...
note it's using index_next_same(), not index_next(). There is no index_prev_same() call, though.

We also don't get this problem with forward range non-equality scans because we use read_range_first()/read_range_next() functions which set h->end_range which is checked by the ICP function.

I'll need to check what happens with reverse range scans.

[Sergey Petrunia (sergefp)]

Nope, reverse "range" scans also suffer from the same problem.

[Elena Stepanova (elenst)]

Fix released in 5.5.25 and will be in 5.3.8 when it is out

[Ovais Tariq (ovais-tariq)]

I cannot reproduce this bug on MySQL 5.6.6-m9 and MariaDB 5.5.23 because the test data here (https://bugs.launchpad.net/maria/+bug/1000051/+attachment/3148604/+files/A.data) and the test query does not seem to force MySQL/MariaDB to use ICP, even if I change the sort order to ASC.

MariaDB 5.5.23 EXPLAIN output:
MariaDB [test]> EXPLAIN SELECT SQL_NO_CACHE * FROM A, B WHERE b1 = a1 AND a3 = "3" ORDER BY a2 DESC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: A
         type: ref
possible_keys: a3,a3_2
          key: a3_2
      key_len: 2
          ref: const
         rows: 731
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: B
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.A.a1
         rows: 1
        Extra: Using index
2 rows in set (0.00 sec)

MariaDB [test]> EXPLAIN SELECT SQL_NO_CACHE * FROM A, B WHERE b1 = a1 AND a3 = "3" ORDER BY a2 ASC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: A
         type: ref
possible_keys: a3,a3_2
          key: a3_2
      key_len: 2
          ref: const
         rows: 731
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: B
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.A.a1
         rows: 1
        Extra: Using index
2 rows in set (0.00 sec)

MySQL 5.6.6-m9 EXPLAIN output:
mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM A, B WHERE b1 = a1 AND a3 = "3" ORDER BY a2 DESC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: A
         type: ref
possible_keys: a3,a3_2
          key: a3_2
      key_len: 2
          ref: const
         rows: 731
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: B
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.A.a1
         rows: 1
        Extra: Using index
2 rows in set (0.00 sec)

mysql> EXPLAIN SELECT SQL_NO_CACHE * FROM A, B WHERE b1 = a1 AND a3 = "3" ORDER BY a2 ASC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: A
         type: ref
possible_keys: a3,a3_2
          key: a3_2
      key_len: 2
          ref: const
         rows: 731
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: B
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.A.a1
         rows: 1
        Extra: Using index
2 rows in set (0.00 sec)