[#MDEV-2628] LP:1000051 - Query with simple join and ORDER BY takes thousands times longer when run with ICP

[MDEV-2628] LP:1000051 - Query with simple join and ORDER BY takes thousands times longer when run with ICP Created: 2012-05-16 Updated: 2015-02-02 Resolved: 2012-10-04
Status:	Closed
Project:	MariaDB Server
Component/s:	None
Affects Version/s:	None
Fix Version/s:	None

Type:

Bug

Priority:

Major

Reporter:

Elena Stepanova

Assignee:

Sergei Petrunia

Resolution:

Fixed

Votes:

Labels:

Launchpad

Attachments:

LPexportBug1000051.xml

LPexportBug1000051_A.data

Description

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

Comments

Comment by Elena Stepanova [ 2012-05-16 ]

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

Comment by Elena Stepanova [ 2012-05-16 ]

data file for the test case
LPexportBug1000051_A.data

Comment by Elena Stepanova [ 2012-05-16 ]

Re: Query with simple join and ORDER BY takes thousands times longer when run with ICP
The initial user's data can be found on FTP as lp-1000051.tar.gz. It's considerably bigger.

Comment by Sergei Petrunia [ 2012-05-18 ]

Re: Query with simple join and ORDER BY takes thousands times longer when run with ICP
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.

Comment by Sergei Petrunia [ 2012-05-18 ]

Re: Query with simple join and ORDER BY takes thousands times longer when run with ICP
Nope, reverse "range" scans also suffer from the same problem.

Comment by Elena Stepanova [ 2012-06-24 ]

Re: Query with simple join and ORDER BY takes thousands times longer when run with ICP
Fix released in 5.5.25 and will be in 5.3.8 when it is out

Comment by Rasmus Johansson (Inactive) [ 2012-09-18 ]

Launchpad bug id: 1000051

Comment by Ovais Tariq [ 2012-09-18 ]

Re: Query with simple join and ORDER BY takes thousands times longer when run with ICP
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)

Generated at Thu Feb 08 06:43:08 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.

[MDEV-2628] LP:1000051 - Query with simple join and ORDER BY takes thousands times longer when run with ICP Created: 2012-05-16 Updated: 2015-02-02 Resolved: 2012-10-04