paper-outline
paper-outline copied to clipboard
mrdrivingduck
Orca: A Modular Query Optimizer Architecture for Big Data
1. Introduction
在大数据处理的场景中，查询优化变得至关重要。原有的优化器对大数据的处理捉襟见肘。本文提出 orca 优化器专门为分析型任务设计，在以下几点上与其它优化器有所不同：
- 模块化：使用了高度可扩展的抽象元数据描述，不再像传统优化器一样是 DBMS 内核的一部分；相反，orca 可以被快速移植到其它 DBMS 中
- 扩展性：？
- 多核心：内部使用高效的多核心调度器，在多个 CPU core 上调度独立的优化子任务
- 可验证：内置正确性验证和性能验证机制，优化器可以作为一个模块被独立测试，提高工程体验
- 性能：能使查询性能提升十倍至一千倍
这篇文章 是论文作者之一写的，精要介绍了整篇论文的内容。
2. Preliminaries
2.1 Massively Parallel Processing
Pivotal 的 Greenplum 数据库是一个大规模并行处理 (MPP) 分析型数据库，采用 share-nothing 架构，每个节点有着自己的内存、操作系统和磁盘。存储和数据处理将被分布到多个独立的数据库上，它们共同工作，对外表现为一个单体数据库。Master 节点是 GPDB 的入口，客户端连接到 master 节点并提交 SQL，master 将 SQL 优化并拆分为较小的任务，分发并协同多个 segment 共同完成数据处理和存储。Master 和 segment 通过网络互联。
在查询执行期间，数据可以以多种方式在 segment 之间分布：
- Hash：元组按照 hash 计算值分布在不同 segment 上 (Redistribute Motion)
- Replicated：每个 segment 上完整存储所有的元组 (Broadcast Motion)
- Singleton：从不同的 segment 将一张表的所有元组聚集到一个节点上 (Gather Motion)
2.2 SQL on Hadoop
Hive 等项目支持将 SQL 查询编译为 MapReduce 任务，并由 Hadoop 执行。HiveQL 加速了复杂查询的编码，但是编译出的 MapReduce 任务性能低下。其它基于 Hadoop 的 SQL 优化器只能支持一小部分的 SQL 标准特性。
Pivotal 的 HAWQ 是一个具有全兼容 SQL 接口、并带有基于代价估算优化器、基于 HDFS 的引擎。
3. Orca Architecture
Orca 是一个基于级联优化框架的现代化优化器。与其它级联优化器和相应 DBMS 紧耦合不同，orca 可以运行与数据库系统之外，作为一个独立的优化器：
- 这对不同的计算框架 (MPP/Hadoop) 来说非常重要，因为只需要一个优化器就够了
- 这意味着可以将传统的关系型优化应用到新的查询框架中，如 Hadoop
- 能够独立运行优化器意味着不用运行数据库就可以进行测试
DXL
优化器与 DBMS 解耦意味着两者之间需要有信息交互的格式。Orca 提出 Data eXchange Language，使用 XML 格式对输入的查询、输出的查询计划、以及优化中需要用到的 DBMS metadata 进行编码。使用 DXL 的最直接的好处是，Orca 可以独立运行。
如图：
- Orca 的输入是一个 DXL 查询
- Orca 的输出是一个 DXL 计划
- 优化过程中，Orca 需要向 DBMS 查询一些元数据 (比如表的定义)
DBMS 为了接入 Orca，需要实现 DXL 翻译模块：
- Query2DXL：将查询树范围为 DXL 格式
- DXL2Plan：将 DXL 格式的查询计划翻译为相应 DBMS 可执行的查询计划
翻译模块在 Orca 外实现。这意味着，只要提供相应的 translator，多种系统都可以使用 Orca。
Memo
In-memory 数据结构。
Search and Job Scheduler
调度器通过以下三步产生相互依赖或并行的工作单元进行查询优化：
- Exploration：产生逻辑表达式
- Implementation：产生物理计划
- Optimization：优化
Transformations
产生等价逻辑表达式，或为已有的逻辑表达式选择物理实现。
Property Enforcement
没懂。
Metadata Cache
DBMS 的 metadata 变更不频繁，在 DBMS 和 Orca 之间反复传输开销很大。Orca 在优化器内缓存了 DBMS 的 catalog，只有在 cache 中的条目不可用，或者 catalog 发生变动时，才会重新获取。Metadata 缓存也为单独调试、测试 Orca 优化器提供了便利。
GPOS
屏蔽底层 OS 不同的 API，Orca 提供了一层被称为 GPOS 的抽象层，包含如下基础设施功能：
- 内存管理
- 并发控制原语
- 异常处理
- 文件 I/O
- 同步数据结构
5. Metadata Exchange
优化器内的每个会话在访问 metadata cache 时，由独立的 MD Accessor 服务。如果缓存缺失所需的信息，MD Accessor 负责透明地从外部的 MD Provider 向 DBMS 获取数据。在优化过程中，内存中的 metadata cache 会被 pin 住，并在优化结束后被 unpin。
另外，Orca 实现了一个基于文件的 MD Provider，可以从 DXL 文件中装载 metadata。这意味着 Orca 不需要与一个正在运行中的 DBMS 后端同时运行。
6. Verifiability
6.1 Minimal Repros
AMPERe 是一款自动抓取最小化重现信息的工具。其动机是为了在不能访问客户生产环境系统的前提下，重现、调试客户的问题。一次 AMPERe dump 将会在意料之外的错误抛出时自动触发，或者在产生次优查询计划时按需触发。AMPERe dump 包含重现问题的最少信息：
- 输入查询
- 优化器配置
- Metadata
上述信息被序列化为 DXL 格式。如果 dump 是因为异常，那么还将包含堆栈信息。
AMPERe 使得可以在 DBMS 之外重放一个优化器 session。任何 Orca 实例可以载入 dump，获取输入查询、metadata、配置参数，并调用出一个与问题触发场景相同的优化器 session。
AMPERe dump 还可以作为单独的 test case。
Testing Optimizer Accuracy
没太懂。