MySQL · 特性分析 · 優化器 MRR & BKA · 數據庫內核月報

上一篇文章咱們對 ICP 進行了一次全面的分析，本篇文章小編繼續為大家分析優化器的另外兩個選項: MRR & batched_key_access(BKA) ，分析一下他們的作用、原理、相互關系、源碼實現以及使用范圍。 ## 什么是 MRR MRR 的全稱是 Multi-Range Read Optimization，是優化器將隨機 IO 轉化為順序 IO 以降低查詢過程中 IO 開銷的一種手段，咱們對比一下 mrr=on & mrr=off 時的執行計劃：其中表結構如下： ~~~ mysql> show create table t1\G *************************** 1\. row *************************** Table: t1 Create Table: CREATE TABLE `t1` ( `id` int(11) NOT NULL AUTO_INCREMENT, `a` int(11) DEFAULT NULL, `b` int(11) DEFAULT NULL, `c` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `mrrx` (`a`,`b`), KEY `xx` (`c`) ) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=latin1 1 row in set (0.00 sec) ~~~ 操作如下： ~~~ mysql> set optimizer_switch='mrr=off'; Query OK, 0 rows affected (0.00 sec) mysql> explain select * from test.t1 where (a between 1 and 10) and (c between 9 and 10) ; +----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+ | 1 | SIMPLE | t1 | range | mrrx,xx | xx | 5 | NULL | 2 | Using index condition; Using where | +----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------+ 1 row in set (0.00 sec) ~~~ 當把 MRR 關掉的情況下，執行計劃使用的是索引 xx(c)，即從索引 xx 上讀取一條數據后回表，取回該主鍵的完整數據，當數據較多且比較分散的情況下會有比較多的隨機 IO, 導致性能低下，我們將 MRR 打開，執行以下操作： ~~~ mysql> set optimizer_switch='mrr=on'; Query OK, 0 rows affected (0.00 sec) mysql> explain select * from test.t1 where (a between 1 and 10) and (c between 9 and 10) ; +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+ | 1 | SIMPLE | t1 | range | mrrx,xx | xx | 5 | NULL | 2 | Using index condition; Using where; Using MRR | +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------------------------------+ 1 row in set (0.00 sec) ~~~ 可以看到 extra 的輸出中多了 “Using MRR” 信息，即使用了 MRR Optimization IO 層面進行了優化，減少 IO 方面的開銷，更詳細的說明可以參考[這里](http://dev.mysql.com/doc/refman/5.6/en/mrr-optimization.html)。 ## MRR 原理在不使用 MRR 時，優化器需要根據二級索引返回的記錄來進行“回表”，這個過程一般會有較多的隨機 IO, 使用 MRR 時，SQL 語句的執行過程是這樣的： * 優化器將二級索引查詢到的記錄放到一塊緩沖區中； * 如果二級索引掃描到文件的末尾或者緩沖區已滿，則使用快速排序對緩沖區中的內容按照主鍵進行排序； * 用戶線程調用 MRR 接口取 cluster index，然后根據cluster index 取行數據； * 當根據緩沖區中的 cluster index 取完數據，則繼續調用過程 2) 3)，直至掃描結束；通過上述過程，優化器將二級索引隨機的 IO 進行排序，轉化為主鍵的有序排列，從而實現了隨機 IO 到順序 IO 的轉化，提升性能。 ## MRR 源碼分析首先，咱們來看一下 mrr 相對應的內存結構： ~~~ class DsMrr_impl { ... handler *h; TABLE *table; /* Always equal to h->table */ private: /* Secondary handler object. It is used for scanning the index */ handler *h2; /* Buffer to store rowids, or (rowid, range_id) pairs */ uchar *rowids_buf; uchar *rowids_buf_cur; /* Current position when reading/writing */ uchar *rowids_buf_last; /* When reading: end of used buffer space */ uchar *rowids_buf_end; /* End of the buffer */ bool dsmrr_eof; /* TRUE <=> We have reached EOF when reading index tuples */ int dsmrr_init(handler *h, RANGE_SEQ_IF *seq_funcs, void *seq_init_param, uint n_ranges, uint mode, HANDLER_BUFFER *buf); …. int dsmrr_fill_buffer(); int dsmrr_next(char **range_info); bool get_disk_sweep_mrr_cost(uint keynr, ha_rows rows, uint flags, uint *buffer_size, Cost_estimate *cost); …. } ~~~ 簡單說明：h2 指的是 MRR 使用的 second index 或主鍵索引, h 是指利用 h2 返回的主建來查詢的句柄，rowids_buf 是 MRR 執行過程中存儲有序主鍵的緩存區，大小由 MySQL 的變量?`read_rnd_buffer_size`?設置，下面我們結合程序的執行過程來看一下源碼。 1. MRR 中有序主建的收集過程優化器對查詢語句的條件進行分析并選擇合適的二級索引，并對二級索引的條件進行篩選拼裝成 DYNAMIC_ARRAY ranges，在執行的時候將 ranges 傳入初始化函數?`ha_myisam::multi_range_read_init`?，繼而會調用?`dsmrr_fill_buffer`?函數，在`dsmrr_fill_buffer`中會使用二級索引的句柄查找符合 ranges 的數據并添加至 rowids_buf 中，在掃描結束或緩沖區滿的時候會對 rowids_buf 進行快速排序，詳細過程可以參考函數：`dsmrr_fill_buffer`，其調用堆棧如下： ~~~ #0 DsMrr_impl::dsmrr_fill_buffer (this=0x2aab0000cf00) #1 0x00000000006e49dd in DsMrr_impl::dsmrr_init(...) #2 0x00000000017d35e4 in ha_myisam::multi_range_read_init(...) #3 0x0000000000d134c6 in QUICK_RANGE_SELECT::reset (this=0x2aab00014070) #4 0x00000000009a266f in join_init_read_record (tab=0x2aab0000f5b8) #5 0x000000000099d6d4 in sub_select #6 0x000000000099c914 in do_select (join=0x2aab000064b0) #7 0x00000000009982f8 in JOIN::exec (this=0x2aab000064b0) #8 0x0000000000a5bd7c in mysql_execute_select ........ ~~~ 2. MRR 中主建緩沖區的使用過程物理執行階段，調用?`ha_myisam::multi_range_read_next`，在使用 MRR 的情況下會從過程1）中收集的有序主建的緩沖區取主建，然后再調用引擎層的 rnd_pos 直接找到數據，其中使用 mrr 的調用堆棧如下： ~~~ #0 DsMrr_impl::dsmrr_next (this=0x2aab0000cf00, range_info=0x2aaafc03de70) #1 0x00000000017d3634 in ha_myisam::multi_range_read_next (this=0x2aab0000ca40, range_info=0x2aaafc03de70) #2 0x0000000000d138cc in QUICK_RANGE_SELECT::get_next (this=0x2aab00014070) #3 0x0000000000d46908 in rr_quick (info=0x2aab0000f648) #4 0x00000000009a2791 in join_init_read_record (tab=0x2aab0000f5b8) #5 0x000000000099d6d4 in sub_select (join=0x2aab000064b0, join_tab=0x2aab0000f5b8, end_of_records=false) #6 0x000000000099c914 in do_select (join=0x2aab000064b0) ~~~ 二緩索引（h2）& 主建索引（h) 的協同是通過`rowids_buf_cur`來進行的。最初的初始化過程中，h2 會首先將數據填沖到 rowids_buf 中，如果發現緩沖區中的數據已經取完，則會繼續調用?`dsmrr_fill_buffer`?往 rowids_buf 填主鍵并進行排序，如此反復，直至 h2 掃描至文件末尾，詳情可以參考函數?`DsMrr_impl::dsmrr_next`。通過上面的分析，是不是感覺 MRR 有點像二級索引與主鍵的 join 操作，那就是有點和 BKA 有些類似的概念了，咱們下面看一下 BKA 是如何實現的。 ## BKA 原理 BKA 是指在表連接的過程中為了提升 join 性能而使用的一種 join buffer，其作用是在讀取被 join 表的記錄的時候使用順序 IO，BKA 被使用的標識是執行計劃的 extra 信息中會有 “Batched Key Access” 信息，我們首先看一個例子： ~~~ DROP TABLE t1, t2; CREATE TABLE t1 (a int PRIMARY KEY, b int); CREATE TABLE t2 (a int PRIMARY KEY, b int); INSERT INTO t1 VALUES (1,2), (2,1), (3,2), (4,3), (5,6), (6,5), (7,8), (8,7), (9,10); INSERT INTO t2 VALUES (3,0), (4,1), (6,4), (7,5); mysql> set optimizer_switch="mrr=on,mrr_cost_based=off,batched_key_access=on"; mysql> explain SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a WHERE t2.b <= t1.a AND t1.a <= t1.b; +----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+ | 1 | SIMPLE | t2 | ALL | PRIMARY | NULL | NULL | NULL | 4 | Using where | | 1 | SIMPLE | t1 | eq_ref | PRIMARY | PRIMARY | 4 | test.t2.a | 1 | Using where; Using join buffer (Batched Key Access) | +----+-------------+-------+--------+---------------+---------+---------+-----------+------+-----------------------------------------------------+ 2 rows in set (0.00 sec) ~~~ 從以上的例子中我們可以看到，在讀取表 t1 的時候使用了帶 BKA 功能的 join buffer, 其中 BKA & join buffer 的關系與實現我們放在后面詳解。 ## BKA & MRR 之間的關系使用 BKA 的表的 JOIN 過程如下： 1. 連接表將滿足條件的記錄放入JOIN_CACHE，并將兩表連接的字段放入一個 DYNAMIC_ARRAY ranges 中，此過程類似于 MRR 操作的過程，且在內存中使用的是同樣的結構體 DsMrr_impl； 2. 在進行表的過接過程中，會將 ranges 相關的信息傳入?`DsMrr_impl::dsmrr_fill_buffer`，并進行被連接表主建的查找及排序等操作操作，這個過程比較復雜，包括需要判斷使用的 key、key 是主建時的特殊操作等； 3. `JOIN_CACHE_BKA::join_matching_records`?會調用過程2中產生的有序主建，然后順序讀取數據并進入下一步的操作（`evaluate_join_record`?等）； 4. 當緩沖區的數據被讀完后，會重復進行過程2，3, 直到記錄被讀取完。由上面的分析可以看出，BKA將有序主建投遞到存儲引擎是通過 MRR 的接口的調用來實現的（`DsMrr_impl::dsmrr_next`），所以BKA 依賴 MRR，如果要使用BKA, MRR 是需要打開的，另外?`batched_key_access`?是默認關閉的，如果要使用，需要打開此選項。 BKA 的詳細說明可參考[這里](https://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html)。 ## BKA 源碼實現表之間的連接操作是通過 JOIN_CACHE 來做的，5.6 目前實現了 BNL, BKA (JOIN_CACHE_BKA & JOIN_CACHE_BKA_UNIQUE) 兩種表連接的優化方式，其中 BKA 就是其中減少隨機 IO 的一種方式，BKA內存中對應的結構是 JOIN_CACHE_BKA，咱們首先看一下多表 JOIN 之間的過程； 1. 優化器生成的執行計劃是由一個 JOIN_TAB 的左支樹組成，每個 JOIN_TAB 包含了相關的表、使用的索引、語句中包含的條件等信息； 2. 進入物理執行計劃后，會對每一個表進行讀數據，然后進入?`evaluate_join_record`, 當發現滿足條件的記錄時，則會將該記錄添加到下一個JOIN_TAB 中的JOIN_CACHE 中，其堆棧如下： ~~~ #0 JOIN_CACHE::put_record (this=0x2aab00019d20) #1 0x000000000099d29c in sub_select_op (join=0x2aab00016268, join_tab=0x2aab00018ed8, end_of_records=false) #2 0x000000000099ee1c in evaluate_join_record (join=0x2aab00016268, join_tab=0x2aab00018bd8) #3 0x000000000099d984 in sub_select (join=0x2aab00016268, join_tab=0x2aab00018bd8, end_of_records=false) #4 0x000000000099c914 in do_select (join=0x2aab00016268) #5 0x00000000009982f8 in JOIN::exec (this=0x2aab00016268) #6 0x0000000000a5bd7c in mysql_execute_select (thd=0x314d690, select_lex=0x31503a8, free_join=true) ~~~ 3. 當緩沖區滿或者讀到文件的末尾時，會調用下一個JOIN_TAB 中?`JOIN_CACHE::join_records`?方法（BKA 使用時 JOIN_CACHE 為 JOIN_CACHE_BKA），然后會進入 MRR 的相關邏輯，其完整的堆棧為： ~~~ #0 DsMrr_impl::dsmrr_fill_buffer (this=0x2aab000128e0) #1 0x00000000006e49dd in DsMrr_impl::dsmrr_init #2 0x00000000017d35e4 in ha_myisam::multi_range_read_init #3 0x0000000000d838aa in JOIN_CACHE_BKA::init_join_matching_records (this=0x2aab00019d20, seq_funcs=0x2aaafc03dd80, ranges=4) #4 0x0000000000d8335c in JOIN_CACHE_BKA::join_matching_records (this=0x2aab00019d20, skip_last=false) #5 0x0000000000d812e8 in JOIN_CACHE::join_records (this=0x2aab00019d20, skip_last=false) #6 0x0000000000d86ed3 in JOIN_CACHE::end_send (this=0x2aab00019d20) #7 0x000000000099d0d1 in sub_select_op (join=0x2aab00016268, join_tab=0x2aab00018ed8, end_of_records=true) #8 0x000000000099d3c4 in sub_select (join=0x2aab00016268, join_tab=0x2aab00018bd8, end_of_records=true) at #9 0x000000000099c97d in do_select (join=0x2aab00016268) #10 0x00000000009982f8 in JOIN::exec (this=0x2aab00016268) #11 0x0000000000a5bd7c in mysql_execute_select ~~~ 4. `dsmrr_fill_buffer`?的過程相對復雜，需要首先取出兩表相連接的字段的索引，如果沒有索引，則會使用主建并直接讀取，如果使用了索引，則需要從上一個JOIN_TAB中將索引的信息讀出來并從 join_cache 的 buffer 中取出該索引的數據，然后再進行回表，查找主建、排序等操作，其堆棧如下： ~~~ #0 JOIN_CACHE_BKA::get_next_key (this=0x2aab00019d20, key=0x2aab0001e178) #1 0x0000000000d82f83 in bka_range_seq_next (rseq=0x2aab00019d20, range=0x2aab0001e178) #2 0x00000000006e3cac in handler::multi_range_read_next (this=0x2aab0001e020, range_info=0x2aaafc03dc10) #3 0x00000000006e5466 in DsMrr_impl::dsmrr_fill_buffer (this=0x2aab000128e0) #4 0x00000000006e49dd in DsMrr_impl::dsmrr_init (…) #5 0x00000000017d35e4 in ha_myisam::multi_range_read_init (…) #6 0x0000000000d838aa in JOIN_CACHE_BKA::init_join_matching_records (this=0x2aab00019d20, seq_funcs=0x2aaafc03dd80, ranges=4) ~~~ 此過程只是兩個表的使用 BKA 時的過程，當是多表時，過程將更為復雜。 ## 小結本篇文章中我們詳細的介紹了 MRR、BKA 以及 MRR & BKA 之間的關系等內容，測試用例都是在mrr_cost_based=OFF 的情況下進行的，因為SQL 語句是否使用 MRR 優化依賴于其代價的大小，優化器的代價計算是一個比較復雜的過程，無論是 MRR 還是 BKA 都只是優化器進行優化的方法，當其發現優化后的代價過高時就會不使用該項優化，因此在使用 MRR 相關的優化時，盡量設置 mrr_cost_based=ON，畢竟大多數情況下優化器是對的。