数据库查询优化完全指南：从关系系统定义到六大优化准则（CS-Xmind-Note 408 数据库笔记深度解读）-平芜编程栈

文档
教程
知识库

【免费下载链接】CS-Xmind-Note

计算机专业课（408）思维导图和笔记：计算机组成原理（第五版王爱英），数据结构（王道），计算机网络（第七版谢希仁），操作系统（第四版汤小丹）

项目地址：https://gitcode.com/gh_mirrors/cs/CS-Xmind-Note

本篇基于 CS-Xmind-Note 仓库中的《查询优化》笔记展开。它围绕关系数据库系统中最关键的性能话题——查询优化，依次厘清"关系系统"的最低门槛、查询优化的定义与价值，并逐条剖析六大优化准则。读完本篇，你将掌握 RDBMS 查询优化器"怎么做"的底层思路，能够用关系代数与 SQL 两种视角理解并实践选择、投影、连接三大运算的重排与合并技巧，为数据库性能调优打下扎实的理论基础。

一、前置概念：关系系统与关系模型

1.1 关系系统与关系模型的联系与区别

关系系统和关系模型是两个密切相关而又有区别的概念。关系模型由关系数据结构、关系操作集合、关系完整性约束三要素组成（详见关系模型笔记），而支持关系模型的数据库管理系统（DBMS）称为关系系统。

关键点在于：关系模型中并非每一部分都同等重要，因此我们不苛求完全支持关系模型的系统才可称为关系系统，而是给出一个"关系系统的最小要求"及分类定义。这正是理解查询优化的起点——正是因为关系系统只需承诺最核心的三种运算能力，系统内部才拥有极大的"怎么执行"的自由度，查询优化才有了存在的空间。

1.2 关系系统的最小要求（关系系统的定义）

一个系统要被称为关系系统，至少要满足以下两条：

支持关系数据库（关系数据结构）
- 从用户观点看，数据库由表构成，并且只有表这一种结构。
- 实体与实体间的联系也都用"表"来表达，概念单一、清晰易用，这正是关系模型"概念单一"性质的体现。
支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径
- 注意：并不要求关系系统的选择、投影、连接运算与关系代数的相应运算完全一样，只要求有等价的这三种运算功能即可。
- "不必定义任何物理存取路径"意味着用户不需要关心数据在磁盘上如何组织、如何定位，这为系统内部的查询优化留下了空间。

从该定义可以看出，选择（σ）、投影（π）、连接（⋈）是关系系统能力的最低公约数，而它们恰恰也是查询优化准则反复操练的三种运算，相关运算定义可对照关系代数笔记复习。

二、查询优化：让系统替用户解决"怎么做"

2.1 查询优化的定义

查询优化：对于给定的查询，选择代价最小的操作序列，使查询过程既省时间、又具有较高的效率。

对于关系数据库系统，用户只需提出"做什么"（非过程化的 SQL 声明），而由系统解决"怎么做"的问题。具体来说，是DBMS 中的查询处理程序自动实现查询优化，从若干等价执行计划中挑选出代价最小者。

这与 SQL 的非过程化特性一脉相承——SQL 语言只描述结果而不规定执行过程（详见数据库语言SQL笔记），把执行策略的决策权完全交给了优化器。

2.2 查询优化的重要性

关系查询优化是影响 RDBMS 性能的关键因素。
关系系统的查询优化既是 RDBMS 实现的关键技术，又是关系系统的优点所在。

可以这样理解：同样的一个 SQL 查询，若按字面顺序机械执行（如先做笛卡尔积再做选择），中间结果可能膨胀到天文数字；而经过优化的执行序列可以在数秒钟内返回结果。优化器对性能的影响往往比用户改写查询语句的影响更大。

2.3 查询优化的优点

查询优化的优点有两点：

用户不必考虑如何最好地表达查询以获得较好的效率——用户可以把精力放在业务逻辑上，而非 SQL 书写技巧；
系统可以比用户程序的"优化"做得更好——优化器掌握全局限定信息（统计信息、索引分布、数据规模），能综合权衡，胜过用户凭经验猜测的执行策略。

三、查询优化的一般准则：六条经典规则

以下是笔记中给出的六条一般准则，它们是查询优化器设计的基础性启发规则。下面逐条展开原理、代价分析和对应实现。

准则一：选择运算应尽可能先做（最重要、最基本）

在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。

原理：选择（σ）是"行"的过滤，能将元组数量大幅压缩。把选择下推到查询树的最底层、最早执行，后续所有运算（笛卡尔积、连接、投影）面对的中间关系都变小了，成本随之呈数量级下降。

关系代数体现：将σ( R ⋈ S )重写为σ(R) ⋈ S或σ(R) ⋈ σ(S)，即把选择条件下推到连接之前。

SQL 对应：WHERE中的过滤条件应尽量利用索引直接定位，如：

-- 低效写法：先连接再过滤 SELECT Sname FROM Student, SC WHERE Student.Sno = SC.Sno AND SC.Grade >= 90; -- 高效写法：让优化器把 Grade>=90 的选择下推到 SC 表上先执行 -- 两种写法逻辑等价，后者经优化后先做选择再连接

在 PostgreSQL/MySQL 等优化器中，这对应谓词下推（Predicate Pushdown）规则。

准则二：在执行连接前对关系适当地预处理

预处理方法主要有两种：在连接属性上建立索引和对关系排序。

原理：连接是最昂贵的运算。若连接属性（join key）上有索引，可以避免对参与连接的关系做全表扫描，直接按索引定位匹配元组，这对应索引连接（Index Join）；若先按连接属性排序，则可用归并连接（Merge Join）在 O(n+m) 时间内完成连接。

SQL 对应（建索引，对应数据库语言SQL笔记中索引一节）：

-- 为连接属性建立索引，加速等值连接 CREATE INDEX idx_sc_sno ON SC(Sno); CREATE INDEX idx_student_sno ON Student(Sno); -- 连接查询 SELECT Sname, Cno FROM Student, SC WHERE Student.Sno = SC.Sno;

索引使数据库程序无须对整个表进行扫描即可找到所需数据，是准则二的核心落地手段。

准则三：把投影运算和选择运算同时进行

如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有这些运算，以避免重复扫描关系。

原理：投影（π）是"列"的裁剪，选择（σ）是"行"的过滤。若多个 π 与 σ 作用在同一关系上，完全可以在一次扫描中同时完成行列两级裁剪，避免对同一关系反复读取（I/O 开销是关系数据库性能的最大瓶颈之一）。

关系代数体现：π_A(σ_C(R))在一次扫描中完成，而不是先投影再扫描选择、或先选择再扫描投影。

SQL 对应：避免嵌套子查询造成的重复扫描：

-- 一次扫描完成选择+投影（推荐） SELECT Sno, Sname FROM Student WHERE Sdept = 'CS'; -- 冗余的中间层（不推荐，可能造成重复扫描） SELECT Sno, Sname FROM (SELECT * FROM Student) AS T WHERE T.Sdept = 'CS';

准则四：把投影同其前或其后的双目运算结合起来

没有必要为了去掉某些字段而扫描一遍关系。

原理：投影的目的只是"去掉某些字段"。与其单独执行一次 π（单独扫描一遍关系），不如把 π 合并到其前或后的双目运算（如连接 ⋈、笛卡尔积 ×、并 ∪ 等）中一并完成，让投影所需字段在双目运算的扫描过程中顺手裁剪掉。

关系代数体现：π_{A,B}( R ⋈ S )应改写为π_{A,B}( π_R( R ) ⋈ π_S( S ) )之类的形式，把投影下推到连接的两侧（即"投影下推"）。

SQL 对应：SELECT子句只列出必要的列，并信任优化器将列裁剪（Column Pruning）下推到连接算子：

-- 只需要 Student 的 Sname，无需取出 Student 全部列参与连接 SELECT Sname FROM Student, SC WHERE Student.Sno = SC.Sno;

准则五：把某些选择同它前面要执行的笛卡尔积结合起来成为一个连接运算

连接特别是等值连接运算，要比同样关系上的笛卡尔积省很多时间。

原理：笛卡尔积（×）将两个关系所有元组两两组合，结果规模是 m×n；而连接（尤其等值连接 ⋈）只保留满足连接条件的元组对。表达式σ_C( R × S )若先算笛卡尔积再过滤，中间结果巨大；把它合并为连接运算R ⋈_C S后，边匹配边产出，避免构造无意义的组合。

关系代数体现：σ_{R.Sno=S.Sno}( R × S )≡R ⋈ S（自然/等值连接），这也是关系代数笔记中"条件连接（θ 连接）是从 R×S 的结果集中选取满足 AθB 条件的元组"的由来。

SQL 对应：

-- 隐式写法（先笛卡尔积再过滤，交给优化器合并为连接） SELECT * FROM Student, SC WHERE Student.Sno = SC.Sno; -- 显式写法（语义等价，明确表达连接意图） SELECT * FROM Student INNER JOIN SC ON Student.Sno = SC.Sno;

两种写法逻辑等价，优化器会将前者重写为连接形式。

准则六：找出公共子表达式

找出公共子表达式（Common Subexpression）。

原理：若查询中出现多次计算的相同子表达式（例如视图展开后、多子查询共享的部分），只需计算一次，将结果暂存（物化）后供多处引用，避免重复执行相同的计算与 I/O。

典型场景：视图（VIEW）展开后，多个查询共享同一视图定义；或一条复杂查询中多个子查询含有相同的连接子表达式。SQL 中可通过视图、CTE（公共表表达式）显式复用：

-- 用 CTE 抽取公共子表达式，避免重复计算 WITH CS_Students AS ( SELECT Sno, Sname FROM Student WHERE Sdept = 'CS' ) SELECT * FROM CS_Students WHERE Sname LIKE '张%' UNION ALL SELECT * FROM CS_Students WHERE Sno IN (SELECT Sno FROM SC WHERE Grade < 60);

四、六大准则的体系化理解与自测

4.1 准则速查表

准则	核心动作	本质收益	典型实现机制
1. 选择先做	下推 σ	中间结果数量级缩小	谓词下推
2. 连接前预处理	建索引 / 排序	连接避免全表扫描	索引连接、归并连接
3. 投影与选择同时做	合并 π 与 σ	避免重复扫描关系	一次扫描完成行列裁剪
4. 投影与双目运算结合	投影下推	避免为去字段单独扫描	列裁剪
5. 选择 + 笛卡尔积 → 连接	合并 σ(×) 为 ⋈	避免无谓的 m×n 中间结果	连接重写
6. 找出公共子表达式	提取复用	避免重复计算与 I/O	视图 / CTE 物化复用

4.2 综合示例：一条查询的优化前后对比

设查询"找出计算机系（CS）且成绩及格的学生姓名"：

原始关系代数表达式（未优化）： π_Sname( σ_{Sdept='CS' ∧ Grade>=60}( Student × SC ) )

按六条准则逐步优化：

准则五：将σ( Student × SC )合并为等值连接Student ⋈ SC（连接条件 Student.Sno = SC.Sno）；
准则一：把Sdept='CS'下推到 Student 侧先做选择，把Grade>=60下推到 SC 侧先做选择；
准则三：在扫描 Student、SC 的同时完成各自的选择与所需列裁剪；
准则四：把最终投影 π_Sname 与连接运算结合，连接时只保留需要的列；

最终得到：

π_Sname( σ_{Sdept='CS'}(Student) ⋈ σ_{Grade>=60}(SC) )

中间结果从"两张全表笛卡尔积"缩小为"两表各自过滤后的小关系再连接"，执行代价相差数个数量级，正是准则一所述"节约几个数量级"的直观体现。

4.3 关联知识延伸阅读

三种运算的数学定义与示例：关系代数笔记（选择 σ、投影 π、条件连接 θ、自然连接）
SQL 中 WHERE 过滤、JOIN 连接、视图、索引的具体语法：数据库语言SQL笔记
查询优化在数据库课程体系中的位置：数据库总览

五、小结

本篇基于查询优化笔记完整梳理了数据库查询优化的知识骨架：关系系统的最小要求（关系数据结构 + 选择/投影/连接三运算）、查询优化的定义（选择代价最小的操作序列）、其"关键技术 + 系统优点"的双重定位，以及六大一般准则。六条准则可以凝练为一句话：让数据尽早变少（先选、早裁、合并）、让连接变快（预处理、避免笛卡尔积）、让计算不重复（公共子表达式）。掌握这六条准则，既是对 408 考研数据库部分高频考点的系统复习，也是理解真实 RDBMS 优化器（谓词下推、投影下推、连接算法选择、物化复用）行为模式的入门钥匙。