友好列表与 Lambda 让 DuckDB 处理数据更轻松高效

title: Friendly Lists and Their Buddies, the Lambdas

author: Tania Bogatsch & Maia de Graaf

简介

在数据分析领域，嵌套的数据类型（如列表和结构体）非常常见。许多常用的数据格式（如 Parquet 和 JSON）都支持嵌套类型。

过去，我们在处理嵌套类型时，通常需要先对数据进行规范化，然后在分析结束后重新聚合数据。这种操作方式不仅麻烦，还会影响性能。为了简化这一过程，DuckDB 等分析系统提供了对嵌套类型的原生支持，避免了中间的复杂操作。

本文将首先介绍列表和 lambda 函数的基础知识。接着，我们会深入探讨它们的技术细节。最后，我们会展示一些来自社区的实际应用。
如果你对列表和 lambda 已经比较熟悉，可以直接跳到最后的社区示例部分！

列表

在谈到 lambda 之前，先让我们了解一下 DuckDB 中的 LIST 类型^[1]。

列表是一种包含相同类型元素的集合。下表展示了一个包含两列的表格，l 列是整数列表，n 列是整数。

CREATE OR REPLACE TABLE my_lists (l INTEGER[], n INTEGER);  
INSERT INTO my_lists VALUES ([1], 1), ([1, 2, 3], 2), ([-1, NULL, 2], 2);  
FROM my_lists;

┌───────────────┬───────┐  
│       l       │   n   │  
│    int32[]    │ int32 │  
├───────────────┼───────┤  
│ [1]           │     1 │  
│ [1, 2, 3]     │     2 │  
│ [-1, NULL, 2] │     2 │  
└───────────────┴───────┘

DuckDB 的执行引擎通过 Vectors 传递所有数据。
如果你对 Vectors 和向量化执行感兴趣，可以参考官方文档^[2]，以及相关的研究论文（1^[3] 和 2^[4]）。
在这个例子中，l 和 n 分别生成了两个向量，内部结构与 Arrow^[5] 的物理列表表示形式相似。

仔细观察你会发现，l 列的嵌套子向量和 n 列的向量非常相似。这种嵌套的向量结构，使得 DuckDB 的执行引擎能够在嵌套类型上重用现有组件。后面我们会进一步讨论这种设计的意义。

Lambdas

Lambda 函数 是一种匿名函数，意思是它没有名称。在 DuckDB 中，lambda 函数的语法是 (param1, param2, ...) -> expression。
参数名可以随意命名，expression 可以是任意的 SQL 表达式。

目前，DuckDB 提供了三种与 lambda 相关的标量函数：
list_transform^[6]、
list_filter^[7] 和
list_reduce^[8]，
它们都有相应的别名。这些函数的第一个参数都是 LIST，第二个参数是 lambda 函数。

我们之前在 SQL 体操：让 SQL 变得更灵活的文章中已经提到了 lambda，这次我们将详细展示它的功能。

深入探讨：列表转换

现在回到我们之前的例子，假设我们想将 n 加到列表 l 的每个元素上。

纯关系型方法

如果只使用传统的关系型操作符，即不使用原生的列表函数，我们需要执行以下步骤：

1. 将列表展开，同时保持每行数据的关联。我们可以通过生成一个临时的唯一标识符（例如 rowid^[9] 或 UUID^[10]）来实现。
2. 对每个元素加上 n。
3. 使用临时标识符 rowid，通过将转换后的元素重新聚合成列表。

SQL 代码如下：

WITH flattened_tbl AS (  
    SELECT unnest(l) AS elements, n, rowid  
    FROM my_lists  
)  
SELECT array_agg(elements + n) AS result  
FROM flattened_tbl  
GROUP BY rowid  
ORDER BY rowid;

┌──────────────┐  
│    result    │  
│   int32[]    │  
├──────────────┤  
│ [2]          │  
│ [3, 4, 5]    │  
│ [1, NULL, 4] │  
└──────────────┘

这个例子虽然不算复杂，但如果进行更复杂的转换，SQL 查询会变得冗长且难以维护。
更重要的是，这种方式增加了 unnest 操作和带有 GROUP BY 的聚合函数 array_agg，对于大数据集来说会造成很大开销。

为了进一步理解为什么这种方法性能较差，我们需要深入技术细节。
在执行时，查询会按下图所示的步骤进行。我们可以直接从子向量发出 unnest 操作，而无需复制数据。
对于相关列 rowid 和 n，我们使用选择向量^[11]，避免了数据的重复拷贝。
接着，我们将表达式执行在子向量和扩展的向量 n 上。

最耗时的操作是最后一步：将转换后的元素重新聚合成它们原来的列表。因为我们不传递父向量，无法知道转换后的元素与原列表之间的关联关系。重建这些列表需要进行大量数据的复制和分区，即使使用 DuckDB 的高性能聚合操作符，也会带来性能影响。

因此，这种规范化的方法不仅书写复杂，而且会因为不必要的开销降低查询性能。这再次证明了强行将嵌套数据转换成关系型结构可能带来的性能损耗。

原生列表函数

通过支持原生的列表函数，DuckDB 避免了这些性能问题，直接对 LIST 数据结构进行操作。如前所述，列表实际上是嵌套的列，因此我们可以将这些函数转化为执行引擎已经熟悉的概念，最大限度地利用其性能优势。

对于转换操作，相关的列表函数是 list_transform。以下是重写后的查询：

SELECT list_transform(l, x -> x + n) AS result  
FROM my_lists;

或者，使用 Python 风格的列表推导语法：

SELECT [x + n FOR x IN l] AS result  
FROM my_lists;

在内部，这个查询会扩展所有相关的向量（在本例中是 n）。我们仍然使用选择向量来避免数据复制。接着，lambda 函数 x -> x + n 作用于子向量和扩展向量 n 上。
由于这是一个原生的列表函数，我们可以保留父向量，从而省略重新聚合步骤。

为了更好地理解 list_transform 的性能，我们进行了一个基准测试。首先，我们向 my_lists 表添加了 100 万行，每行包含五个元素。

INSERT INTO my_lists  
    SELECT [r, r % 10, r + 5, r + 11, r % 2], r   
    FROM range(1_000_000) AS tbl(r);

接着，我们对这些数据分别运行了规范化查询和原生查询。两者都在 MacBook Pro 2021（M1 Max 芯片）上，使用 DuckDB v1.0.0 通过 CLI 运行。

规范化查询	原生查询
0.522 s	0.027 s

可以看到，原生查询的速度提升了 10 倍以上。非常惊人！如果我们使用 EXPLAIN ANALYZE 查看执行计划（这篇博文未展示），可以看到 DuckDB 的大部分时间消耗在 HASH_GROUP_BY 和 UNNEST 操作符上。而在原生查询计划中，这些操作符已经不复存在。

社区中的列表和 lambdas

为了更好地展示结合 LIST 类型和 lambda 函数的强大功能，我们在社区 Discord、GitHub 等平台上寻找了一些有趣的用例。

`list_transform`

如前所述，list_transform^[12] 可以对输入列表的每个元素应用一个 lambda 函数，并返回一个包含转换后元素的新列表。
在这里，一位用户^[13] 通过嵌套不同的原生列表函数，创建了一个 list_shuffle 函数。

CREATE OR REPLACE MACRO list_shuffle(l) AS (  
    list_select(l, list_grade_up([random() FOR _ IN l]))  
);

另一位用户^[14] 研究了如何使用 DuckDB 查询远程 Parquet 文件。
在他们的查询中，首先使用 list_transform 生成一系列 Parquet 文件的 URL 列表，然后调用 read_parquet 函数读取文件并计算数据总量。查询如下：

SELECT  
   sum(size) AS size  
FROM read_parquet(  
    ['https://huggingface.co/datasets/vivym/midjourney-messages/resolve/main/data/' ||  
        format('{:06d}', n) || '.parquet'  
        FOR n IN generate_series(0, 55)  
    ]  
);

`list_filter`

list_filter^[15] 函数可以过滤输入列表中的元素，只保留 lambda 函数返回 true 的元素。以下示例来自 Discord 的讨论^[16]，用户希望从每个列表中删除索引为 idx 的元素。

CREATE OR REPLACE MACRO remove_idx(l, idx) AS (  
    list_filter(l, (_, i) -> i != idx)  
);

到目前为止，我们主要展示了支持 lambda 函数的相关功能。然而，SQL 的功能强大且灵活，通常可以通过多种方式实现同样的功能。我们展示了如何使用其他原生列表函数来实现同样的目标。在这个例子中，我们使用 list_slice^[17] 和 list_concat^[18] 完成了同样的操作。

CREATE OR REPLACE MACRO remove_idx(l, idx) AS (  
    l[:idx - 1] || l[idx + 1:]  
);

`list_reduce`

我们最近添加了 list_reduce^[19] 函数，它会将 lambda 函数应用到累加器值上。
累加器值是上一次 lambda 执行的结果，最终也是函数返回的值。

以下示例来自 GitHub 讨论^[20]，用户希望通过 lambda 函数验证 BSN 号码^[21]，这是荷兰的社保号码。BSN 必须为 8 位或 9 位数字，但为了简化问题，我们只关注 9 位数字的情况。通过将每位数字按从 9 到 2 依次相乘，最后一位数字乘以 -1，最终和必须能够被 11 整除才能认为是有效的 BSN。

设置

在我们的示例中，我们假设输入的 BSN 是 INTEGER[] 类型。

CREATE OR REPLACE TABLE bsn_tbl AS  
FROM VALUES   
    ([2, 4, 6, 7, 4, 7, 5, 9, 6]),   
    ([1, 2, 3, 4, 5, 6, 7, 8, 9]),   
    ([7, 6, 7, 4, 4, 5, 2, 1, 1]),   
    ([8, 7, 9, 0, 2, 3, 4, 1, 7]),   
    ([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])  
    tbl(bsn);

解决方案

当这个问题首次提出时，DuckDB 还没有 list_reduce 支持。用户提出了如下方案：

CREATE OR REPLACE MACRO valid_bsn(bsn) AS (  
    list_sum(  
        [array_extract(bsn, x)::INTEGER * (IF (x = 9, -1, 10 - x))   
        FOR x IN range(1, 10, 1)]  
    ) % 11 = 0  
);

现在我们可以使用 list_reduce 重写查询。我们还添加了一个检查，确保 BSN 长度为 9 位。

CREATE OR REPLACE MACRO valid_bsn(bsn) AS (  
    list_reduce(list_reverse(bsn),   
        (x, y, i) -> IF (i = 1, -x, x) + y * (i + 1)) % 11 = 0  
    AND len(bsn) = 9  
);

执行我们的宏并查询 bsn_tbl 表，结果如下：

SELECT bsn, valid_bsn(bsn) AS valid  
FROM bsn_tbl;

┌────────────────────────────────┬─────────┐  
│              bsn               │  valid  │  
│            int32[]             │ boolean │  
├────────────────────────────────┼─────────┤  
│ [2, 4, 6, 7, 4, 7, 5, 9, 6]    │ true    │  
│ [1, 2, 3, 4, 5, 6, 7, 8, 9]    │ false   │  
│ [7, 6, 7, 4, 4, 5, 2, 1, 1]    │ true    │  
│ [8, 7, 9, 0, 2, 3, 4, 1, 7]    │ true    │  
│ [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] │ false   │  
└────────────────────────────────┴─────────┘

结论

对于数据分析系统来说，支持原生嵌套类型至关重要。

DuckDB 提供了对嵌套类型的原生支持以及多种函数，方便我们直接操作这些类型。这些函数不仅简化了操作，还极大提升了性能。

在本文中，我们通过分析 list_transform 函数，深入探讨了嵌套类型的技术细节。

此外，我们还展示了社区中一些实际的使用场景。

引用链接

[1] LIST 类型: https://duckdb.org/docs/sql/data_types/list.md
[2] 官方文档: https://duckdb.org/docs/internals/vector.md
[3] 1: https://15721.courses.cs.cmu.edu/spring2016/papers/p5-sompolski.pdf
[4] 2: https://drive.google.com/file/d/1LJeys01Ho9DREfRJhb9wHu3ssSC22Lll/view
[5] Arrow: https://arrow.apache.org
[6] list_transform: https://duckdb.org/docs/sql/functions/lambda.md#list_transformlist-lambda
[7] list_filter: https://duckdb.org/docs/sql/functions/lambda.md#list_filterlist-lambda
[8] list_reduce: https://duckdb.org/docs/sql/functions/lambda.md#list_reducelist-lambda
[9] rowid: https://duckdb.org/docs/sql/statements/select.md#row-ids
[10] UUID: https://duckdb.org/docs/sql/data_types/numeric.md#universally-unique-identifiers-uuids
[11] 选择向量: https://duckdb.org/docs/internals/vector.html
[12] list_transform: https://duckdb.org/docs/sql/functions/lambda.md#list_transformlist-lambda
[13] 用户: https://discord.com/channels/909674491309850675/1032659480539824208/1248004651983573162
[14] 用户: https://til.simonwillison.net/duckdb/remote-parquet
[15] list_filter: https://duckdb.org/docs/sql/functions/lambda.md#list_filterlist-lambda
[16] Discord 的讨论: https://discord.com/channels/909674491309850675/921073327009853451/1235818484047544371
[17] list_slice: https://duckdb.org/docs/sql/functions/list.md#list_slicelist-begin-end
[18] list_concat: https://duckdb.org/docs/sql/functions/list.md#list_concatlist1-list2
[19] list_reduce: https://duckdb.org/docs/sql/functions/lambda.md#list_reducelist-lambda
[20] GitHub 讨论: https://github.com/duckdb/duckdb/discussions/9752
[21] BSN 号码: https://www.netherlandsworldwide.nl/bsn