通过重写冗余操作加速数据库查询

SQL数据库查询经常包含相同操作的重复执行。例如，在表中查找特定人员的记录可能涉及提取所有具有该人员名字的条目和所有具有该人员姓氏的条目，然后计算它们的交集。如果名字和姓氏搜索需要两次查询同一数据库表，这种冗余会增加检索时间。

在IEEE数据工程国际会议（ICDE）上发表的论文中，描述了一种重写复杂SQL查询以消除此类冗余的方法。有时，这涉及检索条目的超集，然后根据附加条件进行筛选。但通常来说，检索后进行的少量额外计算比多次查询同一表更高效。

查询重写技术

查询计划是执行SQL查询所需的一系列步骤，包括数据扫描和聚合等操作。查询计划优化是从大量可能方案中选择最高效查询计划的过程。

这项工作的重点是识别在重叠数据上进行计算的子查询，并将它们融合为单一计算，通过补偿操作（检索后计算）重建原始结果。它不要求子查询在语法上完全相同或产生相同输出。

以以下查询为例：

1
2
3
4

WITH cte AS (...complex_subquery...)
SELECT customer_id FROM cte WHERE fname = 'John'
UNION ALL
SELECT customer_id FROM cte WHERE lname = 'Smith'

该查询在FROM子句中两次使用cte块。这种写法不是最优的，特别是当重复计算代价高昂时。相关技术可以识别此类模式并进行重写，例如将上述查询转换为：

1
2
3
4

WITH cte AS (...complex_subquery...)
SELECT customer_id FROM cte, (VALUES (1), (2)) T(tag)
WHERE (fname = 'John' AND tag=1)
   OR (lname = 'Smith' AND tag=2)

重写规则构建模块

定义了用于新查询计划优化规则的基本原语，特别是Fuse函数，该函数接受两个输入计划并返回⊥（当融合不可能时）或四元组融合结果。如果Fuse(P1, P2) = (P, M, L, R)，则：

• P是融合后的计划
• M是将P2的输出列映射到P的输出列的映射
• L和R是定义在P输出列上的两个筛选条件，分别用于恢复P1和P2

从语义上，可以按以下方式重建P1和P2：

1
2

P1 = ProjectoutCols(P1)(FilterL(P))
P2 = ProjectM(outCols(P2))(FilterR(P))

Fuse是一个递归函数，可以处理不同的操作符，如表扫描、筛选、投影、连接、聚合和去重聚合。

优化规则

引入了多种基于上述原语重写查询计划的优化规则：

GroupByJoinToWindow：转换表达式被聚合并连接回自身以获取聚合行附加信息的常见模式

JoinOnKeys：处理返回相同数据不同视图的相似子查询被自连接在一起的模式

UnionAllOnJoin：处理客户将两个整体相似但仅在单个表上不同的计算结果合并的场景

UnionAll：对应前面示例查询中的模式，客户使用通用表达式然后对结果进行不同投影的联合操作

实际应用效果

在包含3TB数据的TPC-DS基准数据库实验中，该技术使99个查询的整体执行时间相比基线提高了14%。对于直接被重写规则转换的查询，观察到性能提升60%，某些查询执行速度提高六倍以上。

该技术已投入生产使用，虽然某中心Athena从中受益，但同样技术也适用于其他数据库系统，因为它们不需要实现新的操作符或执行模型。最终结果是客户查询运行速度更快，由于扫描数据量减少，费用也相应降低。