[MDEV-18094] Query with order by limit picking index scan over filesort Created: 2018-12-27  Updated: 2019-09-24  Resolved: 2019-09-21

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.1, 10.2, 10.3, 10.4
Fix Version/s: 10.2.28, 10.1.42, 10.3.19, 10.4.9

Type: Bug Priority: Major
Reporter: Varun Gupta (Inactive) Assignee: Varun Gupta (Inactive)
Resolution: Fixed Votes: 1
Labels: order-by-optimization

Issue Links:
Relates
relates to MDEV-8306 Complete cost-based optimization for ... Stalled
relates to MDEV-17761 Odd optimizer choice with ORDER BY LI... Stalled

 Description   

The dataset used

create table t0 (a int);
 
INSERT INTO t0 VALUES (0),(0),(0),(0),(2),(0),(0),(1),(1),(0);
 
 
 
CREATE TABLE t1 (
 
a int(11) DEFAULT NULL,
 
b int(11) DEFAULT NULL,
 
d int(11) DEFAULT NULL,
 
KEY b_3 (a,d),
 
KEY b_4 (a,b)
 
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
 
insert into t1 select A.a , B.a, C.a from t0 A, t0 B, t0 C, t0 D;


MariaDB [test]> select count(*) from t1;
 
+----------+
 
| count(*) |
 
+----------+
 
|    10000 |
 
+----------+

Now running the query without any limit

MariaDB [test]> analyze select a,b,d from t1 where a=1 and d=2 order by b;
 
+------+-------------+-------+------+---------------+------+---------+-------------+------+--------+----------+------------+-----------------------------+
 
| id   | select_type | table | type | possible_keys | key  | key_len | ref         | rows | r_rows | filtered | r_filtered | Extra                       |
 
+------+-------------+-------+------+---------------+------+---------+-------------+------+--------+----------+------------+-----------------------------+
 
|    1 | SIMPLE      | t1    | ref  | b_3,b_4       | b_3  | 10      | const,const |  200 | 200.00 |   100.00 |     100.00 | Using where; Using filesort |
 
+------+-------------+-------+------+---------------+------+---------+-------------+------+--------+----------+------------+-----------------------------+

Now running the query with limit= NUMBER OF TABLE RECORDS

MariaDB [test]> analyze select a,b,d from t1 where a=1 and d=2 order by b limit 10000;
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | r_rows  | filtered | r_filtered | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+
 
|    1 | SIMPLE      | t1    | range | b_3,b_4       | b_4  | 5       | NULL | 2000 | 2000.00 |    10.00 |      10.00 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+

This looks incorrect, we definitely have a problem with the cost model that changes ref access -> index(or range) by which we can do the ORDERING.

With limit = 2x table_records

MariaDB [test]> analyze select a,b,d from t1 where a=1 and d=2 order by b limit 20000;
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref         | rows  | r_rows   | filtered | r_filtered | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
|    1 | SIMPLE      | t1    | index | b_3,b_4       | b_4  | 10      | const,const | 10266 | 10000.00 |     1.95 |       2.00 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+



 Comments   
Comment by Varun Gupta (Inactive) [ 2018-12-27 ]

Some numbers from the optimizer trace

          {
 
            "reconsidering_access_paths_for_index_ordering": {
 
              "clause": "ORDER BY",
 
              "fanout": 1,
 
              "read_time": 82.001,
 
              "table_name": "t1",
 
              "rows_estimation": 200,
 
              "possible_keys": [
 
                {
 
                  "index": "b_3",
 
                  "can_resolve_order": false,
 
                  "cause": "not_usable_index_for_the query"
 
                },
 
                {
 
                  "index": "b_4",
 
                  "can_resolve_order": true,
 
                  "updated_limit": 10266,
 
                  "range_scan_time": 82,
 
                  "index_scan_time": 82,
 
                  "records": 2000,
 
                  "chosen": true
 
                }
 
              ]
 
            }
 
          }

Comment by Varun Gupta (Inactive) [ 2019-02-14 ]

With histograms

MariaDB [test]> set histogram_size=255;
 
Query OK, 0 rows affected (0.001 sec)
 
 
 
MariaDB [test]> analyze table t2 persistent for all;
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.t2 | analyze | status   | Engine-independent statistics collected |
 
| test.t2 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
2 rows in set (1.267 sec)
 
 
 
MariaDB [test]> analyze select a,b,c from t2 where a=1 and c=2 order by b limit 10000;
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref         | rows  | r_rows   | filtered | r_filtered | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
|    1 | SIMPLE      | t2    | index | a_c,a_b       | a_b  | 10      | const,const | 10000 | 10000.00 |     2.00 |       2.00 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
1 row in set (0.761 sec)

WITHOUT EITS

MariaDB [test]> set use_stat_tables= NEVER;
 
Query OK, 0 rows affected (0.000 sec)
 
 
 
MariaDB [test]> analyze select a,b,c from t2 where a=1 and c=2 order by b limit 10000;
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | r_rows  | filtered | r_filtered | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+
 
|    1 | SIMPLE      | t2    | range | a_c,a_b       | a_b  | 5       | NULL | 2000 | 2000.00 |    10.00 |      10.00 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+---------+----------+------------+-------------+
 
1 row in set (0.163 sec)

So even with histograms we are picking up index_scan over range_scan!

Comment by Sergei Petrunia [ 2019-02-14 ] 

MariaDB [test]> analyze select a,b,c from t2 where a=1 and c=2 order by b limit 10000;
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref         | rows  | r_rows   | filtered | r_filtered | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
|    1 | SIMPLE      | t2    | index | a_c,a_b       | a_b  | 10      | const,const | 10000 | 10000.00 |     2.00 |       2.00 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+-------------+-------+----------+----------+------------+-------------+
 
1 row in set (0.761 sec)

Looks like an invalid plan:

  • why would we use a full index scan (type=index) on index a_b when a ref(or range) access is possible, over a=1 ?
  • if type=index, why "ref" is non-empty? and how come it is "const,const" - we dont have anything for the second component?
Comment by Varun Gupta (Inactive) [ 2019-08-26 ]

Patch
http://lists.askmonty.org/pipermail/commits/2019-August/013946.html

Comment by Sergei Petrunia [ 2019-09-19 ]

Ok to push.

Comment by Sergei Petrunia [ 2019-09-19 ]

The patch fixes some of the cases. But does it fix all cases listed in the MDEV? (AFIAU, no?)

Comment by Varun Gupta (Inactive) [ 2019-09-21 ]

In this issue we see for limit = 10000 plan was changed from ref+Filesort to range scan.
but with limit = 20000, the number of records in the table is 10000, we picked index scan which is not at all beneficial.
So this patch fixes that even with limit > table records, if we planned to use range scan we should force creating a QUICK_SELECT.

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