Orca的架構是怎么樣的

這篇文章主要介紹Orca的架構是怎么樣的，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

大數據系統的流行引起了人們對查詢優化的新興趣，因為新型的數據管理系統在前所未有的可擴展性，可用性和處理能力方面取得了突破，通過SQL或類似SQL的接口，可以輕松訪問數百TB甚至PB的大型數據集進行分析。優秀的和平庸的優化器之間的差異一直是眾所周知的[。但是，這些系統必須處理的數據量越來越大，從而加劇了優化錯誤，并比以往任何時候都需要強調查詢優化的重要性。

好的查詢優化器在架構設計上需要考慮以下的幾個方面：

• 模塊化。使用元數據和系統描述的高度可擴展的抽象，不再局限于特定的主機系統，如傳統的優化器。相反，可以通過數據支持的插件將其快速移植到其他數據管理系統。

• 可擴展性。通過將查詢及其優化的所有元素表示為具有同等地位的一等公民，避免多階段優化的陷阱，在此階段，某些優化將在事后進行處理。眾所周知，多階段優化器難以擴展，因為新的優化或查詢構造通常與先前設置的階段邊界不匹配。

• 支持多核架構。 系統需要部署一個高效的多核感知調度程序，該調度程序可在多個內核之間分配各個細粒度的優化子任務，以加快優化過程。

• 可驗證性。有確定的特殊規定內置機制級別來保證正確性和性能。除了改善工程實踐之外，這些工具還使人們能夠高度自信地進行快速開發，并縮短了新功能和錯誤修復的周轉時間。

• 性能。 查詢的性能是我們最希望等到的結果

一、MPP架構

Orca是Pivatol開發的大數據模塊化查詢優化器，被用于Greemplum和Hawq之中。他就是按照上面的要求來設計的。

上圖是Greemplum的體系架構，通過在多個服務器或主機之間分配負載以創建單個數據庫陣列來處理大量數據的存儲和處理，所有這些數據庫共同工作以呈現單個數據庫入口。  主節點是GPDB的入口點，客戶端可以在此連接并提交SQL語句。 主節點與其他數據庫實例(稱為段)協同工作，以處理數據處理和存儲。  當查詢提交給主節點時，將對其進行優化并將其分解為較小的查詢，這些較小的查詢將被分配給各部分，以共同協作以交付最終結果。  互連使用標準的千兆以太網交換結構，負責各段之間的進程間通信的聯網層。

在查詢執行期間，可以通過多種方式將數據分布到段，包括散列分布，其中元組根據某種哈希函數分布到段，復制分布，其中表的完整副本存儲在每個段和單例分布，其中整個分布式表從多個段收集到單個主機(通常是主節點)。

二、SQL on Hadoop 架構

在Hadoop上處理分析查詢正變得越來越流行。最初，查詢表示為MapReduce工作和Hadoop的吸引力在于其可擴展性和容錯能力。編碼，手動優化和維護MapReduce中的復雜查詢非常困難，因此像類似SQL的聲明性語言是在Hadoop之上開發的。  HiveQL查詢被編譯到MapReduce作業中，并由Hadoop執行。  HiveQL加快了復雜查詢的編碼速度，但同時也很明顯地表明，Hadoop生態系統，因為已編譯的MapReduce作業顯示了較差的性能。

Pivotal通過引入HAWQ 來應對挑戰，它是一種在HDFS之上的大規模并行SQL兼容引擎。  HAWQ以Orca為核心來設計有效的查詢計劃，從而最大程度地降低訪問Hadoop集群中數據的成本。  HAWQ的體系結構將創新的基于成本的最先進的優化器與Hadoop的可伸縮性和容錯能力相結合，以實現PB級數據的交互式處理。

最近，包括Cloudera的Impala和Facebook的Presto在內的許多其他努力引入了新的優化器，以在Hadoop上應用SQL處理。當前，這些工作僅支持SQL標準功能的一部分，并且其優化僅限于基于規則的。相比之下，HAWQ具有完全符合標準的SQL接口和基于成本的優化器，這兩者都是Hadoop查詢引擎中前所未有的功能。

三、Orca的架構

Orca是Pivotal研發的數據管理產品(包括GPDB和HAWQ)的新查詢優化器。 Orca是基于Cascades優化框架的現代的自上而下的查詢優化器。  盡管許多Cascades優化器與主機系統緊密耦合，但是Orca的獨特功能是它能夠作為獨立的優化器在數據庫系統之外運行。  此功能對于使用一個優化程序支持具有不同計算架構(例如MPP和Hadoop)的產品至關重要。

1. DXL

將優化器與數據庫系統分離，需要建立一種通信機制來處理查詢。 Orca包括一個用于在優化器和數據庫系統之間交換信息的框架，稱為數據交換語言(DXL)。  該框架使用基于XML的語言對通信所需的信息進行編碼，例如輸入查詢，輸出計劃和元數據。  覆蓋在DXL上的是一種簡單的通信協議，用于發送初始查詢結構并檢索優化的計劃。 DXL的主要優點是將Orca包裝為獨立產品。

Orca的輸入是DXL查詢，Orca的輸出是DXL計劃。在優化期間，可以查詢數據庫系統以獲取元數據(例如，表定義)。  Orca通過允許數據庫系統注冊元數據提供程序(MD  Provider)來抽象化元數據訪問詳細信息，該數據提供程序負責將元數據序列化為DXL，然后再發送給Orca。還可以從包含以DXL格式序列化的元數據對象的常規文件中使用元數據。

數據庫系統需要包括使用/發送DXL格式數據的轉換器。  Query2DXL轉換器將查詢分析樹轉換為DXL查詢，而DXL2Plan轉換器將DXL計劃轉換為可執行計劃。此類轉換器的實現完全在Orca之外完成，這允許多個系統通過提供適當的轉換器來使用Orca。  Orca的體系結構具有高度的可擴展性。所有組件均可單獨更換并單獨配置。

2. Orca的不同組件包

(1) Memo

由優化器生成的計劃替代方案的空間被編碼在稱為Memo 的緊湊型內存數據結構中。 Memo結構由一組稱為組的容器組成，其中每個組包含邏輯上等效的表達式。  Memo組捕獲查詢的不同子目標(例如，表上的過濾器或兩個表的聯接)。 稱為組表達式的組成員以不同的邏輯方式(例如，不同的連接順序)實現組目標。  每個組表達式都是一個運算符，具有其他組作為其子級。 Memo的這種遞歸結構允許對可能的計劃的巨大空間進行緊湊的編碼。

(2) 搜索和作業計劃程序

Orca使用搜索機制在可能的計劃替代方案的空間中導航，并以最低的估計成本確定計劃。 搜索機制由專門的Job Scheduler啟用，該Job  Scheduler通過以下三個主要步驟來創建依賴或并行工作單元以執行查詢優化：探索(在其中生成等效的邏輯表達式)，實現(在其中生成物理計劃)和優化(在所需的物理屬性中，例如，排序順序)，并計劃替代方案的成本。

(3) 變形

通過應用可以產生等效邏輯表達式(例如，InnerJoin(A，B)→InnerJoin(B，A))或現有表達式的物理實現(例如，Join(A，B)的轉換規則，可以生成計劃替代方案  )→HashJoin(A，B))。 應用轉換規則的結果將復制到Memo中，這可能會導致創建新組和/或向現有組添加新的組表達式。  每個轉換規則都是一個獨立的組件，可以在Orca配置中顯式激活/禁用它。

(4) 屬性強制

Orca包括一個可擴展的框架，用于根據正式的屬性規范描述查詢要求和計劃特征。  屬性具有不同的類型，包括邏輯屬性(例如，輸出列)，物理屬性(例如，排序順序和數據分布)和標量屬性(例如，連接條件中使用的列)。  在查詢優化期間，每個運算符都可以從其子級請求特定的屬性。  優化的子計劃可能自己滿足所需的屬性(例如，IndexScan計劃提供排序的數據)，或者需要在計劃中插入強制程序(例如，Sort運算符)以交付所需的屬性。  該框架允許每個操作符根據子計劃的屬性和操作符的本地行為來控制執行的位置。

(5) 元數據緩存

由于元數據(例如，表定義)很少更改，因此在每次查詢時都將其傳送會產生開銷。  Orca在優化器端緩存元數據，并且僅當緩存中不可用或自上次將其加載到緩存以來發生更改時才從目錄中檢索元數據。  元數據緩存還從優化器中提取數據庫系統詳細信息，這在測試和調試期間特別有用。

(6) GPOS

為了與可能具有不同API的操作系統進行交互，Orca使用了稱為GPOS的OS抽象層。  GPOS層為Orca提供了廣泛的基礎架構，包括內存管理器，用于并發控制，異常處理，文件I / O和同步數據結構的原語。

四、查詢優化

1. 工作流

我們使用下面的查詢來解釋查詢優化的流程：

SELECT T1.a FROM T1, T2 WHERE T1.a = T2.b ORDER BY T1.a;

其中T1的分布為Hashed(T1.a)，而T2的分布為Hashed(T2.a)。

下面的XML顯示了DXL中上一個查詢的表示形式，其中我們提供了所需的輸出列，排序列，數據分布和邏輯查詢。元數據(例如表格和運算符定義)都裝飾有元數據ID(Mdid)，以允許在優化過程中請求更多信息。  Mdid是由數據庫系統標識符，對象標識符和版本號組成的唯一標識符。例如，“ 0.96.1.0”是指GPDB版本為“  1.0”的整數相等運算符。元數據版本用于使已跨查詢進行修改的緩存元數據對象無效。

<? xml version =" 1.0 " encoding =" UTF -8 "? > < dxl:DXLMessage xmlns:dxl =" http: // greenplum . com / dxl / v1 " >   < dxl:Query >     < dxl:OutputColumns >         < dxl:Ident ColId ="0" Name ="a" Mdid =" 0.23.1.0 "/ >     </ dxl:OutputColumns >     < dxl:SortingColumnList >         < dxl:SortingColumn ColId ="0" OpMdid =" 0.97.1.0 " >     </ dxl:SortingColumnList >     < dxl:Distribution Type =" Singleton " / >     < dxl:LogicalJoin JoinType =" Inner " >       < dxl:LogicalGet >         < dxl:TableDescriptor Mdid =" 0.1639448.1.1 " Name =" T1 " >           < dxl:Columns >             < dxl:Ident ColId ="0" Name ="a" Mdid =" 0.23.1.0 "/ >             < dxl:Ident ColId ="1" Name ="b" Mdid =" 0.23.1.0 "/ >           </ dxl:Columns >         </ dxl:TableDescriptor >       </ dxl:LogicalGet >     < dxl:LogicalGet >       < dxl:TableDescriptor Mdid =" 0.2868145.1.1 " Name =" T2 " >         < dxl:Columns >             < dxl:Ident ColId ="2" Name ="a" Mdid =" 0.23.1.0 "/ >             < dxl:Ident ColId ="3" Name ="b" Mdid =" 0.23.1.0 "/ >         </ dxl:Columns >       </ dxl:TableDescriptor >     </ dxl:LogicalGet >       < dxl:Comparison Operator ="=" Mdid =" 0.96.1.0 " >         < dxl:Ident ColId ="0" Name ="a" Mdid =" 0.23.1.0 "/ >         < dxl:Ident ColId ="3" Name ="b" Mdid =" 0.23.1.0 "/ >       </ dxl:Comparison >     </ dxl:LogicalJoin >   </ dxl:Query > </ dxl:DXLMessage >

DXL查詢消息被傳送到Orca，在該消息中被解析并轉換為內存中邏輯表達式樹，該樹被復制到備忘錄中。下圖顯示了備忘錄的初始內容。邏輯表達式為兩個表和InnerJoin操作創建三個組。為了簡潔起見，我們省略了加入條件。組0稱為根組，因為它對應于邏輯組的根表達。邏輯表達式中運算符之間的依賴關系被捕獲為組之間的引用。例如，InnerJoin  [1,2]將組1和組2稱為子級。如以下步驟所述進行優化。

(1)探索。 觸發生成邏輯等效表達式的轉換規則。 例如，將觸發一個Join Commutativity規則，以從InnerJoin  [1,2]中生成InnerJoin [2,1]。 探索的結果是將新的組表達式添加到現有組中，并可能創建新的組。  Memo結構具有基于表達式拓撲的內置重復檢測機制，以檢測和消除由不同轉換創建的任何重復表達式。

(2)統計推導。在探索結束時，備忘錄Memo將維護給定查詢的完整邏輯空間。然后觸發Orca的統計信息派生機制，以計算Memo組的統計信息。  Orca中的統計對象主要是列直方圖的集合，用于得出基數和數據偏斜的估計值。統計信息是在緊湊的Memo結構上進行的，以避免擴展搜索空間。

為了導出目標組的統計信息，Orca會選擇最有希望提供可靠統計信息的組表達式。統計承諾計算是特定于表達式的。例如，具有少量聯接條件的InnerJoin表達式比具有大量聯接條件的另一個等效的InnerJoin表達式更有希望(這種情況可能在生成多個聯接順序時出現)。基本原理是，加入條件的數量越多，估計誤差的傳播和放大機會就越大。由于需要在給定表達式的所有節點之間匯總置信度分數，因此計算基數估計的置信度分數具有挑戰性。我們目前正在探索幾種在緊湊的備忘錄Memo結構中計算置信度得分的方法。

在選擇了目標組中最有希望的組表達式之后，Orca遞歸地觸發對所選擇的組表達式的子組進行統計推導。最后，通過組合子組的統計對象來構造目標組的統計對象。  下圖說明了正在運行的示例的統計信息派生機制。首先，執行一個自上而下的傳遞，其中父組表達式從其子組中請求統計信息。例如，(a =  b)上的InnerJoin(T1，T2)請求T1.a和T2.b上的直方圖。通過注冊的MD提供程序按需從目錄中加載請求的直方圖，將其解析為DXL并存儲在MD緩存中以為將來的請求提供服務。接下來，執行自下而上的遍歷以將子統計對象合并為父統計對象。由于連接條件可能會影響列的直方圖，因此會在列T1.a和T2.b上生成(可能已修改)直方圖。

Statistics derivation mechanism

構造的統計對象附加到各個組，在優化過程中可以在其中進行增量更新(例如，通過添加新的直方圖)。 這對于保持統計數據衍生成本的可管理性至關重要。

(3)實現。 觸發創建邏輯表達式的物理實現的轉換規則。 例如，觸發Get2Scan規則以從邏輯Get中生成物理表Scan。  類似地，觸發InnerJoin2HashJoin和InnerJoin2NLJoin規則以生成哈希和嵌套循環聯接實現。

(4)優化。 在此步驟中，將強制實施屬性，并為替代方案進行成本估算。 優化開始于向Memo的根組提交初始優化請求，以指定查詢要求，例如結果分配和排序順序。  向組g提交請求r對應于向g中的根物理運算符請求滿足r的最低成本計劃。

上圖顯示了備忘錄中針對正在運行的示例的優化請求。 初始優化請求為req。  #1：{Singleton，}，它指定需要根據T1.a給出的順序將查詢結果收集到主數據庫。  我們還顯示了組哈希表，其中每個請求都與以最低估計成本滿足它的最佳組表達式(GExpr)相關聯。  黑框表示插入到備忘錄中的執行程序操作符，用于傳遞排序順序和數據分發。 聚集運算符將所有段中的元組收集到主數據庫。  GatherMerge運算符將所有段中的排序數據收集到主數據庫，同時保持排序順序。 重新分配運算符根據給定參數的哈希值跨段分配元組。

上圖圖顯示了req的優化。 #1 by Inner-HashJoin [1,2]。  對于此請求，替代方案之一是根據聯接條件對齊子分布，以便將要聯接的元組放置在同一位置。  這是通過請求第1組的Hashed(T1.a)分布和第2組的Hashed(T2.b)分布來實現的。兩個組均被要求傳遞任何排序順序。  找到最佳子計劃后，InnerHashJoin會合并子屬性，以確定已交付的分發和排序順序。  請注意，組2的最佳計劃需要在T2.b上哈希分布T2，因為T2最初是散列在T2.a上，而組1的最佳計劃是簡單掃描，因為T1已經散列在T1.a.

2. 查詢執行

最終計劃的副本將分發到每個細分分段。 在分布式查詢執行期間，每個段上的分布式強制執行器既充當數據的發送者，又充當數據的接收者。  例如，在段S上運行的Redistribute(T2.b)實例基于T2.b的哈希值將S上的元組發送到其他段，并且還從其他段上的其他Redistribute(T2.b)實例接收元組。

五、并行查詢優化

查詢優化可能是數據庫系統中最占用CPU的過程。 有效使用CPU可以轉化為更好的查詢計劃，從而提高系統性能。  并行查詢優化器對于受益于利用越來越多的內核的高級CPU設計至關重要。

Orca是啟用了多核的優化器。 優化過程被分解為稱為優化任務的小型工作單元。 Orca目前有七種不同類型的優化工作：

• Exp(g)：生成組g中所有組表達式的邏輯等效表達式。

• Exp(gexpr)：生成組表達式gexpr的邏輯等效表達式。

• Imp(g)：生成組g中所有組表達式的實現。

• Imp(gexpr)：生成組表達式gexpr的實現替代方案。

• Opt(g，req)：返回計劃的費用最少的計劃，該計劃是由操作員在g組中確定的，并且滿足優化請求的要求。

• Opt(gexpr，req)：以gexpr為根并且滿足優化請求req的估計成本最低的計劃返回。

• Xform(gexpr，t)使用規則t變換組表達式gexpr。

Optimization jobs dependency graph

對于給定的查詢，可以創建每種類型的數百甚至數千個工作實例。 這引入了處理作業依賴性的挑戰。 例如，只有在優化其子組之前，才能優化組表達式。  上圖顯示了部分作業圖，其中優化請求req0下的組g0的優化觸發了一棵深層的依賴作業。 依賴關系被編碼為父子鏈接; 父級作業在子級作業完成之前無法完成。  當子級工作進展順利時，父級工作需要暫停。 如果子作業不依賴其他作業，則允許它們選擇可用線程并并行運行。  當所有子作業完成時，將通知已暫停的父作業以繼續處理。

六、元數據交換

Orca旨在在數據庫系統之外工作。優化器與數據庫系統之間的主要交互點是元數據交換。例如，優化器可能需要知道是否在給定的表上定義了索引，以設計出有效的查詢計劃。元數據提供程序的集合促進了對元數據的訪問，這些元數據提供程序是特定于系統的插件，用于從數據庫系統檢索元數據。

下圖顯示了Orca如何與不同的后端系統交換元數據。在查詢優化過程中，Orca訪問的所有元數據對象都固定在內存中的緩存中，并在優化完成或引發錯誤時取消固定。所有對元數據對象的訪問都通過MD  Accessor完成，該訪問器可跟蹤優化會話中正在訪問的對象，并確保在不再需要它們時將其釋放。如果請求的元數據對象尚未在緩存中，則MD  Accessor還負責透明地從外部MD Provider提取元數據。服務于不同優化會話的不同MD訪問器可能具有用于獲取元數據的不同外部MD提供程序。

Metadata exchange framework

七、其它優化方案

1. 基礎查詢優化

Volcano Parallel Database 引入了實現數據庫并行性的基本原理。  所提出的框架引入了交換運算符，該交換運算符實現了兩種并行處理方式，即通過流水線實現操作符之間的并行化，以及通過跨運行在不同進程上的運算符對元組進行分區，實現了操作符內部并行化。  提出的設計允許每個操作符獨立于本地數據執行，以及與在其他進程中運行的其他操作符并行工作。 幾個MPP數據庫()利用這些原理來構建商業上成功的產品。

Cascades 是可擴展的優化器框架，其原理已用于構建MS-SQL Server，SCOPE ，PDW 和Orca(我們在本文中介紹的優化器)。  該框架之所以流行，是因為它把邏輯和物理計劃空間完全分開了。 這主要是通過將運算符和轉換規則封裝到獨立的組件中來實現的。  這種模塊化的設計使Cascades可以對邏輯上相等的表達式進行分組，以消除多余的工作，與Volcano的詳盡的方法形成對比，允許按需觸發規則，并允許根據規則的用途對給定的規則進行應用操作符排序。

2. MPP數據庫SQL優化

存儲和查詢數據量的指數增長已轉化為大規模并行處理(MPP)系統的更廣泛使用，例如Teradata ，Oracle的Exadata ，Netezza  ，Pivotal Greenplum數據庫和Vertica 。由于篇幅所限，我們總結了最近在重新設計查詢優化器以應對大數據挑戰方面的一些努力。

SQL Server并行數據倉庫(PDW)廣泛使用了已建立的Microsoft SQL Server優化器。對于每個查詢，PDW觸發對SQL  Server優化器的優化請求，該優化器在僅保留數據庫的元數據和統計信息而不保留其用戶數據的Shell數據庫上工作。然后，將SQL  Server優化程序采用的替代方案運送到PDW的數據移動服務(DMS)，在其中使用分發信息對這些邏輯計劃進行改進。盡管這種方法避免了從頭開始構建優化器，但由于優化邏輯分布在兩個不同的過程和代碼庫中，因此使調試和維護變得更加困難。

為并行執行而優化的結構化計算(SCOPE)是Microsoft的數據分析平臺，它充分利用了并行數據庫和MapReduce系統的特性。  SCOPE的腳本語言(例如Hive )是基于SQL的。  SCOPE是為使用僅附加文件系統的Cosmos分布式數據平臺開發的，而Orca的設計目標是與多個基礎數據管理系統一起工作。

SAP HANA 是一個分布式的內存數據庫系統，用于處理業務分析和OLTP查詢。  MPP數據庫中的分析查詢可能會產生大量中間結果。并發分析查詢會耗盡可用內存，其中大部分已被消耗以存儲和索引原始數據，并且會觸發數據溢出到磁盤，從而對查詢性能產生負面影響。

Vertica  是C-Store項目的商業化MPP版本，其中數據被組織為投影，每個投影都是表屬性的子集。最初的StarOpt及其經過修改的StratifiedOpt優化器是為針對星型/雪花模式的查詢而定制設計的，其中相同范圍的聯接鍵位于同一位置。如果無法實現數據并置，則可以在所有節點上復制相關的投影以提高性能，這是Vertica的V2Opt優化器所解決的。

3. SQL on Hadoop

在Hadoop上執行SQL的經典方法是使用Hive 將查詢轉換為MapReduce作業。 MapReduce的性能可能無法滿足交互式分析的要求。  Stinger  是通過利用和擴展Hive在Hadoop上優化查詢評估的一項計劃。但是，這種方法可能需要對MapReduce計算框架進行重大的重新設計，以優化數據傳遞，并在磁盤上實現中間結果。

通過創建專門的查詢引擎，無需使用MapReduce，就可以在HDFS中基于SQL的數據處理，從而解決了Hadoop上的交互式處理問題。 Impala  ，HAWQ 和Presto是朝著這個方向努力的關鍵。這些方法的查詢優化器和執行引擎的設計和功能不同，這兩者都是查詢性能的差異化因素。  DBMS和Hadoop技術的共同定位允許使用DBMS中的SQL和HDFS中的MapReduce在每個平臺上本地處理數據。 Hadapt  率先提出了這種方法。微軟還引入了PolyBase ，以提供將來自PDW 的表與HDFS上的數據連接起來的功能，以優化從一個平臺到另一個平臺的數據交換。

AsterixDB  是一種開放源代碼的工作，可以基于NoSQL樣式數據模型有效地存儲，索引和查詢半結構化信息。目前，AsterixDB的查詢計劃器是由用戶提示驅動的，而不是像Orca這樣的成本驅動的方法。  Dremel 是Google提供的可擴展的列存儲解決方案，用于分析MapReduce管道的輸出。  Dremel提供了類似于AsterixDB的腳本語言(AQL)和SCOPE 的高級腳本語言來處理只讀嵌套數據。

以上是“Orca的架構是怎么樣的”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！