MySQL源碼:Range和Ref優(yōu)化的成本評估

在開始介紹index merge/ROR優(yōu)化之前，打算先介紹MySQL是如何對range/ref做成本評估的。MySQL是基于成本(cost)模型選擇執(zhí)行計劃，在多個range，全表掃描，ref之間會選擇成本最小的作為最終的執(zhí)行計劃。仍然強烈建議先閱讀登博的slide：《查詢優(yōu)化淺析》，文中

在開始介紹index merge/ROR優(yōu)化之前，打算先介紹MySQL是如何對range/ref做成本評估的。MySQL是基于成本(cost)模型選擇執(zhí)行計劃，在多個range，全表掃描，ref之間會選擇成本最小的作為最終的執(zhí)行計劃。仍然強烈建議先閱讀登博的slide：《查詢優(yōu)化淺析》，文中較為詳細(xì)的介紹MySQL在range優(yōu)化時成本的計算。

本文將繼續(xù)介紹range/ref執(zhí)行計劃選擇的一些不容忽略的細(xì)節(jié)。希望看客能夠通過此文能夠了解更多細(xì)節(jié)。

目錄

0. 成本計算的總原則

MySQL的一個執(zhí)行計劃，有兩部分成本，CPU成本(CPU COST)和IO成本(IO COST)。CPU COST是指查詢出紀(jì)錄后，需要做過濾等處理的時候的CPU消耗，IO COST是指，從存儲引擎讀取數(shù)據(jù)時需要做的IO消耗。

總成本 ＝ CPU COST + IO COST

補充說明：(1) IO成本計算不考慮緩存的影響。因為在優(yōu)化器本身是無法預(yù)知需要的數(shù)據(jù)到底在內(nèi)存中還是磁盤上。

1. range成本的計算與分析

MySQL使用一顆SEL_ARG的樹形結(jié)構(gòu)描述了WHERE條件中的range，如果有多個range，則使用遞歸的方式遍歷SEL_ARG結(jié)構(gòu)，在前面詳細(xì)的介紹range的紅黑樹結(jié)構(gòu)，以及MySQL如何遍歷之。

接上文，這里將看看，遍歷到最后，MySQL如何計算一個簡單range的成本。

1.1 range返回的記錄數(shù)

MySQL首先計算range需要返回都少紀(jì)錄，通過函數(shù)check_quick_select返回對某個索引做range查詢大約命中多少條紀(jì)錄。

found_records= check_quick_select(param, idx, *key, update_tbl_stats);

1.2 CPU COST

#define TIME_FOR_COMPARE 5 // 5 compares == one read
double cpu_cost= (double) found_records / TIME_FOR_COMPARE;

1.3 IO COST

對于InnoDB的二級索引，且不是覆蓋掃描：

found_read_time := number of ranges + found_records

這里，found_records是主要部分，number of ranges表示一共有多少個range，這是一個修正值，表示IO COST不小于range的個數(shù)。

1.4 全表掃描的成本

具體的，對于InnoDB表，我們來看：

read_time= number of total page + （records / TIME_FOR_COMPARE + 1） + 1.1;

對于InnoDB取值為：主鍵索引(數(shù)據(jù))所使用的page數(shù)量(stat_clustered_index_size)

對于MyISAM取值為：stats.data_file_length/IO_SIZE + file->tables

1.5 關(guān)于range執(zhí)行計劃的分析

這里來看看，range的選擇度(selectivty)大概為多少的時候，會放棄range優(yōu)化，而選擇全表掃描。下面時一個定量的分析：

(1) 假設(shè)總記錄數(shù)為R；range需要返回的紀(jì)錄數(shù)為r

(2) 假設(shè)該表的總頁面數(shù)(IO COST)為P；單個頁面紀(jì)錄數(shù)為c

\[r+1\frac{r}{5} > P + \frac{R}{5} + 1 + 1.1 \]

\[ \frac{r}{R} > \frac{1}{6} + \frac{5}{6} * \frac{P}{R} + \frac{5.5}{6*R} \]

\[ \frac{r}{R} > \frac{1}{6} + \frac{5}{6} * \frac{1}{c} \frac{5.5}{6*R} \]

在我的測試案例中，P=4，R=1016 ，有

\[ \frac{r}{R} > 0.171 \]

也就是說這個案例中，如果選擇度(selectivity)高于17.1%就會放棄range優(yōu)化，而走全表掃描。這里紀(jì)錄數(shù)超過1016*0.171＝173時將放棄range優(yōu)化。

1.6 驗證

MySQL通過函數(shù)check_quick_select返回range可能掃描的記錄數(shù)，所以，這里通過對該函數(shù)設(shè)置斷點，并手動設(shè)置返回值，通過此來驗證上面對selectivity的計算，詳細(xì)地：

(gdb) p head->file->stats.records
$1 = 1016
(gdb) p head->file->scan_time()
$3 = 4
(gdb) p 1016*(1.0/6+(5.0/6)*(4.0/1016)+5.5/(6*1016))
$43 = 173.58333333333329
(gdb) b check_quick_select
Breakpoint 5 at 0x679377: file opt_range.cc, line 7436.
(gdb) c
Continuing.
遇到斷點：
(gdb) return 173
看到：
root@test 05:07:52>explain select * from users where reg_date >= '2012-09-20 12:00:00';
+----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+
| 1 | SIMPLE | users | range | ind_regdate | ind_regdate | 9 | NULL | 173 | Using where |
+----+-------------+-------+-------+---------------+-------------+---------+------+------+-------------+
(gdb) return 174
看到
root@test 05:08:05>explain select * from users where reg_date >= '2012-09-20 12:00:00';
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | users | ALL | ind_regdate | NULL | NULL | NULL | 1016 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+

上面可以看到，如果range命中的記錄數(shù)超過173的時候，就會放棄range，選擇全表掃描。

1.7 一些限制

(1) 無論時InnoDB還是MyISAM的scan_time，range返回的記錄數(shù)都不是精確值，而且對于InnoDB，總記錄數(shù)也不是精確值，所以上面只是一個High level的預(yù)估。

(2) 上面案例中，條紀(jì)錄很短，所以看到總page很少，實際情況，單條紀(jì)錄更大，也就是上面的單個頁面紀(jì)錄數(shù)為c更小，所以通常選擇度更高的時候，才會選擇全表掃描。

2. ref成本的計算與分析

2.1 ref返回的記錄數(shù)

ref優(yōu)化的時候，計算返回的記錄數(shù)從代碼上來看要復(fù)雜很多，但是思想很簡單。

思路：在range優(yōu)化階段，任何等值都會當(dāng)作范圍條件（參考1，參考2）。

對于kp1 = const and kp2 = const這類ref，MySQL將直接使用range優(yōu)化時返回的結(jié)果，這個結(jié)果是通過存儲引擎接口records_in_range返回。

還有一類較為特殊的ref，kp1 = const and kp2 > const，對于此類ref，range優(yōu)化的時候，會使用兩個索引列，但是ref只能用一個索引列。這時，ref首先根據(jù)索引統(tǒng)計信息(show index from users中Cardinality的值)預(yù)估。因為這里有range優(yōu)化的值，還會做一次修正，因為range使用了更多的索引字段。修正邏輯為：如果發(fā)現(xiàn)索引統(tǒng)計信息太過保守(例如數(shù)據(jù)分布不均勻時，遇到一個熱點)，這時會用range優(yōu)化的值修正。

所以，返回的紀(jì)錄數(shù)，使用如下代碼獲取：

records= keyinfo->rec_per_key[max_key_part-1]
if(records < (double)table->quick_rows[key]...)
 records= (double)table->quick_rows[key];

2.2 CPU COST

CPU COST := records/(double) TIME_FOR_COMPARE;

2.3 IO COST

ref在做IO成本評估的時候，基本同range相同，ref命中多少紀(jì)錄則需要多少個IO COST。但是跟range優(yōu)化打不同的是，這里做了一個修正(range優(yōu)化并沒有做)，也是IO COST最壞不會超過全表掃描IO消耗的3倍(或者總記錄數(shù)除以10)，有下面的代碼：

s->worst_seeks= min((double) s->found_records / 10,
 (double) s->read_time*3);
IO COST := record_count*min(tmp,s->worst_seeks);

這里record_count是前一次關(guān)聯(lián)后的記錄數(shù)。tmp是當(dāng)前ref命中的記錄數(shù)。這個修正的邏輯是很好理解的：即使加上索引掃描其io cost仍然是有限度的。因為range的評估并沒有加上這個修正，所以就導(dǎo)致了一些奇怪的事情發(fā)生了，后面我們再詳細(xì)分析這一點。

2.4 全表掃描的成本

簡單版本(不考慮多表關(guān)聯(lián))：

scan_time() + s->records/TIME_FOR_COMPARE

scan_time()為存儲引擎返回的全表掃描IO次數(shù)；s->records為存儲引擎維護的單表總紀(jì)錄數(shù)。

復(fù)雜版本(有多表關(guān)聯(lián))：

假設(shè)前面關(guān)聯(lián)后的紀(jì)錄數(shù)為record_count，當(dāng)前表的where條件將過濾后剩余3/4的紀(jì)錄（不滿足where條件的為1/4），并將這個值記為rnd_records。

(s->records - rnd_records)/TIME_FOR_COMPARE +
record_count * (rnd_records/TIME_FOR_COMPARE)

這里假設(shè)將過濾1/4數(shù)據(jù)，實際代碼中還將做一次修正，如果有range計算，假設(shè)其命中q條紀(jì)錄，那么就認(rèn)為將過濾s->records-q條紀(jì)錄。

2.5 關(guān)于ref執(zhí)行計劃的分析

上面的分析，可以看到，ref成本有一部分是取min函數(shù)的，為了分析ref和全表掃描的臨界條件，為了簡化做下面的假設(shè)：

(1) scan_time()*3 < s->records / 10
(2) scan_time()*3 < r 

第一個條件表示約30條紀(jì)錄一個page；第二個條件是ref命中的記錄數(shù)為總頁面的3倍。

那么放棄ref全表掃描的條件是：

scan_time()*3 + r/5 > scan_time() + R/5
即：
scan_time()*2 > (R-r)/5
scan_time() > (R-r)/10
具體的：

(1) 假設(shè)總記錄數(shù)為R；ref需要返回的紀(jì)錄數(shù)為r

(2) 假設(shè)該表的總頁面數(shù)(IO COST)為P；單個頁面紀(jì)錄數(shù)為c

那么range的代價超過全表掃描代價，則有：

\[3*P + \frac{r}{5} > P + \frac{R}{5} \]

\[\frac{r}{R} > 1 - \frac{10*P}{R}\]

\[\frac{r}{R} > 1 - \frac{10}{c}\]

在我的測試案例中，P=6.4，R=900 ，有

\[ \frac{r}{R} > 0.929 \]

對于具體的案例，由于取整的問題，會和上面有小小的偏差：

3*((int)6.39) + r/5 > 6.39453125 + 900/5
r > 841.97

2.6 驗證

這里再通過gdb修改r的值來驗證，因為ref命中紀(jì)錄的預(yù)估是取range的計算值，所以：

gdb) set s->table->quick_rows[1]=841
(gdb) c
root@test 04:37:16>explain select * from users where reg_date = '2012-09-21 12:00:00';
+----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+
| 1 | SIMPLE | users | ref | IND_REGDATE | IND_REGDATE | 9 | const | 841 | Using where |
+----+-------------+-------+------+---------------+-------------+---------+-------+------+-------------+
1 row in set (47.61 sec)
(gdb) set s->table->quick_rows[1]=842
(gdb) c
root@test 04:38:46>explain select * from users where reg_date = '2012-09-21 12:00:00';
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | users | ALL | IND_REGDATE | NULL | NULL | NULL | 900 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+

另一個結(jié)論是，如果當(dāng)條記錄很小，單個頁面的記錄數(shù)很多的話，只有選擇度(selectivity)非常高的時候，MySQL才會放棄ref，走全表掃描，這也是，Vadim在2006年吐槽MySQL的一點。

3. 上面計算的局限性

上面的推倒嘗試介紹一些通用的情況，但是實際上優(yōu)化器中計算ref/range的成本時，會有一些不同：

(1) 無論時InnoDB還是MyISAM的scan_time，range返回的記錄數(shù)都不是精確值，而且對于InnoDB，總記錄數(shù)也不是精確值，所以上面只是一個High level的預(yù)估

(2) 上面案例中，條紀(jì)錄很短，所以看到總page很少，實際情況，單條紀(jì)錄更大，也就是上面的單個頁面紀(jì)錄數(shù)為c更小，所以通常選擇度更高的時候，才會選擇全表掃描。

(3) 上面的計算，都不是覆蓋掃描的情況，覆蓋掃描的時候，成本計算與上面略有不同

(4) 上面都是使用gdb修改某些值的方式來驗證。如果想通過創(chuàng)建一個表，夠造某個索引的區(qū)分度/選制度，因為scan_time和返回的記錄數(shù)都是預(yù)估的，這樣的方式是不行的

4. 案例中使用的數(shù)據(jù)和表

CREATE TABLE `users` (
 `id` int(11) NOT NULL,
 `nick` varchar(32) DEFAULT NULL,
 `reg_date` datetime DEFAULT NULL,
 KEY `IND_NICK` (`nick`),
 KEY `IND_REGDATE` (`reg_date`),
 KEY `IND_ID` (`id`)
) ENGINE=MyISAM
for id in `seq 1 886`; \
do mysql -uroot test -e \
"insert into users values($id,char(round(ord('A') + rand()*(ord('z')-ord('A')))),\
'2012-09-21 12:00:00')" ;done
for id in `seq 887 900`; \
do mysql -uroot test -e \
"insert into users values($id,char(round(ord('A') + rand()*(ord('z')-ord('A')))),\
'2012-09-20 12:00:00')" ;done

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