Skip to main content

第 7 章 查询优化（Query Optimization）

原文：Readings in Database Systems, Fifth Edition (2015)，Chapter 7: Query Optimization，Introduced by Joe Hellerstein。原书文本采用 CC BY-NC-SA 4.0 许可；本译文按同一许可发布。

导读：Joe Hellerstein

选读论文​

  • Goetz Graefe and William J. McKenna. “The Volcano Optimizer Generator: Extensibility and Efficient Search.” ICDE, 1993.
  • Ron Avnur and Joseph M. Hellerstein. “Eddies: Continuously Adaptive Query Processing.” SIGMOD, 2000.
  • Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, Miso Cilimdzic. “Robust Query Processing Through Progressive Optimization.” SIGMOD, 2004.

查询优化是数据库技术的标志性组件之一，它是连接声明式语言和高效执行的桥梁。查询优化器以难以实现好而闻名，是 DBMS 中最困难的部分之一；因此，它们仍然是成熟商业 DBMS 的明显差异化因素。相比之下，最好的开源关系数据库优化器也有限，有些优化器相对天真，只能处理最简单的查询。

重要的是要记住，没有任何查询优化器真正产生“最优”计划。第一，它们都使用估计技术来猜测真实计划代价，而众所周知，这些估计技术中的错误可能膨胀；在某些情况下，可能糟糕到和随机猜测一样 [88]。第二，优化器使用启发式规则来限制自己选择的计划搜索空间，因为这个问题是 NP-hard [86]。最近受到显著关注的一个假设，是传统使用二表连接算子；已有研究表明，在某些情况下，这在理论上劣于新的多路连接算法 [121]。

尽管有这些警告，关系查询优化已经证明是成功的，并且使关系数据库系统能够在实践中相当好地服务广泛的日常用例。数据库厂商已经投入多年时间，使它们的优化器能在一系列用例上可靠运行。用户也已经学会接受连接数量上的限制。总体而言，优化器仍然让声明式 SQL 查询在大多数用途上远比命令式代码更好。

除了难以构建和调优之外，严肃的查询优化器还倾向于随着时间越来越复杂，因为它们要演化以处理更丰富的工作负载和更多边界情况。数据库查询优化的研究文献实际上已经自成一个领域，充满技术细节，其中许多细节都由 IBM、Microsoft 等成熟厂商的研究人员在文献中讨论过，这些研究人员与产品团队紧密合作。在本书中，我们关注大图景：查询优化曾经考虑过的主要架构，以及这些架构如何随时间被重新评估。

Volcano/Cascades​

我们从当前技术状态开始。数据库研究早期有两种查询优化参考架构，覆盖了今天大多数严肃的优化器实现。第一种是第 3 章描述的 Selinger 等人的 System R 优化器。System R 优化器是教科书材料，已经在许多商业系统中实现；每个数据库研究者都应详细理解它。第二种是 Goetz Graefe 及其合作者在一系列研究项目中逐步完善的架构：Exodus、Volcano 和 Cascades。Graefe 的工作在研究文献或教材中被覆盖的频率不如 System R 工作高，但在实践中使用广泛，尤其是在 Microsoft SQL Server 中，据说也存在于许多其他商业系统中。Graefe 关于这个主题的论文带有某种内部人士风味，面向那些了解并关心实现查询优化器的人。我们为本书选择 Volcano 论文，是因为它是这项工作中最容易接近的代表，但爱好者也应该阅读 Cascades 论文 [65]；它不仅提出并解决了 Volcano 的若干详细缺陷，而且是该方法最新的、因而也是标准的参考。最近出现了两个开源 Cascades 风格优化器：Greenplum 的 Orca 优化器现在是 Greenplum 开源的一部分，Apache Calcite 则是一个可与多个后端查询执行器和语言一起使用的优化器，包括 LINQ。

Graefe 的优化器架构主要因两个原因值得注意。第一，它被明确设计为可扩展。Volcano 值得被认为相当前瞻：它远早于 MapReduce 和大数据栈，就探索了数据流可用于广泛数据密集型应用的想法。因此，Graefe 优化器不仅仅用于把 SQL 编译成数据流迭代器计划。它们可以为其他输入语言和执行目标参数化；最近几年，随着一方面出现专门化数据模型和语言（见第 2 章和第 9 章），另一方面出现专门化执行引擎（第 5 章），这是一个高度相关的主题。第二项创新，是这些优化器使用自顶向下或目标导向的搜索策略，在可能计划空间中寻找最便宜的计划。这个设计选择与 Graefe 设计中的可扩展 API 相关，但并非内在必然：Starburst 系统展示了如何为 Selinger 的自底向上算法实现可扩展性 [103]。查询优化中的“自顶向下”与“自底向上”之争双方都有拥护者，但没有明确赢家；递归查询处理文献中也出现过类似的自顶向下/自底向上争论，结果也差不多是平局 [128]。爱好者会感兴趣地注意到，这两类文献，也就是递归查询处理和查询优化器搜索，在 Evita Raced 优化器中被直接连接起来；该优化器通过使用递归查询作为实现优化器的语言，实现了自顶向下和自底向上的优化器搜索 [43]。

自适应查询处理​

到 20 世纪 90 年代末，若干趋势表明，查询优化的整体架构值得显著重新思考。这些趋势包括：

  • 流式数据上的连续查询。
  • Online Aggregation 等交互式数据探索方法。
  • 查询位于 DBMS 外部、且不提供可靠统计信息或性能信息的数据源。
  • 不可预测且动态的执行环境，包括弹性和多租户环境，以及传感器网络等广域分布式系统。
  • 查询中的不透明数据和用户定义函数，此时只能通过观察行为来估计统计信息。

此外，人们一直对一个理论事实存在实际担忧：对于多算子查询，计划代价估计经常不稳定 [88]。由于这些趋势，人们开始对处理查询的自适应技术产生兴趣，在这些技术中，执行计划可以在查询中途改变。我们呈现自适应查询处理设计空间中两个互补点；另有一篇长综述提供了更全面的概览 [52]。

Eddies​

我们的第二篇论文代表的 eddies 工作，非常用力地推动了自适应问题：如果查询“重规划”必须在执行中途发生，为什么不完全移除规划和执行之间的架构区别？在 eddies 方法中，优化器被封装为一个数据流算子，而这个算子本身插入在其他数据流边之间。它可以监控这些边上的数据流速率，因此动态了解它们的行为，并保留它愿意记录的任何历史。有了这种持续的信息流，它可以通过数据流路由动态控制查询规划的其余方面：可交换算子的顺序由元组通过算子的路由顺序决定（这是我们这里收录的第一篇 eddies 论文的重点）；物理算子的选择，例如连接算法、索引选择，由在流中多个替代的、可能冗余的物理算子之间路由元组来决定 [129, 51]；算子的调度则由缓冲输入并决定接下来交付哪个输出来决定 [131]。作为扩展，多个查询可以通过介入它们的数据流并共享公共算子来调度 [109]。Eddies 拦截正在进行中的查询算子数据流，把数据从输入流水线化到输出。因此，高效实现 eddy 路由很重要；Deshpande 沿着这个方向开发了实现增强 [50]。这种流水线方法的优势在于，eddies 可以在执行连接等流水线算子的中途自适应改变策略；如果查询算子非常长寿，例如在流系统中，或者某个选择非常糟糕、应该在它运行完成很久之前就放弃，这就很有用。有趣的是，最初的 Ingres 优化器也有能力按每个元组做出某些查询优化决策 [161]。

Progressive Optimization​

本节第三篇来自 IBM 的论文代表了一种更演进式的方法，它用自适应功能扩展 System R 风格优化器；这种通用技术由 Kabra 和 DeWitt [93] 开创，但在这里得到了更完整处理。Eddies 关注算子内部重优化，也就是数据“运动中”的重优化；而这项工作关注算子之间重优化，也就是数据“静止时”的重优化。一些传统关系算子，包括排序和大多数哈希连接，是阻塞式的：它们在产生任何输出之前会消耗完整输入。这提供了一个机会：在输入被消耗之后，把观察到的统计信息与优化器预测进行比较，并使用传统查询优化技术重新优化查询计划的“剩余部分”。这种方法的缺点是，在算子消耗输入期间不做重优化，因此不适用于流上的连续查询、不适用于 symmetric hash join [160] 等流水线算子，也不适用于那些计划前半部分选择了糟糕算子的长时间运行关系查询，例如从 DBMS 外部且不提供有用统计信息的数据源访问数据时 [116, 157]。

值得注意的是，这两种自适应架构原则上可以共存：eddy “只是”一个数据流算子，这意味着传统优化器可以生成一个查询计划，其中包含连接一组流式算子的 eddy，同时也可以按照第三篇论文的方法，在数据流的阻塞点执行重优化。

讨论​

这把我们带到对当前数据流架构趋势的讨论，尤其是开源大数据栈中的趋势。Google MapReduce 把关于运动中数据自适应性的讨论倒退了十年，因为它把阻塞算子作为容错机制烘焙进执行模型。21 世纪头十年的中后期，几乎不可能就优化数据流流水线进行理性讨论，因为这与 Google/Hadoop 容错模型不一致。

过去几年，关于大数据执行框架的讨论突然完全打开，迅速增长的各种数据流和查询系统正在部署，它们相似之处多于差异（Tenzing、F1、Dremel、DryadLINQ、Naiad、Spark、Impala、Tez、Drill、Flink 等）。请注意，上面列出的所有自适应优化动机问题，在今天的大数据讨论中都非常相关，但处理得并不好。

更一般地说，我会认为，无论在研究还是开源领域，“大数据”社区都过于缓慢地关注查询优化，这既损害了当前系统，也损害了查询优化领域。首先，“手工规划”的 MapReduce 编程模型作为讨论主题持续的时间远远超过了应有时间。Hadoop 和系统研究社区花了很长时间才接受 SQL 或 LINQ 这样的声明式语言是一个好的通用接口，同时可以保留低层 MapReduce 风格数据流编程作为特殊情况的“快速路径”。更令人困惑的是，即使社区开始构建 Hive 等 SQL 接口，查询优化仍然是讨论很少且实现糟糕的主题。也许这是因为好的查询优化器比查询执行器更难构建。也许这是商业数据库和开源数据库之间历史质量差距的后果。MySQL 是此前十年“数据库技术”的开源事实参考，而它有一个天真的启发式优化器。也许因此，许多（大多数？）开源大数据开发者并不理解，也不信任查询优化器技术。

无论如何，在大数据社区中，潮水正在转向。声明式查询已经作为大数据的主要接口回归，基本上所有项目都在努力开始构建至少达到 20 世纪 80 年代水平的优化器。鉴于我上面提到的问题清单，我相信未来几年我们也会看到更多创新的查询优化方法部署在新系统中。