Categories
程式開發

數據庫內核雜談(九):開源優化器ORCA


前兩期文章介紹了數據庫優化器的一些技術細節。這篇文章,我們通過介紹一款真實的,開源的,已經搭載在生產環境中的數據庫優化器ORCA,帶大家從工程實踐的角度來了解數據庫優化器,也算是對優化器內容的一個小結。

今天介紹的內容主要來自於2014年SIGMOD的ORCA paper (本人也是作者之一,沾沾自喜一波)。 ORCA是Pivotal(原Greenplum)公司構建的。

Github link是:https://github.com/greenplum-db/gporca

注:本期內容中英文結合比較多,因為有些詞彙我實在是不知道如何翻譯,請各位讀者見諒。

ORCA的誕生

ORCA項目大致立項於2011-2012年(因為12年我正好去Pivotal實習,當時ORCA項目應該是剛開始沒多久)。

那個時候,大數據風口才起來。 Hadoop,HDFS等詞也開始頻頻出現。 Cloudera作為第一個以Hadoop-based的大數據公司逐漸嶄露頭角。我想, Pivotal開始準備花精力來重新研發一款優化器,也是瞄準了這個風口;由於數據量爆炸式地增長,原有的優化器對於海量數據的處理已經捉襟見肘。但同時,客戶對於運行複雜的分析語句的需求卻越來越高:不僅希望可以支持更複雜,更龐大的數據處理,甚至希望時間上能更快。當時Pivotal旗下是有兩款大數據產品:

1)Greenplum Database(GPDB)是一款基於開源PostgreSQL擴展的MPP(massively parallel processing),可支持大規模水平擴展的分佈式數據庫。 GPDB採用的是master-worker模式,每個worker process運行在不同的機器上,擁有各自的存儲和運算資源。客戶端通過master把查詢語句分發到各個機器上,以達到並行計算來處理海量數據。

數據庫內核雜談(九):開源優化器ORCA 1

上圖展示了GPDB的架構圖。 Master節點管理所有的worker節點,worker節點負責存儲和處理數據,所有這些節點構成一個邏輯數據庫。用戶只和Master節點交互來發送SQL語句:當用戶提交查詢語句給master節點後,master會根據數據分佈進行優化,把最終的執行計劃發給各個worker執行,執行的過程中各個worker之間也會有數據交互。最終結果會返回給master再返回給客戶。

2) HAWQ針對Hadoop存儲的SQL執行引擎。 HAWQ通過數據接口可以直接讀取Hive表裡的數據(也支持原生存儲格式),然後用SQL執行引擎來計算得到查詢結果。與HiveQL通過把SQL解析成一連串的MapReduce job的執行模式相比,速度要快好幾個量級。 HAWQ雖然在開發執行引擎過程中藉鑑了很多GPDB的東西,但畢竟是一款不同的數據庫引擎,Pivotal因此希望有一款兼容的優化器能夠服務於它。

另一方面,雖然關於優化器的研究一直在進行,但是大部分的工作都是對於原始優化器的修修補補,低垂的果實也摘得差不多了。如果還要強行在原先的優化器上加入新的功能,就有點事倍功半了。

基於上述這些原因,Pivotal決定開發一款新的,最先進的優化器ORCA。

ORCA的架構

在ORCA構建的伊始,就制定瞭如下這些目標:

1)模塊化:開發的第一天起,ORCA就完全以一個獨立的模塊進行開發。所有的數據輸入和輸出都接口化。這也是為了能夠讓ORCA能夠兼容不同的數據庫產品。

2)高延展性:算子類,優化規則(transformation rule),數據類型類都支持擴展,使得ORCA可以不斷迭代。方便更高效地加入新的優化規則。

3)高並發優化:ORCA內部實現了可以利用多核並發的調度器來進一步提高對複雜語句的優化效率。

4) 可驗證和測試性: 在構建ORCA的同時,為了ORCA的可驗證性和可測試性,同時構建了一批測試和驗證工具,確保ORCA一直在正確的道路上迭代。

絕大部分的優化器都是緊耦合與數據庫系統的。簡單來說,就是代碼耦合度高。比如共享數據結構,可以直接調用內部方法等。而ORCA為了能夠適配不同的數據庫引擎,一大特點就是把自己做成了一個完全獨立運行於數據庫系統之外的程序。做個類比,可以把ORCA想像成一個微服務,獨立運行,只能通過暴露的RESTAPI進行交互。 DXL(Data eXchange Language)就是ORCA暴露出的接口: DXL定制了一套基於XML語言的數據交互接口。這些數據包括:用戶輸入的查詢語句,優化器輸出的執行計劃,數據庫的元數據及數據分佈等。

數據庫內核雜談(九):開源優化器ORCA 2

上圖給出了ORCA通過DXL與數據庫系統交互的示例:數據庫輸入DXL Query和DXL Metadata,然後ORCA返回DXL plan。任何數據庫系統只要實現DXL接口,理論上都可以使用ORCA進行查詢優化。 DXL接口的另一個好處就在於,大幅度簡化了優化器的測試,驗證bug修復的難度。只需要通過DXL輸入mock(假數據)數據,就可以讓ORCA進行優化並輸出執行結果,而不需要真正搭建一個實體數據庫來操作。舉個例子,比如傳統情況下要測試TPC-DS中的一個語句優化在100TB流量20個服務器下的表現,就需要搭建一個20個服務器的環境外加把100TB的數據導入進行測試。這樣的測試成本無疑是很高的。但如果測試ORCA,只需要通過DXL來mock一個測試環境,讓ORCA給出相應的優化結果即可,甚至都不用啟動數據庫就能進行測試。在後續的工具章節會詳細介紹。

看完了ORCA的交互機制,我們通過ORCA的架構圖來詳解它的架構機制。

數據庫內核雜談(九):開源優化器ORCA 3

ORCA的架構分成幾大塊:

1)Memo

用來存儲執行計劃的搜索空間的叫Memo。 Memo就是一個非常高效的存儲搜索空間的數據結構。它有一系列的集合(group)構成。每個group代表了執行計劃的一個子表達式(想對應與查詢語句的一個子表達式)。不同的group又產生相互依賴的關係。根group就代表整個查詢語句。舉個例子,假設語句是 ***selct * from table1 join table2 on (table1.col1 = table2.col1) ***

那memo就由3個group構成。根group就是join。 Group1是table scan of table1, group2是table scan of table2. 每個group除了表達抽象的語句表達式,在優化過程中,還會加入具體的物理算子。我們暫且不深入,到後面再細說。

2)Search&Job scheduler

ORCA實現了一套算法來掃描Memo併計算得到預估代價最小的執行計劃。搜索由job scheduler來調度和分配,調度會生成相應的有依賴關係或者可並行的搜索子工作。

這些工作主要分成三步,一是exploration,探索和補全計劃空間,就是根據優化規則不斷生成語義相同的邏輯表達式。舉個例子,select * from a, b where a.c1 = b.c2 可以生成兩個語義相同的邏輯表達式: a join b**b join a。第二步是implementation,就是實例化邏輯表達式變成物理算子。比如, *a join b *可以變成 a hash_join b 或者 a merge_join b。第三步是優化,把計劃的必要條件都加上,比如某些算子需要input被排過序,數據需要被重新分配,等等。然後對不同的執行計劃進行算分,來計算最終預估代價。

3)Transformations

Plan transformation就是剛才優化中第一步exploration的詳解,如何通過優化規則來補全計劃空間。舉個例子,下面就是一則優化規則 *InnerJoin(A,B) -> InnerJoin(B,A)*。這些transformation的條件通過觸發將新的表達式,存放到Memo中的同一個group裡。

4)Property enforcement

在優化過程中,有些算子的實現需要一些先決條件。比如,sortGroupBy需要input是排序過的。這時候就需要enforce order這個property。加入了這個property,ORCA在優化的過程中就會要求子節點能滿足這個要求。比如要讓子節點滿足這個sort order property,一個可能的方法是對其進行排序,或者,有些子節點的算子可以直接滿足條件,比如index scan。

5)Metadata Cache

數據庫中表的元數據(column類型)等變動不會太大,因此Orca把表的元數據緩存在內存用來減少傳輸成本,只有當元數據發生改變時(metadata version改變時),再請求獲取最新的元數據。

6)GPOS

為了可以運行在不同操作系統上,ORCA也實現了一套OS系統的API用來適配不同的操作系統包括內存管理,並發控制,異常處理和文件IO等等。

優化過程詳解

這一章節,我們通過一個具體的示例來看ORCA是如何對SQL語句進行優化的。語句是:

數據庫內核雜談(九):開源優化器ORCA 4

考慮到分佈式數據庫,我們假定T1的數據分佈是按照T1.a的hash後分配到不同的node上, 而T2的數據分佈是根據T2.a進行分配。

數據庫內核雜談(九):開源優化器ORCA 5

上圖給出了以DXL形式傳給ORCA的SQL語句。首先,可以看出,XMLbased的形式確實是比較繁瑣的。 DXL中定義了輸出column:除了給出了output name,也給出了metadataID信息。同時也給出了需要排序的column。 Metadata(表和操作符都被添加了相應的metadataID), ORCA可以通過這些ID,快速從Metadata Cache中定位信息。同時metadata中有version信息,用來確認是否需要更新metadata。

DXL語句傳送到ORCA後,以多組邏輯表達式的的形式存放到Memo中。

數據庫內核雜談(九):開源優化器ORCA 6

上圖展現了Memo中存入的邏輯表達式group:分為3個group:2個table scan,1個inner_join。 Group 0是root group。因為它就是整個邏輯語法樹的根節點。我們通過邊來表示group之間的依賴關係。 InnerJoin(1, 2)代表了group1和group2是它的子group。得到初始化的Memo後,下面進入具體的優化階段:

1)exploration

根據現有的優化規則(transformation rule)來生成語義相同的邏輯表達式。比如, 通過join commutatitivty規則,可以從innerjoin(1,2)生成innerjoin(2,1)。

2)cardinality estimation (statistics derivation)

Cardinality estimation在之前的文章中介紹過,用來估算每一個SQL節點的輸入和輸出量。每一組邏輯表達式其實是一個SQL節點的一部分,舉個例子,scan of table1 估計出有多少行數據被輸出。 ORCA內部用column histogram來預估cardinality和可能的數據分佈情況。具體的算法上一篇也介紹過一二,這邊就不再贅述了。 Cardinality estimation是自底向上進行,也就是先從葉group開始,最後至根節點。下圖給出了示例。

數據庫內核雜談(九):開源優化器ORCA 7

首先,從根節點自上而下來請求statistics, Group0會向子group發送請求來得到statistics。舉例來說, InnerJoin(T1, T2) on (T1.a = T2.b) 會分別像子group請求T1.a和T2.b的histogram。表的元數據會緩存的MDCache中,如果不存在,Orca會發起MD調用來像數據庫系統獲取最新的metadata。

3)Implementation 邏輯到物理的轉換

第三部開始實施從邏輯表達式到物理算子的轉換。舉個例子,local table_scan可以轉換成物理的sequentialScan,或者BtreeIndexScan。 InnerJoin(T1, T2) 可以轉換成IndexInnerjoin(T1, T2), 或者MergeJoin(T1, T2) 等等。

4)優化

在優化這一步中,會首先進行property enforcement,然後不同的物理執行計劃被計算出預估代價Cost。這就是之前介紹過的Cost Model Calibration。每個對應的物理算子會有一個cost formula,配合上cardinality estimation計算出來的輸入和輸出,就可以算出相應的cost。整個過程是首先發送一個優化請求給根group。這個優化請求一般會有結果的分佈或者結果的排序的條件,同時它要求獲取當前group裡Cost最小的執行計劃。

對於優化請求,每一組物理算子會先計算自身的那一部分cost。同時把請求發送給子算子,這和statistics derivation的模式是一樣的。對於一個物理算子組來說,可能在整個優化過程中接受到重複的優化請求,ORCA會把這些請求cache起來去重,用來確保對相同請求,只計算一次。

具體如何發送優化請求,如何計算cost,如何分發子請求,請允許作者省略幾千字。倒不是我不想細寫。寫了這一段,有興趣讀下來的讀者也是絕少數,反而倒是消磨了廣大讀者繼續讀下去的意願。考慮再三,為了不引起反感,我還是不瞎忙活了。 如果讀者真的感興趣,可以參考原論文,或者在文章下面留言,我們可以繼續交流。

5)執行

優化完成以後,ORCA會通過DXL把執行計劃發回給數據庫,數據庫可以根據執行計劃,分配給每個worker。每個worker在執行計算的同時,會通過distribution operator把數據分發到其他node上繼續執行。最終所有計算結果會匯聚到master node返回給用戶。

並行優化

執行優化可能是最消耗CPU資源的過程。更高效地執行優化過程來產生高效的執行計劃可以大幅度提升整個數據庫的性能。考慮到現在服務器的多核配置,如何利用多核資源來加速優化過程是ORCA的另一個重要的特性。 ORCA的job scheduler配合GPOS就可以利用多核進行並行優化。在前面的章節提到過,整個優化過程其實是被分發到每個物理算子組中進行,每個組在執行優化的過程中,根據依賴關係,可以並行進行。現在ORCA的優化任務有下面幾類:

1)給定一個邏輯表達式,根據變換規則生成所有語義相同的邏輯表達式

2)給定一個邏輯表達式,根據變換規則生成所有物理算子

3)對某個表達式組作用某個變換規則

4)優化某一個表達式或者一個物理算子組

因此,對與一個語句,ORCA會產生幾百甚至上千個優化子任務。這些任務之間是有依賴關係的。舉例來說,一個group必須等到它的所有子節點被優化完成後才能進行優化。這裡就需要job scheduler來協調子任務的優化過程。 job scheduler會根據優化任務的依賴關係,來決定先優化哪些任務。

下圖給出了一個優化子任務的依賴關係示例。

數據庫內核雜談(九):開源優化器ORCA 8

元數據獲取

ORCA一大特性就可以獨立於數據庫系統運行。元數據獲取就是ORCA和數據庫系統一個重要的交互。在優化中,ORCA需要知道表的數據分佈,對於column的histogram,或者對於某個column是否有index等的信息。下圖展示了ORCA是如何與不同的數據庫獲取元數據信息。

數據庫內核雜談(九):開源優化器ORCA 9

在優化過程中,所有的元數據信息會被cache在ORCA中。優化過程中,ORCA通過MDAccessor來獲取所有的元數據。 MDProvider除了plug-in到其他系統,也提供了文件形式導入metadata。這就使得測試ORCA變得非常容易:我們可以單獨運行ORCA程序,通過文件形式提供metadata和SQL語句來獲取ORCA的執行計劃來測試。

測試和驗證

測試和驗證一個優化器的難度不亞於實現一個優化器。在實現ORCA的初期,測試和驗證需求就被放在了第一位。拜DXL接口和文件形式的MD provider所賜,我們可以很容易地添加回歸測試用例來確保在迭代feature的過程中,不引入bug。本文我們會介紹兩個ORCA構建中比較特別的工具。

AMPERe

AMPEre是一款用來重現和調試bug的工具,類似於core dump。當出現問題時,可能是優化器crash了,或者是生成的執行計劃非常慢。 AMPERe可以把當前的整個狀態復制下來,用作复盤和調試。整個狀態包括要優化的語句,優化器的當前配置,數據庫的元數據,如果是崩潰了,還會有stack trace等信息。這些信息以DXL的形式被保存到文件中。工程師可以讀取這些這些數據來調試。更重要的是,我們可以通過把語句,元數據以DXL的形式導入到patch了fix的新版本ORCA中,用來測試原有的問題是否被修復,比如不再crash,或者ORCA生成了一個新的執行計劃,等等。

下圖展示了這樣一個過程。

數據庫內核雜談(九):開源優化器ORCA 10

AMPERe同時也是ORCA testing framework中重要的一部分,我們可以用AMPERe記錄很多已知的客戶遇到過的真實問題並把它們做成回歸測試用例。每次有新版本更新的時候都可以用這些用例來做回歸測試。

測試優化器的準確性

哈!終於講到這了。我小小地驕傲一下,這是我當時在Pivotal實習的項目。用來測試Optimizer生成的執行是否優秀。 Testing Accuracy of Query Optimizer, 所以工具的名字叫TAQO

TAQO的想法很簡單,對於某個SQL語句,如何判斷一個優化器作出了正確的選擇呢。

假定優化器生成了3個執行計劃,分別是P1, P2, P3。然後對應的cost是C1, C2,和C3,並假設C1

在測試過程中,對於一個測試語句,TAQO讓ORCA生成不同的執行計劃,然後再執行這些計劃得到相應的運行時間。最後計算運行時間和預估Cost的相關值。相關值越高,則說明越準確。

同樣,我們可以用TAQO為ORCA做回歸測試。比如,運行當前版本對應TPC-DS語句併計算TAQO值。有了新版本後,再運行一下TAQO來計算新值。確保所有語句的TAQO值沒有下跌。如果有下跌,就可以第一時間發現是否這個版本引入了某些修改導致了ORCA在優化中翻了一些錯誤。

總結

後續還有測試結果的比較,這邊就不贅述了。我們當時比較了Cloudera的Impala,Hontonworks的Stinger,和當時Facebook剛推出的Presto。結果當然是ORCA要更好一些,畢竟,好多競品也才出現,很多功能還不夠完善,很多SQL語法也還支持得不好。

至此,文章的主要內容就介紹到這。可見,除了我們前兩篇介紹到的技術,實踐中構建一個優化器是一個非常龐大和復雜的工程。

說些題外話,後來作者雖然離開了Pivotal,和原來的這些同事關係都很好。 QueryProcessing組的成員陸陸續續後面都離開了,一半加入了初創公司Datometry(我就在這一半中),參與數據庫虛擬化系統的開發。另一半加入了AWS,參與Redshift的開發,大家還是依然活躍在數據庫領域方面。現在作者並不直接參與數據庫系統開發啦。但還是時刻保持關注,讀讀paper,有機會也去參加參加會議,寫點blog,也算間接對數據庫領域做些貢獻吧。

作者介紹:

顧仲賢,現任Facebook Tech Lead,專注於數據庫,分佈式系統,數據密集型應用後端架構與開發。擁有多年分佈式數據庫內核開發經驗,發表數十篇數據庫頂級期刊併申請獲得多項專利,對搜索,即時通訊系統有深刻理解,愛設計愛架構,持續跟進互聯網前沿技術。

2008年畢業於上海交大軟件學院,2012年,獲得美國加州大學戴維斯計算機碩士,博士學位;2013-2014年任Pivotal數據庫核心研發團隊資深工程師,開發開源數據庫優化器Orca;2016年作為初創員工加入Datometry,任首席工程師,負責全球首家數據庫虛擬化平台開發;2017年至今就職於Facebook任Tech Lead,領導重構搜索相關後端服務及數據管道, 管理即時通訊軟件WhatsApp數據平台負責數據收集,整理,並提供後續應用。

相關閱讀:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫

數據庫內核雜談(二):存儲“演化論”

數據庫內核雜談(三):索引優化

數據庫內核雜談(四):執行模式

數據庫內核雜談(五):如何實現排序和聚合

數據庫內核雜談(六):表的 JOIN(連接)

數據庫內核雜談(七):數據庫優化器(上)

數據庫內核雜談(八):數據庫優化器(下)