A Detailed Analysis of filesort

Posted on In , Views: Word count in article: 7.6k Reading time ≈ 27 mins.
Notes on the MySQL filesort sorting mechanism: comparing the original and modified algorithms, the meaning of max_sort_length, and how the sort/addon fields are organized.

This article explains things very well, so I’d like to recommend it to everyone.

[Reprinted] https://blog.csdn.net/n88Lpo

Abstract

Sorting (filesort) is a topic DBAs can’t avoid, and people often discuss it. Some common questions:

  • During sorting, is the data used for sorting compressed to store empty characters, the way InnoDB does? For example, with varchar(30), if I only stored 1 character, will it be compressed, or computed as 30 characters?
  • What exactly do max_length_for_sort_data / max_sort_length mean?
  • What is the fundamental difference between the original filesort algorithm (sort with table lookup) and the modified filesort algorithm (sort without table lookup)?
  • Why is Rows_examined in the slow query log larger when sorting is involved, and how exactly is it calculated?

In MySQL, the following algorithms are typically used to complete sorting:

  • In-memory sort (priority queue, commonly used with order by limit to return a small number of rows, improving sort efficiency; but note that with order by limit n,m, if n is too large, it may involve switching the sort algorithm)
  • In-memory sort (quicksort)
  • External sort (merge sort)

But due to limited space, this article does not explain these algorithms, nor does it consider the branching logic of the priority-queue algorithm. It analyzes the flow based only on quicksort and merge sort.

If the word “filesort” appears in the execution plan, it usually means sorting was used, but the execution plan does not reveal the following:

  • Whether temporary files were used.
  • Whether a priority queue was used.
  • Whether it was the original filesort algorithm (sort with table lookup) or the modified filesort algorithm (sort without table lookup).

How to check these will be described later. This article will also provide a large number of sorting interfaces for interested readers to use, and to keep as notes for myself.

14. Overall Summary

I’ll put the summary up front so readers can skim it quickly. This article is long, so a detailed summary is needed here.

Summary 1: How is a row organized during sorting?

  • A sort record consists of the sort field + the addon field, where the sort field is the field(s) after order by, and the addon field is the field(s) that need to be accessed. For example, in ‘select a1,a2,a3 from test order by a2,a3’, the sort field is ‘a2,a3’ and the addon field is ‘a1,a2,a3’. Variable-length fields in the sort field cannot be packed/compressed; for example, varchar uses its defined size to compute space. Note that this is an important factor in why sorting uses a lot of space.
  • If, when computing the space of the sort field, a field’s size exceeds max_sort_length, then it is computed using the size specified by max_sort_length.
  • For a sort record, if the length of the sort field + addon field exceeds max_length_for_sort_data, then the addon field will not be stored; instead, the sort field + ref field is used, where the ref field is the primary key or ROWID. At this point the original filesort algorithm (sort with table lookup) is used.
  • If the addon field contains variable-length fields such as varchar, then the pack technique is used for compression to save space.

You can refer to sections 3, 4, 5, 6, and 8.

Summary 2: What method is used for sorting?

  • original filesort algorithm (sort with table lookup)

If the sort uses the sort field + ref field, then a table lookup is required to obtain the needed data. If the sort used a temporary file (i.e., external merge sort, when the sort volume is large), then batch table lookups are used. Batch table lookups involve the memory size specified by the read_rnd_buffer_size parameter, mainly used for sorting and returning results. If the sort did not use a temporary file (in-memory sort can complete it, when the sort volume is small), then single-row table lookups are used.

  • modified filesort algorithm (sort without table lookup)

If the sort uses the sort field + addon field, then sort-without-table-lookup is used: all needed fields are stored during the sorting process, and variable-length fields in the addon field can be packed for compression to save space. Additionally, the sort field and the addon field may contain duplicate fields — for example, in Example 2, the sort field is a2, a3, and the addon field is a1, a2, a3. This is another reason why sorting uses a lot of space.

You can see which method was used in OPTIMIZER_TRACE; see section 12.

Summary 3: Does each sort always allocate the memory size specified by the sort_buffer_size parameter?

No. MySQL does a preliminary calculation, comparing the upper bound of rows that the InnoDB clustered index may store against the upper bound of rows that the memory size specified by sort_buffer_size can hold, and takes the smaller of the two to determine the final memory allocation size — the goal being to save memory space.

You can see the memory size used in OPTIMIZER_TRACE; see sections 8 and 12.

Summary 4: What is the difference between examined_rows in OPTIMIZER_TRACE and Rows_examined in the slow query log?

  • Rows_examined in the slow query log includes duplicate counting; the duplicate part is the portion that was sorted after filtering by the where condition.
  • examined_rows in OPTIMIZER_TRACE does not include duplicate counting; it is the actual number of rows scanned at the InnoDB layer.

You can refer to section 11.

Summary 5: How are external-sort temporary files used?

In fact, a statement uses more than one temporary file, but they all start with MY and are placed in the tmpdir directory; lsof can show these files.

  • Temporary file 1: used to store the results of the in-memory sort, in units of chunks, where one chunk’s size is the sort buffer’s size.
  • Temporary file 2: based on the previous temporary file 1, used for merge sort.
  • Temporary file 3: stores the final merge-sort result, dropping the sort field and keeping only the addon field (the fields that need to be accessed) or the ref field (ROWID or primary key), so it is generally smaller than the previous two temporary files.

But they don’t all exist at the same time: either temporary file 1 and temporary file 2 exist, or temporary file 2 and temporary file 3 exist. To see the use of temporary files, you can check Sort_merge_passes; its value indirectly reflects the size of the external sort volume.

You can refer to section 10.

Summary 6: Which algorithm did the sort use?

Although this article doesn’t cover the algorithms, there are two internal sort algorithms you should know about:

  • In-memory sort (priority queue, commonly used with order by limit to return a small number of rows, improving sort efficiency; but note that with order by limit n,m, if n is too large, it may involve switching the sort algorithm)
  • In-memory sort (quicksort)

You can check whether the priority-queue algorithm was used via OPTIMIZER_TRACE; see section 12.

Summary 7: What exactly is the “Creating sort index” state?

All the sorting flows we discussed above are contained within this state, including:

  • Obtaining the data needed for sorting (e.g., in the example, the full table scan obtaining data from the InnoDB layer)
  • Filtering data by the where condition
  • In-memory sort
  • External sort

Summary 8: How to avoid temporary files getting too large?

First, consider whether an index can be used to avoid sorting. If not, you need to consider the following points:

  • Keep the fields after order by to just what meets the requirement, as few as possible.
  • Make the fields involved after order by fixed-length field types as far as possible, rather than variable-length types like varchar — because the sort field cannot be compressed.
  • Don’t define variable-length fields too large; define them reasonably. For example, if varchar(10) meets the requirement, don’t use varchar(50). Although this space is compressed when stored at the InnoDB layer, the MySQL layer may use the full length (e.g., for the sort field).
  • In queries, avoid using (select *) and instead use the fields you actually need to query, which reduces the number of addon fields. In another article of mine I also describe the other drawbacks of (select *); see: https://www.jianshu.com/p/ce063e2024ad

1. Starting from a Problem

This is a case a friend recently ran into. The gist is: my table is only about 30G in InnoDB, so why did a temporary file reach over 200G after performing a sort with the following statement? Of course the statement is bizarre — let’s not ask for now why such a statement exists; we only need to study the principle. Section 13 of this article explains the reason and reproduces the problem.

The temporary files are as follows.

Below is the case information:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
show create table  t\G
*************************** 1. row ***************************
       Table: t
Create Table: CREATE TABLE `t` (
  `ID` bigint(20) NOT NULL COMMENT 'ID',
  `UNLOAD_TASK_NO` varchar(50) NOT NULL ,
  `FORKLIFT_TICKETS_COUNT` bigint(20) DEFAULT NULL COMMENT 'forklift ticket count',
  `MANAGE_STATUS` varchar(20) DEFAULT NULL COMMENT 'management status',
  `TRAY_BINDING_TASK_NO` varchar(50) NOT NULL ,
  `STATISTIC_STATUS` varchar(50) NOT NULL ,
  `CREATE_NO` varchar(50) DEFAULT NULL ,
  `UPDATE_NO` varchar(50) DEFAULT NULL ,
  `CREATE_NAME` varchar(200) DEFAULT NULL COMMENT 'creator name',
  `UPDATE_NAME` varchar(200) DEFAULT NULL COMMENT 'updater name',
  `CREATE_ORG_CODE` varchar(200) DEFAULT NULL COMMENT 'creator org code',
  `UPDATE_ORG_CODE` varchar(200) DEFAULT NULL COMMENT 'updater org code',
  `CREATE_ORG_NAME` varchar(1000) DEFAULT NULL COMMENT 'creator org name',
  `UPDATE_ORG_NAME` varchar(1000) DEFAULT NULL COMMENT 'updater org name',
  `CREATE_TIME` datetime DEFAULT NULL COMMENT 'create time',
  `UPDATE_TIME` datetime DEFAULT NULL COMMENT 'update time',
  `DATA_STATUS` varchar(50) DEFAULT NULL COMMENT 'data status',
  `OPERATION_DEVICE` varchar(200) DEFAULT NULL COMMENT 'operation device',
  `OPERATION_DEVICE_CODE` varchar(200) DEFAULT NULL COMMENT 'operation device code',
  `OPERATION_CODE` varchar(50) DEFAULT NULL COMMENT 'operation code',
  `OPERATION_ASSIST_CODE` varchar(50) DEFAULT NULL COMMENT 'assist operation code',
  `CONTROL_STATUS` varchar(50) DEFAULT NULL COMMENT 'control status',
  `OPERATOR_NO` varchar(50) DEFAULT NULL COMMENT 'operator employee no',
  `OPERATOR_NAME` varchar(200) DEFAULT NULL COMMENT 'operator name',
  `OPERATION_ORG_CODE` varchar(50) DEFAULT NULL COMMENT 'operation dept code',
  `OPERATION_ORG_NAME` varchar(200) DEFAULT NULL COMMENT 'operation dept name',
  `OPERATION_TIME` datetime DEFAULT NULL COMMENT 'operation time',
  `OPERATOR_DEPT_NO` varchar(50) NOT NULL COMMENT 'operator dept code',
  `OPERATOR_DEPT_NAME` varchar(200) NOT NULL COMMENT 'operator dept name',
  `FORKLIFT_DRIVER_NAME` varchar(200) DEFAULT NULL ,
  `FORKLIFT_DRIVER_NO` varchar(50) DEFAULT NULL ,
  `FORKLIFT_DRIVER_DEPT_NAME` varchar(200) DEFAULT NULL ,
  `FORKLIFT_DRIVER_DEPT_NO` varchar(50) DEFAULT NULL ,
  `FORKLIFT_SCAN_TIME` datetime DEFAULT NULL ,
  `OUT_FIELD_CODE` varchar(200) DEFAULT NULL,
  PRIMARY KEY (`ID`),
  KEY `IDX_TRAY_BINDING_TASK_NO` (`TRAY_BINDING_TASK_NO`),
  KEY `IDX_OPERATION_ORG_CODE` (`OPERATION_ORG_CODE`),
  KEY `IDX_OPERATION_TIME` (`OPERATION_TIME`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=8



desc 
SELECT 
    ID,
    UNLOAD_TASK_NO,
    FORKLIFT_TICKETS_COUNT,
    MANAGE_STATUS,
    TRAY_BINDING_TASK_NO,
    STATISTIC_STATUS,
    CREATE_NO,
    UPDATE_NO,
    CREATE_NAME,
    UPDATE_NAME,
    CREATE_ORG_CODE,
    UPDATE_ORG_CODE,
    CREATE_ORG_NAME,
    UPDATE_ORG_NAME,
    CREATE_TIME,
    UPDATE_TIME,
    DATA_STATUS,
    OPERATION_DEVICE,
    OPERATION_DEVICE_CODE,
    OPERATION_CODE,
    OPERATION_ASSIST_CODE,
    CONTROL_STATUS,
    OPERATOR_NO,
    OPERATOR_NAME,
    OPERATION_ORG_CODE,
    OPERATION_ORG_NAME,
    OPERATION_TIME,
    OPERATOR_DEPT_NO,
    OPERATOR_DEPT_NAME,
    FORKLIFT_DRIVER_NAME,
    FORKLIFT_DRIVER_NO,
    FORKLIFT_DRIVER_DEPT_NAME,
    FORKLIFT_DRIVER_DEPT_NO,
    FORKLIFT_SCAN_TIME,
    OUT_FIELD_CODE
FROM
    t
GROUP BY id , UNLOAD_TASK_NO , FORKLIFT_TICKETS_COUNT , 
MANAGE_STATUS , TRAY_BINDING_TASK_NO , STATISTIC_STATUS , 
CREATE_NO , UPDATE_NO , CREATE_NAME , UPDATE_NAME , 
CREATE_ORG_CODE , UPDATE_ORG_CODE , CREATE_ORG_NAME , 
UPDATE_ORG_NAME , CREATE_TIME , UPDATE_TIME , DATA_STATUS , 
OPERATION_DEVICE , OPERATION_DEVICE_CODE , OPERATION_CODE , 
OPERATION_ASSIST_CODE , CONTROL_STATUS , OPERATOR_NO ,
OPERATOR_NAME , OPERATION_ORG_CODE , OPERATION_ORG_NAME , 
OPERATION_TIME , OPERATOR_DEPT_NO , OPERATOR_DEPT_NAME , 
FORKLIFT_DRIVER_NAME , FORKLIFT_DRIVER_NO , 
FORKLIFT_DRIVER_DEPT_NAME , FORKLIFT_DRIVER_DEPT_NO ,
FORKLIFT_SCAN_TIME , OUT_FIELD_CODE;


+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table                   | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra          |
+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
|  1 | SIMPLE      | t | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 5381145 |   100.00 | Using filesort |
+----+-------------+-------------------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
1 row in set, 1 warning (0.00 sec)

You might wonder what this statement is good for. Let’s set aside its function for now and only consider the question of why it generates a 200G temporary file.

Next I’ll analyze the sorting flow in stages. Note that the entire sorting flow is under the state ‘Creating sort index’. We’ll start the analysis from the filesort function interface.

2. Test Cases

To better illustrate the flow that follows, we use two tables that are completely identical except for field lengths. Note, however, that these two tables have very little data, so no external sort will occur; when external sort is involved, we’ll have to assume their data volume is large. We also divide them according to the original filesort algorithm and the modified filesort algorithm, but these two methods haven’t been explained yet, so don’t worry too much about them.

  • original filesort algorithm (sort with table lookup)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
mysql> show create table tests1 \G
*************************** 1. row ***************************
       Table: tests1
Create Table: CREATE TABLE `tests1` (
  `a1` varchar(300) DEFAULT NULL,
  `a2` varchar(300) DEFAULT NULL,
  `a3` varchar(300) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

mysql> select * from tests1;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| a    | a    | a    |
| a    | b    | b    |
| a    | c    | c    |
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
| c    | g    | g    |
| c    | h    | h    |
+------+------+------+
8 rows in set (0.00 sec)

mysql> desc select * from tests1 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | tests1 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    8 |    12.50 | Using where; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)
  • modified filesort algorithm (sort without table lookup)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
mysql> desc select * from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | tests2 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    8 |    12.50 | Using where; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> show create table tests2 \G
*************************** 1. row ***************************
       Table: tests2
Create Table: CREATE TABLE `tests2` (
  `a1` varchar(20) DEFAULT NULL,
  `a2` varchar(20) DEFAULT NULL,
  `a3` varchar(20) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

mysql> select * from tests2;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| a    | a    | a    |
| a    | b    | b    |
| a    | c    | c    |
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
| c    | g    | g    |
| c    | h    | h    |
+------+------+------+
8 rows in set (0.00 sec)

mysql> desc select * from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | tests2 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    8 |    12.50 | Using where; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.01 sec)

We’ll start the whole discussion from the filesort function interface. Sections 3 through 10 below are the main sorting flow.

3. Stage 1: Determine the Sort Fields and Order

This mainly stores the sort order into the sortorder of the Filesort class. For example, order by a2,a3 in our case refers to the a2 and a3 columns. The main interface is Filesort::make_sortorder. Following the source code’s description, we call this the sort field (sort_length in the source). Clearly, during sorting, besides the sort field, we should also include additional fields. Exactly which fields are included depends on the method — original filesort algorithm (sort with table lookup) or modified filesort algorithm (sort without table lookup) — discussed below.

4. Stage 2: Compute the Length of the Sort Field

This mainly calls the sortlength function. This step brings in the setting of the max_sort_length parameter for the judgment; by default, max_sort_length is 1024 bytes.

The rough steps are:

  1. Loop over each sort field.
  2. Compute the length of each sort field: the formula is ≈ defined length * 2.

For example, here I defined a1 varchar(300), so its computed length ≈ 300 * 2 (600). Why * 2? This should be related to Unicode encoding; you can refer to the function my_strnxfrmlen_utf8. Also note this is approximate, because the source code has other considerations, such as whether a character can be null, but it doesn’t take up much so we won’t consider it.

  1. Bring in the max_sort_length parameter for the calculation.

OK, now that we have the length of one sort field, we compare it with max_sort_length: if this sort field is greater than max_sort_length’s value, then max_sort_length’s setting prevails. The code for this step is as follows:

1
set_if_smaller(sortorder->length, thd->variables.max_sort_length);

So, if some field of the sort field exceeds the max_sort_length setting, then the sort may not be that precise.

By this point, the length of each sort field and the total length of the sort field have been computed. For example, in the two different cases given earlier:

  • (a2 varchar(300) a3 varchar(300) order by a2,a3): each sort field is about 300*2 bytes, and the total length of the two fields is about 1200 bytes.
  • (a2 varchar(20) a3 varchar(20) order by a2,a3): each sort field is about 20*2 bytes, and the total length of the two fields is about 80 bytes.

And it’s worth noting that this is computed by the defined size — e.g., varchar(300) is computed as 300 characters — rather than the number of characters actually occupied in InnoDB, which is what we usually see. This is one reason why sorting uses more space than the actual InnoDB data file size.

Below, taking (a2 varchar(300) a3 varchar(300) order by a2,a3) as an example, let’s actually look at the debug result:

1
2
3
4
5
6
7
(gdb) p sortorder->field->field_name
$4 = 0x7ffe7800fadf "a3"
(gdb) p sortorder->length
$5 = 600
(gdb) p  total_length
$6 = 1202 (here a2,a3 can be NULL, each adding 1 byte)
(gdb)

As you can see, there’s no problem.

  1. The loop ends, computing the total length of the sort field.

Later we’ll see that the sort field cannot use the pack technique.

5. Stage 3: Compute the Space for Additional Fields

For sorting, it’s clear that besides the sort field, what we usually need is the actual data. There are essentially two approaches:

  • original filesort algorithm: store only the rowid or primary key as the additional field, then do a table lookup to extract data. Following the source code’s description, we call this associated table-lookup field the ref field (the variable is called ref_length in the source).
  • modified filesort algorithm: put all the fields in the read_set (the fields that need to be read) into the additional fields, so no table lookup is needed to read data. Following the source code’s description, we call these additionally stored fields the addon fields (the variable is called addon_length in the source).

This step is about judging which algorithm to use. The main criterion is the parameter max_length_for_sort_data, whose default size is 1024 bytes; but as we’ll see later, the computation here is whether (sort field length + total addon field) exceeds max_length_for_sort_data. Additionally, if the modified filesort algorithm is used, then a pack will be done on each addon field, mainly to compress the null bytes and save space.

The main entry function for this step is Filesort::get_addon_fields. Below is the step-by-step analysis.

  1. Loop over all fields of this table.
  2. Filter out fields that don’t need to be stored, based on read_set.

Fields that don’t need to be accessed naturally won’t be included. Below is the source filtering code:

1
2
if (!bitmap_is_set(read_set, field->field_index)) // is it in the read set?
      continue;
  1. Get the field’s length.

This is the actual length now. For example, our a1 varchar(300) with charset UTF8 has a length ≈ 300*3 (900).

  1. Get the length of fields that can be packed.

Unlike the above, for fixed-length type fields such as int, only variable-length type fields need packing.

  1. The loop ends, getting the total length of the addon fields and the total length of fields that can be packed.

After the loop ends, you can get the total length of the addon fields. But note that the addon field and the sort field may contain duplicate fields — for example, in Example 2 the sort field is a2, a3, and the addon field is a1, a2, a3.

If the following condition is met:

total length of addon fields + total length of sort fields > max_length_for_sort_data

then the original filesort algorithm (sort with table lookup) will be used; otherwise, the modified filesort algorithm is used. Here is this line of code:

1
2
3
4
5
6
  if (total_length + sortlength > max_length_for_sort_data) // if the length is greater than max_length_for_sort_data, exit
  {
    DBUG_ASSERT(addon_fields == NULL);
    return NULL;
// return NULL, no packing, use original filesort algorithm (sort with table lookup)
  }

Back to the first case in the example in section 2: because we need to access a1, a2, a3, and they are all varchar(300) UTF8, the addon field length is about 300 * 3 * 3 = 2700 bytes. We also computed earlier that the sort field is about 1202 bytes, so 2700+1202 is far greater than the default max_length_for_sort_data setting of 1024 bytes, so the original filesort algorithm will be used for sorting.

What about the second case in the example in section 2? Clearly it’s much smaller (each field varchar(20)), about 20 * 3 * 3 (addon field) + 82 (sort field), which is less than 1024 bytes, so the modified filesort algorithm sort method will be used, and these addon fields can basically all use the pack technique to save space. But note that no matter what, the (sort field) cannot be packed, while fixed-length types don’t need packing to compress space.

6. Stage 4: Determine the Length of Each Row

With the computation above, we get the length of each row (the length before packing, if packing is possible). Below is this computation process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (using_addon_fields()) 
// if the pack technique is used, check whether the addon_fields array exists; use the modified filesort algorithm, sort without table lookup
  {
    res_length= addon_length; // total length; 3 varchar(300) utf8 is 3*300*3
  }
  else // use the original filesort algorithm
  {
    res_length= ref_length;   // rowid (primary key length)
    /* 
      The reference to the record is considered 
      as an additional sorted field
    */
    sort_length+= ref_length;  // essentially rowid (primary key) + sort field length; sort with table lookup
  }
  /*
    Add hash at the end of sort key to order cut values correctly.
    Needed for GROUPing, rather than for ORDERing.
  */
  if (use_hash)
    sort_length+= sizeof(ulonglong);

  rec_length= sort_length + addon_length; 
// modified filesort algorithm: sort_length is the sort-key length, addon_length is the length of accessed fields; original filesort algorithm: rowid (primary key) + sort field length, since addon_length is 0

OK, let’s summarize a bit:

  • original filesort algorithm: each row’s length is the total length of the sort field + the ref field length (primary key or rowid).
  • modified filesort algorithm: each row’s length is the total length of the sort field + the addon field length (the total length of the fields that need to be accessed).

Of course, which algorithm is used — see the previous section. But note that for variable-length types like varchar, the defined size prevails — e.g., UTF8 varchar(300) is 300*3 = 900 rather than the actual stored size — while fixed length is unchanged.

OK, let’s look back at the two examples in section 2 and compute their row lengths respectively:

  • Example 1: According to our computation, it will use the original filesort algorithm sort method, and the final computed row length should be (sort field length + rowid length) ≈ 1202+6 bytes. Below is the debug result:
1
2
(gdb) p rec_length
$1 = 1208
  • Example 2: According to our computation, it will use the modified filesort algorithm sort method, and the final computed row length should be (sort field length + addon field length) ≈ 82 + 20 * 3 * 3 (result is 262). Note this is approximate, not accounting for non-null and variable-length factors. Below is the debug result:
1
2
(gdb) p rec_length
$2 = 266

As you can see, the error is small.

7. Stage 5: Determine the Maximum Memory Allocation

The memory allocated here is related to the sort_buffer_size parameter. But does it always allocate at least sort_buffer_size of memory each time? Actually no. MySQL judges whether the table is small — that is, it does a simple computation, with the goal of saving memory overhead — which we’ll describe here.

  1. Roughly compute the number of rows in the InnoDB layer’s primary-key leaf nodes.

This step mainly computes an upper bound on rows via (the space size of the clustered index leaf nodes / the size of each clustered index row * 2), calling the function ha_innobase::estimate_rows_upper_bound. The source is as follows:

1
2
 num_rows= table->file->estimate_rows_upper_bound(); 
// the upper bound comes from the InnoDB clustered-index leaf nodes / clustered-index length * 2

Then the result is stored. If the table is very small, then this value will be very small.

  1. Based on the previously computed per-row length, compute the maximum number of rows the sort buffer can hold.

This step computes the maximum number of rows the sort buffer can hold as follows:

1
2
ha_rows keys= memory_available / (param.rec_length + sizeof(char*));
// number of rows that can be sorted; the maximum number of rows the sort buffer can sort
  1. Compare the two and take the minimum as the standard for allocating memory.

Then compare the two values and take the smaller, as follows:

1
2
param.max_keys_per_buffer= (uint) min(num_rows > 0 ? num_rows : 1, keys);
// the smaller of the stored row upper bound and the number of sortable rows
  1. Allocate memory based on the result.

Allocate as follows:

1
table_sort.alloc_sort_buffer(param.max_keys_per_buffer, param.rec_length);

That is, allocate based on the total computed row length and the computed number of rows.

8. Stage 6: Read Data and Perform In-Memory Sort

By this point the preparation is done. Next, data is read row by row, and then the data remaining after filtering by the where condition is sorted. If there is a lot of data to sort, then after the sort memory fills up, an in-memory sort is performed, and the sorted content is written to a sort temporary file, awaiting the next step of external merge sort. For merge sort, each merged file fragment must be sorted, otherwise merge sort cannot complete; therefore, after the sort memory fills up, an in-memory sort must be done. What if it doesn’t fill up? Then a single in-memory sort is enough. Let’s look at this process; the whole process is concentrated in the find_all_keys function.

  1. Read the needed data.

Actually, before this step, read_set is also changed, because for the original filesort algorithm (sort with table lookup), not all needed fields are read. For simplicity, we won’t describe it.

This step reads one row of data. Here it enters the InnoDB layer to read data; the specific flow won’t be explained. Below is this line of code:

1
error= file->ha_rnd_next(sort_form->record[0]); // read one row of data
  1. Increment Rows_examined by 1.

This metric corresponds to Rows_examined in the slow query log. This metric will be double-counted when there is sorting, but here it is still correct; the duplicate part is discussed later.

  1. Filter out the where condition.

This filters out rows that don’t satisfy the where condition. The code is as follows:

1
2
if (!error && !qep_tab->skip_record(thd, &skip_record) && !skip_record) 
// here it does the where filter condition comparison
  1. Write the row data into the sort buffer.

This step writes the data into the sort buffer. Note this does not involve a sort operation; it only stores the data in memory. It’s divided into 2 parts:

  • Write the sort field. If it’s the original filesort algorithm, then rowid (primary key) is also included.
  • Write the addon field. This only happens with the modified filesort algorithm; before writing, it also calls Field::pack to compress fields that can be packed. The pack function for varchar fields is Field_varstring::pack — simply put, it stores the actual size rather than the defined size.

The whole process is in find_all_keys -> Sort_param::make_sortkey. This step also involves a question we care a lot about — exactly how the sorted data is stored — which needs careful reading.

Below, let’s debug the different storage methods of the two examples in section 2. Since we want to look at the data in memory, we just need to look at what the final copied memory data is, and then the truth will come out. We just need to put a breakpoint on the find_all_keys function and look at memory after the Sort_param::make_sortkey operation for one row of data, as follows:

  • Example 1 (all fields are varchar(300)): It will use the original filesort algorithm (sort with table lookup), and what should ultimately be stored is the sort field (a2, a3) + rowid.

The sort result is as follows:

1
2
3
4
5
6
7
8
9
mysql> select * from test.tests1 where a1='b' order by a2,a3;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
+------+------+------+
3 rows in set (9.06 sec)

We take the second row as the target to view.

Due to space constraints, I’ll show part of it, because here there are about 1200-some bytes, as follows:

1
2
3
4
5
6
7
8
9
(gdb) x/1300bx start_of_rec
0x7ffe7ca79998: 0x01    0x00    0x45    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799a0: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799a8: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799b0: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799b8: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799c0: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7ca799c8: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
...

This is followed by a large amount of 0X20 0X00.

We see a large amount of 0X20 0X00 — these are exactly the placeholders. The actual useful data is only the two bytes 0x45 0x00, where 0x45 is exactly our uppercase letter E, i.e., the e in the data, which is related to the comparison character set. The 0X20 0X00 here takes up a lot of space. We initially computed the sort field to be about 1200 bytes, but in fact only a few bytes are useful.

For the sort field, this is much larger than the actual stored data.

  • Example 2 (all fields are varchar(20)): It will use the modified filesort algorithm, and what should ultimately be stored is the sort field (a2, a3) + the addon field (the needed fields, here a1, a2, a3).

The sort result is as follows:

1
2
3
4
5
6
7
8
mysql> select * from test.tests2 where a1='b' order by a2,a3;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
+------+------+------+

We take the first row as the target to view.

The data here is not large; after compression it’s only 91 bytes. Let’s view it all, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(gdb) p rec_sz
$6 = 91
(gdb) x/91x start_of_rec 
0x7ffe7c991bc0: 0x01    0x00    0x44    0x00    0x20    0x00    0x20    0x00
0x7ffe7c991bc8: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7c991bd0: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7c991bd8: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7c991be0: 0x20    0x00    0x20    0x00    0x20    0x00    0x20    0x00
0x7ffe7c991be8: 0x20    0x01    0x00    0x44    0x00    0x20    0x00    0x20
0x7ffe7c991bf0: 0x00    0x20    0x00    0x20    0x00    0x20    0x00    0x20
0x7ffe7c991bf8: 0x00    0x20    0x00    0x20    0x00    0x20    0x00    0x20
0x7ffe7c991c00: 0x00    0x20    0x00    0x20    0x00    0x20    0x00    0x20
0x7ffe7c991c08: 0x00    0x20    0x00    0x20    0x00    0x20    0x00    0x20
0x7ffe7c991c10: 0x00    0x20    0x07    0x00    0x00    0x01    0x62    0x01
0x7ffe7c991c18: 0x64    0x01    0x64

This is the whole row record. We find that, for the sort field, there’s no compression — it’s still 0x20 0x00 placeholders — while for the addon field (the needed fields, here a1, a2, a3), it’s much smaller here, because it’s been packed, i.e.:

1
2
3
4
5
0x01 0x62: data b

0x01 0x64: data d

0x01 0x64: data d

And 0x01 should be the length.

In any case, for the sort field, it’s still much larger than the actual stored data.

  1. If the sort buffer is full, sort the data in the sort buffer, then write it to a temporary file.

If the volume of data to be sorted is very large, then the sort buffer certainly can’t hold it. So if it fills up, an in-memory sort operation is performed once, then the sorted data is written to the external sort file — this is called a chunk. The location of the external file is specified by the tmpdir parameter, and the name starts with MY. Note that external sort usually requires 2 temporary files; this is the first, used to store the in-memory sort result, written in chunk units. As follows:

1
2
3
4
5
6
7
8
9
10
if (fs_info->isfull()) // if the sort buffer is full and the sort buffer has finished sorting
        {
          if (write_keys(param, fs_info, idx, chunk_file, tempfile)) // write to physical file, complete in-memory sort; if memory won't fill up, this won't run, and sorting completes in create_sort_index
          {
            num_records= HA_POS_ERROR;
            goto cleanup;
          }
          idx= 0;
          indexpos++;
        }

Eventually it calls the write_keys function to sort and write to the external sort file. The core here is to sort first, then loop over each sort file and write it to the external sort file. Below, let me verify the length written to the temporary file. I expanded the data of Example 2 in section 2 N-fold to make it use external file sort. Below is the verification result; just set a breakpoint at write_keys:

1
2
3
1161        if (my_b_write(tempfile, record, rec_length))
(gdb) p rec_length
$8 = 91

We can see each row’s length is still 91 bytes (after packing/compression), consistent with the length seen earlier, indicating that this data is written completely intact to the external sort file, which is obviously much larger than we’d imagine.

OK, at this point the data has been found. If it exceeds the sort buffer’s size, the result needed for external sort has already been stored in temporary file 1, and it is stored to the temporary file in fragments (chunks), with the name starting with MY.

9. Stage 7: Output the Sort-Method Summary

This makes a staged summary of the sorting process above. The code is as follows:

1
2
3
4
5
6
7
8
9
10
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() ?
               "<sort_key, packed_additional_fields>" :
               param.using_addon_fields() ?
               "<sort_key, additional_fields>" : "<sort_key, rowid>");

Let’s parse it:

  • rows: the number of rows sorted, i.e., the number of rows remaining after applying the where filter condition.
  • examined_rows: the number of rows scanned at the InnoDB layer. Note this is not the Rows_examined in the slow query log; this is an accurate result with no double counting.
  • number_of_tmp_files: during external sort, the number of chunks in the temporary file used to save results. Each time the sort buffer fills and is sorted, it’s written to one chunk, but all chunks coexist in one temporary file.
  • sort_buffer_size: the memory size used by the internal sort, which is not necessarily the size specified by the sort_buffer_size parameter.
  • sort_mode: explained here as follows.
  1. sort_key, packed_additional_fields: the modified filesort algorithm (sort without table lookup) was used, and there are packed fields, usually variable-length fields such as varchar.
  2. sort_key, additional_fields: the modified filesort algorithm (sort without table lookup) was used, but there are no fields that need packing, e.g., all fixed-length fields.
  3. sort_key, rowid: the original filesort algorithm (sort with table lookup) was used.

10. Stage 8: Perform the Final Sort

This involves 2 parts:

  • If the sort buffer is not full, then sorting begins here, calling the function save_index.
  • If the sort buffer is full, then a merge sort is performed, calling merge_many_buff -> merge_buffers, and finally merge_index completes the merge sort.

For merge sort, this may generate another 2 temporary files to store the final sort result. They still start with MY, and are still stored in the location specified by the tmpdir parameter. So in external sort, 3 temporary files may be generated, summarized as follows:

  • Temporary file 1: used to store the in-memory sort result, in chunk units, where one chunk’s size is the sort buffer’s size.
  • Temporary file 2: based on the previous temporary file 1, used for merge sort.
  • Temporary file 3: stores the final merge-sort result, dropping the sort field and keeping only the addon field (the fields that need to be accessed) or the ref field (ROWID or primary key), so it is generally smaller than the previous two temporary files.

But they don’t all exist at the same time: either temporary file 1 and temporary file 2 exist, or temporary file 2 and temporary file 3 exist.

This is easy to verify; just put breakpoints on merge_buffers and merge_index, as follows.

Temporary file 1 and temporary file 2 exist at the same time:

1
2
3
[root@gp1 test]# lsof|grep tmp/MY
mysqld     8769     mysql   70u      REG              252,3   79167488    2249135 /mysqldata/mysql3340/tmp/MYt1QIvr (deleted)
mysqld     8769     mysql   71u      REG              252,3   58327040    2249242 /mysqldata/mysql3340/tmp/MY4CrO4m (deleted)

Temporary file 2 and temporary file 3 coexist:

1
2
3
[root@gp1 test]# lsof|grep tmp/MY
mysqld     8769     mysql   70u      REG              252,3     360448    2249135 /mysqldata/mysql3340/tmp/MYg109Wp (deleted)
mysqld     8769     mysql   71u      REG              252,3   79167488    2249242 /mysqldata/mysql3340/tmp/MY4CrO4m (deleted)

But due to limited ability, I haven’t carefully studied the specific process of merge sort; here I’ll just give a rough interface. Note that each call to merge_buffers increments Sort_merge_passes by 1 — this should be the number of merges, and the magnitude of this increment can indirectly reflect the size of the temporary files used by external sort.

11. Other Sorting Issues

This describes 2 additional sorting issues.

  1. The table lookup of the original filesort algorithm (sort with table lookup)

Finally, for the original filesort algorithm (sort with table lookup) sort method, a table lookup to obtain data may still be needed. This step may use the memory size defined by the read_rnd_buffer_size parameter.

For example, the first example in section 2 will use the original filesort algorithm (sort with table lookup), but the table-lookup operation has the following criteria:

  • If no external-sort temporary file is used, it means the sort volume is not large, so the ordinary table-lookup method is used, calling the function rr_from_pointers, i.e., the single-row table-lookup method.
  • If an external-sort temporary file is used, it means the sort volume is large, requiring the batch table-lookup method. In this case the rough steps are: read the sorted rowids (primary keys), then do batch table lookups, which is completed in the memory specified by read_rnd_buffer_size, calling the function rr_from_cache. This is also an optimization, because table lookups are generally scattered and very costly.
  1. About the computation of Rows_examined during sorting

First, the value I’m referring to is the Rows_examined in the slow query log. During sorting, double counting may occur. Section 8 above already explained this; this value is still correct in section 8, but in the end, when the data satisfying the where condition is returned, the function evaluate_join_record is also called, and as a result Rows_examined increases by the number of rows satisfying the where condition. Again, taking the two examples in section 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
mysql> select * from test.tests1 where a1='b' order by a2,a3;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
+------+------+------+
3 rows in set (5.11 sec)

mysql> select * from test.tests2 where a1='b' order by a2,a3;
+------+------+------+
| a1   | a2   | a3   |
+------+------+------+
| b    | d    | d    |
| b    | e    | e    |
| b    | f    | f    |
+------+------+------+
3 rows in set (5.28 sec)

mysql> desc select * from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | tests2 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    8 |    12.50 | Using where; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

8 rows in set (0.00 sec)

mysql> desc select * from tests2 where a1='b' order by a2,a3;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | tests2 | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    8 |    12.50 | Using where; Using filesort |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.01 sec)

The slow query log is as follows. Don’t fixate on the time (because I deliberately paused for a while during debug); we only focus on Rows_examined, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Time: 2019-12-23T12:03:26.108529+08:00
# User@Host: root[root] @ localhost []  Id:     4
# Schema:   Last_errno: 0  Killed: 0
# Query_time: 5.118098  Lock_time: 0.000716  Rows_sent: 3  Rows_examined: 11  Rows_affected: 0
# Bytes_sent: 184
SET timestamp=1577073806;
select * from test.tests1 where a1='b' order by a2,a3;
# Time: 2019-12-23T12:03:36.138274+08:00
# User@Host: root[root] @ localhost []  Id:     4
# Schema:   Last_errno: 0  Killed: 0
# Query_time: 5.285573  Lock_time: 0.000640  Rows_sent: 3  Rows_examined: 11  Rows_affected: 0
# Bytes_sent: 184
SET timestamp=1577073816;
select * from test.tests2 where a1='b' order by a2,a3;

We can see Rows_examined is 11 in both. Why 11? Clearly, the total number of rows we scan is 8 (this is a full table scan, the table has 8 rows total), and after filtering, the result needing sorting is 3 rows, and these 3 rows are double-counted once. So it’s 8+3=11, meaning 3 rows were double-counted.

12. View the Sort Result via OPTIMIZER_TRACE

To use OPTIMIZER_TRACE, just run “SET optimizer_trace=”enabled=on”;”, and after running the statement, check information_schema.OPTIMIZER_TRACE.

In section 9 we explained the meaning of the sort-method summary output. Here let’s look at the concrete result, still taking the 2 examples in section 2:

  • Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
"filesort_priority_queue_optimization": {
  "usable": false,
  "cause": "not applicable (no LIMIT)"
},
"filesort_execution": [
],
"filesort_summary": {
  "rows": 3,
  "examined_rows": 8,
  "number_of_tmp_files": 0,
  "sort_buffer_size": 1285312,
  "sort_mode": "<sort_key, rowid>"
  • Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
"filesort_priority_queue_optimization": {
  "usable": false,
  "cause": "not applicable (no LIMIT)"
},
"filesort_execution": [
],
"filesort_summary": {
  "rows": 3,
  "examined_rows": 8,
  "number_of_tmp_files": 0,
  "sort_buffer_size": 322920,
  "sort_mode": "<sort_key, packed_additional_fields>"

Now we understand. These summaries are actually generated during the execution stage. A few points to note:

  • The examined_rows here is different from Rows_examined in the slow query log, because here there’s no double counting — it’s accurate.
  • It also indicates whether priority-queue sort was used, i.e., the “filesort_priority_queue_optimization” part.
  • Via “sort_buffer_size”, you can see that the size specified by the sort_buffer_size parameter was not allocated here, saving memory; this was explained in section 7.

The other metrics were already explained in section 9 and won’t be described again.

13. Back to the Problem Itself

OK, I’ve described the rough flow. These are the main flows; the actual flow is much more complex. Now let’s return to the original case. Its max_sort_length and max_length_for_sort_data are both the default value of 1024.

The group by in the case is actually a sort operation, as we can see from the execution plan. So let’s first analyze its sort field. Clearly, everything after group by is a sort field. Among them, the field CREATE_ORG_NAME is defined as varchar(1000), and its occupied space is (1000 * 2), i.e., 2000 bytes, but this exceeds max_sort_length, so it’s 1024 bytes. Likewise, the UPDATE_ORG_NAME field is also varchar(1000) and is treated the same way. The other fields won’t exceed the max_sort_length limit, and as said in section 5, the sort field won’t be compressed.

I roughly computed that the total size of the sort field is about (3900 * 2) bytes. As you can see, the sort field of one row of data basically reaches 8K of capacity, while the addon field’s length (before packing/compression) would be even larger, clearly exceeding the max_length_for_sort_data setting. So for such a sort, it’s obviously impossible to use the modified filesort algorithm (sort without table lookup); the original filesort algorithm (sort with table lookup) is used. So one row’s record is (sort field + primary key), and the primary key size is negligible, making the final size of one row’s record about 8K. This value is usually far larger than the size of varchar fields stored after InnoDB compression — which is why, in this example, although the table is only about 30G, the temporary file reached over 200G.

OK, let’s reproduce the problem. We use Example 1 from section 2 and increase its data. In principle, Example 1 will use the original filesort algorithm (sort with table lookup), because here the total length of the sort field (a2, a3) + the length of the addon field (a1, a2, a3) is about 300 * 2 * 2 + 300 * 3 * 3, which clearly exceeds max_length_for_sort_data. So one row’s length for this sort is the sort field (a2, a3) + the ref field (ROWID), about 300 * 2 * 2 + 6 = 1206 bytes. Below is this table’s total data and InnoDB file size (I call it the bgtest5 table here):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
mysql> show create table bgtest5 \G
*************************** 1. row ***************************
       Table: bgtest5
Create Table: CREATE TABLE `bgtest5` (
  `a1` varchar(300) DEFAULT NULL,
  `a2` varchar(300) DEFAULT NULL,
  `a3` varchar(300) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.01 sec)

mysql> SELECT COUNT(*) FROM bgtest5;
+----------+
| COUNT(*) |
+----------+
|    65536 |
+----------+
1 row in set (5.91 sec)

mysql> desc select * from bgtest5  order by a2,a3;
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra          |
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
|  1 | SIMPLE      | bgtest5 | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 66034 |   100.00 | Using filesort |
+----+-------------+---------+------------+------+---------------+------+---------+------+-------+----------+----------------+
1 row in set, 1 warning (0.00 sec)

Note this is a full-table sort now, with no where filter condition. Below is the size of this table’s ibd file:

1
2
3
[root@gp1 test]# du -hs bgtest5.ibd
11M     bgtest5.ibd
[root@gp1 test]#

Next we need to put the gdb breakpoint on merge_many_buff. Our goal is to observe the size of temporary file 1, which, as said earlier, stores the in-memory sort result, as follows:

1
2
[root@gp1 test]# lsof|grep tmp/MY
mysqld     8769     mysql   69u      REG              252,3   79101952    2249135 /mysqldata/mysql3340/tmp/MYzfek5x (deleted)

You can see this file’s size is 79101952 bytes, i.e., about 80M, which matches our computed total of 1206 (per-row size) * 65535 (number of rows) ≈ 80M. This far exceeds the ibd file’s size of 11M, and note that another file of roughly the same size will subsequently be generated to store the merge-sort result, as follows:

1
2
3
[root@gp1 test]# lsof|grep tmp/MY
mysqld     8769     mysql   69u      REG              252,3   79167488    2249135 /mysqldata/mysql3340/tmp/MYzfek5x (deleted)
mysqld     8769     mysql   70u      REG              252,3   58327040    2249242 /mysqldata/mysql3340/tmp/MY8UOLKa (deleted)

This proves it: the phenomenon of sort temporary files being far larger than the ibd file is indeed possible.