数据库的查询执行计划与等价变换技术

描述
查询执行计划是数据库优化器将SQL查询转换为具体执行步骤的树形结构，而等价变换则是通过逻辑等价规则重写查询，以生成更高效执行计划的技术。两者的结合是数据库查询优化的核心，旨在减少计算开销和资源消耗。

步骤详解

1. 查询解析与初始逻辑计划生成

   • 数据库首先解析SQL语句，检查语法和语义正确性，生成初始的逻辑查询树。例如，查询：

     SELECT * FROM orders WHERE customer_id = 101 AND amount > 1000;  
     

     会被解析为：

     Project(*)  
       └─ Filter(customer_id=101 AND amount>1000)  
             └─ Scan(orders)  
     

   • 此阶段仅关注逻辑正确性，不涉及具体执行方式。

2. 等价变换规则的应用
   优化器基于关系代数规则重写逻辑计划，常见变换包括：

   • 谓词下推：将过滤条件尽可能靠近数据源，减少中间结果大小。
     例如：

     SELECT * FROM orders JOIN customers ON orders.customer_id = customers.id  
     WHERE customers.country = 'USA';  
     

     重写后优先过滤customers.country='USA'，再执行连接。
   • 常量折叠：在编译时计算常量表达式，如WHERE salary > 1000+200简化为salary > 1200。
   • 连接顺序调整：基于表大小和条件选择性，重新排列连接顺序（如小表优先连接）。

3. 物理执行计划生成
   逻辑计划重写后，优化器选择具体物理操作符（如HashJoin、IndexScan等），考虑因素包括：

   • 成本估算：基于统计信息（如表大小、索引选择性）计算不同计划的CPU/I/O成本。
   • 访问路径选择：决定是否使用索引、全表扫描或位图索引扫描。
   • 最终生成物理计划，例如：

     NestedLoopJoin  
       ├─ IndexScan(orders, index_on_customer_id)  
       └─ IndexScan(customers, index_on_id)  
     

4. 计划比较与选择
   优化器可能生成多个候选计划，通过成本模型选择最优解。例如：

   • 若orders表的customer_id索引选择性高，优先使用索引扫描；
   • 若数据分布倾斜，可能选择全表扫描避免随机I/O。

5. 执行与动态优化

   • 数据库执行最终计划，部分系统（如Oracle）支持动态采样或执行时重优化，根据运行时数据调整策略。

关键点总结

• 等价变换依赖关系代数的数学基础（如交换律、结合律），确保变换后结果不变。
• 优化效果取决于统计信息的准确性和成本模型的合理性。
• 实际应用中需权衡优化时间与执行效率，避免过度优化。