Orca: A Modular Query Optimizer Architecture for Big Data

一个通用，可拓展，多核，高性能大数据优化器

GPDB

采用了shared-nothing的多处理架构，每个处理器拥有自己的内存，操作系统和磁盘等。主节点（master）管理其他的数据库实例（segment），数据在节点的分布可以是hashed，replicated，singleton等。

ORCA

• 基于Cascades优化流程（top-down)，并且可以作为其他存储系统的独立优化器模块；
• 提供了一种中间语言（Data eXchange Language）去编码信息，Query2DXL, DXL2Plan。

The input to Orca is a DXL query. The output of Orca is a DXL plan. During optimization, the database system can be queried for metadata (e.g., table definitions). Orca abstracts metadata access details by allowing database system to register a metadata provider (MD Provider) that is responsible for serializing metadata into DXL before being sent to Orca. Metadata can also be consumed from regular files containing metadata objects serialized in DXL format.

• Memo: 存储Plan的内存结构，里面由一系列groups（逻辑等价表达式）组成；
• Search and Job Scheduler: 搜索机制以及Job调度，将Plan转换为依赖或者并行执行单元，步骤如下：

exploration, where equivalent logical expressions are generated, implementationwhere physical plans are generated, and optimization, where required physical properties (e.g., sort order) are enforced and plan alternatives are costed.

• Transformation: 转换，包括物理和逻辑；
• Property Enforcement: 可扩展的框架，用于描述查询需求和基于正式属性规范的计划字符特性，包括逻辑属性(如输出列)、物理属性(如排序顺序和数据分布)和标量属性(如连接条件中使用的列)；
• Metadata Cache: 元数据（例如表的定义）缓存；
• GPOS: 操作系统抽象层。

Query Optimization

• 统计信息获取

Top-down的统计信息流请求机制（从父节点传入子节点）。相关的直方表信息从catalog通过MD provider解析成DXL存储在MD cache中，再由子节点传入父节点，将统计信息应用到root group。

• 优化流程

• 优化#1请求

Parallel Query Optimization

Optimization process is broken to small work units called optimization jobs.

Metadata Exchange

元数据包括表的定义，索引等信息

Verifiability

• a cardinality estimation testing framework,
• a number of benchmark tests at various scales,
• a data generator that can generate data by reversing database statistics [Reversing Statistics for Scalable Test Databases Generation], and
• two unique testing tools

• AMPEReis a tool for Automatic capture of Minimal Portable and Executable Repros.(Automatic Capture of Minimal, Portable, and Executable Bug Repros using AMPERe.[DBTest'12])
• TAQOfor Testing the Accuracy of Query Optimizer (Testing the Accuracy of Query Optimizers. [DBTest'12])