Priority queue optimization for filesort is now visible in M_MySQL

TL;DR:Priority queue optimization for filesort with small LIMIT is now visible in MariaDB: there is a status variable and you can also see it in the slow query log (KB page link).

A longer variant:

One of the new optimizations in MySQL 5.6 is ability to use a priority queue instead of sorting for ORDER BY … LIMIT queries. The optimization was ported into MariaDB 10.0 long ago, but we still get questions if/when it will be ported. I guess, the reason for this is that, besides the query speed, you can’t see this optimization. Neither EXPLAIN, nor EXPLAIN FORMAT=JSON or PERFORMANCE_SCHEMA or status variables give any indication whether filesort used priority queue or the regular quicksort+merge algorithm.

MySQL 5.6 has only one way one can check whether filesort used priority queue. You need to enable optimizer_trace (set optimizer_trace=1), and then run the query (not EXPLAIN, but the query itself). Then, you can look into the optimizer trace and find something like this:

..."filesort_priority_queue_optimization": {"limit": 10,"rows_estimate": 198717,"row_size": 215,"memory_available": 262144,"chosen": true},...

MariaDB doesn’t support optimizer_trace at the moment. Even if it did, I think it would be wrong to require one to look into the optimizer trace to find out about the picked query plan.

The natural place to show the optimization would be EXPLAIN output. We could show something like“Using filesort (priority queue)”. This was my initial intent. After looking into the source code, this turned out to be difficult to do. The logic that makes the choice between using quicksort+merge and using priority queue is buried deep inside query execution code. (As if the mess caused by late optimizations of ORDER BY and UNIONs didn’t teach anybody in MySQL team anything).

As for query execution, there are two facilities where one could record execution-time details about the query plan. They are the status variables and the slow query log.

Status variables

We’ve addedSort_priority_queue_sortsstatus variable. Now, the list of sort-related status variables is:

MariaDB [test]> show status like 'Sort%';+---------------------------+-------+| Variable_name | Value |+---------------------------+-------+| Sort_merge_passes | 0 |<font color="red">| Sort_priority_queue_sorts | 1 |</font>| Sort_range| 0 || Sort_rows | 11|| Sort_scan | 1 |<code>+---------------------------+-------+</code>

(Sort_range + Sort_scan)gives total number of sorts.Sort_priority_queue_sortsgives number of sorts that were done using priority queue.

Slow query log

Percona’sExtended statistics in the slow query logshows Filesort/Filesort_on_disk fields. We thought that adding information about priority queue use would be appropriate. Now, slow query log entries look like this:

# Time: 140714 18:30:39# User@Host: root[root] @ localhost []# Thread_id: 3Schema: testQC_hit: No# Query_time: 0.053857Lock_time: 0.000188Rows_sent: 11Rows_examined: 100011# Full_scan: YesFull_join: NoTmp_table: NoTmp_table_on_disk: No# Filesort: YesFilesort_on_disk: NoMerge_passes: 0<font color="red">Priority_queue: Yes</font>SET timestamp=1405348239;select * from t1 where col1 between 10 and 20 order by col2 limit 100;

pt-query-digestis able to parse slow query logs with the new field.

What about PERFORMANCE_SCHEMA

What about PERFORMANCE_SCHEMA? After all, it is the most powerful tool for tracking query execution. It has “absorbed” some status variables intoevents_statements_historytable. For sorting, it has these columns:

| SORT_MERGE_PASSES | bigint(20) unsigned| NO | | NULL| || SORT_RANGE| bigint(20) unsigned| NO | | NULL| || SORT_ROWS | bigint(20) unsigned| NO | | NULL| || SORT_SCAN | bigint(20) unsigned| NO | | NULL| |

Should we add a SORT_PRIORITY_QUEUE_SORTS column there? We didn’t add it into 10.0 right now because of compatibility concerns. Some tools may rely on the structure of PERFORMANCE_SCHEMA tables. Also, PERFORMANCE_SCHEMA table definitions are stored on disk, and one would have to runmysql_fix_privilege_tablesafter a minor upgrade, which is not good.

Posted inEXPLAIN,mysql,mariadbon July 14th, 2014 by spetrunia| |