数据库查询处理 (Query Processing)

1. 核心概念与流程 (Overview)

查询处理的目标是将用户的高级语言（如 SQL）转换成数据库系统能够执行的低级指令，并寻找最高效的执行方式。

三个关键步骤 :
1. Parsing and translation (解析与翻译): 检查语法，将查询转换成关系代数表达式。
2. Optimization (优化): 这是最关键的一步。同一个查询可以有多种执行计划（Plan），优化器负责估算各种计划的代价，找出成本最低的一个。
3. Evaluation (执行): 查询执行引擎根据优化后的计划，一步步执行并返回结果。

2. 代价估算指标 (Measures of Query Costs)

数据库主要关注磁盘 I/O，因为它是最慢的环节。我们通常忽略 CPU 开销，主要计算磁盘访问的次数。

基本符号:
- b: 需要传输的数据块 (block) 数量。
- S: 寻道 (seek) 次数。
- t_T: 传输一个 block 的时间 (Transfer time)。
- t_S: 一次寻道的时间 (Seek time)。
总代价公式:

st = b × t_T + S × t_S

(意思是：总时间 = 搬运数据的时间 + 找数据位置的时间)

3. 选择操作 (Selection Operation)

如何在表中找到满足条件（例如 salary < 2500）的行？主要有线性扫描和索引扫描两种方式。

A. 线性扫描 (Linear Scan / A1)

适用场景: 没有任何索引，或者是堆文件。
代价:
- 最坏情况（扫描全表）: t_S + b_r × t_T 。
- 平均情况（等值查找且结果唯一）: t_S + (b_r/2) × t_T 。

B.二分查找（A2/binary search)

数据文件有序，在排序域做等值查询

C. 索引扫描 (Index Scan)

利用索引（如 B+ 树）跳着找数据。代价取决于索引类型（聚集/非聚集）和查询类型（等值/范围）。假设 B+ 树高度为 h_i。

算法	场景	关键点	代价估算 (Cost)
A2	聚集索引 + 等值 (主键)	数据按顺序存，找到索引直接取数据	(h_i + 1) × (t_T + t_S)
A3	聚集索引 + 等值 (非主键)	可能会有多个匹配项，但它们物理上存储在一起	h_i(t_T + t_S) + t_S + t_T × b (b是匹配块数)
A4	辅助索引 + 等值	坑点: 匹配的记录可能散落在磁盘各处，每读一条记录可能都要重新寻道	(h_i + n) × (t_T + t_S) (n是匹配记录数)
A5	聚集索引 + 范围 (A > v)	找到第一个值，然后顺着物理顺序往下读	类似 A3，很高效
A6	辅助索引 + 范围	同样因为物理存储不连续，如果n 很大，性能极差，甚至不如全表扫描	(h_i + n) × (t_T + t_S)

🧠 重点提示: 对于辅助索引（Secondary Index），如果查询结果很多（n 很大），使用索引可能比全表扫描还慢，因为随机 I/O (Seek) 太多了！

D. 复杂选择 (Complex Selections 不清楚)

第一类：处理 AND (Conjunction)

场景：WHERE age = 20 AND dept = 'CS'。我们需要同时满足这两个条件的记录。

A7: 单索引过滤 (Conjunctive selection using one index)

核心逻辑： “擒贼先擒王”。
怎么做：
1. 在所有条件中，挑出一个 代价最小 （选择性最好、有索引）的条件。
2. 利用这个条件对应的索引，先把这一批候选记录从磁盘读进内存。
3. 对于剩下的条件，直接在内存里对刚才读进来的记录进行测试过滤。

A8: 组合索引 (Conjunctive selection using composite index)

核心逻辑： “一步到位”。
怎么做：
- 如果数据库里正好有一个包含多个字段的 组合索引 （Composite Index，比如建立在(ID,dept_name) 上的索引），那就直接用这个索引查。
- 这种方式通常最快，因为索引直接覆盖了查询条件，不需要回表或者做额外的内存过滤。

A9: 标识符交集 (Intersection of Identifiers)

核心逻辑： “多管齐下，先求交集”。
怎么做：
1. 如果每个条件都有索引，那就分别去查这些索引。
2. 注意！这一步 不读数据 ，只拿 指针 （Record Pointers/Identifiers，也就是数据的地址）。
3. 在内存里把这几组指针求交集 (Intersection)。
4. 最后，只去取那些“在交集里”的指针对应的实际数据。
优点： 避免了读取那些只满足一个条件但不满足另一个条件的无效数据块，节省了 I/O。

第二类：处理 OR (Disjunction)

场景：WHERE age = 20 OR dept = 'CS'。只要满足其中一个条件就行。

A10: 标识符并集 (Union of Identifiers)

核心逻辑： “各自为战，汇总再去重”。
怎么做：
1. 分别利用各个条件的索引，查出满足条件的记录指针集合。
2. 在内存里对这些集合求并集 (Union)。
3. **根据并集里的指针去磁盘取数据。
关键限制：
- 只有当所有参与 OR 的条件都有索引时，这个算法才适用¹³。
- 如果其中哪怕有一个条件没有索引（比如age有索引，但在dept上没索引），数据库通常只能放弃这一招，被迫去做全表扫描 (Linear Scan)。因为没有索引的那个条件可能藏在表的任何角落，不扫全表就找不全。

4. 排序 (Sorting)

当内存放不下整个表时，需要进行外部归并排序 (External Sort-Merge)。

过程:
1. 分段排序 (Create runs): 读入一部分数据到内存，排好序，写回磁盘。
2. 归并 (Merge runs): 将排好序的片段（Runs）逐步合并成一个大的有序文件。

5. 连接操作 (Join Operation) ✨ 核心考点

连接（Join）通常是最耗时的操作。

A. 嵌套循环连接 (Nested-Loop Join)

逻辑: 两层 for 循环。外层表每一行，都去内层表扫描一遍。
代价: 极高。最坏情况下（内存只能放一个 block），需要 n_r × b_s + b_r 次传输。
优化: Block Nested-Loop (一次处理一块，减少 I/O)；总是把小表作为外层表。

B. 索引嵌套循环连接 (Indexed Nested-Loop Join)

逻辑: 外层表循环，内层表利用索引查找，不需要全表扫描内层表。
代价: b_r(t_T + t_S) + n_r × c (c 是单次索引查找的代价)。
适用: 内层表有索引时非常快。

C. 归并连接 (Merge-Join)

前提: 两个表都必须在连接字段上排好序。
逻辑: 两个指针对齐扫描，类似归并排序的合并步骤。
代价: 非常低，每个 block 只读一次。b_r + b_s 次传输。
限制: 只能用于等值连接 (Equi-joins)。

D. 哈希连接 (Hash-Join)

逻辑: 用哈希函数把两个表的数据划分到不同的桶 (Bucket/Partition)。只有同一个桶里的数据才可能匹配。
适用: 等值连接。

6. 表达式求值 (Evaluation of Expressions)

当一个查询包含多个操作（如先选择，再投影，再连接）时，如何传递数据？

实体化 (Materialization):
- 把每一步的中间结果都存到磁盘临时表中。
- 缺点: 慢，需要大量的磁盘写操作。
流水线 (Pipelining):
- 像工厂流水线一样，上一步产生一个元组（Tuple），立刻传给下一步处理，不写磁盘。
- 优点: 高效，无需临时文件，不仅省空间还省时间。

好的，没问题。这份笔记将完全按照“辅导书”的硬核风格编写，剥离废话，通过逻辑结构、核心公式和算法步骤来拆解《数据库系统原理》第16章“查询优化”的核心考点。

📚 数据库系统原理核心笔记：查询优化 (Query Optimization)

查询优化概述 (Overview)

查询优化的核心目标是为给定的 SQL 查询找到执行成本（Cost）最低的执行计划。

1.1 优化流程 (Procedure)

查询优化通常分为三个核心步骤：

查询重写 (Query Rewriting): 利用关系代数的等价规则 (Equivalence Rules)，将初始的关系代数表达式转换为逻辑上等价但效率更高的形式（生成等价查询树）。
计划生成 (Plan Generation): 为逻辑查询树中的每个操作（如连接、选择）标注具体的实现算法（如 Hash Join, Index Scan），并决定是采用流水线 (Pipelining) 还是物化 (Materialization) 策略，生成候选执行计划。
代价评估与选择 (Cost Estimation & Selection): 基于统计信息估算每个计划的执行代价，选择最优或次优计划。

1.2 为什么需要优化？

同一个 SQL 语句可以对应多种等价的关系代数表达式，其执行效率差异巨大。

案例： σ_{r.A = s.A}(r × s) （先做笛卡尔积再筛选）的效率远低于 r ⋈ s （直接连接）。
差异量级： 优化前后的代价差异可能达到秒级 vs 天级。

查询重写与等价规则 (Equivalence Rules)

这是基于启发式规则 (Heuristics) 进行优化的理论基础。如果两个关系代数表达式在任何合法的数据库实例上产生相同的结果集，则称它们是等价的。

2.1 核心等价规则 (Key Rules)

选择操作 (Selection):
- 串接律 (Cascade): σ_{θ₁ ∧ θ₂}(E) = σ_θ₁(σ_θ₂(E))。这意味着可以将复杂的 AND 条件拆分为多个简单的选择。
- 交换律 (Commutativity): σ_θ₁(σ_θ₂(E)) = σ_θ₂(σ_θ₁(E))。这允许调整过滤条件的顺序，先执行过滤性强的条件。
投影操作 (Projection):
- 串接律: Π_L₁(Π_L₂(...(Π_{L_n}(E))...)) = Π_L₁(E)，其中 L₁ ⊆ L₂。只保留最后需要的列。
连接操作 (Join) —— 重点:
- 交换律: E₁ ⋈ E₂ = E₂ ⋈ E₁。
- 结合律: (E₁ ⋈ E₂) ⋈ E₃ = E₁ ⋈ (E₂ ⋈ E₃)。这构成了连接顺序选择 (Join Ordering) 的基础。
- 小技巧: 通常将较小的关系作为连接操作的左操作数（Outer Relation）以降低代价。
选择下移 (Pushing Selection) —— 核心优化手段:
- Rule 7a: 如果选择条件 θ₀ 只涉及 E₁ 的属性，则 σ_θ₀(E₁ ⋈ E₂) = (σ_θ₀(E₁)) ⋈ E₂。
- Rule 7b: 如果条件可以拆分，应分别下推到对应的子表达式中：σ_{θ₁ ∧ θ₂}(E₁ ⋈ E₂) = (σ_θ₁(E₁)) ⋈ (σ_θ₂(E₂))。
- 目的: 尽早过滤数据，减小参与连接的元组数量。
投影下移 (Pushing Projection):
- Rule 8: 将投影操作尽可能下移到连接之前，仅保留后续操作需要的属性（连接属性 + 最终结果属性），以减少中间结果的宽度（元组大小）。

2.2 启发式优化算法的 6 个步骤 (Heuristic Optimization Steps)

这是一套标准的处理流程，用于将初始查询树转换为优化后的查询树：

分解选择: 利用 Rule 1 将连接条件（Conjunctive Selection）分解为单个选择操作序列。
下移选择: 利用 Rule 2, 7a, 7b, 11，将选择操作尽可能移动到查询树的叶端。
重排叶节点: 利用 Rule 6 (结合律/交换律) 调整叶节点顺序，让限制性最强 (Most Restrictive) 的选择操作最先执行。
替换笛卡尔积: 利用 Rule 4a，将相邻的“笛卡尔积 + 选择”合并为“连接”操作 (⋈)。
下移投影: 利用 Rule 3, 8a, 8b, 12，将投影操作下移，甚至在每一层都增加投影，尽早丢弃无用属性。
识别流水线: 将查询树分解，识别可以流水线执行的子树。

统计信息与基数/代价估计 (Statistics & Cost Estimation)

代价估算 (Cost Estimation) 是基于数据库目录 (Catalog) 中的统计信息来进行的。

3.1 关键统计指标 (Catalog Information)

n_r: 关系 r 的元组总数。
b_r: 关系 r 占用的磁盘块数。
l_r: r 中每个元组的平均字节大小。
f_r: 块因子，即一个磁盘块能容纳的元组数 (b_r = ⌈n_r/f_r⌉)。
V(A, r): 属性 A 在关系 r 中的不同值个数 (Distinct Values)。

3.2 结果大小估算公式 (Size Estimation Formulas)

准确估算中间结果的大小 (Cardinality) 是计算代价的前提。

1. 选择操作 (σ):

等值查询 (A = a): 假设数据均匀分布，结果行数为 n_r/V(A, r)。
主键等值 (ID = key): 结果行数为 1。
范围查询 (A ≤ v): 利用最大最小值进行线性插值：$n_r \cdot \frac{v - min(A,r)}{max(A,r) - min(A,r)}$。
复杂条件 (Conjunction): 假设条件独立，$\sigma_{\theta_1 \land \theta_2}(r) = n_r \cdot \frac{S_1}{n_r} \cdot \frac{S_2}{n_r}$。

2. 连接操作 (r ⋈ s):

外键连接: 如果 r 与 s 的连接基于 s 的外键（指向 r 的主键），则结果大小严格等于 s 的大小 (n_s)。
一般连接: 如果两个表的连接属性都不是主键，估算公式取较小值： $$ ze = \min \left( \frac{n_r \cdot n_s}{V(A, r)}, \frac{n_r \cdot n_s}{V(A, s)} \right) $$

优化方法与策略 (Optimization Approaches)

4.1 基于代价的优化 (Cost-Based Optimization - CBO)

原理: 枚举所有可能的执行计划，计算每个计划的代价，选择最小者。
连接顺序 (Join Ordering): 连接操作的顺序对代价影响巨大。对于 N 个表的连接，存在 (2(N − 1))!/(N − 1)! 种顺序，搜索空间极大。
解决方法: 采用动态规划 (Dynamic Programming) 算法，类似于矩阵连乘问题。对于子集 {r₁, r₂, ..., r_n} 的最优连接顺序只需计算一次并存储。

4.2 启发式优化 (Heuristic Optimization)

原理: 基于经验规则（如“尽早过滤”）直接修剪查询树，而不计算所有可能的代价。
适用性: 现代优化器通常结合使用 CBO 和启发式方法。先用启发式规则重写查询（如视图展开、条件化简），再用 CBO 选择具体的物理计划。

4.3 新兴技术 (AI4DB)

利用机器学习（如强化学习 RL）来解决传统基数估计（Cardinality Estimation）不准的问题。
利用 AI 自动枚举和选择连接顺序，甚至实现端到端的查询优化。