Optimizing Queries over Partitioned Tables in MPP Systems

[mrdrivingduck]

分区消除对于带有分区表的查询计划的性能来说至关重要，但在 MPP 架构中存在一些挑战。本文提出了一种能够生成在查询运行时决定访问哪些分区的查询计划，避免扫描不需要扫描的分区。

PDF：OptimizingQueriesOverPartitionedTablesInMPPSystems.pdf

[mrdrivingduck]

1. Introduction

当数据量较大时，分区是一个不错的选择。现代数据库系统通常在不同的节点上存储或处理分区数据，从而获得并行。在一台机器上，分区数据可以按行水平划分，也可以按列垂直划分，从而减少查询时需要扫描的数据。

对于查询来说，优化器需要根据查询条件决定是否只扫描一部分分区，这被称为 静态分区消除。由于现在数据使用星型模式，静态分区消除不一定总是可以成功。有一些分区消除只能在运行时才能够被决定，这被称为 动态分区消除技术 - 大部分数据库要么不支持，要么支持得很差。另外还有无法在优化时确定分区键的场景，比如 prepared statement。

上述交代了问题。那么本文的贡献有：

• 处理分区表的一个模型：
  • 两个抽象算子：PartitionSelector 和 DynamicScan
  • 产生的查询计划大小与总分区数或需要扫描的分区数无关
  • 以统一的形式支持静态和动态的分区消除
  • 方法与分区表的具体存储方式无关
• 分区消除算法，在查询计划的所有可以的位置放置 PartitionSelector 算子
• 多级分区表支持
• 性能优势

[mrdrivingduck]

2. Optimizing Queries on Partitioned Tables

2.2 Query Model for Partitioned Tables

为了实现分区表扫描，引入了两个新的算子 PartitionSelector 和 DynamicScan。这两个运算符成对出现，被实现为 生产者-消费者 模式。PartitionSelector 计算需要扫描的分区的 OID，而 DynamicScan 根据这些 OID 进行扫描。两者通过共享内存进行通信。

如图，分区表的扫描有很多种模式：

1. 全分区扫描：PartitionSelector 产生所有子分区的 OID，由 DynamicScan 进行扫描；在两者的祖先节点上放置 Sequence 算子，保证前者先于后者执行完
2. 等值断言：对分区有等值过滤条件
3. 范围断言：对分区有范围过滤条件
4. 连接扫描：根据左子树的条件动态选择右子树要扫描的分区；这种情况下不需要 Sequence 算子

对于 PartitionSelector 算子来说，其必备元素包含：

• 分区表 OID
• partScanId 标识符
• 可选的分区列过滤条件

根据分区表 OID 和给出的分区列过滤条件，计算出所有符合条件的子分区，并把子分区的 OID push 到相同 partScanId 的 DynamicScan 中。PartitionSelector 最多只有一个孩子节点，并且输出与孩子节点一致 (如连接扫描所示，外节点)。

DynamicScan 负责消费所属 partScanId 的子分区 OID，并从相应分支中获取元组。

2.3 Placement of PartitionSelectors

在计划树中，DynamicScan 的位置是确定的，重点是计算 PartitionSelector 的放置位置。通常可以有多个放置位置，但不是所有的放置都能达到最佳的分区消除效果。算法的输入是一个表达式树，上面只有 DynamicScan 算子而还没有任何 PartitionSelector 算子。PartitionSelector 的最优位置的定义是：扫描子分区的数量最少。另外，两者并不需要是同一个节点的直接后代。

主算法：

1. 对于所有要插入的 PartitionSelector 来说，计算哪些 PartitionSelector 需要被放置到当前算子的上面，哪些 PartitionSelector 需要被放置到子节点中，该计算函数被各个算子重载
2. 将需要被放置到子节点的 PartitionSelector 下推，递归对子节点调用这个算法
3. 将需要被放置到当前 PartitionSelector 的算子放置到当前算子上

2.3.1 Default PartitionSelector Placement

默认实现，用于无法进行分支过滤的算子，比如 GroupBy、Union、Project 等：

• 如果子节点定义了给定的 partScanId，那么把 PartitionSelector 下推的到子节点
• 否则把 PartitionSelector 放在当前节点上

2.3.2 PartitionSelector Placement for Select

对于一个 select 计划树，判断相应的 part scan 是否定义在子树中：

• 如果不是，那么把 PartitionSelector 放置在当前节点上
• 如果是，则下推到相应子树中，但需要把当前算子上对分区列的过滤条件加入到相关 PartitionSelector 中，并与上级算子传递下来的过滤条件进行 AND 操作

2.3.3 PartitionSelector Placement for Join

对于连接来说：

• 如果左右子树中不包含 DynamicScan 的定义，那么直接把 PartitionSelector 放置在当前节点上
• 如果左子树 (outer) 包含 DynamicScan 的定义，那么 PartitionSelector 肯定不能放在 inner 了，这样就破坏了两者的执行顺序，应当把 PartitionSelector 下推到 outer side
• 如果 inner side 包含 DynamicScan 的定义，那么如果连接条件中有涉及到分区列，那么就可以将这个过滤条件加到 PartitionSelector 中，然后将其下推到 outer side 实现分支消除；否则就需要下推到 inner side

如图，id 为 1 的 DynamicScan 出现在了 outer side 中，所以相应 PartitionSelector 也被下推到了 outer side 中；由于 outer side 中还有个 select，于是进一步下推，并把 select 的过滤条件加入到相应 PartitionSelector 中；最后，为了保证先后顺序，再加个 Sequence 算子。

而 id 为 2 的 DynamicScan 出现在了 inner side 中，而 join 条件可以被用于分支消除，所以 PartitionSelector 被下推到了 outer side，同时带上了连接过滤条件。这样 inner side 在扫描时就可以动态根据 outer side 中 PartitionSelector 指定的子分区进行扫描，从而实现分区消除。

2.4 Multi-level Partitioned Tables

将先前 PartitionSelector 的描述符定义进行修改，使其支持多个分区键和多个分区过滤表达式：

[mrdrivingduck]

3. Implementation

3.1 Query Optimization

MPP 系统中有多种数据分布模式：

• Hash 分布
• Replicated 分布
• Singleton 分布

通过 Motion 算子来作为进程的执行边界。由于分区选择依赖于共享内存实现 PartitionSelector 和 DynamicScan 之间的通信，因此优化器需要保证一对 PartitionSelector 和 DynamicScan 算子在同一个进程内被执行，这意味着两者之间到公共祖先之间不能有 Motion 算子。

为啥？同一个进程还需要共享内存吗？应该是同一台机器吧。。。

经过对论文的理解，它的意思应该是被同属于一个 slice 的进程执行：

那么 ORCA 优化器具体是怎么干的呢？超出我能力范围了。。。