Presto Query Planing

在深入研究Presto查询规划器和基于成本的优化如何工作之前，让我们先建立一个查询，并针对这个查询进行分析。我们提供了一个示例查询作为我们研究的对象，以帮助您理解查询规划的过程。

实例使用了TPC-H数据集，汇总每个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

在计划执行之前，需要对其进行转化和分析，Presto根据语法规则校验SQL文本，下一步就是对查询进行分析：

确认查询中的Tables

表是根据catalogs以及Schemas进行组织的，因此多个表可以具有相同的名字，例如，TPC-H数据提供多个达标不同的orders表，但是他们在不同的Schema下面：sf10.orders 以及 sf100.orders
标识查询中使用的colums
如SQL中所示，orders.totalprice即明确的引用了order表中的totalprice 列，当SQL中Table中相同字段时，通常直接写Column名就可以，Presto Analyzer会确定Column来自哪个表。

确定ROW中Field的引用

 一个废弃的表达式：c.bonus可能引用c表中的bonus列，但也可能是引用c 列中的bonus field（带有命名field的结构），这个分析工作主要由Presto决定，且当有冲突时，列优先， 析需要遵循SQL语言的作用域和可见性规则， 收集到的信息，比如标识符消歧，稍后在规划过程中使用， 这样planner 就不需要再次理解理解查询语言的规则。

如您所见，Query Analyzer具有复杂的横切功能， 它的角色是非常技术性的，并且从用户的角度来看，只要查询是正确的，它对用户就是透明的，只有当查询违反SQL语法、超过用户权限或由于其他原因不正常时，Query Analyzer才会提示用户；

一旦分析完成，处理并解析了查询中的所有标识符，Presto进入下一个阶段，即Query Planning

Initial Query Planning

查询计划可以看做是获取查询结果的流程，需要注意的是SQL是一种声明式的语言，即 用户编写一个SQL来指定他们希望从系统获得的数据。 这与命令式程序有很大的不同，命令式程序通常需要指定如果处理数据，而使用SQL时，用户不指定如何处理数据以获得结果， 这部分留给Query Planner和Optimizer来确定处理所需结果数据的步骤和顺序。

这一系列步骤通常称为Query Plan。理论上，很多的查询计划可以产生相同的查询结果，但性能可能会相差很大，这就是Presto planner和Optimizer试图确定最优计划的原因。我们将那些可以产生相同执行结果的计划称为：equivalent plans
让我们考虑上面提到的那个SQL，关于这个SQL最简单的查询计划就是最接近SQL查询语法结构的，该计划如实例2所示， 正如你所知道的执行计划就是一棵树，它的执行从叶子节点开始，沿着树结构向上进行。

- 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]

查询计划的每个元素都可以简单的实现，例如 ：
TableScan访问表的底层存储并返回一个包含该表数据的结构集。
FilTer 会过滤掉一些行数据，值保留满足条件的行；
CrossJoin 对来自子节点的两个数据集进行操作， 它在这些数据集中生成所有行的组合，也可能将其中一个数据集存储在内存中，这样就不需要多次访问底层存储。

最新的Presto版本更改了查询计划中不同操作的命名。例如,TableScan 修改为 ScanProject，而Filter修改为FilterProject,但相应的功能没有该表

现在让我们考虑这个查询计划的计算复杂性。在不知道所有实际数据细节的情况下，我们无法完全把握其复杂性。但是我们可以假设，一个查询计划节点的复杂度的下限是他所生成数据的大小。因此我们使用Big Omega（Ω）来进行描述，表示最低限的近似值。如果 N，O，C以及R分别表示 nation,Orders,custoner以及region几张表里的行的数目，我们可以进行如下描述：

• TableScan[orders]读取order表，返回了O行数据，所以他的复杂度是：Ω(O)。同理其他两个TableScans分别返回N行和C行；即Ω(N) 和Ω(C)
• 在 TableScan[nation]和TableSca[orders]之上的CrossJoin 对来自nation和orders表的数据进行合并，他的复杂度是：Ω(N × O)
• 在上一层的CrossJoin将读取customer数据的TableScan[Customer]和上一个复杂度为Ω(N × O)的CrossJoin的数据进行合并，复杂度为：Ω(N × O × C).
• 位于底层的TableScan[region]复杂度为：Ω(R)。但是由于LateralJoin他被调用N次，N就是Aggregate返回的行数，所以他的复杂度是：Ω(R × N)
• Sort操作需要对N行进行排序因此他花费的时间不能少于 N × log(N)

暂时不考虑其他成本，执行计划的消耗至少是：Ω[N + O + C + (N × O)+ (N × O × C) + (R × N) + (N × log(N))]
在不知相对表大小的情况下可以将其简化为Ω[(N × O × C) + (R × N) + (N × log(N))]
如果我们假设，region是最小的表，并且nation是第二小的表，那么我们可以忽略结果的第二部分和第三部分得到最终结果：Ω(N × O × C)

代数公式讲得够多了,是时候看看这在实践中意味着什么了，让我们举个例子，一个广受欢迎的购物网站有来自200个nations的1亿用户，他们总共下了10亿份orders。那么这两个表的CrossJoin需要（20,000,000,000,000,000,000）行数据。 对于一个健壮的拥有100节点的中等集群，每个节点每秒处理100万行， 那么计算该查询对应的中间数据将花费63个世纪。

当然，Presto肯定不会去执行这样一个不现实的计划。不过一个幼稚的计划也有他的作用。这个最初的计划可以作为SQL语法和查询优化二者之前的桥梁。 查询优化的作用是将初始计划转换为一个与之等效的计划，但是该计划可以在Presto集群有限资源的情况下尽可能快地执行，至少在合理的时间内执行。

下一篇文章我们讨论一下查询优化是如何达到这个目标的，未完待续...