前言

查詢優(yōu)化器是關(guān)系數(shù)據(jù)庫系統(tǒng)的核心模塊，是數(shù)據(jù)庫內(nèi)核開發(fā)的重點和難點，也是衡量整個數(shù)據(jù)庫系統(tǒng)成熟度的“試金石”。

查詢優(yōu)化理論誕生距今已有四十來年，學(xué)術(shù)界和工業(yè)界其實已經(jīng)形成了一套比較完善的查詢優(yōu)化框架(System-R 的 Bottom-up 優(yōu)化框架和 Volcano/Cascade 的 Top-down 優(yōu)化框架)，但圍繞查詢優(yōu)化的核心難題始終沒變——如何利用有限的系統(tǒng)資源盡可能為查詢選擇一個“好”的執(zhí)行計劃。

近年來，新的存儲結(jié)構(gòu)（如 LSM 存儲結(jié)構(gòu)）的出現(xiàn)和分布式數(shù)據(jù)庫的流行進一步加大了查詢優(yōu)化的復(fù)雜性，本文章結(jié)合 OceanBase 數(shù)據(jù)庫過去近十年時間的實踐經(jīng)驗，與大家一起探討查詢優(yōu)化在實際應(yīng)用場景中的挑戰(zhàn)和解決方案。

查詢優(yōu)化器簡介

SQL 是一種結(jié)構(gòu)化查詢語言，它只告訴數(shù)據(jù)庫”想要什么”，但是它不會告訴數(shù)據(jù)庫”如何獲取”這個結(jié)果，這個"如何獲取"的過程是由數(shù)據(jù)庫的“大腦”查詢優(yōu)化器來決定的。在數(shù)據(jù)庫系統(tǒng)中，一個查詢通常會有很多種獲取結(jié)果的方法，每一種獲取的方法被稱為一個"執(zhí)行計劃"。給定一個 SQL，查詢優(yōu)化器首先會枚舉出等價的執(zhí)行計劃。

其次，查詢優(yōu)化器會根據(jù)統(tǒng)計信息和代價模型為每個執(zhí)行計劃計算一個“代價”，這里的代價通常是指執(zhí)行計劃的執(zhí)行時間或者執(zhí)行計劃在執(zhí)行時對系統(tǒng)資源(CPU + IO + NETWORK)的占用量。最后，查詢優(yōu)化器會在眾多等價計劃中選擇一個"代價最小"的執(zhí)行計劃。下圖展示了查詢優(yōu)化器的基本組件和執(zhí)行流程。

查詢優(yōu)化器面臨的挑戰(zhàn)

查詢優(yōu)化自從誕生以來一直是數(shù)據(jù)庫的難點，它面臨的挑戰(zhàn)主要體現(xiàn)在以下三個方面:

挑戰(zhàn)一：精準(zhǔn)的統(tǒng)計信息和代價模型

統(tǒng)計信息和代價模型是查詢優(yōu)化器基礎(chǔ)模塊，它主要負(fù)責(zé)給執(zhí)行計劃計算代價。精準(zhǔn)的統(tǒng)計信息和代價模型一直是數(shù)據(jù)庫系統(tǒng)想要解決的難題，主要原因如下:

1、統(tǒng)計信息：在數(shù)據(jù)庫系統(tǒng)中，統(tǒng)計信息搜集主要存在兩個問題。首先，統(tǒng)計信息是通過采樣搜集，所以必然存在采樣誤差。其次，統(tǒng)計信息搜集是有一定滯后性的，也就是說在優(yōu)化一個 SQL 查詢的時候，它使用的統(tǒng)計信息是系統(tǒng)前一個時刻的統(tǒng)計信息。

2、選擇率計算和中間結(jié)果估計：選擇率計算一直以來都是數(shù)據(jù)庫系統(tǒng)的難點，學(xué)術(shù)界和工業(yè)界一直在研究能使選擇率計算變得更加準(zhǔn)確的方法，比如動態(tài)采樣，多列直方圖等計劃，但是始終沒有解決這個難題，比如連接謂詞選擇率的計算目前就沒有很好的解決方法。

3、代價模型：目前主流的數(shù)據(jù)庫系統(tǒng)基本都是使用靜態(tài)的代價模型，比如靜態(tài)的 buffer 命中率，靜態(tài)的 IO RT，但是這些值都是隨著系統(tǒng)的負(fù)載變化而變化的。如果想要一個非常精準(zhǔn)的代價模型，就必須要使用動態(tài)的代價模型。

挑戰(zhàn)二：海量的計劃空間

復(fù)雜查詢的計劃空間是非常大的，在很多場景下，優(yōu)化器甚至沒辦法枚舉出所有等價的執(zhí)行計劃。下圖展示了星型查詢等價邏輯計劃個數(shù)(不包含笛卡爾乘積的邏輯計劃)，而優(yōu)化器真正的計劃空間還得正交上算子物理實現(xiàn)，基于代價的改寫和分布式計劃優(yōu)化。在如此海量的計劃空間中，如何高效的枚舉執(zhí)行計劃一直是查詢優(yōu)化器的難點。

挑戰(zhàn)三：高效的計劃管理機制

計劃管理機制分成計劃緩存機制和計劃演進機制。

1、計劃緩存機制：計劃緩存根據(jù)是否參數(shù)化，優(yōu)化一次/總是優(yōu)化以及是否緩存可以劃分成如下圖所示的三種計劃緩存方法。每個計劃緩存方法都有各自的優(yōu)缺點，不同的業(yè)務(wù)需求會選擇不同的計劃緩存方法。在螞蟻/阿里很多高并發(fā)，低時延的業(yè)務(wù)場景下，就會選擇參數(shù)化+優(yōu)化一次+緩存的策略，那么就需要解決不同參數(shù)對應(yīng)不同計劃的問題(parametric query optimization)，后面我們會詳細討論。

2、計劃演進機制：計劃演進是指對新生成計劃進行驗證，保證新計劃不會造成性能回退。在數(shù)據(jù)庫系統(tǒng)中， 新計劃因為一些原因(比如統(tǒng)計信息刷新，schema版本升級)無時無刻都在才生，而優(yōu)化器因為各種不精確的統(tǒng)計信息和代價模型始終是沒辦法百分百的保證新生成的計劃永遠都是最優(yōu)的，所以就需要一個演進機制來保證新生成的計劃不會造成性能回退。

OceanBase 查詢優(yōu)化器工程實踐

下面我們來看一下 OceanBase 根據(jù)自身的框架特點和業(yè)務(wù)模型如何解決查詢優(yōu)化器所面臨的挑戰(zhàn)。

從統(tǒng)計信息和代價模型的維度看，OceanBase 發(fā)明了基于 LSM-TREE 存儲結(jié)構(gòu)的基表訪問路徑選擇。從計劃空間的角度看，因為 OceanBase 原生就是一個分布式關(guān)系數(shù)據(jù)庫系統(tǒng)，它必然要面臨的一個問題就是分布式計劃優(yōu)化。從計劃管理的角度看，OceanBase 有一整套完善的計劃管理機制。

1.基于 LSM - TREE 的基表訪問路徑選擇
基表訪問路徑選擇方法是指優(yōu)化器選擇索引的方法，其本質(zhì)是要評估每一個索引的代價并選擇代價最小的索引來訪問數(shù)據(jù)庫中的表。對于一個索引路徑，它的代價主要由兩部分組成，掃描索引的代價和回表的代價(如果一個索引對于一個查詢來說不需要回表，那么就沒有回表的代價)。

通常來說，索引路徑的代價取決于很多因素，比如掃描/回表的行數(shù)，投影的列數(shù)，謂詞的個數(shù)等。為了簡化我們的討論，在下面的分析中，我們從行數(shù)這個維度來介紹這兩部分的代價。

• 掃描索引的代價
  掃描索引的代價跟掃描的行數(shù)成正比，而掃描的行數(shù)則是由一部分查詢的謂詞來決定，這些謂詞定義了索引掃描開始和結(jié)束位置。理論上來說掃描的行數(shù)越多，執(zhí)行時間就會越久。掃描索引的代價是順序 IO。
• 回表的代價
  回表的代價跟回表的行數(shù)也是正相關(guān)的，而回表的行數(shù)也是由查詢的謂詞來決定，理論上來說回表的行數(shù)越多，執(zhí)行時間就會越久。回表的掃描是隨機 IO，所以回表一行的代價通常會比順序掃描索引一行的代價要高。

在傳統(tǒng)關(guān)系數(shù)據(jù)庫中，掃描索引的行數(shù)和回表的行數(shù)都是通過優(yōu)化器中維護的統(tǒng)計信息來計算謂詞選擇率得到(或者通過一些更加高級的方法比如動態(tài)采樣)。

舉個簡單的例子，給定聯(lián)合索引(a,b)和查詢謂詞 a > 1 and a < 5 and b < 5, 那么謂詞 a > 1 and a < 5 定義了索引掃描開始和結(jié)束的位置，如果滿足這兩個條件的行數(shù)有 1w 行，那么掃描索引的代價就是 1w 行順序掃描，如果謂詞 b < 5 的選擇率是 0.5，那么回表的代價就是 5k 行的隨機掃描。

那么問題來了：傳統(tǒng)的計算行數(shù)和代價的方法是否適合基于 LSM-TREE 的存儲引擎？

LSM-TREE 存儲引擎把數(shù)據(jù)分為了兩部分(如下圖所示)，靜態(tài)數(shù)據(jù)(基線數(shù)據(jù))和動態(tài)數(shù)據(jù)(增量數(shù)據(jù))。其中靜態(tài)數(shù)據(jù)不會被修改，是只讀的，存儲于磁盤；所有的增量修改操作（增、刪、改）被記錄在動態(tài)數(shù)據(jù)中，存儲于內(nèi)存。靜態(tài)數(shù)據(jù)和增量數(shù)據(jù)會定期的合并形成新的基線數(shù)據(jù)。在 LSM-TREE 存儲引擎中，對于一個查詢操作，它需要合并靜態(tài)數(shù)據(jù)和動態(tài)數(shù)據(jù)來形成最終的查詢結(jié)果。

考慮下圖中 LSM-TREE 存儲引擎基線數(shù)據(jù)被刪除的一個例子。在該圖中，基線中有 10w 行數(shù)據(jù)，增量數(shù)據(jù)中維護了對這 10w 行數(shù)據(jù)的刪除操作。在這種場景下，這張表的總行數(shù)是 0 行，在傳統(tǒng)的基于 Buffer-Pool 的存儲引擎上，掃描會很快，也就是說行數(shù)和代價是匹配的。但是在 LSM-TREE 存儲引擎中，掃描會很慢(10w 基線數(shù)據(jù) + 10w 增加數(shù)據(jù)的合并)，也就是行數(shù)和代價是不匹配的。

這個問題的本質(zhì)原因是在基于 LSM-TREE 的存儲引擎上，傳統(tǒng)的基于動態(tài)采樣和選擇率信息計算出來的行數(shù)不足以反應(yīng)實際計算代價過程中需要的行數(shù)。

舉個簡單的例子，在傳統(tǒng)的關(guān)系數(shù)據(jù)庫中，我們插入 1w 行，然后刪除其中 1k 行，那么計算代價的時候會用 9k 行去計算，在 LSM-TREE 的場景下，如果前面 1w 行是在基線數(shù)據(jù)里面，那么內(nèi)存中會有額外的 1k 行，在計算代價的時候我們是需要用 11k 行去計算。

為了解決 LSM-TREE 存儲引擎的計算代價行數(shù)和表中真實行數(shù)不一致的行為，OceanBase 提出了“邏輯行”和“物理行”的概念以及計算它們的方法。其中邏輯行可以理解為傳統(tǒng)意義上的行數(shù)，物理行主要用于刻畫 LSM-TREE 這種存儲引擎在計算代價時需要真正訪問的行數(shù)。

再考慮上圖中的例子，在該圖中，邏輯行是 0 行，而物理行是 20w 行。給定索引掃描的開始/結(jié)束位置，對于基線數(shù)據(jù)，因為 OceanBase 為基線數(shù)據(jù)維護了塊級別的統(tǒng)計信息，所以能很快的計算出來基線行數(shù)。對于增量數(shù)據(jù)，則通過動態(tài)采樣方法獲取增/刪/改行數(shù)，最終兩者合并就可以得到邏輯行和物理行。下圖展示了 OceanBase 計算邏輯行和物理行的方法。

相比于傳統(tǒng)的基表訪問路徑方法，OceanBase 的基于邏輯行和物理行的方法有如下兩個優(yōu)勢:

優(yōu)勢一：實時統(tǒng)計信息

因為同時考慮了增量數(shù)據(jù)和基線數(shù)據(jù)，相當(dāng)于統(tǒng)計信息是實時的，而傳統(tǒng)方法的統(tǒng)計信息搜集是有一定的滯后性的(通常是一張表的增/刪/修改操作到了一定程度，才會觸發(fā)統(tǒng)計信息的重新搜集)。

優(yōu)勢二：解決了索引列上的謂詞依賴關(guān)系

考慮索引(a,b)以及查詢條件 a = 1 and b = 1 , 傳統(tǒng)的方法在計算這個查詢條件的選擇率的時候必然要考慮的一個問題是 a 和 b 是否存在依賴關(guān)系，然后再使用對應(yīng)的方法(多列直方圖或者動態(tài)采樣)來提高選擇率計算的正確率。OceanBase 目前的估行方法默認(rèn)能夠解決 a 和 b 的依賴關(guān)系的場景。

2.OceanBase 分布式計劃優(yōu)化

OceanBase 原生就有分布式的屬性，那么它必然要解決的一個問題就是分布式計劃優(yōu)化。很多人認(rèn)為分布式計劃優(yōu)化很難，無從下手，那么分布式計劃優(yōu)化跟本地優(yōu)化到底有什么區(qū)別？分布式計劃優(yōu)化是否需要修改現(xiàn)有的查詢優(yōu)化框架來做優(yōu)化？

在筆者看來，現(xiàn)有的查詢優(yōu)化框架完全有能力處理分布式計劃優(yōu)化，但是分布式計劃優(yōu)化會大大增加計劃的搜索空間，主要原因如下:

1、在分布式場景下，選擇的是算子的分布式算法，而算子的分布式算法空間比算子本地算法的空間要大很多。下圖展示了一個 Hash Join 在分布式場景下可以選擇的分布式算法。

2、在分布式場景下，除了序這個物理屬性之外，還增加了分區(qū)信息這個物理屬性。分區(qū)信息主要包括如何分區(qū)以及分區(qū)的物理信息。分區(qū)信息決定了算子可以采用何種分布式算法。

3、在分布式場景下，分區(qū)裁剪/并行度優(yōu)化/分區(qū)內(nèi)(間)并行等因素也會增大分布式計劃的優(yōu)化復(fù)雜度。

OceanBase 目前采用兩階段的方式來做分布式優(yōu)化。在第一階段，OceanBase 基于所有表都是本地的假設(shè)生成一個最優(yōu)本地計劃。在第二階段，OceanBase 開始做并行優(yōu)化, 用啟發(fā)式規(guī)則來選擇本地最優(yōu)計劃中算子的分布式算法。下圖展示了 OceanBase 二階段分布式計劃的一個例子。

OceanBase 二階段的分布式計劃優(yōu)化方法能減少優(yōu)化空間，降低優(yōu)化復(fù)雜度，但是因為在第一階段優(yōu)化的時候沒有考慮算子的分布式信息，所以可能導(dǎo)致生成的計劃次優(yōu)。目前 OceanBase 正在實現(xiàn)一階段的分布式計劃優(yōu)化:

1、在 System-R 的 Bottom-up 的動態(tài)規(guī)劃算法中，枚舉所有算子的所有分布式實現(xiàn)并且維護算子的物理屬性。

2、在 System-R 的 Bottom-up 的動態(tài)規(guī)劃算法中，對于每一個枚舉的子集, 保留代價最小/有 Interesting order/有 Interesting 分區(qū)的計劃。

一階段的分布式計劃優(yōu)化可能會導(dǎo)致計劃空間增長很快，所以必須要有一些 Pruning 規(guī)則來減少計劃空間或者跟本地優(yōu)化一樣在計劃空間比較大的時候，使用遺傳算法或者啟發(fā)式規(guī)則來解決這個問題。

3.OceanBase 計劃管理機制

OceanBase 基于螞蟻/阿里真實的業(yè)務(wù)場景，構(gòu)建了一套完善的計劃緩存機制和計劃演進機制。

OceanBase 計劃緩存機制
如下圖所示，OceanBase 目前使用參數(shù)化計劃緩存的方式。這里涉及到兩個問題：為什么選擇參數(shù)化以及為什么選擇緩存？

1、參數(shù)化：在螞蟻/阿里很多真實業(yè)務(wù)場景下，為每一個參數(shù)緩存一個計劃是不切實際的。考慮一個根據(jù)訂單號來查詢訂單信息的場景，在螞蟻/阿里高并發(fā)的場景下，為每一個訂單號換成一個計劃是不切實際的，而且也不需要，因為一個帶訂單號的索引能解決所有參數(shù)的場景。

2、計劃緩存：計劃緩存是因為性能的原因，對于螞蟻/阿里很多真實業(yè)務(wù)場景來說，如果命中計劃，那么一個查詢的性能會在幾百 us，但是如果沒有命中計劃，那么性能大概會在幾個 ms。對于高并發(fā)，低時延的場景，這種性能優(yōu)勢是很重要的。

OceanBase 使用參數(shù)化計劃緩存的方式，但是在很多螞蟻真實的業(yè)務(wù)場景下，對所有的參數(shù)使用同一個計劃并不是最優(yōu)的選擇。考慮一個螞蟻商戶域的業(yè)務(wù)場景，這個場景以商戶的維度去記錄每一筆賬單信息，商戶可以根據(jù)這些信息做一些分析和查詢。這種場景肯定會存在大小賬號問題，如下圖所示，淘寶可能貢獻了 50% 的訂單，LV 可能只貢獻了 0.1% 的訂單。考慮查詢“統(tǒng)計一個商戶過去一年的銷售額”，如果是淘寶和美團這種大商戶，那么直接主表掃描會是一個合理的計劃，對于 LV 這種小商戶，那么走索引會是一個合理的計劃。

為了解決不同參數(shù)對應(yīng)不同計劃的問題，OceanBase 實現(xiàn)了如下圖所示的自適應(yīng)計劃匹配。該方法會通過直方圖和執(zhí)行反饋來監(jiān)控每一個緩存的計劃是否存在不同參數(shù)需要對應(yīng)不同計劃的問題。一旦存在，自適應(yīng)計劃匹配會通過漸進式的合并選擇率空間來達到把整個選擇率空間劃分成若干個計劃空間(每個空間對應(yīng)一個計劃)的目的。

OceanBase 計劃演進機制
在螞蟻/阿里很多高并發(fā)，低時延的業(yè)務(wù)場景下，OceanBase 必須要保證新生成的計劃不會導(dǎo)致性能回退。下圖展示了 OceanBase 對新計劃的演進過程。不同于傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)采用定時任務(wù)和后臺進程演進的方式，OceanBase 會使用真實的流量來進行演進，這樣的一個好處是可以及時的更新比較優(yōu)的計劃。比如當(dāng)業(yè)務(wù)新建了一個更優(yōu)的索引時，傳統(tǒng)數(shù)據(jù)庫系統(tǒng)并不能立刻使用該索引，需要在演進定時任務(wù)啟動后才能演進驗證使用，而 OceanBase 可以及時的使用該計劃。

總結(jié)

OceanBase 查詢優(yōu)化器的實現(xiàn)立足于自身架構(gòu)和業(yè)務(wù)場景特點，比如 LSM-TREE 存儲結(jié)構(gòu)、Share-Nothing 的分布式架構(gòu)和大規(guī)模的運維穩(wěn)定性。OceanBase 致力于打造基于 OLTP 和 OLAP 融合的查詢優(yōu)化器。從 OLTP 的角度看，我們立足于螞蟻/阿里真實業(yè)務(wù)場景，完美承載了業(yè)務(wù)需求。從 OLAP 的角度看，我們對標(biāo)商業(yè)數(shù)據(jù)庫，進一步打磨我們 HTAP 的優(yōu)化器能力。

原文鏈接
本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的支付宝工程师如何搞定关系数据库的“大脑”——查询优化器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。