前言
查詢優化器是關系資料庫系統的核心子產品，是資料庫核心開發的重點和難點，也是衡量整個資料庫系統成熟度的“試金石”。
查詢優化理論誕生距今已有四十來年，學術界和工業界其實已經形成了一套比較完善的查詢優化架構(System-R 的 Bottom-up 優化架構和 Volcano/Cascade 的 Top-down 優化架構)，但圍繞查詢優化的核心難題始終沒變——如何利用有限的系統資源盡可能為查詢選擇一個“好”的執行計劃。
近年來，新的存儲結構（如 LSM 存儲結構）的出現和分布式資料庫的流行進一步加大了查詢優化的複雜性，本文章結合 OceanBase 資料庫過去近十年時間的實踐經驗，與大家一起探讨查詢優化在實際應用場景中的挑戰和解決方案。
查詢優化器簡介
SQL 是一種結構化查詢語言，它隻告訴資料庫”想要什麼”，但是它不會告訴資料庫”如何擷取”這個結果，這個"如何擷取"的過程是由資料庫的“大腦”查詢優化器來決定的。在資料庫系統中，一個查詢通常會有很多種擷取結果的方法，每一種擷取的方法被稱為一個"執行計劃"。給定一個 SQL，查詢優化器首先會枚舉出等價的執行計劃。
其次，查詢優化器會根據統計資訊和代價模型為每個執行計劃計算一個“代價”，這裡的代價通常是指執行計劃的執行時間或者執行計劃在執行時對系統資源(CPU + IO + NETWORK)的占用量。最後，查詢優化器會在衆多等價計劃中選擇一個"代價最小"的執行計劃。下圖展示了查詢優化器的基本元件和執行流程。
查詢優化器面臨的挑戰
查詢優化自從誕生以來一直是資料庫的難點，它面臨的挑戰主要展現在以下三個方面:
挑戰一：精準的統計資訊和代價模型
統計資訊和代價模型是查詢優化器基礎子產品，它主要負責給執行計劃計算代價。精準的統計資訊和代價模型一直是資料庫系統想要解決的難題，主要原因如下:
1、統計資訊：在資料庫系統中，統計資訊搜集主要存在兩個問題。首先，統計資訊是通過采樣搜集，是以必然存在采樣誤差。其次，統計資訊搜集是有一定滞後性的，也就是說在優化一個 SQL 查詢的時候，它使用的統計資訊是系統前一個時刻的統計資訊。
2、選擇率計算和中間結果估計：選擇率計算一直以來都是資料庫系統的難點，學術界和工業界一直在研究能使選擇率計算變得更加準确的方法，比如動态采樣，多列直方圖等計劃，但是始終沒有解決這個難題，比如連接配接謂詞選擇率的計算目前就沒有很好的解決方法。
3、代價模型：目前主流的資料庫系統基本都是使用靜态的代價模型，比如靜态的 buffer 命中率，靜态的 IO RT，但是這些值都是随着系統的負載變化而變化的。如果想要一個非常精準的代價模型，就必須要使用動态的代價模型。
挑戰二：海量的計劃空間
複雜查詢的計劃空間是非常大的，在很多場景下，優化器甚至沒辦法枚舉出所有等價的執行計劃。下圖展示了星型查詢等價邏輯計劃個數(不包含笛卡爾乘積的邏輯計劃)，而優化器真正的計劃空間還得正交上算子實體實作，基于代價的改寫和分布式計劃優化。在如此海量的計劃空間中，如何高效的枚舉執行計劃一直是查詢優化器的難點。
挑戰三：高效的計劃管理機制
計劃管理機制分成計劃緩存機制和計劃演進機制。
1、計劃緩存機制：計劃緩存根據是否參數化，優化一次/總是優化以及是否緩存可以劃分成如下圖所示的三種計劃緩存方法。每個計劃緩存方法都有各自的優缺點，不同的業務需求會選擇不同的計劃緩存方法。在螞蟻/阿裡很多高并發，低延遲時間的業務場景下，就會選擇參數化+優化一次+緩存的政策，那麼就需要解決不同參數對應不同計劃的問題(parametric query optimization)，後面我們會詳細讨論。
2、計劃演進機制：計劃演進是指對新生成計劃進行驗證，保證新計劃不會造成性能回退。在資料庫系統中， 新計劃因為一些原因(比如統計資訊重新整理，schema版本更新)無時無刻都在才生，而優化器因為各種不精确的統計資訊和代價模型始終是沒辦法百分百的保證新生成的計劃永遠都是最優的，是以就需要一個演進機制來保證新生成的計劃不會造成性能回退。
OceanBase 查詢優化器工程實踐
下面我們來看一下 OceanBase 根據自身的架構特點和業務模型如何解決查詢優化器所面臨的挑戰。
從統計資訊和代價模型的次元看，OceanBase 發明了基于 LSM-TREE 存儲結構的基表通路路徑選擇。從計劃空間的角度看，因為 OceanBase 原生就是一個分布式關系資料庫系統，它必然要面臨的一個問題就是分布式計劃優化。從計劃管理的角度看，OceanBase 有一整套完善的計劃管理機制。
1.基于 LSM - TREE 的基表通路路徑選擇
基表通路路徑選擇方法是指優化器選擇索引的方法，其本質是要評估每一個索引的代價并選擇代價最小的索引來通路資料庫中的表。對于一個索引路徑，它的代價主要由兩部分組成，掃描索引的代價和回表的代價(如果一個索引對于一個查詢來說不需要回表，那麼就沒有回表的代價)。
通常來說，索引路徑的代價取決于很多因素，比如掃描/回表的行數，投影的列數，謂詞的個數等。為了簡化我們的讨論，在下面的分析中，我們從行數這個次元來介紹這兩部分的代價。
-
掃描索引的代價
掃描索引的代價跟掃描的行數成正比，而掃描的行數則是由一部分查詢的謂詞來決定，這些謂詞定義了索引掃描開始和結束位置。理論上來說掃描的行數越多，執行時間就會越久。掃描索引的代價是順序 IO。
-
回表的代價
回表的代價跟回表的行數也是正相關的，而回表的行數也是由查詢的謂詞來決定，理論上來說回表的行數越多，執行時間就會越久。回表的掃描是随機 IO，是以回表一行的代價通常會比順序掃描索引一行的代價要高。
在傳統關系資料庫中，掃描索引的行數和回表的行數都是通過優化器中維護的統計資訊來計算謂詞選擇率得到(或者通過一些更加進階的方法比如動态采樣)。
舉個簡單的例子，給定聯合索引(a,b)和查詢謂詞 a > 1 and a < 5 and b < 5, 那麼謂詞 a > 1 and a < 5 定義了索引掃描開始和結束的位置，如果滿足這兩個條件的行數有 1w 行，那麼掃描索引的代價就是 1w 行順序掃描，如果謂詞 b < 5 的選擇率是 0.5，那麼回表的代價就是 5k 行的随機掃描。
那麼問題來了：傳統的計算行數和代價的方法是否适合基于 LSM-TREE 的存儲引擎？
LSM-TREE 存儲引擎把資料分為了兩部分(如下圖所示)，靜态資料(基線資料)和動态資料(增量資料)。其中靜态資料不會被修改，是隻讀的，存儲于磁盤；所有的增量修改操作（增、删、改）被記錄在動态資料中，存儲于記憶體。靜态資料和增量資料會定期的合并形成新的基線資料。在 LSM-TREE 存儲引擎中，對于一個查詢操作，它需要合并靜态資料和動态資料來形成最終的查詢結果。
考慮下圖中 LSM-TREE 存儲引擎基線資料被删除的一個例子。在該圖中，基線中有 10w 行資料，增量資料中維護了對這 10w 行資料的删除操作。在這種場景下，這張表的總行數是 0 行，在傳統的基于 Buffer-Pool 的存儲引擎上，掃描會很快，也就是說行數和代價是比對的。但是在 LSM-TREE 存儲引擎中，掃描會很慢(10w 基線資料 + 10w 增加資料的合并)，也就是行數和代價是不比對的。
這個問題的本質原因是在基于 LSM-TREE 的存儲引擎上，傳統的基于動态采樣和選擇率資訊計算出來的行數不足以反應實際計算代價過程中需要的行數。
舉個簡單的例子，在傳統的關系資料庫中，我們插入 1w 行，然後删除其中 1k 行，那麼計算代價的時候會用 9k 行去計算，在 LSM-TREE 的場景下，如果前面 1w 行是在基線資料裡面，那麼記憶體中會有額外的 1k 行，在計算代價的時候我們是需要用 11k 行去計算。
為了解決 LSM-TREE 存儲引擎的計算代價行數和表中真實行數不一緻的行為，OceanBase 提出了“邏輯行”和“實體行”的概念以及計算它們的方法。其中邏輯行可以了解為傳統意義上的行數，實體行主要用于刻畫 LSM-TREE 這種存儲引擎在計算代價時需要真正通路的行數。
再考慮上圖中的例子，在該圖中，邏輯行是 0 行，而實體行是 20w 行。給定索引掃描的開始/結束位置，對于基線資料，因為 OceanBase 為基線資料維護了塊級别的統計資訊，是以能很快的計算出來基線行數。對于增量資料，則通過動态采樣方法擷取增/删/改行數，最終兩者合并就可以得到邏輯行和實體行。下圖展示了 OceanBase 計算邏輯行和實體行的方法。
相比于傳統的基表通路路徑方法，OceanBase 的基于邏輯行和實體行的方法有如下兩個優勢:
優勢一：實時統計資訊
因為同時考慮了增量資料和基線資料，相當于統計資訊是實時的，而傳統方法的統計資訊搜集是有一定的滞後性的(通常是一張表的增/删/修改操作到了一定程度，才會觸發統計資訊的重新搜集)。
優勢二：解決了索引列上的謂詞依賴關系
考慮索引(a,b)以及查詢條件 a = 1 and b = 1 , 傳統的方法在計算這個查詢條件的選擇率的時候必然要考慮的一個問題是 a 和 b 是否存在依賴關系，然後再使用對應的方法(多列直方圖或者動态采樣)來提高選擇率計算的正确率。OceanBase 目前的估行方法預設能夠解決 a 和 b 的依賴關系的場景。
2.OceanBase 分布式計劃優化
OceanBase 原生就有分布式的屬性，那麼它必然要解決的一個問題就是分布式計劃優化。很多人認為分布式計劃優化很難，無從下手，那麼分布式計劃優化跟本地優化到底有什麼差別？分布式計劃優化是否需要修改現有的查詢優化架構來做優化？
在筆者看來，現有的查詢優化架構完全有能力處理分布式計劃優化，但是分布式計劃優化會大大增加計劃的搜尋空間，主要原因如下:
1、在分布式場景下，選擇的是算子的分布式算法，而算子的分布式算法空間比算子本地算法的空間要大很多。下圖展示了一個 Hash Join 在分布式場景下可以選擇的分布式算法。
2、在分布式場景下，除了序這個實體屬性之外，還增加了分區資訊這個實體屬性。分區資訊主要包括如何分區以及分區的實體資訊。分區資訊決定了算子可以采用何種分布式算法。
3、在分布式場景下，分區裁剪/并行度優化/分區内(間)并行等因素也會增大分布式計劃的優化複雜度。
OceanBase 目前采用兩階段的方式來做分布式優化。在第一階段，OceanBase 基于所有表都是本地的假設生成一個最優本地計劃。在第二階段，OceanBase 開始做并行優化, 用啟發式規則來選擇本地最優計劃中算子的分布式算法。下圖展示了 OceanBase 二階段分布式計劃的一個例子。
OceanBase 二階段的分布式計劃優化方法能減少優化空間，降低優化複雜度，但是因為在第一階段優化的時候沒有考慮算子的分布式資訊，是以可能導緻生成的計劃次優。目前 OceanBase 正在實作一階段的分布式計劃優化:
1、在 System-R 的 Bottom-up 的動态規劃算法中，枚舉所有算子的所有分布式實作并且維護算子的實體屬性。
2、在 System-R 的 Bottom-up 的動态規劃算法中，對于每一個枚舉的子集, 保留代價最小/有 Interesting order/有 Interesting 分區的計劃。
一階段的分布式計劃優化可能會導緻計劃空間增長很快，是以必須要有一些 Pruning 規則來減少計劃空間或者跟本地優化一樣在計劃空間比較大的時候，使用遺傳算法或者啟發式規則來解決這個問題。
3.OceanBase 計劃管理機制
OceanBase 基于螞蟻/阿裡真實的業務場景，建構了一套完善的計劃緩存機制和計劃演進機制。
OceanBase 計劃緩存機制
如下圖所示，OceanBase 目前使用參數化計劃緩存的方式。這裡涉及到兩個問題：為什麼選擇參數化以及為什麼選擇緩存？
1、參數化：在螞蟻/阿裡很多真實業務場景下，為每一個參數緩存一個計劃是不切實際的。考慮一個根據訂單号來查詢訂單資訊的場景，在螞蟻/阿裡高并發的場景下，為每一個訂單号換成一個計劃是不切實際的，而且也不需要，因為一個帶訂單号的索引能解決所有參數的場景。
2、計劃緩存：計劃緩存是因為性能的原因，對于螞蟻/阿裡很多真實業務場景來說，如果命中計劃，那麼一個查詢的性能會在幾百 us，但是如果沒有命中計劃，那麼性能大概會在幾個 ms。對于高并發，低延遲時間的場景，這種性能優勢是很重要的。
OceanBase 使用參數化計劃緩存的方式，但是在很多螞蟻真實的業務場景下，對所有的參數使用同一個計劃并不是最優的選擇。考慮一個螞蟻商戶域的業務場景，這個場景以商戶的次元去記錄每一筆賬單資訊，商戶可以根據這些資訊做一些分析和查詢。這種場景肯定會存在大小賬号問題，如下圖所示，淘寶可能貢獻了 50% 的訂單，LV 可能隻貢獻了 0.1% 的訂單。考慮查詢“統計一個商戶過去一年的銷售額”，如果是淘寶和美團這種大商戶，那麼直接主表掃描會是一個合理的計劃，對于 LV 這種小商戶，那麼走索引會是一個合理的計劃。
為了解決不同參數對應不同計劃的問題，OceanBase 實作了如下圖所示的自适應計劃比對。該方法會通過直方圖和執行回報來監控每一個緩存的計劃是否存在不同參數需要對應不同計劃的問題。一旦存在，自适應計劃比對會通過漸進式的合并選擇率空間來達到把整個選擇率空間劃分成若幹個計劃空間(每個空間對應一個計劃)的目的。
OceanBase 計劃演進機制
在螞蟻/阿裡很多高并發，低延遲時間的業務場景下，OceanBase 必須要保證新生成的計劃不會導緻性能回退。下圖展示了 OceanBase 對新計劃的演進過程。不同于傳統的資料庫系統采用定時任務和背景程序演進的方式，OceanBase 會使用真實的流量來進行演進，這樣的一個好處是可以及時的更新比較優的計劃。比如當業務建立了一個更優的索引時，傳統資料庫系統并不能立刻使用該索引，需要在演進定時任務啟動後才能演進驗證使用，而 OceanBase 可以及時的使用該計劃。
總結
OceanBase 查詢優化器的實作立足于自身架構和業務場景特點，比如 LSM-TREE 存儲結構、Share-Nothing 的分布式架構和大規模的運維穩定性。OceanBase 緻力于打造基于 OLTP 和 OLAP 融合的查詢優化器。從 OLTP 的角度看，我們立足于螞蟻/阿裡真實業務場景，完美承載了業務需求。從 OLAP 的角度看，我們對标商業資料庫，進一步打磨我們 HTAP 的優化器能力。