search

mrdrivingduck / paper-outline

🔍 To record the papers I have read.
24 stars 0 forks source link

Orca: A Modular Query Optimizer Architecture for Big Data #3

Open mrdrivingduck opened 3 years ago

mrdrivingduck commented 3 years ago

PDF: orca-a-modular-query-optimizer-architecture-for-big-data.pdf

Related publications:

mrdrivingduck commented 3 years ago

1. Introduction

在大数据处理的场景中，查询优化变得至关重要。原有的优化器对大数据的处理捉襟见肘。本文提出 orca 优化器专门为分析型任务设计，在以下几点上与其它优化器有所不同：

  1. 模块化：使用了高度可扩展的抽象元数据描述，不再像传统优化器一样是 DBMS 内核的一部分；相反，orca 可以被快速移植到其它 DBMS 中
  2. 扩展性：？
  3. 多核心：内部使用高效的多核心调度器，在多个 CPU core 上调度独立的优化子任务
  4. 可验证：内置正确性验证和性能验证机制，优化器可以作为一个模块被独立测试，提高工程体验
  5. 性能：能使查询性能提升十倍至一千倍

这篇文章 是论文作者之一写的，精要介绍了整篇论文的内容。

mrdrivingduck commented 3 years ago

2. Preliminaries

2.1 Massively Parallel Processing

Pivotal 的 Greenplum 数据库是一个大规模并行处理 (MPP) 分析型数据库，采用 share-nothing 架构，每个节点有着自己的内存、操作系统和磁盘。存储和数据处理将被分布到多个独立的数据库上，它们共同工作，对外表现为一个单体数据库。Master 节点是 GPDB 的入口，客户端连接到 master 节点并提交 SQL，master 将 SQL 优化并拆分为较小的任务，分发并协同多个 segment 共同完成数据处理和存储。Master 和 segment 通过网络互联。

在查询执行期间，数据可以以多种方式在 segment 之间分布：

2.2 SQL on Hadoop

Hive 等项目支持将 SQL 查询编译为 MapReduce 任务，并由 Hadoop 执行。HiveQL 加速了复杂查询的编码，但是编译出的 MapReduce 任务性能低下。其它基于 Hadoop 的 SQL 优化器只能支持一小部分的 SQL 标准特性。

Pivotal 的 HAWQ 是一个具有全兼容 SQL 接口、并带有基于代价估算优化器、基于 HDFS 的引擎。

mrdrivingduck commented 3 years ago

3. Orca Architecture

Orca 是一个基于级联优化框架的现代化优化器。与其它级联优化器和相应 DBMS 紧耦合不同，orca 可以运行与数据库系统之外，作为一个独立的优化器：

  1. 这对不同的计算框架 (MPP/Hadoop) 来说非常重要，因为只需要一个优化器就够了
  2. 这意味着可以将传统的关系型优化应用到新的查询框架中，如 Hadoop
  3. 能够独立运行优化器意味着不用运行数据库就可以进行测试

DXL

优化器与 DBMS 解耦意味着两者之间需要有信息交互的格式。Orca 提出 Data eXchange Language，使用 XML 格式对输入的查询、输出的查询计划、以及优化中需要用到的 DBMS metadata 进行编码。使用 DXL 的最直接的好处是，Orca 可以独立运行。

image

如图：

DBMS 为了接入 Orca，需要实现 DXL 翻译模块：

翻译模块在 Orca 外实现。这意味着，只要提供相应的 translator，多种系统都可以使用 Orca。

Memo

In-memory 数据结构。

Search and Job Scheduler

调度器通过以下三步产生相互依赖或并行的工作单元进行查询优化：

Transformations

产生等价逻辑表达式，或为已有的逻辑表达式选择物理实现。

Property Enforcement

没懂。

Metadata Cache

DBMS 的 metadata 变更不频繁，在 DBMS 和 Orca 之间反复传输开销很大。Orca 在优化器内缓存了 DBMS 的 catalog，只有在 cache 中的条目不可用，或者 catalog 发生变动时，才会重新获取。Metadata 缓存也为单独调试、测试 Orca 优化器提供了便利。

GPOS

屏蔽底层 OS 不同的 API，Orca 提供了一层被称为 GPOS 的抽象层，包含如下基础设施功能：

mrdrivingduck commented 3 years ago

4. Query Optimization

TO DO ...

mrdrivingduck commented 3 years ago

5. Metadata Exchange

优化器内的每个会话在访问 metadata cache 时，由独立的 MD Accessor 服务。如果缓存缺失所需的信息，MD Accessor 负责透明地从外部的 MD Provider 向 DBMS 获取数据。在优化过程中，内存中的 metadata cache 会被 pin 住，并在优化结束后被 unpin。

image

另外，Orca 实现了一个基于文件的 MD Provider，可以从 DXL 文件中装载 metadata。这意味着 Orca 不需要与一个正在运行中的 DBMS 后端同时运行。

mrdrivingduck commented 3 years ago

6. Verifiability

6.1 Minimal Repros

AMPERe 是一款自动抓取最小化重现信息的工具。其动机是为了在不能访问客户生产环境系统的前提下，重现、调试客户的问题。一次 AMPERe dump 将会在意料之外的错误抛出时自动触发，或者在产生次优查询计划时按需触发。AMPERe dump 包含重现问题的最少信息：

上述信息被序列化为 DXL 格式。如果 dump 是因为异常，那么还将包含堆栈信息。

AMPERe 使得可以在 DBMS 之外重放一个优化器 session。任何 Orca 实例可以载入 dump，获取输入查询、metadata、配置参数，并调用出一个与问题触发场景相同的优化器 session。

AMPERe dump 还可以作为单独的 test case。

image

Testing Optimizer Accuracy

没太懂。