對于數據庫來說，慢查詢往往意味著風險。SQL執行得越慢，消耗的CPU資源或IO資源也會越大。大量的慢查詢可直接引發業務故障，關注慢查詢即是關注故障本身。本文主要介紹了美團如何利用數據庫的代價優化器來優化慢查詢，并給出索引建議，評估跟蹤建議質量，運營治理慢查詢。
一、背景
慢查詢是指數據庫中查詢時間超過指定閾值（美團設置為100ms）的SQL，它是數據庫的性能殺手，也是業務優化數據庫訪問的重要抓手。隨著美團業務的高速增長，日均慢查詢量已經過億條，此前因慢查詢導致的故障約占數據庫故障總數的10%以上，而且高級別的故障呈日益增長趨勢。因此，對慢查詢的優化已經變得刻不容緩。
那么如何優化慢查詢呢？最直接有效的方法就是選用一個查詢效率高的索引。關于高效率的索引推薦，主要有基于經驗規則和代價的兩種算法。
在日常工作中，基于經驗規則的推薦隨處可見，對于簡單的SQL，如 * from where name like 'Bobby%' ，直接添加索引IX(name) 就可以取得不錯的效果；但對于稍微復雜點的SQL，如 * from where name like 'Bobby%' and dt > '2021-07-06' ，到底選擇IX(name)、IX(dt)、IX(dt,name) 還是IX(name,dt)，該方法也無法給出準確的回答。更別說像多表Join、子查詢這樣復雜的場景了。所以采用基于代價的推薦來解決該問題會更加普適，因為基于代價的方法使用了和數據庫優化器相同的方式，去量化評估所有的可能性，選出的是執行SQL耗費代價最小的索引。
二、基于代價的優化器介紹1、SQL執行與優化器
一條SQL在MySQL服務器中執行流程主要包含：SQL解析、基于語法樹的準備工作、優化器的邏輯變化、優化器的代價準備工作、基于代價模型的優化、進行額外的優化和運行執行計劃等部分。具體如下圖所示：
SQL執行與優化器
2、代價模型介紹
而對于優化器來說，執行一條SQL有各種各樣的方案可供選擇，如表是否用索引、選擇哪個索引、是否使用范圍掃描、多表Join的連接順序和子查詢的執行方式等。如何從這些可選方案中選出耗時最短的方案呢？這就需要定義一個量化數值指標，這個指標就是代價(Cost)，我們分別計算出可選方案的操作耗時，從中選出最小值。
代價模型將操作分為層和（存儲引擎）層兩類，層主要是CPU代價，層主要是IO代價，比如MySQL從磁盤讀取一個數據頁的代價為1，計算符合條件的行代價為為0.2。除此之外還有：
在MySQL 5.7中，這些操作代價的默認值都可以進行配置。為了計算出方案的總代價，還需要參考一些統計數據，如表數據量大小、元數據和索引信息等。MySQL的代價優化器模型整體如下圖所示：
代價模型
3、基于代價的索引選擇
還是繼續拿上述的 SQL * from where name like 'Bobby%' and dt > '2021-07-06' 為例，我們看看MySQL優化器是如何根據代價模型選擇索引的。首先，我們直接在建表時加入四個候選索引。
復制Create Table: CREATE TABLE `sync_test1` ( `id` int(11) NOT NULL AUTO_INCREMENT, `cid` int(11) NOT NULL, `phone` int(11) NOT NULL, `name` varchar(10) NOT NULL, `address` varchar(255) DEFAULT NULL, `dt` datetime DEFAULT NULL, PRIMARY KEY (`id`), KEY `IX_name` (`name`), KEY `IX_dt` (`dt`), KEY `IX_dt_name` (`dt`,`name`), KEY `IX_name_dt` (`name`,`dt`) ) ENGINE=InnoDB
通過執行explain看出MySQL最終選擇了IX_name索引。
復制mysql> explain select * from sync_test1 where name like 'Bobby%' and dt > '2021-07-06'; +----+-------------+------------+------------+-------+-------------------------------------+---------+---------+------+------+----------+------------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+------------+------------+-------+-------------------------------------+---------+---------+------+------+----------+------------------------------------+ | 1 | SIMPLE | sync_test1 | NULL | range | IX_name,IX_dt,IX_dt_name,IX_name_dt | IX_name | 12 | NULL | 572 | 36.83 | Using index condition; Using where | +----+-------------+------------+------------+-------+-------------------------------------+---------+---------+------+------+----------+------------------------------------+然后再打開MySQL追蹤優化器Trace功能?？梢钥闯觯瑳]有選擇其他三個索引的原因均是因為在其他三個索引上使用range scan的代價均>= 。
復制mysql> select * from INFORMATION_SCHEMA.OPTIMIZER_TRACE\G; *************************** 1. row *************************** TRACE: { ... "rows_estimation": [ { "table": "`sync_test1`", "range_analysis": { "table_scan": { "rows": 105084, "cost": 21628 }, ... "analyzing_range_alternatives": { "range_scan_alternatives": [ { "index": "IX_name", "ranges": [ "Bobby\u0000\u0000\u0000\u0000\u0000 <= name <= Bobby?????" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "rows": 572, "cost": 687.41, "chosen": true }, { "index": "IX_dt", "ranges": [ "0x99aa0c0000 < dt" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "rows": 38698, "cost": 46439, "chosen": false, "cause": "cost" }, { "index": "IX_dt_name", "ranges": [ "0x99aa0c0000 < dt" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "rows": 38292, "cost": 45951, "chosen": false, "cause": "cost" }, { "index": "IX_name_dt", "ranges": [ "Bobby\u0000\u0000\u0000\u0000\u0000 <= name <= Bobby?????" ], "index_dives_for_eq_ranges": true, "rowid_ordered": false, "using_mrr": false, "index_only": false, "rows": 572, "cost": 687.41, "chosen": false, "cause": "cost" } ], "analyzing_roworder_intersect": { "usable": false, "cause": "too_few_roworder_scans" } }, "chosen_range_access_summary": { "range_access_plan": { "type": "range_scan", "index": "IX_name", "rows": 572, "ranges": [ "Bobby\u0000\u0000\u0000\u0000\u0000 <= name <= Bobby?????" ] }, "rows_for_plan": 572, "cost_for_plan": 687.41, "chosen": true } ... }下面我們根據代價模型來推演一下代價的計算過程：
補充說明4、基于代價的索引推薦思路
如果想借助MySQL優化器給慢查詢計算出最佳索引，那么需要真實地在業務表上添加所有候選索引。對于線上業務來說，直接添加索引的時間空間成本太高，是不可接受的。MySQL優化器選最佳索引用到的數據是索引元數據和統計數據，所以我們想是否可以通過給它提供候選索引的這些數據，而非真實添加索引的這種方式來實現。
通過深入調研MySQL的代碼結構和優化器流程，我們發現是可行的：一部分存在于層的frm文件中，比如索引定義；另一部分存在于層中，或者通過調用層的接口函數來獲取，比如索引中某個列的不同值個數、索引占據的頁面大小等。索引相關的信息，如下圖所示：
基于代價的索引推薦思路
因為MySQL本身就支持自定義存儲引擎，所以索引推薦思路是構建一個支持虛假索引的存儲引擎，在它上面建立包含候選索引的空表，再采集樣本數據，計算出統計數據提供給優化器，讓優化器選出最優索引，整個調用關系如下圖所示：
基于代價的索引推薦思路
三、索引推薦實現
因為存儲引擎本身并不具備對外提供服務的能力，直接在MySQL 層修改也難以維護，所以我們將整個索引推薦系統拆分成支持虛假索引的存儲引擎和對外提供服務的Go-兩部分，整體架構圖如下：
架構圖
首先簡要介紹一下存儲引擎，這是一個輕量級的存儲引擎，負責將索引的相關接口透傳到Go-部分。因為它必須采用C++實現，與Go-間存在跨語言調用的問題，我們使用了Go原生的輕量級RPC技術+cgo來避免引入重量級的RPC框架，也不必引入第三方依賴包。函數調用鏈路如下所示，MySQL優化器調用的C++函數，參數轉換成C語言，然后通過cgo調用到Go語言的方法，再通過Go自帶的RPC客戶端向服務端發起調用。
調用鏈路
下面將重點闡述核心邏輯Go-部分，主要流程步驟如下。
1、前置校驗
首先根據經驗規則，排除一些不支持通過添加索引來提高查詢效率的場景，如查系統庫的SQL，非、、 SQL等。
2、提取關鍵列名
這一步提取SQL可用來添加索引的候選列名，除了選擇給出現在where中的列添加索引，MySQL對排序、聚合、表連接、聚合函數（如max）也支持使用索引來提高查詢效率。我們對SQL進行語法樹解析sql時間區間查詢效率，在樹節點的where、join、order by、group by、聚合函數中提取列名，作為索引的候選列。值得注意的是，對于某些SQL，還需結合表結構才能準確地提取，比如：
3、生成候選索引
將提取出的關鍵列名進行全排列即包含所有的索引組合，如列A、B、C的所有索引組合是['A', 'B', 'C', 'AB', 'AC', 'BA', 'BC', 'CA', 'CB', 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']，但還需排除一些索引才能得到所有的候選索引，比如：
4、數據采集
直接從業務數據庫采集，數據分成元數據、統計數據、樣本數據三部分：
數據采集
下面介紹樣本數據的采樣算法，好的采樣算法應該盡最大可能采集到符合原表數據分布的樣本。比如基于均勻隨機采樣的方式 * from table where rand() < rate ，然而它會給線上數據庫造成大量I/O的問題，嚴重時可引發數據庫故障。所以我們采用了基于塊的采樣方式：它參考了MySQL 8.0的直方圖采樣算法，如對于一張100萬的表，采集10萬行數，根據主鍵的最小值最大值將表數據均分成100個區間，每個區間取一塊1000行數據，采集數據的SQL，最后將采集到的數據塞入采樣表中。代碼如下：
復制 A,B,C,id from table where id >= 1000 and id = 10000 and id 100 and B < 1000 ，候選索引A、B來說，優化器會調用此函數在索引頁A上估算A > 100有多少行數，在索引頁B上估計B
其次是用于計算索引區分度的。如果直接套用上述公式：樣本列上不同值個數 * (原表行數 / 樣本表行數)， 如上述的候選索引A，根據樣本統計出共有100個不同值，那么在原表中，該列有多少不同值？一般以為是10,000 =100 *（1,000,000/100,000）。但這樣計算不適用某些場景，比如狀態碼字段，可能最多100個不同值。針對該問題，我們引入斜率和兩趟計算來規避，流程如下：
統計數據計算
6、候選索引代價評估
這一步讓優化器幫助我們從候選索引中選出最佳索引，主要步驟如下：
值得注意的是，MySQL表最多建64個索引（二級索引），計算所有候選索引的可能時，使用的是增幅比指數還恐怖的全排列算法。如下圖所示，隨著列數的增加，候選索引數量急劇上升，在5個候選列時的索引組合數量就超過了MySQL最大值，顯然不能滿足一些復雜SQL的需求。統計美團線上索引列數分布后，我們發現sql時間區間查詢效率，95%以上的索引列數都