query planner guide
1.0.0
[佔位符]
查詢計劃器是數據庫管理系統（DBMS）的組件，該系統負責生成執行數據庫查詢的計劃。查詢計劃指定了DBMS將要檢索查詢要求的數據所採取的步驟。查詢計劃者的目標是生成盡可能高效的計劃，這意味著它將盡快將數據返回給用戶。
查詢計劃者是複雜的軟件，它們很難理解。本實現基於成本的查詢計劃者的指南將為您提供該過程的分步概述，如何實現自己的基於成本的查詢計劃者，同時仍然涵蓋查詢計劃者的基本概念。
由AI撰寫，由人類編輯
本指南的編寫：
目標：
圖TD
用戶（（用戶））
解析器[查詢解析器]
計劃者[查詢計劃者]
執行人[查詢處理器]
用戶 - 文字查詢 - >解析器
解析器 - ast->計劃者
計劃者 - 物理計劃 - >執行人
查詢引擎的基本體系結構由這些組件組成：
通常，查詢計劃者分為兩種類型：
啟發式規劃師是使用預定義規則生成查詢計劃的查詢計劃者。
基於成本的規劃師是基於生成查詢的成本的查詢計劃者，它試圖根據輸入查詢的成本找到最佳計劃。
儘管啟發式規劃師通常會通過應用轉換規則找到最佳計劃，如果它知道轉換計劃更好，但基於成本的計劃者通過列舉等效計劃找到最佳計劃，並嘗試找到其中的最佳計劃。
在基於成本的查詢計劃者中，通常由階段組成：
在計劃列舉階段，計劃者將列舉可能的等效計劃。
之後，在查詢優化階段，計劃者將從列舉計劃列表中搜索最佳計劃。最好的計劃是該計劃的成本最低，該計劃定義了成本模型（或成本功能）。
因為邏輯計劃的自然是具有類似樹狀的結構，因此您可以認為優化/搜索實際上是一個搜索問題。這裡有很多樹搜索算法：
注意：從理論上講，可以使用任何類型的樹搜索算法。但是，實際上，這是不可行的，因為當我們的搜索算法複雜時，搜索時間會增加
注意：搜索終止條件通常是：
火山查詢計劃器（或火山優化器生成器）是基於成本的查詢計劃者
火山規劃師使用動態編程方法來從枚舉計劃列表中找到最佳的查詢計劃。
詳細信息：https：//ieeexplore.ieee.org/document/344061（我懶得在這裡解釋論文）
這是一個很好的解釋：https：//15721.courses.cs.cmu.edu/spring2017/slides/15-optimizer2.pdf#page=9
我們的查詢計劃者是基於成本的查詢計劃者，遵循火山查詢計劃者的基本思想，我們的計劃者將由兩個主要階段組成：
圖LR
AST（（AST））
logical_plan [計劃]
Exportored_plans [``
計劃＃1
...
計劃#N
``]]
enasemation_plan [“計劃#x（最佳計劃）”]
ast-轉換為邏輯計劃 - > logical_plan
logical_plan-探索階段 - > explored_plans
Expentored_plans-優化階段 - > enasemation_plan
LinkStyle 1,2顏色：橙色，中風：橙色，中風寬度：5px
邏輯計劃是保持執行查詢所需的轉換步驟的抽象的數據架構。
這是一個邏輯計劃的示例：
圖TD
1 [“ project tbl1.id，tbl1.field1，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”];
2 [“加入”];
3 [“掃描TBL1”];
4 [“加入”];
5 [“掃描TBL2”];
6 [“掃描TBL3”];
1-> 2;
2-> 3;
2-> 4;
4-> 5;
4-> 6;
雖然邏輯計劃僅具有抽象，但物理計劃是持有實現詳細信息的數據架構。每個邏輯計劃都會有多個物理計劃。例如，邏輯上的加入可能會有許多物理計劃，例如哈希（Hash）加入，合併加入，廣播加入等。
等效組是一組等效表達式（對於每個表達式，它們的邏輯計劃在邏輯上是等效的）
例如
圖TD
子圖組＃8
expr＃8 [“掃描TBL2（field1，field2，id）”]
結尾
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組11
expr＃11 [“加入”]
結尾
Expr＃11->組＃7
Expr＃11->組＃10
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃7
expr＃7 [“掃描TBL1（ID，field1）”]
結尾
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃10
expr＃10 [“加入”]
結尾
Expr＃10->組＃8
Expr＃10->組＃9
子圖組＃9
expr＃9 [“掃描TBL3（ID，field2）”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃12 [“ project tbl1.id，tbl1.field1，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃12->組＃11
Expr＃6->組＃5
在這裡，我們可以看到Group#6有2個等效的表達式，它們都代表相同的查詢（一個是從表進行掃描，然後是項目，一個將投影向下推到掃描節點）。
轉換規則是從一個邏輯計劃轉換為另一個邏輯等效邏輯計劃的規則
例如，計劃：
圖TD
1 [“ project tbl1.id，tbl1.field1，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”];
2 [“加入”];
3 [“掃描TBL1”];
4 [“加入”];
5 [“掃描TBL2”];
6 [“掃描TBL3”];
1-> 2;
2-> 3;
2-> 4;
4-> 5;
4-> 6;
應用投影下降轉換時，將轉換為：
圖TD
1 [“項目 *。 *”];
2 [“加入”];
3 [“掃描TBL1（ID，field1）”];
4 [“加入”];
5 [“掃描TBL2（field1，field2）”];
6 [“掃描tbl3（id，field2，field2）”];
1-> 2;
2-> 3;
2-> 4;
4-> 5;
4-> 6;
轉換規則可以通過邏輯性狀/屬性（例如表模式，數據統計信息等）影響。
實施規則是返回給定邏輯計劃的物理計劃的規則。
實現規則可以受到物理性狀/屬性（例如數據佈局（是否排序）等）的影響。
在探索階段，計劃者將應用轉換規則，生成等效的邏輯計劃
例如，計劃：
圖TD
1326583549 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.if，tbl3.field2，tbl3.field2”];
-425111028 [“ JOIN”];
-349388609 [“ scan tbl1”];
1343755644 [“ JOIN”];
-1043437086 [“ scan tbl2”];
-1402686787 [“ scan tbl3”];
1326583549-> -425111028;
-425111028-> -349388609;
-425111028-> 1343755644;
1343755644-> -1043437086;
1343755644-> -1402686787;
應用轉換規則後，導致以下圖：
圖TD
子圖組＃8
expr＃8 [“掃描TBL2（ID，field1，field2）”]
結尾
子圖組11
expr＃11 [“加入”]
Expr＃14 [“加入”]
結尾
Expr＃11->組＃7
Expr＃11->組＃10
Expr＃14->組＃8
Expr＃14->組＃12
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
expr＃16 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
Expr＃16->組＃2
Expr＃16->組＃13
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃13
Expr＃15 [“加入”]
結尾
Expr＃15->組＃1
Expr＃15->組＃3
子圖組＃7
expr＃7 [“掃描TBL1（ID，field1）”]
結尾
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃10
expr＃10 [“加入”]
結尾
Expr＃10->組＃8
Expr＃10->組＃9
子圖組＃9
expr＃9 [“掃描TBL3（ID，field2）”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組12
Expr＃13 [“加入”]
結尾
Expr＃13->組＃7
Expr＃13->組＃9
子圖組6
expr＃12 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃12->組＃11
Expr＃6->組＃5
在這裡，我們可以看到應用投影下降規則和加入重新排序規則。
優化階段是在勘探階段穿越擴展的樹，以找到我們查詢的最佳計劃。
此“實際上”是樹搜索優化，因此您可以使用任何可以想像的樹搜索算法（但是您必須確保它正確）。
這是優化階段後生成的物理計劃的示例：
圖TD
組6 [“”
第6組
選擇：project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2
操作員：ProjectOperator
費用：成本（CPU = 641400.00，MEM = 1020400012.00，TIME = 1000000.00）
”
第6組 - >組＃11
組＃11 [”
第11組
選擇：加入
操作員：HashJoineperator
費用：成本（CPU = 641400.00，MEM = 1020400012.00，TIME = 1000000.00）
”
組＃11->組＃7
組11->組＃10
組＃7 [”
第7組
選擇：掃描TBL1（ID，field1）
操作員：NormalsCanoperator
費用：成本（CPU = 400.00，MEM = 400000.00，時間= 1000.00）
”
組＃10 [”
小組＃10
選擇：加入
操作員：合併器
特質：排序
費用：成本（CPU = 640000.00，MEM = 20000012.00，時間= 1100000.00）
”
組＃10->組＃8
組＃10->組＃9
組＃8 [”
第8組
選擇：掃描TBL2（ID，field1，field2）
操作員：NormalsCanoperator
特質：排序
費用：成本（CPU = 600000.00，MEM = 12.00，TIME = 1000000.00）
”
組＃9 [”
組＃9
選擇：掃描TBL3（ID，field2）
操作員：NormalsCanoperator
特質：排序
費用：成本（CPU = 40000.00，MEM = 20000000.00，TIME = 100000.00）
”
生成的計劃顯示了選定的邏輯計劃，估計成本和物理操作員
我們的計劃者將執行精疲力盡的搜索以找到最佳計劃
由於規劃師的代碼很大，所以我不會逐步編寫指南，但是我會解釋一下代碼的每一部分
在這裡，我們將定義一種徹底使用本教程的查詢語言
SELECT emp . id ,
emp . code ,
dept . dept_name ,
emp_info . name ,
emp_info . origin
FROM emp
JOIN dept ON emp . id = dept . emp_id
JOIN emp_info ON dept . emp_id = emp_info . id我們將實現的查詢語言是一種類似SQL的語言。但是，為了簡單起見，我們將限制其功能和語法。
該語言以
SELECT tbl . field , [...]
FROM tbl JOIN [...]它只會支持SELECT和JOIN ，還必須在Select語句中的字段（以table.field的形式）中的字段，所有其他功能都不會受到支持
首先，我們必須為我們的語言定義AST。 AST（或抽象語法樹）是用來表示文本的句法結構的樹。
由於我們的語言是如此簡單，因此我們可以在幾行代碼中定義AST結構：
sealed trait Identifier
case class TableID ( id : String ) extends Identifier
case class FieldID ( table : TableID , id : String ) extends Identifier
sealed trait Statement
case class Table ( table : TableID ) extends Statement
case class Join ( left : Statement , right : Statement , on : Seq [( FieldID , FieldID )]) extends Statement
case class Select ( fields : Seq [ FieldID ], from : Statement ) extends Statement
例如，查詢
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . id可以表示為
Select (
Seq (
FieldID ( TableID ( " tbl1 " ), " id " ),
FieldID ( TableID ( " tbl1 " ), " field1 " ),
FieldID ( TableID ( " tbl2 " ), " id " ),
FieldID ( TableID ( " tbl2 " ), " field1 " ),
FieldID ( TableID ( " tbl2 " ), " field2 " ),
FieldID ( TableID ( " tbl3 " ), " id " ),
FieldID ( TableID ( " tbl3 " ), " field2 " ),
FieldID ( TableID ( " tbl3 " ), " field2 " )
),
Join (
Table ( TableID ( " tbl1 " )),
Join (
Table ( TableID ( " tbl2 " )),
Table ( TableID ( " tbl3 " )),
Seq (
FieldID ( TableID ( " tbl2 " ), " id " ) -> FieldID ( TableID ( " tbl3 " ), " id " )
)
),
Seq (
FieldID ( TableID ( " tbl1 " ), " id " ) -> FieldID ( TableID ( " tbl2 " ), " id " )
)
)
)定義AST結構後，我們將不得不編寫查詢解析器，該解析器用於將文本查詢轉換為AST形式。
由於本指南是使用Scala進行實施，因此我們將選擇Scala-Parser-Combionators創建我們的查詢解析器。
查詢解析器類：
object QueryParser extends ParserWithCtx [ QueryExecutionContext , Statement ] with RegexParsers {
override def parse ( in : String )( implicit ctx : QueryExecutionContext ) : Either [ Throwable , Statement ] = {
Try (parseAll(statement, in) match {
case Success (result, _) => Right (result)
case NoSuccess (msg, _) => Left ( new Exception (msg))
}) match {
case util. Failure (ex) => Left (ex)
case util. Success (value) => value
}
}
private def select : Parser [ Select ] = ??? // we will implement it in later section
private def statement : Parser [ Statement ] = select
}
然後定義一些解析規則：
// common
private def str : Parser [ String ] = """ [a-zA-Z0-9_]+ """ .r
private def fqdnStr : Parser [ String ] = """ [a-zA-Z0-9_]+.[a-zA-Z0-9_]+ """ .r
// identifier
private def tableId : Parser [ TableID ] = str ^^ (s => TableID (s))
private def fieldId : Parser [ FieldID ] = fqdnStr ^^ { s =>
val identifiers = s.split( '.' )
if (identifiers.length != 2 ) {
throw new Exception ( " should never happen " )
} else {
val table = identifiers.head
val field = identifiers( 1 )
FieldID ( TableID (table), field)
}
}這是兩個規則，用於解析標識符： TableID和FieldID 。
表ID（或表名稱）通常僅包含字符，數字和下劃線（ _ ），因此我們將使用一個簡單的正則表達式[a-zA-Z0-9_]+來識別表名。
另一方面，我們語言中的字段ID（對於現場預選賽）是完全合格的場名稱。通常，它以table.field的形式，字段名稱通常也只包含字符，數字和下劃線，因此我們將使用Regex [a-zA-Z0-9_]+.[a-zA-Z0-9_]+來解析字段名稱。
定義了解析標識符的規則後，我們現在可以定義規則以解析查詢語句：
// statement
private def table : Parser [ Table ] = tableId ^^ (t => Table (t))
private def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) " table規則是一個簡單的規則，它僅通過使用tableId規則的分析TableID創建Table節點。
subQuery是解析子問題的規則。在SQL中，我們可以編寫一個看起來像這樣的查詢：
SELECT a
FROM ( SELECT b FROM c) d SELECT b FROM c是上述語句中的子查詢。在這裡，在我們簡單的查詢語言中，我們將指出一個語句是一個子查詢，如果它被一對括號（ () ）包含。由於我們的語言只有精選的語句，因此我們可以寫出解析規則如下：
def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "現在，我們將定義Select語句的解析規則：
private def fromSource : Parser [ Statement ] = table ||| subQuery
private def select : Parser [ Select ] =
" SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep(
" JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)
) ^^ {
case _ ~ fields ~ _ ~ src ~ joins =>
val p = if (joins.nonEmpty) {
def chain ( left : Statement , right : Seq [( Statement , Seq [( FieldID , FieldID )])]) : Join = {
if (right.isEmpty) {
throw new Exception ( " should never happen " )
} else if (right.length == 1 ) {
val next = right.head
Join (left, next._1, next._2)
} else {
val next = right.head
Join (left, chain(next._1, right.tail), next._2)
}
}
val temp = joins.map { join =>
val statement = join._1._1._2
val joinOn = join._2.map(on => on._1._1 -> on._2)
statement -> joinOn
}
chain(src, temp)
} else {
src
}
Select (fields, p)
}在SQL中，我們可以使用子問題作為聯接源。例如：
SELECT * . *
FROM tbl1
JOIN ( SELECT * . * FROM tbl2)
JOIN tbl3因此，我們的解析器還將實施規則以在聲明的聯接部分中解析子查詢，這就是為什麼我們有分析規則：
" SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep( " JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)有關完整實施，請參見queryparser.scala
參見Queryparserspec.scala
從文本查詢生成AST後，我們可以將其直接轉換為邏輯計劃
首先，讓我們定義邏輯計劃的接口：
sealed trait LogicalPlan {
def children () : Seq [ LogicalPlan ]
}
children是兒童邏輯計劃的清單。例如：
圖TD
1326583549 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.if，tbl3.field2，tbl3.field2”];
-425111028 [“ JOIN”];
-349388609 [“ scan tbl1”];
1343755644 [“ JOIN”];
-1043437086 [“ scan tbl2”];
-1402686787 [“ scan tbl3”];
1326583549-> -425111028;
-425111028-> -349388609;
-425111028-> 1343755644;
1343755644-> -1043437086;
1343755644-> -1402686787;
PROJECT節點的子節點是第一個JOIN節點。第一個JOIN節點有2個孩子，這是第二個JOIN節點和SCAN tbl1節點。很快， ...
由於我們的查詢語言很簡單，因此我們只需要3種邏輯節點：
case class Scan ( table : ql. TableID , projection : Seq [ String ]) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq .empty
}
case class Project ( fields : Seq [ql. FieldID ], child : LogicalPlan ) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq (child)
}
case class Join ( left : LogicalPlan , right : LogicalPlan , on : Seq [(ql. FieldID , ql. FieldID )]) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq (left, right)
}
然後，我們可以編寫該功能以將AST轉換為邏輯計劃：
def toPlan ( node : ql. Statement ) : LogicalPlan = {
node match {
case ql. Table (table) => Scan (table, Seq .empty)
case ql. Join (left, right, on) => Join (toPlan(left), toPlan(right), on)
case ql. Select (fields, from) => Project (fields, toPlan(from))
}
}有關完整實施，請參見LogicalPlan.scala
我們可以為小組定義類，如以下內容：
case class Group (
id : Long ,
equivalents : mutable. HashSet [ GroupExpression ]
) {
val explorationMark : ExplorationMark = new ExplorationMark
var implementation : Option [ GroupImplementation ] = None
}
case class GroupExpression (
id : Long ,
plan : LogicalPlan ,
children : mutable. MutableList [ Group ]
) {
val explorationMark : ExplorationMark = new ExplorationMark
val appliedTransformations : mutable. HashSet [ TransformationRule ] = mutable. HashSet ()
}
Group是一組邏輯上等效的計劃。
每個GroupExpression代表一個邏輯計劃節點。由於我們定義了一個邏輯計劃節點將具有子節點的列表（在上一節中），並且GroupExpression代表一個邏輯計劃節點，並且Group代表一組等效計劃，因此GroupExpression的孩子是Group的列表。
例如
圖TD
子圖組＃8
Expr＃8
結尾
子圖組＃2
Expr＃2
結尾
子圖組11
Expr＃11
結尾
Expr＃11->組＃7
Expr＃11->組＃10
子圖組5
Expr＃5
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
Expr＃4
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃7
Expr＃7
結尾
子圖組＃1
Expr＃1
結尾
子圖組＃10
Expr＃10
結尾
Expr＃10->組＃8
Expr＃10->組＃9
子圖組＃9
Expr＃9
結尾
子圖組＃3
Expr＃3
結尾
子圖組6
Expr＃12
Expr＃6
結尾
Expr＃12->組＃11
Expr＃6->組＃5
正如我們在這裡可以看到的那樣， Group#6具有2個等效表達式： Expr#12和Expr#6 ， Expr#12的孩子是Group#11
注意：我們將在勘探階段實施多輪轉換，因此，對於每個Group和GroupExpression ，我們都有ExplorationMark標誌的探索狀態。
class ExplorationMark {
private var bits : Long = 0
def get : Long = bits
def isExplored ( round : Int ) : Boolean = BitUtils .getBit(bits, round)
def markExplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = true )
def markUnexplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = false )
}
ExplorationMark只是一個bitset包裝器類，如果探索了第i-thile，它將標記為第1位，否則將標記為0。
ExplorationMark也可用於可視化確切的轉換，有關更多細節，請參見可視化。
備忘錄是一群幫助者，可以幫助構建同等的群體。備忘錄由幾個hashmap組成來緩存組和組表達式，還提供了註冊新組或組表達式的方法。
class Memo (
groupIdGenerator : Generator [ Long ] = new LongGenerator ,
groupExpressionIdGenerator : Generator [ Long ] = new LongGenerator
) {
val groups : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]()
val parents : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]() // lookup group from group expression ID
val groupExpressions : mutable. HashMap [ LogicalPlan , GroupExpression ] = mutable. HashMap [ LogicalPlan , GroupExpression ]()
def getOrCreateGroupExpression ( plan : LogicalPlan ) : GroupExpression = {
val children = plan.children()
val childGroups = children.map(child => getOrCreateGroup(child))
groupExpressions.get(plan) match {
case Some (found) => found
case None =>
val id = groupExpressionIdGenerator.generate()
val children = mutable. MutableList () ++ childGroups
val expression = GroupExpression (
id = id,
plan = plan,
children = children
)
groupExpressions += plan -> expression
expression
}
}
def getOrCreateGroup ( plan : LogicalPlan ) : Group = {
val exprGroup = getOrCreateGroupExpression(plan)
val group = parents.get(exprGroup.id) match {
case Some (group) =>
group.equivalents += exprGroup
group
case None =>
val id = groupIdGenerator.generate()
val equivalents = mutable. HashSet () + exprGroup
val group = Group (
id = id,
equivalents = equivalents
)
groups.put(id, group)
group
}
parents += exprGroup.id -> group
group
}
}
有關完整實施，請參見備忘錄。
計劃器內部的第一步是初始化
圖LR
查詢（（QUERY））
AST（（AST））
root_plan（（rootplan））
root_group（（rootgroup））
查詢 - “ queryparser.parse（query）” - > ast
ast-“ logicalplan.toplan（ast）” - > root_plan
root_plan-“備忘錄。
首先，查詢將被解析為AST。然後轉換為邏輯計劃，稱為root plan ，然後從root plan中初始化該組，稱為root group 。
def initialize ( query : Statement )( implicit ctx : VolcanoPlannerContext ) : Unit = {
ctx.query = query
ctx.rootPlan = LogicalPlan .toPlan(ctx.query)
ctx.rootGroup = ctx.memo.getOrCreateGroup(ctx.rootPlan)
// assuming this is first the exploration round,
// by marking the initialRound(0) as explored,
// it will be easier to visualize the different between rounds (added nodes, add connections)
ctx.memo.groups.values.foreach(_.explorationMark.markExplored(initialRound))
ctx.memo.groupExpressions.values.foreach(_.explorationMark.markExplored(initialRound))
}有關更多詳細信息，請參見Volcanoplanner.scala
例如，查詢：
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . id初始化後，這些小組將看起來像這樣：
圖TD
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃6->組＃5
在這裡您可以看到，每個組都有一個等效的表達
初始化後，現在是勘探階段，它將探索所有可能的等效計劃。
探索方法非常簡單：
在研究探索法規之前，讓我們先談談轉換規則。
轉換規則是一條規則，用於將邏輯計劃轉換為另一個等效邏輯計劃，如果該計劃與規則條件匹配。
這是轉換規則的接口：
trait TransformationRule {
def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean
def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression
}
由於邏輯計劃是類似樹的數據架構，因此轉換規則的match實現是在樹上匹配的模式。
例如，這是用於匹配項目節點的match ，同時還檢查它是否是包含聯接和掃描的後代：
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case Project (_, child) => check(child)
case _ => false
}
}
// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
node match {
case Scan (_, _) => true
case Join (left, right, _) => check(left) && check(right)
case _ => false
}
}該計劃“匹配”：
圖TD
子圖組＃2
Expr＃2 [“掃描”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1
Expr＃1 [“掃描”]
結尾
子圖組＃3
Expr＃3 [“掃描”]
結尾
子圖組6
Expr＃6 [“項目”]
結尾
Expr＃6->組＃5
雖然該計劃不是：
圖TD
子圖組＃2
Expr＃2 [“掃描”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃3
Expr＃5->組＃4
子圖組＃4
Expr＃4 [“掃描”]
結尾
子圖組＃7
Expr＃7 [“項目”]
結尾
Expr＃7->組＃6
子圖組＃1
Expr＃1 [“掃描”]
結尾
子圖組＃3
Expr＃3 [“項目”]
結尾
Expr＃3->組＃2
子圖組6
expr＃6 [“加入”]
結尾
Expr＃6->組＃1
Expr＃6->組＃5
正如我們之前說過的，探索方法是：
這是探索代碼（非常簡單，是的）：
private def exploreGroup (
group : Group ,
rules : Seq [ TransformationRule ],
round : Int
)( implicit ctx : VolcanoPlannerContext ) : Unit = {
while ( ! group.explorationMark.isExplored(round)) {
group.explorationMark.markExplored(round)
// explore all child groups
group.equivalents.foreach { equivalent =>
if ( ! equivalent.explorationMark.isExplored(round)) {
equivalent.explorationMark.markExplored(round)
equivalent.children.foreach { child =>
exploreGroup(child, rules, round)
if (equivalent.explorationMark.isExplored(round) && child.explorationMark.isExplored(round)) {
equivalent.explorationMark.markExplored(round)
} else {
equivalent.explorationMark.markUnexplored(round)
}
}
}
// fire transformation rules to explore all the possible transformations
rules.foreach { rule =>
if ( ! equivalent.appliedTransformations.contains(rule) && rule.`match`(equivalent)) {
val transformed = rule.transform(equivalent)
if ( ! group.equivalents.contains(transformed)) {
group.equivalents += transformed
transformed.explorationMark.markUnexplored(round)
group.explorationMark.markUnexplored(round)
}
}
}
if (group.explorationMark.isExplored(round) && equivalent.explorationMark.isExplored(round)) {
group.explorationMark.markExplored(round)
} else {
group.explorationMark.markUnexplored(round)
}
}
}
}有關更多詳細信息，請參見Volcanoplanner.scala
現在是時候實施一些轉換規則了
投影下降是一個簡單的轉換規則，用於將投影推向存儲層。
例如，查詢
SELECT field1, field2
from tbl有計劃
圖LR
項目[Project Field1，field2]
掃描[掃描TBL]
項目 - >掃描
通過此計劃，在執行時，將完全獲取存儲層（掃描下）的行（在掃描下），然後將刪除不必要的字段（項目）。不必要的數據仍然必須從掃描節點轉移到項目節點，因此這裡有一些浪費的努力。
只需告訴存儲層僅獲取必要的字段，我們就可以使它變得更好。現在該計劃將轉變為：
圖LR
項目[Project Field1，field2]
掃描[“掃描TBL（field1，field2）”]
項目 - >掃描
讓我們介紹代碼：
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case Project (_, child) => check(child)
case _ => false
}
}
// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
node match {
case Scan (_, _) => true
case Join (left, right, _) => check(left) && check(right)
case _ => false
}
}我們在這裡的預測下降規則將匹配計劃節點時的計劃，並且其所有後代都是掃描並僅加入節點。
注意：實際上，真正的投影下降匹配更為複雜，但是為了簡單起見，這裡的匹配規則只是掃描和加入後代的項目節點
這是轉換代碼：
override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
val plan = expression.plan. asInstanceOf [ Project ]
val pushDownProjection = mutable. ListBuffer [ FieldID ]()
extractProjections(plan, pushDownProjection)
val newPlan = Project (plan.fields, pushDown(pushDownProjection.distinct, plan.child))
ctx.memo.getOrCreateGroupExpression(newPlan)
}
private def extractProjections ( node : LogicalPlan , buffer : mutable. ListBuffer [ FieldID ]) : Unit = {
node match {
case Scan (_, _) => () : Unit
case Project (fields, parent) =>
buffer ++= fields
extractProjections(parent, buffer)
case Join (left, right, on) =>
buffer ++= on.map(_._1) ++ on.map(_._2)
extractProjections(left, buffer)
extractProjections(right, buffer)
}
}
private def pushDown ( pushDownProjection : Seq [ FieldID ], node : LogicalPlan ) : LogicalPlan = {
node match {
case Scan (table, tableProjection) =>
val filteredPushDownProjection = pushDownProjection.filter(_.table == table).map(_.id)
val updatedProjection =
if (filteredPushDownProjection.contains( " * " ) || filteredPushDownProjection.contains( " *.* " )) {
Seq .empty
} else {
(tableProjection ++ filteredPushDownProjection).distinct
}
Scan (table, updatedProjection)
case Join (left, right, on) => Join (pushDown(pushDownProjection, left), pushDown(pushDownProjection, right), on)
case _ => throw new Exception ( " should never happen " )
}
}轉換代碼將首先從根項目節點中找到所有預測，然後將它們推向下面的所有掃描節點。
例如，可以看到我們的規則，例如計劃
圖TD
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃6->組＃5
應用投影下降變換後，將導致一個新的等效計劃，並將投影推向掃描操作（新計劃是帶有橙色邊框節點的樹）。
圖TD
子圖組＃8
expr＃8 [“掃描TBL2（ID，field1，field2）”]
結尾
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組11
expr＃11 [“加入”]
結尾
Expr＃11->組＃7
Expr＃11->組＃10
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃7
expr＃7 [“掃描TBL1（ID，field1）”]
結尾
子圖組＃10
expr＃10 [“加入”]
結尾
Expr＃10->組＃8
Expr＃10->組＃9
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃9
expr＃9 [“掃描TBL3（ID，field2）”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃12 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃12->組＃11
Expr＃6->組＃5
樣式Expr＃12中風寬度：4PX，中風：橙色
樣式Expr＃8中風寬度：4PX，中風：橙色
樣式expr＃10中風寬度：4PX，中風：橙色
樣式Expr＃9中風寬度：4PX，中風：橙色
樣式Expr＃11中風寬度：4PX，中風：橙色
樣式Expr＃7中風寬度：4PX，中風：橙色
LinkStyle 0中風寬度：4PX，中風：橙色
LinkStyle 1中風寬度：4PX，中風：橙色
LinkStyle 6中風寬度：4PX，中風：橙色
LinkStyle 7中風寬度：4PX，中風：橙色
LinkStyle 8中風寬度：4PX，中風：橙色
有關完整實施
加入重新訂購也是查詢計劃者世界上最知名的轉型之一。我們的計劃者還將實施一個重新訂購規則。
由於在現實世界中加入重新訂購併不是一個容易實施的部分。因此，我們將在此處實施一個簡單的挖掘版本加入重訂單規則。
首先，規則match ：
// check if the tree only contains SCAN and JOIN nodes, and also extract all SCAN nodes and JOIN conditions
private def checkAndExtract (
node : LogicalPlan ,
buffer : mutable. ListBuffer [ Scan ],
joinCondBuffer : mutable. ListBuffer [(ql. FieldID , ql. FieldID )]
) : Boolean = {
node match {
case node @ Scan (_, _) =>
buffer += node
true
case Join (left, right, on) =>
joinCondBuffer ++= on
checkAndExtract(left, buffer, joinCondBuffer) && checkAndExtract(right, buffer, joinCondBuffer)
case _ => false
}
}
private def buildInterchangeableJoinCond ( conditions : Seq [(ql. FieldID , ql. FieldID )]) : Seq [ Seq [ql. FieldID ]] = {
val buffer = mutable. ListBuffer [mutable. Set [ql. FieldID ]]()
conditions.foreach { cond =>
val set = buffer.find { set =>
set.contains(cond._1) || set.contains(cond._2)
} match {
case Some (set) => set
case None =>
val set = mutable. Set [ql. FieldID ]()
buffer += set
set
}
set += cond._1
set += cond._2
}
buffer.map(_.toSeq)
}
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case node @ Join (_, _, _) =>
val buffer = mutable. ListBuffer [ Scan ]()
val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
if (checkAndExtract(node, buffer, joinCondBuffer)) {
// only match if the join is 3 tables join
if (buffer.size == 3 ) {
var check = true
val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
interChangeableCond.foreach { c =>
check &= c.size == 3
}
check
} else {
false
}
} else {
false
}
case _ => false
}
}如果我們匹配3向加入時，我們的規則只會匹配（涉及表的數量必須為3，並且聯接條件必須為3向，例如tbl1.field1 = tbl2.field2 = tbl3.field3 ）
例如，
tbl1
JOIN tbl2 ON tbl1 . field1 = tbl2 . field2
JOIN tbl3 ON tbl1 . field1 = tbl3 . field3由於它的3向加入，此處的加入語句將“匹配”（這是tbl1 ， tbl2 ， tbl3之間的聯接，並且條件為tbl1.field1 = tbl2.field2 = tbl3.field3 ）
接下來，是變換代碼：
override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
val plan = expression.plan. asInstanceOf [ Join ]
val buffer = mutable. ListBuffer [ Scan ]()
val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
checkAndExtract(plan, buffer, joinCondBuffer)
val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
//
val scans = buffer.toList
implicit val ord : Ordering [ Scan ] = new Ordering [ Scan ] {
override def compare ( x : Scan , y : Scan ) : Int = {
val xStats = ctx.statsProvider.tableStats(x.table.id)
val yStats = ctx.statsProvider.tableStats(y.table.id)
xStats.estimatedTableSize.compareTo(yStats.estimatedTableSize)
}
}
def getJoinCond ( left : Scan , right : Scan ) : Seq [(ql. FieldID , ql. FieldID )] = {
val leftFields = interChangeableCond.flatMap { c =>
c.filter(p => p.table == left.table)
}
val rightFields = interChangeableCond.flatMap { c =>
c.filter(p => p.table == right.table)
}
if (leftFields.length != rightFields.length) {
throw new Exception ( s " leftFields.length( ${leftFields.length} ) != rightFields.length( ${rightFields.length} ) " )
} else {
leftFields zip rightFields
}
}
val sorted = scans.sorted
val newPlan = Join (
sorted( 0 ),
Join (
sorted( 1 ),
sorted( 2 ),
getJoinCond(sorted( 1 ), sorted( 2 ))
),
getJoinCond(sorted( 0 ), sorted( 1 ))
)
ctx.memo.getOrCreateGroupExpression(newPlan)
}這裡的轉換代碼將通過其估計的大小重新排序表。
例如，如果我們有3個表A，B，C，估計尺寸為300B，100B，200B和A JOIN語句A JOIN B JOIN C ，則將其轉換為B JOIN C JOIN A
注意：您可能會在此代碼中註意到，我們利用表統計信息來提示改變計劃。實際上，計劃者可以使用各種統計數據來幫助其轉換，例如表尺寸，行大小，無效，直方圖等。
例如，可以看到我們的規則，例如計劃
圖TD
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃6->組＃5
加入重新訂購轉換後，導致
圖TD
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
expr＃8 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
Expr＃8->組＃2
Expr＃8->組＃7
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃7
expr＃7 [“加入”]
結尾
Expr＃7->組＃1
Expr＃7->組＃3
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃6->組＃5
樣式Expr＃8中風寬度：4PX，中風：橙色
樣式Expr＃7中風寬度：4PX，中風：橙色
LinkStyle 2中風寬度：4PX，中風：橙色
LinkStyle 6中風寬度：4PX，中風：橙色
LinkStyle 3中風寬度：4PX，中風：橙色
LinkStyle 7中風寬度：4PX，中風：橙色
我們可以看到tbl2 JOIN tbl1 JOIN tbl3是由tbl1 JOIN tbl2 JOIN tbl3是由轉換生成的（新添加的節點和邊緣由Orange Lines表示）
請參閱X3TableJoinreOrderBysize.scala以獲取完整實現
現在我們可以將轉型規則放在一個地方
private val transformationRules : Seq [ Seq [ TransformationRule ]] = Seq (
Seq ( new ProjectionPushDown ),
Seq ( new X3TableJoinReorderBySize )
)並運行它們來探索等效組
for (r <- transformationRules.indices) {
exploreGroup(ctx.rootGroup, transformationRules(r), r + 1 )
}例如，計劃
圖TD
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組6
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃6->組＃5
探索後，將導致此圖
圖TD
子圖組＃8
expr＃8 [“掃描TBL2（ID，field1，field2）”]
結尾
子圖組11
expr＃11 [“加入”]
Expr＃14 [“加入”]
結尾
Expr＃11->組＃7
Expr＃11->組＃10
Expr＃14->組＃8
Expr＃14->組＃12
子圖組＃2
expr＃2 [“掃描TBL2”]
結尾
子圖組5
expr＃5 [“加入”]
expr＃16 [“加入”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
Expr＃16->組＃2
Expr＃16->組＃13
子圖組＃4
expr＃4 [“加入”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃13
Expr＃15 [“加入”]
結尾
Expr＃15->組＃1
Expr＃15->組＃3
子圖組＃7
expr＃7 [“掃描TBL1（ID，field1）”]
結尾
子圖組＃1
expr＃1 [“掃描TBL1”]
結尾
子圖組＃10
expr＃10 [“加入”]
結尾
Expr＃10->組＃8
Expr＃10->組＃9
子圖組＃9
expr＃9 [“掃描TBL3（ID，field2）”]
結尾
子圖組＃3
expr＃3 [“掃描TBL3”]
結尾
子圖組12
Expr＃13 [“加入”]
結尾
Expr＃13->組＃7
Expr＃13->組＃9
子圖組6
expr＃12 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
expr＃6 [“ project tbl1.id，tbl1.field1，tbl2.id，tbl2.field1，tbl2.field2，tbl3.id，tbl3.field2，tbl3.field2”]
結尾
Expr＃12->組＃11
Expr＃6->組＃5
樣式Expr＃12中風寬度：4PX，中風：橙色
樣式Expr＃8中風寬度：4PX，中風：橙色
樣式expr＃10中風寬度：4PX，中風：橙色
樣式Expr＃13中風寬度：4PX，中風：橙色
樣式Expr＃14筆寬度：4PX，中風：橙色
樣式Expr＃11中風寬度：4PX，中風：橙色
樣式Expr＃9中風寬度：4PX，中風：橙色
樣式expr＃15筆劃寬度：4PX，中風：橙色
樣式Expr＃7中風寬度：4PX，中風：橙色
樣式expr＃16筆寬度：4PX，中風：橙色
LinkStyle 0中風寬度：4PX，中風：橙色
LinkStyle 15筆寬度：4PX，中風：橙色
Linkstyle 12中風寬度：4PX，中風：橙色
LinkStyle 1中風寬度：4PX，中風：橙色
LinkStyle 16筆寬度：4PX，中風：橙色
LinkStyle 13中風寬度：4PX，中風：橙色
LinkStyle 2中風寬度：4PX，中風：橙色
LinkStyle 6中風寬度：4PX，中風：橙色
LinkStyle 3中風寬度：4PX，中風：橙色
LinkStyle 10筆寬度：4PX，中風：橙色
LinkStyle 7中風寬度：4PX，中風：橙色
LinkStyle 14中風寬度：4PX，中風：橙色
LinkStyle 11中風寬度：4PX，中風：橙色
有關更多詳細信息，請參見Volcanoplanner.scala
在探索階段之後，我們現在擁有一個完全擴展的樹，其中包含所有可能的計劃，現在是優化階段。
在此階段，我們將為根系找到最佳計劃。優化過程如下：
這是一個例子
圖TD
子圖組＃2 [“組＃2（成本= 1）”]
expr＃2 [“ expr＃2（成本= 1）”]
結尾
子圖組＃5 [“組＃5（成本= 3）”]
expr＃5 [“ expr＃5（成本= max（3,2）= 3”]
結尾
Expr＃5->組＃1
Expr＃5->組＃4
子圖組＃4 [“組＃4（成本= 2）”]
expr＃4 [“ expr＃4（成本= max（1,2）= 2）”]
expr＃7 [“ expr＃7（成本= 1+2 = 3）”]
結尾
Expr＃4->組＃2
Expr＃4->組＃3
子圖組＃1 [“組＃1（成本= 3）”]
expr＃1 [“ expr＃1（成本= 3）”]
結尾
子圖組＃3 [“組＃3（成本= 2）”]
expr＃3 [“ expr＃3（成本= 2）”]
結尾
子圖組＃6 [“組＃6（成本= 4.5）”]
expr＃6 [“ expr＃6（成本= 3*1.5 = 4.5）”]
結尾
Expr＃6->組＃5
子圖組＃8 [“組＃8（成本= 1）”]
expr＃8 [“ expr＃8（成本= 1）”]
結尾
子圖組＃9 [“組＃9（成本= 2）”]
expr＃9 [“ expr＃9（成本= 2）”]
結尾
Expr＃7->組＃8
Expr＃7->組＃9
例如，使用max功能， Expr#4成本由其子小組成本（ Group#2和Group#3 ）計算得出。另一個例子是Group#4 ，其成本是通過計算其等效表達式成本之間的最小值來計算的。
由於優化階段的目標是鑑於探索的組表達式製定最佳的物理計劃。我們可以定義物理計劃如下：
sealed trait PhysicalPlan {
def operator () : Operator
def children () : Seq [ PhysicalPlan ]
def cost () : Cost
def estimations () : Estimations
def traits () : Set [ String ]
}
operator是用於執行計劃的物理操作員，我們將在後面的部分中介紹它。然後， children是兒童計劃節點的列表，他們用來參與成本計算過程。第三個屬性是cost ， cost是對象持有成本信息（例如CPU成本，內存成本，IO成本等）。 estimations是持有該計劃的估計統計信息（例如行計數，行大小等），它也參與了成本計算。最後， traits是一組物理特徵，它影響實施規則，以影響物理計劃生成過程。
接下來，我們可以實現物理節點類：
case class Scan (
operator : Operator ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq .empty // scan do not receive any child
}
case class Project (
operator : Operator ,
child : PhysicalPlan ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq (child)
}
case class Join (
operator : Operator ,
leftChild : PhysicalPlan ,
rightChild : PhysicalPlan ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq (leftChild, rightChild)
}
有關完整實施，請參見物理計劃
優化階段的第一件事，即，我們必須實施實施規則。實施規則是從邏輯計劃轉換為實體計劃而無需執行的規則。
由於我們不是直接執行計劃者中的物理計劃，因此我們將返回物理計劃構建器，也更容易自定義每個節點的成本函數。
這是實施規則的接口：
trait PhysicalPlanBuilder {
def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ]
}
trait ImplementationRule {
def physicalPlanBuilders ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ]
}
在這裡，鑑於孩子的物理計劃， PhysicalPlanBuilder商是用於構建物理計劃的界面。
例如，邏輯聯接具有2個物理實現，哈希和合併加入
圖TD
兒童＃1 [“孩子＃1”]
孩子＃2 [“孩子＃2”]
孩子＃3 [“孩子＃3”]
孩子＃4 [“孩子＃4”]
hash_join [`hash加入
成本= f（成本（兒童＃1），費用（兒童＃2））
``]]
merge_join [“`合併加入
成本= g（成本（兒童＃3），成本（兒童＃4））
``]]
hash_join->孩子＃1
hash_join->孩子＃2
Merge_join->孩子＃3
MERGE_JOIN->孩子＃4
the HASH JOIN cost is using function f() to calculate cost, and MERGE JOIN is using function g() to calculate cost, both are using its children as function parameters. So it's easier to code if we're returning just the phyiscal plan builder from the implementation rule instead of the physical plan.
As we've said before, the optimization process is described as following:
And here is the code:
private def implementGroup ( group : Group , combinedRule : ImplementationRule )(
implicit ctx : VolcanoPlannerContext
) : GroupImplementation = {
group.implementation match {
case Some (implementation) => implementation
case None =>
var bestImplementation = Option .empty[ GroupImplementation ]
group.equivalents.foreach { equivalent =>
val physicalPlanBuilders = combinedRule.physicalPlanBuilders(equivalent)
val childPhysicalPlans = equivalent.children.map { child =>
val childImplementation = implementGroup(child, combinedRule)
child.implementation = Option (childImplementation)
childImplementation.physicalPlan
}
// calculate the implementation, and update the best cost for group
physicalPlanBuilders.flatMap(_.build(childPhysicalPlans)).foreach { physicalPlan =>
val cost = physicalPlan.cost()
bestImplementation match {
case Some (currentBest) =>
if (ctx.costModel.isBetter(currentBest.cost, cost)) {
bestImplementation = Option (
GroupImplementation (
physicalPlan = physicalPlan,
cost = cost,
selectedEquivalentExpression = equivalent
)
)
}
case None =>
bestImplementation = Option (
GroupImplementation (
physicalPlan = physicalPlan,
cost = cost,
selectedEquivalentExpression = equivalent
)
)
}
}
}
bestImplementation.get
}
}This code is an exhaustive search code, which is using recursive function to traverse all nodes. At each node (group), the function is called once to get its best plan while also calculate the optimal cost of that group.
Finally, the best plan for our query is the best plan of the root group
val implementationRules = new ImplementationRule {
override def physicalPlanBuilders (
expression : GroupExpression
)( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
expression.plan match {
case node @ Scan (_, _) => implement. Scan (node)
case node @ Project (_, _) => implement. Project (node)
case node @ Join (_, _, _) => implement. Join (node)
}
}
}
ctx.rootGroup.implementation = Option (implementGroup(ctx.rootGroup, implementationRules))See VolcanoPlanner.scala for full implementation
Here is an example of the plan after optimization, it's shown the selected logical node, the selected physical operator, and the estimated cost
圖TD
Group#6["
Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
”
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
”
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
”
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
”
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
”
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
”
Next, we will implement some implementation rules.
The first, easiest one is the implementation rule of logical PROJECT
object Project {
def apply ( node : logicalplan. Project )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
Seq (
new ProjectionImpl (node.fields)
)
}
}
class ProjectionImpl ( projection : Seq [ql. FieldID ]) extends PhysicalPlanBuilder {
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
val child = children.head
val selfCost = Cost (
estimatedCpuCost = 0 ,
estimatedMemoryCost = 0 ,
estimatedTimeCost = 0
) // assuming the cost of projection is 0
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + child.cost().estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + child.cost().estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + child.cost().estimatedTimeCost
)
val estimations = Estimations (
estimatedLoopIterations = child.estimations().estimatedLoopIterations,
estimatedRowSize = child.estimations().estimatedRowSize // just guessing the value
)
Some (
Project (
operator = ProjectOperator (projection, child.operator()),
child = child,
cost = cost,
estimations = estimations,
traits = child.traits()
)
)
}
}
The implementation rule for logical PROJECT, is returning one physical plan builder ProjectionImpl . ProjectionImpl cost calculation is simple, it just inherits the cost from the child node (because the projection is actually not doing any intensive operation). Beside that, it also updates the estimation (in this code, estimation is also inherit from the child node)
See Project.scala for full implementation
Writing implementation rule for logical JOIN is way harder than PROJECTION.
One first reason is, a logical JOIN has many physical implementation, such as HASH JOIN, MERGE JOIN, BROADCAST JOIN, etc.
The second reason is, estimating cost for physical JOIN is also hard, because it depends on lots of factors such as row count, row size, data histogram, indexes, data layout, etc.
So, to keep everything simple in this guide, I will only implement 2 physical JOIN: HASH JOIN and MERGE JOIN. The cost estimation functions are fictional (just to show how it works, I'm not trying to correct it). And in the MERGE JOIN, all data is assuming to be sorted by join key.
Here is the code:
object Join {
def apply ( node : logicalplan. Join )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
val leftFields = node.on.map(_._1).map(f => s " ${f.table.id} . ${f.id} " )
val rightFields = node.on.map(_._2).map(f => s " ${f.table.id} . ${f.id} " )
Seq (
new HashJoinImpl (leftFields, rightFields),
new MergeJoinImpl (leftFields, rightFields)
)
}
}
The HASH JOIN:
class HashJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {
private def viewSize ( plan : PhysicalPlan ) : Long = {
plan.estimations().estimatedLoopIterations * plan.estimations().estimatedRowSize
}
// noinspection ZeroIndexToHead,DuplicatedCode
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
// reorder the child nodes, the left child is the child with smaller view size (smaller than the right child if we're store all of them in memory)
val (leftChild, rightChild) = if (viewSize(children( 0 )) < viewSize(children( 1 ))) {
(children( 0 ), children( 1 ))
} else {
(children( 1 ), children( 0 ))
}
val estimatedLoopIterations = Math .max(
leftChild.estimations().estimatedLoopIterations,
rightChild.estimations().estimatedLoopIterations
) // just guessing the value
val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
val selfCost = Cost (
estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)
Some (
Join (
operator = HashJoinOperator (
leftChild.operator(),
rightChild.operator(),
leftFields,
rightFields
),
leftChild = leftChild,
rightChild = rightChild,
cost = cost,
estimations = estimations,
traits = Set .empty // don't inherit trait from children since we're hash join
)
)
}
}
We can see that the cost function of HASH JOIN is composed of its children costs and estimations
val selfCost = Cost (
estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)Next, the MERGE JOIN:
class MergeJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {
// noinspection ZeroIndexToHead,DuplicatedCode
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
val (leftChild, rightChild) = (children( 0 ), children( 1 ))
if (leftChild.traits().contains( " SORTED " ) && rightChild.traits().contains( " SORTED " )) {
val estimatedTotalRowCount =
leftChild.estimations().estimatedLoopIterations +
rightChild.estimations().estimatedLoopIterations
val estimatedLoopIterations = Math .max(
leftChild.estimations().estimatedLoopIterations,
rightChild.estimations().estimatedLoopIterations
) // just guessing the value
val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
val selfCost = Cost (
estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
estimatedMemoryCost = 0 , // no additional memory cost
estimatedTimeCost = estimatedTotalRowCount
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)
Some (
Join (
operator = MergeJoinOperator (
leftChild.operator(),
rightChild.operator(),
leftFields,
rightFields
),
leftChild = leftChild,
rightChild = rightChild,
cost = cost,
estimations = estimations,
traits = leftChild.traits() ++ rightChild.traits()
)
)
} else {
None
}
}
}
Same with HASH JOIN, MERGE JOIN also uses its children costs and estimations to calculate its cost, but with different formulla:
val selfCost = Cost (
estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
estimatedMemoryCost = 0 , // no additional memory cost
estimatedTimeCost = estimatedTotalRowCount
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)See HashJoinImpl.scala and MergeJoinImpl.scala for full implementation
You can see other rules and physical plan builders here:
Now, after done implementing the implementation rules, now we can find our best plan. Let's start over from the user query
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . idwill be converted to the logical plan
圖TD
1326583549["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"];
-425111028["JOIN"];
-349388609["SCAN tbl1"];
1343755644["JOIN"];
-1043437086["SCAN tbl2"];
-1402686787["SCAN tbl3"];
1326583549 --> -425111028;
-425111028 --> -349388609;
-425111028 --> 1343755644;
1343755644 --> -1043437086;
1343755644 --> -1402686787;
After exploration phase, it will generate lots of equivalent plans
圖TD
subgraph Group#8
Expr#8["SCAN tbl2 (id, field1, field2)"]
結尾
subgraph Group#11
Expr#11["JOIN"]
Expr#14["JOIN"]
結尾
Expr#11 --> Group#7
Expr#11 --> Group#10
Expr#14 --> Group#8
Expr#14 --> Group#12
subgraph Group#2
Expr#2["SCAN tbl2"]
結尾
subgraph Group#5
Expr#5["JOIN"]
Expr#16["JOIN"]
結尾
Expr#5 --> Group#1
Expr#5 --> Group#4
Expr#16 --> Group#2
Expr#16 --> Group#13
subgraph Group#4
Expr#4["JOIN"]
結尾
Expr#4 --> Group#2
Expr#4 --> Group#3
subgraph Group#13
Expr#15["JOIN"]
結尾
Expr#15 --> Group#1
Expr#15 --> Group#3
subgraph Group#7
Expr#7["SCAN tbl1 (id, field1)"]
結尾
subgraph Group#1
Expr#1["SCAN tbl1"]
結尾
subgraph Group#10
Expr#10["JOIN"]
結尾
Expr#10 --> Group#8
Expr#10 --> Group#9
subgraph Group#9
Expr#9["SCAN tbl3 (id, field2)"]
結尾
subgraph Group#3
Expr#3["SCAN tbl3"]
結尾
subgraph Group#12
Expr#13["JOIN"]
結尾
Expr#13 --> Group#7
Expr#13 --> Group#9
subgraph Group#6
Expr#12["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
Expr#6["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
結尾
Expr#12 --> Group#11
Expr#6 --> Group#5
style Expr#12 stroke-width: 4px, stroke: orange
style Expr#8 stroke-width: 4px, stroke: orange
style Expr#10 stroke-width: 4px, stroke: orange
style Expr#13 stroke-width: 4px, stroke: orange
style Expr#14 stroke-width: 4px, stroke: orange
style Expr#11 stroke-width: 4px, stroke: orange
style Expr#9 stroke-width: 4px, stroke: orange
style Expr#15 stroke-width: 4px, stroke: orange
style Expr#7 stroke-width: 4px, stroke: orange
style Expr#16 stroke-width: 4px, stroke: orange
linkStyle 0 stroke-width: 4px, stroke: orange
linkStyle 15 stroke-width: 4px, stroke: orange
linkStyle 12 stroke-width: 4px, stroke: orange
linkStyle 1 stroke-width: 4px, stroke: orange
linkStyle 16 stroke-width: 4px, stroke: orange
linkStyle 13 stroke-width: 4px, stroke: orange
linkStyle 2 stroke-width: 4px, stroke: orange
linkStyle 6 stroke-width: 4px, stroke: orange
linkStyle 3 stroke-width: 4px, stroke: orange
linkStyle 10 stroke-width: 4px, stroke: orange
linkStyle 7 stroke-width: 4px, stroke: orange
linkStyle 14 stroke-width: 4px, stroke: orange
linkStyle 11 stroke-width: 4px, stroke: orange
And the at optimization phase, a final best plan is chose
圖TD
Group#6["
Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
”
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
”
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
”
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
”
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
”
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
”
Now we've done building a functional query planner which can optimize the query from user, but our query plan could not run by itself. So it's the reason why now we will implement the query processor to test out our query plan.
Basically the query process receive input from the query planner, and execute them
圖LR
plan(("Physical Plan"))
storage[("Storage Layer")]
processor["Query Processor"]
plan -- execute --> processor
storage -- fetch --> processor
Volcano/iterator model is the query processing model that is widely used in many DBMS. It is a pipeline architecture, which means that the data is processed in stages, with each stage passing the output of the previous stage to the next stage.
Each stage in the pipeline is represented by an operator. Operators are functions that perform a specific operation on the data, such as selecting rows, filtering rows, or aggregating rows.
Usually, operator can be formed directly from the query plan. For example, the query
SELECT field_1
FROM tbl
WHERE field = 1will have the plan
圖TD
project["PROJECT: field_1"]
scan["SCAN: tbl"]
filter["FILTER: field = 1"]
project --> scan
filter --> project
will create a chain of operators like this:
scan = {
next() // fetch next row from table "tbl"
}
project = {
next() = {
next_row = scan.next() // fetch next row from scan operator
projected = next_row["field_1"]
return projected
}
}
filter = {
next() = {
next_row = {}
do {
next_row = project.next() // fetch next row from project operator
} while (next_row["field"] != 1)
return next_row
}
}
results = []
while (row = filter.next()) {
results.append(row)
}
notes : this pseudo code did not handle for end of result stream
The basic interface of an operator is described as following:
trait Operator {
def next () : Option [ Seq [ Any ]]
}
See Operator.scala for full implementation of all operators
Let's define a query
SELECT emp . id ,
emp . code ,
dept . dept_name ,
emp_info . name ,
emp_info . origin
FROM emp
JOIN dept ON emp . id = dept . emp_id
JOIN emp_info ON dept . emp_id = emp_info . idwith some data and stats
val table1 : Datasource = Datasource (
table = " emp " ,
catalog = TableCatalog (
Seq (
" id " -> classOf [ String ],
" code " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id
),
rows = Seq (
Seq ( " 1 " , " Emp A " ),
Seq ( " 2 " , " Emp B " ),
Seq ( " 3 " , " Emp C " )
),
stats = TableStats (
estimatedRowCount = 3 ,
avgColumnSize = Map ( " id " -> 10 , " code " -> 32 )
)
)
val table2 : Datasource = Datasource (
table = " dept " ,
catalog = TableCatalog (
Seq (
" emp_id " -> classOf [ String ],
" dept_name " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by emp_id (this is just a fake trait to demonstrate how trait works)
),
rows = Seq (
Seq ( " 1 " , " Dept 1 " ),
Seq ( " 1 " , " Dept 2 " ),
Seq ( " 2 " , " Dept 3 " ),
Seq ( " 3 " , " Dept 3 " )
),
stats = TableStats (
estimatedRowCount = 4 ,
avgColumnSize = Map ( " emp_id " -> 10 , " dept_name " -> 255 )
)
)
val table3 : Datasource = Datasource (
table = " emp_info " ,
catalog = TableCatalog (
Seq (
" id " -> classOf [ String ],
" name " -> classOf [ String ],
" origin " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id (this is just a fake trait to demonstrate how trait works)
),
rows = Seq (
Seq ( " 1 " , " AAAAA " , " Country A " ),
Seq ( " 2 " , " BBBBB " , " Country A " ),
Seq ( " 3 " , " CCCCC " , " Country B " )
),
stats = TableStats (
estimatedRowCount = 3 ,
avgColumnSize = Map ( " id " -> 10 , " name " -> 255 , " origin " -> 255 )
)
)The cost model is optimized for CPU
val costModel : CostModel = ( currentCost : Cost , newCost : Cost ) => {
currentCost.estimatedCpuCost > newCost.estimatedCpuCost
}Now, executing the query by running this code:
val planner = new VolcanoPlanner
QueryParser .parse(query) match {
case Left (err) => throw err
case Right (parsed) =>
val operator = planner.getPlan(parsed)
val result = Utils .execute(operator)
// print result
println(result._1.mkString( " , " ))
result._2.foreach(row => println(row.mkString( " , " )))
}it will print:
emp.id,emp.code,dept.dept_name,emp_info.name,emp_info.origin
1,Emp A,Dept 1,AAAAA,Country A
1,Emp A,Dept 2,AAAAA,Country A
2,Emp B,Dept 3,BBBBB,Country A
3,Emp C,Dept 3,CCCCC,Country B
Voila, We've done building a fully functional query planner and query engine :). You can start writing one for your own, good luck
See Demo.scala for full demo code
Thanks for reading this, this guide is quite long, and not fully correct, but I've tried my best to write it as understandably as possible ?
