mysql merge Union merge sort_union の違い

MYSQLマニュアルのIndex Merge Optimizationを見て、アイデアが浮かんだので以下のように記録しました

まず、2つの方法の違いを説明しましょう:
どちらの方法もテーブル内で異なるセカンダリインデックスを使用しますそれらは単一の表面であることに注意してください。
マージユニオン: or を使用する場合、セカンダリ インデックスにすべてのキー部分が含まれている場合、並べ替えられたクラスター化インデックスのキー値または ROWID を取得できます。重複を削除するには単純なユニオンで十分であり、追加の並べ替えは必要ありません。コード インターフェイス Quick_ror_union_select クラス
merge sort_union: 上記との違いは、セカンダリ インデックスのすべてのキー部分が含まれていないため、クラスター化インデックスのキー値を結合する前に、まずソートされたクラスター化インデックスのキー値または ROWID を取得する必要があることです。または ROWID 操作
ソース コード インターフェイス Quick_index_merge_select
リファレンス マニュアル: 9.2.1.4 インデックス マージの最適化
一般に、主キーがソートされていることを mysql が判断できない限り、追加のソート操作が必要です。


マージソートアルゴリズムをある程度理解していれば、そのような処理が必要であることが分かります。
マージする際には、マージする必要があるすべてのサブセットをソートする必要があることがわかります。アルゴリズム:

1 2 5 9 と 3 4 7 8 を主キーとみなす場合、最終的なマージを完了するにはそれらをソートする必要があります。 もちろん、上位のソート操作をマージすることも、他のソートを行うこともできます。ソートが適切に行われている限り、この方法を使用します。もう 1 つのポイントは、マージ

ソートのデータ構造に精通している友人なら、マージ
ソートが外部ディスクのソートにも良い方法であることを知っているはずです。

ここを理解するには、INNODB B+ ツリー ページ ブロック内の結合インデックスの配置を理解する必要があります:
例: seq int、id1 int、id2 int seq は主キー、ID1、DI2 は結合されたキーです。 B+ インデックス
次に、値

values(1,1,2)
values(2,1,3)
values(3,1,2)

を挿入します。明らかに、結合されたインデックス内のリーフ ノードの順序は次のとおりです:

1       2       3
id1:1  id1:1  id1:1
id2:2  id2:2  id2:3
seq:1  seq:3  seq:2

つまり、最初に id1 で並べ替え、次に id2 で並べ替え、最後に ID で並べ替えます。主キーの配列

すると、最終的な主キーの順序が 1 3 2 であることがわかります。明らかに、このような
結果セットはマージされた結果セットとして使用できないため、これをソートする必要があります。
sort_union sort が由来するのはそのためです。

次に、2 つの実行プランの異なる
スクリプトを示してみましょう:

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,1,2,4,4);
insert into testmer values(2,1,3,4,5);
insert into testmer values(3,1,2,4,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,5     | NULL |    6 |   100.00 | Using sort_union(id1,id3); Using where |
+----+-------------+---------+------------+-------------+---------------+---------+---------+------+------+----------+----------------------------------------+
1 row in set, 1 warning (5.07 sec)

配置は次のとおりであるため、ここではキー (id1、id2) を並べ替えるだけでよいことは明らかです:

1 2 3
id1:1 id1 :1 id1:1
id2:2 id2:2 id2:3
seq:1 seq:3 seq:2

セカンダリインデックス KEY_PART を 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,10   | NULL |    2 |   100.00 | Using union(id1,id3); Using where |
+----+-------------+---------+------------+-------------+---------------+---------+---------+------+------+----------+-----------------------------------+

もちろん、ここでソートする必要はありません、 id1=1 と id2 =2 を見ていきます (id3=4 と id4=1 にも同じことが当てはまります)

配置は次のとおりです:

1         2      
id1:1   id1:1   
id2:2   id2:2 
seq:1  seq:3

つまり、KEY_PART に complete が含まれている場合、主キーは次のようになります。

実際、DEBUG 環境で実行しましたが、ブレークポイント 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

select * from testmerforceindex(id1,id3) where id1=1 and id2=1 or id3 を実行すると、 =4 および id4=1;

Unique::unique_add はトリガーされず、並べ替え操作も存在しません。

最後に、ソースコードのmerge_sortソートインターフェースについて説明しましょう
QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
Call
Unique::unique_add
(バランスの取れたバイナリツリーと非赤黒ツリーの違いを参照してください) to:
http://blog.itpub.net/7728585/viewspace-2127419/
)

以下はソースコード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 PK,
  then rows that will be retrieved by PK scan are not put into Unique and 
  primary key scan is not performed here, it is performed later separately.
  RETURN
    0     OK
    other error
*/

以下は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

関数インターフェース呼び出しの2つのメソッドを添付します:

merge sort_union:

T@3: | | | | | | | | | | >QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT
T@3: | | | | | | | | | | <QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT 1589
T@3: | | | | | | | | | | >QUICK_INDEX_MERGE_SELECT::init
T@3: | | | | | | | | | | <QUICK_INDEX_MERGE_SELECT::init 1595
T@3: | | | | | | | | >QUICK_INDEX_MERGE_SELECT::reset
T@3: | | | | | | | | | >QUICK_INDEX_MERGE_SELECT::read_keys_and_merge
T@3: | | | | | | | | | <QUICK_INDEX_MERGE_SELECT::read_keys_and_merge 10716
T@3: | | | | | | | | <QUICK_INDEX_MERGE_SELECT::reset 1602
T@3: | | | | | | | | >QUICK_INDEX_MERGE_SELECT::get_next
T@3: | | | | | | | | <QUICK_INDEX_MERGE_SELECT::get_next 10753
T@3: | | | | | | | | >QUICK_INDEX_MERGE_SELECT::get_next
T@3: | | | | | | | | <QUICK_INDEX_MERGE_SELECT::get_next 10753
T@3: | | | | | | | | >QUICK_INDEX_MERGE_SELECT::get_next
T@3: | | | | | | | | <QUICK_INDEX_MERGE_SELECT::get_next 10753
T@3: | | | | | | | | >QUICK_INDEX_MERGE_SELECT::get_next
T@3: | | | | | | | | <QUICK_INDEX_MERGE_SELECT::get_next 10753
T@3: | | | | | | | >QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT
T@3: | | | | | | | <QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT 1635

merge Union:

T@3: | | | | | | | | | | >QUICK_ROR_UNION_SELECT::init
T@3: | | | | | | | | | | <QUICK_ROR_UNION_SELECT::init 1942
T@3: | | | | | | | | >QUICK_ROR_UNION_SELECT::reset
T@3: | | | | | | | | <QUICK_ROR_UNION_SELECT::reset 2004
T@3: | | | | | | | | >QUICK_ROR_UNION_SELECT::get_next
T@3: | | | | | | | | <QUICK_ROR_UNION_SELECT::get_next 10948
T@3: | | | | | | | | >QUICK_ROR_UNION_SELECT::get_next
T@3: | | | | | | | | <QUICK_ROR_UNION_SELECT::get_next 10948
T@3: | | | | | | | | >QUICK_ROR_UNION_SELECT::get_next
T@3: | | | | | | | | <QUICK_ROR_UNION_SELECT::get_next 10913
T@3: | | | | | | | >QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT
T@3: | | | | | | | <QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT 2021

呼び出しパスを確認し、ソースコードの呼び出し状況を確認することができます。並べ替えが実際に行われていることを確認してから、どのような並べ替え方法が使用されているかを確認してください。

この記事は私の個人的な意見のみを示しており、エラーがある場合はプロンプトが表示されます。ありがとう！

上記は、mysql merge Union merge sort_union のさまざまな内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) に注目してください。