[MDEV-8361] ORDER BY optimizer doesnt recognize that NL-join produces the desired ordering Created: 2015-06-23  Updated: 2016-01-21

Status: Open
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 5.1.67, 5.2.14, 5.3.12, 5.5, 10.0, 10.1
Fix Version/s: 10.1

Type: Bug Priority: Major
Reporter: Sergei Petrunia Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 1
Labels: optimizer, order-by-optimization, upstream


 Description   

ORDER BY optimizer doesn't recognize that NL-join produces the required ordering. Originally reported here:https://www.facebook.com/MySQLatFacebook/posts/10153059170661696 ,
http://bugs.mysql.com/bug.php?id=77439.

create table a1 (a int, b int, primary key (a,b));
 
create table a2 (a int, b int, primary key (a,b));
 
insert into a1 values (1,2),(1,3),(1,4),(2,4),(2,5),(2,6);
 
insert into a2 values (2,1),(2,2),(4,1),(4,2),(6,1),(6,2);

Plan without ORDER BY:

MariaDB [j2]> explain select * from a1 join a2 on a1.b=a2.a;                                                                      
+------+-------------+-------+-------+---------------+---------+---------+---------+------+-------------+                         
| id   | select_type | table | type  | possible_keys | key     | key_len | ref     | rows | Extra       |                         
+------+-------------+-------+-------+---------------+---------+---------+---------+------+-------------+                         
|    1 | SIMPLE      | a1    | index | NULL          | PRIMARY | 8       | NULL    |    6 | Using index |                         
|    1 | SIMPLE      | a2    | ref   | PRIMARY       | PRIMARY | 4       | j2.a1.b |    1 | Using index |                         
+------+-------------+-------+-------+---------------+---------+---------+---------+------+-------------+
 

MariaDB [j2]> explain select * from a1 join a2 on a1.b=a2.a order by a1.a, a1.b, a2.a, a2.b;
 
+------+-------------+-------+-------+---------------+---------+---------+---------+------+----------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref     | rows | Extra                                        |
 
+------+-------------+-------+-------+---------------+---------+---------+---------+------+----------------------------------------------+
 
|    1 | SIMPLE      | a1    | index | NULL          | PRIMARY | 8       | NULL    |    6 | Using index; Using temporary; Using filesort |
 
|    1 | SIMPLE      | a2    | ref   | PRIMARY       | PRIMARY | 4       | j2.a1.b |    1 | Using index                                  |
 
+------+-------------+-------+-------+---------------+---------+---------+---------+------+----------------------------------------------+

a1 table uses 'index', so rows are ordered by a1.a, a1.b. Then, ref access returns rows in the order of a2.a, a2.b. (a2.a is also equal to constant).

However, test_if_skip_sort_order only looks at one table when determining whether to do sorting.



 Comments   
Comment by Jan Lindström (Inactive) [ 2015-06-23 ]

Index is used if both index columns are provided (note that result is different):

explain select * from a1 join a2 on a1.b=a2.a and a1.a = a2.b;
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 
1	SIMPLE	a1	index	PRIMARY	PRIMARY	8	NULL	6	Using index
 
1	SIMPLE	a2	eq_ref	PRIMARY	PRIMARY	8	test.a1.b,test.a1.a	1Using index
 
explain select * from a1 join a2 on a1.b=a2.a and a1.a = a2.b order by a1.a, a1.b, a2.a, a2.b;
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 
1	SIMPLE	a1	index	PRIMARY	PRIMARY	8	NULL	6	Using index
 
1	SIMPLE	a2	eq_ref	PRIMARY	PRIMARY	8	test.a1.b,test.a1.a	1Using index

But even first column in primary key :

explain select * from a1 join a2 on a1.a=a2.a order by a1.a, a1.b, a2.a, a2.b;
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 
1	SIMPLE	a1	index	PRIMARY	PRIMARY	8	NULL	6	Using index; Using temporary; Using filesort
 
1	SIMPLE	a2	ref	PRIMARY	PRIMARY	4	test.a1.a	1	Using index

Generated at Thu Feb 08 07:26:35 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.