在深入研究Presto查詢規(guī)劃器和基于成本的優(yōu)化如何工作之前，讓我們先建立一個查詢，并針對這個查詢進行分析。我們提供了一個示例查詢作為我們研究的對象，以幫助您理解查詢規(guī)劃的過程。

實例使用了TPC-H數(shù)據(jù)集，匯總每個nation的所有order值并列出排名前五的。

-- 實例一：
SELECT
    (SELECT name FROM region r WHERE regionkey = n.regionkey) AS region_name,
    n.name AS nation_name,
    sum(totalprice) orders_sum
FROM nation n, orders o, customer c
WHERE n.nationkey = c.nationkey
    AND c.custkey = o.custkey
GROUP BY n.nationkey, regionkey, n.name
ORDER BY orders_sum DESC
LIMIT 5;

如上SQL所示：
子查詢：(SELECT name FROM region WHERE regionkey = n.regionkey)目的是從region表中提取region_name

Parsing and Analysis

在計劃執(zhí)行之前，需要對其進行轉(zhuǎn)化和分析，Presto根據(jù)語法規(guī)則校驗SQL文本，下一步就是對查詢進行分析：

確認查詢中的Tables

表是根據(jù)catalogs以及Schemas進行組織的，因此多個表可以具有相同的名字，例如，TPC-H數(shù)據(jù)提供多個達標不同的orders表，但是他們在不同的Schema下面：sf10.orders 以及 sf100.orders
標識查詢中使用的colums
如SQL中所示，orders.totalprice即明確的引用了order表中的totalprice 列，當(dāng)SQL中Table中相同字段時，通常直接寫Column名就可以，Presto Analyzer會確定Column來自哪個表。

確定ROW中Field的引用

?一個廢棄的表達式：c.bonus可能引用c表中的bonus列，但也可能是引用c 列中的bonus field（帶有命名field的結(jié)構(gòu)），這個分析工作主要由Presto決定，且當(dāng)有沖突時，列優(yōu)先， 析需要遵循SQL語言的作用域和可見性規(guī)則， 收集到的信息，比如標識符消歧，稍后在規(guī)劃過程中使用， 這樣planner 就不需要再次理解理解查詢語言的規(guī)則。

如您所見，Query Analyzer具有復(fù)雜的橫切功能， 它的角色是非常技術(shù)性的，并且從用戶的角度來看，只要查詢是正確的，它對用戶就是透明的，只有當(dāng)查詢違反SQL語法、超過用戶權(quán)限或由于其他原因不正常時，Query Analyzer才會提示用戶；

一旦分析完成，處理并解析了查詢中的所有標識符，Presto進入下一個階段，即Query Planning

Initial Query Planning

查詢計劃可以看做是獲取查詢結(jié)果的流程，需要注意的是SQL是一種聲明式的語言，即 用戶編寫一個SQL來指定他們希望從系統(tǒng)獲得的數(shù)據(jù)。 這與命令式程序有很大的不同，命令式程序通常需要指定如果處理數(shù)據(jù)，而使用SQL時，用戶不指定如何處理數(shù)據(jù)以獲得結(jié)果， 這部分留給Query Planner和Optimizer來確定處理所需結(jié)果數(shù)據(jù)的步驟和順序。

這一系列步驟通常稱為Query Plan。理論上，很多的查詢計劃可以產(chǎn)生相同的查詢結(jié)果，但性能可能會相差很大，這就是Presto planner和Optimizer試圖確定最優(yōu)計劃的原因。我們將那些可以產(chǎn)生相同執(zhí)行結(jié)果的計劃稱為：equivalent plans
讓我們考慮上面提到的那個SQL，關(guān)于這個SQL最簡單的查詢計劃就是最接近SQL查詢語法結(jié)構(gòu)的，該計劃如實例2所示， 正如你所知道的執(zhí)行計劃就是一棵樹，它的執(zhí)行從葉子節(jié)點開始，沿著樹結(jié)構(gòu)向上進行。

- Limit[5]
    - Sort[orders_sum DESC]
        - LateralJoin[2]
            - Aggregate[by nationkey...; orders_sum := sum(totalprice)]
                - Filter[c.nationkey = n.nationkey AND c.custkey = o.custkey]
                    - CrossJoin
                        - CrossJoin
                            - TableScan[nation]
                            - TableScan[orders]
                        - TableScan[customer]
                - EnforceSingleRow[region_name := r.name]
                    - Filter[r.regionkey = n.regionkey]
                        - TableScan[region]

查詢計劃的每個元素都可以簡單的實現(xiàn)，例如 ：
TableScan訪問表的底層存儲并返回一個包含該表數(shù)據(jù)的結(jié)構(gòu)集。
FilTer 會過濾掉一些行數(shù)據(jù)，值保留滿足條件的行；
CrossJoin 對來自子節(jié)點的兩個數(shù)據(jù)集進行操作， 它在這些數(shù)據(jù)集中生成所有行的組合，也可能將其中一個數(shù)據(jù)集存儲在內(nèi)存中，這樣就不需要多次訪問底層存儲。

最新的Presto版本更改了查詢計劃中不同操作的命名。例如,TableScan 修改為 ScanProject，而Filter修改為FilterProject,但相應(yīng)的功能沒有該表

現(xiàn)在讓我們考慮這個查詢計劃的計算復(fù)雜性。在不知道所有實際數(shù)據(jù)細節(jié)的情況下，我們無法完全把握其復(fù)雜性。但是我們可以假設(shè)，一個查詢計劃節(jié)點的復(fù)雜度的下限是他所生成數(shù)據(jù)的大小。因此我們使用Big Omega（Ω）來進行描述，表示最低限的近似值。如果 N，O，C以及R分別表示 nation,Orders,custoner以及region幾張表里的行的數(shù)目，我們可以進行如下描述：

• TableScan[orders]讀取order表，返回了O行數(shù)據(jù)，所以他的復(fù)雜度是：Ω(O)。同理其他兩個TableScans分別返回N行和C行；即Ω(N) 和Ω(C)
• 在 TableScan[nation]和TableSca[orders]之上的CrossJoin 對來自nation和orders表的數(shù)據(jù)進行合并，他的復(fù)雜度是：Ω(N × O)
• 在上一層的CrossJoin將讀取customer數(shù)據(jù)的TableScan[Customer]和上一個復(fù)雜度為Ω(N × O)的CrossJoin的數(shù)據(jù)進行合并，復(fù)雜度為：Ω(N × O × C).
• 位于底層的TableScan[region]復(fù)雜度為：Ω(R)。但是由于LateralJoin他被調(diào)用N次，N就是Aggregate返回的行數(shù)，所以他的復(fù)雜度是：Ω(R × N)
• Sort操作需要對N行進行排序因此他花費的時間不能少于 N × log(N)

暫時不考慮其他成本，執(zhí)行計劃的消耗至少是：Ω[N + O + C + (N × O)+ (N × O × C) + (R × N) + (N × log(N))]
在不知相對表大小的情況下可以將其簡化為Ω[(N × O × C) + (R × N) + (N × log(N))]
如果我們假設(shè)，region是最小的表，并且nation是第二小的表，那么我們可以忽略結(jié)果的第二部分和第三部分得到最終結(jié)果：Ω(N × O × C)

代數(shù)公式講得夠多了,是時候看看這在實踐中意味著什么了，讓我們舉個例子，一個廣受歡迎的購物網(wǎng)站有來自200個nations的1億用戶，他們總共下了10億份orders。那么這兩個表的CrossJoin需要（20,000,000,000,000,000,000）行數(shù)據(jù)。 對于一個健壯的擁有100節(jié)點的中等集群，每個節(jié)點每秒處理100萬行， 那么計算該查詢對應(yīng)的中間數(shù)據(jù)將花費63個世紀。

當(dāng)然，Presto肯定不會去執(zhí)行這樣一個不現(xiàn)實的計劃。不過一個幼稚的計劃也有他的作用。這個最初的計劃可以作為SQL語法和查詢優(yōu)化二者之前的橋梁。 查詢優(yōu)化的作用是將初始計劃轉(zhuǎn)換為一個與之等效的計劃，但是該計劃可以在Presto集群有限資源的情況下盡可能快地執(zhí)行，至少在合理的時間內(nèi)執(zhí)行。

Optimization Rules

接下來討論一下查詢優(yōu)化是如何達到這個目標的。

Predicate Pushdown
Predicate pushdown 即所謂的謂詞下推，他可能是最重要也是最容易理解的優(yōu)化策略，它的做法是盡可能的將過濾條件靠近數(shù)據(jù)源，使得在執(zhí)行查詢之前盡可能的過濾無用的數(shù)據(jù)。針對上面的例子如果應(yīng)用該優(yōu)化策略的話，結(jié)果如下所示：
之前的執(zhí)行計劃（一部分：）

...
- Aggregate[by nationkey...; orders_sum := sum(totalprice)]
    - Filter[c.nationkey = n.nationkey AND c.custkey = o.custkey] // original filter
        - CrossJoin
            - CrossJoin
                - TableScan[nation]
                - TableScan[orders]
            - TableScan[customer]
...

優(yōu)化后的執(zhí)行計劃：

...
- Aggregate[by nationkey...; orders_sum := sum(totalprice)]
    - Filter[c.nationkey = n.nationkey] // transformed simpler filter
        - InnerJoin[o.custkey = c.custkey] // added inner join
            - CrossJoin
                - TableScan[nation]
                - TableScan[orders]
            - TableScan[customer]
...

即在不改變表關(guān)聯(lián)前后關(guān)系的基礎(chǔ)上，將之前的Filter轉(zhuǎn)化為更為簡單的Filter 同時將大的CrossJoin轉(zhuǎn)化為InnerJoin，且前后兩個執(zhí)行計劃是等效的（即上文提到的equivalent plans），如果假設(shè)這樣的JOIN可以在分布式系統(tǒng)中實現(xiàn)，我們依然按照之前的約定：計算復(fù)雜度用處理數(shù)據(jù)的行數(shù)表示。那么結(jié)果就是該優(yōu)化策略將之前復(fù)雜度為Ω(N × O × C)的CrossJoin替換成了復(fù)雜度為Ω(N × O）的JOIN

如上所示謂詞下推并沒有對nation表和orders表之間的CrossJoin進行替換，主要是因為nation和orders表之間沒有關(guān)聯(lián)條件，只能使用CrossJoin，那該如何消除這個CrossJoin呢，那就要提到Cross Join Elimination

Cross Join Elimination

也許有人會疑問，既然nation和orders表之間沒有關(guān)聯(lián)條件，才導(dǎo)致兩個表關(guān)聯(lián)只能使用CrossJoin，那為什么非要先將沒有關(guān)聯(lián)條件nation和orders表進行關(guān)聯(lián)？

這主要是因為在沒有基于成本的優(yōu)化器（cost-based optimizer）時，在ELECT的SQL中，Presto通常按照表出現(xiàn)的前后順序安排表間的JOIN順序。所以才會出現(xiàn)上面的情況。

事實上在大部分情況下，CrossJoin都不是必須的，都可以進行優(yōu)化，因為基本都會對CrossJoin之后的數(shù)據(jù)進行過濾，只獲取滿足條件的數(shù)據(jù)。但CrossJoin代價是很大的，有可能永遠也無法執(zhí)行完；

Cross Join Elimination的目的就是對表之間的JOIN順序進行重新排列，以減少CrossJoin的數(shù)量，理想的情況是沒有CrossJoin。在不清楚相關(guān)表大小的情況下，如果沒有cross join elimination，那就需要用戶在寫SQL時進行控制。使用cross join elimination前后的結(jié)果如下所示：

...
    - Aggregate[by nationkey...; orders_sum := sum(totalprice)]
        - Filter[c.nationkey = n.nationkey] // filter on nationkey first
            - InnerJoin[o.custkey = c.custkey] // then inner join cutkey
                - CrossJoin
                    - TableScan[nation]
                    - TableScan[orders]
                - TableScan[customer]
...

使用cross join elimination之后：即先Join nation和customer，之后在JOIN orders

...
    - Aggregate[by nationkey...; orders_sum := sum(totalprice)]
        - InnerJoin[c.custkey = o.custkey] // reordered to custkey first
            - InnerJoin[n.nationkey = c.nationkey] // then nationkey
                - TableScan[nation]
                - TableScan[customer]
            - TableScan[orders]
...

TopN

如果SQL中有LIMIT時，通常情況下它的前面也會有Order BY子句；因為如果沒有ORDER 子句，SQL不會保證返回那些行。正如上面的查詢中我們在LIMIT之前也使用了ORDER BY；

當(dāng)執(zhí)行這樣的查詢時，Presto會對所有結(jié)果數(shù)據(jù)進行排序并返回前幾行數(shù)據(jù)。這種方法的復(fù)雜度為Θ(row_count × log(row_count))同時Θ(row_count)的內(nèi)存占用；

然而如果僅僅是為了獲取排序之后的前幾的數(shù)據(jù)，卻需要保留所有已排序的數(shù)據(jù)，這是一種浪費。因此一種優(yōu)化規(guī)則是，將后面帶有LIMIT的ORDER BY查詢轉(zhuǎn)化為TopN， 在查詢執(zhí)行期間，TopN在堆數(shù)據(jù)結(jié)構(gòu)中保存所需的行，流式的讀取數(shù)據(jù)并更新堆數(shù)據(jù)。這使得計算復(fù)雜度降低到Θ(row_count × log(limit))并且內(nèi)存占用為Θ(limit)，總體的查詢成本為： Ω[O + (R × N) + N].

Partial Aggregations

Presto不需要將orders表中的所有行傳遞給join，因為我們對單個訂單不感興趣，我們的示例SQL中是要計算每一個nation的totalprice的匯總，因此可以進行預(yù)聚合，如下所示；

...
- Aggregate[by nationkey...; orders_sum := sum(totalprice)]
    - InnerJoin[c.custkey = o.custkey]
        - InnerJoin[n.nationkey = c.nationkey]
            - TableScan[nation]
            - TableScan[customer]
        - Aggregate[by custkey; totalprice := sum(totalprice)]
            - TableScan[orders]
...

我們通過預(yù)聚合數(shù)據(jù)來減少流向下游的數(shù)據(jù)量，預(yù)聚合的結(jié)果是不完整的，但數(shù)據(jù)量會顯著的的減少，從而提升下性能；

為了提高并行性，這種預(yù)聚合的實現(xiàn)方式是不同的，該方式被稱為：Partial Aggregations。 這里，我們呈現(xiàn)的是簡化的計劃，但是在實際的EXPLAIN計劃中，這與最終的匯總不同
需要注意的是，如上所示的預(yù)聚合并非總是可以實現(xiàn)優(yōu)化，如果預(yù)聚合不能減少數(shù)據(jù)量時，查詢性能將會受到影響。出于該原因， 該優(yōu)化目前在默認情況下是禁用的，可以通過session中的push_partial_aggregation_through_join 切換啟用。默認情況下，會將預(yù)聚合放在JOIN上以減少Presto中節(jié)點間的數(shù)據(jù)傳輸量， 為了更有效的利用Partial Aggregations的優(yōu)勢，我們需要充分考慮實際情況。

Implementation Rules

到目前為止，我們介紹的規(guī)則都是優(yōu)化規(guī)則，這些規(guī)則的目標是減少查詢處理時間、減少查詢的內(nèi)存占用或減少通過網(wǎng)絡(luò)交換的數(shù)據(jù)量。但是上面的示例SQL還包含一個我們一直沒有提到的操作：lateral join；

Lateral Join Decorrelation

lateral join類似一個for-each循環(huán)，他遍歷數(shù)據(jù)集中的所有行并針對每一行執(zhí)行相應(yīng)的查詢，但是Presto并非這樣處理的。相反，Presto會將其轉(zhuǎn)換為一個left join，用SQL表示如下：
原始的SQL

SELECT
    (SELECT name FROM region r WHERE regionkey = n.regionkey) AS region_name,
    n.name AS nation_name
FROM nation n

轉(zhuǎn)化后的SQL：

SELECT
    r.name AS region_name,
     n.name AS nation_name
FROM nation n
LEFT OUTER JOIN region r ON r.regionkey = n.regionkey

但是需要注意的是，二者并非完全等價的。因為在第一個SQL中，當(dāng)region表中存在regionkey重復(fù)的數(shù)據(jù)時，查詢會出錯（只有當(dāng)region表中regionkey字段唯一時才可以有效執(zhí)行）。但是第二個查詢在此情況下可以正常執(zhí)行且不會失敗，而是生成多行數(shù)據(jù)，正因如此lateral join會在轉(zhuǎn)換時添加兩個額外的條件：首先，他對所有的數(shù)據(jù)行進行編號，以便于區(qū)分；其次，在連接之后會檢測是否有重復(fù)行，如果存在重復(fù)行，那么查詢將失敗，以保證轉(zhuǎn)換后的SQL與之前的語義完全一致。如以下示例中所示：

- TopN[5; orders_sum DESC]
    - MarkDistinct & Check
        - LeftJoin[n.regionkey = r.regionkey]
            - AssignUniqueId
                - Aggregate[by nationkey...; orders_sum := sum(totalprice)]
                    - ...
            - TableScan[region]

Semi-Join (IN) Decorrelation

可以在查詢中使用子查詢，這樣不僅可以提取所需的信息(正如我們在 lateral join示例中看到的那樣)，還可以使用in謂詞過濾行。事實上，IN可以在Where子句中使用，也可以在SELECT子句中使用，當(dāng)你在SELECT中使用IN時，并不是簡單的Boolean值的操作，這與EXISTS有很大的不同，相反，IN可以計算為true、false、或者 null

讓我們考慮這樣一個查詢，他的目的是查找來自同一國家的客戶（customer表）和產(chǎn)品供應(yīng)商（supplier表）的訂單。SQL如下：

SELECT DISTINCT o.orderkey
FROM lineitem l
JOIN orders o ON o.orderkey = l.orderkey
JOIN customer c ON o.custkey = c.custkey
WHERE c.nationkey IN (
    -- subquery invoked multiple times
    SELECT s.nationkey
    FROM part p
    JOIN partsupp ps ON p.partkey = ps.partkey
    JOIN supplier s ON ps.suppkey = s.suppkey
    WHERE p.partkey = l.partkey
);

與lateral join一樣，這可以通過循環(huán)執(zhí)行子查詢來實現(xiàn)，其中將多次調(diào)用子查詢來檢索所有suppliers的國家。

Presto沒有這樣做，相反，子查詢只計算一次，并且將子查詢中的關(guān)聯(lián)條件去掉，而是通過關(guān)聯(lián)條件將子查詢與外部查詢進行JOIN。
這樣做的重點是不要產(chǎn)生多個結(jié)果(這就要使用deduplicating aggregation)，并且正確地保留了IN語法的三值邏輯（即IN值可以是true、false、null）。

在這種情況下，deduplicating aggregation使用與連接相同的分區(qū)，因此可以以流式的執(zhí)行，無需通過網(wǎng)絡(luò)進行數(shù)據(jù)交換，占用的內(nèi)存最少。