DuckDB-源码分析（1）背景与应用

2019年，CWI发表了一篇关于DuckDB的论文：《DuckDB: an Embeddable Analytical Database》，旨在OLAP领域构建一个嵌入式的数据库，解决单点交互式数据分析的问题，并给边缘计算提供除SQLite之外的更优选择。在论文中，作者们总结DuckDB为在一个进程内的SQL OLAP DBMS，这句话至少有两个解读点：

1. DuckDB的工作方式应该和SQLite一致，即在进程内部运行，并不需要类似MySQL或者PG的等单独起一个数据库服务；
2. 作为AP系统，可以支撑一定复杂的数据分析和查询任务。

SQLite是在全球运行最多的关系型数据库管理系统，每个浏览器和操作系统以及各种嵌入式设备都能找到该数据库使用的痕迹。但是SQLite更多为TP任务服务，很难利用向量化、内存加速来提高数据分析的速度。所以DuckDB弥补了SQLite这方面的空白。

DuckDB 支持多种数据格式：

• CSV: 批量加载 CSV 文件并自动映射列内容；
• DataFrames: DuckDB 可以直接处理同一个 Python 进程中的 DataFrame 内存内容；
  JSON: DuckDB可以直接将JSON转换为关系型表格。也提供 JSON 数据类型；
• Parquet: DuckDB 可以查询 Parquet 文件及其架构元数据。查询中使用的谓词会下推到 Parquet 存储层进行计算，以减少加载的数据量。Parquet 是数据湖泊理想的列式格式，可用于读写数据；
• Apache Arrow: DuckDB 可以通过ADBC直接访问 Apache Arrow 列式数据，无需复制和转换数据；
• 云存储: DuckDB 可以访问云存储桶（例如 S3 或 GCP）中的数据，减少传输和复制基础设施，并允许廉价处理大量数据。

DuckDB官方提供了一个简单的WASM版本的在线环境：https://shell.duckdb.org/，可以直接在内部执行SQL，简单如下所示：

duckdb> SELECT count(*) FROM 'https://shell.duckdb.org/data/tpch/0_01/parquet/lineitem.parquet';
┌──────────────┐
│ count_star() │
╞══════════════╡
│        60175 │
└──────────────┘

duckdb> SELECT count(*) FROM 'https://shell.duckdb.org/data/tpch/0_01/parquet/customer.parquet';
┌──────────────┐
│ count_star() │
╞══════════════╡
│         1500 │
└──────────────┘

duckdb> SELECT * FROM 'https://shell.duckdb.org/data/tpch/0_01/parquet/orders.parquet' LIMIT 10;
┌────────────┬───────────┬───────────────┬──────────────┬─────────────┬─────────────────┬─────────────────┬────────────────┬───────────────────────────────────────────────────────────────────────────┐
│ o_orderkey ┆ o_custkey ┆ o_orderstatus ┆ o_totalprice ┆ o_orderdate ┆ o_orderpriority ┆ o_clerk         ┆ o_shippriority ┆ o_comment                                                                 │
╞════════════╪═══════════╪═══════════════╪══════════════╪═════════════╪═════════════════╪═════════════════╪════════════════╪═══════════════════════════════════════════════════════════════════════════╡
│          1 ┆       370 ┆ O             ┆    172799.49 ┆ 1996-01-02  ┆ 5-LOW           ┆ Clerk#000000951 ┆              0 ┆ nstructions sleep furiously among                                         │
│          2 ┆       781 ┆ O             ┆     38426.09 ┆ 1996-12-01  ┆ 1-URGENT        ┆ Clerk#000000880 ┆              0 ┆  foxes. pending accounts at the pending, silent asymptot                  │
│          3 ┆      1234 ┆ F             ┆     205654.3 ┆ 1993-10-14  ┆ 5-LOW           ┆ Clerk#000000955 ┆              0 ┆ sly final accounts boost. carefully regular ideas cajole carefully. depos │
│          4 ┆      1369 ┆ O             ┆     56000.91 ┆ 1995-10-11  ┆ 5-LOW           ┆ Clerk#000000124 ┆              0 ┆ sits. slyly regular warthogs cajole. regular, regular theodolites acro    │
│          5 ┆       445 ┆ F             ┆    105367.67 ┆ 1994-07-30  ┆ 5-LOW           ┆ Clerk#000000925 ┆              0 ┆ quickly. bold deposits sleep slyly. packages use slyly                    │
│          6 ┆       557 ┆ F             ┆      45523.1 ┆ 1992-02-21  ┆ 4-NOT SPECIFIED ┆ Clerk#000000058 ┆              0 ┆ ggle. special, final requests are against the furiously specia            │
│          7 ┆       392 ┆ O             ┆    271885.66 ┆ 1996-01-10  ┆ 2-HIGH          ┆ Clerk#000000470 ┆              0 ┆ ly special requests                                                       │
│         32 ┆      1301 ┆ O             ┆    198665.57 ┆ 1995-07-16  ┆ 2-HIGH          ┆ Clerk#000000616 ┆              0 ┆ ise blithely bold, regular requests. quickly unusual dep                  │
│         33 ┆       670 ┆ F             ┆    146567.24 ┆ 1993-10-27  ┆ 3-MEDIUM        ┆ Clerk#000000409 ┆              0 ┆ uriously. furiously final request                                         │
│         34 ┆       611 ┆ O             ┆     73315.48 ┆ 1998-07-21  ┆ 3-MEDIUM        ┆ Clerk#000000223 ┆              0 ┆ ly final packages. fluffily final deposits wake blithely ideas. spe       │
└────────────┴───────────┴───────────────┴──────────────┴─────────────┴─────────────────┴─────────────────┴────────────────┴───────────────────────────────────────────────────────────────────────────┘

再测试一下语言的API使用，也非常简单，这里以Python为例：

import duckdb
con = duckdb.connect()
con.sql("SELECT * FROM 'orders.parquet' LIMIT 10").show()
con.close()

┌────────────┬───────────┬───────────────┬──────────────┬─────────────┬─────────────────┬─────────────────┬────────────────┬───────────────────────────────────────────────────────────────────────────┐
│ o_orderkey │ o_custkey │ o_orderstatus │ o_totalprice │ o_orderdate │ o_orderpriority │     o_clerk     │ o_shippriority │                                 o_comment                                 │
│   int32    │   int32   │    varchar    │    double    │    date     │     varchar     │     varchar     │     int32      │                                  varchar                                  │
├────────────┼───────────┼───────────────┼──────────────┼─────────────┼─────────────────┼─────────────────┼────────────────┼───────────────────────────────────────────────────────────────────────────┤
│          1 │       370 │ O             │    172799.49 │ 1996-01-02  │ 5-LOW           │ Clerk#000000951 │              0 │ nstructions sleep furiously among                                         │
│          2 │       781 │ O             │     38426.09 │ 1996-12-01  │ 1-URGENT        │ Clerk#000000880 │              0 │  foxes. pending accounts at the pending, silent asymptot                  │
│          3 │      1234 │ F             │     205654.3 │ 1993-10-14  │ 5-LOW           │ Clerk#000000955 │              0 │ sly final accounts boost. carefully regular ideas cajole carefully. depos │
│          4 │      1369 │ O             │     56000.91 │ 1995-10-11  │ 5-LOW           │ Clerk#000000124 │              0 │ sits. slyly regular warthogs cajole. regular, regular theodolites acro    │
│          5 │       445 │ F             │    105367.67 │ 1994-07-30  │ 5-LOW           │ Clerk#000000925 │              0 │ quickly. bold deposits sleep slyly. packages use slyly                    │
│          6 │       557 │ F             │      45523.1 │ 1992-02-21  │ 4-NOT SPECIFIED │ Clerk#000000058 │              0 │ ggle. special, final requests are against the furiously specia            │
│          7 │       392 │ O             │    271885.66 │ 1996-01-10  │ 2-HIGH          │ Clerk#000000470 │              0 │ ly special requests                                                       │
│         32 │      1301 │ O             │    198665.57 │ 1995-07-16  │ 2-HIGH          │ Clerk#000000616 │              0 │ ise blithely bold, regular requests. quickly unusual dep                  │
│         33 │       670 │ F             │    146567.24 │ 1993-10-27  │ 3-MEDIUM        │ Clerk#000000409 │              0 │ uriously. furiously final request                                         │
│         34 │       611 │ O             │     73315.48 │ 1998-07-21  │ 3-MEDIUM        │ Clerk#000000223 │              0 │ ly final packages. fluffily final deposits wake blithely ideas. spe       │
├────────────┴───────────┴───────────────┴──────────────┴─────────────┴─────────────────┴─────────────────┴────────────────┴───────────────────────────────────────────────────────────────────────────┤
│ 10 rows                                                                                                                                                                                    9 columns │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

DuckDB的实现主要分为几个部分，parser、logical planner、optimizer、physical planner、execution engine和storage engine。

• Parser
  DuckDB的SQL parser直接使用Postgres的libpg_query，可以直接得到一个C结构体表示的parse tree。DuckDB将其转换成自己内部的C++对象，无缝接入。

• Logical Planner
  DuckDB的Logical planner由binder和plan generator两部分组成，binder将parse tree与schema的信息（列名、类型等）绑定。plan generator将parse tree转换成一棵逻辑查询算子（scan, filter, project等）结构树。经过planning阶段后生成logical plan，DuckDB同时保存所存储数据的统计信息，这些数据在logical plan生成阶段通过不同的expression trees向下传播，用于optimizer阶段优化查询计划。

• Optimizer
  DuckDB实现了RBO和CBO的优化器。Optimizer将前面logical planner生成的logical plan转换成一个等价但执行代价更小的计划。常见的优化方式有predicate pushdown、expression rewriting、join ordering等。

• Physical Panner
  Physical planner将logical plan转换成physical plan。在生成physical plan过程中，会选择合适的实现。

• Execution Engine
  DuckDB实现了一个向量化执行引擎，execution engine以火山的模式开始执行查询计划的。Query execution以从物理执行计划的root节点拉取chunk data开始。chunk data是结果集中间表或者基表的水平子集，递归的从子节点拉取数据，到scan operator为止。scan operator从persistent tables中读取chunk data。回溯到root节点的chunk是空时则代表该计划已经执行完。

可移植性问题没有选择JIT实现，因为JIT依赖编译组件，比如LLVM。

• Transaction
  DuckDB使用MVCC提供了ACID，DuckDB实现了HyPer的MVCC变体，就地更新数据，并将previous states保存在一个单独的undo buffer，用于并发事务或者中止。

• Storage
  DuckDB使用列式存储，并使用了读优化的数据存储布局。逻辑表水平划分为chunks of columns，这些chunk of columns压缩成physical block。physical block中保存min/max索引，用于在查询时判断该Block是否相关，裁剪block读的大小。也为每个column保留索引，优化列读。

作为新手学习OLAP，DuckDB是一个非常好的开始，相比于Clickhouse或者其他大型AP实现，其抽象和代码都相对清晰和完善，但是因为使用场景有限，面向云上和多核以及分布式下的设计就需要参考其他的数据库，接下来笔者会从不同部分对DuckDB进行展开和详细剖析。