<未完成>数据库系统的算子执行

一觉醒来发现自己变成反面教材了, 我是不是不该退役啊?

查询计划

在关系型数据库中, 操作可以视为在可重集合上的关系代数运算的组合. 在第一篇文章中介绍了一些最常见的关系代数运算和对应的 SQL 语句. 关系代数的每个运算都根据其语义接受一个或多个关系, 并产出新的关系. 将每个运算视作一个算子, 接受一个或多个表, 产出新的表. 这个由算子(operator)组成的有向无环图(DAG)就是查询计划(Query Plan).

例如, 对于 SQL 语句

1
2
3

SELECT name
FROM R JOIN S ON R.id = S.id
WHERE S.age > 18

这其中包含连接 \(\bowtie\)、投影 \(\pi\)、选择 \(\sigma\). 从算子的角度来看, 首先是从关系 \(R\) 和 \(S\) 中提取元组的 access method, 接着是对 \(S\) 中的元组进行选择的 operator: \(\sigma_{age>18}(S)\), 然后是将选择后的 \(S'\) 中的元组与 \(R\) 做连接的 operator: \(T = R \bowtie_{R.sid=S'.sid} S'\), 最后对这个连接后的临时表的元组进行投影操作的 operator: \(\pi_{name}(T)\). (实际上不一定会成表, 即不会在 Catalog 中有这个临时表的元数据, 不过无论是什么, 在算子看来只是一堆元组而已)

而上一篇博客介绍了从表中提取元组、执行查询(包括高效的单点查询和范围查询)的 Access Method, 本文主要介绍一些常见算子的实现方式, 如 JOIN, ORDER BY, GROUP BY. <TODO: 查证一下 SELECT, WHERE 等算子实现>

总结来说: 数据在算子构成的逻辑管道中流通最终被塑造为查询结果.

在查询计划的有向无环图中, 一个让元组能够连续流动而无需间接存储的过程就是一个 pipeline, 而阻碍某个 pipeline (导致元组被迫”停下”被存储等待) 的运算符就是 pipeline break, 例如 JOIN, ORDER BY. 对于 Hash Join, 需要对其中一个表建立哈希表(Pipeline #1), 而另一个表则可以作为另一条 Pipeline #2 在 #1 结束后启动, 则对于另一个表来说这条数据流动没有阻塞; 对于 Sort-Merge Join, 则需要三条 pipeline: 两个表分别 sort 都是 breaker, 最后再在 JOIN 那个算子节点上继续流动; 对于 ORDER BY, 必须间接存储, 等所有元组都获取到后才能排序.

不过这是总体上的概念, 具体的实现上大致可分为三种模型, 主要的区别在于获取元组的多少: 是”一次获取一个元组”(迭代器模型), 还是”一次获取全部元组”(物化模型), 还是”一次获取一部分元组”(向量批处理模型).

三种算子执行模型

迭代器模型

就像迭代器一样, 每个算子有一个 Next() 函数, 负责计算并返回下一个元组, 通常是更高层的算子调用 Next() 并且进一步导致其子节点调用 Next(), 直到最底层的 FROM 负责 emit 出表中的原始元组, 整体就像从顶层往上拉数据一样, 所以称作 Top-to-Bottom Pull-based.

利于, 对于一个最简单的 FROM S:

1 2	for t in S: emit(t)

而选择则是:

1 2	for t in child.Next(): if predicate(t): emit(t)

Hash Join:

for t1 in left.Next():
    buildHashTable(t1)
for t2 in right.Next():
    if Some(t1) = probe(t2):
        emit(t1 ⨝ t2)

折鸦夜明け前

<未完成>数据库系统的算子执行

查询计划

三种算子执行模型

迭代器模型

物化模型

和向量批处理模型

两种方向

具体的算子执行

提供数据

更新

表达式求值和 JIT

Sorting

Aggregation

Join