数据库查询优化中的谓词迁移优化技术

描述
谓词迁移（Predicate Move-Around）是数据库查询优化器在生成逻辑执行计划时使用的一种高级重写优化技术。其核心思想是将逻辑查询树中的过滤条件（谓词）尽可能“移动”到更靠近数据源的位置，从而尽早过滤掉无关数据，减少后续连接、聚合等操作的中间结果集大小，降低查询的整体执行代价。与基础“谓词下推”不同，谓词迁移能处理更复杂的场景，如在包含外连接、子查询的查询中智能地重新定位谓词。

解题过程循序渐进讲解

步骤1：理解基本概念与目标

• 谓词（Predicate）：即查询中的过滤条件，通常出现在WHERE、JOIN...ON、HAVING子句中，形式如column = value、column > constant等。
• 优化目标：将谓词沿着查询树向下（向数据源方向）或跨分支移动，使过滤操作尽可能提前执行，减少查询处理的数据量。
• 关键原则：
  1. 保持等价性：谓词迁移不能改变查询的语义和结果。
  2. 保持有效性：移动后的谓词所引用的列必须在新的位置可访问（在作用域内）。
  3. 考虑连接类型：外连接（LEFT/RIGHT JOIN）的谓词迁移受限，需区分“保留表”侧的谓词。

步骤2：识别可迁移的谓词类型

• 本地谓词（Local Predicate）：仅引用单个表的列，例如t1.a > 10。这类谓词最容易迁移，可直接下推至该表的扫描操作之后。
• 连接谓词（Join Predicate）：涉及多个表的列，例如t1.a = t2.b。通常用于定义表间连接条件，但有时可被拆分或转化为其他形式迁移。
• 复杂谓词：包含子查询、聚合函数或表达式，迁移时需谨慎验证等价性。

步骤3：分析基本迁移模式（以内连接为例）
假设查询：

SELECT * FROM t1, t2, t3
WHERE t1.a = t2.a AND t2.b = t3.b AND t1.c > 10 AND t3.d < 5;

• 初始查询树：WHERE中的所有条件在连接后执行过滤。
• 优化过程：
  1. 将t1.c > 10下推至表t1的扫描后。
  2. 将t3.d < 5下推至表t3的扫描后。
  3. 连接谓词t1.a = t2.a和t2.b = t3.b保留在连接操作中作为连接条件。
• 效果：t1和t3先过滤掉大量不满足条件的行，大大减小连接操作的输入数据量。

步骤4：处理外连接中的谓词迁移
外连接的语义会限制谓词迁移。以左外连接为例：

SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id
WHERE t2.col IS NOT NULL;

• 迁移分析：
  • 如果直接将t2.col IS NOT NULL下推到左连接的右侧（t2表），会错误地将t2中为NULL的行过滤掉，改变左连接“保留t1所有行”的语义，使结果中可能丢失t1中未匹配的行。
  • 正确做法：将此谓词作为连接后的过滤条件（即保持在WHERE中），此时它实际上将左连接转换为内连接（因为t2.col为NULL的行会被过滤）。优化器可能识别此模式，主动将左连接改为内连接以便更激进地下推谓词。
• 迁移规则小结：
  • 涉及“保留表”（左连接的左表）的谓词可下推到该表扫描后。
  • 涉及“非保留表”的谓词且该谓词“拒绝NULL”（如t2.col = 1）时，不可下推至该表扫描后，但可能触发连接类型的转换。

步骤5：处理子查询与复杂表达式中的谓词迁移
对于包含子查询的谓词，优化器可能采用“解嵌套”将子查询转换为连接后再迁移。例如：

SELECT * FROM t1 WHERE t1.id IN (SELECT t2.id FROM t2 WHERE t2.x > 0);

• 优化器先将IN子查询解嵌套为半连接（Semi-Join）：t1 ⋉ t2。
• 然后将t2.x > 0下推至子查询内的t2表扫描后。
• 最后，如果t1也有本地谓词，可继续下推。

步骤6：实现与代价估算

• 优化器在逻辑优化阶段遍历查询树，应用谓词迁移规则生成多个候选计划。
• 对每个候选计划，估算谓词迁移后的选择性（过滤后行数），计算连接、聚合等操作的代价变化。
• 选择总代价最小的计划进入物理优化阶段。

示例总结
通过将谓词迁移到合适位置，数据库能尽早过滤数据，减少中间结果，降低I/O和CPU消耗。这是现代查询优化器的核心能力之一，尤其在复杂查询中效果显著。实际优化中，谓词迁移常与其他技术（如连接消除、子查询展开）结合使用，由优化器自动完成，无需手动改写SQL。