Shulou(Shulou.com)05/31 Report--

What is the internal principle of MySQL sorting, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Sort, sort, sort

When we view the MySQL execution plan through explain, we often see Using filesort displayed in the Extra column.

In fact, this situation shows that MySQL uses sorting.

Using filesort often appears in the case of order by, group by, distinct, join and so on.

Third, index optimization sorting

When we look at sorting, the first thing that comes to mind in our DBA must be whether it can be optimized with indexes.

By default, INNODB uses the B tree index, and the B tree index itself is ordered. If you have a query as follows

Select * from film where actor_name=' Miss' order by prod_time

Then you only need to add a (actor_name,prod_time) index to take advantage of the features of B tree to avoid additional sorting.

As shown in the following figure:

After finding the data of actor_name=' Mr. Cang's actor as Mr. Cang through B-tree, you only need to look to the right in order, and no additional sorting operation is needed.

The corresponding ones that can be sorted using the index are listed as follows:

SELECT * FROM T1 ORDER BY key_part1,key_part2,...; SELECT * FROM T1 WHERE key_part1 = constant ORDER BY key_part2;SELECT * FROM T1 ORDER BY key_part1 DESC, key_part2 DESC;SELECT * FROM T1 WHERE key_part1 = 1 ORDER BY key_part1 DESC, key_part2 DESC;SELECT * FROM T1 WHERE key_part1 > constant ORDER BY key_part1 ASC;SELECT * FROM T1 WHERE key_part1

< constant ORDER BY key_part1 DESC;SELECT * FROM t1 WHERE key_part1 = constant1 AND key_part2 >

Constant2 ORDER BY key_part2

From the above example, we can also see how to build a composite index if you want MySQL to use index optimization sorting.

Fourth, sort mode 4.1 actual trace results

However, there are still a lot of SQL that cannot use indexes for sorting, such as

Select * from film where Producer like 'Tokyo fever%' and prod_time > '2015-12-01' order by actor_age

We want to find out about the films produced by Tokyo Hot since December 1 last year, and sorted by the age of the actors.

(well, suppose I have a database that every male DBA wants to maintain:)

In this case, sorting can no longer be avoided by using an index, so what exactly will MySQL sort do to columns?

In general terms, it will follow:

Filter the data according to "Producer like 'Tokyo hot%' and prod_time > '2015-12-01'" to find the data you need.

Sort the found data according to "order by actor_age" and return the necessary data to the client in actor_age order according to "select *".

There is no proof, we can use MySQL's optimize trace to see if it is as mentioned above.

If you see more detailed MySQL optimizer trace information through optimize trace, you can check out Ali Yinfeng's blog about optimizer trace.

The trace results are as follows:

Filter the data according to "Producer like 'Tokyo hot%' and prod_time > '2015-12-01'" to find the data you need.

"attaching_conditions_to_tables": {"original_condition": "((`room`.`Producer` like 'Tokyo hot%') and (`room`.`prod _ time` > '2015-12-01'))", "attached_conditions_computation": [], "attached_conditions_summary": [{"table": "`Tokyo'" "attached": "((`Tokyo '.`Producer` like' Tokyo hot%') and (`room`.`prod _ time` > '2015-12-01'))"}]}

Sort the found data according to "order by actor_age" and return the necessary data to the client in actor_age order according to "select *".

"join_execution": {"select#": 1, "steps": [{"filesort_information": [{"direction": "asc", "table": "`room`", "field": "actor_age"}] "filesort_priority_queue_optimization": {"usable": false, "cause": "not applicable (no LIMIT)"}, "filesort_execution": [], "filesort_summary": {"rows": 1, "examined_rows": 5 "number_of_tmp_files": 0, "sort_buffer_size": 261872, "sort_mode": ""}}]}

Here, we can clearly see that MySQL performs an asc sort operation for the film table .actor _ age field when executing this select.

"filesort_information": [{"direction": "asc", "table": "`room`", "field": "actor_age"} 4.2 Overview of sorting modes

Here we are mainly concerned about how MySQL is sorted and what sort algorithm is used.

Please pay attention here.

"sort_mode":

There are three kinds of sort_mode for MySQL.

The sql/filesort.cc source code in the extract 5.7.13 is as follows:

Opt_trace_object (trace, "filesort_summary") .add ("rows", num_rows) .add ("examined_rows", param.examined_rows) .add ("number_of_tmp_files", num_chunks) .add ("sort_buffer_size", table_sort.sort_buffer_size ()) .add _ alnum ("sort_mode") Param.using_packed_addons ()? ": param.using_addon_fields ()": ")

"

< sort_key, rowid >

"and"

< sort_key, additional_fields >

"students who have read other articles introducing MySQL ranking should be more aware of it."

< sort_key, packed_additional_fields >

"relatively new.

< sort_key, rowid >

It corresponds to the "original sorting mode" before MySQL 4.1,

< sort_key, additional_fields >

Corresponding to the "modified sorting mode" introduced after MySQL 4.1,

< sort_key, packed_additional_fields >

It is a further optimized "packaged data sorting mode" introduced after MySQL 5.7.3.

Let's introduce these three modes one by one:

4.2.1 back to the table sort mode

According to the index or full table scan, the sort field values and row ID of the query are obtained according to the filter conditions.

The sorted field values and row ID form a key-value pair, which are stored in sort buffer.

If the sort buffer memory is larger than the memory of these key-value pairs, there is no need to create temporary files. Otherwise, every time the sort buffer fills up, you need to sort it in memory directly with qsort (quick sort algorithm) and write it to a temporary file

Repeat the above steps until all rows of data have been read normally

If a temporary file is used, you need to use the external sorting of the disk to write row id to the result file

Read the data that the user needs to return in order according to the row ID in the result file. Because the row ID is not sequential, the table is returned to a random IO. To further optimize the performance (become a sequential IO), MySQL reads a batch of row ID and inserts the read data into the cache in the order of sort fields (memory size read _ rnd_buffer_size).

4.2.2 do not return to table sort mode

According to the index or full table scan, according to the filter conditions to obtain the data to be queried

The column values to be sorted and the fields to be returned by the user form key-value pairs, which are stored in sort buffer.

If the sort buffer memory is larger than the memory of these key-value pairs, there is no need to create temporary files. Otherwise, every time the sort buffer fills up, you need to sort it in memory directly with qsort (quick sort algorithm) and write it to a temporary file

Repeat the above steps until all rows of data have been read normally

If a temporary file is used, you need to use the external sorting of the disk to write the sorted data to the result file

Return the field data that the user needs directly from the result file, instead of going back to the table query again according to row ID.

4.2.3 packing data sort mode

The improvement of the third sorting mode is simply that it is more compact when saving the char and varchar fields in sort buffer.

In the previous two modes, columns defined as VARCHAR with 3 characters stored in "yes" would apply for 255character memory space in memory, but with the 5.7.3 improvement, only 2 bytes of field length and 3 character memory space (used to save the three characters "yes") would be enough, which was compressed more than 50 times, allowing more key-value pairs to be saved in sort buffer.

4.2.4 comparison of three modes

The second mode is the improvement of the first mode, which avoids the second return to the table and uses the method of exchanging space for time.

However, because the sort buffer is so large, if the data that the user wants to query is very large, a lot of time is wasted on sorting outside the disk, resulting in more IO operations, which may not be as efficient as the first way.

Therefore, MySQL provides the user with a parameter of max_length_for_sort_data. When "sorted key-value pair size" > max_length_for_sort_data, MySQL thinks that the IO efficiency of external sorting on disk is not as efficient as that of returning to the table, and will choose the first sorting mode; otherwise, it will choose the second mode of not returning to the table.

The third mode is mainly to solve the problem of waste of storage space of variable length character data. For the actual data is not much, the improvement effect of longer field definition will be more obvious.

Can see that the students here are absolutely true love, but it is not over, the things behind may be more brain-burning.

I suggest we all have a cup of coffee before we continue to watch.

Many articles may be almost done here, but you have forgotten to pay attention to the question: "if the sorted data cannot be completely stored in sort buffer memory, how can the whole sorting process be completed through external sorting?"

To solve this problem, we first need to take a brief look at how external sorting is done.

5. External sorting 5.1 General external sorting 5.1.1 two-way external sorting

Let's first take a look at the simplest and most common two-way external sorting algorithm.

Assuming that the memory is only 100m, but the sorted data is 900m, the corresponding external sorting algorithm is as follows:

Read 100MB data from 900m data to be sorted into memory and sort according to the traditional internal sorting algorithm (quick sort)

Write sorted data to disk

Repeat steps 1 and 2 until each 100MB chunk sorted data is written to disk.

Each time you read the pre-10MB (= 100MB / (9 chunks + 1)) data in the sorted chunk, a total of 9 chunk require 90MB, and the rest of the 10MB is used as the output cache

Perform a "9-way merge" of the data and write the results to the output cache. If the output cache is full, the final sort result file is written directly and the output cache is emptied; if the input cache of 9 10MB is empty, read the 10MB data from the corresponding file until the entire file is read. The final output of the sorting result file is the data sorted by 900MB.

5.1.2 Multiplex external sorting

The above sorting algorithm is a two-way sorting algorithm (sorting first, then merging). But there is a problem with this algorithm. Assuming that the data to be sorted is 50GB and there is only 100MB in memory, then fetching 200KB from each of the 500 sorted shards (100MB / 501is about 200KB) is a lot of random IO. Efficiency is very slow, and the correspondence can be improved in this way:

Read 100MB data from the 50GB data to be sorted into memory and sort according to the traditional internal sorting algorithm (quick sort)

Write sorted data to disk

Repeat steps 1 and 2 until each 100MB chunk sorted data is written to disk.

25 pieces at a time are merged and sorted, resulting in 20 larger 2.5GB ordered files (500 paces, 25 bits and 20).

The ordered files of the 20 2.5GB are merged and sorted to form the final sorting result file.

The corresponding situation with a larger amount of data can be merged more times.

5.2 MySQL external sorting 5.2.1 MySQL external sorting algorithm

So what kind of columns is the external sort used by MySQL? let's take the back-table sorting mode as an example:

According to the index or full table scan, according to the filter conditions to obtain the data to be queried

The column values to be sorted and row ID form a key-value pair, which are stored in sort buffer.

If the sort buffer memory is larger than the memory of these key-value pairs, there is no need to create temporary files. Otherwise, each time the sort buffer fills up, you need to sort it in memory directly with qsort (Quick sort Mode) and write it to a temporary file as a block. Unlike a normal external sort written to multiple files, MySQL only writes to a temporary file and simulates the merge sorting of multiple files by saving the file offset

Repeat the above steps until all rows of data have been read normally

One batch of data per MERGEBUFF (7) block is extracted and sorted and merged into another temporary file until all the data is sorted into a new temporary file.

Repeat the above merge sorting process until there are fewer MERGEBUFF2 (15) block left.

A more popular explanation:

In the first loop, one block corresponds to one sort buffer (size sort_buffer_size) sorted data; every seven are merged.

In the second loop, one block corresponds to MERGEBUFF (7) sort buffer data, merging every seven.

...

Until the number of all block is less than MERGEBUFF2 (15).

The last loop, writing only the row ID to the result file

Read the data that the user needs to return in order according to the row ID in the result file. To further optimize performance, MySQL reads a batch of row ID and inserts the read data into the cache (memory size read _ rnd_buffer_size) according to the sort field requirements.

What we need to pay attention to here is:

MySQL writes the externally sorted slices into the same file, and distinguishes each shard location by saving the file offset.

MySQL merges one per MERGEBUFF (7) fragments, and when the final number of fragments reaches MERGEBUFF2 (15), merge for the last time. Both values are written to death in the code.

5.2.2 sort_merge_passes

There is only one sentence to describe Sort_merge_passes in the MySQL manual.

Sort_merge_passesThe number of merge passes that the sort algorithm has had to do. If this value is large, you should consider increasing the value of the sort_buffer_size system variable.

This paragraph does not specify what sort_merge_passes is, what it means when the value is large, and how it can be alleviated.

We have figured out the external sorting algorithm of MySQL above, and this problem is clear.

In fact, sort_merge_passes corresponds to the number of times MySQL does merge sorting, that is, if the value of sort_merge_ passes is relatively large, it means that the greater the gap between sort_buffer and the data to be sorted, we can alleviate the number of sort_merge_passes merge sorting by increasing sort_buffer_size or making the key-value pair entered into sort_buffer_size smaller.

Accordingly, we can see the evidence in the source code.

Steps 5 to 7 of the above MySQL external sorting algorithm are implemented through the merge_many_buff () function in the sql/filesort.cc file. In step 5, a single merge is implemented using merge_buffers (). The source code is excerpted as follows:

Int merge_many_buff (Sort_param * param, Sort_buffer sort_buffer, Merge_chunk_array chunk_array, size_t * p_num_chunks, IO_CACHE * t_file) {. For (iTun0; I)

< num_chunks - MERGEBUFF * 3 / 2 ; i+= MERGEBUFF) { if (merge_buffers(param, // param from_file, // from_file to_file, // to_file sort_buffer, // sort_buffer last_chunk++, // last_chunk [out] Merge_chunk_array(&chunk_array[i], MERGEBUFF), 0)) // flag goto cleanup; } if (merge_buffers(param, from_file, to_file, sort_buffer, last_chunk++, Merge_chunk_array(&chunk_array[i], num_chunks - i), 0)) break; /* purecov: inspected */...} 截取部分merge_buffers()的代码如下， int merge_buffers(Sort_param *param, IO_CACHE *from_file, IO_CACHE *to_file, Sort_buffer sort_buffer, Merge_chunk *last_chunk, Merge_chunk_array chunk_array, int flag){... current_thd->

Inc_status_sort_merge_passes ();...}

You can see that each merge_buffers () adds sort_merge_passes, that is, every time the MERGEBUFF (7) block is merged and sorted, the sort_merge_passes will be added by one, and the more sort_merge_passes means that there is too much data to sort, which requires multiple merge pass. The solution is to reduce the size of the data to be sorted or increase the sort_buffer_size.

With a small advertisement, there are sort_merge_pass performance indicators and alarm settings with excessive parameter values in our qmonitor.

VI. Interpretation of trace results

Having explained the three sorting modes and the methods of external sorting, let's look back at the results of trace.

6.1 whether there is an external sort of disk

"number_of_tmp_files": 0

Number_of_tmp_files indicates how many shards there are, and if number_of_tmp_files is not equal to 0, it means that a sort_buffer_size-sized memory cannot hold all the key-value pairs, that is, MySQL uses disks to sort.

6.2 whether there is priority queue optimization sorting

Since there is no paging restriction on data in our SQL, filesort_priority_queue_optimization is not enabled.

"filesort_priority_queue_optimization": {"usable": false, "cause": "not applicable (no LIMIT)"}

Normally, using Limit enables optimization of priority queues. Priority queues are similar to FIFO first-in, first-out queues.

The algorithm has changed slightly, taking the sorting mode of the back table as an example.

Sort_buffer_size is big enough

If the Limit limit returns N pieces of data, and the N pieces of data are smaller than sort_buffer_size, then MySQL will use sort buffer as a priority queue and insert it into the queue sequentially when the priority queue is inserted in the second step. In the third step, when the queue is full, it will not write to the external disk file, but will directly eliminate the last piece of data until all the data is read normally.

The algorithm is as follows:

According to the index or full table scan, according to the filter conditions to obtain the data to be queried

The column values to be sorted and the row ID form a key-value pair, which are stored in the priority queue in order.

If the priority queue is full, eliminate the last record directly.

Repeat the above steps until all rows of data have been read normally

The last loop, writing only the row ID to the result file

Read the data that the user needs to return in order according to the row ID in the result file. To further optimize performance, MySQL reads a batch of row ID and inserts the read data into the cache (memory size read _ rnd_buffer_size) according to the sort field requirements.

Sort_buffer_size is not big enough.

Otherwise, when N pieces of data are larger than sort_buffer_size, MySQL cannot directly use sort buffer as priority queue, and the normal external sorting of files is the same, but when the final result is returned, the data is only returned according to N row ID. We will not enumerate the specific algorithms.

Here, whether MySQL chooses priority queue or not is determined in the check_if_pq_applicable () function of sql/filesort.cc. The specific code details will not be expanded here.

In addition, we did not discuss the case of limit MJ n. If it is Limit MJ n, the corresponding "N row ID" above is "misn row ID". In fact, the limit MJ n of MySQL is to take the data of m lines, and finally throw away the M pieces of data.

From the above, we can also see that when the sort_buffer_size is large enough and the limit data is relatively small, the optimization effect is obvious.

7. MySQL other related sorting parameters 7.1 max_sort_length

Here you need to distinguish between max_sort_length and max_length_for_sort_data.

Max_length_for_sort_data is for MySQL to choose. "

< sort_key, rowid >

"or"?

< sort_key, additional_fields >

The mode of ".

On the other hand, when the size of the key-value pair cannot be determined (for example, the data to be queried by the user contains SUBSTRING_INDEX (col1,'.', 2)) MySQL will allocate max_sort_length bytes of memory to each key-value pair, resulting in a waste of memory space and excessive sorting outside the disk.

7.2 innodb_disable_sort_file_cache

If innodb_disable_sort_file_cache is set to ON, it means that temporary files generated in sorting do not use the file system cache, similar to O_DIRECT opening files.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.