點擊下載
本文文檔

當前位置：首頁 - 科技 - 知識百科 - 正文

MySQL源碼:Range和Ref優化的成本評估

來源：懂視網責編：小采時間：2020-11-09 13:14:29

MySQL源碼:Range和Ref優化的成本評估

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

推薦度：

點擊下載本文 文檔為doc格式

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

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

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

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

0. 成本計算的總原則

1. range成本的計算與分析

1.1 range返回的記錄數

1.2 CPU COST

1.3 IO COST

1.4 全表掃描的成本

1.5 關于range執行計劃的分析

1.6 驗證

1.7 一些限制

2. ref成本的計算與分析

2.1 ref返回的記錄數

2.2 CPU COST

2.3 IO COST

2.4 全表掃描的成本

2.5 關于ref執行計劃的分析

2.6 驗證

3. 上面計算的局限性

4. 案例中使用的數據和表

0. 成本計算的總原則

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

總成本＝ CPU COST + IO COST

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

1. range成本的計算與分析

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

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

1.1 range返回的記錄數

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

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的個數。

1.4 全表掃描的成本

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

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

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

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

1.5 關于range執行計劃的分析

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

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

(2) 假設該表的總頁面數(IO COST)為P；單個頁面紀錄數為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優化，而走全表掃描。這里紀錄數超過1016*0.171＝173時將放棄range優化。

1.6 驗證

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

(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命中的記錄數超過173的時候，就會放棄range，選擇全表掃描。

1.7 一些限制

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

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

2. ref成本的計算與分析

2.1 ref返回的記錄數

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

思路：在range優化階段，任何等值都會當作范圍條件（參考1，參考2）。

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

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

所以，返回的紀錄數，使用如下代碼獲取：

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命中多少紀錄則需要多少個IO COST。但是跟range優化打不同的是，這里做了一個修正(range優化并沒有做)，也是IO COST最壞不會超過全表掃描IO消耗的3倍(或者總記錄數除以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是前一次關聯后的記錄數。tmp是當前ref命中的記錄數。這個修正的邏輯是很好理解的：即使加上索引掃描其io cost仍然是有限度的。因為range的評估并沒有加上這個修正，所以就導致了一些奇怪的事情發生了，后面我們再詳細分析這一點。

2.4 全表掃描的成本

簡單版本(不考慮多表關聯)：

scan_time() + s->records/TIME_FOR_COMPARE

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

復雜版本(有多表關聯)：

假設前面關聯后的紀錄數為record_count，當前表的where條件將過濾后剩余3/4的紀錄（不滿足where條件的為1/4），并將這個值記為rnd_records。

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

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

2.5 關于ref執行計劃的分析

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

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

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

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

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

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

(2) 假設該表的總頁面數(IO COST)為P；單個頁面紀錄數為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命中紀錄的預估是取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 |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+

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

3. 上面計算的局限性

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

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

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

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

4. 案例中使用的數據和表

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

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