数据库查询优化中的查询重写与等价变换

1. 问题描述

查询重写是数据库优化器的核心步骤之一，其目标是在不改变查询语义的前提下，将用户提交的SQL转换为更高效的执行形式。通过应用关系代数的等价规则（如结合律、分配律、谓词简化等），优化器可减少中间结果集大小、降低计算开销。例如，将子查询展开为连接操作、消除冗余条件、提前过滤数据等。

2. 核心等价规则与重写场景

2.1 谓词传递与简化

• 场景：WHERE age > 18 AND age > 20
• 重写逻辑：
  • 根据谓词传递性，age > 18 AND age > 20 可简化为 age > 20（减少条件判断次数）。
  • 若存在矛盾条件（如 age > 20 AND age < 18），直接重写为 FALSE，避免全表扫描。

2.2 连接/过滤顺序调整

• 场景：多表连接时先过滤再连接

  SELECT * FROM orders JOIN customers ON orders.cid = customers.id 
  WHERE customers.country = 'US' AND orders.amount > 100;
  

• 重写逻辑：
  • 将过滤条件下推到连接前执行（谓词下推），减少连接操作的数据量：

    SELECT * FROM (SELECT * FROM orders WHERE amount > 100) AS o 
    JOIN (SELECT * FROM customers WHERE country = 'US') AS c 
    ON o.cid = c.id;
    

2.3 子查询展开

• 场景：IN子查询转换为半连接（Semi-Join）

  SELECT * FROM products WHERE category_id IN 
  (SELECT id FROM categories WHERE type = 'Electronics');
  

• 重写逻辑：
  • 子查询可能产生重复值，但IN操作符隐式去重，因此可安全转换为半连接：

    SELECT products.* FROM products 
    WHERE EXISTS (SELECT 1 FROM categories 
                 WHERE categories.id = products.category_id 
                 AND categories.type = 'Electronics');
    

  • 进一步，优化器可能直接使用半连接算法（如Hash Semi-Join）避免显式去重。

2.4 公共表达式提取

• 场景：重复计算的子查询或表达式

  SELECT (SELECT AVG(score) FROM reviews WHERE product_id = p.id) AS avg_score,
         (SELECT COUNT(*) FROM reviews WHERE product_id = p.id) AS review_count 
  FROM products p;
  

• 重写逻辑：
  • 提取公共子查询，避免多次扫描同一表：

    SELECT p.id, r.avg_score, r.review_count 
    FROM products p 
    LEFT JOIN (SELECT product_id, AVG(score) AS avg_score, COUNT(*) AS review_count 
               FROM reviews GROUP BY product_id) AS r 
    ON p.id = r.product_id;
    

3. 优化器实现重写的步骤

1. 语法树解析：将SQL转换为抽象语法树（AST）。
2. 逻辑规则匹配：遍历AST，匹配预定义的等价规则（如谓词合并、子查询展开）。
3. 代价估算比较：对重写后的多个等价形式估算执行代价（I/O、CPU），选择最优方案。
4. 生成执行计划：将重写后的逻辑计划转换为物理算子（如HashJoin、IndexScan）。

4. 实际应用注意事项

• 语义等价性：重写需严格保证结果一致性（例如，NULL值处理可能影响外连接重写）。
• 统计信息依赖：重写效果依赖数据分布（如小表驱动大表时谓词下推收益更大）。
• 数据库差异：不同数据库（如MySQL vs. PostgreSQL）的重写策略可能不同。

通过系统化应用查询重写，可显著提升复杂查询性能，尤其在OLAP场景下减少不必要的计算与数据传输。