目前，美團(tuán)內(nèi)部每天產(chǎn)生的慢查詢數(shù)量已經(jīng)超過上億條。如何高效準(zhǔn)確地為慢查詢推薦缺失的索引來改善其執(zhí)行性能，是美團(tuán)數(shù)據(jù)庫(kù)研發(fā)中心面臨的一項(xiàng)挑戰(zhàn)。為此，我們與華東師范大學(xué)開展了科研合作，在AI領(lǐng)域?qū)λ饕扑]進(jìn)行了探索和實(shí)踐，并將基于代價(jià)的方法和新提出的基于AI+數(shù)據(jù)驅(qū)動(dòng)的方法共同應(yīng)用于慢查詢的索引推薦，成功提升了推薦效果。

• 1 背景

• 2 索引推薦介紹

  • 2.1 基于代價(jià)的索引推薦

  • 2.2 基于AI+數(shù)據(jù)驅(qū)動(dòng)的索引推薦

• 3 整體架構(gòu)

  • 3.1 模型訓(xùn)練

  • 3.2 模型部署

• 4 建模過程

  • 4.1 生成候選索引

  • 4.2 特征工程

  • 4.3 建模舉例

  • 4.4 模型預(yù)測(cè)和索引評(píng)估

• 5 項(xiàng)目運(yùn)行情況

• 6 未來規(guī)劃

?1 背景?

隨著美團(tuán)業(yè)務(wù)量的不斷增長(zhǎng)，慢查詢的數(shù)量也日益增多。目前，日均慢查詢數(shù)量已經(jīng)超過上億條，如果僅依靠DBA和開發(fā)人員手動(dòng)地對(duì)這些慢查詢進(jìn)行分析并建立合適的索引，顯然是不太現(xiàn)實(shí)的。為了解決這一難題，美團(tuán)內(nèi)部DAS（數(shù)據(jù)庫(kù)自治服務(wù)）平臺(tái)已經(jīng)集成了基于代價(jià)的慢查詢優(yōu)化建議來自動(dòng)地為慢查詢推薦索引。然而，仍然存在一些問題：

• 基于代價(jià)的慢查詢優(yōu)化建議是借助于優(yōu)化器的代價(jià)估計(jì)，來推薦出對(duì)于查詢代價(jià)改善最大的索引，但優(yōu)化器的代價(jià)估計(jì)并不是完全準(zhǔn)確[1]，因此可能存在著漏選或者錯(cuò)選推薦索引的問題。

• 基于代價(jià)的慢查詢優(yōu)化建議需要計(jì)算查詢?cè)诓煌饕虏樵兇鷥r(jià)的改善程度，因此需要進(jìn)行大量的增刪索引操作，但真實(shí)增刪索引的代價(jià)是非常大的，需要借助于假索引[2]技術(shù)，假索引技術(shù)并不創(chuàng)建真實(shí)的物理索引文件，只是通過模擬索引存在時(shí)的查詢計(jì)劃來估算索引對(duì)于查詢的收益。目前，美團(tuán)大部分業(yè)務(wù)都是運(yùn)行在MySQL實(shí)例上的，不同于商業(yè)數(shù)據(jù)庫(kù)SQL Server和開源數(shù)據(jù)庫(kù)PostgreSQL，MySQL內(nèi)部并沒有集成假索引技術(shù)，因此需要自己構(gòu)建支持假索引的存儲(chǔ)引擎，其開發(fā)成本較高，這也是目前DAS平臺(tái)基于代價(jià)的慢查詢優(yōu)化建議所采用的方案。

為了解決上述兩個(gè)問題，美團(tuán)數(shù)據(jù)庫(kù)研發(fā)中心與華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院展開了《基于數(shù)據(jù)驅(qū)動(dòng)的索引推薦》的科研合作，雙方通過在DAS平臺(tái)上集成基于AI+數(shù)據(jù)驅(qū)動(dòng)的索引推薦，來與基于代價(jià)的方法并行地為慢查詢推薦索引，以提升推薦效果。

• 首先，基于代價(jià)的方法每天會(huì)為慢查詢推薦索引，并在采樣庫(kù)上評(píng)估推薦的索引是否真正地改善了查詢的執(zhí)行時(shí)間，這為AI方法積累了大量可信的訓(xùn)練數(shù)據(jù)，根據(jù)此數(shù)據(jù)訓(xùn)練的AI模型，可以在一定程度上彌補(bǔ)基于代價(jià)的方法漏選或錯(cuò)選索引的問題。

• 其次，基于AI的方法將針對(duì)慢查詢的索引推薦看作是二分類問題，通過分類模型直接判別在某一列或某些列上建立索引是否能夠改善查詢的執(zhí)行性能，并不借助于查詢優(yōu)化器和假索引技術(shù)，這使得AI方法更加通用，且開發(fā)成本更低。

?2 索引推薦介紹?

索引推薦可以劃分為兩個(gè)級(jí)別：Workload級(jí)別和Query級(jí)別：

• 在Workoad級(jí)別，索引推薦是在限制的索引存儲(chǔ)空間或索引個(gè)數(shù)下，推薦出一組最優(yōu)的索引集合來使得整個(gè)Worklaod的代價(jià)最低。

• Query級(jí)別的索引推薦可以被視為Workload級(jí)別索引推薦的簡(jiǎn)化版本，在Query級(jí)別，索引推薦是為單個(gè)慢查詢推薦缺失的索引，以改善其性能。

| 2.1 基于代價(jià)的索引推薦

基于代價(jià)的索引推薦[3]大多聚焦于Workload級(jí)別的索引推薦，出現(xiàn)在查詢中每一列或者列的組合都可以看作是一個(gè)能夠改善Workload代價(jià)的候選索引，所有的候選索引構(gòu)成了一個(gè)巨大的搜索空間（候選索引集合）。

?這是一個(gè)屬于NP-hard范疇的搜索問題[4]。目前，基于代價(jià)的索引推薦方法大多會(huì)采用“貪心策略”來簡(jiǎn)化搜索過程，但這可能會(huì)導(dǎo)致最后推薦出的索引是次優(yōu)解[5]。

| 2.2 基于AI+數(shù)據(jù)驅(qū)動(dòng)的索引推薦

基于AI+數(shù)據(jù)驅(qū)動(dòng)的索引推薦聚焦于Query級(jí)別的索引推薦，出發(fā)點(diǎn)是在某個(gè)數(shù)據(jù)庫(kù)中因?yàn)槿笔饕龑?dǎo)致的慢查詢，在其它數(shù)據(jù)庫(kù)中可能有相似的索引創(chuàng)建案例：這些查詢語句相似，因此在相似位置上的列創(chuàng)建索引也可能帶來類似的收益。例如下圖中，查詢和在語句結(jié)構(gòu)和列類型上非常相似。因此，我們可以通過學(xué)習(xí)查詢的索引創(chuàng)建模式來為查詢 推薦缺失的索引。

對(duì)于不同列數(shù)的索引推薦，我們會(huì)分別訓(xùn)練基于XGBoost的二分類模型。例如，我們目前最高支持三列的索引推薦，因此會(huì)分別訓(xùn)練一個(gè)單列索引推薦模型、一個(gè)兩列索引推薦模型和一個(gè)三列索引推薦模型。對(duì)于給定的一個(gè)單列候選索引和它對(duì)應(yīng)的慢查詢，我們使用單列索引推薦模型來判斷該單列候選索引是否能夠改善該慢查詢的性能。

同樣的，對(duì)于給定的一個(gè)兩列（三列）候選索引和它對(duì)應(yīng)的慢查詢，我們使用兩列（三列）索引推薦模型來判斷這個(gè)兩列（三列）候選索引是否能夠改善該慢查詢的性能。如果一條慢查詢中包含的候選索引個(gè)數(shù)為，那么則需要次模型預(yù)測(cè)來完成對(duì)這條慢查詢的索引推薦。

?3 整體架構(gòu)?

基于AI+數(shù)據(jù)驅(qū)動(dòng)的索引推薦的整體架構(gòu)如下圖所示，主要分為兩個(gè)部分：模型訓(xùn)練和模型部署。

| 3.1 模型訓(xùn)練

如上文所述，我們收集DAS平臺(tái)基于代價(jià)的慢查詢優(yōu)化建議每天的索引推薦數(shù)據(jù)（包括慢查詢和被驗(yàn)證有效的推薦索引）作為訓(xùn)練數(shù)據(jù)。我們生成每條查詢的單列、兩列和三列候選索引，并通過特征工程來為每個(gè)候選索引構(gòu)建特征向量，使用索引數(shù)據(jù)來為特征向量打標(biāo)簽。之后，單列、兩列和三列特征向量將分別用于訓(xùn)練單列、兩列和三列索引推薦模型。

| 3.2 模型部署

針對(duì)需要推薦索引的慢查詢，我們同樣生成候選索引并構(gòu)建特征向量。接下來，我們使用分類模型來預(yù)測(cè)特征向量的標(biāo)簽，即預(yù)測(cè)出候選索引中的有效索引。隨后，我們?cè)诓蓸訋?kù)上創(chuàng)建模型預(yù)測(cè)出的有效索引，并通過實(shí)際執(zhí)行查詢來觀察建立索引前后查詢性能是否得到改善。只有當(dāng)查詢性能真正得到改善時(shí)，我們才會(huì)將索引推薦給用戶。

?4 建模過程?

| 4.1 生成候選索引

我們提取查詢中出現(xiàn)在聚合函數(shù)、WHERE、JOIN、ORDER BY、GROUP BY這些關(guān)鍵詞中的列作為單列候選索引，并對(duì)這些單列候選索引進(jìn)行排列組合來生成兩列和三列候選索引。同時(shí)，我們會(huì)獲取查詢所涉及的表中已經(jīng)存在的索引，并將其從候選索引集合中刪除。這一步驟遵循索引的最左前綴原則：如果存在索引，那么候選索引 和 都將從候選索引集合中刪除。

| 4.2 特征工程

一個(gè)候選索引的特征向量包括語句特征和統(tǒng)計(jì)特征兩部分。語句特征描述了候選索引列在查詢中的出現(xiàn)位置（采用one-hot的編碼方式），統(tǒng)計(jì)特征描述了候選索引列的統(tǒng)計(jì)信息，如所在表的表行數(shù)、Cardinality值、選擇率等，這些是判斷是否需要在候選索引列上建立索引的重要指標(biāo)。

下表以單列候選索引 為例，展示了它的部分重要特征及其含義：

兩列候選索引 的特征是通過對(duì)單列候選索引 和 的特征進(jìn)行拼接而成的，此外，我們還會(huì)計(jì)算 和 共同的Cardinality值作為兩列候選索引 的額外統(tǒng)計(jì)特征，以更加全面地描述其統(tǒng)計(jì)信息。同樣地，我們也會(huì)采用使用這種方式來構(gòu)建三列候選索引 的特征。在生成完一條查詢的特征向量之后，我們使用這條查詢使用到的索引來為生成的特征向量打標(biāo)簽。

| 4.3 建模舉例

下圖以查詢 為例，展示我們?yōu)橛?xùn)練集中的一條查詢生成特征向量并打標(biāo)簽的過程。查詢 涉及兩張表customer表和warehouse表，其中customer表的c_w_id、c_id、c_d_id、c_last四列參與到查詢中，因此對(duì)應(yīng)生成四條單列特征向量；warehouse表的w_id列參與到查詢中，因此只生成了一條單列特征向量。查詢 使用的單列索引為Idx(w_id)，所以單列候選索引 (w_id) 對(duì)應(yīng)的特征向量被標(biāo)記為正樣本，其余特征向量則被標(biāo)記為負(fù)樣本。

接下來，我們對(duì)單列候選索引進(jìn)行排列組合來生成多列候選索引及其特征向量。由于查詢 使用到的多列索引只有一個(gè)三列索引Idx(c_d_id, c_id, c_last)，因此我們跳過生成兩列候選索引，只生成三列候選索引。這是因?yàn)槲覀兪腔诓樵兪褂玫降乃饕齺頌樘卣飨蛄看驑?biāo)簽的，如果查詢沒有使用到兩列索引，那么生成的所有兩列特征向量均為負(fù)樣本，這可能會(huì)導(dǎo)致訓(xùn)練集正負(fù)樣本不均衡的問題。

最后，基于查詢使用到的三列索引，我們將三列候選索引 (c_d_id, c_id, c_last) 對(duì)應(yīng)的特征向量標(biāo)記為正樣本。以上就是我們?yōu)椴樵?生成特征向量并打標(biāo)簽的整個(gè)過程，查詢 為單列索引推薦模型的訓(xùn)練集貢獻(xiàn)了五條樣本（一條正樣本，四條負(fù)樣本），為三列索引推薦模型的訓(xùn)練集貢獻(xiàn)了六條樣本（一條正樣本，五條負(fù)樣本）。

| 4.4 模型預(yù)測(cè)和索引評(píng)估

在為一條慢查詢推薦索引時(shí)，我們依次生成慢查詢中所有的單列、雙列和三列候選索引，并通過上述的特征工程來構(gòu)造特征向量。然后，我們將特征向量輸入給對(duì)應(yīng)的分類模型進(jìn)行預(yù)測(cè)，并從三個(gè)分類模型的預(yù)測(cè)結(jié)果中分別挑選出一個(gè)預(yù)測(cè)概率最高的候選索引（即一個(gè)單列索引、一個(gè)兩列索引和一個(gè)三列索引）作為模型推薦的索引。

雖然推薦的索引越多，慢查詢的性能就越有可能得到改善，但是模型推薦的部分索引可能是無效的，這些無效索引帶來的存儲(chǔ)空間開銷和更新索引的開銷是不可忽視的。因此，直接將模型推薦的索引全部推薦給用戶是不合理的。為此，在將索引推薦給用戶之前，我們會(huì)首先將三個(gè)分類模型推薦的索引建立在采樣庫(kù)上進(jìn)行驗(yàn)證，采樣庫(kù)是線上數(shù)據(jù)庫(kù)的一個(gè)mini版本，它抽取了線上數(shù)據(jù)庫(kù)的部分?jǐn)?shù)據(jù)。在采樣庫(kù)上，我們會(huì)觀察在建立推薦的索引之后，查詢的執(zhí)行時(shí)間是否得到改善。如果得到改善，我們就把查詢使用到的一個(gè)或多個(gè)模型推薦的索引作為索引建議推薦給用戶。

?5 項(xiàng)目運(yùn)行情況?

正如前文所述，美團(tuán)DAS平臺(tái)目前采用代價(jià)方法和AI模型并行為慢查詢推薦索引。具體來說，AI模型可以在某些場(chǎng)景下，彌補(bǔ)代價(jià)方法漏選或錯(cuò)選推薦索引的問題。就在剛過去的3月份，在代價(jià)方法推薦索引的基礎(chǔ)上，AI模型有額外12.16%的推薦索引被用戶所采納。

這些額外補(bǔ)充的索引對(duì)于查詢的改善情況如上圖所示：上半部分展示了優(yōu)化的查詢執(zhí)行次數(shù)，下半部分展示了查詢?cè)谑褂猛扑]的索引之后的執(zhí)行時(shí)間以及減少的執(zhí)行時(shí)間，這些索引總計(jì)約優(yōu)化了52億次的查詢執(zhí)行，減少了4632小時(shí)的執(zhí)行時(shí)間。

?6 未來規(guī)劃?

目前，大模型技術(shù)（如GPT-4）已經(jīng)得到了越來越多的認(rèn)可，幾乎可以勝任各種領(lǐng)域的任務(wù)。我們計(jì)劃嘗試通過Fine-Tune開源的大型語言模型（如Google開源的T5模型）來解決索引推薦的問題：輸入一條慢查詢，讓模型來生成針對(duì)慢查詢的索引建議。

在推薦索引無法改善慢查詢的情況下，后續(xù)我們可以提供一些文本建議來幫助用戶優(yōu)化SQL，比如減少返回不必要的列，使用JOIN代替子查詢等。

?7 本文作者?

彭淦，美團(tuán)基礎(chǔ)研發(fā)平臺(tái)工程師，主要負(fù)責(zé)美團(tuán)數(shù)據(jù)庫(kù)自治服務(wù)DAS的SQL優(yōu)化建議工作。

?8 特別感謝?

在這里特別感謝華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院的蔡鵬教授，教授在VLDB、ICDE、SIGIR、ACL等領(lǐng)域重要國(guó)際會(huì)議上發(fā)表多篇論文。目前的研究方向?yàn)閮?nèi)存事務(wù)處理，以及基于機(jī)器學(xué)習(xí)技術(shù)的自適應(yīng)數(shù)據(jù)管理系統(tǒng)。本文也是美團(tuán)數(shù)據(jù)庫(kù)研發(fā)中心跟蔡鵬教授展開科研合作后的具體實(shí)踐。

美團(tuán)科研合作致力于搭建美團(tuán)技術(shù)團(tuán)隊(duì)與高校、科研機(jī)構(gòu)、智庫(kù)的合作橋梁和平臺(tái)，依托美團(tuán)豐富的業(yè)務(wù)場(chǎng)景、數(shù)據(jù)資源和真實(shí)的產(chǎn)業(yè)問題，開放創(chuàng)新，匯聚向上的力量，圍繞機(jī)器人、人工智能、大數(shù)據(jù)、物聯(lián)網(wǎng)、無人駕駛、運(yùn)籌優(yōu)化等領(lǐng)域，共同探索前沿科技和產(chǎn)業(yè)焦點(diǎn)宏觀問題，促進(jìn)產(chǎn)學(xué)研合作交流和成果轉(zhuǎn)化，推動(dòng)優(yōu)秀人才培養(yǎng)。面向未來，我們期待能與更多高校和科研院所的老師和同學(xué)們進(jìn)行合作。歡迎老師和同學(xué)們發(fā)送郵件至：meituan.oi@meituan.com。

?9 參考文獻(xiàn)?

• [1] Leis V, Gubichev A, Mirchev A, et al. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (2015), 204-215.

• [2] https://github.com/HypoPG/hypopg

• [3] Kossmann J, Halfpap S, Jankrift M, et al. 2020. Magic mirror in my hand, which is the best in the land? an experimental evaluation of index selection algorithms. Proc. VLDB Endow. 13,12 (2020), 2382-2395.

• [4] Piatetsky-Shapiro G. 1983. The optimal selection of secondary indices is NP-complete. SIGMOD Record. 13,2 (1983), 72-75.

• [5] Zhou X, Liu L, Li W, et al. 2022. Autoindex: An incremental index management system for dynamic workloads. ?In ICDE. 2196-2208.

----------? END? ----------

?推薦閱讀?

? |?基于代價(jià)的慢查詢優(yōu)化建議

? |?基于AI算法的數(shù)據(jù)庫(kù)異常監(jiān)測(cè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

? |?數(shù)據(jù)庫(kù)異常智能分析與診斷