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

描述
查询执行计划是数据库优化器生成的、用于执行SQL查询的步骤序列，它决定了数据访问的顺序、连接方法、索引使用等。等价变换是指在不改变查询结果的前提下，通过逻辑规则重写查询语句，以生成更高效执行计划的技术。该技术是查询优化的核心，旨在降低查询的响应时间和资源消耗。

步骤详解

1. 查询解析与语法树生成

   • 描述：数据库首先解析SQL语句，检查语法和表/列是否存在，生成初始的抽象语法树（AST）。
   • 示例：对于查询 SELECT * FROM t1 JOIN t2 ON t1.id = t2.id WHERE t1.val > 100，AST会包含FROM、JOIN、WHERE等子句的树形结构。

2. 逻辑优化：等价变换规则应用

   • 目的：利用关系代数规则重写查询，减少中间结果规模或简化计算。
   • 常见变换规则：
     • 谓词下推：将WHERE条件尽可能靠近数据源，提前过滤无效数据。
       • 示例：将 SELECT * FROM (SELECT * FROM t1 WHERE t1.val > 100) AS sub JOIN t2 ON ... 重写为直接对t1过滤后连接。
     • 常量折叠：提前计算表达式中常量，如 WHERE id = 3+2 简化为 WHERE id = 5。
     • 连接顺序调整：基于表大小和过滤性，调整连接顺序（如小表优先连接）。
     • 子查询展开：将部分子查询转化为连接操作，避免嵌套循环的开销。

3. 物理优化：生成执行计划候选

   • 描述：为逻辑计划中的每个操作选择具体的物理实现方式。
   • 关键选择：
     • 扫描方式：全表扫描、索引扫描、索引范围扫描。
     • 连接算法：哈希连接、排序合并连接、嵌套循环连接。
     • 排序与聚合：内存排序 vs. 磁盘临时表。

4. 代价估算与计划选择

   • 代价模型：基于统计信息（如表大小、索引选择性）预估每个计划的CPU、I/O成本。
     • 示例：索引扫描的代价 = 索引高度 × 单页I/O成本 + 数据行访问成本。
   • 比较候选计划：选择总代价最低的计划作为最终执行计划。

5. 计划执行与反馈

   • 执行引擎：按照计划顺序访问数据，逐步生成结果。
   • 自适应优化：部分数据库（如Oracle、SQL Server）会监控实际执行情况，动态调整后续计划。

总结
等价变换通过逻辑重写优化查询结构，而执行计划将逻辑操作映射为物理操作。两者结合确保数据库在庞大数据量下仍能高效响应查询。实际应用中需结合统计信息、索引设计等因素综合优化。