CMU 15-445/645-笔记-12-Query 执行-part1

2022-11-28 12:36 作者:dengluzhanghao 0人读过 | 我要投稿

## 课程目标

1. 如何处理查询计划(Query Plan)，即如何组织这个执行流程，让这些 operator 之间的数据流以某种方式传递，用来快速的产生结果

2. 访问方式：用索引还是循序?

3. 对表达式的评估

## Processing Model

这个 Processing Model 指的是，用某种方式，去执行一个查询计划

是从上到下，还是从下到上?在每个 operator 之间应该传什么

- Iterator Model(很多数据库系统都在用)

- Materialization Model(Iterator Model 的特定版本，只用在内存型数据库系统中)

- Vectorized/Batch Model(基于 Iterator Model，主要用于分析型 workload 中)

### Iterator Model

> 1980 末到 1990 初期有一个非常有影响力的系统叫 Volcano，这个系统是由写了 B+ Tree 那本书的作者发明的，这个人也实现了 Volcano 查询优化

对于 Iterator Model 而言，它的工作方式是，对于所有的 operator (Join、Sorting)来说，它们都要去实现一个 Next 函数

在查询计划树中，父节点会调用其子节点上定义的 Next 函数，子节点会返回这个 Next 函数的结果(下一个父节点需要处理的 tuple)，总之，这个是层层的递归调用的过程，对于查询计划树来讲，父节点的 Next 会层层调用子节点的 Next，直到达到这个树的叶子节点为止。然后将处理好的结果(tuple) 层层向上发送，做逐个处理

这个模型的好处在于，对于一个 tuple 能够尽可能的被多次使用，在一个 operator 处理完之后能返回传入下一个 operator 做继续处理(能够减少磁盘 I/O，因为 tuple 是在 page 中，而 page 是在内存中)

> 在一个查询计划中，对一个给定的 tuple 进行一系列加工处理的过程，叫 Pipeline

那么它是如何工作的?

上图展示的是不同 operator 对应用的不同 Next 函数，本质上也都是 for 循环

步骤 2、3 都是对左边节点进行处理

步骤 2、4、5 都是对右边节点进行处理(左边节点处理完之后)

当进行 Join 操作时，如果构建的 hash table 中有任何一条 tuple 能匹配上 Join 的条件，就将 Join 之后的结果发送给父节点，即步骤 1

使用 Iterator Model 的数据库有那些呢? 见下图

但是有些 operator 不允许一直进行这种 Pipeline 处理(比如 Joins、SubQueries, ORDER BY 等)

比如在步骤 2 中

```

for t1 in left.Next():

buildHashTable();

```

这个 for 循环没执行完，hash table 也没构建完的情况下，只能不停的执行步骤 3 去拿数据，而不是把结果从步骤 2 向上传递到步骤 1，也就是这里的 Pipeline 操作没有被执行

使用 Iterator Model ，对于输出控制比如 limit ，就很容易实现它

### Materialization Model

基本思路是，每次调用 Next 函数时，不让它只返回一个 tuple，而是返回所有的 tuple。这样就可以不用一直去调用 Next 函数来逐个获取这些 tuple 了

这个 Model 的输出结果可以是一个 materialized row 或者是单个列(这个列上保存了所有的 tuple 值)

例子图如下(没有 Next 函数了，或者说它被封装在了 out.output 函数中，返回的都是一个 output buffer，它里面包含了所有的 tuple)

步骤 2、3 都是对左边节点进行处理

步骤 2、4、5 都是对右边节点进行处理(左边节点处理完之后)

当进行 Join 操作时，如果构建的 hash table 中有任何一条 tuple 能匹配上 Join 的条件，就将 Join 之后的结果发送给父节点，即步骤 1

那么又有哪些数据库使用了这个

使用 Materialization Model 的数据库有那些呢? 见下图

Materialization Model 适用于 OLTP 场景，因为在这个场景中，都是一次获取少量的记录

记录少 -> (在内存中)调用 Next 函数次数少 -> CPU 跳到硬盘上写数据次数少(CPU 有 latch ，保证事务) -> 函数阻塞时间短 -> 减少 CPU 阻塞

> 数据量一多，如果有跨事务的数据很容易出现死锁问题

### Vectorization Model

那么每次调用 Next 函数时，如果传递的是一些 tuple 而不是单个 tuple，是不是会更高效?对于 Vectorization Model 来讲，是的

> 在现代 CPU 中有一些指令允许一次对一堆数据进行多个操作，比如 simd

一个对 Vectorization Model 优化的处理是，用一个 output buffer 对要发送的数据量做一个检查，如果 output buffer 的容量足够大，那么就可以向上返回一堆 tuple(其实就是先将tuple 放到这个 output buffer 中，等这个 buffer

满了再向上传递)

如下图所示

这个优化使得 Vectorization Model 支持 OLAP 了，因为它减少了每个 operator 调用 Next 的次数

而上图中也有很多数据库支持

显而易见，Vectorization Model 就是 Iterator Model 的一种增强版本

## Plan Processing Direction

上述所使用的 3 种 Model 都是 top-down 方案，即从根节点开始，调用 Next 方法来得到输出，整体上它会自上而下的调用 Next，然后将数据向上传递到根节点处

当然这个数据流也可以从(Query Plan)底部开始，将数据向上推(虽然很少见，但 VoltDB /德国的 HyPer 都使用了这个方案)。但是这种方式必须确保正在处理的数据能够放在 CPU 缓存和寄存器中(也就是说这种方式需要对内存位置和内存分配的操作足够地细致才行)

1. top-down 方式适用于面向磁盘的数据库系统

2. bottom-top 方式适用于面向内存的数据库系统

## Access Methods

Access Methods，即一种通过它从数据库系统的表里面查数据的方法，这个方法会伴随整个 Next 函数(因为 Next 函数里面也需要查数据)

基本上有 3 种 Access Methods

1. 循序扫描

2. 索引扫描

3. 多索引/bit map 扫描

### 循序扫描

简单来说，就是在 operator 中有一大堆 for 循环

在获取下一个 page 中的 tuple 时，operator 需要去维护迭代 for 循环中调用 Next 函数结束时的状态(每一次返回时，那个 tuple 所在的位置)，这样每次回头再次调用 Next 时，就可以从上次结束时的状态的地方继续处理

这通常被称之为游标(cursor)

### 循序扫描-优化

一些能让循序扫描变快的方法如上

1. Prefetching(用 2 个 buffer 来进行 Join 操作)

2. Buffer Pool Bypass(用 1 个小 buffer 对查询进行缓存，而不是去污染 buffer pool 缓存)

3. Parallelization(下节课会介绍)

重点是下面 3 个

### Zone Maps

Zone Maps 是用来提前计算好关于 page 的一些信息，后续访问时就可以决定要不要去访问这些 page

基本思想是，对于数据库表中每个 page 来说，它会根据 page 来计算生成一些额外的元数据，这些元数据是关于该 page 中给定属性相关值的信息

例子

比如在上图的表中，只有 5 个 tuple

对此，Zone Map 会提前计算出这个表中这一列的一些聚合信息

如果现在有这么一个查询，即

```

SELECT * FROM table WHERE val > 600;

```

有了 Zone Map 之后，这个查询会先去查 Zone Map 上的数据，发现这个 table 中没有一个 tuple 的值是 > 400 的，于是直接跳过这个 table

Zone Map 可以保存在一个专门的 Zone Map block/page 中，上面保存了不同 page 下的 Zone Map

> Vertica、MemSQL、Amazon RedShift、Oracle、DB2、Cloudera Impala、Netezza 等有应用 Zone Map

但是要维护这些 Zone Map 数据会是一个麻烦，因为假如 page 中的数据不断更新的话，就得不停维护这些 Zone Map，所以 Zone Map 在 OLTP 数据库中是不适用的，因为维护成本很高

但对于 OLAP 数据库来说，因为其写少读多的特性，适合应用 Zone Map

### Late Materialization

在列存储数据库中，可以将 operator 间的数据做延迟传递

SIMD 指令会将这些数据的 offset 值或者 column ID 给出来，从而做到延迟传递/获取的功能

为什么列储存需要做这些?

因为在列存储中，为了获取单个 tuple 的所有数据，需要做一大堆不同的读操作，因为这些数据被拆散到不同的列中了，所以为了提升性能，需要尽可能延迟这些读操作

例子

假设要对 foo 和 bar 这 2 张表进行 Join

在对应的查询计划树中，首先要处理的就是 filter operator，即只需要 a 这一列

根据查询计划树，后面就不需要 a 这个列了，那么这个时候只需要将 b 和 c 相对于 a 的 offset 值或者判断条件上传即可，并不需要后面将整个 b 和 c 上传

对于 b 的 Join 操作来说也是如此

对于 c 来说，由于 offset 的关系，它知道 c 在哪里，所以直接就根据这个拿到磁盘中 c 这一列，计算出最终结果

### Heap Clustering

### Index Scan

索引扫描，主要是为了识别在表中有哪些索引，方便快速查找数据，避免不必要的操作，在查询计划树中传递更少的数据给下一个 operator

选择索引也是一项技术活，取决于上面那个图中所提到的

例子

假设有这么一个查询

已经为 age 和 dept 建立了索引的情况下，在这个查询中，要使用哪些索引呢?这取决于表中这些数据的值

场景 1，肯定是要根据 dept 索引来查，因为一共就 2 个人在 cs，直接查就能查到，而如果使用 age 索引来查，那基本和循序扫描没啥区别

场景 2，这种情况就可以使用 age 索引了，因为它更具有选择性(selective)(当然这里直接做循序扫描会更好，因为还要遍历一遍索引着实没有那个必要)

### Muti-Index Scan

多索引扫描指的是通过不同的索引进行多次查找，基于判断条件，将查找结果进行合并

例子

依然是前面那个语句

先找出 age < 30 的 record ID

再找出 dept 为 CS 的所有 record ID

最后在其交集里面取 country 为 US 的数据

### Index Scan Page Sorting

如果使用的是非聚簇索引，那么查询时只需要沿着叶子节点扫描就行，扫描时随机跳到不同 page 上的不同 record ID 上，因为这些 tuple 排列的方式和索引中叶子节点的排列方式不一样

在最糟糕的情况下，假设只有一个 buffer page，同时往这个 buffer pool 里面放入一个 page，然后每次沿着叶子节点进行扫描时，都会读取一个 page，如果查看的 page 和接受到的 page 不同，那就必须要做一次磁盘 I/O 来重新获取下这个 page

如果输出结果不是基于索引的 id 来排序，即可能是基于其他属性进行的排序，但没有根据这个创建索引，那么在对数据进行查找之前，数据库引擎会沿着叶子节点扫描，获取到所有的 record ID，然后根据 page ID 先对它们进行排序

那么对于每个组中的每个 page 来说，都需要一次 I/O 来获取它，并且会先把当前 page 中所有 tuple 处理完毕后再去处理下一个 page

> 如果在聚簇索引叶子节点中间做插入，会引发页分裂(合并的 page 需要进行 split 处理)，而聚簇索引依赖主键来快速的做顺序插入，但一旦中间插入，整个主键就会被重建，树的中间节点都会发生改变，叶子节点里面的 key/value 也会做移动，也就是说在 split 时，这些叶子节点就无法准确的和底层这些 page 链接起来(原来的 key/value 对应的 page 就变了)

## Expression Evaluation