Calcite技術研究

• 2020 年 2 月 24 日
• 筆記

原文作者：王長春，來自平安銀行零售大數據團隊

概述

Apache Calcite是一個基礎的軟體框架，它提供了查詢處理、查詢優化以及查詢語言支援的能力。很多流行的開源數據處理系統例如Apache Hive,Apache Storm,ApacheFlink,Druid等都採用了它。

下圖是採用Apache Calcite的開源數據處理系統，以及Calcite能連接到的數據源。

大多數數據處理系統是使用Calcite來做SQL解析和查詢優化。還有部分使用Avatica(Calcite的子項目)來構建自己的JDBC driver。還有部分使用Calcite來重寫查詢請求以使用物化視圖。

最近十幾年來，出現了很多專門的數據處理引擎。例如列式存儲、流處理引擎、文檔搜索引擎等等。這些引擎宣稱他們在特殊方面能提供更高「性價比」的性能，並且宣稱「one size fits all」範式的時代已經終結了。Spark、Storm、Flink、Elasticsearch、Druid等多種引擎的流行確實說明了這一點。

這些數據處理引擎都面臨著一些共同但是難以解決的問題。

• 一是數據處理引擎都要做查詢優化以及提供sql查詢語言或者其他DSL查詢語言。
• 二是使用者可能使用了多個專門的數據引擎，例如使用了ES、Spark、Druid.那麼使用者很可能會有在異構數據源上支援查詢以及查詢優化的需求。

Apache Calcite就是為解決這些問題而設計的。Calcite提供了所有數據處理系統所需要的查詢執行、查詢優化、查詢語言等能力。但是Calcite沒有提供數據存儲以及數據管理的能力，這兩個能力是由各自的數據處理引擎來提供的。此外，Calcite提供了跨平台查詢優化能力。

總結一下，Calcite在現在這麼流行，主要原因如下：

• 開源並完全按照Apache基金會的規則規範運作。Calcite已於2013年成為Apache頂級項目。
• Calcite使用Java開發，便於被數據處理引擎集成。
• Calcite數據模型強大，既能支援流式數據處理引擎，也能支援批式數據處理引擎。
• Calcite優化器的每個模組都是可插拔的可擴展的，包括rules和成本模型。這使得Calcite優化器非常靈活。
• Calcite能在多個數據處理引擎上執行查詢以及做查詢優化。
• Calcite提供了ANSI 標準SQL，以及各種SQL dialect. 另外Calcite提供了符合JDBC 規範的Driver。

Calcite架構

Calcite包含了很多典型數據管理系統的組成模組。但是，它故意忽略了一些關鍵模組，例如數據的存儲，數據處理演算法，以及元數據的存儲。但正是這些特點，使得calcite成為有多個數據存儲和多個數據處理引擎的應用程式的中間層。當然，它也可以成為構建一個數據處理引擎的基礎組件。

Calcite架構如上圖所示。

Calcite優化器使用關係運算符樹作為內部表現形式。優化引擎主要由規則、元數據提供者、以及planner engine組成。

Calcite包含一個查詢解析器和驗證器，可以將SQL查詢轉換為關係運算符樹。由於Calcite不包含存儲層，它提供了一種機制來通過適配器定義外部存儲引擎中的table schema和views（適配器將在下文中詳述）。這樣，應用程式就可以通過calcite訪問外部存儲引擎。

在查詢被優化後，calcite還能將優化後的關係表達式翻譯回SQL。這使得calcite能夠和有sql介面但是沒有優化器的數據處理引擎很好的集成。

查詢代數

3.1 運算符

Calcite的核心是關係代數。除了表達DML操作的基本運算符外，calcite還提供了一些額外的運算符，這些運算符能夠簡潔的表達複雜操作，或者能夠更高效的識別優化機會。例如，OLAP中的decision making,以及流處理引擎中的窗口函數。Calcite引入了window運算符並且封裝了window的定義，例如窗口的上下界、分區以及聚合函數。

3.2 Traits

Calcite不使用不同的實體來代表邏輯和物理運算符。它使用traits來描述運算符的物理屬性。這些特質能夠幫助優化器計算不同可選的plan的成本。改變特質的值不會改變已經計算過的邏輯表達式的值，舉例：某個運算符已經產生的行數不會被改變。

在優化過程中，Calcite試圖在關係表達式上強制執行某些traits，比如某些列的排序。關係運算符可以實現converter介面來指示如何改變表達式的traits的值。

Calcite包括一些通用特質，這些特質描述了關係運算符（例如ordering,grouping,partitioning）所產生的數據的物理屬性。Calcite優化器能對這些屬性進行推理和探索以發現不必要的運算符。例如如果sort運算符的輸入已經是有序的，那麼這個sort運算符就可以刪掉。

除了通用特質，Calcite的一個重要功能就是calling convention特質。本質上來說，這個特質代表的是表達式所被執行的數據處理系統。這個特質使得calcite能夠滿足查詢運行在多個引擎上時，優化可以透明地進行。

例如上圖所示，mysql中有products表，Splunk中有orders表。理所當然的，orders表的scan是在splunk convention中。Products表的scan發生在jdbc-mysql convention中。Join是一個邏輯convention，即還沒有實現被選擇。另外，上圖的sql查詢還包括filter,這個運算符根據適配器的規則被下推到splunk。對join來說，一個可能的實現是使用Spark作為外部引擎。Join轉化為spark convention，他的輸入是從jdbc-mysql和splunk到spark convention的converters運算符。

適配器

適配器定義了calcite如何與各種數據源集成以訪問各種數據源。適配器的組件如下圖所示：

適配器由model、schema以及schema factory組成。Model是數據源的物理屬性的規範。Schema是model中的數據的定義（主要是格式和布局）。數據本身可以通過table訪問。Calcite使用適配層中定義的table介面訪問數據。適配器可以定義一系列的規則並添加到planner中。例如，他可以添加以下規則：把邏輯關係表達式轉化為這個適配層對應的引擎的關係表達式。Schema factory從model中獲取元數據資訊並生成schema。

章節3中提到過，Calcite使用calling convention來識別關係運算符屬於哪一數據處理引擎。這些運算符為適配層中的表實現了訪問方法。當查詢被解析並且轉化為關係代數表達式之後，calcite會為每個表創建一個scan的運算符。Scan運算符是適配層必須要實現的。如果適配層實現了scan運算符，calcite優化器就能使用client側運算符例如sorting,filtering,join等。

適配器是一個很好的抽象，他使得查詢優化不局限於某個數據處理引擎，可以跨多個數據處理引擎。Calcite可以把查詢中涉及到的多個表邏輯下推到各自的數據處理引擎，然後再對結果數據執行聚合和join。實現適配器的最小要求是提供table scan 運算符，當然也可以包括更多高級的優化。任何關係代數中的表達式都能根據優化規則下推到適配器中。

Calcite本身已經實現了很多的適配器，當然我們也可以自己開發新的數據處理引擎對應的適配器。下圖是calcite內置的適配器。

查詢處理與優化

查詢優化是calcite的一個重要功能。查詢優化其實就是重複地在關係表達式上執行planner rule。這個過程依賴於成本模型，planner 引擎會試圖產生一個有相同語義但是成本更低的替代表達式。優化器的各個組件都是可擴展的，你可以添加關係運算符，規則，成本模型，以及統計數據。

5.1 規劃器規則（planner rules）

Calcite包括一系列的規劃器規則來進行表達式樹的轉換。一個規則匹配樹的一個模式並在不改變語義的前提下執行轉換。Calcite包含幾百個優化規則。當然也可以添加自己的規則到calcite中。

例如，Calcite提供了Cassandra適配器。Cassandra有以下特點：數據根據部分欄位分區，且在每個分區中，行是根據另一部分欄位排過序的。對適配器來說，下推盡量多的查詢到backend中是非常好的查詢優化。下推sort到cassandra的規則必須符合兩個條件：

1） 對錶的查詢過濾後只會到一個分區中（因為行在一個分區中是有序的）

2） Cassandra的分區排序和要求的排序有相同的前綴

若要符合這兩個條件，需要把logicalFilter重寫為cassandraFilter以實現分區filter 下推到cassandra。

再比如如下更複雜的查詢：

SELECT products.name, COUNT(*)FROM sales JOIN products USING (productId) WHERE sales.discount IS NOT NULLGROUP BY products.name ORDER BY COUNT(*) DESC;

這個查詢對應的關係代數表達式可以用下圖中的左半部分表示：

因為where子句僅僅用於sales表，我們可以把filter挪到join之前如右半部分圖所示。這個優化可以大幅減少執行時間。另外，如果這兩張表不在同一個backend中，這個優化能使適配器把filter下推到backend中。這個優化就是calcite的FilterIntoJoinRule。

5.2 元數據提供者

元數據有兩個重要作用：一是指導規劃器降低整個查詢計劃的成本，二是提供資訊給rules。元數據提供者負責提供這些資訊給優化器。實際上，calcite的默認的元數據提供者實現包括這些功能：執行運算符樹的子表達式的全部成本，行數，表達式的結果集的數據量，最大並行度。它還能提供plan結構資訊，例如某個tree node下面有個filter condition。

Calcite提供了元數據plugin介面。數據處理引擎可以選擇重寫providers中已經存在的函數，或者提供他們新的元數據函數。在大多數情況下，數據處理引擎通過元數據提供者介面提供數據的統計數據（如行數數據量）就已經足夠了，剩下的工作calcite通過它的默認實現就可以完成。

元數據提供者是可插拔的，他們通過一個java輕量級編譯器Janino來編譯和運行時實例化。元數據提供者的實現包括元數據結果的cache,這個cache能很大幅度提高性能。

5.3 規劃器引擎

規劃器引擎的主要功能是觸發優化規則一直進行優化直到達到給定的目標。目前calcite提供兩種不同的規劃器引擎，新的引擎是可插拔的。

第一種是基於成本的規劃引擎。它的規則的目標是減少整個表達式的成本。這個引擎使用動態編程演算法，類似於Volcano。最初，每個表達式帶著基於表達式的摘要以及輸入註冊到規劃器。當一個規則在表達式e1上觸發後，會產生表達式e2.規劃器會把e2添加到e1所在的相等表達式集合Sa中。同時，規劃器產生新表達式的摘要，這個摘要會和以前註冊到規劃器的摘要進行比較。如果一個相似的摘要（表達式e3的摘要）在Sb中發現，規劃器發現了重複將會把Sa和Sb合併。這個過程會一直持續到規劃器達到一個配置的固定點。規劃器將窮舉搜索空間直到所有的規則在所有的表達式上都應用過。或者當規劃的成本在上個迭代中的改進小於某閾值時也會停止優化。元數據提供者需要提供cost函數，這個cost函數會被優化器用來決策哪個plan會被選擇。默認的cost 函數會根據一個給定的表達式綜合考慮CPU IO 以及記憶體資源。

第二個引擎是窮舉式規劃器。它會一直觸發規則直到它產生的表達式不再被任何規則所改變。這個規劃器在不考慮表達式成本的場景下是有用的，它可以快速執行規則。

用戶可以根據自己的需求選擇規劃器引擎，也可以從一種引擎切換到另一種。或者，用戶也可以產生多階段優化邏輯，即在不同的階段使用不同的規則集。

總結

本文主要描述的Calcite的架構以及基本原理，並簡單介紹了Calcite的主要模組。Calcite的內容很多，後面還需要更深入的研究。