没有内存？没问题。 DuckDB 有外部聚合 

原文 No Memory? No Problem. External Aggregation in DuckDB^[1]

作者: Laurens Kuiper

2024-03-29

TL;DR:：自 0.9.0 版本发布以来，DuckDB 的全并行聚合哈希表可以有效地聚合比内存中容纳的更多组。换句话说，DuckDB 现在可以处理比以前版本更大的数据集，并对其进行高效的聚合操作，即使数据集的大小超过了可用内存。这是因为 DuckDB 的聚合哈希表现在可以并行处理数据，并将中间结果存储在磁盘上，而不是内存中。

大多数分组聚合查询只产生少量输出行。例如，“过去十年中，每个欧洲首都起飞了多少航班？”，即使包含所有航班信息的表有数百万行，每个欧洲首都也只会产生一行。但情况并非总是如此，例如“过去十年中，每个客户下了多少订单？”，每个客户会产生一行，这可能是数百万行，这会显著增加查询的内存消耗。然而，即使聚合无法在内存中完成，DuckDB 仍然可以完成查询。这是因为 DuckDB 能够将中间结果溢出到磁盘上，而不是将所有数据都保存在内存中。这使得 DuckDB 能够处理比其他内存数据库更大的数据集。

如果对实现不感兴趣？可以直接跳到实验部分！

Introduction 引言

大约两年前，我们发表了关于 DuckDB 哈希聚合的第一篇博客文章，标题为“DuckDB 中的并行分组聚合”^[2]。那么，我们为什么现在要写另一篇博客文章呢？

与大多数作为服务器的数据库系统不同，DuckDB 可以在各种环境中使用，这些环境可能没有太多内存。然而，某些数据库查询，例如具有许多唯一组的分组，需要大量内存。比如我正在写这篇文章的这台笔记本电脑有 16 GB 的 RAM，但一个查询需要 20 GB 怎么办？如发生这种情况：

Out of Memory Error: could not allocate block of size X (Y/Z used)

查询已被取消。遗憾的是，我们无法下载更多的 RAM^[3]。但幸运的是，这台笔记本电脑还配备了一个快速 SSD，存储空间为 1TB。在许多情况下，我们不需要同时将所有 20GB 的数据都放在内存中，我们可以暂时将一些数据存储在SSD上。需要时再将其加载回来，我们仍然可以完成查询。我们必须谨慎使用存储空间，因为尽管现代 SSD 速度很快，和内存比仍然慢得多。

简而言之，这就是本文的主题。自 0.9.0 版本发布以来，DuckDB 的哈希聚合可以通过将数据卸载到磁盘存储来处理比内存中更多的唯一组。在本文中，我们将解释这是如何工作的。如果您想知道什么是哈希聚合，哈希冲突是如何解决的，或者 DuckDB 的哈希表是如何结构的，请查看我们关于哈希聚合的第一篇博客文章。

Memory Management 内存管理

大多数数据库系统将持久数据存储在“页”上。根据请求，这些页可以从存储中的数据库文件读取，放入内存，并在必要时再次写回。通常的做法是使所有页大小相同：这允许页被交换，并避免内存和存储中的碎片化^[4]。当数据库启动时，会分配一部分内存并为这些页保留，称为“缓冲池”。负责管理缓冲池的数据库组件被恰当地称为“缓冲区管理器”。

剩余的内存用于短期（即临时）内存分配，例如用于聚合的哈希表。这些分配以不同的方式进行，这是好事，因为如果存在许多唯一的组，哈希表可能需要非常大，因此无论如何我们都无法将固定大小的页面用于此目的。如果临时数据超过内存容量，聚合等运算符必须决定何时将数据选择性地写入存储中的临时文件。

... 至少，这是传统做事的方式。这对 DuckDB 来说意义不大。为什么我们要以不同的方式管理持久数据和临时数据？区别在于持久数据应该被持久化，而临时数据则不应该。为什么缓冲区管理器不能同时管理两者呢？

DuckDB 的缓冲区管理器并不传统。大多数持久数据和临时数据都存储在固定大小的页面上，并由缓冲区管理器管理。缓冲区管理器会尝试充分利用您的内存。这意味着我们不会为缓冲池预留一部分内存。这允许 DuckDB 将所有内存用于持久数据，而不仅仅是一部分，如果这对您的工作负载来说是最好的。如果您正在进行需要大量内存的大型聚合，DuckDB 可以将持久数据从内存中逐出，以便为大型哈希表释放空间。

由于 DuckDB 的缓冲区管理器管理着所有内存，包括持久数据和临时数据，因此它在选择何时将临时数据写入存储方面比聚合等运算符要好得多。将卸载的责任留给缓冲区管理器也使我们免于在每个需要处理不适合内存的数据的运算符中实现读取和写入临时文件的工作。

为什么其他数据库系统中的缓冲区管理器不管理临时数据？有两个问题：内存碎片和无效引用。

Memory Fragmentation 内存碎片化

哈希表和查询运算符中使用的其他数据结构并不像用于持久数据的页面那样具有固定大小。我们也不希望在内存中存在大量大小可变的页面与固定大小的页面一起浮动，因为这会导致内存碎片化。

理想情况下，我们会将固定大小用于所有内存分配，但这不是一个好主意：有时，处理查询最有效的方法需要分配一个大数组，例如。因此，我们决定将固定大小用于几乎所有分配。这些短期分配在使用后立即释放，不像用于持久数据的固定大小页面那样被保留。这些分配不会相互造成碎片化，因为 DuckDB 在可能的情况下使用 jemalloc^[5] 来分配内存，它使用大小类对分配进行分类，并为它们维护单独的区域。

Invalid References 无效引用

临时数据通常不能直接写入存储，因为它们往往包含指针。例如，DuckDB 实现了 Umbra^[6] 提出的字符串类型，该类型具有固定宽度。超过 12 个字符的字符串不会存储在字符串类型中，而是存储在其他地方，并存储一个指向这个“其他地方”的指针。

这在我们想要将数据卸载到存储时会引发问题。假设这个“其他地方”是缓冲区管理器可以在任何时候卸载到存储以释放一些内存的页之一，其中存储了超过 12 个字符的字符串。如果页被卸载然后重新加载，它很可能被加载到内存中的不同地址。指向长字符串的指针现在无效了，因为它们仍然指向之前的地址！

通常，包含指向存储指针的数据是通过先对其进行序列化来写入的。当将其读回内存时，必须再次对其进行反序列化。 （序列化/反序列化）操作可能成本很高^[7]，因此存在像 Arrow Flight^[8] 这样的数据格式，它们试图最小化成本。但是，我们不能在这里使用 Arrow，因为 Arrow 是按列主序布局的，但对于哈希表来说，按行主序布局更有效率^[9]。

我们可以创建一个行主序版本的 Arrow Flight，但我们完全可以避免（解）序列化：我们已经创建了一个专用的行主序页面布局，它实际上使用旧的无效指针在将数据读回内存后重新计算新的有效指针。

页面布局将固定大小的行和可变大小的数据（如字符串）放在不同的页面上。对于一个查询，行的长度是固定的：在发出 SQL 查询后，DuckDB 会创建并执行查询计划。因此，甚至在执行该计划之前，我们已经知道需要哪些列、它们的类型以及这些类型有多宽。

如图所示，需要少量的“元数据”来重新计算指针。固定大小的行存储在“行页”中，可变大小的行存储在“Var 页”中。

请记住，固定大小的行中有指针指向可变大小的数据。元数据描述了哪些固定大小的行指向哪个 Var 页以及 Var 页的最后一个已知地址。例如，元数据 1 描述了存储在 Row 页 1 偏移量 0 处的 5 行，其可变大小的数据存储在 Var 页 1 中，该页的地址为 0x42

假设缓冲区管理器决定卸载 Var 页 1。当我们再次请求 Var 页 1 时，它被加载到地址 0x500
 。这 5 行中的指针现在无效。例如，其中一行包含指针 0x48
 ，这意味着它存储在 Var 页 1 的偏移量 0x48 - 0x42 = 6
 处。我们可以通过将偏移量添加到页面的新地址来重新计算指针： 0x500 + 6 = 0x506
 。对于其字符串存储在同一行和 Var 页上的行，我们执行指针重新计算，因此每当 Row 页或 Var 页满时，我们都会创建一个新的元数据。

指针重计算相对于（解）序列化的优势在于它可以被延迟执行。我们可以通过比较元数据中的指针和当前指向该页面的指针来检查 Var Page 是否被卸载。如果指针相同，我们就不需要重新计算指针。

External Aggregation 外部聚合

既然我们已经弄清楚了如何处理临时数据，现在终于可以谈谈哈希聚合了。第一个大挑战是在并行执行聚合。

DuckDB 使用Morsel 驱动的并行化^[10] 来并行执行查询，这意味着聚合等查询操作符必须对并行性有所了解。这与计划驱动的并行化^[11]不同，后者使操作符对并行性一无所知。

简要总结我们关于聚合的第一篇博客文章：在 DuckDB 中，所有活动线程都有自己的线程局部哈希表，它们将输入数据填充到其中。这将使线程保持忙碌，直到所有输入数据都被读取。多个线程的哈希表中很可能有相同的组。因此，必须将线程局部哈希表组合起来以完成分组聚合。可以通过对哈希表进行分区并将每个线程分配给组合每个分区中的数据来并行完成此操作。在很大程度上，我们仍然使用相同的方法。您将在下面的图片中看到这一点，该图片展示了我们新的实现方式。

我们将第一阶段称为线程局部预聚合。输入数据是大约 100,000 行的数据块。这些数据被分配给活动线程，线程将它们放入线程本地的哈希表中，直到所有输入数据都被读取。我们使用线性探测来解决冲突，并使用salt来减少处理这些冲突的开销。这在我们的第一篇关于聚合的博客文章中有解释，所以在这里我就不再重复了。

现在我们已经解释了哪些内容没有改变，我们可以讨论哪些内容已经改变。与上次相比，第一个不同之处在于我们分区的方式。以前，如果我们有 32 个线程，每个线程会创建 32 个哈希表，每个分区一个。这总共是 1024 个哈希表，当有更多线程活动时，这种方式并不好扩展。现在，每个线程有一个哈希表，但哈希表中的数据是分区的。数据也存储在我们之前介绍的专用页面布局中，以便可以轻松地卸载到存储中。

第二个不同之处在于，在 Thread-Local Pre-Aggregation 过程中哈希表不会被调整大小。我们保持哈希表的大小较小，以减少在这个阶段发生的缓存未命中次数。这意味着哈希表在某个时刻会填满。当它填满时，我们会重置它并重新开始。我们可以这样做，因为我们将在第二阶段晚些时候完成聚合。当我们重置哈希表时，我们“取消固定”存储实际数据的页面，这告诉我们的缓冲区管理器，当它需要释放内存时，可以将它们写入存储。

这两项更改共同导致在第一阶段对内存的需求较低。每个线程只需要在内存中保留一个小型的哈希表。我们可以通过多次填充哈希表来收集大量数据，但缓冲区管理器几乎可以在需要时卸载所有这些数据。

第二阶段是分区聚合，线程本地分区数据被交换，每个线程将一个分区的数据合并到一个哈希表中。这个阶段与之前基本相同，只是我们现在有时创建的分区数量比线程多得多。为什么呢？一个分区的哈希表可能适合内存，但是 8 个线程可能同时合并一个分区，我们可能无法在内存中容纳 8 个分区。解决这个问题的简单方法就是过度分区。如果我们创建的分区数量多于线程，例如 32 个分区，那么分区的大小就会变小，8 个线程将只同时合并 32 个分区中的 8 个，这不会需要那么多内存。

Experiments 实验

聚合结果只有少数几个唯一组别时，很容易就能在内存中处理。为了评估我们的外部哈希聚合实现，我们需要有很多唯一组别的聚合。为此，我们将使用 H2O.ai 数据库操作基准测试，我们已将其恢复并继续维护。具体来说，我们将使用 G1_1e9_2e0_0_0.csv.zst
 文件，该文件未压缩时为 50GB。H2O.ai 基准测试的源代码可以在这里找到。您可以自己从 https://blobs.duckdb.org/data/G1_1e9_2e0_0_0.csv.zst下载该文件（压缩后为 18.8GB）。

仅产生少量唯一组的聚合可以轻松放入内存。为了评估我们的外部哈希聚合实现，我们需要具有许多唯一组的聚合。为此，我们将使用 H2O.ai 数据库式操作基准测试^[12]，该基准测试 我们已恢复^[13] 并 现在维护^[14]。具体来说，我们将使用 G1_1e9_2e0_0_0.csv.zst
 文件，解压缩后大小为 50 GB。H2O.ai 基准测试的源代码可以在这里找到 这里^[15]。您可以从 https://blobs.duckdb.org/data/G1_1e9_2e0_0_0.csv.zst（压缩后 18.8 GB）自行下载该文件。

我们使用基准中的以下查询来加载数据：

SET preserve_insertion_order = false;
CREATE TABLE y (
    id1 VARCHAR, id2 VARCHAR, id3 VARCHAR,
    id4 INT, id5 INT, id6 INT, v1 INT, v2 INT,
    v3 FLOAT);
COPY y FROM 'G1_1e9_2e0_0_0.csv.zst' (FORMAT CSV, AUTO_DETECT true);
CREATE TYPE id1ENUM AS ENUM (SELECT id1 FROM y);
CREATE TYPE id2ENUM AS ENUM (SELECT id2 FROM y);
CREATE TABLE x (
    id1 id1ENUM, id2 id2ENUM, id3 VARCHAR,
    id4 INT, id5 INT, id6 INT, v1 INT, v2 INT,
    v3 FLOAT);
INSERT INTO x (SELECT * FROM y);
DROP TABLE IF EXISTS y;

H2O.ai 聚合基准测试包含 10 个查询，这些查询在唯一分组数量上有所不同。

-- Query 1: ~100 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id1, sum(v1) AS v1
FROM x
GROUP BY id1;

-- Query 2: ~10,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id1, id2, sum(v1) AS v1
FROM x
GROUP BY id1, id2;

-- Query 3: ~10,000,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id3, sum(v1) AS v1, avg(v3) AS v3
FROM x
GROUP BY id3;

-- Query 4: ~100 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id4, avg(v1) AS v1, avg(v2) AS v2, avg(v3) AS v3
FROM x
GROUP BY id4;

-- Query 5: ~1,000,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id6, sum(v1) AS v1, sum(v2) AS v2, sum(v3) AS v3
FROM x
GROUP BY id6;

-- Query 6: ~10,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT
    id4,
    id5,
    quantile_cont(v3, 0.5) AS median_v3,
    stddev(v3) AS sd_v3
FROM x
GROUP BY id4, id5;

-- Query 7: ~10,000,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id3, max(v1)-min(v2) AS range_v1_v2
FROM x
GROUP BY id3;

-- Query 8: ~10,000,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id6, v3 AS largest2_v3
FROM (
    SELECT id6, v3, row_number() OVER (
          PARTITION BY id6
          ORDER BY v3 DESC) AS order_v3
    FROM x
    WHERE v3 IS NOT NULL) sub_query
WHERE order_v3 <= 2;

-- Query 9: ~10,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id2, id4, pow(corr(v1, v2), 2) AS r2
FROM x
GROUP BY id2, id4;

-- Query 10: ~1,000,000,000 unique groups
CREATE OR REPLACE TABLE ans AS
SELECT id1, id2, id3, id4, id5, id6, sum(v3) AS v3, count(*) AS count
FROM x
GROUP BY id1, id2, id3, id4, id5, id6;

基准页面的结果^[16] 是在 c6id.metal
 AWS EC2 实例上获得的。在这个实例上，所有查询都能轻松地放入内存，而且使用多个线程也不会影响性能。DuckDB 仅用 8.58 秒就能完成最大的查询，即查询 10，它返回 10 亿个唯一组。然而，许多人不会使用这样强大的机器来处理数字。在我的笔记本电脑上，一台 2020 年的 MacBook Pro，一些较小的查询可以放入内存，比如查询 1，但查询 10 肯定不行。

以下表格是所用硬件的概述。

尽管 AWS EC2 实例的 CPU 核心与我的笔记本电脑的 CPU 核心无法直接比较，但该实例显然拥有更多的计算能力和内存。尽管硬件差异很大，DuckDB 仍然可以无问题地完成所有 10 个查询。

查询的运行时间以秒为单位报告，是通过在我的笔记本电脑上使用 DuckDB 0.10.1 运行 3 次并取中位数获得的。c6id.metal
 实例的结果来自 基准测试网站^[17]。尽管无法将所有唯一组放入我的笔记本电脑内存中，但 DuckDB 可以计算所有唯一组并返回它们。最大的查询（查询 10）需要将近 4.5 分钟才能完成。这比强大的 c6id.metal
 实例要长 30 倍以上。当然，这种巨大的差异可以用硬件的巨大差异来解释。有趣的是，这仍然比 c6id.metal
 实例上的 Spark 快，后者需要 603.05 秒！

Conclusion 结论

DuckDB 一直在改进其大于内存的查询处理能力。在这篇博文中，我们展示了 DuckDB 用于溢出和加载存储数据的某些技巧。这些技巧在 DuckDB 的 0.9.0 版本中发布的基于外部哈希的聚合中实现。我们在 H2O.ai 基准测试中对哈希聚合进行了测试，DuckDB 能够在只有 16GB 内存的笔记本电脑上完成所有 50GB 的查询。

想了解更多吗？请阅读我们关于外部聚合的论文^[18]。

引用链接

[1]
 No Memory? No Problem. External Aggregation in DuckDB: https://duckdb.org/2024/03/29/external-aggregation
[2]
 “DuckDB 中的并行分组聚合”: https://duckdb.org/2022/03/07/aggregate-hashtable
[3]
 下载更多的 RAM: https://knowyourmeme.com/memes/download-more-ram
[4]
 https://en.wikipedia.org/wiki/Fragmentation_(computing): https://en.wikipedia.org/wiki/Fragmentation_%28computing%29
[5]
 jemalloc: https://jemalloc.net/
[6]
 Umbra: https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf
[7]
 （序列化/反序列化）操作可能成本很高: https://www.vldb.org/pvldb/vol10/p1022-muehleisen.pdf
[8]
 Arrow Flight: https://arrow.apache.org/blog/2019/10/13/introducing-arrow-flight/
[9]
 按行主序布局更有效率: https://ir.cwi.nl/pub/13807/13807B.pdf
[10]
 Morsel 驱动的并行化: https://db.in.tum.de/~leis/papers/morsels.pdf
[11]
 计划驱动的并行化: https://dl.acm.org/doi/pdf/10.1145/93605.98720
[12]
 H2O.ai 数据库式操作基准测试: https://duckdblabs.github.io/db-benchmark/
[13]
 我们已恢复: https://duckdb.org/2023/04/14/h2oai
[14]
 现在维护: https://duckdb.org/2023/11/03/db-benchmark-update
[15]
 这里: https://github.com/duckdblabs/db-benchmark
[16]
 基准页面的结果: https://duckdblabs.github.io/db-benchmark/
[17]
 基准测试网站: https://duckdblabs.github.io/db-benchmark/
[18]
 外部聚合的论文: https://hannes.muehleisen.org/publications/icde2024-out-of-core-kuiper-boncz-muehleisen.pdf