Orca: A Modular Query Optimizer Architecture for Big Data（翻译）

jhonye

发布于 2023-09-28 11:36:58

3070

发布于 2023-09-28 11:36:58

摘要

数据管理系统中的分析查询处理性能主要取决于系统的查询优化器的能力。数据量的增加和对处理复杂分析查询的兴趣的增加促使Pivotal构建了一个新的查询优化器。

在本文中，我们介绍了Orca的架构，这是Pivotal所有数据管理产品（包括Pivotal Greenplum Database和Pivotal HAWQ）的新查询优化器。Orca是一个综合性的开发单元，将最先进的查询优化技术与自己的原创研究相结合，形成了一个模块化和可移植的优化器架构。

除了描述整体架构外，我们还突出了几个独特的特点，并与其他系统进行了性能比较。

关键词： Query Optimization, Cost Model, MPP, Parallel Processing

前言

大数据带来了对查询优化的新兴兴趣，因为一种新型的数据管理系统在可扩展性、可用性和处理能力方面推动了前所未有的突破（例如，[9,18,20,21]），这使得数百TB甚至PB级别的大型数据集可以通过SQL或类似SQL的接口轻松进行分析。优化器的好坏差异一直被认为是巨大的[15]。然而，这些系统需要处理的数据量的增加放大了优化错误，并且比以往任何时候都更加强调查询优化的重要性。

尽管在这个领域有大量的研究，但大多数现有的商业和开源项目中的查询优化器仍然主要基于早期商业数据库开发的技术[22]，并且往往容易产生次优的结果。

意识到研究和实际实现之间存在的巨大差距，我们着手设计一种满足当前需求并为未来发展提供足够空间的架构。

在本文中，我们描述了Orca，这是我们在Greenplum/Pivotal最近的研究和开发工作的成果。Orca是一个专为高要求的分析工作负载而设计的最先进的查询优化器。它在几个重要方面与其他优化器有所区别：

模块化。通过使用高度可扩展的元数据和系统描述抽象，Orca不再局限于像传统优化器那样特定的主机系统。相反，通过其元数据提供程序SDK支持的插件，它可以快速移植到其他数据管理系统。
可扩展性。通过将查询及其优化的所有元素作为平等的一等公民来表示，Orca避免了多阶段优化的陷阱，其中某些优化被视为事后处理。多阶段优化器通常很难扩展，因为新的优化或查询结构往往与先前设置的阶段边界不匹配。
多核准备。Orca采用了高效的多核感知调度器，将个别细粒度的优化子任务分布到多个核心，以加速优化过程。
可验证性。Orca在内置机制的级别上具有特殊的验证正确性和性能的功能。除了改进工程实践外，这些工具还能够以高信心进行快速开发，并减少新功能和错误修复的周转时间。
性能。Orca是我们以前系统的重大改进，在许多情况下，查询速度提高了10倍到1000倍。

我们描述了Orca的架构，并突出了其设计所实现的一些高级功能。我们提供了各种组件的蓝图，并详细介绍了我们在实现这个项目时开创和应用的工程实践。最后，我们基于TPC-DS基准测试提供了与其他系统相比的性能结果。特别是，我们关注贡献给开源领域的查询处理系统。

本文的剩余部分组织如下。我们在第2节中介绍了计算架构的基础知识。在第3节中，我们介绍了Orca的架构并描述了其组件。第4节介绍了查询优化的工作流程。第5节描述了Orca与后端数据库系统之间如何交换元数据。我们在第6节中描述了我们构建的用于维护可验证查询优化器的工具。第7节介绍了我们的实验研究，然后在第8节讨论了相关工作。我们在第9节总结本文并给出最后的评论。

初步介绍

我们对大规模并行处理数据库（第 2.1 节）和 Hadoop 查询引擎（第 2.2 节）进行了初步介绍。

大规模并行处理（MPP）

Pivotal的Greenplum Database（GPDB）[20]是一个大规模并行处理（MPP）的分析数据库。GPDB采用了share-nothing计算架构，具有两个或多个协作处理器。每个处理器都有自己的内存、操作系统和磁盘。GPDB利用这种高性能的系统架构，将PB级数据仓库的负载分布到多个服务器或主机上，使用系统资源并行处理给定的查询。

图1 显示了GPDB的高级架构。大量数据的存储和处理通过将负载分布到多个服务器或主机上来处理，创建一个由多个单独的数据库组成的数组，所有这些数据库共同呈现一个单一的数据库映像。主节点是GPDB的入口点，客户端连接并提交SQL语句。主节点与其他数据库实例（称为段）协调工作，处理数据的处理和存储。当查询提交到主节点时，它会被优化并分解成较小的组件，分派给段一起处理并生成最终结果。互连是负责段之间的进程间通信的网络层。互连使用标准的千兆以太网交换结构。

在查询执行过程中，数据可以通过多种方式分布到段中，包括哈希分布，根据某个哈希函数将元组分布到段中；复制分布，即在每个段中存储表的完整副本；以及单例分布，即从多个段中将整个分布表聚集到单个主机（通常是主节点）。

SQL on Hadoop

在Hadoop上处理分析查询变得越来越受欢迎。最初，查询被表示为MapReduce作业，Hadoop的吸引力归功于其可扩展性和容错性。然而，在MapReduce中手动编写、优化和维护复杂查询是困难的，因此在Hadoop之上开发了类似SQL的声明性语言，如Hive [28]。HiveQL查询被编译为MapReduce作业，并由Hadoop执行。HiveQL加速了复杂查询的编码，但也表明Hadoop生态系统需要一个优化器，因为编译后的MapReduce作业性能较差。

Pivotal通过引入HAWQ [21]来应对这一挑战，它是一个基于HDFS的大规模并行SQL兼容引擎。HAWQ在其核心中采用Orca来设计高效的查询计划，最小化在Hadoop集群中访问数据的成本。HAWQ的架构将创新的最先进的基于成本的优化器与Hadoop的可扩展性和容错性相结合，以实现对PB级数据的交互式处理。

最近，包括Cloudera的Impala [17]和Facebook的Presto [7]在内的其他一些工作引入了新的优化器，以实现在Hadoop上进行SQL处理。目前，这些工作仅支持SQL标准功能的子集，并且它们的优化仅限于基于规则。相比之下，HAWQ具有完整的标准兼容SQL接口和基于成本的优化器，这两者在Hadoop查询引擎中都是前所未有的特性。我们在第7节的实验研究中说明了Orca在功能和性能方面在HAWQ与其他Hadoop SQL引擎之间的关键作用。

ORCA 架构

Orca是Pivotal数据管理产品（包括GPDB和HAWQ）的新查询优化器。Orca是基于Cascades优化框架[13]的现代自顶向下查询优化器。虽然许多Cascades优化器与它们的主机系统紧密耦合，但Orca的一个独特特性是它能够作为一个独立的优化器在数据库系统之外运行。这种能力对于支持具有不同计算架构（如MPP和Hadoop）的产品使用一个优化器至关重要。它还允许在Hadoop等新的查询处理范例中利用丰富的关系优化遗产[7,10,16,17]。此外，将优化器作为一个独立产品运行，可以在不经过数据库系统的单体结构的情况下进行精细的测试。

DXL。将优化器与数据库系统解耦需要建立一个用于处理查询的通信机制。Orca包括一个用于优化器和数据库系统之间交换信息的框架，称为Data eXchange Language（DXL）。该框架使用基于XML的语言来编码通信所需的信息，如输入查询、输出计划和元数据。在DXL上叠加的是一个简单的通信协议，用于发送初始查询结构并检索优化后的计划。DXL的一个主要优点是将Orca打包为一个独立的产品。

图2显示了Orca与外部数据库系统之间的交互。Orca的输入是一个DXL查询。Orca的输出是一个DXL计划。在优化过程中，可以查询数据库系统的元数据（例如表定义）。Orca通过允许数据库系统注册一个元数据提供者（MD Provider）来抽象元数据访问细节，该提供者负责将元数据序列化为DXL后发送给Orca。元数据也可以从包含以DXL格式序列化的元数据对象的常规文件中获取。

数据库系统需要包含以DXL格式消费/发出数据的转换器。Query2DXL转换器将查询解析树转换为DXL查询，而DXL2Plan转换器将DXL计划转换为可执行计划。这些转换器的实现完全在Orca之外进行，这使得多个系统可以通过提供适当的转换器来使用Orca。

Orca的架构具有高度的可扩展性；所有组件都可以单独替换并单独配置。图3显示了Orca的不同组件。我们简要描述这些组件如下。

备忘录（Memo）。优化器生成的计划备选方案空间被编码在一种紧凑的内存数据结构中，称为备忘录（Memo）[13]。备忘录结构由一组容器组成，称为组（groups），每个组包含逻辑上等价的表达式。备忘录组捕捉查询的不同子目标（例如对表的过滤或两个表的连接）。组成员称为组表达式，以不同的逻辑方式实现组目标（例如不同的连接顺序）。每个组表达式是一个操作符，其子节点是其他组。备忘录的这种递归结构允许紧凑地编码大量可能的计划空间，如我们在第4.1节中所示。

搜索和作业调度器。Orca使用搜索机制来浏览可能计划备选方案的空间，并确定估计成本最低的计划。搜索机制由一个专门的作业调度器启用，该调度器创建依赖或并行的工作单元，以执行查询优化的三个主要步骤：探索（exploration），生成等价的逻辑表达式；实现（implementation），生成物理计划；优化（optimization），强制执行所需的物理属性（例如排序顺序）并计算计划备选方案的成本。我们在第4.2节中详细讨论了优化作业调度的细节。

转换（Transformations）。[13]通过应用转换规则生成计划备选方案，这些规则可以生成等价的逻辑表达式（例如InnerJoin(A,B) → InnerJoin(B,A)），或者现有表达式的物理实现（例如Join(A,B) → HashJoin(A,B)）。应用转换规则的结果被复制到备忘录中，这可能会创建新的组和/或将新的组表达式添加到现有组中。每个转换规则都是一个自包含的组件，可以在Orca配置中显式地激活/停用。

属性强制执行（Property Enforcement）。Orca包括一个可扩展的框架，用于基于形式化属性规范描述查询要求和计划特性。属性具有不同的类型，包括逻辑属性（例如输出列），物理属性（例如排序顺序和数据分布）和标量属性（例如用于连接条件的列）。在查询优化过程中，每个操作符可以从其子节点请求特定的属性。优化后的子计划可以自行满足所需的属性（例如，索引扫描计划提供排序数据），或者需要在计划中插入一个强制执行器（例如，排序操作符）来提供所需的属性。该框架允许每个操作符根据子计划的属性和操作符的本地行为来控制强制执行器的放置。我们在第4.1节中更详细地描述了这个框架。

元数据缓存（Metadata Cache）。由于元数据（例如表定义）很少更改，每次查询都将其发送会产生开销。Orca在优化器端缓存元数据，并且仅在缓存中不可用或自上次加载到缓存以来发生更改时，从目录中检索其中的部分。元数据缓存还将数据库系统的细节与优化器抽象开来，这在测试和调试过程中特别有用。

GPOS（Generalized Operating System Interface）。为了与可能具有不同API的操作系统进行交互，Orca使用了一个名为GPOS的操作系统抽象层。GPOS层为Orca提供了一个广泛的基础设施，包括内存管理器、并发控制原语、异常处理、文件I/O和同步数据结构。通过使用GPOS，Orca能够与不同操作系统进行通信，而不需要直接处理操作系统特定的细节。这种抽象层的存在使得Orca能够在不同操作系统上运行，并且更容易进行移植和维护。

查询优化

我们在第4.1节中描述了Orca的优化工作流程。然后在第4.2节中展示了优化过程如何可以并行进行。

优化工作流

我们使用以下运行示例来说明查询优化的工作流程：

SELECT T1.a FROM T1, T2 WHERE T1.a = T2.b ORDER BY T1.a;

其中，T1的分布是Hashed(T1.a)，T2的分布是Hashed(T2.a)（参见第2.1节）。

清单1 显示了先前查询在DXL中的表示，其中我们给出了所需的输出列、排序列、数据分布和逻辑查询。元数据（例如表和操作符定义）使用元数据ID（Mdid）进行修饰，以便在优化过程中请求进一步的信息。Mdid是一个由数据库系统标识符、对象标识符和版本号组成的唯一标识符。例如，'0.96.1.0'表示GPDB的整数相等操作符，版本号为'1.0'。元数据版本用于使经过修改的缓存元数据对象失效。我们在第5节中更详细地讨论元数据交换。

DXL查询消息被发送到Orca，其中它被解析并转换为一个内存中的逻辑表达式树，然后被复制到备忘录中。图4 显示了备忘录的初始内容。逻辑表达式为两个表和InnerJoin操作创建了三个组。为了简洁起见，我们省略了连接条件。组0被称为根组，因为它对应于逻辑表达式的根。逻辑表达式中操作符之间的依赖关系被捕捉为组之间的引用。例如，InnerJoin[1,2]表示Group 1和Group 2作为子节点。优化过程按照以下步骤进行。

(1) 探索（Exploration）。触发生成逻辑上等价的表达式的转换规则。例如，触发了连接交换规则，将InnerJoin[1,2]生成为InnerJoin[2,1]。探索会向现有组添加新的组表达式，可能还会创建新的组。备忘录结构具有内置的重复检测机制，基于表达式拓扑结构，可以检测和消除不同转换生成的重复表达式。

(2) 统计推导（Statistics Derivation）。在探索结束时，备忘录维护了给定查询的完整逻辑空间。然后，Orca的统计推导机制被触发，为备忘录组计算统计信息。Orca中的统计对象主要是一组用于推导基数和数据倾斜估计的列直方图。统计推导是在紧凑的备忘录结构上进行的，以避免扩展搜索空间。

为了为目标组推导统计信息，Orca选择具有最高可靠统计信息交付承诺的组表达式。统计信息承诺计算是针对表达式特定的。例如，具有较少连接条件的InnerJoin表达式比具有较多连接条件的等价InnerJoin表达式更有前景（在生成多个连接顺序时可能出现这种情况）。其原因是连接条件越多，估计误差传播和放大的可能性越高。由于需要在给定表达式的所有节点上聚合置信度分数，计算基数估计的置信度分数是具有挑战性的。我们目前正在探索在紧凑的备忘录结构中计算置信度分数的几种方法。

在选择目标组中最有前景的组表达式后，Orca会递归地触发选定组表达式的子组上的统计推导。最后，通过组合子组的统计对象构建目标组的统计对象。

图5 说明了运行示例的统计推导机制。首先，进行自顶向下的遍历，其中父组表达式从其子组请求统计信息。例如，InnerJoin(T1,T2) on (a=b)请求T1.a和T2.b的直方图。所请求的直方图通过注册的元数据提供程序从目录中按需加载，解析为DXL并存储在元数据缓存中，以便为将来的请求提供服务。接下来，进行自底向上的遍历，将子组的统计对象合并为父统计对象。这将导致（可能修改过的）T1.a和T2.b的直方图，因为连接条件可能会影响列的直方图。

构建的统计对象被附加到各个组上，它们可以在优化过程中进行增量更新（例如，通过添加新的直方图）。这对于保持统计推导的成本可控性至关重要。

(3) 实现。触发创建逻辑表达式的物理实现的转换规则。例如，触发Get2Scan规则将逻辑Get转换为物理表扫描。类似地，触发InnerJoin2HashJoin和InnerJoin2NLJoin规则来生成哈希连接和嵌套循环连接的实现。

(4) 优化。在这一步中，属性被强制执行，并对计划备选方案进行成本估算。优化从向备忘录的根组提交初始优化请求开始，指定查询的要求，如结果分布和排序顺序。向组g提交请求r相当于请求在g中以根物理运算符满足r的最低成本计划。

对于每个传入的请求，每个物理组表达式根据传入的要求和运算符的本地要求将相应的请求传递给子组。在优化过程中，可能会向同一组提交许多相同的请求。Orca将计算的请求缓存到组哈希表中。只有在组哈希表中不存在时，才会计算传入的请求。此外，每个物理组表达式维护一个本地哈希表，将传入的请求映射到相应的子请求。本地哈希表在从备忘录中提取物理计划时提供了链接结构，我们将在本节后面展示。

图6 展示了运行示例中备忘录中的优化请求。初始优化请求是req. #1: {Singleton, <T1.a>}，它指定查询结果需要按照T1.a1给定的顺序汇总到主节点。我们还展示了组哈希表，其中每个请求与满足该请求的最佳组表达式（GExpr）关联，并以最低估计成本满足该请求。黑色方框表示插入备忘录的强制执行运算符，用于提供排序顺序和数据分布。Gather运算符将元组从所有段收集到主节点。GatherMerge运算符将排序的数据从所有段收集到主节点，同时保持排序顺序。Re-distribute运算符根据给定参数的哈希值将元组分布到各个段中。

图7 展示了通过InnerHashJoin[1,2]对req. #1进行的优化。对于这个请求，其中一个备选计划是基于连接条件对子组分布进行对齐，以便要连接的元组是共位的。这通过从组1请求Hashed(T1.a)分布和从组2请求Hashed(T2.b)分布来实现。两个组都被要求提供任意的排序顺序。在找到子组的最佳计划之后，InnerHashJoin组合子属性以确定生成的分布和排序顺序。请注意，组2的最佳计划需要在T2.b上进行哈希分布，因为T2最初是在T2.a上进行哈希分布的，而组1的最佳计划是一个简单的扫描，因为T1已经在T1.a上进行了哈希分布。

当确定生成的属性不满足初始要求时，需要 enforced 未满足的属性。Orca中的属性 enforcing 是一个灵活的框架，允许每个运算符根据子计划提供的属性和运算符的本地行为来定义 enforce 所需属性的行为。例如，一个保持顺序的嵌套循环连接运算符如果外部子计划已经提供了顺序，可能就不需要在连接之上再 enforce 排序顺序。

Enforcers 被添加到包含正在优化的组表达式的组中。图7 展示了通过属性enforce满足req. #1的两个可能计划。左侧的计划在段上对连接结果进行排序，然后在主节点上合并排序结果。右侧的计划将连接结果从段收集到主节点，然后对其进行排序。这些不同的备选方案被编码到备忘录中，由成本模型来区分它们的成本。

最后，根据优化请求给出的链接结构从备忘录中提取最佳计划。图6 说明了运行示例的计划提取过程。我们展示了相关组表达式的本地哈希表。每个本地哈希表将传入的优化请求映射到相应的子优化请求。

首先，在根组中查找req. #1的最佳组表达式，这将导致GatherMerge 运算符。GatherMerge 的本地哈希表中对应的子请求是req #3。req #3的最佳组表达式是Sort。因此，我们将GatherMerge链接到Sort。Sort的本地哈希表中对应的子请求是req #4。req #4的最佳组表达式是InnerHashJoin[1,2]。因此，我们将Sort链接到InnerHashJoin。按照相同的过程完成计划提取，得到图6 中显示的最终计划。

提取的计划以DXL格式序列化，并发送到数据库系统进行执行。数据库系统中的DXL2Plan转换器将DXL计划根据底层查询执行框架转换为可执行计划。

多阶段优化。我们在Orca中的正在进行的工作涉及实现多阶段优化。在Orca中，优化阶段被定义为使用一组转换规则（可选的）超时和成本阈值的完整优化工作流。当满足以下任何条件时，阶段终止：（1）找到成本低于成本阈值的计划，（2）超时发生，或者（3）转换规则的子集用尽。优化阶段的规范可以通过Orca的配置由用户提供。这种技术允许资源受限的优化，例如，将最昂贵的转换规则配置为在后续阶段运行，以避免增加优化时间。这种技术还是尽早获取查询计划以减少复杂查询的搜索空间的基础。

查询执行。最终计划的副本被分发到每个段。在分布式查询执行过程中，每个段上的分布强制执行器充当数据的发送者和接收者。例如，运行在段S上的Redistribute(T2.b)实例根据T2.b的哈希值将元组从S发送到其他段，并且还从其他段上的Redistribute(T2.b)实例接收元组。

并行查询优化

查询优化可能是数据库系统中最消耗CPU资源的过程。有效利用CPU可以产生更好的查询计划，从而提高系统性能。将查询优化并行化对于利用利用越来越多核心的先进CPU设计至关重要。

Orca是一个支持多核的优化器。优化过程被分解为称为优化作业的小工作单元。目前，Orca有七种不同类型的优化作业：

Exp(g)：生成组g中所有组表达式的逻辑等价表达式。
Exp(gexpr)：生成组表达式gexpr的逻辑等价表达式。
Imp(g)：生成组g中所有组表达式的实现。
Imp(gexpr)：生成组表达式gexpr的实现备选方案。
Opt(g, req)：返回以组g中的运算符为根，并满足优化请求req的估计成本最低的计划。
Opt(gexpr, req)：返回以gexpr为根，并满足优化请求req的估计成本最低的计划。
Xform(gexpr, t)：使用规则t转换组表达式gexpr。

对于给定的查询，可能会创建数百甚至数千个每种类型的作业实例。这给处理作业依赖关系带来了挑战。例如，一个组表达式在其子组也被优化之前无法进行优化。图8 显示了一个部分作业图，其中在优化请求req0下优化组g0触发了一个深层次的依赖作业树。依赖关系被编码为子父链接；父作业在其子作业完成之前无法完成。当子作业在进行时，父作业需要被暂停。这样，如果子作业不依赖于其他作业，它们可以利用可用的线程并行运行。当所有子作业完成时，通知暂停的父作业恢复处理。

Orca包括一个专门设计的作业调度器，从头开始最大化作业依赖图的扇出，并提供并行查询优化所需的基础设施。调度器提供API来定义可重入过程的优化作业，这些作业可以被可用的处理线程接收。它还维护作业依赖图，以识别并行性的机会（例如，在不同的组中运行转换），并在依赖的作业终止时通知暂停的作业。

在并行查询优化过程中，不同的优化请求可能会触发对Memo组进行多个并发修改的请求。为了最小化具有相同目标的作业之间的同步开销（例如，探索相同的组），作业不应该知道彼此的存在。当正在处理某个目标的优化作业时，所有具有相同目标的其他传入作业都被迫等待，直到收到正在运行的作业完成的通知。此时，暂停的作业可以获取已完成作业的结果。这个功能是通过将作业队列附加到每个组来实现的，因此只要存在具有相同目标的活动作业，传入的作业就会排队等待。

元数据交换

Orca被设计为在数据库系统之外工作。优化器与数据库系统之间的一个主要交互点是元数据交换。例如，优化器可能需要知道在给定表上是否定义了索引，以制定高效的查询计划。访问元数据是通过一组元数据提供程序实现的，这些提供程序是特定于系统的插件，用于从数据库系统中检索元数据。

图9 显示了Orca如何与不同的后端系统交换元数据。在查询优化过程中，Orca访问的所有元数据对象都被固定在内存缓存中，并在优化完成或抛出错误时解除固定。所有对元数据对象的访问都通过MD Accessor完成，它跟踪在优化会话中访问的对象，并确保在不再需要时释放它们。如果请求的元数据对象尚未在缓存中，MD Accessor还负责从外部MD提供程序透明地获取元数据。为不同的优化会话提供服务的不同MD Accessor可能具有不同的外部MD提供程序来获取元数据。

除了特定于系统的提供程序，Orca还实现了一个基于文件的MD提供程序，用于从DXL文件加载元数据，从而消除了访问实时后端系统的需求。Orca还包括一个自动化工具，用于将优化器所需的元数据收集到一个最小的DXL文件中。我们在第6.1节中展示了在后端数据库系统离线时如何使用该工具重放客户查询的优化过程。

可验证性

测试查询优化器与构建查询优化器一样具有挑战性。从早期开发阶段开始，Orca就考虑了测试。它内置了一个测试方案，使开发人员很难在添加新功能时引入回归问题，并且使测试工程师能够简单地添加测试用例以在每个构建中进行验证。此外，我们利用了几个我们构建的工具和测试框架来确保Orca的质量和可验证性，包括一个基数估计测试框架、多个不同规模的基准测试、一个可以通过反转数据库统计信息生成数据的数据生成器[24]，以及我们接下来讨论的两个独特的测试工具。

第一个工具，在第6.1节中讨论，是自动捕获和重放优化器异常的工具。

第二个工具，在第6.2节中讨论，实现了一种自动化方法来衡量优化器成本模型的准确性。

6.1 最小重现

AMPERe [3]是一种用于自动捕获最小便携可执行重现的工具。构建AMPERe的动机是能够在没有访问客户生产系统的情况下重现和调试优化器中的客户问题。

当遇到意外错误时，AMPERe会自动触发转储，但也可以按需生成以调查次优查询计划。转储捕获了重现问题所需的最小数据量，包括输入查询、优化器配置和元数据，以DXL格式序列化（参见第3节）。如果转储是由于异常而生成的，它还包括异常的堆栈跟踪信息。

列表2 显示了一个简化的AMPERe转储示例。转储只包含重现问题所需的必要数据。例如，转储捕获了MD Cache的状态，其中仅包含在查询优化过程中获取的元数据。AMPERe还具有可扩展性。Orca中的任何组件都可以向AMPERe序列化器注册自己，以在输出转储中生成附加信息。

AMPERe允许在生成转储的系统之外重放转储。任何Orca实例都可以加载转储文件，以检索输入查询、元数据和配置参数，以便调用与触发问题情况完全相同的优化会话。这个过程在图10 中描述，其中优化器从转储中加载输入查询，为元数据创建基于文件的MD提供程序，设置优化器的配置，然后启动优化线程以立即重现问题。

AMPERe还用作测试框架，其中转储文件充当包含输入查询和预期计划的测试用例。当重放转储文件时，Orca可能会生成与预期计划不同的计划（例如，由于成本模型的更改）。这种差异导致测试用例失败，并触发对计划差异的根本原因进行调查。使用这个框架，任何带有相应AMPERe转储的错误，无论是通过内部测试还是通过客户报告提交的，都可以自动转化为一个自包含的测试用例。

6.2 测试优化准确性

Orca的成本模型的准确性可能受到多种错误来源的影响，包括不准确的基数估计和未正确调整的成本模型参数。因此，成本模型对于执行计划的墙钟时间提供了不完美的预测。量化优化器的准确性对于避免由错误修复和新添加的功能引入的性能回归至关重要。

Orca包括一个名为TAQO [15]的内置工具，用于测试查询优化器的准确性。TAQO通过测量优化器的成本模型对任意两个给定计划进行正确排序的能力来评估其准确性，即具有较高估计成本的计划确实运行时间更长。例如，在图11 中，优化器正确排序了(p1,p3)，因为它们的实际成本与计算的成本估计成正比。另一方面，优化器错误排序了(p1,p2)，因为它们的实际成本与计算的成本估计成反比。

TAQO 通过对优化给定查询时优化器考虑的计划进行成本估算和执行来衡量优化器的准确性。一般来说，评估搜索空间中的每个单独计划是不可行的。这个限制可以通过从搜索空间中均匀采样计划来克服。优化请求的链接结构（参见第4.1节）为TAQO提供了基于[29]中介绍的方法构建均匀计划采样器的基础设施。

给定一个给定查询的搜索空间中的计划样本，TAQO计算基于估计成本的采样计划排序和基于实际成本的排序之间的相关性得分。相关性得分结合了多个指标，包括计划的重要性（该得分对于非常好的计划的成本估计错误惩罚优化器更多），以及计划之间的距离（该得分不会因为实际执行时间接近的计划的估计成本的微小差异而对优化器进行惩罚）。相关性得分还允许对不同数据库系统的优化器进行基准测试，以评估它们的相对质量。我们在[15]中更详细地讨论了TAQO中实施的测试方法学。

TAQO的测试方法学通过计算相关性得分来评估优化器的准确性。该得分综合考虑了多个因素，包括计划的重要性、计划之间的距离等。重要性指标惩罚优化器对于非常好的计划的成本估计错误，而距离指标则不会因为实际执行时间接近的计划的估计成本的微小差异而对优化器进行惩罚。

通过使用TAQO，可以评估不同数据库系统的优化器的相对质量。此外，TAQO还可以将带有AMPREe转储的错误自动转化为自包含的测试用例，以避免由于错误修复和新功能引入的性能回归。

更详细的TAQO测试方法学实施细节可以在[15]中找到。

实验

在我们的实验研究中，我们选择进行一个端到端的数据库系统评估，该系统配备了Orca，而不是评估Orca的各个组件，以突出我们新的查询优化器的附加价值。我们首先将Orca与Pivotal GPDB的传统查询优化器进行比较。然后，我们将Pivotal HAWQ（其核心采用了Orca）与其他流行的SQL on Hadoop解决方案进行比较。

7.1 TPC-DS 基准测试

我们的实验基于TPC-DS基准测试[1]。TPC-DS是一个广泛采用的决策支持基准测试，包含一组复杂的业务分析查询。它通过提供更丰富的模式和更多样化的业务问题（包括业务报告、即席探索、迭代查询和数据挖掘等）取代了著名的TPC-H基准测试。在我们的开发过程中，我们观察到TPC-H往往缺乏我们企业客户工作负载的复杂性。另一方面，TPC-DS具有25个表、429个列和99个查询模板，可以很好地代表现代决策支持系统，并且是测试查询优化器的优秀基准测试。TPC-DS查询中丰富的SQL语法（包括WITH子句、窗口函数、子查询、外连接、CASE语句、Intersect、Except等）对于任何查询引擎都是一个严格的SQL兼容性测试。

7.2 MPP 数据库

在这部分中，我们将Orca的性能与GPDB传统查询优化器（也称为Planner）进行比较，该优化器部分继承了其设计自PostgreSQL优化器。Planner是一个强大的优化器，多年来一直在为数百个生产系统提供良好的服务，并且在过去十年中不断改进。

7.2.1 实验设置

对于Orca和Planner之间的比较，我们使用一个由16个节点组成的集群，通过10Gbps以太网连接。每个节点配备了双路3.33GHz的Intel Xeon处理器，48GB的内存和两个RAID-5组中的十二个600GB SAS驱动器。操作系统为Red Hat Enterprise Linux 5.5。我们安装了两个隔离的GPDB相同版本的实例（一个使用Orca，另一个使用Planner）。我们使用了10TB的TPC-DS基准测试，并使用了分区表进行性能评估。

7.2.2 性能数据

我们从TPC-DS的99个模板中生成了111个查询。Orca和Planner都以原始形式支持所有这些查询，无需进行任何重写。完全的SQL兼容性提供了最大程度的BI工具兼容性，并为来自不同背景的数据分析师提供了易用性。正如我们在第7.3节的SQL on Hadoop实验中所展示的，目前许多Hadoop SQL引擎仅原生支持TPC-DS查询的一个小子集。

图12 显示了Orca相对于Planner在所有查询中的性能提升速度，超过1的速度提升比例表示Orca的性能改进。我们观察到，对于80%的查询，Orca能够生成类似或更好的查询计划。对于整个TPC-DS套件，Orca相比Planner显示了5倍的性能提升。

特别地，对于14个查询，Orca实现了至少1000倍的速度提升比例-这是由于我们在10000秒处强制执行的超时。这些查询在Planner的计划下需要超过10000秒，而在Orca的计划下只需几分钟即可完成。

Orca提供的性能改进是由以下突出特点的组合所致：

join顺序重排。Orca基于动态规划、左深连接树和基于基数的连接顺序，包含了一系列连接顺序优化方法。
子查询优化。Orca采用并扩展了一个统一的子查询表示方法，以检测深度相关的谓词，并将其提升到连接操作中，避免重复执行子查询表达式。
分区消除。Orca引入了一种新颖的实时分区表修剪框架[2]。通过扩展Orca的强制执行框架以适应新的属性，实现了这一功能。
公共表达式。Orca为WITH子句引入了一种新的生产者-消费者模型。该模型允许对复杂表达式进行一次计算，并由多个操作符共享其输出结果。

前面所述的特性之间的相互作用是通过Orca的架构和组件抽象实现的。每个特性的设计、实现和测试都尽量减少对其他特性行为的改变。这些特性的综合效益和良好的相互作用在图12 中得到了体现。

对于少数查询，与Planner相比，Orca生成的计划可能会出现最多2倍的性能下降。这些次优计划部分是由于基数估计错误或次优的成本模型参数，需要进一步调优。我们正在积极研究这些问题，并不断改进Orca。

我们还测量了使用完整的转换规则时的优化时间和Orca的内存占用。平均优化时间约为4秒，而平均内存占用约为200MB。正如我们在第4.1节中提到的，我们正在进行的工作包括实施技术来快速优化复杂查询并改善资源消耗。

7.3 SQL on Hadoop

由于其可扩展性，Hadoop迅速成为一个受欢迎的分析生态系统。近年来，许多基于Hadoop的系统都开发了具有SQL或类SQL查询接口的功能。在本节中，我们将比较由Orca驱动的Pivotal HAWQ与三个Hadoop SQL引擎（Impala [17]、Presto [7]和Stinger [16]）的性能。有关这些系统的讨论，请参阅第8节。

7.3.1 实验设置

实验是在一个由10个节点组成的集群上进行的；其中两个节点用于HDFS名称节点和SQL引擎的协调器服务，另外八个节点用于HDFS数据节点和工作节点。每个节点配备了双路2.7GHz的Intel Xeon八核处理器，64GB的内存和22个900GB的JBOD磁盘。操作系统为Red Hat Enterprise Linux 6.2。我们使用CDH 4.4和Impala 1.1.1进行Impala实验，使用Presto 0.52和Hive 0.12进行Stinger实验。我们尽最大努力调整了每个系统的最佳配置，包括启用短路读取、为工作节点分配尽可能多的内存，并为协调器服务设置一个独立节点。对于HAWQ，我们在实验中使用了Pivotal HD版本1.1。

在不同的系统中优化TPC-DS查询事实上是相当具有挑战性的，因为目前系统对SQL的支持有限。例如，Impala尚不支持窗口函数、没有LIMIT的ORDER BY语句以及一些分析函数如ROLLUP和CUBE。 Presto尚不支持非等值连接。Stinger目前不支持WITH子句和CASE语句。此外，这些系统都不支持INTERSECT、EXCEPT、不相交的连接条件和相关子查询。这些不支持的特性迫使我们排除了大量的查询。在排除不支持的查询之后，我们需要重新编写剩下的查询以解决不同系统中的解析限制。例如，Stinger和Presto不支持隐式的交叉连接和某些数据类型。经过广泛的过滤和重写，我们最终在Impala中获得了31个查询的查询计划，在Stinger中获得了19个查询的查询计划，在Presto中获得了12个查询的查询计划，总共111个查询中的一部分。

7.3.2 性能

我们最初尝试使用10TB的TPC-DS基准来评估不同的系统。然而，Stinger的大多数查询在合理的时间限制内无法返回结果，而Impala和Presto的几乎所有查询都因内存错误而失败。这主要是因为这些系统在操作符的内部状态超出内存限制时无法将部分结果溢出到磁盘上。

为了在不同系统之间获得更好的覆盖率，我们使用了256GB的TPC-DS基准，考虑到我们集群的总工作内存约为400GB（8个节点的每个节点50GB）。不幸的是，即使在这种设置下，我们仍无法成功运行Presto中的任何TPC-DS查询（尽管我们成功地在Presto中运行了更简单的连接查询）。对于Impala和Stinger，我们成功运行了一些TPC-DS查询，接下来我们将进行讨论。

图15总结了所有系统中支持的查询数量。我们展示了每个系统能够优化的查询数量（即返回查询计划），以及能够完成执行并返回查询结果的查询数量（对于256GB的数据集）。

图13和图14显示了HAWQ相对于Impala和Stinger的加速比。由于这两个系统并不支持所有查询，我们只列出了成功的查询。图13中标有“∗”的柱状图表示内存不足的查询。对于查询46、59和68，Impala和HAWQ的性能相似。

对于HAWQ具有最大加速比的查询，我们发现Impala和Stinger按照查询中明确指定的连接顺序处理，而Orca则通过基于成本的方法探索不同的连接顺序来建议最佳顺序。例如，在查询25中，Impala首先连接两个事实表store_sales和store_returns，然后将这个巨大的中间结果与另一个事实表catalog_sales连接，这是相当低效的。相比之下，Orca首先将事实表与维度表连接，以减少中间结果。总的来说，连接顺序是一个非常复杂的优化问题，需要优化器方面的广泛基础设施支持。

Impala建议用户按照连接表的大小降序编写连接。然而，这个建议忽略了表上的过滤器（可能是有选择性的），对于复杂查询给数据库用户增加了非常大的开销，并且可能不被自动生成查询的BI工具支持。查询优化器中缺乏连接顺序优化对生成的计划质量有负面影响。HAWQ加速的其他可能原因，如资源管理和查询执行，超出了本文的范围。

在这组实验中，HAWQ的平均加速比相对于Impala为6倍，相对于Stinger为21倍。需要注意的是，图13和图14中列出的查询是TPC-DS基准中相对简单的查询。其他系统尚不支持更复杂的查询（例如，带有相关子查询的查询），而Orca完全支持。当其他系统支持所有查询时，我们计划在未来重新评估TPC-DS基准的性能。

总结

通过开发Orca，我们的目标是开发一个查询优化平台，不仅代表了最先进的技术，而且还足够强大和可扩展，以支持快速开发新的优化技术和高级查询功能。

在本文中，我们描述了从零开始构建这样一个系统所需的工程努力。将一些技术保障集成到Orca中需要巨大的投资，然而，这已经以快速的开发速度和高质量的软件成果为代价，带来了显著的回报。Orca的模块化设计使其能够通过使用清晰统一的抽象来轻松适应不同的数据管理系统，将系统的能力和元数据进行编码。

参考

[1] TPC-DS. http://www.tpc.org/tpcds, 2005.

[2] L. Antova, A. ElHelw, M. Soliman, Z. Gu, M. Petropoulos, and F. Waas. Optimizing Queries over Partitioned Tables in MPP Systems. In SIGMOD, 2014.

[3] L. Antova, K. Krikellas, and F. M. Waas. Automatic Capture of Minimal, Portable, and Executable Bug Repros using AMPERe. In DBTest, 2012.

[4] K. Bajda-Pawlikowski, D. J. Abadi, A. Silberschatz, and E. Paulson. Efficient Processing of Data Warehousing Queries in a Split Execution Environment. In SIGMOD, 2011.

[5] A. Behm, V. R. Borkar, M. J. Carey, R. Grover, C. Li,N. Onose, R. Vernica, A. Deutsch, Y. Papakonstantinou, and V. J. Tsotras. ASTERIX: Towards a Scalable, Semistructured Data Platform for Evolving-world Models. Dist. Parallel Databases, 29(3), 2011.

[6] R. Chaiken, B. Jenkins, P.- ̊A. Larson, B. Ramsey,D. Shakib, S. Weaver, and J. Zhou. SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets. PVLDB, 1(2), 2008.

[7] L. Chan. Presto: Interacting with petabytes of data at Facebook. http://prestodb.io, 2013.

[8] Y. Chen, R. L. Cole, W. J. McKenna, S. Perfilov, A. Sinha, and E. Szedenits, Jr. Partial Join Order Optimization in the Paraccel Analytic Database. In SIGMOD, 2009.

[9] J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google’s Globally-distributed Database. In OSDI, 2012.

[10] D. J. DeWitt, A. Halverson, R. Nehme, S. Shankar,J. Aguilar-Saborit, A. Avanes, M. Flasza, and J. Gramling. Split Query Processing in Polybase. In SIGMOD, 2013.

[11] F. Fa ̈rber, S. K. Cha, J. Primsch, C. Bornho ̈vd, S. Sigg, and W. Lehner. SAP HANA Database: Data Management for Modern Business Applications. SIGMOD Rec., 40(4), 2012.

[12] G. Graefe. Encapsulation of Parallelism in the Volcano Query Processing System. In SIGMOD, 1990. [13] G. Graefe. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull., 18(3), 1995.

[14] G. Graefe and W. J. McKenna. The Volcano Optimizer Generator: Extensibility and Efficient Search. In ICDE, 1993.

[15] Z. Gu, M. A. Soliman, and F. M. Waas. Testing the Accuracy of Query Optimizers. In DBTest, 2012.

[16] Hortonworks. Stinger, Interactive query for Apache Hive. http://hortonworks.com/labs/stinger/, 2013.

[17] M. Kornacker and J. Erickson. Cloudera Impala: Real-Time Queries in Apache Hadoop, for Real. http://www.cloudera.com/content/cloudera/en/ products- and- services/cdh/impala.html, 2012.

[18] A. Lamb, M. Fuller, R. Varadarajan, N. Tran, B. Vandiver, L. Doshi, and C. Bear. The Vertica Analytic Database: C-store 7 Years Later. VLDB Endow., 5(12), 2012.

[19] S. Melnik, A. Gubarev, J. J. Long, G. Romer,S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: Interactive Analysis of Web-Scale Datasets. PVLDB, 3(1):330–339, 2010. [20] Pivotal. Greenplum Database. http://www.gopivotal.com/products/pivotal- greenplum- database, 2013.

[21] Pivotal. HAWQ. http://www.gopivotal.com/sites/default/files/Hawq_WP_042313_FINAL.pdf, 2013.

[22] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access Path Selection in a Relational Database Management System. In SIGMOD, 1979.

[23] S. Shankar, R. Nehme, J. Aguilar-Saborit, A. Chung,M. Elhemali, A. Halverson, E. Robinson, M. S. Subramanian, D. DeWitt, and C. Galindo-Legaria. Query Optimization in Microsoft SQL Server PDW. In SIGMOD, 2012.

[24] E. Shen and L. Antova. Reversing Statistics for Scalable Test Databases Generation. In Proceedings of the Sixth International Workshop on Testing Database Systems, pages 7:1–7:6, 2013.

[25] M. Singh and B. Leonhardi. Introduction to the IBM Netezza Warehouse Appliance. In CASCON, 2011.

[26] M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen,M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. J. O’Neil, P. E. O’Neil, A. Rasin, N. Tran, and S. B. Zdonik. C-Store: A Column-oriented DBMS. In VLDB, 2005.

[27] Teradata. http://www.teradata.com/, 2013.

[28] A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, N. Zhang, S. Anthony, H. Liu, and R. Murthy. Hive - A Petabyte Scale Data Warehouse using Hadoop. In ICDE, 2010.

[29] F. Waas and C. Galindo-Legaria. Counting, Enumerating, and Sampling of Execution Plans in a Cost-based Query Optimizer. In SIGMOD, 2000.

[30] F. M. Waas and J. M. Hellerstein. Parallelizing Extensible Query Optimizers. In SIGMOD Conference, pages 871–878, 2009.

[31] R. Weiss. A Technical Overview of the Oracle Exadata Database Machine and Exadata Storage Server, 2012.

本文系外文翻译，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

大数据

数据库性能优化

本文系外文翻译，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。