数据库的查询执行计划中的谓词传递闭包优化技术（深入扩展）

描述
谓词传递闭包优化是数据库查询优化中的一种逻辑优化技术，其核心思想是通过已知的谓词（即查询条件）推导出隐含的谓词，从而减少查询处理的数据量。例如，如果查询包含条件A = B和B = C，优化器可推导出A = C，进而利用这一新谓词过滤数据。该技术适用于等值谓词和范围谓词，能显著提升连接查询和过滤操作的效率。

解题过程

1. 识别谓词关系

   • 优化器首先解析查询中的谓词，识别出列之间的关联性。例如，对于查询：

     SELECT * FROM t1, t2 WHERE t1.a = t2.b AND t2.b = 10;  
     

   • 谓词包括t1.a = t2.b（等值连接条件）和t2.b = 10（常量过滤条件）。
   • 关键步骤：提取所有谓词中的列和常量，构建一个“谓词图”（Predicate Graph），其中边表示列之间的等值或比较关系。

2. 构建传递闭包

   • 基于图论中的传递闭包概念，通过已知关系推导隐含关系。例如：
     • 若存在t1.a = t2.b和t2.b = t3.c，可推导出t1.a = t3.c。
     • 若存在t1.a > 10和t1.a = t2.b，可推导出t2.b > 10。
   • 实现方式：使用并查集（Union-Find）或深度优先搜索（DFS）对等值关系进行分组，再处理非等值谓词的传递（如范围传播）。

3. 应用推导出的谓词

   • 将隐含谓词添加到查询树中，扩大过滤或连接条件的覆盖范围。例如：
     • 原查询：SELECT * FROM t1, t2 WHERE t1.a = t2.b AND t2.b > 5。
     • 推导后：增加t1.a > 5作为过滤条件，可提前对表t1进行数据裁剪。
   • 注意点：需确保推导的谓词不会改变查询语义，尤其涉及NULL值或外连接时需谨慎（如外连接中推导的谓词可能无效）。

4. 优化效果评估

   • 减少连接操作的数据量：通过提前过滤基表，降低中间结果集大小。
   • 提升索引利用率：隐含谓词可能使得原本无法使用索引的列具备索引条件（如将t2.b的索引条件传递到t1.a）。
   • 代价模型调整：优化器需重新计算谓词添加后的执行计划代价，选择最优路径。

示例说明
假设查询为：

SELECT * FROM employees e, departments d  
WHERE e.dept_id = d.dept_id AND d.budget > 1000000;  

• 传递闭包优化后，可推导出e.dept_id对应的部门预算也满足> 1000000。
• 优化器可能将查询重写为：

  SELECT * FROM employees e, departments d  
  WHERE e.dept_id = d.dept_id AND d.budget > 1000000 AND e.dept_id IN (  
      SELECT dept_id FROM departments WHERE budget > 1000000  
  );  
  

• 实际执行时，可能会先对departments表按budget过滤，再通过dept_id直接关联过滤后的employees数据，减少连接计算量。