SQL優化-RBO（Rule-Based Optimization）

語言: CN / TW / HK

時間 2022-08-29 17:02:47 開務資料庫

主題: go c++ linux mysql python oracle postgresql arrow rocksdb benchmark

SQL 優化的過程可以分為邏輯優化和物理優化兩個部分。邏輯優化主要是基於規則的優化，簡稱 RBO（Rule-Based Optimization）。物理優化會為邏輯查詢計劃中的運算元選擇某個具體的實現，需要用到一些統計資訊，決定哪一種方式代價最低，所以是基於代價的優化 CBO（Cost-Based Optimization）。

優化器是開務資料庫中的一個核心的模組，開務資料庫使用優化器來完成對 SQL 語句優化並得到最優的邏輯計劃，開務資料庫裡的優化器分為 RBO 和 CBO 兩個階段。

RBO 是基於規則的優化，這些規則背後的原理是關係代數的等價變換，其中典型的規則包括：列剪裁，謂詞下推等。RBO 將內建的規則作為優化的基礎，同時這些規則是硬編碼在開務資料庫的程式碼中的，RBO 會根據這些規則從目標 SQL 諸多可能的代數轉換中選擇一條來作為邏輯計劃。

開務資料庫的 RBO 優化器採用了 Optgen 語言編寫，它提供了一種直觀的語法來定義、匹配和替換目標表達式樹中的節點。優化器規則的編寫便是基於這種語言，使用 Optgen 語言可以很容易實現 RBO 規則。

開務資料庫的 RBO 規則實現如下圖所示，①被稱為匹配模式，②被稱為替換模式，優化器規則是某表示式滿足①模式，然後轉化為②模式的表示式。

①的匹配模式又分為三部分，第一部分中括號內是規則的名稱，在 Opt 檔案編譯時會作為規則的標識，第二部分是第二行左小括號後位規則作用域，在開務資料庫內有明確的型別劃分。編寫規則時要清楚這條規則是針對哪種型別表示式發生作用，第三部分是剩下的規則部分，是規則的匹配條件。

模式①匹配條件是等值表示式，左孩子不是變數，右孩子是變數。這裡的 NormalizeEq 是名稱，Eq 是規則型別，針對等值表示式。模式②表示新構建一個等值表示式，只是與原表示式相比，左右孩子互換。示例：1=a => a=1

開務資料庫內建了上百種 RBO 規則，支援大量的 SQL 語句的代數優化，包括傳統的列裁剪、最大最小消除、投影消除、謂詞下推等等，也包括一些複雜的 Join 等下推操作。TryDecorrelateGroupBy，這個規則的 OptGen 規則描述如下：

[TryDecorrelateGroupBy, Normalize]
(InnerJoin | InnerJoinApply
    $left:*
    $right:* &
        (HasOuterCols $right) &
        (GroupBy | DistinctOn
            $input:*
            $aggregations:*
            $groupingPrivate:*
        ) &
        (IsUnorderedGrouping $groupingPrivate)
    $on:*
    $private:*
)
=>
(Select
    ((OpName $right)
        (InnerJoinApply
            $newLeft:(EnsureKey $left)
            $input
            []
            $private
        )
        (AppendAggCols
            $aggregations
            ConstAgg (NonKeyCols $newLeft)
        )
        (AddColsToGrouping $groupingPrivate (KeyCols $newLeft))
    )
    $on
)

TryDecorrelateGroupBy 主要作用在 InnerJoin | InnerJoinApply 操作中，它將 Join“下推”到 GroupBy 運算子中，以嘗試繼續“挖掘”以找到並消除不必要的相關性。最終的希望是觸發 DecorrelateJoin 規則，將 JoinApply 操作符轉換為非 Apply Join 操作符。

SELECT left.x, left.y, input.*
FROM left
INNER JOIN LATERAL
 (
  SELECT COUNT(*) FROM input WHERE input.x = left.x GROUP BY c
) AS input
ON left.y = 10
=>
SELECT CONST_AGG(left.x), CONST_AGG(left.y), COUNT(*)
FROM left WITH ORDINALITY
INNER JOIN LATERAL
 (
  SELECT * FROM input WHERE input.x = left.x
) AS input
ON True
GROUP BY input.c, left.ordinality
HAVING left.y = 10

開務資料庫採用了 Optgen 語言作為 RBO 規則的編寫語言，通過上面的例子可以看出，按照既定模式新增完善 RBO 規則十分便捷，通過編譯可以將規則嵌入到系統 RBO 規則框架中；後續會有更深入的關於 RBO 使用框架與大家分享，敬請期待！

開務資料庫是一款浪潮集團核心研發的先進、安全的雲原生分散式資料庫；具備雲原生、多中心、高可用、事務強一致等特性，滿足HTAP場景需求。業務範圍覆蓋能源、工業網際網路、政務、教育、金融等多行業。我們是一支平均年齡30歲的年輕團隊，在短短不到三年的時間裡，我們已取得近300項發明專利受理，10項自有產品軟著授權。熱烈歡迎廣大夥伴加入我們的團隊，熱門崗位火熱招聘中，簡歷投遞郵箱：[email protected] / [email protected]

資料庫儲存核心研發工程師

工作職責：

1、負責儲存子系統的研發路線規劃、架構設計和關鍵技術問題攻關；

2、負責編寫功能測試用例，測試工具進行系統驗證；

3、負責資料庫的系統性能診斷與調優；

4、負責資料庫相關關鍵技術的預研和在團隊中的引導；

5、深入理解業務場景的資料庫儲存需求，針對性的為不同業務場景提供最合適的儲存方案。

任職要求：

1、學歷：本科或者本科以上學歷；

2、專業：計算機或相關專業；

3、專業知識：

— 3 年及以上 GO/C++ 開發經驗；

— 精通 C/C++/GO 語言，Linux 系統程式設計。熟悉無鎖資料結構，熟悉現代硬體體系結構 (CPU/Cache/Memory/Storage), 熟悉併發程式設計；

— 熟練使用 MySQL、PostgeSQL 等主流資料庫；

— 熟悉資料庫儲存系統的基本理論，熟悉事務處理，日誌與恢復策略，多版本併發控制技術的實現，對資料庫的基本理論和內部實現機制有深刻的理解；

— 技術視野開闊，有一定的系統性能優化經驗，掌握各種效能診斷工具和各種優化方法；

— 熟悉時序資料庫，有實際的時序資料庫開發經驗優先；

— 熟悉 RocksDB、Arrow、Parquet 等開源儲存專案原始碼者優先。

Base 地： 上海 / 天津 / 濟南 / 北京

資料庫方案工程師

工作職責：

1、負責分散式資料庫，或其相關工具、平臺等產品的梳理、規劃、設計和推進工作；

2、進行解決方案的調研、設計和驗證；

3、設計、撰寫和維護產品紅皮書；

4、跨部門溝通，協調各類資源以確保產品順利上線，推進產品迭代。

任職要求：

1、5年以上的資料庫運維及方案設計經驗（ORACLE/Mysql/PostgreSQL任意一種），對部署，優化，災備，恢復，高可用有實際經驗；

2、1年左右的分散式資料庫經驗，瞭解國內任意一款分散式資料庫，有部署，POC，問題處理經驗；

3、對OLTP和OLAP系統或其中一種有實際運維設計經驗；

4、對資料庫災備，同步方案有實際專案經驗；

5、會一種資料庫benchmark工具，設計相應場景進行測試並結合已有經驗給與相應調整優化；

6、有基本的程式設計能力，如go，shell，python其中一項，可以寫簡單程式對資料庫進行併發測試，功能驗證；

7、有專案管理能力，很好的溝通能力，可以與開發人員順暢溝通，並於合作高校學生完成實驗及文件編寫；

8、紮實的技術，linux和資料庫方面有一定積累，能對開發人員及學生進行一定指導，促使相關工作順利推進；

9、較強的文件編寫組織能力，根據實驗文件及相關手冊，編寫使用者解決方案手冊；

10、有一定語言表達能力，能做資料庫相關功能培訓。

Base地： 上海/天津/濟南/北京

「其他文章」