Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-8361

ORDER BY optimizer doesnt recognize that NL-join produces the desired ordering

        Details

          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.

            Gliffy Diagrams

              Attachments

                Activity

                Hide
                Permalink
                jplindst Jan Lindström added a comment - - edited

                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
                Show
                jplindst Jan Lindström added a comment - - edited 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

                  People

                  • Assignee:
                    Unassigned
                    Reporter:
                    psergey Sergei Petrunia
                  • Votes:
                    1 Vote for this issue
                    Watchers:
                    5 Start watching this issue

                    Dates

                    • Created:
                      Updated: