Shulou(Shulou.com)06/01 Report--

Sometimes when you view the execution plan of SQL, you will encounter Using filesort, as follows.

Mysql > explain select * from tb1 where col1 = 4 order by col2\ G

* * 1. Row *

Id: 1

Select_type: SIMPLE

Table: tb1

Type: ref

Possible_keys: idx_col1

Key: idx_col1

Key_len: 4

Ref: const

Rows: 1

Extra: Using where; Using filesort

1 row in set (0.00 sec)

This filesort means that MySQL needs to do an extra sort, or Quicksort, to be exact.

First, a preliminary understanding of the concept of Quicksort sorting (From Wikipedia).

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

1. Pick an element, called a pivot, from the array.

2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way) After this partitioning, the pivot is in its final position. This is called the partition operation.

3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Let's take a look at an implementation of Python.

#! / usr/bin/env python

#-*-coding: utf-8-*-

From _ _ future__ import print_function

Def quicksort (array):

If len (array) < 2:

Return array

Else:

Pivot = array [0]

Less = [i for i in array [1:] if i pivot]

Return quicksort (less) + [pivot] + quicksort (greater)

Print (quicksort ([10,5,2,3]))

Coming back to filesort, there are three implementations of the Original, Modified and In-Memory filesort Algorithm in MySQL.

The Original filesort Algorithm

1. Scan or obtain all records according to WHERE conditions.

two。 Put the sort key and row ID of each record, that is, into sort buffer. If the sort buffer is full, do a quicksort in memory, then write to a temporary file and record to the pointer. Repeat the process until all records are read.

3. Perform several multi-merge operations and write all row ID to the result file.

4. Get the record again according to row ID.

It is easy to find that steps 1 and 4 above read the record twice, so there is the following improved implementation.

The Modified filesort Algorithm

The change from Original is that in step 2, sort key and other columns involved are recorded, that is, not row ID. After the completion of step 3, you can get the results.

In this algorithm, the space ratio is large, and if the amount of sorted data is large, temporary files will be written frequently. In order to avoid it, the max_length_for_sort_data parameter is introduced.

The In-Memory filesort Algorithm

Well, when the amount of sorted data is relatively small, it is so small that it can be sorted in sort buffer. In view of this situation, there is In-Memory filesort. At this point, MySQL uses sort buffer as priority queue and avoids using temporary files.

Above, we can see that MySQL has optimized the sorting as much as possible, and it also shows from the side that it does not want to sort, such as the original SQL, establishing a (col1, col2) joint index, we can avoid sorting, this reason should start from the B+ tree index.

If you are interested, please follow Subscription account's Database Best practices (DBBestPractice).

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.