查询优化是数据库理论里的重要部分[1]，也是数据库实现中最困难的组件之一。所谓查询优化，就是把用户声明性的查询描述，转化为一系列查询执行计划的过程。在这个过程中，通常需要对查询开销进行估计，然后寻找最佳执行路线，这点要做完美很困难，因为前者常常会出现很大偏差，甚至导致错误的计划制定；而后者则是个NP问题，因此没有最优解，通常的做法都是简化搜索路线，采用启发式手段达到近似最优解。查询优化尽管复杂，但是在数据库领域中已经证明了自身。正是强大的查询计划制定，才使得数据库能够处理来自用户的各种不同查询。可以说，删除了查询优化和事务，正是NoSQL对数据库做的最大简化。

更细一些来说，在估计查询开销时，需要技术来计算此次查询所需要的IO和CPU开销分别为多少，这需要一些pre-computing技术来获取数据摘要，比如最常见的Data Sketching技术，获得基数，频率，最大值，最小值等方面的统计数据。而在指定查询计划方面，Goetz Graefe的两篇文章[2]和[3]是目前最具备代表意义的实现方案，称为Volcano/Cascades，不仅大量商业数据库的查询优化器实现了该方案，开源社区的作品也不乏对应实现，例如本号前篇文章中提到的HAWQ/GreenPlum里的Orca查询优化器，以及Apache Calcite这个项目，它们都是这种查询优化器方案的实施者。从采用了Calcite优化器的Hive 0.14比没采用的性能快2.5倍[4]中我们就可以看出优化器的意义。Volcano/Cascades方案的主要特点有2：一是采用了易于扩展的抽象，把SQL转化成一系列数据流操作，而这种抽象是语言无关的，在大数据时代，可以很方便的用MapReduce实现这种抽象，Graefe在九十年代就提出这种模型，非常具有前瞻意义；二是采用了自顶而下的搜索设计来寻找到最省力的执行路线—事实上，自顶而下还是自底而上搜搜，两者在数据库研究者中并没达成一致，自顶而下的搜索，是以目标为导向的，因此更加直接和易于接受。

下面简要介绍一下Volcano/Cascades查询优化方案。先来看下数据库的查询执行过程：

查询首先进入Parser，在通过语法和语义验证之后，会产生一个逻辑表达式生成树，这个树就是查询优化器的输入，而优化器的输出就是执行计划，执行计划由一系列物理操作符组成的树状结构表示，而物理操作符表示针对数据流处理的一个具体方法，输入数据流，输出也是数据流，例如：顺序扫描，hash join，nested loop join等等（这些术语跟B-Tree一样是数据库底层的嘴最基本知识，可自行检索了解）。执行计划最终送入执行引擎产生最终结果。Volcano/Cascades查询优化器内部的执行分三个步骤：

1. 生成逻辑计划空间，就是跟输入表达式基于代数等价原则等价的所有逻辑表达式。例如：A \join ( B \join C )的等价表达式有：A \join ( C \join B)，(B \join C) \join A，(C \join B) \join A ，这里，用 \join 表示关系代数里的Join操作，限于公众号文字输入的限制，真实的代数操作符应为：

   中间那个特殊符号既代表Join。

2. 生成执行计划空间，这是把逻辑表达式跟物理执行计划对应起来。例如，对于逻辑Get表达式，只有一个算法，叫顺序扫描；对于逻辑Join表达式，有两种算法，hash join和nested loop join。

3. 从执行计划空间中找到最佳的执行计划。

下图可以更加形象的描述这三个步骤：

第一阶段的生成结果，其实质上是产生一个DAG有向无环图，如下所示，这里边方框代表OR操作，圆圈代表具体逻辑操作，比如图中的Join。当把逻辑表达式扩展之后，DAG图就会膨胀到很大的空间。

下图是针对A \join B 生成的物理执行DAG，因此在第二步骤之后，初始的输入逻辑就会生成一个非常庞大的物理执行计划空间DAG，因此第三步寻找最优解的搜索空间是巨大的，需要用动态规划来求解。

在求解最优方案的过程中，开销的估计至关重要，因此这被称为Cost Based Query Optimization，查询优化器会把等价的操作分组放置，通过对DAG图自上而下的方式做剪枝最终获得启发解。只有究竟如何求解，Volcano/Cascades框架并没有具体阐明，这是各家具体实现中自行考虑的问题，例如之前本号介绍的GreenPlum的Orca，就是一种求解实现。

在Volcano/Cascades方案之后，查询优化的研究重心转移到解决新的挑战上面，比如：在外部存储环境中如何设计查询优化，此时开销的估计变得非常困难；另外，在复杂操作符上，开销估计常常会发生错误，这也给查询优化带来挑战，通常把这类查询优化解决方案叫做自适应查询优化，文献[5]是全面综述。自适应查询优化的研究对于后来出现的OLAP非常重要，像大多数的SQL on Hadoop都属于这类范畴，它们需要在外接数据源的情况下完成查询任务。Eddy方案[6]是自适应查询优化里最具代表性的方案，它的主要思想是将查询执行看作由物理操作符决定的数据流路由过程，通过动态监控数据流，根据过去的历史记录来判定未来的优化路径。

如上图所示，在这个查询中，数据流被路由到3个Join操作和一个Select操作，Eddy优化器来根据过去的数据决定数据流路由。而路由的设计是Eddy优化器的关键所在，图中还展现了一个数据结构——路由表，用来存放给定查询所有可能的路由选择，在工程实现中，会选择更加紧凑的结构比如位图来实现高效查询。总体来说，Eddy优化器有2个处理步骤：

1. 利用统计信息构造和调整路由表。统计信息可以是根据每个处理的数据单元，也可以降低频率以提高处理效率。

2. 利用路由表找到合适的路径下发数据流。需要注意的是，这里路由的选择并不一定总是确定性的，也可以带有随机——毕竟对于数据是未知的。

查询优化的理论出现很早，但在开源数据库社区，乃至大数据社区中得到重视并不是一开始就有。这还是跟数据库理论本身过于复杂有关。然而，查询优化带来的好处已经得到验证，对于OLAP数据仓库所起到的效果更大，因为OLTP所涉及到的操作通常非常短，存储引擎和数据结构，乃至索引本身的设计都至关重要，而OLAP数据仓库，由于面临更加庞大的数据需要处理，因此缺乏良好的计划将导致查询效率差距巨大。列举一下常见的SQL Over Hadoop方案，除了Hive，其余各家都是通过查询优化的设计来获得远优于Hive的性能。例如Impala，Spark SQL，Presto，Tajo，Drill，以及上文提到的Apache Calcite，这些项目都采用了查询优化，那么，它们在设计上有什么差异呢？这是个很难回答的问题，因为研究任何一个查询优化器的设计都需要长时间的代码阅读，因此本文仅仅针对部分可以找到的材料给出一些分析，如有错误或者遗漏敬请批判。

首先来看Impala，这是一个实现了cost based query optimizer的OLAP，由于Impala外接HDFS进行查询，无需数据加载过程，因此必然也是自适应的查询优化。Cost估计采用HLL做基数估计，在生成查询计划时主要以数据局部性为优化目标避免数据大量迁移，例如Join提供两类算法：Broadcast和Partition，前者用于把数据复制到所有分区做Join，通常用于其中一个表比另一个表小很多的场景，后者用于两个Join的表大小差不多，需要分区分别进行操作。两者都是Hash Join，具体采用哪种取决于哪种需要搬动的数据少。下图是一个查询优化的例子，左边表示需要对2个Hadoop表t1和t2，以及1个HBase表t3做Join，然后做聚合后排序取TopN返回，右边是生成的执行计划。由此可见，Impala的查询优化设计比较简单，对Cost的考虑主要限制在数据迁移最小化这里，因此只能说比全表扫描的结果好，但并没有从减少扫描的区域上做太多文章，所以无法跟更高级的查询计划相比。当然，这也跟Impala的设计目标一致，因为没有数据加载的过程，直接外接HDFS，是很难深入获悉数据分布的直方图信息的。

接下来看看Spark SQL，这也是一个提供了cost based query optimizer的解决方案。Spark SQL的查询优化器被称为Catalyst，它的cost model目前只针对Join操作进行评估：当Join的table已知足够小时，采用类似Impala Broadcast的方式复制数据，而该功能是Spark本身提供的。因此，Spark SQL的查询优化还相当初级，根据其论文描述，只有几百行代码而已，这样的工作显然只是个开始。

下一个是Presto，根据其Wiki描述[7]，这也是一个cost based query optimizer，但对cost如何评估没有任何信息。从描述上看，cost based query optimizer是Presto的未来改进计划，目前还不存在。

以上是最熟知的开源方案，下边来说一个冷门的项目Apache Tajo，作为一个SQL on Hadoop，虽然是Apache顶级项目，但却鲜有人过问，以至于几乎认为它是个没有亮点的产品。然而看过资料之后才发觉，Tajo的查询优化算得上完善。

在作者的访谈中[8]特地提到，Tajo的查询优化来自学术界多年的成果，提供了多达40种的物理操作符算子，这远比Impala，Spark SQL丰富，因此也提供了更大的优化空间。尽管Tajo外接HDFS存储，但它跟Impala/Spark SQL/Presto这些不同，并不是说数据存在于HDFS上面，安装好Tajo后就可以直接来查询，因此通过数据注入，Tajo可以在该过程中对数据具备更多的洞察力，这为cost model的估计提供了更丰富的支撑，更好的查询优化也成为可能，因此也就具备了理论上更佳的查询性能。

至于本号之前提到的HAWQ，虽然这是一种SQL On Hadoop的方案，它也是只采用Hadoop作为存储，因此依赖数据注入，提供完备的cost based query optimization就成为可能，所以HAWQ宣称查询性能可以十多倍于Impala并不是不可能做到的事情。在数据库资深研究人员Daniel Abadi的VLDB演讲中，就把HAWQ和Impala/Hive这些分开放置[8]，想必就是该原因。

查询优化是数据库设计的重要理论，没有相关背景知识，直接去研究开源项目就会造成困扰，正如本号之前试图读懂HAWQ的优化器设计Orca一样。然而，数据库的原理长期在开源社区中得到忽视，而真正优秀的云端产品往往基本不开源，随着更多的理论为广大工程人员所掌握，开源社区也会在目前产品上推出更加优秀的设计，毕竟，从目前来看，不论是开源的OLTP，还是OLAP，都还远远没有达到跟理想接近的地步，对于基础架构有要求的公司，特别是云服务企业，则需要具备憋大招的决心，而能力则一定是在决心后可以养成的。

[1] http://www.redbook.io/index.html

[2] Goetz Graefe and William J. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE, 1993.

[3] Goetz Graefe. The cascades framework for query optimization. IEEE Data Eng. Bull. 18, 3 (1995)

[4] http://zh.hortonworks.com/blog/hive-0-14-cost-based-optimizer-cbo-technical-overview/

[5] Deshpande, A., Ives, Z. and Raman, V. Adaptive query processing. Foundations and Trends in Databases. 1, 1 (2007), 1-140

[6] Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.

[7] https://github.com/facebook/presto/wiki/New-Optimizer

[8] http://www.hadoopsphere.com/2015/02/building-open-source-data-warehouse.html

[9] http://www.slideshare.net/abadid/sqlonhadoop-tutorial