DuckDB 综述

date

Jul 11, 2023

slug

duckdb-overview

status

Published

Topic

TPCH 测试

DML 支持

TPCC 小量数据测试 100g OLTP 性能基准测试

100GB

500GB 1TB 场景的 TPCH （机器资源不足）

SQL 执行机制

优化器 cbo or rbo

执行器索引 pipeline 并行

支持 binlog 之类的吗主从或者说是复制策略吗

mmap

测试单写，批量写

批量读

如何理解嵌入

Background

DuckDB是一个开源OLAP数据库，专为分析数据管理而设计。与SQLite类似，它是一个可以嵌入到应用程序中的进程内数据库。in-process olap database

下面是 DuckDB 团队发现对于嵌入式 In-Process OLAP 的一些要求，并尝试解决它们：

组合 OLAP 和 ETL 的 workload：能够处理 AP workload 的同时不完全牺牲 OLTP 的性能，同时有效支持批量 append 和批量 update。

传输效率：需要很方便的在 application 和 DBMS 之间传递数据，因为不是所有任务都能在嵌入式数据库中完成，例如机器学习、画图等，所以需要很方便的在 DBMS 和 application 之间传递数据。而由于 In-Process OLAP 的好处是在同一地址空间内，可以非常方便的来传递数据。

弹性（Resilience）：边缘计算的 OLAP 所在的硬件和服务器级别的硬件差别非常大而且各异，更容易出现硬件问题，嵌入式DBMS要能够检测这些问题并防止数据损坏

Cooperation：系统需要优雅地适应资源争用（CPU or RAM），由于嵌入式数据库不再是机器的唯一使用者，因此它不能像以前那样持续使用所有硬件，否则会导致底层应用程序资源匮乏

Architecture

一个整体的架构图：

DuckDB 各个组件之间的架构非常的 "textbook"，也就是说会把整个数据库分为：

Parser, logical planner, optimizer, physical planner, execution engine, transaction and storage managers.

作为嵌入式数据库，DuckDB没有客户端协议接口或服务器进程，而是使用C/C++ API进行访问。此外，DuckDB提供了SQLite兼容层，允许以前使用SQLite的应用程序通过重新链接或库 overload 来使用DuckDB。

Parser

SQL Parser 源自 Postgres SQL Parser

Logical Planner

binder，解析所有引用的 schema 中的对象（如 table 或 view）的表达式，将其与列名和类型匹配。Binder 将 parse tree 与 schema 的信息（列名、类型等）绑定起来。Schema 信息保存在 catalog。
plan generator，将 binder 生成的 AST 转换为由基本 logical query 查询运算符组成的树，就得到了一颗 type-resolved logical query plan。 DuckDB 还保留存储数据的统计信息，并将其作为规划过程中不同表达式树的一部分进行传播。这些统计信息用于优化程序本身，并且也用于防止整数溢出

optimizer

DuckDB 实现了基于规则（rule-based）和基于代价（cost-based）的优化器。Optimizer 的主要任务是优化 SQL，它将前面 logical planner 生成的 logical plan 转换成一个等价但执行代价更小的 logical plan。常见的优化方式有谓词下推（predicate pushdown）、表达式重写（expression rewriting）、调整 join 顺序（join ordering）等。
使用动态规划进行 join order 的优化，针对复杂的 join graph 会 fallback 到贪心算法
会消除所有的 subquery
有一组 rewrite rules 来简化 expression tree，例如执行公共子表达式消除和常量折叠
Cardinality estimation 是使用采样和HyperLogLog 的组合完成的，这个过程将优化 logical plan。

Physical Planner 和 Execution Engine

Physical planner 和 execution engine 的代码都在 execution 目录下。 Physical planner 将 Logical plan 转换成 physical plan。Physical plan 是一个真正可以执行的物理计划。
DuckDB 最开始采用了基于 Pull-based 的 Vector Volcano 的执行引擎，后来切换到了 Push-based 的 pipelines 执行方法
DuckDB 采用了向量化计算来来加速计算，具有内部实现的多种类型的 vector 以及向量化的 operator
另外出于可移植性原因，没有采用 JIT，因为 JIT引擎依赖于大型编译器库（例如LLVM），具有额外的传递依赖。采用 SQL 的解释执行，而没有采用 SQL 的编译执行，原因是编译执行需要依赖编译组件，比如 LLVM，这会导致 DuckDB 的体积膨胀不少。

Transactions

DuckDB 通过 MVCC 提供了 ACID 的特性，实现了HyPer专门针对混合OLAP / OLTP系统定制的可串行化MVCC 变种。该变种立即 in-place 更新数据，并将先前状态存储在单独的 undo buffer 中，以供并发事务和 abort 使用

Storage

Storage 是 DuckDB 的列式存储引擎，处于整个 DuckDB 架构的最底层，负责提供数据的高效读写。
DuckDB 支持内存型和持久化型两种工作模式。其中，内存型不持久化数据，采用 InMemoryBlockManager 来管理数据
DuckDB 采用 SingleFileBlockManager 来管理外存上的数据。看这个名字就可以猜到，DuckDB 把所有数据都保存在了一个文件中。

DML 能力

DML(Data Manipulation Language)
The SQL commands that deal with the manipulation of data present in the database belong to DML or Data Manipulation Language and this includes most of the SQL statements. It is the component of the SQL statement that controls access to data and to the database. Basically, DCL statements are grouped with DML statements.
List of DML commands:
INSERT: It is used to insert data into a table.
UPDATE: It is used to update existing data within a table.
DELETE: It is used to delete records from a database table.
LOCK: Table control concurrency.
CALL: Call a PL/SQL or JAVA subprogram.
EXPLAIN PLAN: It describes the access path to data.

支持Delete Statement

DELETE语句从由table-name标识的表中删除行。如果WHERE子句不存在，则删除表中的所有记录。如果提供了WHERE子句，则仅删除WHERE子句结果为true的行。表达式为false或NULL的行将保留。 USING子句允许根据其他表或子查询的内容进行删除。

支持 Insert Statement

支持 Update Statement

支持 Call Statement

SQL 执行机制：向量化解释型执行引擎

Vector 向量

Vector Execution Format

Vector是在执行过程中用于存储内存数据的容器格式。

DataChunk 是一组Vectors，例如用于表示PhysicalProjection操作符中的列列表。

Data Flow

DuckDB使用向量化的查询执行模型。 DuckDB中的所有运算符都经过优化，可以处理固定大小的向量。这种固定大小在代码中通常称为“STANDARD_VECTOR_SIZE”。默认STANDARD_VECTOR_SIZE为2048元组。

Vector Format

向量在逻辑上表示包含单一类型数据的数组。DuckDB支持不同的向量格式，这使得系统能够以不同的物理表示存储相同的逻辑数据。这样可以实现更紧凑的表示，并且可能允许整个系统进行压缩执行。

DuckDB 内部是一个 vectorized push-based model，在执行过程中，vector 会在各个操作符之间流转，而不是一个个 tuple。

DuckDB 具有非常多自定义的 vector format，非常类似 Arrow，但是对于执行更加友好，是和 volox team 一起设计的，所以很 volex team 的 vector 有很多相似之处。

每个 vector 只保存单个类型的数据，这里有 logical array 和实际物理实现的区别，对外的操作符看来就是一致的 logical array。

可以看到下面举例了四种类型的 vector，各自都有自己的逻辑和物理表达形式。

而为了统一起来上层访问不同类型的 vector（避免 operator 算子处理不同 vector 时出现组合爆炸等问题），DuckDB 使用了一种统一的访问格式去访问底层不同的物理格式，也就是新增了一个 selection 数组，通过 DATA 和 Selection 去访问一个数据（类似 dictionary vector 结构）：

作为一款现代的 OLAP， DuckDB 也支持非结构化的类型存储，包括了 struct 和 list 这两种结构的 native 存储，DuckDB 不是直接存储 BLOB 或者 JSON 格式，而是使用已有的 vector 去递归表示两种结构。像 Struct 包含了三个 vector 去表达一个 struct 结构，list 通过 offset 和 length 去表达 list 中的每一个元素。这样可以直接利用已有的高性能算子去计算 nested type 的计算，而不是单独开发一套新的针对结构化类型的算子。

Execution 执行

最开始 DuckDB 采用 pull-based 的执行引擎，每个算子都实现了 GetChunk 算子，非常经典的 valcano 模型。

在这个模型中，单线程执行是非常自然的，多线程并行的能力不是很好；在 volcano 模型下，DuckDB 实现并行的方式是添加了一个 Exchange Operator，由优化器将执行计算分成多个 partition，每个partition内部的执行仍然是单线程的 pull-based 的执行，不感知并行，通过 Exchange 算子将多个并行执行的算子的结果给组合起来。

这么做有不少问题：

优化器在做 plan explosion 的时候很难找到最好的 plan，因为需要感知并行，来做不同的 partition 切分

就算找到了合适的 plan 去执行，在真正执行的过程中不同 partition 之间容易出现 data skew 的情况

另外还有就是中间结果物化的成本，例如在 Exchange Operator 执行的时候需要将下面的执行结果给物化下来

在 2021 年 DuckDB 切换到了 push-based 的执行引擎，并采用了 Morsel-Driven 的并行实现方式。

Move to push-based execution model #1583
Push-Based Execution in DuckDB - Mark Raasveldt

DuckDB 会将一个 plan 切分成多个 pipeline，每个 pipeline 采用 push-based 的方式进行数据传递和调用。

DuckDB 在实现 push-based 的执行引擎时，将不同的算子抽象成三种类型 Source，Operator 和 Sink，其 Source 和 Sink 能够感知到全局状态以及并行，中间的每个 Operator 算子都是不感知并行，只是做计算。

pull-based 的执行的控制流其实隐含在函数调用中（非常灵活和方便），但是 push-based 的执行能够显式的去控制执行流，而不是只靠函数调用，也就是说 push-based 的控制流由 DuckDB 手动控制，有很多好处

可以进行更多优化，因为了解每个算子的执行状态

vector cache，在不同的 operator 之间增加小的 cache，更加 cache friendly 去执行

scan sharing，每个算子可以将数据发送到多个算子中去，可以有多个 output

backpressure，因为了解了全局状态，可以设定一个 buffer size，在buffer 不够的时候暂停执行，有了足够空间再次执行

async IO，当算子执行 blocking IO 操作的时候暂停执行，等有了数据再继续执行

可以参照这篇文章了解 pipeline

pipeline 核心思路

https://zhuanlan.zhihu.com/p/402355976 从代码层面详细介绍 event 事件机制驱动的 pipeline 构建和执行过程

Pipeline represent a chain of physical operators that are executed in sequence that include

source eg. Scan 特殊 operator 类比水源

operator eg. Filter ...

sink eg. Agg GroupBY HashJoin 特殊 operator 类比水槽

To improve performance.The pipeline can be split into multiple sub-pipelines that are executed in parallel.

Define a physical operator whether sink operator ?

If any operator that need to digest the data of all child nodes before they can proceed to the next step that called Pipeline Breaker

所谓 pipeline breaker 就是在多个 pipeline 的执行的时候不能顺畅的执行下去，需要等这个同步的点执行完毕才能继续执行。

How to split into multiple sub-pipelines ?

Depends on whether physical operator is Pipeline breaker

If a physical operator is Pipeline breaker pull it out,

use it as new sub pipeline source

And use it as prev sub pipeline sink.

在 duckdb 中 Pipeline Breaker 就是 Sink 算子，它会安排在每个流水线的末尾，Sink 在消费完所有上游的数据后，往往也可以作为下游 Pipeline 的 Source 去产出数据。

For Example:

SELECT * FROM t1;

Pipeline: Table Scan --> Project.

SELECT * FROM t1 GROUP BY a LIMIT 10;

Pipeline1: ( Depends on Pipeline0 GROUP BY a) ............ Project ---> TOP10.

Pipeline2: Table Scan ---> Project ---> GROUP BY a.

SELECT * FROM t1 ORDER BY a LIMIT 10;

Pipeline1: ( Depends on Pipeline0 ORDER BY a) ............ Project ---> TOP10.

Pipeline2: Table Scan ---> Project ---> ORDER BY a.

SELECT t1.a, t2.a FROM t1 JOIN t2 ON t1.a == t2.a;

Pipeline1: Table Scan ---> HashJoin（sink）

Pipeline2: Table Scan ---> HashJoin （operater） -----> project

Pipeline3: HashJoin (source) -----> project

其中 Pipeline 2 依赖 pipeline 1，Pipeline 3 依赖 Pipeline 2

duckdb 中每个 Pipeline 均有一个 Source 和 Sink，加上中间的 N 多无状态算子组成，其中 Source 和中间的算子可以无脑并行。比如 Scan 本地文件的 Source，可以开 M 个线程，每个线程扫描一部分文件，每次得到一个 Chunk，就可以在当前线程下喂给下一个算子，算子处理后再交给下一个算子，直到 Sink 为止。

在 duckdb Pipeline 中的一条线内部的每个operater 是没有再做并行的

再准确点意思就是比如一个p1: scan -> Filter，不可以 scan 和 fliter 同时开始做。

构建 pipeline 的过程还是从 root 开始由上到下

DuckDB 的 Hash Join 采用了 partitioned hash join，当数据量比较大的时候可以通过 repartition 将数据落盘避免 OOM，这个多线程版本的 partitioned hash join，主要分为 3 个阶段：

并发读取和计算所有 build 端的数据，当所有数据都读完后检查总数据量是否能全部放在内存中，如果不能就将 build 端的数据 repartition，选出第一批能放在内存中的 partition 为它们构造 hash table，剩下的数据存放在磁盘上。

并发读取和计算所有 probe 端的数据，这时读上来的数据要么属于内存中的 partition，要么属于磁盘上的 partition，先把属于磁盘上的 partition 的数据落盘，用属于内存中的 partition 的数据去 probe 此时 build 端的放在内存中的 hash table，得到结果返回给上层。

并发处理磁盘上的数据：挑选一批 build 端能放入内存的 partition，构造 hash table，然后 probe 端去并发的 probe 得到结果进行下一步计算。循环这样的处理过程直到所有磁盘上的 partition 都 join 完成。

这 3 个过程也分别对应了 3 个基本的 Pipeline，可以表示成下图，其中 Pipeline 2 依赖 pipeline 1，Pipeline 3 依赖 Pipeline 2：

partitioned hash join 会分成 3 个阶段分别作为 sink、operator 和 source 角色

这是一个join 的物理计划树和 SELECT t1.a, t2.a FROM t1 JOIN t2 ON t1.a == t2.a; 对应

下面是构建 JoinPipelines 的过程

PipelineExecutor 和 Pipeline 内基于 Push 的执行模型

PipelineExecutor::Execute() 函数通过调用 Pipeline 中各个 PhysicalOperator 的相应接口，以 Push 的方式完成了当前 Pipeline 的执行，执行逻辑可以概括为：

先调用 FetchFromSource() 从 Pipeline 的 source PhysicalOperator 中获取计算结果作为 source DataChunk，这里会调用 source 的 GetData() 接口。

再调用 ExecutePushInternal() 依次执行 Pipeline 中 operators 列表中的各个 PhysicalOperator 和最后一个 sink PhysicalOperator 完成这批数据后续的所有计算操作。对于普通 operator 会调用它的 Execute() 接口，对最后的 sink 会调用它的 Sink() 接口。PipelineExecutor::ExecutePushInternal() 可以看做是 Pipeline 内的数据消费者。

最后调用 PushFinalize() 完成当前 ExecutorTask 的执行，这里会调用 sink 的 Combine 接口，用以完成一个 ExecutorTask 结束后的收尾清理工作。

PhysicalOperator 同时包含了 source、operator、sink 所需要的所有接口，各个 PhysicalOperator 需要实现对应的接口完成相应的计算逻辑。比如 partitioned hash join 因为会分成 3 个阶段分别作为 sink、operator 和 source 角色，它同时实现了所有的接口。

大致理解 duckdb 的思路，用 event 来区分 pipeline 状态是为了解决 operator sink 操作的并发同步。

有一个主的 pipeline 初始化之后，把所有可以并行的 pipeline 全部拉起来跑，跑完之后进入 finish 状态回到

主pipeline sink 出去

TPC-H

测试环境

cpu: amd5700h

mem:32GB

ssd: nevm 512GB

duckdb: 0.8.1

基本流程(可略)

Step 1: Generate test data with TPC-H

Manual Generation

First, you should use git to clone the tpch-dbgen repo:

This repo contains the program for generating TPC-H data.

Then, enter the tpch-dbgen directory and type make all, and it will generate some executable binaries such as dbgen and qgen. We will show you how to generate TPC-H data by using one line of command in the following sections. Meanwhile, you can read this README for more details.

Finally, type the following command and wait for several seconds:

This command will generate the data we want, which contains a table called LINEITEM with a size of 700MB.

Step 2: Create database and tables

Step3 copy from table

tpch-duckdb-bench 测试脚本程序

https://github.com/loloxwg/duckdb.git

tpch-duckdb-bench

测试工具

tpch-olap-engiue for duckdb

测试结果

论文结果

Quantifying TPC-H Choke Points and Their Optimizations

论文中测试对比 monetdb 以及 duckdb 对比图

对照测试组

parquet指直接操作 parquet 进行测试

native 指操作 db内部数据进行测试

10GB 数据集测试结果

20GB 数据集测试结果

50GB 数据集测试结果

100GB 数据集测试结果

单独测试 native 的情况，并且限制了内存大小20 GB，否则容易造成 oom

TPC-C

TPC-C是业界常用的一套Benchmark，由TPC委员会制定发布，用于评测数据库的联机交易处理（偏向OLTP能力）。主要涉及10张表，包含了NewOrder（新订单的生成）、Payment（订单付款）、OrderStatus（最近订单查询）、Delivery（配送）和StockLevel（库存缺货状态分析）等五类业务事务模型。TPC-C使用tpmC值（Transactions per Minute）来衡量系统最大有效吞吐量（MQTh，Max Qualified Throughput），其中Transactions以NewOrder Transaction为准，即最终衡量单位为每分钟处理的新订单数。

使用TPC-C工具测试PolarDB-X1.0数据库性能_云原生关系型数据库 PolarDB-阿里云帮助中心

本文介绍如何使用TPC-C工具测试PolarDB-X 1.0数据库的联机交易处理（偏向OLTP能力），您可以按照本文介绍自行测试对比，快速了解数据库系统的性能。

https://help.aliyun.com/document_detail/139634.html

测试环境

cpu: amd5700h && arm m1pro

mem:32GB && 16GB

ssd: nevm 512GB

duckdb: 0.8.1

TPC-C 数据配置

10 Warehouses数据集结果

Apple M1 Pro 16GB 内存

X86 R7 5700 32GB 内存

20 Warehouses 数据集结果

Apple M1 Pro 16GB 内存

X86 R7 5700 32GB 内存

100 Warehouses 数据集结果

X86 R7 5700 32GB 内存

MMP 默认不使用

duckdb8.2dev 中只有 extension jemalloc使用了 mmap

src 下没有 mmap 的使用

Unsupported .help options removal

Updated May 15, 2023

上面这条 issue 也证明了没有 mmap的使用，~~可能是早期有但是后边可能觉得 mmap 不适合数据库某些场景，然后移除了~~

但是保留了用户使用 mmap 的权利用插件的形式，只要引入 jemalloc 就可以使用 mmap 了

OOM when reading Parquet file

Updated Nov 11, 2022

DuckDB 是使用buffer manager 来管理缓存，采用了精巧的内存管理机制来避免 OOM

来自知乎

Buffer Manager

DuckDB 的 buffer manager 是 lock-free 的（类似Lean Store ），粒度是 256KB 的级别，实现了下面这些功能：

限制内存使用量

当计算需要的时候 pin blocks 在内存中

当不需要的时候 unpin blocks

是否支持 binlog

单文件存储拥有wal日志

DuckDB通过使用保存在磁盘上的预写日志（WAL）来支持数据持久性。WAL记录对数据库所做的所有更改，包括插入、更新和删除，并确保它们在发生崩溃或系统故障时是持久的。

MySQL binlog中记录数据库发生更改的各种事件（events），这些事件的种类非常多，完整的事件类型如下所示：

其中的一些我们熟悉的事件：

WRITE_ROWS_EVENT：插入记录。

UPDATE_ROWS_EVENT：更新记录。

DELETE_ROWS_EVENT：删除记录。

和 DuckDB 中 WAL Type 有 Overlap

嵌入应用

DuckDB 是一款嵌入式数据库，不需要启动数据库服务器，也不需要使用客户端连接服务器。不过，可以使用 C 或 C++ 绑定将数据库服务器直接嵌入应用程序。主构建程序将会创建共享链接库 build/release/src/libduckdb.[so|dylib|dll]，同时也会创建一个静态链接库。

SQLite is the world’s most widely deployed DBMS. Simplicity in installation, and embedded in-process operation are central to its success. DuckDB adopts these ideas of simplicity and embedded operation.

SQLite是世界上部署最广泛的DBMS。安装的简单性和嵌入式进程内操作是其成功的核心。DuckDB采用了这些简单性和嵌入式操作的思想。

DuckDB has no external dependencies, neither for compilation nor during run-time. For releases, the entire source tree of DuckDB is compiled into two files, a header and an implementation file, a so-called “amalgamation”. This greatly simplifies deployment and integration in other build processes.

DuckDB没有外部依赖项，无论是编译还是运行时。对于发布，DuckDB的整个源代码树被编译成两个文件，一个头文件和一个实现文件，即所谓的“合并”。这极大地简化了其他构建过程中的部署和集成。For building, all that is required to build DuckDB is a working C++11 compiler.对于构建，构建DuckDB所需的只是一个工作C++11编译器。

For DuckDB, there is no DBMS server software to install, update and maintain. DuckDB does not run as a separate process, but completely embedded within a host process. For the analytical use cases that DuckDB targets, this has the additional advantage of high-speed data transfer to and from the database. In some cases, DuckDB can process foreign data without copying. For example, the DuckDB Python package can run queries directly on Pandas data without ever importing or copying any data.

对于DuckDB，没有需要安装、更新和维护的DBMS服务器软件。DuckDB不作为单独的进程运行，而是完全嵌入在主机进程中。对于DuckDB所针对的分析用例，这具有高速数据搬迁到数据库和从数据库搬迁的额外优势。在某些情况下，DuckDB可以处理外部数据而无需复制。例如，DuckDB Python包可以直接对Pandas数据运行查询，而无需导入或复制任何数据。