前面以案例的形式介紹了什么是index merge，以及它的使用場(chǎng)景。本文將介紹index merge實(shí)現(xiàn)的主要數(shù)據(jù)結(jié)構(gòu)以及MySQL如何評(píng)估index merge的成本。在開(kāi)始本文之前，需要先理解Range訪問(wèn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)介紹：SEL_ARG結(jié)構(gòu)，SEL_TREE結(jié)構(gòu)。 1. 概述:index merge的

前面以案例的形式介紹了什么是index merge，以及它的使用場(chǎng)景。本文將介紹index merge實(shí)現(xiàn)的主要數(shù)據(jù)結(jié)構(gòu)以及MySQL如何評(píng)估index merge的成本。在開(kāi)始本文之前，需要先理解Range訪問(wèn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)介紹：SEL_ARG結(jié)構(gòu)，SEL_TREE結(jié)構(gòu)。

1. 概述:index merge的數(shù)據(jù)結(jié)構(gòu)

index merge的主要數(shù)據(jù)結(jié)構(gòu)仍然是存放在SEL_TREE中：

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

在merges這個(gè)list中存放了所有可能的index merge。本文將從幾個(gè)案例，來(lái)看看SEL_TREE/SEL_IMERGE如何代表一個(gè)index merge訪問(wèn)方式。本文將不再重復(fù)介紹SEL_ARG/SEL_TREE的Range相關(guān)結(jié)構(gòu)。

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

2. 案例1:簡(jiǎn)單的index merge

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

這是一個(gè)多個(gè)索引的index merge，且沒(méi)有任何的range可以使用。or條件的三個(gè)分支，分表可以使用一個(gè)獨(dú)立的索引，其構(gòu)成的SEL_TREE結(jié)構(gòu)如下：

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:單個(gè)查詢(xún)多個(gè)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)

這個(gè)案例中，And條件兩邊都可以各自使用index merge，MySQL可以選擇其中任何一個(gè)執(zhí)行。對(duì)應(yīng)的SEL_TREE中，將會(huì)有多個(gè)SEL_IMERGE對(duì)象，每個(gè)SEL_IMERGE對(duì)象里面存儲(chǔ)了多個(gè)獨(dú)立的可以使用索引的條件(有獨(dú)立的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會(huì)在選擇執(zhí)行計(jì)劃時(shí)，逐一評(píng)估每個(gè)SEL_IMERGE的成本，然后選擇最優(yōu)的執(zhí)行計(jì)劃。

4. 成本計(jì)算

MySQL在計(jì)算index merge的成本時(shí)，分開(kāi)考慮了ROR和non-ROR的場(chǎng)景。所以這里先單獨(dú)介紹一下什么是ROR，后面再介紹MySQL如何區(qū)別對(duì)待ROR的成本計(jì)算。

4.1 什么是Rowid-Ordered Retrieval

Rowid-Ordered Retrieval簡(jiǎn)稱(chēng)ROR。看下面的說(shuō)明。有基于索引的查詢(xún)：

"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。

那么這個(gè)查詢(xún)就是一個(gè)ROR查詢(xún)。簡(jiǎn)單說(shuō)明：對(duì)于該索引左前綴(key_1,...key_n)都是定值，對(duì)應(yīng)該值的子樹(shù)順序是按照剩余索引列來(lái)排序的，而剩余的索引列又都是主鍵最左前綴，所以子樹(shù)的順序恰好同主鍵順序相同。

(這一段可以參考函數(shù)is_key_scan_ror的注釋和實(shí)現(xiàn)部分)

示例：

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 |
+----+-------------+-----------------+-------------+---------------+-----------+---------+------+------+-------------------------------------+
這就是一個(gè)ROR的index查詢(xún)。ROR在Explain的執(zhí)行計(jì)劃中并沒(méi)有任何體現(xiàn)，通過(guò)在代碼中設(shè)置斷點(diǎn)可以觀察到。在函數(shù)get_best_disjunct_quick中，代碼會(huì)跳到標(biāo)簽skip_to_ror_scan處執(zhí)行。

在對(duì)index merge的成本評(píng)估時(shí)，只有所有的SEL_TREE子樹(shù)都是ROR的，對(duì)應(yīng)的SEL_IMERGE才是ROR的。后面我們將看看ROR和non-ROR在成本評(píng)估上的不同。

4.2 成本概述

一個(gè)index merge是由多個(gè)SEL_TREE子樹(shù)組成，每個(gè)SEL_TREE對(duì)應(yīng)一個(gè)range操作(參考)，所以每個(gè)SEL_TREE成本仍然會(huì)按照range操作類(lèi)似各自計(jì)算成本，并累加。

各個(gè)SEL_TREE子樹(shù)各自獲取ROWIDs后，MySQL需要對(duì)這些ROWID進(jìn)行去重，最后根據(jù)ROWID獲取所有數(shù)據(jù)。去重操作其實(shí)是一個(gè)對(duì)多組ROWID歸并排序的問(wèn)題。對(duì)于ROR和non-ROR場(chǎng)景歸并排序復(fù)雜度略有不同。對(duì)于non-ROR的場(chǎng)景，需要先進(jìn)行分組排序，然后合并。而對(duì)于ROR，因?yàn)镽OWID是順序的，所以前面的分組排序就省略了，直接做合并操作，這讓non-ROR和ROR在成本計(jì)算上有較大的不同。

在完成去重之后，最后是根據(jù)ROWID取出主鍵的成本(對(duì)應(yīng)的二級(jí)索引里面取出的ROWID)。

一個(gè)細(xì)節(jié)：如果某個(gè)SEL_TREE對(duì)應(yīng)的索引恰好是主鍵索引時(shí)，那么MySQL會(huì)在其他SEL_TREE子樹(shù)掃描時(shí)，直接判斷掃描出來(lái)的ROWID是否在主鍵對(duì)應(yīng)的SEL_TREE的range內(nèi)，如果這個(gè)ROWID已經(jīng)存在，則不在記錄。這樣可以盡可能的減少歸并排序的元素個(gè)數(shù)。我們稱(chēng)這部分成本味"二級(jí)ROWID過(guò)濾成本"。

4.3 SEL_TREE子樹(shù)的成本

這部分成本計(jì)算與range成本計(jì)算相同(參考)，這里會(huì)將多個(gè)子樹(shù)成本單獨(dú)計(jì)算并累加。

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場(chǎng)景的成本計(jì)算

這里通過(guò)排序進(jìn)行去重，是典型的歸并排序，如果超過(guò)MySQL排序內(nèi)存的限制，則是典型的外排序。先分組做紅黑樹(shù)排序，然后進(jìn)行合并。成本分為幾部分：創(chuàng)建紅黑樹(shù)、外排時(shí)磁盤(pán)讀寫(xiě)、最后順序讀取排序結(jié)果。

4.4.1 去重復(fù)成本計(jì)算概述

這部分的成本可以完整的參考函數(shù)Unique::get_use_cost，這里做一個(gè)較為詳細(xì)的補(bǔ)充說(shuō)明。

對(duì)這個(gè)問(wèn)題做一個(gè)簡(jiǎn)單的抽象：有兩部分?jǐn)?shù)據(jù)，第一部分有cpk_scan_records條，已排序。第二部分有non_cpk_scan_records未排序，現(xiàn)在需要返回去重后所有數(shù)據(jù)。單條數(shù)據(jù)大小為key_size，可用內(nèi)存為max_in_memory_size。因?yàn)榍懊鎸?duì)第二部數(shù)據(jù)做了"二級(jí)ROWID過(guò)濾"，所以這部分ROWID跟第一部分沒(méi)有重復(fù)。因此，僅這里的第二部分?jǐn)?shù)據(jù)需要進(jìn)行去重。去重通過(guò)一個(gè)排序?qū)崿F(xiàn)。

簡(jiǎn)單的說(shuō)，需要對(duì)non_cpk_scan_records條記錄進(jìn)行外排序，最大可用內(nèi)存是max_in_memory_size，單條記錄大小是key_size。排序分成兩部分，對(duì)部分?jǐn)?shù)據(jù)做排序，然后合并。

4.4.2 二級(jí)ROWID過(guò)濾成本

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

imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID;

另外，這里記cpk_scan_records為主鍵聚簇索引對(duì)應(yīng)的SEL_TREE返回的ROWID數(shù)量，non_cpk_scan_records為二級(jí)索引對(duì)應(yīng)的所有SEL_TREE返回的ROWID數(shù)量。

4.4.3 排序比較成本

需要進(jìn)行N=non_cpk_scan_records*key_size/max_in_memory_size次排序。在每次排序過(guò)程中，如果已經(jīng)排序好的記錄樹(shù)m個(gè)，那么新增一條記錄平均需要做log2(m+1)次比較操作，m取值是從1,2...N。比較操作的成本為log2((m+1)!)，MySQL使用了如下公式計(jì)算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為底數(shù)，再使用\[log_{n}{m} = \frac{\lg{n}}{\lg{m}}\] 通過(guò)此公式底數(shù)都可以轉(zhuǎn)換為10進(jìn)行運(yùn)算(這一部并不是必須的，不過(guò)MySQL是這樣計(jì)算的)。

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

對(duì)應(yīng)的代碼段：

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

4.4.4 外排序時(shí)候的磁盤(pán)IO成本

在外排的時(shí)候，需要對(duì)所有的數(shù)據(jù)進(jìn)行一次IO操作，成本計(jì)算如下：

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;

第一行是完整樹(shù)的IO成本，第二部分是最后一個(gè)可能不完整樹(shù)的IO成本。

4.4.5 合并成本

最后是合并成本，這是一個(gè)典型的歸并排序，是對(duì)K個(gè)有序列表進(jìn)行歸并，時(shí)間復(fù)雜度為：

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

歸并過(guò)程中有一次讀寫(xiě)操作，IO和比較成本加起來(lái)就是合并的成本：

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

total_buf_elems是總元素個(gè)數(shù)；n_buffers子樹(shù)數(shù)量；elem_size為單個(gè)元素大小。

未盡的細(xì)節(jié)：MySQL一次最多對(duì)15(MERGEBUFF2)顆子樹(shù)做歸并。

4.4.6 最后的讀取

這時(shí)，完成了所有的排序操作，最后是讀取結(jié)果到內(nèi)存的成本：

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

4.4.7 根據(jù)ROWID取出記錄的成本

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

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

(rows / total_rows) *total_pages

代碼參考：

imerge_cost += get_sweep_read_cost(param, non_cpk_scan_records);

4.5 ROR場(chǎng)景的成本計(jì)算

ROR的時(shí)候，去重時(shí)則少了對(duì)子隊(duì)列的排序，直接是對(duì)多個(gè)已經(jīng)排列好的隊(duì)列做合并排序。所以這里的成本計(jì)算相對(duì)簡(jiǎn)單：索引讀取，合并排序，最后是根據(jù)ROWID取出所有記錄的成本。

4.5.1 索引讀取成本

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

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

參考函數(shù)get_index_only_read_time的實(shí)現(xiàn)。

4.5.2 合并排序

這次合并排序，是對(duì)多個(gè)有序列表的合并。若有K個(gè)有序列表，總記錄數(shù)味N，那么其成本為：

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

這里N為各個(gè)SEL_TREE子樹(shù)對(duì)應(yīng)found_records之和(MySQL這里的計(jì)算略微不同)。

4.5.3 根據(jù)ROWID取出記錄的成本

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

(rows / total_rows) *total_pages

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

(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這里做了一個(gè)近似：

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

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

5 最后

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

原文地址：index merge的數(shù)據(jù)結(jié)構(gòu)和成本評(píng)估, 感謝原作者分享。

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com