PPT 07 查询处理
7. PPT 07 查询处理：同一句 SQL，数据库到底怎么跑¶
这一章以 第十一章 查询处理.docx 为主要讲解来源。PPT 给了算法名，Word 笔记真正讲清楚了 cost 为什么这么算，尤其是 selection、external sort、block nested-loop join、hash join。
全章主线：
7.1 代价符号：先把每个字母翻译成人话¶
| 符号 | 含义 |
|---|---|
| \(n_r\) | 关系 \(r\) 的 tuple 数 |
| \(b_r\) | 关系 \(r\) 占用的 block 数 |
| \(l_r\) | 关系 \(r\) 的一条 tuple 大小 |
| \(f_r\) | blocking factor，一个 block 能放多少 tuple |
| \(M\) | 内存 buffer 一共有多少个 block |
| \(t_T\) | 传输一个 block 的时间 |
| \(t_S\) | 一次 seek / 随机定位的时间 |
| \(V(A,r)\) | \(r\) 中属性 \(A\) 有多少个不同值 |
考试默认：
第一步永远是：
不要拿 tuple 数直接套 join 公式。
7.2 Selection：先判断全表扫还是用索引¶
Selection 就是 \(\sigma_{condition}(r)\)。
人话：
A1 线性扫描¶
如果没有可用索引，就扫整个文件。
如果文件连续存放：
如果条件是 key 等值查询，比如：
平均找到一半就能停：
但最坏情况还是可能扫完整表。
A2/A3 主索引或聚集索引¶
如果数据文件按属性 A 排序，并且 A 上有 B+ 树索引：
如果 A 是 key：
如果 A 不是 key：
所以聚集索引对范围查询很舒服。
A4/A4' 辅助索引¶
辅助索引的关键问题：
如果辅助索引查的是 key：
如果辅助索引查的是 non-key：
所以客观题常见结论：
7.3 多条件 selection：先用最能过滤的条件¶
如果条件是：
Word 笔记里的策略：
比如：
就先用 salary>100000。
常见算法：
A7：用一个索引先筛，再在内存里检查其他条件。
A8：如果有复合索引，优先用复合索引。
A9：每个条件分别用索引找 record id，再取交集。
A10：OR 条件可分别找 record id，再取并集；但最好每个条件都有索引。
7.4 External sort：内存放不下，就先分 run 再归并¶
如果关系 r 有 br 个 block，内存有 M 个 block。
第一阶段 run generation：
初始 run 个数：
这个阶段：
第二阶段 merge：
为什么是 M-1？
需要的归并轮数：
代价要看题目是否把最终结果写回磁盘。
常用记忆：
考试如果只问算法流程，就写：
7.5 Nested-loop join：最朴素，但通常最慢¶
Join 是 \(r \bowtie s\)。
人话：
Tuple nested-loop join：
如果外关系是 r，内关系是 s：
因为：
这个算法一般只是理解基线，真正考试更常算 block nested-loop join。
7.6 Block nested-loop join：外表一次装 M-2 个 block¶
Block nested-loop join 的画面：
为什么是 M-2？
公式：
seek 粗略理解：
做题模板：
例子：
R 做 outer：
S 做 outer：
选 R 做 outer。
7.7 Index nested-loop join：内表连接属性有索引时很香¶
Index nested-loop join 的条件：
画面：
如果 outer 是 r：
它适合：
如果每次查索引都返回很多分散记录，它也会变差。
7.8 Sort-merge join：两边有序时，像拉拉链¶
Sort-merge join 适用于等值连接，尤其是两边已经按 join key 排好序时。
流程：
如果两边已经排好序：
如果没排序，要先加外部排序成本。
它的直觉就是归并排序最后一步：
7.9 Hash join：先分桶，再桶内匹配¶
Hash join 是你当前最需要补画面的部分。
它只适合：
例如 \(r.A = s.A\)。
第一步：partition，按连接属性分桶¶
用同一个 hash 函数 h：
关键性质：
因此：
这一步就是把大问题切成很多小问题。
第二步：build/probe，桶内连接¶
对每个桶 i：
术语：
一般选小关系做 build input，因为它的每个 partition 更容易放进内存。
buffer 为什么限制 partition 数¶
如果要一次分成 N 个 partition：
内存一共 M 个 block，通常最多分 \(M-1\) 个 partition，还要留一个 input buffer。
什么时候不用 recursive partition¶
Hash join 希望 build input 的每个 partition 能放进内存。
如果 build relation 有 b_build 个 block，分成 N 个桶，平均每桶 \(b_{build} / N\)。
希望：
也就是每个 build partition 能放进内存，还留出输入/输出空间。
如果做不到：
2021 样卷画面¶
题目类似：
选 build：
最多 partition：\(M - 1 = 5\)。
s 平均每桶：\(20 / 5 = 4\) blocks。
内存可容纳 build partition：\(M - 2 = 4\) blocks。
刚好放下，所以不需要 recursive partition。
如果不递归，block transfer 近似：
对于上例：
题目如果要求算 seek，按它给的 bb、连续存放假设再补。
7.10 查询处理 A4 规则¶
先算 br，别直接用 nr。
全表扫：br transfers + 1 seek；key 平均 br/2。
secondary index 返回很多记录时可能很慢。
BNLJ：B(outer)+ceil(B(outer)/(M-2))*B(inner)，两边都试。
External sort：初始 runs = ceil(br/M)，每轮最多 merge M-1 个 runs。
Sort-merge join：两边已有序时约 br+bs；没序先加排序成本。
Hash join：等值连接；partition 后同编号桶 join。
Hash join build 选小表；最多 M-1 个 partition。
不递归 hash join transfers 约 3(br+bs)。
build partition 必须能放进内存，否则 recursive partition。