第15章 查询处理

本课程对应Abraham Silberschatz、Henry F. Korth、S. 在“第15章 查询处理”的证据链中，Sudarshan著，杨冬青、李红燕、张金波等译《数据库系统概念（原书第7版）》，机械工业出版社2021年6月出版，820页，ISBN 9787111681816。原版第7版由McGraw-Hill于2019年发布。课程按原书11部分、32章与附录A逐项重构，不复制原文。

中文版第7版纸书正文收录第1-23章；第24-26章由中文版提供中文在线内容；第27-32章是原版官网英文在线章节；附录A在纸书中。本页媒介为“纸书正文”。 全课程另设学习地图与总复习，共35页；正式知识分母仍是32章与附录A。本页属于“第六部分 查询处理与优化”，依据正式目录覆盖9个节点。

“第15章 查询处理”没有使用未获授权的中文纸书正文；以 作者官网第 7 版完整目录 界定 32 章与附录 A，以 作者公开在线章节、大学模式实验 和 McGraw-Hill 第 7 版变更说明 核对可公开内容。中文解释、SQL、图示、实验与练习均为独立教学重写；实现行为再以 PostgreSQL 官方文档 等一手规范复核。

从一次可观察状态变化开始

先预测：给定一份固定的大学数据库、一个操作和一个故障时刻，哪些逻辑行、物理页、锁、版本或日志记录应该变化，哪些绝不能变化？不要先运行再解释。把预测写成状态表，然后用独立查询、执行统计、页或日志轨迹核对。若预测与观察不一致，先检查模型和实验边界，而不是立即改配置。

本页主问题是“把关系运算映射为扫描、排序、哈希和连接算法并核算I/O与内存”。交付不以读完为准，而以另一位学习者能从算子流水线图、三种连接算法实验和I/O成本对账复现同一结论为准。最小正确性合同是：每个物理算子保持逻辑语义，代价估算注明页数、内存页和输入有序性。

核心词汇与系统边界

查询计划、外部排序、嵌套循环连接、归并连接、哈希连接 构成本页词汇表。每个词都要回答四个问题：它约束什么状态，由哪个模块执行，在哪个故障或并发边界会失效，用什么证据发现失效。只给一句名词解释不构成掌握。

第七版机制逐项深读

15.1 概述

在“第15章 查询处理”中，“15.1 概述”组织“依据原书第7版完整目录覆盖9个节点：把关系运算映射为扫描、排序、哈希和连接算法并核算I/O与内存”的语义、结构、执行和证据；若不能给出一个状态变化与独立对账，本节点仍未完成。

15.2 查询代价的度量

在“第15章 查询处理”中，“15.2 查询代价的度量”把逻辑算子落实为扫描、排序、连接与流水线；结果正确之外还要核对估计行数、实际行数和缓冲访问。

15.3 选择运算

在“第15章 查询处理”中，“15.3 选择运算”是闭包关系运算：输入和输出仍是关系；先手算元组集合，再检查重复语义、属性重命名与连接条件。

15.4 排序

在“第15章 查询处理”中，分析“15.4 排序”区分 CPU、内存、顺序 I/O、随机 I/O 与网络代价，不能把抽象 cost 直接当毫秒。

15.5 连接运算

在“第15章 查询处理”中，“15.5 连接运算”的物理算法可以变化，但逻辑语义不可漂移；证据应同时保存手算结果和数据库返回结果。

15.6 其他运算

在“第15章 查询处理”中，“15.6 其他运算”的交付物至少包含可重放 SQL、输入基线、正常轨迹、失败样本和恢复终点，不能只留最终截图。

15.7 表达式求值

在“第15章 查询处理”中，验证“15.7 表达式求值”固定 SQL 和数据，只改变工作内存或连接算法，比较溢写、首行时间、总时间和结果校验和。

15.8 内存中的查询处理

在“第15章 查询处理”中，“15.8 内存中的查询处理”的阻塞算子会改变首行延迟和资源峰值；计划图必须标出数据量在每个边界的变化。

15.9 小结

在“第15章 查询处理”中，“15.9 小结”组织“依据原书第7版完整目录覆盖9个节点：把关系运算映射为扫描、排序、哈希和连接算法并核算I/O与内存”的语义、结构、执行和证据；若不能给出一个状态变化与独立对账，本节点仍未完成。

机制推演：从语义到物理证据

选择可以顺序扫描或借助索引，外部排序分初始段与多路归并，连接可采用嵌套循环、归并或分区哈希。物化保存中间结果，流水线减少落盘；算法选择取决于页数、内存和数据顺序。

推演时始终区分五层。在“第15章 查询处理”的证据链中，第一层是业务不变量，说明哪些数据库状态合法；第二层是逻辑模型与查询语义，说明结果应该是什么；第三层是物理计划和数据结构，说明系统怎样得到结果；第四层是并发、日志与复制协议，说明交错和故障后仍保留哪些承诺；第五层是观测证据，说明我们怎样知道前四层真的成立。性能优化只能改变第三层和部分第四层的实现，不能悄悄改变前两层。

对每个节点建立因果链：输入版本与配置 → 操作或调度 → 中间状态 → 可观察输出 → 独立对账。在“第15章 查询处理”的证据链中，若结论涉及性能，报告中位数、尾延迟、吞吐、I/O和等待，而不是只截一条最快记录；若涉及正确性，至少准备一个应成功样本和一个应失败样本，并记录错误类别或恢复终点。

证据解释与交接

语义证据证明结果定义没有漂移。保存关系模式、约束、查询文本、参数、隔离级别和预期行集；涉及NULL、重复、顺序或聚集时，单独列出处理规则。任何实现比较都必须共享同一语义合同。

执行证据证明机制判断可以复核。保存计划、实际行数、缓冲命中、I/O、锁或版本、日志位置和错误状态中与本章相关的部分。计划估计与实际偏差本身就是结果，不应通过只截取计划名称隐藏。

失败证据证明边界真实存在。每次只注入一个变量：空输入、重复键、倾斜、并发冲突、进程崩溃、存储丢失或网络分区。明确失败前最后一个持久状态、恢复后第一个可用状态，以及是否需要人工介入。

交接证据让另一位学习者无需口头补充就能复现。最少包括版本卡、大学模式加载与重置脚本、预测表、算子流水线图、三种连接算法实验和I/O成本对账、正常与失败轨迹、独立对账、已知限制和回退条件。若更换DBMS或版本，先重跑基线再比较。

本章回顾

重新完成“把关系运算映射为扫描、排序、哈希和连接算法并核算I/O与内存”：先声明不变量和输入版本，按9个目录节点建立模型，手算正常路径，注入一个边界或故障，收集语义与执行证据，最后由独立查询对账。最终交付算子流水线图、三种连接算法实验和I/O成本对账，并能证明“每个物理算子保持逻辑语义，代价估算注明页数、内存页和输入有序性”。

小结

• 算子选择决定 I/O 与内存消耗
• 扫描、排序、哈希是基础构件
• 连接算法按输入规模选择
• 流水线减少中间结果落盘
• 成本核算要先估算再执行

复习与独立验收

← 上一页：第14章 索引 · 下一页：第16章 查询优化 →