Optimization of Common Table Expressions in MPP Database Systems

[mrdrivingduck]

• PDF: p1704-elhelw.pdf
• Online: https://dl.acm.org/doi/abs/10.14778/2824032.2824068
• PostgreSQL 13 Documentation: WITH Queries (Common Table Expressions)

[mrdrivingduck]

Abstract

在大数据分析中，经常会包含 带有相似或相同表达式的复杂查询，通常被称为 Common Table Expressions (CTEs)。CTE 可以：

• 被用户显式定义，用于简化查询表达
• 被智能工具隐式定义

在 MPP 数据库系统中，由于查询处理是分布式的，为有效优化/执行 CTE 带来了新的挑战。本文将描述 Orca 优化器中对 CTE 的表示、优化和执行框架。

[mrdrivingduck]

1. Introduction

CTE 通常被用于具有很多重复计算的复杂分析查询中。CTE 可以被视为是一个只为单个查询而存在的临时表：

with v as (SELECT ...)
SELECT * from v ...;

如上所述，使用 with 子句可以避免将复杂的查询作为子查询嵌套在父查询中；另外，子查询还有可能在父查询中被多次引用。因此，定义 CTE 有两个目标：

1. 简化查询，增强可读性
2. 只解析复杂查询一次，后续可以通过重用来提升性能

CTE 遵从 producer/consumer 模式，数据从 CTE 定义处生产，从 CTE 被引用处消费。

一种可能的思路是 内联 (inline) CTE，将 CTE 定义在引用处展开。这种方法简化了查询执行的逻辑，但是会因为多次执行相同的表达式而带来性能开销。另外，如果 CTE 定义较为复杂，查询优化的时间将会大大增加。

一种替代的思路是以真正的 producer/consumer 模式执行 CTE。CTE 表达式被单独优化并执行一次，结果被保存在内存或文件 (结果过大，或结果需要在进程间传递，如 MPP)。这些数据会在所有 CTE 被引用的地方消费。这种方法避免了重复执行同一个表达式的开销，但可能会引入额外的磁盘开销。另外，如果同一个执行计划被多个 consumer 使用，优化器将错失重要的优化机会。

[mrdrivingduck]

1.1 Challenges

1.1.1 死锁问题

MPP 系统由多个进程并行执行。如果 CTE 的定义在一个进程中，CTE 的消费者在另一个进程中，那么后者必须等待前者。在更复杂的查询中，优化器需要保证没有任何两个及以上的进程在互相等待。

1.1.2 内联处理

总是内联 CTE，或从不内联 CTE，可以轻而易举地被证明为是次优的。如图所示，三处 CTE 的定义：

1. 如果不使用内联，那么 v3 处无法利用索引
2. 如果全部内联，那么存在重复执行的问题
3. 在 v3 处使用内联，利用索引；在其它两处不内联，从而避免重复执行

优化器需要更加灵活地选择内联策略。

1.1.3 情景化的优化

隔离化的优化可能错事很多优化机会。比如，如果所有的 CTE consumer 上都有 filter，那么 filter 可以被下推至 CTE producer 中；如果多数 CTE consumer 的上层都要求结果有序，那么将 sort 算子下推到 CTE producer 中可能能够避免重复排序。

1.2 Contributions

• MPP 数据库系统中优化 CTE 的框架
• CTE 不会在每次被引用时都被重新优化，而是只有在有优化机会时才会被优化；这样确保优化时间不会随着 consumer 的增多而指数增长
• 基于代价估算的优化方法，决定是否将 CTE 在查询中内联展开，代价模型涵盖磁盘 I/O 和重复执行 CTE 的代价
• 降低搜索空间并加快执行速度的几个优化方法
• 保证 CTE producer 总是比 CTE consumer 先执行的查询执行模型，防止死锁

[mrdrivingduck]

2. Related Work

CTE 优化

两阶段优化：第一阶段使用 SCOPE 优化器，第二阶段在一个链表中记录所有 CTE consumer 所需要的物理属性 (分区/排序)，随后识别 CTE consumer 的最近公共祖先，根据 consumer 的本地需求重新优化。相比之下本文的优势：

• CTE 优化在优化器核心完成，不用重新优化
• 优化框架能够识别到优化 CTE 的入口处，不需要寻找公共祖先
• 单阶段优化，避免不需要的优化

PostgreSQL：将 CTE 视为一个单独的子查询，与主查询的优化相隔离。相比之下，错失了如下的重要优化机会：

• 内联 CTE
• 当 CTE consumer 有相同的物理属性需求时，下推算子到 CTE 中

Oracle 优化器：将 CTE 查询的结果存放在临时表中，优化器能够内联 CTE consumer 为子查询。

[mrdrivingduck]

3. Background

3.1 Massively Parallel Processing

现代的 scale-out 数据库都是基于两种原则之一设计的：

• 分片 (Sharded)
• 大规模并行处理 (MPP)

两者都是 shared-nothing 架构。

分片数据库通过在一小部分分片上执行查询来优化性能，分片之间的通信相对受限。分片可以被放置在不同的数据中心，甚至不同的地理位置上。

MPP 数据库通过并行查询来提升查询性能。查询优化器生成带有显式数据移动指令的执行计划，执行数据移动的代价也被优化器计算在内。

[mrdrivingduck]

4. Representation of CTEs

示例 SQL：

WITH v AS (SELECT i brand FROM item WHERE i color = ’red’)
SELECT * FROM v as v1, v as v2
WHERE v1.i brand = v2.i brand;

在查询的逻辑表示中，引入如下新的 CTE 算子：

• CTEProducer：位于 CTE 表达式定义的根节点，每个 CTE 表达式定义对应一棵树，一个 CTEProducer 节点，同时带有一个唯一的 id
• CTEConsumer：在 CTE 表达式被引用的地方放置，节点的个数与查询中引用 CTE 的次数一致，CTEConsumer 的 id 对应于相应的 CTEProducer
• CTEAnchor：指示 CTE 在查询中被定义的位置，表示 CTE 的作用域；CTE 只能在以 CTEAnchor 为根节点的子树中被引用
• Sequence：按从左到右的顺序依次执行孩子节点

下面给出了上述逻辑表示的两者可能的计划：

• 所有 CTE 被内联，CTEAnchor 被移除，每个 CTEConsumer 被 CTEProducer 对应的树替代
• 没有 CTE 内联，CTEAnchor 被 Sequence 算子替代，CTEProducer 作为算子左孩子节点，原 Sequence 算子的孩子节点作为算子右孩子节点

Sequence 算子保证了执行的特定顺序：CTEProducer 在任何 CTEConsumer 之前被执行。这保证了当执行到达 CTEConsumer 时，CTEProducer 的数据已经可以被读取。这保证了没有死锁。

对于嵌套的 CTE 来说，上述算子的使用也是类似。只不过一个 CTE 的 consumer 出现在了另一个 CTE 的 producer 树中：

WITH v as (SELECT i current price p FROM item
                    WHERE i color = ’red’),
          w as (SELECT v1.p FROM v as v1, v as v2
                    WHERE v1.p < v2.p)
SELECT * FROM v as v3, w as w1, w as w2
WHERE v3.p < w1.p + w2.p;

[mrdrivingduck]

6. Plan Enumeration

6.3 Optimizations Across Consumers

针对多个 CTEConsumer 的场景，优化不止于局限于单个 CTEConsumer，还应该在 CTEConsumer 之间。

6.3.1 Predicate Push-down

通过将 CTE 定义内联展开到 CTEConsumer，可以下推一些谓词到 CTE 定义中，从而实现优化。在 Orca 中，甚至还实现了一些不需要内联就可以下推谓词的优化。考虑如下查询：

WITH v as (SELECT i brand, i color FROM item
                    WHERE i current price < 50)
SELECT * FROM v v1, v v2
WHERE v1.i brand = v2.i brand
AND v1.i color = ’red’
AND v2.i color = ’blue’;

查询中有两个 CTEConsumer，各有一个谓词。如果没有内联，CTEProducer 将会输出很多 CTEConsumer 不需要的元组。如果在 CTEConsumer 的公共节点上构造新的谓词，并将谓词推入到 CTEProducer 的定义中，那么将减少需要被物化的元组数量。

6.3.2 Always Inlining Single-use CTEs

在 Orca 中，只被使用一次的 CTE 将会被自动内联。否则，将会引入物化开销。

6.3.3 Elimination of Unused CTEs

从来没有被引用到的 CTE 将会被整体移除。

[mrdrivingduck]

7. Contextualized Optimization

7.1 Enforcing Physical Properties

...

7.2 Cost Estimation

正确估算 CTE 的代价对于优化过程来说很重要：

• CTEProducer 的代价包含：完整执行其子树的代价 + 将结果物化到磁盘的代价
• CTEConsumer 的代价包含：从磁盘中读取元组的代价 (相当于 table scan 的代价)

对于每一个 CTEConsumer，优化器都有两条路可走：

• 内联 CTE 表达式，代价为执行整个表达式的代价
• 不内联 CTE 表达式，代价为读取物化元组的代价

但是在 CTEConsumer 本地比较两条路的代价是不对的。如果走第二条路，那么意味着在另一个地方会有 CTEProducer 的开销，而 CTEProducer 的开销又会被所有的 CTEConsumer 均摊。

[mrdrivingduck]

8. CTE-Based Optimizations

8.1 CTE-Generating Transformations

在一些查询中，隐式使用了 CTE，从而避免了中间结果的重复计算：

SELECT COUNT(DISTINCT cs item sk), AVG(DISTINCT cs qty)
FROM catalog sales WHERE cs net profit > 1000;

由于分组聚合需要重复做，可以暂时物化分组的输入，避免表扫描重复执行：

Common Subexpression Elimination

对于查询中有公共表达式但是并没有定义为 CTE 的查询，可以将公共部分提取出来作为 CTE 来处理：

SELECT *
FROM (SELECT i brand, count(*) as b
             FROM item GROUP BY i brand HAVING count(*) > 10) t1,
           (SELECT i brand, count(*) as b
            FROM item GROUP BY i brand HAVING count(*) > 20) t2
WHERE t1.i brand <> t2.i brand;

两个表达式中都有对同一个表的分组聚合，那么可以将这个公共部分作为 CTE 来处理：

[mrdrivingduck]

9. Execution

在 MPP 数据库中，查询计划的不同部分可以在不同的进程中执行，进程可以在同一个 host 中，也可以在不同 host 中。在 Orca 优化器输出的执行计划里，保证 CTEConsumer 向 同一个 host 下的 CTEProducer (可能是同一个进程，也可能是不同进程) 读取元组。换句话说，保证 CTEConsumer 与 CTEProducer 之间的通信不走网络。网络应该只能通过 Motion 算子完成。

一般来说，CTEProducer 对应多个 CTEConsumer，执行引擎允许它们在同一个进程中被执行，也允许它们在不同进程中被执行。当涉及多进程时，执行引擎提供同步机制，确保 consumer 能够等待 producer 的元组生产完毕。CTEProducer 和 CTEConsumer 之间通过共同的 CTE id 相互识别。CTEProducer 会获知在同一进程以及不同进程之间的 CTEConsumer 数量。

在 GPDB 中，每个 CTEConsumer 执行前会进行依赖检查，等待 CTEProducer 元组就绪的确认；如果进程中含有 CTEProducer，那么一旦 CTEProducer 的元组准备完毕，需要立刻通知所有 CTEConsumer。

CTEProducer 的执行结果被缓存在 TupleStore 数据结构中，根据数据大小、可用内存和计划决定缓存在内存里还是在磁盘上。如果至少有一个 consumer 在另一个进程中，那么 TupleStore 将被缓存在磁盘上，CTEConsumer 将会接收到文件名和通知。

额外优化：如果 producer 的上级是一个 Sort 算子，那么将省去显式的物化操作：因为 Sort 算子会物化下层节点的执行结果。