Using filesort in Extra (MySQL)

When an existing index cannot be used, MySQL needs to use additional sorting methods to satisfy SQL queries. In this case, the query plan of the statement will appear using filesort. Usually, we will optimize by adding indexes and LIMIT rows.

At the same time, you might have some questions in your mind,

  • What does MySQL dofilesort?
  • filesortDo I have to use temporary files?
  • What sort algorithm is used?
  • Do I have to go back to the table to query the data field when the sort field and the data field are different?

MySQL filesort is the source code for MySQL filesort.

(The following is based on the MySQL 8.0 source code, which may differ from the 5.x filesort process.)

Filesort overview

Before we get to that, let’s start with an analogy and look at this question:

How many steps does it take to put an elephant in the fridge?

The answer, which everyone can blurt out, requires three steps:

Open the fridge -> put the elephant in the fridge -> close the fridge

Similarly, filesort’s overall process is simple:

Read data -> Sort data -> Output results

At first glance, is there a “I can do it” feeling?

Before you worry, let’s break down the steps and take a look at what MySQL does around these steps.

The whole process

Take a look at the entire Filesort process in one diagram, and we’ll break down each step as we go.

Do it before you do it. – Sort the data

Before fetching data, MySQL first prepares the contents needed for sorting data, and stores them in Sort_param, including sorting field length, de-gravity, stable sorting, and so on.

class Sort_param {
  uint m_fixed_rec_length{0};   ///< Maximum length of a record, see above.
  uint m_fixed_sort_length{0};  ///< Maximum number of bytes used for sorting.
 public:
  uint sum_ref_length{0};    // Length of record ref.
  uint m_addon_length{0};    // Length of added packed fields.
  uint fixed_res_length{0};  // Length of records in final sorted file/buffer.
  uint max_rows_per_buffer{0};  // Max (unpacked) rows / buffer.
  ha_rows max_rows{0};          // Select limit, or HA_POS_ERROR if unlimited.
	......
}
Copy the code

These data are used to prepare for sorting later. Different methods of obtaining data and data formats depend on these parameters. To understand these parameters, you need to first understand the organization format of ref, Addon, and sort data.

Ref or Addon?

There is a very important step in the sorting data preparation process:

param->init_for_filesort( ... ) ;Copy the code

Init_for_filesort initializes the sorting process information, including record length, de-repetition, stable sorting, etc., which is contained in Sort_param. To understand the meaning of the fields in Sort_param, you need to distinguish the two definitions: ref and addon

  • Ref, primary key, or ROWID, is used primarily for sorted back table queries
  • Addon, need to access the field, corresponding to the SELECT field, do not need to return to the table after sorting

MySQL > select * from sort key where ref or addon is concatenated to sort key;

However, how to decide which one to use? The choice of one also determines the method of obtaining the subsequent query field. Selecting REF means that the table needs to be returned through the primary key or ROWId to obtain the query field data, while selecting Addon means that the query field data needs to be taken out together at the beginning, which reduces a return to the table.

Decide_addon_fields (…) To make the answer:

// Generally, prefer using addon fields (ie., sorting rows instead of just row IDs) if we can .
Copy the code

With the exception of some special cases (such as full-text indexing, forced ROWId queries, sorting using priority queues, etc., as defined in sort_param.h/Addon_fields_status), MySQL uses Addon in preference.

About max_length_for_sort_data

In older versions of MySQL, ref is used by default when fields other than sort key are larger than this value. In newer versions of MySQL (8.0), this field is deprecated and will not be used in the future.

The data format

There are a lot of parameters in the sorting information, and it is difficult to understand the meaning of each field with various lengths. Let’s change the way and look at their meanings through data formats in different scenarios.

It is not hard to see that record lengths vary when different record formats are used, so you need to calculate the length of each segment separately. Where, Rowid format corresponds to the previous ref, Addon format corresponds to AdDON, and Packed Addon format is a format that packs and compreses Addon format (for example, the variable length string is packed to reduce space occupation. There are also packaging methods for blob, DeciAML, etc.).

Is it possible to take a shortcut – PQ priority queue

With the basic information sorted and the data format decided, it’s normal to start retrieving the data.

However, MySQL makes a judgment call to see if priority queues can be used. So what is a priority queue and why? Let’s take it step by step.

What is a PQ priority queue

The Priority Queue (PQ) is different from common queues. It is queued according to the Priority size. Its structure is a complete binary heap.

  • To queue, join the end of the queue first, and then adjust the binary heap structure from bottom to top to meet the rules
  • Out of the queue, only from the top of the heap, and then adjust the binary heap from top to bottom

Why use priority queues

The question can be rephrased, what are the scenarios for priority queues?

Its sorting performance is not necessarily the best compared with other algorithms such as fast sorting, but it may be faster for non-strict sorting and maximum filter maintenance under certain finite sets. For example, to find the two largest numbers out of 100, one way is to sort them all and take the top2, and another way is to use a priority queue, which only has two values, and find the top2 by going in and out of the queue, which will perform better than full sort.

When are priority queues used

Getting back to the topic, when is MySQL used?

Check_if_pq_applicable (); check_if_pq_applicable(); , will not be used in the following scenarios:

  • There is noLIMIT

If LIMIT is not used in SQL, then it is not used. This also makes sense, if the queue size is equal to the collection size, then it is better to use another sorting algorithm (such as fast sorting).

  • Need to go to the heavy

It is related to the structure of the priority queue, and there is no strict priority size relationship between the data. The child node can only be guaranteed to have a lower priority than the parent node.

  • The LIMIT is too large or the data is too long
  • When sorted data can all be stored in the cache, fast queue is faster than priority queue

MySQL can use fast sorting when all sorted data can be stored in memory, so you need to compare the speed of the two. MySQL considers that priority queue is 3 times slower than fast queue. If (number of rows in sort data / 3) < LIMIT number of rows, select fast queue; otherwise, select priority queue.

  • LIMIT number of rows cannot be placed in the cache

Priority queue sorting needs to be done in memory, so it is necessary to determine whether the cache can store LIMIT row data.

Finally step one – read the data

Before we start reading the data, let’s see what we have ready:

  1. Sort basic information, including data format, format segment length, maximum number of data lines, whether to use priority queues, and so on
  2. MySQL global OR session configuration, including sort_buffer_size
  3. The data source iterator, source_iterator, is used to retrieve data

Based on this, the process of reading the data is as follows:

while (get_next_sortkey()) { if (using priority queue) push sort key into queue else { try to put sort key into buffer; if (no free space in sort buffer) { do { allocate new, larger buffer; retry putting sort key into buffer; } until (record fits or no space for new buffer) if (no space for new buffer) { sort record pointers (all buffers); dump sorted sequence to 'tempfile'; dump Merge_chunk describing sequence location into 'chunk_file'; }}}}Copy the code

The overall idea is to read the data into the priority queue or sort buffer first. When the buffer space is insufficient, apply for expansion. When the buffer space cannot be applied for, save the data in the unit of chunk to the temporary file tempfile. Where the size of a chunk is equal to the size of the sort buffer, tempfile is used to store data, merge_chunk is used to store chunk-related information,

At the same time, some problems will be involved in this process:

  • Data in priority queue, do not determine the queue size?

Not judging the queue size is normally problematic. When the queue is full, the push operation will not report an error and will directly discard the object, and we cannot know whether the actual operation is successful or not. Therefore, MySQL determines whether to use priority queues before reading data, and only uses them if the data can be placed in the cache.

  • What happens if the query is terminated while reading the data?

If the query terminates, the read will also terminate. MySQL will check for killed data after each read from the source_iterator and throw an exception if it is killed.

for (;;) { if ((error = source_iterator->Read())) { break; }... If (THD ->killed) {return HA_POS_ERROR; }... }Copy the code
  • When space is insufficient, can first sort again fall dish, use what method sort?

Filesort_buffer::sort_buffer

  • Why is it sorted before chunk?

This is where the final result ordering comes in. Because the sort buffer doesn’t fit, the chunk_file will split the data between different chunk_file types, but the chunk_file will eventually be used to sort the whole data. The chunk_file type is best suited for merge sorts, and the chunk_file will order the data for subsequent merge sorts.

  • How chunk_file relates to tempfile?

When the sort Buffer is full, the entire buffer is stored as a chunk in a tempFile. Where all chunks are stored in the same tempfile, a structure called merge_chunk is needed to record the location and size of chunk in the tempfile. This structure is stored in the chunk_file.

Different scenarios in different ways – data sorting

After reading the data, there are two possible results: data in memory, data in a temporary file, num_chunks, and chunk_file if the value is greater than 0.

  • The data is in memory

Use the fastest quicksort directly to complete the whole process in memory.

  • The data is in a temporary file

MySQL uses the merge sort algorithm to sort all chunks, and the core uses the multi-way merge algorithm. At the same time, the whole process is closely related to two parameters, MERGEBUFF(7) and MERGEBUFF2(15).

When the number of remaining chunks is smaller than MERGEBUFF2(15), merge all chunks once to get the result. (The source implementation is recorded in merge_index(…).) C)

When the number of remaining chunks is larger than MERGEBUFF2(15), merge sort with MERGEBUFF(7) as a batch and merge into a larger chunkd until less than 15. (Source code implementation documented in Merge_many_buff (…) C)

By merging and sorting multiple times, it will eventually merge into an ordered data set.

What if the query is terminated during sorting? During the sorting process, a checkpoint is buried to check whether the query was aborted, that is, to determine whether THD -> KILLED is true.

The end result – the result output

The sorting results in the output of a complete ordered data set, recorded in outfile, and is cleaned of cache (sort Buffer, etc.), temporary files (tempfile, chunk_file, etc.) before returning the actual data set.

conclusion

Finally, we’ll come back and answer the first few questions.

  • What does MySQL dofilesort?

Go back to the original flow chart that illustrates the entire Filesort process.

  • filesortDo I have to use temporary files?

Not necessarily. When sort Buffer can hold data to be sorted, it does not use temporary files.

  • What sort algorithm is used?

Filesort uses three sorting algorithms:

  1. Priority queue sort. Determine whether data can be used before obtaining it to optimize SQL inclusionLIMITThe sorting efficiency is higher than that of fast sorting.
  2. Quicksort. The sorting data is all placed insort buffer, mainly used for memory sort.
  3. Multiple merge sort. A singlesort bufferCan not put the data, need to drop disk auxiliary, use multiple merge sort merge multiplechunk, and finally merged into an ordered result set.
  • Do I have to go back to the table to query the data field when the sort field and the data field are different?

Not necessarily, it depends on which data format to use in the sorting information preparation phase.