calcite查詢優(yōu)化器介紹概述目錄TOC\o"1-3"\h\u1019calcite查詢優(yōu)化器介紹概述 1256571.1基本概念 1221581.1.1關系代數表達式 176331.1.2轉換規(guī)則 299701.1.3代價計算 34541.2優(yōu)化原理 455851.2.1Volcano優(yōu)化器 457691.2.2calcite優(yōu)化流程 6查詢優(yōu)化是calcite框架最為重要也最為復雜的一部分，也是本文主要使用的部分。calcite提供了兩種優(yōu)化器VolcanoPlanner、HepPlanner，分別是基于代價的優(yōu)化器和基于規(guī)則的優(yōu)化器。calcite優(yōu)化器中的每一部分都具有可插拔性、可擴展性，方便改寫?；靖拍铌P系代數表達式查詢處理中語法分析和翻譯這一步將高級查詢語言轉換成優(yōu)化器的內部表示形式，這個內部表示形式通常是關系代數表達式。這些關系代數表達式包括過濾、投影、連接等操作。在calcite中用RelNode這一數據結構表示關系代數表達式，所有的操作都實現了RelNode接口。每一個操作符都有一個特征集合來表示這個操作符的各種屬性特征。calcite中有三種特征：RelCollation、RelDistribution、Convention。RelCollation與關系表達式數據的排序特征有關，假設已知一個排序節(jié)點（Sort）的輸入節(jié)點數據按照排序節(jié)點要求的屬性有序，那么就可以移除這個排序節(jié)點。RelDistribution用來描述一個關系代數表達式數據分布特點。Convention是calcite中最主要的特征，它表示執(zhí)行該關系表達式的系統。如圖3.1所示，兩個掃描節(jié)點的Convention分別是HBase和MySQL，表明兩個掃描操作分別執(zhí)行在HBase和MySQL中，連接操作的Convention是None，表示還沒有執(zhí)行連接操作在何處執(zhí)行。Convention這個特征允許calcite在多個數據處理引擎或數據源執(zhí)行查詢。值得注意的是，改變一個運算符的特征并不影響其語義，但是通常會改變其所在查詢執(zhí)行計劃的代價。圖3.1不同的Convention轉換規(guī)則無論是基于代價的優(yōu)化器還是基于規(guī)則的優(yōu)化器都需要使用規(guī)則對關系代數表達式進行轉換，calcite內置了90多條優(yōu)化規(guī)則，用戶也可以自己編寫規(guī)則，規(guī)則使得優(yōu)化過程更加靈活和易于擴展。要想了解一個優(yōu)化器的優(yōu)化過程，關鍵要知道規(guī)則是如何匹配關系代數表達式，如何對匹配成功的關系代數表達式進行變換。RelOptRule是所有calcite中轉換規(guī)則的基類，RelOptRule定義了規(guī)則匹配的關系代數表達式結構和對關系代數表達式進行轉換的方法。RelOptRule包含一個列表operands，這個列表是規(guī)則匹配的關鍵，operands列表是有層次結構的，列表中的每一項是一個RelOptRuleOperand，代表一個要匹配的關系代數表達式結構。例如，對于FilterJoinRule，這個規(guī)則的作用是把Join節(jié)點上面的Filter節(jié)點下推到Join的孩子中。這個規(guī)則匹配的關系代數表達式結構如圖3.2所示，該規(guī)則的operands列表包含兩個RelOptRuleOperand，第一個是FilterJoinRule:*Filter*(Join)，表示孩子節(jié)點為Join的Filter節(jié)點，第二個是FilterJoinRule:Filter(*Join*)，表示父節(jié)點是Filter節(jié)點的Join節(jié)點。通過RelOptRule可以知道相應的匹配結構，通過RelOptRuleOperand也能得到相應的RelOptRule。圖3.2FilterJoinRule匹配的關系代數表達式結構規(guī)則從開始優(yōu)化到被觸發(fā)主要有以下幾個關鍵步驟：將規(guī)則注冊到優(yōu)化器：優(yōu)化開始前，優(yōu)化器會把用戶聲明的規(guī)則添加到優(yōu)化器的mapDescToRule列表中，這個列表存儲了所有可能要使用的規(guī)則。篩選候選規(guī)則初始的查詢計劃樹中的RelNode節(jié)點和后來通過規(guī)則轉換生成的新的RelNode節(jié)點都需要被注冊到優(yōu)化器中，在注冊RelNode節(jié)點的過程中，優(yōu)化器會檢查記錄的所有規(guī)則（存儲在mapDescToRule列表中）是否有匹配當前RelNode的規(guī)則。對于一個規(guī)則，只要當前RelNode符合匹配結構中的一項，就把它加入到一個字典classOperands中。這里相當于把這個規(guī)則加入到候選規(guī)則中，不一定會觸發(fā)。比如對于FilterJoinRule，它的匹配結構中有Join節(jié)點，也就是說只要出現一個Join節(jié)點，FilterJoinRule就會被加入到候選規(guī)則中，但是Join節(jié)點的上面不一定存在Filter節(jié)點，FilterJoinRule是否會被觸發(fā)，還需要進一步匹配結構檢查。將規(guī)則放入規(guī)則隊列規(guī)則被放入classOperands后還需要進一步的匹配。對于classOperands中的一個鍵值對RelNode-RelOptRuleOperand，需要遞歸地匹配RelOptRuleOperand結構和當前RelNode周圍的結構，如果完全匹配，優(yōu)化器會創(chuàng)建一個VolcanoRuleMatch對象，這個對象是規(guī)則和其要作用的RelNode結構的映射，之后再把這個VolcanoRuleMatch對象添加到規(guī)則隊列中。至此，這個規(guī)則才確定會被觸發(fā)。代價計算calcite基于代價的優(yōu)化器定義了一個關系代數表達式節(jié)點的代價，包含三項：行數、CPU代價以及I/O代價。calcite為每個運算符指定了其代價計算的默認實現。計算這些代價需要用到calcite的元數據提供器。元數據提供器提供各種統計信息，例如節(jié)點的行數、選擇度等。用戶可以改寫元數據提供器中的函數來注入自己的統計信息。優(yōu)化原理calcite提供的基于代價的優(yōu)化器VolcanoPlanner是對Volcano模型的落地實現。要想了解calcite優(yōu)化過程，需要先了解Volcano模型的設計思想。Volcano優(yōu)化器成本最優(yōu)假設Volcano優(yōu)化器由GoetzGraefe等人于1993年提出，它引進了動態(tài)規(guī)劃的思想以減少查詢計劃搜索空間。Volcano優(yōu)化器提出了成本最優(yōu)假設，這一假設認為，對于最優(yōu)查詢計劃，取其局部的結構來看也是最優(yōu)的，也就是整體最優(yōu)取決于局部最優(yōu)，這其實就是動態(tài)規(guī)劃里的“最優(yōu)子結構”假設在查詢優(yōu)化上的應用。換句話說，一個子樹的代價正比于這個子樹各部分代價的和，如圖3.3所示，以A節(jié)點為根節(jié)點的子樹的代價等于A節(jié)點本身的代價加上B、C節(jié)點的代價。在calcite中，一個節(jié)點的代價分為兩種：節(jié)點本身的代價和以這個節(jié)點為根節(jié)點的子樹的代價，分別被稱為NonCumulativeCost和CumulativeCost，在比較兩個節(jié)點的代價時，應該使用CumulativeCost，因為一個節(jié)點的代價小不代表整個子樹的代價小，可能出現圖3.4的情況，?1的代價小于?3的代價，但是?2的代價遠大于?4的代價，?3為根節(jié)點的子樹的代價小于?1為根節(jié)點的子樹的代價，最終的優(yōu)化是對整棵查詢樹的優(yōu)化。圖3.3子樹的代價圖3.4子樹?1和子樹?3等價集合有了成本最優(yōu)假設，就可以應用動態(tài)規(guī)劃算法的思想，在優(yōu)化過程中記錄子樹的最優(yōu)查詢計劃和最低代價，在以后的計算中，可以直接使用之前的緩存結果。要實現動態(tài)規(guī)劃的思想，需要一個數據結構來記錄子樹的最優(yōu)查詢計劃等信息，Volcano優(yōu)化器使用與或樹[17]（AND-ORTREE）的數據結構來實現這一目的。AND-ORTREE包含兩種節(jié)點：AND節(jié)點和OR節(jié)點。AND節(jié)點代表操作符，例如投影操作符、連接操作符。OR節(jié)點代表一組等價節(jié)點的集合。對于如圖3.5(a)表示的初始查詢A?B?C，其AND-ORTREE表示如圖3.5(b)所示，方塊表示OR節(jié)點，圓圈表示AND節(jié)點。經過交換律規(guī)則和結合律規(guī)則變換后，生成查詢計劃A?(B?C)和A?C?B，如圖3.5(c)所示。與或樹里的OR節(jié)點代表了等價的查詢計劃集合。在calcite中，用RelSet這個數據結構作為具有相同語義的關系代數表達式集合，用RelSubset結構作為具有相同物理特征的關系代數表達式集合。(a)(b)(c)圖3.5AND-ORTREE動態(tài)規(guī)劃算法分類動態(tài)規(guī)劃算法按照遍歷順序可以分為兩類：自底向上的動態(tài)規(guī)劃算法和自頂向下的動態(tài)規(guī)劃算法。自底向上的算法比較簡單：計算以節(jié)點R為根節(jié)點的樹的最優(yōu)查詢計劃和最低代價時，其子樹上每個節(jié)點的最優(yōu)方案和最低代價都已計算完畢，R節(jié)點只需要根據其孩子節(jié)點的最優(yōu)方案來尋找以R節(jié)點為根節(jié)點的整棵樹的最優(yōu)方案和執(zhí)行代價。經典的SystemR系統就采用了自底向上的動態(tài)規(guī)劃算法[15]。自底向上的動態(tài)規(guī)劃存在一些弊端，比如不方便剪枝，在優(yōu)化過程中可能已經知道父節(jié)點的代價會很高，它的子節(jié)點的各種等價情況就無需考慮了，自底向上的動態(tài)規(guī)劃中這部分計算不可避免。Volcano優(yōu)化器采用自頂向下的動態(tài)規(guī)劃算法。優(yōu)化開始時，每個節(jié)點初始的代價作為其所在等價集合的最低代價。在不斷應用優(yōu)化規(guī)則的過程中，可能有新的關系代數表達式被加入到等價集合中，如果新加入的關系代數表達式的代價低于等價集合的最優(yōu)代價，用新加入的關系代數表達式及其代價更新等價集合的最優(yōu)方案和最低代價，然后最優(yōu)的代價需要向上冒泡到所有依賴這一子等價集合的父等價集合，更新這些集合的最優(yōu)方案和最低代價。需要注意的是，向上冒泡的過程中，需要重新計算父等價集合中的每個方案，因為不同的方案對輸入的代價變化有著不同的敏感度，不能假設之前的最優(yōu)方案仍然是最優(yōu)的。calcite優(yōu)化流程calcite的優(yōu)化流程與Volcano優(yōu)化器類似。優(yōu)化器的輸入是一棵樹，樹的每個節(jié)點都是關系代數表達式。初始時，需要通過深度優(yōu)先遍歷把每個節(jié)點注冊到優(yōu)化器中。每個節(jié)點都有一個全局唯一的摘要，節(jié)點的摘要記錄了該節(jié)點的輸入節(jié)點和節(jié)點特征等信息。根據節(jié)點的摘要信息，判斷該節(jié)點是否已經存在于優(yōu)化器緩存中。如果該節(jié)點的摘要已經存在于優(yōu)化器，說明該節(jié)點已完成注冊，否則，將該節(jié)點加入到相應的等價集合RelSet中，節(jié)點添加到RelSet的過程中，會根據節(jié)點的物理特征在RelSet中新建或查找到一個相應的RelSubset，即具有相同物理屬性的節(jié)點等價集合。接下來檢查加入RelSubset的節(jié)點是否使得RelSub