#database
# 1. Query Plan
SQL 语句 -> Query plan。
Operators 组织成 tree 的形式，数据从 leaves 流向 root，root 的输出就是查询结果。
-------------
# 2. Processing Models
## 2.1 Iterator Model
^4a72bd
最常见，绝大多数 row-based DBMS 会使用。
每个 operator 实现一个 `next` 函数：
- 每次调用 `next`，返回一个 tuple 或者 null marker（表示数据结束）
- operator 循环调用 children 的 `next` 来获取 tuples 进行处理
**pipeline breaker**：
operator 阻塞直到 children 吐出它们所有的 tuples。如 join、subquery、order-by
该模型下 LIMIT 很容易实现。
## 2.2 Materialization Model
每个 operator 一次性处理完所有的 input，并且一次性地输出所有的 output。
> The operator "materializes" its output as a single result.
适合 OLTAP workloads：
一般一次只访问少量的 tuples，优势在于**函数调用很少**。
不适合 OLAP 中间结果很大的查询：
因为可能需要将结果置换到磁盘。
## 2.3 Vectorization Model
类似 [[12-query-execution-1#2.1 Iterator Model | iteraotr model]] ，但 `next` 函数每次不是返回一个 tuple，而是返回**一批** tuples。
优势：
- 一次可以处理一批数据
- 有利于 SIMD
--------
# 3. Access Modes
## 3.1 Sequential Scan
优化：
- Prefetching
- Parallelization
- Buffer Pool Bypass
- Zone map、Late Materialization、Heap Clustering
### Zone map
- 可以单独的 zone map pages
- 缺点：
需要有维护开销
因此不适合 OLTP（更新多），更适合 OLAP（写一次读很多次）
### Late Materialization
- 通常更适用于 column store(每列数据是分散的），如果是 row store 一行的数据已经在一起。
- 每个 operator 传递尽可能少的信息（如 record id、column id）给下一个 operator
- 示例
```SQL
SELECT AVG(foo.c)
FROM foo JOIN bar
ON foo.b = bar.b
WHERE foo.a > 100
```
- SELECTION：只需要 a 列
- JOIN：只需要 b 列
- AVG：只需要 c 列
因此 operator 之间可以只传递 offsets，需要时根据 offset 去取数据
**重点：** 需要知道 query plan 的不同部分需要哪些数据
### Heap Clustering
或者叫 clustering index。
按照 clustering index 的顺序存储数据。
## 3.2 Index Scan
DBMS 挑选一个/多个索引来查找 query 需要的 tuples。
要点：quickly、限制无用功（避免读取不需要的 tuples）
使用哪个索引取决于：
- 索引包含了什么 attributes
- 查询引用了什么 attributes
- attribute 的值域
- predicate composistion
- 索引是否唯一
由 query optimizer 负责选择索引。
### Multi-Index Scan
每个索引都有帮助，selective 程度很高 **->** 使用 Multi-Index Scan
1. 使用每个索引计算 record ids 集合
2. 基于查询的谓词，合并这些集合（union vs intersect）
3. 获取 records，然后应用剩余的谓词
Postgres 称之为 [Bitmap Scan](https://www.postgresql.org/message-id/
[email protected]) 。
### Index Scan Page Sorting
问题：直接按照索引去获取 tuples 会导致大量随机访问（index 的顺序跟 tuple 存储的顺序不一样）
**page sorting：**
1. 先找出所有需要的 tuples 的 record ids
2. 基于它们的 page id 进行排序
**order-by 消除：**
如果索引的顺序跟 order-by 指定的顺序一样
--------------------
# 4. Expression Evaluation
expression tree 存在于 operator 内部，比如 filter operator 中的 where 从句。
不同的 tree node 代表了不同的表达式类型：
- Comparisons （=，`<` ，`>`， `!=`）
- Conjunction（`AND`），Disjunction（`OR`）
- Arithmetric operators(`+`， `-`， `*`， `/`， `%` )
- Constant Values
- Tuple Attribute References
- Function Calls
expression evaluation 需要遍历 expression tree，会比较慢，优化：
- JIT compilation
> Expression trees are **flexible** but **slow**