Complete cost-based optimization for ORDER BY with LIMIT (MDEV-8306)

[MDEV-20146] Analyze and Explain for sort-nest Created: 2019-07-24  Updated: 2023-12-12

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: N/A
Fix Version/s: 11.5

Type: Technical task Priority: Major
Reporter: Varun Gupta (Inactive) Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 0
Labels: None


 Description   

This task is concerned with how we would show the sort_nest (MDEV-8306)
in the explain or analyze output.

First thought would be to show the sort nest the same way as we do it for SJ Materialization or Derived tables

This is how it is done for Semi Join Materialization

MariaDB [test]> explain extended select * from t1 where a in (select a from t2 group by a);
 
+------+--------------+-------------+------+---------------+------+---------+------+------+----------+-------------------------------------------------+
 
| id   | select_type  | table       | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                           |
 
+------+--------------+-------------+------+---------------+------+---------+------+------+----------+-------------------------------------------------+
 
|    1 | PRIMARY      | <subquery2> | ALL  | distinct_key  | NULL | NULL    | NULL |    5 |   100.00 |                                                 |
 
|    1 | PRIMARY      | t1          | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | Using where; Using join buffer (flat, BNL join) |
 
|    2 | MATERIALIZED | t2          | ALL  | NULL          | NULL | NULL    | NULL |    5 |   100.00 |                                                 |
 
+------+--------------+-------------+------+---------------+------+---------+------+------+----------+-------------------------------------------------+

Another one could be not to show the table for sort-nest and just mention in the EXTRA column of explain , using sort_nest with the tables inside it. Instead of using temporary, we can have Using Sort Nest.

MariaDB [test]>  explain select * from t1,t2 where t1.a > 95  and t1.a=t2.a order by t2.a+1;
 
+------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+
 
| id   | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                                        |
 
+------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+
 
|    1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      | 100  | Using where; Using temporary; Using filesort |
 
|    1 | SIMPLE      | t2    | ref  | a             | a    | 5       | test.t1.a | 1    |                                              |
 
+------+-------------+-------+------+---------------+------+---------+-----------+------+----------------------------------------------+

2 rows in set (0.004 sec)

 Comments   
Comment by Varun Gupta (Inactive) [ 2019-08-22 ]

This has been implemented , an example of how the sort-nest looks like with explain is

MariaDB [test]> EXPLAIN EXTENDED SELECT t1.a, t2.b, t1.b, t3.a from t1,t2,t3 WHERE t1.a=t2.a and t2.b=t3.a ORDER BY t2.b desc, t1.b desc LIMIT 5;
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+----------+-------------------------------------------------+
 
| id   | select_type | table       | type | possible_keys | key  | key_len | ref         | rows | filtered | Extra                                           |
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+----------+-------------------------------------------------+
 
|    1 | SIMPLE      | t1          | ALL  | NULL          | NULL | NULL    | NULL        | 5    |   100.00 |                                                 |
 
|    1 | SIMPLE      | t2          | ALL  | NULL          | NULL | NULL    | NULL        | 5    |   100.00 | Using where; Using join buffer (flat, BNL join) |
 
|    1 | SIMPLE      | <sort-nest> | ALL  | NULL          | NULL | NULL    | NULL        | 5    |   100.00 | Using filesort                                  |
 
|    1 | SIMPLE      | t3          | ref  | a             | a    | 5       | sort-nest.b | 1    |   100.00 | Using index                                     |
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+----------+-------------------------------------------------+
 
4 rows in set, 1 warning (0.003 sec)
 
 
 
MariaDB [test]> ANALYZE SELECT t1.a, t2.b, t1.b, t3.a from t1,t2,t3 WHERE t1.a=t2.a and t2.b=t3.a ORDER BY t2.b desc, t1.b desc LIMIT 5;
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+--------+----------+------------+-------------------------------------------------+
 
| id   | select_type | table       | type | possible_keys | key  | key_len | ref         | rows | r_rows | filtered | r_filtered | Extra                                           |
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+--------+----------+------------+-------------------------------------------------+
 
|    1 | SIMPLE      | t1          | ALL  | NULL          | NULL | NULL    | NULL        | 5    | 5.00   |   100.00 |     100.00 |                                                 |
 
|    1 | SIMPLE      | t2          | ALL  | NULL          | NULL | NULL    | NULL        | 5    | 5.00   |   100.00 |      20.00 | Using where; Using join buffer (flat, BNL join) |
 
|    1 | SIMPLE      | <sort-nest> | ALL  | NULL          | NULL | NULL    | NULL        | 5    | 5.00   |   100.00 |     100.00 | Using filesort                                  |
 
|    1 | SIMPLE      | t3          | ref  | a             | a    | 5       | sort-nest.b | 1    | 1.00   |   100.00 |     100.00 | Using index                                     |
 
+------+-------------+-------------+------+---------------+------+---------+-------------+------+--------+----------+------------+-------------------------------------------------+
 
4 rows in set (0.005 sec)

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

This has been implemented along with MDEV-8306, so it is in review

Comment by Julien Fritsch [ 2019-11-15 ]

Can you please update the status. Only the assignee can.

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