indexmerge的數據結構和成本評估

前面以案例的形式介紹了什么是index merge，以及它的使用場景。本文將介紹index merge實現的主要數據結構以及MySQL如何評估index merge的成本。在開始本文之前，需要先理解Range訪問相關的數據結構介紹：SEL_ARG結構，SEL_TREE結構。 1. 概述:index merge的

前面以案例的形式介紹了什么是index merge，以及它的使用場景。本文將介紹index merge實現的主要數據結構以及MySQL如何評估index merge的成本。在開始本文之前，需要先理解Range訪問相關的數據結構介紹：SEL_ARG結構，SEL_TREE結構。

1. 概述:index merge的數據結構

index merge的主要數據結構仍然是存放在SEL_TREE中：

class SEL_TREE :public Sql_alloc
{
...
 List merges;
...
};

在merges這個list中存放了所有可能的index merge。本文將從幾個案例，來看看SEL_TREE/SEL_IMERGE如何代表一個index merge訪問方式。本文將不再重復介紹SEL_ARG/SEL_TREE的Range相關結構。

SEL_IMERGE的主要成員是一個SEL_TREE的鏈表，每一個SEL_TREE代表了一個獨立的索引條件，這個鏈表中多個條件共同構成這個index merge。我們通過兩個案例看看一個SEL_TREE如何表示一個index merge。(這里需要注意，SEL_TREE既可以代表一個RANGE條件，也可以代表一個index merge；代表Range時，其merges成員為空)。

2. 案例1:簡單的index merge

SELECT * FROM tmp_sel_tree where 
 ( key1_part1 = 1 or (key1_part2 = 2 and key2_part1 = 3) ) or
 ( key3_part1 = 5 )

這是一個多個索引的index merge，且沒有任何的range可以使用。or條件的三個分支，分表可以使用一個獨立的索引，其構成的SEL_TREE結構如下：

SEL_TREE
 |
 |-->List merges;
 |
 | / SEL_TREE-> SEL_ARG(key1_part1 = 1)
 \ SEL_IMERGE1 | SEL_TREE-> SEL_ARG(key2_part1 = 3)
 \ SEL_TREE-> SEL_ARG(key3_part1 = 5)

3. 案例2:單個查詢多個index merge

SELECT * FROM tmp_sel_tree where 
 ( key1_part1 = 1 or (key1_part2 = 2 and key2_part1 = 3) ) and
 ( key3_part1 = 5 or key2_part1 = 5)

這個案例中，And條件兩邊都可以各自使用index merge，MySQL可以選擇其中任何一個執行。對應的SEL_TREE中，將會有多個SEL_IMERGE對象，每個SEL_IMERGE對象里面存儲了多個獨立的可以使用索引的條件(有獨立的SEL_TREE表示)：

SEL_TREE
 |
 \-->List merges;
 |
 | / SEL_TREE-> SEL_ARG(key1_part1 = 1)
 | SEL_IMERGE1 | SEL_TREE-> SEL_ARG(key2_part1 = 3)
 | \ SEL_TREE-> SEL_ARG(key3_part1 = 5)
 |
 | / SEL_TREE-> SEL_ARG(key2_part1 = 5)
 \ SEL_IMERGE2 | 
 \ SEL_TREE-> SEL_ARG(key3_part1 = 5)

MySQL會在選擇執行計劃時，逐一評估每個SEL_IMERGE的成本，然后選擇最優的執行計劃。

4. 成本計算

MySQL在計算index merge的成本時，分開考慮了ROR和non-ROR的場景。所以這里先單獨介紹一下什么是ROR，后面再介紹MySQL如何區別對待ROR的成本計算。

4.1 什么是Rowid-Ordered Retrieval

Rowid-Ordered Retrieval簡稱ROR?？聪旅娴恼f明。有基于索引的查詢：

"key_1=c_1 AND ... AND key_n=c_n"

該索引定義為：(key_1, ..., key_N [,a_1, ..., a_m])，且主鍵列為(a_1, ..., a_m, b1, ..., b_k)，并且n >= N。

那么這個查詢就是一個ROR查詢。簡單說明：對于該索引左前綴(key_1,...key_n)都是定值，對應該值的子樹順序是按照剩余索引列來排序的，而剩余的索引列又都是主鍵最左前綴，所以子樹的順序恰好同主鍵順序相同。

(這一段可以參考函數is_key_scan_ror的注釋和實現部分)

示例：

CREATE TABLE `tmp_index_merge` (
 `id` int(11) NOT NULL,
 `key1_part1` int(11) NOT NULL,
 `key1_part2` int(11) NOT NULL,
 `key2_part1` int(11) NOT NULL,
 `key2_part2` int(11) NOT NULL,
 `key2_part3` int(11) NOT NULL,
 `key3_part1` int(11) NOT NULL DEFAULT '4',
 PRIMARY KEY (`id`),
 KEY `ind2` (`key2_part1`,`key2_part2`,`key2_part3`),
 KEY `ind1` (`key1_part1`,`key1_part2`,`id`),
 KEY `ind3` (`key3_part1`,`id`)
) ENGINE=InnoDB;
explain select * from tmp_index_merge where (key1_part1 = 4333 and key1_part2 = 1657) or (key3_part1 = 2877);
j+----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+
| 1 | SIMPLE | tmp_index_merge | index_merge | ind1,ind3 | ind1,ind3 | 8,4 | NULL | 2 | Using union(ind1,ind3); Using where |
+----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+
這就是一個ROR的index查詢。ROR在Explain的執行計劃中并沒有任何體現，通過在代碼中設置斷點可以觀察到。在函數get_best_disjunct_quick中，代碼會跳到標簽skip_to_ror_scan處執行。

在對index merge的成本評估時，只有所有的SEL_TREE子樹都是ROR的，對應的SEL_IMERGE才是ROR的。后面我們將看看ROR和non-ROR在成本評估上的不同。

4.2 成本概述

一個index merge是由多個SEL_TREE子樹組成，每個SEL_TREE對應一個range操作(參考)，所以每個SEL_TREE成本仍然會按照range操作類似各自計算成本，并累加。

各個SEL_TREE子樹各自獲取ROWIDs后，MySQL需要對這些ROWID進行去重，最后根據ROWID獲取所有數據。去重操作其實是一個對多組ROWID歸并排序的問題。對于ROR和non-ROR場景歸并排序復雜度略有不同。對于non-ROR的場景，需要先進行分組排序，然后合并。而對于ROR，因為ROWID是順序的，所以前面的分組排序就省略了，直接做合并操作，這讓non-ROR和ROR在成本計算上有較大的不同。

在完成去重之后，最后是根據ROWID取出主鍵的成本(對應的二級索引里面取出的ROWID)。

一個細節：如果某個SEL_TREE對應的索引恰好是主鍵索引時，那么MySQL會在其他SEL_TREE子樹掃描時，直接判斷掃描出來的ROWID是否在主鍵對應的SEL_TREE的range內，如果這個ROWID已經存在，則不在記錄。這樣可以盡可能的減少歸并排序的元素個數。我們稱這部分成本味"二級ROWID過濾成本"。

4.3 SEL_TREE子樹的成本

這部分成本計算與range成本計算相同(參考)，這里會將多個子樹成本單獨計算并累加。

for (every SEL_TREE IN SEL_IMERGE){
 cur_child= get_key_scans_params(param, *ptree, TRUE, FALSE, read_time);
 imerge_cost += (*cur_child)->read_cost;
 ......
}

4.4 non-ROR場景的成本計算

這里通過排序進行去重，是典型的歸并排序，如果超過MySQL排序內存的限制，則是典型的外排序。先分組做紅黑樹排序，然后進行合并。成本分為幾部分：創建紅黑樹、外排時磁盤讀寫、最后順序讀取排序結果。

4.4.1 去重復成本計算概述

這部分的成本可以完整的參考函數Unique::get_use_cost，這里做一個較為詳細的補充說明。

對這個問題做一個簡單的抽象：有兩部分數據，第一部分有cpk_scan_records條，已排序。第二部分有non_cpk_scan_records未排序，現在需要返回去重后所有數據。單條數據大小為key_size，可用內存為max_in_memory_size。因為前面對第二部數據做了"二級ROWID過濾"，所以這部分ROWID跟第一部分沒有重復。因此，僅這里的第二部分數據需要進行去重。去重通過一個排序實現。

簡單的說，需要對non_cpk_scan_records條記錄進行外排序，最大可用內存是max_in_memory_size，單條記錄大小是key_size。排序分成兩部分，對部分數據做排序，然后合并。

4.4.2 二級ROWID過濾成本

如果有子樹SEL_TREE是對應主鍵聚簇索引，另一部分子樹SEL_TREE對應二級索引，那么在遍歷二級索引時將取出對應的ROWID，看看是否再聚簇索引的SEL_TREE子樹中，如果是，那么可以忽略這個ROWID，以免重復計算(減少后面Unique操作)。這部分的成本計算為：

imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID;

另外，這里記cpk_scan_records為主鍵聚簇索引對應的SEL_TREE返回的ROWID數量，non_cpk_scan_records為二級索引對應的所有SEL_TREE返回的ROWID數量。

4.4.3 排序比較成本

需要進行N=non_cpk_scan_records*key_size/max_in_memory_size次排序。在每次排序過程中，如果已經排序好的記錄樹m個，那么新增一條記錄平均需要做log2(m+1)次比較操作，m取值是從1,2...N。比較操作的成本為log2((m+1)!)，MySQL使用了如下公式計算log2((m+1)!)：

\[n! \approx \sqrt{2{\pi}n}(\frac{n}{e})^n\]

\[\log{n!} \approx \log{\sqrt{2{\pi}n}} + n*\log{\frac{n}{e}} \]

這里log是2為底數，再使用\[log_{n}{m} = \frac{\lg{n}}{\lg{m}}\] 通過此公式底數都可以轉換為10進行運算(這一部并不是必須的，不過MySQL是這樣計算的)。

階乘轉換參考：斯特靈公式(口味略重，慎入)。

對應的代碼段：

result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
result /= TIME_FOR_COMPARE_ROWID;

4.4.4 外排序時候的磁盤IO成本

在外排的時候，需要對所有的數據進行一次IO操作，成本計算如下：

293 result += DISK_SEEK_BASE_COST * n_full_trees * max_elements_in_tree / IO_SIZE;
295 result += DISK_SEEK_BASE_COST * key_size * last_tree_elems / IO_SIZE;

第一行是完整樹的IO成本，第二部分是最后一個可能不完整樹的IO成本。

4.4.5 合并成本

最后是合并成本，這是一個典型的歸并排序，是對K個有序列表進行歸并，時間復雜度為：

\[O(N*\lg{K})\]

歸并過程中有一次讀寫操作，IO和比較成本加起來就是合并的成本：

\[\frac{total\_buf\_elems*\log(n\_buffers)}{TIME\_FOR\_COMPARE\_ROWID*\log2} + 2*\frac{total\_buf\_elems*elem\_size}{IO\_SIZE} \]

total_buf_elems是總元素個數；n_buffers子樹數量；elem_size為單個元素大小。

未盡的細節：MySQL一次最多對15(MERGEBUFF2)顆子樹做歸并。

4.4.6 最后的讀取

這時，完成了所有的排序操作，最后是讀取結果到內存的成本：

result += ceil((double)key_size*nkeys/IO_SIZE);

4.4.7 根據ROWID取出記錄的成本

所有非聚簇索引掃描獲得ROWID后，最后仍然需要根據這些ROWID獲取記錄。

對于索引組織表(聚簇索引，InnoDB)，這部分的成本計算較為簡單，假設聚簇索引的總page為total_pages，這里二級索引取出的rowid數量為rows，該表的總記錄樹為total_rows，那么成本為：

(rows / total_rows) *total_pages

代碼參考：

imerge_cost += get_sweep_read_cost(param, non_cpk_scan_records);

4.5 ROR場景的成本計算

ROR的時候，去重時則少了對子隊列的排序，直接是對多個已經排列好的隊列做合并排序。所以這里的成本計算相對簡單：索引讀取，合并排序，最后是根據ROWID取出所有記錄的成本。

4.5.1 索引讀取成本

這部分計算與索引覆蓋掃描計算相同。假設單個索引塊大小為BS，索引字段長度味KL，ROWID長度為RL，總是假設索引塊有50%為空，如果需要掃描的記錄數為RS，那么這部分成本計算為：

\[\frac{RS}{\frac{1}{2}\frac{BS}{(KL+RL)}}\]

參考函數get_index_only_read_time的實現。

4.5.2 合并排序

這次合并排序，是對多個有序列表的合并。若有K個有序列表，總記錄數味N，那么其成本為：

\[O(N*\lg{K})\]

這里N為各個SEL_TREE子樹對應found_records之和(MySQL這里的計算略微不同)。

4.5.3 根據ROWID取出記錄的成本

這部分成本于NON-ROR場景相同，對于索引組織表(聚簇索引，InnoDB)，這部分的成本計算較為簡單，假設聚簇索引的總page為total_pages，這里二級索引取出的rowid數量為rows，該表的總記錄樹為total_rows，那么成本為：

(rows / total_rows) *total_pages

在MySQL中，對于上面表達式的rows計算做了一些不一樣的處理。這里說一下主要思想，MySQL假設每個SEL_TREE完全獨立，總記錄數味R，如果有三個SEL_TREE子樹，記對應的記錄數為R(1),R(2),R(3)。如果數據都均勻分布，那么去重后總記錄數為：

(R(1)+R(2)+R(3)) - R(a)*(R(1)*R(2)+R(2)+R(3)+R(1)*R(3))/R(a)^2 + R(a)*((R(1)*R(2)*R3)/R(a)^3)

MySQL這里做了一個近似：

(R(1)+R(2)+R(3)) - R(a)*((R(1)*R(2)*R3)/R(a)^3)

MySQL利用這個近似值作為上面公式的rows。到這里ROR部分成本就完成了。

5 最后

最后，如果index merge的成本比其他執行計劃的成本要更小的話，那么MySQL就會選擇改執行計劃。案例可以參考index merge介紹。

原文地址：index merge的數據結構和成本評估, 感謝原作者分享。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com