[MDEV-18066] DELETE/UPDATE and ORDER BY ... LIMIT - the choice is not cost-based Created: 2018-12-23  Updated: 2019-08-05

Status: Open
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.1, 10.2, 10.3
Fix Version/s: 10.4

Type: Bug Priority: Major
Reporter: Sergei Petrunia Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: order-by-optimization

Issue Links:
Relates
relates to MDEV-17761 Odd optimizer choice with ORDER BY LI... Stalled

 Description    

create table ten(a int);
 
insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
 
create table one_k(a int);
 
insert into one_k select A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C;


create table t20 (a int, b int, c int, filler char(100));
 
insert into t20 select a,a,a,a from one_k;
 
alter table t20 add key(a), add key(b);


mysql> explain delete from t20  where a  between 1 and 300 order by b limit 1;
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                       |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+
 
|    1 | SIMPLE      | t20   | range | a             | a    | 5       | NULL |  300 | Using where; Using filesort |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+

Here, it will use range + sorting regardless of whether it is possible to use some other index that would match the LIMIT.

For comparison:

mysql> explain delete from t20  where a+0  between 1 and 300 order by b limit 1;
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+
 
|    1 | SIMPLE      | t20   | index | NULL          | b    | 5       | NULL |    1 | Using where |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-------------+



 Comments   
Comment by Sergei Petrunia [ 2018-12-23 ]

This was intended this way by the code in get_index_for_order. 

  if (select && select->quick)
 
  {
 
    ...
 
  }
 
  else if (limit != HA_POS_ERROR)
 
  { // check if some index scan & LIMIT is more efficient than filesort
 
    ...

Comment by Sergei Petrunia [ 2018-12-23 ]

The worse part is that quick select is constructed regardless of whether it is cheap (= and whether its condition is selective): SQL_SELECT::test_quick_select() is invoked with the limit parameter having the value from the LIMIT in the query. The effect of this is:

  if (limit < records)
 
    read_time= (double) records + scan_time + 1; // Force to use index

which means a quick select is constructed if at all possible. For example:

mysql> explain delete from t20  where a  between 1 and 900 order by b limit 1;
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                       |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+
 
|    1 | SIMPLE      | t20   | range | a             | a    | 5       | NULL |  900 | Using where; Using filesort |
 
+------+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------+

A plan to use range access to read 900 rows (out of 1000 in the table).
Without ORDER BY LIMIT, it is not chosen:

mysql> explain delete from t20  where a  between 1 and 900 ;
 
+------+-------------+-------+------+---------------+------+---------+------+------+-------------+
 
| id   | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |
 
+------+-------------+-------+------+---------------+------+---------+------+------+-------------+
 
|    1 | SIMPLE      | t20   | ALL  | a             | NULL | NULL    | NULL | 1000 | Using where |
 
+------+-------------+-------+------+---------------+------+---------+------+------+-------------+

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