DuckDB中自适应基数树的持久化存储

原文：https://duckdb.org/2022/07/27/art-storage.html

tl;dr: DuckDB使用自适应基数树（ART）索引来强制执行约束条件并加速查询过滤。到目前为止，索引未持久化存储，导致索引信息丢失、重载具有数据约束的表的时间较长等问题。我们现在将ART索引持久化存储到磁盘上，大大缩短了数据库加载时间（高达数量级），并且不再丢失现有索引的跟踪。本博文深入探讨了ART存储的实现、基准测试和未来工作。

DuckDB使用ART索引来维护主键（PK）、外键（FK）和唯一约束。 它们还加速了点查询、范围查询（具有高选择性）和连接操作。在最新版本之前（或V0.4.1），DuckDB没有将ART索引持久化存储到磁盘上。 在存储数据库文件时，只会存储有关现有PK和FK的信息，所有其他索引都是临时的，重启数据库时丢失。 对于PK和FK，它们在重载数据库时会被完全重建，从而导致加载时间较长的不便。

关于ART索引已经发表了大量研究工作，尤其是关于同步、 缓存效率和 评估方面。 然而，迄今为止，还没有公开的关于序列化和缓冲区管理ART树的信息。

本博文将描述DuckDB如何存储和加载ART索引。特别是解释索引是如何懒加载的（只有在必要时才将ART节点加载到内存中）。 在ART索引部分，我们将介绍什么是ART索引，它是如何工作的，并提供一些示例。 在DuckDB中的ART部分，我们将解释为什么决定在DuckDB中使用ART索引，以及在哪些地方使用它，讨论不持久化ART索引存在的问题。 在ART存储部分，我们将解释如何在DuckDB中对ART索引进行序列化和缓冲区管理。 在基准测试部分，我们将比较DuckDB v0.4.0（ART存储之前的版本）与DuckDB的最新版本。我们将展示在这两个版本中PK和FK的加载成本之间的差异，以及懒加载ART索引和访问完全加载的ART索引之间的差异。 最后，我们将讨论当前实现的缺点以及未来ART索引改进计划。

ART索引

自适应基数树本质上是一种垂直和水平压缩的紧凑型Trie。

Trie

Trie是一种树状数据结构，其中每个树层级包含关于数据集的一部分信息。它们通常以字符串为例进行说明。 Trie的主要优势在于其具有O(k)的查找时间复杂度，这意味着在最坏情况下，查找操作的成本将等于字符串的长度k。

实际上，Trie也可以用于存储数值数据类型。但是，如果像字符串一样逐个字符地存储它们，将会浪费空间。 例如，考虑类型uint64_t，占据了64位（8字节）的空间。uint64_t的最大值是18,446,744,073,709,551,615。 因此，如果我们像上面的示例一样表示它，我们需要17个Trie层级。 在实际中，Trie根据位扇出（bit fan-out）创建，扇出指定了每个Trie层级表示多少位。 一个带有8位扇出的uint64_t Trie最多有8层，每层表示一个字节。

在下面的示例中，我们有一个Trie，用于索引7、10和12。每个节点由0和1两个位组成，和一个指针（*表示非空，Ø表示空）。 与之前的字符串Trie类似，Trie的每个层级都表示两个位，指针指向子节点。最后，叶子节点指向实际的数据。

很快可以注意到，这种Trie表示在两个方面都是浪费的。首先，许多节点只有一个子节点（即一个路径）， 这可以通过垂直压缩（基数树）来合并。其次，许多节点具有空指针，占用了空间但没有包含任何信息， 这可以通过水平压缩来解决。

垂直压缩（RT）

垂直压缩的基本思想是合并具有只有一个子节点的路径。 为了支持这一点，节点存储一个前缀，包含压缩到该节点的路径。 下图可以看到前两个节点只有一个子节点。这些节点可以折叠到第三个节点（即第一个分叉的节点）作为前缀路径。 在查找时，关键字必须匹配前缀路径中包含的所有值。

下图中，可以看到经过垂直压缩后的Trie。这种Trie变体通常被称为基数树（Radix Tree）。 虽然通过这种Trie变体已经节省了很多浪费的空间，但仍然有许多具有空指针的节点。

水平压缩（ART）

为了充分理解ART索引背后的设计决策，我们首先需要将2位扇出扩展到8位，这是DBMS中常见的扇出值。

上图是在一个具有8位扇出的Trie节点。 实际上，这些节点将存储（2^8）256个指针，其中键是指针在数组中的位置。 在这个示例所描述的情况下，一个节点的大小为（256个指针 * 8字节）2048字节，但实际上只利用了24字节（3个指针 * 8字节）。 为了避免这种情况，ART根据当前节点的填充程度使用4种不同的节点类型。

在图形表示中，我呈现了节点的概念性可视化以及键为0、4和255的示例。 以下是每种节点类型的描述：

Node-4：最多可以容纳4个不同的键。键存储在一个1-字节数组中，每个键对应一个指针。 其总大小为36字节（4个键 * 1字节 + 4个指针 * 8字节） 。 指针数组与键数组对齐。

Node-16：最多可容纳16个不同的键。与Node-4类似，每个键存储在一个1-字节数组中，每个键对应一个指针。 其总大小为144字节（16个键 * 1字节 + 16个指针 * 8字节）。与Node-4一样，指针数组与键数组对齐。

Node-48：最多可以容纳48个不同的键。 当一个键存在于这个节点中时，表示该键的1-字节数组位置将保存一个指向该键子节点的指针数组中的索引。 其总大小为640字节（256个键 * 1字节 + 48个指针 * 8字节）。 请注意，指针数组和键数组不再对齐。键数组存储指针数组的索引。

Node-256：最多可以容纳256个不同的键。 它只有一个指针数组，如果指针被设置，则表示该键存在，并且它指向其子节点。 其总大小为2048字节（256个指针 * 8字节）。

对于上一节中的示例，我们可以使用Node-4而不是Node-256来存储键，因为我们只有3个键。

DuckDB中的ART

在考虑在DuckDB中实现哪种索引结构时，我们希望找到一种既可以用于保持PK/FK/唯一约束， 又可以加速范围查询和连接的结构。DBMS通常实现哈希表用于约束检查，以及B+树用于范围查询。 然而，在ART索引中，我们看到了一种机会，可以通过使用一种数据结构来减少代码复杂性，同时满足两种用例的需求。 ART索引提供的主要特性，我们正在利用的包括：

1. 紧凑的结构：由于ART的内部节点相对较小，它们可以放入CPU缓存，因此比B+树更注重缓存。
2. 快速的点查询：ART点查询的最坏情况时间复杂度是O(k)，对于约束检查来说足够快。
3. 插入不会引起显著的性能降低：许多哈希表变种在达到一定大小时必须重建。 在实际情况下，一个插入操作可能导致性能显著下降，查询突然花费更多的时间来完成，对于用户来说看不出明显的原因。 在ART中，插入操作可能会导致节点的增长（例如，Node-4可能会增长到Node-16），但这些操作是廉价的。
4. 能够处理范围查询：虽然ART不像B+树那样快速执行范围查询，因为它必须执行树遍历，而B+树可以顺序扫描叶节点， 但它仍然比哈希表具有优势，因为这些类型的查询可以执行（有人可能会争辩说可以使用哈希表进行范围查询，但不如ART高效）。 这使我们可以高效地使用ART进行高选择性的范围查询和索引连接。
5. 可维护性：使用一种结构同时进行约束检查和范围查询，而不是两种结构，更具代码效率和可维护性。

用来干什么

如前所述，ART索引在DuckDB中主要用于三个方面。

数据约束。主键、外键和唯一约束都由ART索引维护。 当在带有约束的元组中插入数据时，将有效地尝试在ART索引中执行插入，如果元组已经存在则会失败。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

CREATE TABLE integers(i INTEGER PRIMARY KEY)
-- Insert unique values into ART
INSERT INTO integers VALUES (3), (2)
-- Insert conflicting value in ART will fail
INSERT INTO integers VALUES (3)

CREATE TABLE fk_integers(j INTEGER, FOREIGN KEY (j) REFERENCES integers(i))
-- This insert works normally
INSERT INTO fk_integers VALUES (2), (3)
-- This fails after checking the ART in integers
INSERT INTO fk_integers VALUES (4)

范围查询。对索引列的高选择性（应该是指范围较小）范围查询也将使用ART索引。

1
2
3
4
5

CREATE TABLE integers(i INTEGER PRIMARY KEY)
-- Insert unique values into ART
INSERT INTO integers VALUES (3), (2), (1), (8) , (10)
-- Range queries (if highly selective) will also use the ART index
SELECT * FROM integers where i >=8

连接。具有少量匹配项的Join也将利用现有的ART索引。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

-- Optionally you can always force index joins with the following pragma
PRAGMA force_index_join;

CREATE TABLE t1(i INTEGER PRIMARY KEY)
CREATE TABLE t2(i INTEGER PRIMARY KEY)
-- Insert unique values into ART
INSERT INTO t1 VALUES (3), (2), (1), (8) , (10)
INSERT INTO t2 VALUES (3), (2), (1), (8) , (10)
-- Joins will also use the ART index
SELECT * FROM t1 INNER JOIN t2 on (t1.i = t2.i)

表达式索引。ART索引也可用于快速查找表达式。

1
2
3
4
5
6
7
8
9

CREATE TABLE integers(i INTEGER, j INTEGER)

INSERT INTO integers VALUES (1,1), (2,2), (3,3)

-- Creates index over i+j expression
CREATE INDEX i_index ON integers USING ART((i+j))

-- Uses ART index point query
SELECT i FROM integers  where i+j = 2

ART存储

存储ART索引时存在两个主要约束：

1）必须以允许懒加载的方式存储索引。否则，我们将不得不完全加载索引， 包括可能对在该会话中执行的查询不必要的节点； 2）不能增加节点大小。否则，我们将减少ART索引的缓存感知效率。

后序遍历

为了允许懒加载，我们必须存储节点的所有子节点，收集每个子节点的存储位置信息， 然后，在存储实际节点时，我们存储每个子节点的磁盘信息。要执行这种类型的操作，需要进行后序遍历。

后序遍历如下图所示。红色的圆圈表示存储节点的数字顺序。

下图显示了DuckDB块格式下的实际表示。在DuckDB中，数据存储在256KB的连续块中。每个块由一个id表示。

在本例中，Block0 存储了一些元数据。在偏移量100,000和100,200之间，存储了ART索引的元数据(例如，名称，约束，表达式)及其根节点的<Block,Offset>。

例如，假设我们正在查找在存储序号为1的Leaf[1]中的键。我们将首先在<Block:2, Offset:220>加载ART根节点， 通过检查存储在该节点中的键，我们将看到我们必须在<Block:2, Offset:140>加载Node-16， 然后最后在<Block:2, Offset:0>加载Leaf[1]。这意味着对于这个查找，只有这3个节点被加载到内存中。 后续对这些节点的访问只需要内存访问，而对其他节点的访问(例如，Leaf[2])仍需磁盘访问。

实现这个(反)序列化过程的一个主要问题是，现在我们不仅需要保存指针的内存地址信息， 还需要知道它们是否已经在内存中，以及如果没有的话，它们存储在哪个<Block,Offset>。

如果我们将Block Id和Offset存储在新的变量中， 将会大幅增加ART节点的大小，降低其作为缓存感知数据结构的有效性。

以Node-256为例。保存256个指针的成本为2048字节（256个指针 * 8字节）。 假设我们决定将块信息存储在一个新数组中，如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct BlockPointer { 
	uint32_t block_id;
	uint32_t offset;
}

class Node256 : public Node  {
	// Pointers to the child nodes
	Node* children[256];
	BlockPointer block_info[256];
}

Node-256将增加2048字节(256 * (4+4))，使其当前大小增加一倍，达到4096字节。

Pointer Swizzling

为了避免增加ART节点的大小，我们决定实现Swizzlable Pointers并使用它们来替代常规指针。

这个想法是，我们不需要全部64位的指针来指向一个内存地址。（48位可以提供256TB的地址空间，支持任何当前的架构，更多信息请参见这里 和这里） 因此，我们可以使用最高有效位作为标志（即Swizzle标志）。 如果Swizzle标志被设置，那么Swizzlable Pointer中的值是节点的内存地址。 否则，该变量存储了节点存储位置的块信息。我们使用接下来的31位来存储Block ID，剩下的32位来存储Offset。

在下图中，您可以看到DuckDB的Swizzlable Pointer的可视化表示。

基准测试

为了评估当前存储实现的优点和缺点，我们运行了一个基准测试(可在此Colab获得)， 其中我们创建了一个包含50,000,000个整型元素的表，这些元素之上有一个主键约束。

1
2
3

con = duckdb.connect("vault.db") 
con.execute("CREATE TABLE integers (x integer primary key)")
con.execute("INSERT INTO integers SELECT * FROM range(50000000);")

我们在两个不同版本的DuckDB上运行这个基准测试，其中一个版本不存储索引(v0.4.0)，即索引始终在内存中， 并在数据库重新启动时重新构建；另一个版本存储索引，使用前面描述的懒加载技术。

存储时间

首先测量序列化索引的额外成本。

我们可以看到，存储索引的成本是不存储索引的2倍。原因是我们的表只有一列包含50,000,000个int32_t值。 但是，在存储ART时，我们还为叶子中各自的row_id存储了50,000,000个int64_t值。这是额外存储成本的主要原因。

加载时间

然后测量重新启动数据库所需的加载时间。

在这里，我们可以看到加载数据库的时间有两个数量级的差异。这种差异基本上是由于加载过程中ART索引的完全重建。 相反，在存索引版本中，此时只加载有关ART索引的元数据信息。

查询时间（冷）

我们现在测量在索引上运行点查询的冷查询时间(即，数据库刚刚重新启动，这意味着在存储版本中，索引还不存在于内存中)。 在均匀分布的10000个元素上，我们运行5000次点查询。我们使用这个值总是强制点查询加载大量未使用的节点。

一般来说，在持久化存储版本中，每个查询的开销要高出3倍。这主要有两个原因:

1. 创建节点。在存储版本中，我们确实懒创建节点，这意味着必须为每个节点分配所有参数，并加载键和前缀等值。
2. Block Pinning。对每个节点，我们必须pin/unpin存储它们的块。

查询时间（热）

两个版本中的时间是可比较的，因为存储版本中的所有节点都已经在内存中。 总之，当存储索引处于活跃使用状态时，它们的性能与完全在内存中的索引相似。

后续工作

ART索引存储是DuckDB中一个长期存在的问题，许多用户声称这是一个缺失的功能，这对他们使用DuckDB造成了障碍。 虽然现在实现了存储和懒加载ART索引，但是仍然有许多改进方案来提高ART索引的性能。

1. 缓存Pinned Blocks。在我们当前的实现中，尽管块可以存储多个节点，并且很可能通过查找连续重用，但块会不断地pin/unpin。巧妙地缓存它们将大大节省触发节点加载的查询的时间。
2. 批量加载。我们的ART索引目前不支持批量加载。这意味着当在列上创建索引时，节点将不断调整大小，因为元素将一个接一个地插入。如果我们批量加载数据，我们可以确切地知道我们必须为该数据集创建哪些节点，从而避免频繁地调整大小。
3. 批量插入。在执行批量插入时，会发生与批量加载类似的问题。一个可能的解决方案是创建一个带有批量加载的新ART索引，然后将其与现有的ART索引合并。
4. Vectorized查找/插入。DuckDB使用了一个vectorized的执行引擎。然而，我们的ART查找和插入仍然遵循tuple-at-a-time模型。
5. 可更新的索引存储。在我们当前的实现中，ART索引正磁盘中完全失效后重新存储。这将导致在后续存储中不必要地增加存储时间。直接将节点更新到磁盘而不是完全重写索引可以大大降低未来的存储成本。换句话说，索引始终在每个checkpoint完全存储。