# Query Processing

## 简介

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SKqDH3suePXuli3Z0%2FScreen%20Shot%202019-03-08%20at%208.46.34%20PM.jpg?alt=media\&token=10e40f56-f4fe-437f-bb24-32c7e788f3b2)

如上图所示，通常一个 SQL 会被组织成树状的查询计划，数据从 leaf nodes 流到 root，查询结果在 root 中得出。而本节将讨论在这样一个计划中，如何为这个数据流动过程建模，大纲如下：

* Processing Models
* Access Methods
* Expression Evaluation

## Processing Model

DBMS 的 processing model 定义了系统如何执行一个 query plan，目前主要有三种模型:

* Iterator Model
* Materialization Model
* Vectorized/Batch Model

不同模型的适用场景不同。

### Iterator Model

query plan 中的每步 operator 都实现一个 next 函数，每次调用时，operator 返回一个 tuple 或者 null，后者表示数据已经遍历完毕。operator 本身实现一个循环，每次调用其 child operators 的 next 函数，从它们那边获取下一条数据供自己操作，这样整个 query plan 就被从上至下地串联起来，它也称为 Volcano/Pipeline Model：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SPAXpoLiDtZYjPQzb%2FScreen%20Shot%202019-03-08%20at%209.05.30%20PM.jpg?alt=media\&token=0cf4dffc-d637-4d7a-99f9-f14004bf1fb1)

Iterator 几乎被用在每个 DBMS 中，包括 sqlite、MySQL、PostgreSQL 等等，其它需要注意的是：

* 有些 operators 会等待 children 返回所有 tuples 后才执行，如 Joins, Subqueries 和 Order By
* Output Control 在 Iterator Model 中比较容易，如 Limit，只按需调用 next 即可。

### Materialization Model

每个 operator 处理完所有输入后，将所有结果一次性输出，DBMS 会将一些参数传递到 operator 中防止处理过多的数据，这是一种从下至上的思路，示意如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SQydRFxzDN-0YMd92%2FScreen%20Shot%202019-03-08%20at%209.13.22%20PM.jpg?alt=media\&token=4c066390-2b3f-4bba-b582-b89e02072734)

materialization model：

* 更适合 OLTP 场景，因为后者通常指需要处理少量的 tuples，这样能减少不必要的执行、调度成本
* 不太适合会产生大量中间结果的 OLAP 查询

### Vectorization Model

Vectorization Model 是 Iterator 与 Materialization Model 折衷的一种模型：

* 每个 operator 实现一个 next 函数，但每次 next 调用返回一批 tuples，而不是单个 tuple
* operator 内部的循环每次也是一批一批 tuples 地处理
* batch 的大小可以根据需要改变（hardware、query properties）

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SSpL7OtEU8ncA5L95%2FScreen%20Shot%202019-03-08%20at%209.21.24%20PM.jpg?alt=media\&token=4eb27cd6-bc1d-45f7-9271-443e16357095)

vectorization model 是 OLAP 查询的理想模型：

* 极大地减少每个 operator 的调用次数
* 允许 operators 使用 vectorized instructions (SIMD) 来批量处理 tuples

目前在使用这种模型的 DBMS 有 VectorWise, Peloton, Preston, SQL Server, ORACLE, DB2 等。

### Summary

| Models           | Direction | Emits            | Target          |
| ---------------- | --------- | ---------------- | --------------- |
| Iterator/Volcano | Top-Down  | Single Tuple     | General Purpose |
| Vectorized       | Top-Down  | Tuple Batch      | OLAP            |
| Materialization  | Bottom-Up | Entire Tuple Set | OLTP            |

## Access Methods

access method 指的是 DBMS 从数据表中获取数据的方式，它并没有在 relational algebra 中定义。主要有三种方法：

* Sequential Scan
* Index Scan
* Multi-Index/"Bitmap" Scan

### Sequential Scan

顾名思义，sequential scan 就是按顺序从 table 所在的 pages 中取出 tuple，这种方式是 DBMS 能做的最坏的打算。

```python
for page in table.pages:
    for t in page.tuples:
        if evalPred(t):
            # do something
```

DBMS 内部需要维护一个 cursor 来追踪之前访问到的位置（page/slot）。Sequential Scan 是最差的方案，因此也针对地有许多优化方案：

* Prefetching
* Parallelization
* Buffer Pool Bypass
* (本节) Zone Maps
* (本节) Late Materialization
* (本节) Heap Clustering

#### Zone Maps

预先为每个 page 计算好 attribute values 的一些统计值，DBMS 在访问 page 之前先检查 zone map，确认一下是否要继续访问，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SYzTzVdvka1QB0F-K%2FScreen%20Shot%202019-03-08%20at%209.48.23%20PM.jpg?alt=media\&token=610df84c-2c70-432b-b90a-912a9bac6226)

当 DBMS 发现 page 的 Zone Map 中记录 val 的最大值为 400 时，就没有必要访问这个 page。

#### Late Materialization

在列存储 DBMS 中，每个 operator 只选取查询所需的列数据，若该列数据在查询树上方并不需要，则仅需向上传递 offsets 即可：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_S_fliTre1N8nN2oz2%2FScreen%20Shot%202019-03-08%20at%209.55.46%20PM.jpg?alt=media\&token=7cc8d85e-a851-4c5e-aa5d-69c55bca03ce)

#### Heap Clustering

使用 clustering index 时，tuples 在 page 中按照相应的顺序排列，如果查询访问的是被索引的 attributes，DBMS 就可以直接跳跃访问目标 tuples。

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SalhLkSOb7kD6A_yx%2FScreen%20Shot%202019-03-08%20at%2010.00.32%20PM.jpg?alt=media\&token=2b04bef0-8e8b-479d-b26a-5c3d4137070c)

### Index Scan

DBMS 选择一个 index 来找到查询需要的 tuples。使用哪个 index 取决于以下几个因素：

* index 包含哪些 attributes
* 查询引用了哪些 attributes
* attribute 的定义域
* predicate composition
* index 的 key 是 unique 还是 non-unique

这些问题都将在后面的课程中详细描述，本节只是对 Index Scan 作概括性介绍。

尽管选择哪个 Index 取决于很多因素，但其核心思想就是，越早过滤掉越多的 tuples 越好，如下面这个 query 所示：

```sql
SELECT * FROM students
 WHERE age < 30
   AND dept = 'CS'
   AND country = 'US';
```

students 在不同 attributes 上的分布可能如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_ScefnfeWAkOd66WZf%2FScreen%20Shot%202019-03-08%20at%2010.08.28%20PM.jpg?alt=media\&token=71c18274-06cb-4c68-96cb-309cd3e0ca12)

* Scenario #1：使用 dept 的 index 能过滤掉更多的 tuples
* Scenario #2：使用 country 的 index 能过滤掉更多的 tuples

#### Multi-index Scan

如果有多个 indexes 同时可以供 DBMS 使用，就可以做这样的事情：

* 计算出符合每个 index 的 tuple id sets
* 基于 predicates (union vs. intersection) 来确定是对集合取交集还是并集
* 取出相应的 tuples 并完成剩下的处理

Postgres 称 multi-index scan 为 Bitmap Scan。

仍然以上一个 SQL 为例，使用 multi-index scan 的过程如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_SeJOQCHNWwzK9pYNo%2FScreen%20Shot%202019-03-08%20at%2010.16.01%20PM.jpg?alt=media\&token=d62af38c-fab8-4291-9524-2ad2dae9faa2)

其中取集合交集可以使用 bitmaps, hash tables 或者 bloom filters。

#### Index Scan Page Sorting

当使用的不是 clustering index 时，实际上按 index 顺序检索的过程是非常低效的，DBMS 很有可能需要不断地在不同的 pages 之间来回切换。为了解决这个问题，DBMS 通常会先找到所有需要的 tuples，根据它们的 page id 来排序，完毕后再读取 tuples 数据，使得整个过程每个需要访问的 page 只会被访问一次。如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_ShA0GMpjwLpjmIrHN%2FScreen%20Shot%202019-03-08%20at%2010.28.29%20PM.jpg?alt=media\&token=efd41d96-a3f3-492c-802d-902715ffcdc8)

## Expression Evaluation

DBMS 使用 expression tree 来表示一个 WHERE 语句，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_SJmRDBsMOcTdYyKNm%2F-L_ShOP570xIvRR3bk4N%2FScreen%20Shot%202019-03-08%20at%2010.29.28%20PM.jpg?alt=media\&token=baba6a04-e026-4851-87ad-49827d40d321)

然后根据 expression tree 完成数据过滤的判断，但这个过程比较低效，很多 DBMS 采用 JIT Compilation 的方式，直接将比较的过程编译成机器码来执行，提高 expression evaluation 的效率。

## 参考

[slides](https://15445.courses.cs.cmu.edu/fall2018/slides/10-queryprocessing.pdf), video