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

Today, when I saw the Index Merge Optimization of the MYSQL manual, I couldn't help but have some ideas, so record it as follows

Let's first explain the differences in two ways:

Both methods are done using different secondary indexes in a table, note that it is a single table.

Merge union: when using or, if the secondary index contains all the key part, then you can get the key value or ROWID of the sorted clustered index, then the simple union deduplication is fine without the need for additional sorting.

Source code interface quick_ror_union_select class

Merge sort_union: unlike the above, it does not contain all the key part of the secondary index, so you must first obtain the sorted clustered index key value or ROWID before you can union the clustered index key value or ROWID.

Source code interface quick_index_merge_select

Reference manual: 9.2.1.4 Index Merge Optimization

In general, additional sorting operations are required as long as mysql is not sure that the primary key is sorted.

If we have some knowledge of merge sort algorithm, we can see that this kind of processing is necessary.

We know that all the subsets that need to be merged need to be sorted when merging. Here is a diagram of a simple merging algorithm:

If we think of 1259 and 347.8 as primary key, then they need to be sorted in order to complete the final merger.

Of course, the sorting operation of the upper layer can be merged or other sorting methods can be used, as long as the sorting is good. Another point is merging.

Sorting friends who are familiar with data structures should know that it is also a good way to sort external disks.

To understand here, we need to have an understanding of the arrangement of composite indexes in INNODB B+ tree page blocks:

For example, seq int,id1 int,id2 int seq is the primary key and ID1,DI2 is a combined B+ index.

So we insert the value.

Values (1, 1, 1, 2)

Values (2, 1, 1, 3)

Values (3, 1, 1, 2)

Obviously, the leaf nodes in the composite index are arranged in the following order:

1 2 3

Id1:1 id1:1 id1:1

Id2:2 id2:2 id2:3

Seq:1 seq:3 seq:2

That is, first sort by id1, then sort by id2, and finally sort by primary key seq.

So you can see that the order of the final primary keys is 1-3-2, which is not in order, obviously.

The result set cannot be used as the result set of the merge, so we need to sort it, which is why

The source of sort_union sort.

So let's demonstrate the differences between the two execution plans.

Script:

Create table testmer

(seq int,id1 int,id2 int,id3 int,id4 int,primary key (seq), key (id1,id2), key (id3,id4))

Insert into testmer values (1, 2, 4, 4)

Insert into testmer values (2, 1, 3, 4, 5)

Insert into testmer values (3, 1, 2, 4)

Insert into testmer values (4, 2, 4, 5, 6)

Insert into testmer values (5, 2, 6, 5, 8)

Insert into testmer values (6, 2, 10, 5, 3)

Insert into testmer values (7, 4, 5, 8, 10)

Insert into testmer values (8, 0, 1, 3, 4)

Mysql > select * from testmer

+-+

| | seq | id1 | id2 | id3 | id4 | |

+-+

| | 1 | 1 | 2 | 4 | 4 |

| | 2 | 1 | 3 | 4 | 5 |

| | 3 | 1 | 2 | 4 | 4 |

| | 4 | 2 | 4 | 5 | 6 | |

| | 5 | 2 | 6 | 5 | 8 | |

| | 6 | 2 | 10 | 5 | 3 |

| | 7 | 4 | 5 | 8 | 10 | |

| | 8 | 0 | 1 | 3 | 4 | |

+-+

Using sort_union:

Mysql > explain select * from testmer force index (id1,id3) where id1=1 or id3=4

+- -- +

| | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |

+- -- +

| | 1 | SIMPLE | testmer | NULL | index_merge | id1,id3 | id1,id3 | 5 Magi 5 | NULL | 6 | 100.00 | Using sort_union (id1,id3); Using where |

+- -- +

1 row in set, 1 warning (5.07 sec)

It's obvious that you need to sort just by looking at key (id1,id2), because the order is as follows:

1 2 3

Id1:1 id1:1 id1:1

Id2:2 id2:2 id2:3

Seq:1 seq:3 seq:2

If we take the second-level index KEY_PART with all

Mysql > explain select * from testmer force index (id1,id3) where id1=1 and id2=2 or id3=4 and id4=1

+- -- +

| | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |

+- -- +

| | 1 | SIMPLE | testmer | NULL | index_merge | id1,id3 | id1,id3 | 10 Magi 10 | NULL | 2 | 100.00 | Using union (id1,id3); Using where |

+- -- +

Of course there is no need for sorting here. Let's look at id1=1 and id2=2 (the same is true of id3=4 and id4=1).

The arrangement is as follows:

1 2

Id1:1 id1:1

Id2:2 id2:2

Seq:1 seq:3

That is to say, if the KEY_PART contains complete results, then the primary key is naturally sorted.

Actually, I ran in the DEBUG environment, and the breakpoint hit Unique::unique_add.

(gdb) info b

Num Type Disp Enb Address What

1 breakpoint keep y 0x0000000000ebd333 in main (int, char**) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/main.cc:25

Breakpoint already hit 1 time

6 breakpoint keep y 0x000000000145de13 in Unique::unique_add (void*) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/uniques.h:52

Breakpoint already hit 2 times

Executing select * from testmer force index (id1,id3) where id1=1 and id2=1 or id3=4 and id4=1

No Unique::unique_add is triggered, that is, no sort operation is performed.

Finally, the interface of merge_sort sorting of source code is explained.

QUICK_INDEX_MERGE_SELECT::read_keys_and_merge ()

Call

Unique::unique_add

(using balanced binary trees, balanced binary tree non-red-black tree distinction reference:

Http://blog.itpub.net/7728585/viewspace-2127419/

)

The following is a comment for the source code read_keys_and_merge ():

/ *

Perform key scans for all used indexes (except CPK), get rowids and merge

Them into an ordered non-recurrent sequence of rowids.

The merge/duplicate removal is performed using Unique class. We put all

Rowids into Unique, get the sorted sequence and destroy the Unique.

If table has a clustered primary key that covers all rows (TRUE for bdb

And innodb currently) and one of the index_merge scans is a scan on competition

Then rows that will be retrieved by competes for scan are not put into Unique and

Primary key scan is not performed here, it is performed later separately.

RETURN

0 OK

Other error

, /

Here is my stack information when I gdb:

(gdb) bt

# 0 tree_insert (tree=0x7fffd801c768, key=0x7fffd801ada0, key_size=0, custom_arg=0x7fffd80103d0) at / root/mysql5.7.14/percona-server-5.7.14-7/mysys/tree.c:207

# 1 0x000000000145df19 in Unique::unique_add (this=0x7fffd801c260, ptr=0x7fffd801ada0) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/uniques.h:56

# 2 0x000000000178e6a8 in QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x7fffd89083f0) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/opt_range.cc:10700

# 3 0x0000000001778c73 in QUICK_INDEX_MERGE_SELECT::reset (this=0x7fffd89083f0) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/opt_range.cc:1601

# 4 0x000000000155e529 in join_init_read_record (tab=0x7fffd8906e20) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_executor.cc:2471

# 5 0x000000000155b6a1 in sub_select (join=0x7fffd8905b08, qep_tab=0x7fffd8906e20, end_of_records=false)

At / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_executor.cc:1271

# 6 0x000000000155b026 in do_select (join=0x7fffd8905b08) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_executor.cc:944

# 7 0x0000000001558efc in JOIN::exec (this=0x7fffd8905b08) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_executor.cc:199

# 8 0x00000000015f91c6 in handle_query (thd=0x7fffd8000df0, lex=0x7fffd80033d0, result=0x7fffd8007a60, added_options=0, removed_options=0)

At / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_select.cc:184

# 9 0x00000000015ac025 in execute_sqlcom_select (thd=0x7fffd8000df0, all_tables=0x7fffd8006e98) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_parse.cc:5391

# 10 0x00000000015a4640 in mysql_execute_command (thd=0x7fffd8000df0, first_level=true) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_parse.cc:2889

# 11 0x00000000015acff6 in mysql_parse (thd=0x7fffd8000df0, parser_state=0x7ffff0fd6600) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_parse.cc:5836

# 12 0x00000000015a0eb5 in dispatch_command (thd=0x7fffd8000df0, com_data=0x7ffff0fd6d70, command=COM_QUERY)

At / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_parse.cc:1447

# 13 0x000000000159fce6 in do_command (thd=0x7fffd8000df0) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/sql_parse.cc:1010

# 14 0x00000000016e1c08 in handle_connection (arg=0x3c1c880) at / root/mysql5.7.14/percona-server-5.7.14-7/sql/conn_handler/connection_handler_per_thread.cc:312

# 15 0x0000000001d71ed0 in pfs_spawn_thread (arg=0x3bec1b0) at / root/mysql5.7.14/percona-server-5.7.14-7/storage/perfschema/pfs.cc:2188

# 16 0x0000003ca62079d1 in start_thread () from / lib64/libpthread.so.0

# 17 0x0000003ca5ee8b6d in clone () from / lib64/libc.so.6

Attach two kinds of function interface calls:

Merge sort_union:

Titled 3: | > QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT

Titled 3: | QUICK_INDEX_MERGE_SELECT::init

Titled 3: | QUICK_INDEX_MERGE_SELECT::reset

Titled 3: | > QUICK_INDEX_MERGE_SELECT::read_keys_and_merge

Troup3: |

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.