[MDEV-8002] Ability to use index for order-by and covering index changes with type of join to small table Created: 2015-04-15  Updated: 2021-04-29

Status: Open
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.0
Fix Version/s: 10.2

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

Ubuntu 12.04, CentOS 5.11

Attachments: File orderby_index.sql.gz    
Issue Links:
PartOf
is part of MDEV-8306 Complete cost-based optimization for ... Stalled

 Description   

In join of 4 tables, optimizer won't use covering index with suitable ordering on first table in case join order of last two tables uses index/table scan on one of them instead of eq_ref - that table has only 2 rows, so optimizer does not seem to feel need to use eq_ref on it, but then resulting plan needs filesort. Happens with and without "LIMIT 3".

explain
 
SELECT evaluation, t.ticket_id
 
FROM ticket_game_result g
 
JOIN ticket t ON g.ticket_id=t.ticket_id
 
JOIN uzivatel u ON (t.user_id=u.user_id)
 
JOIN mena c ON c.mena_id=u.mena_id
 
WHERE (g.game_id = 2) AND (g.cancelled = 0) AND (t.vyplacen_date > '2013-06-31 22:00:00')
 
ORDER BY `g`.`evaluation` DESC LIMIT 3;
 

+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 
| id   | select_type | table | type   | possible_keys                                  | key     | key_len | ref                       | rows | Extra                                           |
 
+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | g     | ref    | PRIMARY,fk__ticket_game_result__ticket_id,eval | PRIMARY | 2       | const                     |   54 | Using where; Using temporary; Using filesort    |
 
|    1 | SIMPLE      | t     | eq_ref | PRIMARY,FK_ticket_1,vyplacen_date              | PRIMARY | 8       | orderby_index.g.ticket_id |    1 | Using where                                     |
 
|    1 | SIMPLE      | c     | index  | PRIMARY                                        | PRIMARY | 2       | NULL                      |    2 | Using index; Using join buffer (flat, BNL join) |
 
|    1 | SIMPLE      | u     | eq_ref | PRIMARY,FK_mena                                | PRIMARY | 4       | orderby_index.t.user_id   |    1 | Using where                                     |
 
+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 

explain
 
SELECT evaluation, t.ticket_id
 
FROM ticket_game_result g IGNORE INDEX (PRIMARY)
 
JOIN ticket t ON g.ticket_id=t.ticket_id
 
JOIN uzivatel u ON (t.user_id=u.user_id)
 
JOIN mena c ON c.mena_id=u.mena_id
 
WHERE (g.game_id = 2) AND (g.cancelled = 0) AND (t.vyplacen_date > '2013-06-31 22:00:00')
 
ORDER BY `g`.`evaluation` DESC LIMIT 3;
 

+------+-------------+-------+--------+----------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 
| id   | select_type | table | type   | possible_keys                          | key     | key_len | ref                       | rows | Extra                                           |
 
+------+-------------+-------+--------+----------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | g     | ref    | fk__ticket_game_result__ticket_id,eval | eval    | 3       | const,const               |   54 | Using index; Using temporary; Using filesort    |
 
|    1 | SIMPLE      | t     | eq_ref | PRIMARY,FK_ticket_1,vyplacen_date      | PRIMARY | 8       | orderby_index.g.ticket_id |    1 | Using where                                     |
 
|    1 | SIMPLE      | c     | index  | PRIMARY                                | PRIMARY | 2       | NULL                      |    2 | Using index; Using join buffer (flat, BNL join) |
 
|    1 | SIMPLE      | u     | eq_ref | PRIMARY,FK_mena                        | PRIMARY | 4       | orderby_index.t.user_id   |    1 | Using where                                     |
 
+------+-------------+-------+--------+----------------------------------------+---------+---------+---------------------------+------+-------------------------------------------------+
 

explain
 
SELECT evaluation, t.ticket_id
 
FROM ticket_game_result g
 
JOIN ticket t ON g.ticket_id=t.ticket_id
 
JOIN uzivatel u ON (t.user_id=u.user_id)
 
STRAIGHT_JOIN mena c ON c.mena_id=u.mena_id
 
WHERE (g.game_id = 2) AND (g.cancelled = 0) AND (t.vyplacen_date > '2013-06-31 22:00:00')
 
ORDER BY `g`.`evaluation` DESC LIMIT 3;
 

+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------+
 
| id   | select_type | table | type   | possible_keys                                  | key     | key_len | ref                       | rows | Extra       |
 
+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------+
 
|    1 | SIMPLE      | g     | ref    | PRIMARY,fk__ticket_game_result__ticket_id,eval | eval    | 3       | const,const               |   54 | Using where |
 
|    1 | SIMPLE      | t     | eq_ref | PRIMARY,FK_ticket_1,vyplacen_date              | PRIMARY | 8       | orderby_index.g.ticket_id |    1 | Using where |
 
|    1 | SIMPLE      | u     | eq_ref | PRIMARY,FK_mena                                | PRIMARY | 4       | orderby_index.t.user_id   |    1 |             |
 
|    1 | SIMPLE      | c     | eq_ref | PRIMARY                                        | PRIMARY | 2       | orderby_index.u.mena_id   |    1 | Using index |
 
+------+-------------+-------+--------+------------------------------------------------+---------+---------+---------------------------+------+-------------+

Attached is testing dump of 100KB database showing the behavior - on our production server there was one more trouble with plan changing when otherwise unused index is ignored, but I was not able to replicate that on this smaller dataset and I have seen some similar issue already.
Dump contains analyze table for all 4 tables, because without it after import I was not able to replicate. Plans were totally different.

 Comments   
Comment by Elena Stepanova [ 2015-04-15 ]

Note: Looks pretty much the same on MySQL 5.6

MySQL [test]> explain
 
    -> SELECT evaluation, t.ticket_id
 
    -> FROM ticket_game_result g IGNORE INDEX (PRIMARY)
 
    -> JOIN ticket t ON g.ticket_id=t.ticket_id
 
    -> JOIN uzivatel u ON (t.user_id=u.user_id)
 
    -> JOIN mena c ON c.mena_id=u.mena_id
 
    -> WHERE (g.game_id = 2) AND (g.cancelled = 0) AND (t.vyplacen_date > '2013-06-31 22:00:00')
 
    -> ORDER BY `g`.`evaluation` DESC LIMIT 3;
 
+----+-------------+-------+--------+----------------------------------------+---------+---------+------------------+------+----------------------------------------------------+
 
| id | select_type | table | type   | possible_keys                          | key     | key_len | ref              | rows | Extra                                              |
 
+----+-------------+-------+--------+----------------------------------------+---------+---------+------------------+------+----------------------------------------------------+
 
|  1 | SIMPLE      | g     | ref    | fk__ticket_game_result__ticket_id,eval | eval    | 3       | const,const      |   54 | Using index; Using temporary; Using filesort       |
 
|  1 | SIMPLE      | c     | index  | PRIMARY                                | PRIMARY | 2       | NULL             |    2 | Using index; Using join buffer (Block Nested Loop) |
 
|  1 | SIMPLE      | t     | eq_ref | PRIMARY,FK_ticket_1,vyplacen_date      | PRIMARY | 8       | test.g.ticket_id |    1 | Using where                                        |
 
|  1 | SIMPLE      | u     | eq_ref | PRIMARY,FK_mena                        | PRIMARY | 4       | test.t.user_id   |    1 | Using where                                        |
 
+----+-------------+-------+--------+----------------------------------------+---------+---------+------------------+------+----------------------------------------------------+
 
4 rows in set (0.00 sec)
 
 
 
MySQL [test]> explain
 
    -> SELECT evaluation, t.ticket_id
 
    -> FROM ticket_game_result g
 
    -> JOIN ticket t ON g.ticket_id=t.ticket_id
 
    -> JOIN uzivatel u ON (t.user_id=u.user_id)
 
    -> STRAIGHT_JOIN mena c ON c.mena_id=u.mena_id
 
    -> WHERE (g.game_id = 2) AND (g.cancelled = 0) AND (t.vyplacen_date > '2013-06-31 22:00:00')
 
    -> ORDER BY `g`.`evaluation` DESC LIMIT 3;
 
+----+-------------+-------+--------+------------------------------------------------+---------+---------+------------------+------+--------------------------+
 
| id | select_type | table | type   | possible_keys                                  | key     | key_len | ref              | rows | Extra                    |
 
+----+-------------+-------+--------+------------------------------------------------+---------+---------+------------------+------+--------------------------+
 
|  1 | SIMPLE      | g     | ref    | PRIMARY,fk__ticket_game_result__ticket_id,eval | eval    | 3       | const,const      |   54 | Using where; Using index |
 
|  1 | SIMPLE      | t     | eq_ref | PRIMARY,FK_ticket_1,vyplacen_date              | PRIMARY | 8       | test.g.ticket_id |    1 | Using where              |
 
|  1 | SIMPLE      | u     | eq_ref | PRIMARY,FK_mena                                | PRIMARY | 4       | test.t.user_id   |    1 | NULL                     |
 
|  1 | SIMPLE      | c     | eq_ref | PRIMARY                                        | PRIMARY | 2       | test.u.mena_id   |    1 | Using index              |
 
+----+-------------+-------+--------+------------------------------------------------+---------+---------+------------------+------+--------------------------+
 
4 rows in set (0.00 sec)
 
 
 
MySQL [test]> select @@version;
 
+--------------+
 
| @@version    |
 
+--------------+
 
| 5.6.24-debug |
 
+--------------+
 
1 row in set (0.00 sec)

Comment by Elena Stepanova [ 2015-04-15 ]

jkavalik,

Did you check the performance impact on your real-life data?

Comment by Jiri Kavalik [ 2015-04-15 ]

Last time I checked on MySQL was 5.1..

elenst
On real data:
those with filesort run around 0.42s after warming up - on first run after some time I have seen 5 secs
the one without filesort (straight_join) are mostly under 0.03s

Comment by Elena Stepanova [ 2015-04-15 ]

Assigning to psergey for further consideration.

Comment by Varun Gupta (Inactive) [ 2020-01-29 ]

With the ORDER BY LIMIT optimization in MDEV-8306, the plan now pick an ordered index scan.
The explain shows

+------+-------------+-------+--------+---------------+---------+---------+------------------+------+--------------------------+
 
| id   | select_type | table | type   | possible_keys | key     | key_len | ref              | rows | Extra                    |
 
+------+-------------+-------+--------+---------------+---------+---------+------------------+------+--------------------------+
 
|    1 | SIMPLE      | g     | range  | NULL          | eval    | 3       | NULL             | 2    | Using where; Using index |
 
|    1 | SIMPLE      | t     | eq_ref | NULL          | PRIMARY | 8       | test.g.ticket_id | 1    | Using where              |
 
|    1 | SIMPLE      | u     | eq_ref | NULL          | PRIMARY | 4       | test.t.user_id   | 1    |                          |
 
|    1 | SIMPLE      | c     | eq_ref | NULL          | PRIMARY | 2       | test.u.mena_id   | 1    | Using index              |
 
+------+-------------+-------+--------+---------------+---------+---------+------------------+------+--------------------------+
 
4 rows in set (0.001 sec)

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