数据库查询优化中的公共表达式消除（Common Subexpression Elimination）技术

描述
公共表达式消除（CSE）是数据库查询优化中的一项重要技术，主要用于处理查询中重复出现的相同子表达式或子查询块。当同一个计算逻辑在查询的多个位置出现时，数据库优化器可以通过CSE技术识别这些公共表达式，并确保它们只被计算一次，然后将计算结果共享给所有需要的地方。这项技术能够减少重复计算的开销，降低查询的CPU和I/O消耗，尤其适用于复杂查询中包含多个相同子查询或复杂标量表达式的情况。

解题过程

1. 识别公共表达式

   • 场景：优化器在解析查询后，会构建查询的抽象语法树（AST）或关系代数树。在这个过程中，它会分析树中的各个节点，寻找结构完全相同（或语义等价）的子表达式。
   • 什么算公共表达式：
     • 字面量相同的子查询：例如，在SELECT列表和WHERE条件中出现了完全相同的子查询。
     • 复杂的标量表达式：例如，一个复杂的数学计算或字符串处理函数在多个SELECT项或WHERE条件中被使用。
     • 连接条件或过滤条件中的重复部分。
   • 关键点：优化器需要进行语法和语义分析，确保两个表达式不仅在文本上相同，在当前的查询上下文和模式（Schema）下也具有完全相同的含义。例如，即使文本相同，但如果引用的列有歧义（如自连接时），则可能不是公共表达式。

2. 评估消除的可行性与代价

   • 可行性分析：并非所有公共表达式都适合消除。优化器需要判断：
     • 确定性：该表达式是否是确定性的？即，给定相同的输入，是否总是产生相同的输出？如果表达式包含非确定性函数（如RAND(), CURDATE()），则每次计算结果可能不同，不能共享结果。
     • 无副作用：计算该表达式是否会产生副作用（如调用一个修改数据库状态的存储过程）？如果有副作用，则不能只计算一次。
   • 代价估算：优化器会估算执行公共表达式的代价，以及保存和复用其结果的代价。如果公共表达式的计算成本很低（如简单的加法），而物化（保存）其结果的成本相对较高，那么进行CSE可能得不偿失。优化器的代价模型会对此进行权衡。

3. 执行重写与物化

   • 重写查询：一旦决定对某个公共表达式进行消除，优化器会重写查询计划。
     • 方法一：引入临时计算节点。优化器会在查询执行计划中创建一个新的操作符节点，专门用于计算这个公共表达式。这个节点通常被称为"物化"节点或"公共子表达式"节点。该节点会计算表达式的结果并将其保存在内存（有时是临时存储）中。
     • 方法二：使用CTE（公共表表达式）。如果公共表达式本身是一个完整的子查询，且数据库引擎支持对CTE进行优化（例如，不是所有数据库都会物化CTE），优化器可能会采用类似CTE的物化策略。在查询计划中，这个子查询会被执行一次，结果集被物化，然后被后续步骤多次引用。
   • 替换引用：查询计划中所有使用到该公共表达式的地方，都会被修改为直接引用上一步物化出来的结果，而不是重新执行计算。

4. 集成到执行计划

   • 经过CSE优化后的新执行计划，会作为一个整体被数据库的执行引擎执行。
   • 执行引擎会确保公共表达式节点在真正需要其结果之前被计算，并且其计算结果在其生命周期内（通常在整个查询或相关查询片段的执行期间）是可用的，以便被多次访问。

举例说明

假设有一个查询，要找出公司里工资高于部门平均工资，且奖金也高于部门平均奖金的员工。

原始低效SQL:

SELECT e1.name, e1.salary, e1.bonus
FROM employees e1
WHERE e1.salary > (SELECT AVG(e2.salary) FROM employees e2 WHERE e2.dept_id = e1.dept_id)
  AND e1.bonus > (SELECT AVG(e3.bonus) FROM employees e3 WHERE e3.dept_id = e1.dept_id);

在这个查询中，子查询(SELECT AVG(e2.salary) FROM employees e2 WHERE e2.dept_id = e1.dept_id)和(SELECT AVG(e3.bonus) FROM employees e3 WHERE e3.dept_id = e1.dept_id)结构高度相似，只是聚合的列不同。它们都根据dept_id与外部查询关联，并且都扫描employees表。

优化器进行CSE的可能思路：

1. 识别：优化器发现两个子查询的FROM子句和WHERE条件完全相同，都属于“根据外部行的dept_id来计算本部门的一个聚合值”这一模式。虽然聚合函数不同，但扫描和分组的操作是公共的。
2. 评估：计算每个部门的平均工资和平均奖金是确定性的，无副作用。计算成本较高（需要全表扫描或索引扫描并按部门分组），因此消除的收益很大。
3. 重写：优化器可能会生成一个如下的逻辑执行计划：
   • 步骤1：对employees表进行一次扫描，按dept_id进行分组，同时计算出每个部门的AVG(salary)和AVG(bonus)。这一步将两个子查询的计算合并为一次分组聚合操作。
   • 步骤2：将步骤1的结果（一个包含dept_id, avg_salary, avg_bonus的临时结果集）与原始的employees表（别名为e1）进行连接，连接条件是e1.dept_id = 临时表.dept_id。
   • 步骤3：在连接后的结果上，应用过滤条件e1.salary > 临时表.avg_salary AND e1.bonus > 临时表.avg_bonus。
4. 执行：执行引擎按照这个优化后的计划执行，只需要对employees表进行一次扫描和分组聚合，而不是两次，显著提高了性能。

总结
公共表达式消除是一种基于代码移动和结果复用的经典编译优化技术在数据库领域的应用。它通过识别和合并查询中的冗余计算，将多次计算减少为一次，从而有效提升复杂查询的执行效率。优化器需要智能地判断何时应用此技术，并在减少计算量和增加物化开销之间做出最佳权衡。