数据库执行器初探

2023-10-29 database

简介

在 1994 年发表的 Volcano Model 论文中，提出了基于行的流式迭代模型，首先会从上到下发起拉取数据请求，然后数据从下往上返回，默认会一行一行返回，不过部分会优化为小批，例如 4K、8K 等。

SQL Execution

这样可以简单抽象一系列标准接口，各个运算符可以充分解耦，易于扩展、实现，在数据量不太大的 TP 中还在使用；但需要大量调用 next() 函数，对分支预测不友好，破坏 CPU 流水线、Cache、TLB 失效等，导致在 AP 上效率很低。

于是，就有了 Vectorization 和 Compilation 两大优化方向，各自代表分别为 MonetDB (2005) 以及 Compiling Query Plan (2011) 两篇论文。进而，讨论如何充分利用硬件的特性，包括 Sort vs. Hash (2013) 对比 HashJoin 和 MergeJoin 实现性能，如何利用 SIMD 指令提升 SQL 算子性能。

另外，在 Morsel Driven Parallelism 中讨论了如何适配 NUMA 架构，同时将执行算子以物化算子拆分为不同的 Pipeline 调度执行，这也是大部分的 OLAP 引擎采用的方式，例如 Doris/StarRocks、ClickHouse、DuckDB 等。

并不是说 Pipeline 的执行效率一定要优于 Volcano 模型，例如 DataFusion 采用的是基于 Rust Async 实现的 Pull 模型基本与 DuckDB 持平，当然，基于 Tokio 的运行态 Pull 操作只是触发，实际执行可能还是 Push 模型。

算子

Join

HashJoin 含 Build 和 Probe 两个阶段，通常将小表作为 Build 表，以降低构建 Hash 表的成本，当前很多向量化实现会参考 Balancing Vectorized Query Execution with Bandwidth-Optimized Storage 中的向量化实现，包括 Datafusion、StarRocks、CockroachDB 等。

如下以 CockroachDB Vectorized Hash Joiner 以及 Datafusion 的代码进行介绍。

for row in table(left):  # build
    build_table[hash(row)] = row
for row in table(right): # probe
    if row in build_table:
        output(row)

参考