CMU15445-lecture14

第十四课：查询规划和优化

1 概述

由于SQL是声明式语言，查询语句仅告知数据库管理系统(DBMS)需要计算什么，而非如何计算。因此，DBMS需要将SQL语句转换为可执行的查询计划。但查询计划中每个操作符存在多种执行方式（例如连接算法的选择），不同计划的性能表现也存在差异。DBMS优化器的核心任务就是为给定查询选择最优计划。

查询优化器的首个实现是20世纪70年代设计的IBM System R。在此之前，人们普遍认为DBMS无法生成优于人工设计的查询计划。System R优化器的诸多概念和设计决策至今仍被沿用。当前查询优化主要采用两种高层策略：

1. 静态规则（启发式方法）：通过匹配查询中的已知模式来构建计划，利用规则消除低效操作。这类规则可能需参考目录以理解数据结构，但无需实际扫描数据。
2. 基于代价的搜索：通过读取数据并估算等效计划的执行代价，由代价模型选择最低成本的方案。

查询优化是构建DBMS最具挑战性的环节。尽管已有研究尝试应用机器学习提升优化器的准确性和效率，但目前尚无主流DBMS部署基于该技术的优化器。

逻辑计划与物理计划

优化器负责将逻辑代数表达式映射为最优的等价物理代数表达式。逻辑计划大致等同于查询中的关系代数表达式。

物理运算符通过为查询计划中的不同运算符定义特定的访问路径来确立具体的执行策略。物理计划可能会依赖于被处理数据的物理格式（例如排序方式、压缩形式）。

从逻辑计划到物理计划的映射并不总是存在一一对应关系。

2 逻辑查询优化

部分选择优化策略包括：
• 尽早执行过滤操作（谓词下推）
• 重新排序谓词，使DBMS优先应用最具选择性的谓词
• 分解复杂谓词并进行下推（拆分合取谓词）