Parsing and Translation#

第一步是把用户写的 SQL 查询翻译成数据库内部表示。

具体做两件事：

• parse：检查 SQL 语法是否正确；
• verify：检查查询中引用的 relation、attribute 是否存在。

之后，系统会把查询翻译成关系代数表达式。

1
select name, title
2
from instructor natural join (teaches natural join course)
3
where dept_name = 'Music' and year = 2009;

Optimization#

同一个 SQL 查询可以对应多个等价的关系代数表达式，也可以对应多个不同的物理执行计划。

优化器的任务是：

在所有等价的 evaluation plans 中，选择估计代价最低的计划。

优化包括两层：

1. 逻辑优化：改变关系代数表达式结构，例如 selection pushdown。
2. 物理优化：为每个操作选择具体算法，例如 index scan、hash join、merge join。

Evaluation#

最后一步是执行。

查询执行引擎接收 optimizer 产生的 query-evaluation plan，按计划运行各个操作，访问存储系统并返回结果。

Evaluation Plan#

evaluation plan 指明了：

• 每个关系代数操作采用什么算法；
• 操作之间如何协调；
• 中间结果是物化到磁盘，还是通过 pipeline 直接传给父操作；
• 是否使用索引、排序、hash table 等物理结构。

同一个逻辑表达式可以有不同的物理计划：

这里不仅说明了有 selection / join / projection，还说明了：

• instructor 上的 selection 使用 index；
• teaches 上的 selection 使用 linear scan；
• 下层 join 使用 merge join；
• 上层 join 使用 hash join；
• projection 后还需要 sort 去重。

EXPLAIN#

大多数数据库支持查看优化器选出的执行计划。

常见命令：

1
EXPLAIN <query>;

它通常显示：

• optimizer 选择的 plan；
• 每个操作的 cost estimate；
• 使用的 index / scan / join algorithm。

不同数据库语法略有不同：

• Oracle：explain plan for <query>，再查询 dbms_xplan.display；
• SQL Server：set showplan_text on；
• PostgreSQL：EXPLAIN <query> 和 EXPLAIN ANALYZE <query>。

EXPLAIN ANALYZE 会真正执行查询，并显示实际运行统计信息。

PostgreSQL 中的 cost 常写成：

1
startup_cost..total_cost

含义是：

• startup_cost：产生第一条 tuple 前的代价；
• total_cost：产生全部结果的总代价。

代价模型#

查询总代价通常可以从多个角度衡量：

• disk accesses
• CPU time
• network communication
• memory usage

但在传统数据库代价模型中，磁盘 I/O 通常是主导因素，也比较容易估计。

所以本章简化为：

1
Cost = block transfer cost + seek cost

即：

这里：

• $t_T$：传输一个 block 的时间；
• $t_S$：一次 seek 的时间。

典型值：

NOTE

本章公式通常忽略 CPU cost 和最终输出写盘 cost。

真实数据库系统会把 CPU、内存、并发、网络等因素也纳入优化器代价模型。这里只是为了推导算法代价，先抓最主要的 I/O 因素。

buffer 对代价估计的影响#

很多算法都能利用额外 buffer 降低 I/O。

但可用内存大小受下面因素影响：

• 系统总内存；
• buffer pool 当前状态；
• 其他并发查询；
• 操作系统进程；
• 数据是否已经在 buffer 中。

因此，代价估计常常使用保守假设：

只假设操作拥有它执行所需的最小 buffer。

如果实际运行时数据已经在 buffer 中，真实代价可能显著低于估计代价。

File Scan#

1
scan every block of relation r
2
  test every tuple
3
  output tuple if it satisfies the selection condition

1
select *
2
from student
3
where ID = '12345';

Index Scan#

index scan 使用索引来定位 tuple。

前提是：

selection condition 必须作用在 index 的 search key 上。

clustering index：

• clustering index：数据文件本身按 index search key 的顺序存放，或者至少相近值尽量放在一起；
• secondary index：index leaf 按 search key 排序，但数据文件本身不按这个 search key 排序。

1
A: 0, 5, 10, 20, 30, 30, 30, 50, 60

1
A: 10, 30, 5, 60, 30, 0, 50, 30

A2 Clustering B+-tree Index, Equality on Key#

条件形式：

$$\sigma_{A=v}(r)$$

其中 $A$ 是 key，并且有 primary / clustering B+-tree index。

由于 key 唯一，只会返回一条记录。

代价：

$$Cost = (h_i + 1)(t_T + t_S)$$

含义：

• 访问 B+ 树从 root 到 leaf，共 $h_i$ 个 index blocks；
• leaf entry 中有指向真实记录的 pointer；
• 再访问 1 个 data block。

假设要查：

1
select *
2
from r
3
where A = 30;

B+ 树查找过程可以理解成：

1
root block
2
  -> internal block
3
  -> leaf block containing 30
4
  -> data block containing the actual tuple

如果 $h_i = 3$，则大约访问：

1
3 个 index blocks + 1 个 data block = 4 个 blocks

因为这些 block 在磁盘上不保证连续，所以按每个 block 一次随机 I/O 估计：

$$4(t_T+t_S)$$

真实系统中 root 和上层 internal nodes 往往在 buffer 中，所以实际代价可能更小。

A3 Clustering B+-tree Index, Equality on Nonkey#

条件仍然是 equality，但属性不是 key。

$$\sigma_{A=v}(r)$$

这时 $A=v$ 可能返回多条记录。

因为是 clustering index，满足条件的记录在数据文件中通常连续存放。

设匹配记录占 $b$ 个连续 data blocks，代价为：

$$Cost = h_i(t_T + t_S) + t_S + b \cdot t_T$$

公式分解：

1
h_i(t_T+t_S) : 走 B+ 树，从 root 到 leaf，找到第一个 v
2
+t_S          : seek 到第一个匹配 data block
3
+b*t_T        : 顺序读 b 个连续 data blocks

假设 dept_name 不是 key，很多教师都属于 Music 系。

1
select *
2
from instructor
3
where dept_name = 'Music';

如果 instructor 文件按 dept_name 聚集存放，那么数据可能是：

1
Biology ...
2
Comp. Sci. ...
3
Music, Music, Music, Music ...
4
Physics ...

B+ 树只负责帮你找到第一条 Music。

找到之后，不需要每条记录都随机跳一次。因为所有 Music 记录基本连续，直接顺序读这一段即可。

这就是为什么后半部分是：

$$t_S + b t_T$$

不是：

$$b(t_S+t_T)$$

A4 Secondary B+-tree Index, Equality on Key#

如果是 secondary B+-tree index，但 equality 条件作用在 key 上，则也只返回一条记录。

代价与 A2 相同：

$$Cost = (h_i + 1)(t_T + t_S)$$

区别在于：

• secondary index 的顺序和数据文件物理顺序不同；
• 但 key equality 只取一条记录，所以只会根据 pointer 跳到一个 data block。

假设数据文件按 ID 排序，但我们在 email 上建了 secondary index。

1
select *
2
from student
3
where email = 'a@zju.edu.cn';

如果 email 是 key，那么只匹配一个学生。

虽然数据文件不是按 email 排的，但 index leaf 中的 pointer 会直接指向那条 student record。

所以流程仍是：

1
查 B+ 树 email index -> 找到 pointer -> 读 1 个 data block

不会因为是 secondary index 就找不到。

A4’ Secondary B+-tree Index, Equality on Nonkey#

这是很容易变贵的一种情况。

条件作用在 nonkey 上，可能返回 $n$ 条记录；这些记录在数据文件中未必连续。

设：

• $m$：matching pointers 存放在 $m$ 个 index blocks 中；
• $n$：matching records 数量。

代价估计：

$$Cost = (h_i + m + n)(t_T + t_S)$$

公式分解：

1
h_i : 走 B+ 树到 leaf
2
m   : 读取存放 matching pointers 的 index blocks
3
n   : 根据 n 个 pointers 取 n 条真实记录

最贵的是最后的 $n$。

因为 secondary index 不决定数据文件的物理顺序，所以这 $n$ 条真实记录可能分散在 $n$ 个不同 data blocks 中。

假设数据文件按 ID 排序，但有一个 secondary index 建在 dept_name 上。

1
select *
2
from instructor
3
where dept_name = 'Music';

索引中 Music 的 pointer 可能是：

1
Music -> ptr(record 18), ptr(record 203), ptr(record 967), ptr(record 1802)

这些真实记录在数据文件中可能分布在完全不同的位置：

1
block 2, block 40, block 190, block 350

于是每取一条记录都可能要随机 I/O。

这就是 secondary index on nonkey 可能很差的原因。

WARNING

secondary index on nonkey 在匹配结果很多时可能非常差。

如果匹配了表中 30% 的记录，使用 secondary index 可能产生大量随机 I/O。此时一次 linear file scan 反而可能更便宜。

Selections Involving Comparisons#

比较条件包括：

范围查询的核心问题是：

满足条件的记录能不能连续读？

A5 Clustering B+-tree Index, Comparison#

如果 relation 按 $A$ 排序，并且有 clustering index：

• 对于 $A \ge v$：用 index 找到第一条 $\ge v$ 的 tuple，然后顺序扫描后面的记录；
• 对于 $A \le v$：从 relation 开头开始顺序扫描，直到第一条 $>v$ 的 tuple。

对于 $A \ge v$，代价与 A3 类似：

$$Cost = h_i(t_T + t_S) + t_S + b \cdot t_T$$

这里 $b$ 是满足范围条件的记录所在 block 数。

假设文件按 A 排序：

1
0, 5, 10, 20, 30, 30, 30, 50, 60

查询：

1
where A >= 30

流程是：

1
1. 用 B+ 树找到第一个 A >= 30 的位置
2
2. 跳到这个 data block
3
3. 从 30 开始顺序读到文件末尾

如果满足条件的记录在 4 个连续 blocks 中，那么读数据部分是：

$$t_S + 4t_T$$

因为定位一次后可以连续读。

NOTE

为什么 $A \le v$ 常常不使用 index？

如果文件本身已经按 $A$ 排序，查询：

1
where A <= 30

满足条件的记录在文件开头：

1
0, 5, 10, 20, 30, 30, 30

直接从文件开头顺序扫到第一个大于 30 的记录即可。

使用 index 只能帮你找到边界，但仍然要读前面那一大段，反而多了索引访问成本。

A6 Secondary B+-tree Index, Comparison#

如果使用 secondary index 处理范围查询：

• 对于 $A \ge v$：找到第一条 index entry，再顺序扫描 leaf entries；
• 对于 $A \le v$：从 index leaf 开始扫到第一条 $>v$；
• 对每个 pointer 再去数据文件中取实际记录。

问题是：

index leaf 中的 entries 是连续的，但它们指向的数据记录不一定连续。

假设 secondary index 上满足 A >= 30 的 entries 连续：

1
30 -> ptr(block 20)
2
31 -> ptr(block 2)
3
32 -> ptr(block 88)
4
33 -> ptr(block 7)

扫描 index leaf 很顺序，但取真实 records 时要跳到很多不同 data blocks。

所以如果范围很大，A6 可能比 linear scan 更差。

Implementation of Complex Selections#

复杂 selection 条件通常由 conjunction、disjunction、negation 构成。

1
select *
2
from instructor
3
where dept_name = 'Music' and salary > 90000;

1
1. 用 dept_name index 找出 Music 系教师
2
2. 把这些 tuple 读入内存
3
3. 在内存中继续检查 salary > 90000

1
(dept_name, salary)

1
where dept_name = 'Finance' and salary = 80000

1
dept_name index -> 找到所有 Finance 教师
2
salary index    -> 找到所有工资 80000 的教师
3
然后取交集

1
(dept_name, salary) index -> 直接找 ('Finance', 80000)

1
where dept_name = 'Finance' and salary = 80000

1
dept_name='Finance' -> {r1, r3, r8, r20}
2
salary=80000        -> {r2, r3, r20, r50}
3
intersection        -> {r3, r20}

1
where dept_name = 'Music' or salary > 100000

1
dept_name='Music' -> {r1, r7, r9}
2
salary>100000     -> {r2, r7, r20}
3
union             -> {r1, r2, r7, r9, r20}

1
A or B

1
where dept_name <> 'Music'

Bitmap Index Scan#

PostgreSQL 的 bitmap index scan 用来弥合两种极端：

• secondary index scan：匹配少时很好，匹配多时可能大量随机 I/O；
• linear file scan：匹配多时稳定，匹配少时浪费。

基本思想：

先用 index 找到满足条件的 record ids，再用 bitmap 汇总这些 records 所在的 data pages，最后按 page 读取数据。

bitmap 的粒度是 page / block：

1
1 bit per page

步骤：

1. 用 index scan 找到满足条件的 record ids；
2. 根据 record id 找到其所在 page，并把 bitmap 中对应 bit 置为 1；
3. 再扫描或访问 relation，只读取 bit 为 1 的 pages。

1
page:    0 1 2 3 4 5 6 7
2
bitmap:  0 1 0 1 0 0 1 0

性能特点：

• 如果只有少量 bit 为 1，表现接近 index scan；
• 如果大多数 bit 为 1，表现接近 linear scan；
• 一般不会比两种极端方案差很多。

TIP

这里的 bitmap index scan 和 Chapter 14 中的 bitmap index 不完全一样。

• bitmap index 是一种索引结构；
• bitmap index scan 是 PostgreSQL 的一种执行策略，用 bitmap 收集将要访问的 data pages。

External Sort-Merge#

外部排序最常用的是 external sort-merge。

设：

• $M$：可用内存页数；
• $b_r$：relation $r$ 的 block 数。

算法分两阶段：

1
Phase 1: create sorted runs
2
Phase 2: merge runs

直观理解：

内存一次只能装一小段，就先把每一小段内部排好序；然后像归并排序一样，把很多有序小段合成一个全局有序文件。

1
i = 0
2
repeat until end of relation:
3
  read M blocks into memory
4
  sort these blocks in memory
5
  write sorted data to run R_i
6
  i = i + 1

1
b_r = 1000 blocks
2
M = 100 pages

1
R0: 第 1-100 blocks 排好序
2
R1: 第 101-200 blocks 排好序
3
...
4
R9: 第 901-1000 blocks 排好序

Merge Runs#

如果：

$$N < M$$

则一次 merge pass 就够。

内存分配：

• $N$ 个 buffer pages 分别给 $N$ 个 input runs；
• 1 个 output buffer page。

merge 过程：

1
read first block of each run into memory
2
repeat:
3
  choose smallest tuple among input buffer pages
4
  write it to output buffer
5
  delete it from its input buffer
6
  if an input buffer becomes empty:
7
      read next block of that run
8
until all input buffers are empty

假设有两个有序 runs：

1
run 1: 1, 4, 9, 13
2
run 2: 2, 3, 10, 11

merge 时维护两个指针：

1
run1 指向 1
2
run2 指向 2

比较指针所指元素：

1
1 < 2，输出 1，run1 指针后移到 4
2
2 < 4，输出 2，run2 指针后移到 3
3
3 < 4，输出 3，run2 指针后移到 10
4
4 < 10，输出 4，run1 指针后移到 9
5
...

最后得到：

1
1, 2, 3, 4, 9, 10, 11, 13

多路 merge 和这个逻辑一样，只是从多个 input buffers 的当前最小 tuple 中选最小者。

如果：

$$N \ge M$$

则需要多轮 merge。

每一轮最多合并：

$$M - 1$$

个 runs，因为还要保留 1 个 output buffer。

每一轮会让 run 数大约缩小 $M-1$ 倍，直到只剩一个最终有序 run。

如果 $M=11$，初始有 90 个 runs。

每一轮最多合并 10 个 runs，所以一轮后 run 数变成：

$$\left\lceil \frac{90}{10} \right\rceil = 9$$

这时 9 个 runs 小于 11 个 buffer pages，下一轮就能合并成最终结果。

过程是：

1
90 runs --pass 1--> 9 larger runs --pass 2--> 1 final sorted run

Cost of External Sort-Merge#

设 merge pass 数为：

更精确地说，括号内可写成初始 run 数 $\lceil b_r/M \rceil$。

1
b_r = 1000
2
M = 100

1
读原 relation 1000
2
写初始 runs 1000
3
merge 时读初始 runs 1000
4
最终输出写盘不计

1
读一段连续 blocks：1 次 seek
2
写一个 sorted run：1 次 seek

1
b_r = 1000
2
M = 100
3
P = 1

advanced version#

simple version 的问题是：

merge 时每个 run 只分配 1 个 buffer block，会导致 seeks 过多。

改进做法：给每个 run 分配 $b_b$ 个 buffer blocks。

这样每次可以连续读写 $b_b$ 个 blocks。

一轮可合并的 run 数变成：

这里的 -1 是因为要留一组 buffer 给 output。

merge pass 数：

block transfers 仍然是：

因为一次读 1 个 block 还是一次读 $b_b$ 个 blocks，总共读写的数据量不变。

seek 数减少为：

1
b_r = 1000
2
M = 100
3
b_b = 5

NOTE

advanced version 的本质是：

用更多 buffer 换更少 seeks。

$b_b$ 增大时，每次 seek 后能连续读写更多 blocks；但一轮能合并的 runs 变少，可能导致 merge pass 增加。

所以这里存在 trade-off。

Nested-Loop Join#

计算 theta join：

最直接的算法是：

1
for each tuple t_r in r:
2
  for each tuple t_s in s:
3
    if (t_r, t_s) satisfies theta:
4
      output t_r concatenated with t_s

其中：

• $r$ 是 outer relation；
• $s$ 是 inner relation。

特点：

• 不需要 index；
• 可用于任意 join condition；
• 会检查所有 tuple pairs，代价很高。

1
student natural join takes

1
Alice(ID=1) 和 takes 的 4 条记录逐一比较 -> 匹配 DB、Math
2
Bob(ID=2)   和 takes 的 4 条记录逐一比较 -> 匹配 OS
3
Cindy(ID=3) 和 takes 的 4 条记录逐一比较 -> 无匹配

如果 buffer 最坏情况下只能放两个 relation 各一个 block，代价为：

公式含义：

• 读 outer relation 自身：$b_r$；
• outer 中每一条 tuple 都要触发一次 inner relation 全表扫描：$n_r \cdot b_s$；
• 每次重新扫描 inner，近似一次 seek，共 $n_r$ 次；
• 读 outer blocks 也估计 $b_r$ 次 seeks。

如果较小 relation 能完全放入内存，应把它作为 inner relation。

此时代价可降到：

Block Nested-Loop Join#

nested-loop join 按 tuple 配对，block nested-loop join 按 block 配对。

算法：

1
for each block B_r of r:
2
  for each block B_s of s:
3
    for each tuple t_r in B_r:
4
      for each tuple t_s in B_s:
5
        if (t_r, t_s) satisfies theta:
6
          output t_r concatenated with t_s

核心变化：

普通 nested-loop 是 outer 每条 tuple 扫一遍 inner；block nested-loop 是 outer 每个 block 扫一遍 inner。

因此扫描 inner 的次数从 $n_r$ 次降到 $b_r$ 次。

最坏代价：

公式含义：

• outer 的每个 block 都要读一次，共 $b_r$；
• 对 outer 的每个 block，都完整扫描一次 inner，共 $b_r b_s$；
• 每处理一个 outer block，约一次 outer seek 加一次 inner scan seek，所以 $2b_r$。

最好情况，如果 inner relation 保留在内存中：

1
student: 100 blocks
2
takes:   400 blocks

使用更多 buffer 的改进#

如果内存有 $M$ 个 blocks，可以把 outer relation 按 $M-2$ 个 blocks 为单位读入。

剩下两个 blocks：

• 1 个给 inner relation；
• 1 个给 output。

outer 被分成：

$$\left\lceil \frac{b_r}{M-2} \right\rceil$$

个 chunks。

每个 chunk 都要扫描一遍 inner relation。

代价：

$$Cost_{transfer} = \left\lceil \frac{b_r}{M-2} \right\rceil b_s + b_r$$$$Cost_{seek} = 2\left\lceil \frac{b_r}{M-2} \right\rceil$$

设：

1
student: b_r = 100 blocks
2
takes:   b_s = 400 blocks
3
M = 12 blocks

每次可读入 outer 的：

$$M-2=10$$

个 blocks。

outer chunks 数：

$$\lceil100/10\rceil=10$$

所以只需要扫描 takes 10 次，而不是 100 次。

block transfers：

$$10 \cdot 400 + 100 = 4100$$

这比只用 1 个 outer block 的 40100 又少了一个数量级。

如果 outer relation 能放入内存，即：

$$b_r \le M-2$$

则代价为：

$$b_s + b_r \text{ block transfers} + 2 \text{ seeks}$$

其他优化：

• 如果 equi-join attribute 在 inner relation 中是 key，找到第一个匹配后即可停止 inner loop；
• inner relation 可正向、反向交替扫描，配合 LRU 保留部分 block，减少重复 I/O。

NOTE

正向 / 反向交替扫描的意思是：

1
第 1 次扫 inner：从头到尾
2
第 2 次扫 inner：从尾到头
3
第 3 次扫 inner：从头到尾

这样上一轮刚读到 buffer 里的尾部 blocks，下一轮可能还能继续使用，减少重新读盘。

Indexed Nested-Loop Join#

如果满足：

• join 是 equi-join 或 natural join；
• inner relation 的 join attribute 上有 index；

则可以用 index lookup 替代 inner relation 的文件扫描。

算法：

1
for each tuple t_r in outer relation r:
2
  use index on s to find matching tuples in inner relation s
3
  output matches

最坏情况中，outer relation 每个 tuple 都要做一次 index lookup。

代价：

其中 $c$ 是对 inner relation 做一次 selection 的代价。

如果两个 relation 的 join attributes 上都有索引，通常选择 tuple 数较少的 relation 作为 outer relation。

1
ID=1 -> ptr(takes row 1), ptr(takes row 2)
2
ID=2 -> ptr(takes row 3)
3
ID=4 -> ptr(takes row 4)

1
Alice(ID=1): 用 takes.ID index 查 1 -> DB, Math
2
Bob(ID=2):   用 takes.ID index 查 2 -> OS
3
Cindy(ID=3): 用 takes.ID index 查 3 -> no match

1
4 次 index block 访问 + 1 次 data block 访问 = 5

1
读 student 一次：100
2
5000 个 student tuple 各查一次 takes index：5000 * 5

WARNING

Indexed nested-loop join 不一定总是快。

如果 inner index 是 secondary index，而且每次 lookup 返回很多分散 records，那么 $c$ 会很大。

例如 dept_name 上的 secondary index，每个 department 有大量员工，查一次可能返回很多随机 data blocks。此时 indexed nested-loop 可能输给 block nested-loop 或 hash join。

Merge Join#

merge join 也叫 sort-merge join。

适用于：

• equi-join；
• natural join。

基本步骤：

1. 如果两个 relation 尚未按 join attribute 排序，先排序；
2. 对两个有序 relation 做 merge；
3. 对 join attribute 相同的 tuple 进行配对输出。

核心思想：

两边都按 join key 排序后，可以像归并排序一样用两个指针从前往后扫。

1
ID=1 Alice
2
ID=2 Bob
3
ID=4 Cindy
4
ID=5 David

1
ID=1 DB
2
ID=1 Math
3
ID=3 OS
4
ID=4 AI
5
ID=5 DB

1
student join takes on student.ID = takes.ID

1
student.ID=1, takes.ID=1  -> 相等，输出 Alice-DB, Alice-Math
2
student.ID=2, takes.ID=3  -> 2 < 3，student 指针后移
3
student.ID=4, takes.ID=3  -> 4 > 3，takes 指针后移
4
student.ID=4, takes.ID=4  -> 相等，输出 Cindy-AI
5
student.ID=5, takes.ID=5  -> 相等，输出 David-DB

关键区别：

普通 merge 只需要取较小值推进；merge join 遇到重复 join key 时，需要输出所有匹配组合。

1
r 中 ID=1 有 2 条：r1, r2
2
s 中 ID=1 有 3 条：s1, s2, s3

1
r1-s1, r1-s2, r1-s3
2
r2-s1, r2-s2, r2-s3

如果两个 relation 已经按 join attribute 排好序，并且相同 key 的 tuple 能放进内存，则每个 block 只需读一次。

代价：

如果 relation 未排序，还要加上 sorting cost。

公式含义：

• $b_r+b_s$：两个 relation 各顺序扫描一遍；
• $\lceil b_r/b_b\rceil$：读 $r$ 时，每次 seek 后连续读 $b_b$ blocks；
• $\lceil b_s/b_b\rceil$：读 $s$ 同理。

buffer 分配优化#

设总 buffer memory 为 $M$ pages，分给 relation $r$ 的 buffer 数为 $x_r$，分给 relation $s$ 的 buffer 数为 $x_s$。

约束：

$$x_r + x_s = M$$

估计代价：

$$b_r + b_s + \left\lceil \frac{b_r}{x_r} \right\rceil + \left\lceil \frac{b_s}{x_s} \right\rceil$$

其中前两项是 block transfers，后两项近似是 seeks。

为了最小化 seek，近似最优分配为：

$$x_r = \frac{\sqrt{b_r}M}{\sqrt{b_r}+\sqrt{b_s}}$$$$x_s = \frac{\sqrt{b_s}M}{\sqrt{b_r}+\sqrt{b_s}}$$

直观理解：

block 数越多的 relation，应分到更多 buffer；但比例不是 $b_r:b_s$，而是 $\sqrt{b_r}:\sqrt{b_s}$。

假设：

1
b_r = 100
2
b_s = 400
3
M = 30

则：

$$\sqrt{100}=10, \quad \sqrt{400}=20$$

buffer 分配比例：

1
r : s = 10 : 20 = 1 : 2

所以：

$$x_r=10, \quad x_s=20$$

不是按照 $100:400=1:4$ 分。

原因是 buffer 的边际收益递减。给大表更多 buffer 是合理的，但不需要按表大小线性分配。

Hybrid Merge Join#

如果：

• 一个 relation 已经按 join attribute 排序；
• 另一个 relation 在 join attribute 上有 secondary B+-tree index；

可以使用 hybrid merge join。

步骤：

1. 将已排序 relation 与另一个 relation 的 B+-tree leaf entries 合并；
2. 得到的结果中包含未排序 relation 的 tuple 地址；
3. 按这些地址排序；
4. 按物理地址顺序扫描未排序 relation，用真实 tuple 替换地址。

这样做的原因是：

按物理地址顺序扫描，比根据 index pointer 随机访问大量 tuple 更高效。

1
对每个 student.ID，到 takes.ID index 找 pointer
2
再根据 pointer 随机访问 takes data blocks

1
1. 顺序扫描 student
2
2. 顺序扫描 takes.ID 的 B+ tree leaves
3
3. 先得到匹配的 takes record addresses
4
4. 把这些 addresses 按磁盘物理位置排序
5
5. 最后按物理顺序读取 takes records

Hash Join#

hash join 适用于：

• equi-join；
• natural join。

它的核心思想是：

join key 相同的 tuple 经过同一个 hash function 后，一定落入同一个 partition。

设 join attributes 为 JoinAttrs，hash function 为 $h$。

将 $r$ 和 $s$ 分区：

那么只需要比较：

不需要比较 $r_i$ 和 $s_j$，其中 $i \ne j$。

1
ID=1 -> partition 1
2
ID=2 -> partition 2
3
ID=3 -> partition 0
4
ID=4 -> partition 1

1
student partition 1 只需要和 takes partition 1 比较
2
student partition 2 只需要和 takes partition 2 比较
3
student partition 0 只需要和 takes partition 0 比较

1
1. Partition build input s using hash function h.
2
2. Partition probe input r using the same hash function h.
3
3. For each partition i:
4
     load s_i into memory
5
     build an in-memory hash index on s_i using another hash function
6
     scan r_i tuple by tuple
7
     for each t_r in r_i:
8
         find matching t_s in s_i
9
         output t_r concatenated with t_s

1
student -> student_0, student_1, student_2
2
takes   -> takes_0, takes_1, takes_2

1
load student_0 into memory, build hash table on ID
2
scan takes_0, for each tuple probe hash table
3

4
load student_1 into memory, build hash table on ID
5
scan takes_1, for each tuple probe hash table
6

7
load student_2 into memory, build hash table on ID
8
scan takes_2, for each tuple probe hash table

1
M = 20 blocks
2
b_instructor = 100
3
b_teaches = 400

Hybrid Hash Join#

hybrid hash join 适合：

• memory 相对较大；
• build input 大于内存，但不是大很多。

核心优化：

build relation 的第一个 partition 直接留在内存中，不写回磁盘。

这样 probe relation 的第一个 partition 也可以直接 probe，不需要先写盘再读回。

NOTE

hybrid hash join 的直观理解：

普通 hash join 会把所有 partitions 都写到磁盘，再读回来 join。

hybrid hash join 发现：既然内存够放一个 build partition，就不要把它写出去了。probe relation 中对应 partition 到来时，直接和内存中的 build partition join。

Complex Joins#

1
select *
2
from r, s
3
where r.A = s.A and r.B > s.B;

1
r.B > s.B

1
where r.A = s.A or r.C = s.C

1
r.A = s.A 的 join
2
r.C = s.C 的 join

Semijoin#

semijoin 记作：

含义是：

输出 $r$ 中那些至少能在 $s$ 中找到一个匹配 tuple 的 tuple，但输出结果只包含 $r$ 的属性。

如果某个 tuple $r_i$ 在 $r$ 中出现 $n$ 次，并且至少有一个 $s_i$ 与它匹配，那么它在 semijoin 结果中也出现 $n$ 次。

也就是说，semijoin 保留 $r$ 中 tuple 的重复次数。

可以由普通 join 表达为：

但直接这样做可能产生很大的中间结果。

1
Alice 选了 DB 和 Math -> join 结果里 Alice 出现两次
2
Bob 选了 OS          -> Bob 出现一次

1
Alice 在 takes 中有匹配 -> 输出 Alice 一次
2
Bob 在 takes 中有匹配   -> 输出 Bob 一次
3
Cindy 无匹配            -> 不输出

更好的实现方式：

• block nested-loop semijoin：扫描 $s$，只要发现某个 $r$ tuple 有匹配就输出该 $r$ tuple，并可停止继续找该 tuple 的其他匹配；
• indexed nested-loop semijoin：对每个 $r$ tuple 在 $s$ 的 index 中查是否存在匹配，存在就输出 $r$ tuple；
• merge semijoin：两个输入按 join key 排序，扫描时只输出左侧匹配 tuple；
• hash semijoin：对 $s$ 建 hash table，对 $r$ probe，只要有匹配就输出 $r$ tuple。

NOTE

semijoin 和 join 的区别在输出。

• join 输出 $r$ 和 $s$ 拼接后的 tuple；
• semijoin 只输出 $r$ 的 tuple；
• semijoin 常用于减少数据传输或减少后续操作输入规模。

Joins over Spatial Data#

空间数据 join 的条件通常不是等值比较，而是：

• contains
• overlaps
• contained in
• nearest neighbor
• distance within a threshold

这类条件没有简单的一维排序关系，因此：

• merge join 通常不适用；
• hash join 也很难保证满足空间谓词的对象落入同一 hash bucket；
• nested-loop join 总能用，但大数据集上通常很慢。

更好的做法是使用 indexed nested-loop join，并利用空间索引：

• R-tree
• k-d tree
• k-d-B tree
• quadtree

这些索引支持快速检索重叠、包含、邻近等空间关系。

1
find all restaurants within 1km of each hotel

1
for each hotel:
2
  use spatial index on restaurants
3
  find restaurants whose coordinates are within 1km

Duplicate Elimination#

duplicate elimination 可以通过 sorting 或 hashing 实现。

Projection#

projection 的基本过程是：

1. 对每个 tuple 取出 projection list 中的属性；
2. 如果需要集合语义，再做 duplicate elimination。