用维度表加速 DuckDB 字符串聚合

分析型工作负载中充满了重复的字符串：产品名称、国家名称、车站名称、用户代理、类别标签。以 DuckDB 的公开列车服务数据集为例，该数据集为荷兰铁路列车停靠的每一站都记录一行。数据来自 Rijden de Treinen （列车在运行吗？） 应用发布的开放数据集。你可以直接通过其 URL 查询：

SELECTdeparture_time,station_name,typeFROM'https://blobs.duckdb.org/train_services.parquet'LIMIT5;

该表有 380,959 行，但只有 537 个不同的车站名称，因此每个名称都会在数千行中被重复存储：Amsterdam Centraal（18 字节）仅它自己就出现在其中 7,591 行中。将其加载到一张表中以便跟着操作，可在 Web shell 或 DuckDB CLI 中进行：

CREATETABLEtrain_servicesASFROM'https://blobs.duckdb.org/train_services.parquet';

当你对车站名称进行 GROUP BY 时，DuckDB 必须处理每一行的完整字符串。例如，以下查询统计每个车站有多少列车停靠：

SELECTstation_name,count(*)AScallsFROMtrain_servicesGROUPBYstation_name;

考虑一下仅停靠两个车站的少数几行会发生什么：

字符串处理对每一行都会重复，尽管这里只有两个不同的车站，而整张表也只有 537 个。

本文展示了如何改为在小整数上完成这些工作：为每个不同的字符串分配一个数字，只在最后再查回字符串。

背景

该方法来自数据仓库中的 星型模式，在这里用于提升查询性能。它是在我们查看一份用户报告时想到的，该报告涉及 高基数分组中的内存占用过高。

那份报告最终并不涉及字符串，但 Richard Wesley 指出，在他自己的工作中，构建维度表并在最后把字符串连接回来，对字符串密集的聚合有很大影响。

我们此后已将这一模式加入 性能指南的模式部分。

为什么按字符串分组代价高昂

DuckDB 通过哈希聚合来计算 GROUP BY，每个分组保留一个哈希表条目，如 DuckDB 中的并行分组聚合 博客文章（2022 年）所述。聚合使用每个分组键的哈希来找到该键在哈希表中的槽位，然后将该键与该槽位中存储的键进行比较。对于整数，这只需要几条 CPU 指令。对于字符串，成本会随字符串长度增长。

在 DuckDB 中，字符串值是一个 16 字节结构。不超过 12 字节的字符串内联存储。更长的字符串存储一个 4 字节前缀以及指向实际字符的指针。这种设计让短字符串保持低开销，但许多现实世界中的标签都长于 12 字节。

对于这些较长的字符串，哈希会读取每一行中每个字符串的每一个字节。仅凭前缀无法确认匹配，因此 DuckDB 会沿着指针去比较完整字符串。当新分组出现时，其字符串会被复制到哈希表自己的内存中，这使得哈希表比使用定宽键时更大。

复制字符串也会影响内存使用。更宽的哈希表更难放入 CPU 缓存，而在超出内存的聚合中，它会更早达到内存限制，并不得不将更多数据溢写到磁盘。DuckDB 确实会在磁盘上对字符串列应用字典编码，如 DuckDB 中的轻量级压缩 博客文章（2022 年）所述，但那是一种存储优化：一旦列被读入聚合，每个分组键又重新成为完整字符串。

整数键避免了这些成本，因为其固定宽度使哈希和比较都很廉价。当键范围很小时，DuckDB 可以完全避免哈希：如果统计信息显示键能放入足够小的域中，优化器会选择 完美哈希聚合，由 perfect_ht_threshold 设置控制，它直接使用键值作为数组索引。

构建带排序窄键的维度表

这些示例基于上面加载的 train_services 表。每一行记录一次停靠：service_id、date、服务 type、train_number、station_code 和 station_name，以及 departure_time 和 arrival_time。我们想要编码的重复字符串是 station_name。

第 1 步：度量基数

首先，查明该列有多少个不同的值，因为这个数量决定了键可以有多窄。

SELECTcount(DISTINCTstation_name)ASnum_stationsFROMtrain_services;

这返回 537，而这个数量决定了键需要有多宽。你要选择范围仍能覆盖每个不同值的最窄整数类型，因为更窄的键意味着事实表中每行占用的字节更少，并且你用于分组的哈希表条目也更小。

键来自 row_number()，它从 1 开始且只会向上计数，因此无符号类型是合适的选择，不会把任何范围浪费在负值上。UTINYINT（1 字节）最多容纳 255 个不同值，USMALLINT（2 字节）最多容纳 65,535 个，而 UINTEGER（4 字节）最多可容纳约 43 亿个。

537 个车站名称无法放入 UTINYINT，因此 USMALLINT 是可行的最窄类型，也是下一步要转换成的类型。如果不同值的数量还会增长，请选择更大的类型，以免键用尽。

第 2 步：构建维度表

接下来，为每个不同的字符串分配一个整数键。重要的细节是窗口内的 ORDER BY station_name：键按字符串顺序分配。

CREATEORREPLACETABLEstationsASSELECTstation_name,(row_number()OVER(ORDERBYstation_name))::USMALLINTASstation_idFROM(SELECTDISTINCTstation_nameFROMtrain_servicesWHEREstation_nameISNOTNULL);

排序后的键有两个优点。首先，ORDER BY station_id 产生的顺序与 ORDER BY station_name 相同，因此你可以按这个廉价的整数排序。其次，键的分配是确定性的：从相同数据重建该表会产生相同的键。

第 3 步：将键存储在事实表中

最后，用它的键替换事实表中的字符串列，这是一次性重写表的代价。维度表省略了 NULL，因此 LEFT JOIN 会保留没有车站的行，并给它们一个 NULL 键。

CREATEORREPLACETABLEtrain_services_encodedASSELECTts.*EXCLUDE(station_name),s.station_idFROMtrain_servicestsLEFTJOINstationssUSING(station_name);

这个 stations 维度表保存每个名称一次，按字母顺序编号：

事实表现在存储 2 字节的 USMALLINT 键，因此对其进行分组开销很低：

这些键遵循字符串顺序：Amsterdam Centraal 排在 Rotterdam Centraal 之前，因此它获得较小的键（28 对 403）。在如此小且密集的键范围下，DuckDB 可以使用完美哈希聚合，直接按键索引，而不是进行哈希。

你也可以省略这一步，在每个查询中即时连接维度表。这仍然能保持聚合的哈希表较窄，但每个查询随后都要在连接中为字符串哈希付出一次代价。将键存储在事实表中则使查询不再需要进行字符串处理。

查询编码后的表

有了键之后，查询在整数上进行聚合，只有当结果很小时才查找字符串。LEFT JOIN 会保留没有车站的那组行。

WITHrollupAS(SELECTstation_id,date,count(*)AScallsFROMtrain_services_encodedGROUPBYALL)SELECTs.station_name,rollup.*EXCLUDE(station_id)FROMrollupLEFTJOINstationssUSING(station_id)ORDERBYstation_id,date;

GROUP BY ALL 按每个未被聚合的选定列分组，这里是 station_id 和 date，因此你不必重复该列表。最后的连接针对聚合结果运行，该结果每个分组一行，而不是每个事件一行。如果聚合将十亿行减少到几十万行，连接只需查找几十万个字符串。由于键已排序，ORDER BY station_id 也会按车站名称的字母顺序排序。

对于 top-N 查询，在连接之前应用 LIMIT，这样只查找十个字符串：

WITHtop_stationsAS(SELECTstation_id,count(*)AScallsFROMtrain_services_encodedGROUPBYstation_idORDERBYcallsDESCLIMIT10)SELECTs.station_name,top_stations.callsFROMtop_stationsLEFTJOINstationssUSING(station_id)ORDERBYcallsDESC;

要按字符串过滤，在维度表中查找它的键，并按整数过滤事实表。

SELECTcount(*)FROMtrain_services_encodedWHEREstation_idIN(SELECTstation_idFROMstationsWHEREstation_nameLIKE'%Centraal%');

衡量效果

你能获得多少收益取决于你的数据，主要取决于字符串有多长以及有多少个不同值。在这个 380,000 行的样本上差异很小，并且随着行数和字符串长度的增加而增大。要针对你自己的数据找出答案，请用两种方式运行相同的聚合并进行比较：

.timeron-- Group on the stringSELECTstation_name,count(*)AScallsFROMtrain_servicesGROUPBYstation_name;-- Group on the key, then join the strings backWITHrollupAS(SELECTstation_id,count(*)AScallsFROMtrain_services_encodedGROUPBYstation_id)SELECTs.station_name,rollup.callsFROMrollupLEFTJOINstationssUSING(station_id);

要了解时间花在哪里，请在每个查询前加上 EXPLAIN ANALYZE，并比较聚合运算符的耗时。要比较内存使用，请用 memory_limit 设置一个较低的 SET，并检查哪个查询先开始溢出到磁盘。

变体

到目前为止，示例使用的是具有固定值集合的单个字符串列。下面的变体涵盖手动维度表的内置替代方案、编码多个字符串列，以及在新数据到达时保持键最新。

与 ENUM 的比较

DuckDB 的 ENUM 类型是内建于类型系统中的字典编码：值存储为小整数，DuckDB 为你选择整数宽度。Lord of the Enums 博客文章（2021 年）对此进行了基准测试，其中对 GROUP BY 一个 ENUM 列运行比在原始字符串上进行相同分组更快。你可以从查询创建它：

CREATETYPEstation_enumASENUM(SELECTDISTINCTstation_nameFROMtrain_servicesWHEREstation_nameISNOTNULLORDERBYstation_name);

如果值集合是预先已知且很少变化，ENUM 能给你带来大部分好处，且无需额外连接。维度表在以下情况下是更好的选择：

• 新值不断到来。 ENUM 的值在创建类型时是固定的，因此插入未知值会失败。维度表可以增长。
• 你需要属性。 维度表可以携带额外的列，例如车站所在的城市或它所在的线路，你可以对其分组或过滤，而无需解析字符串。
• 数据离开 DuckDB。整数键和查找表可以导出为 Parquet 或 CSV，并在其他工具中使用。

多个字符串列

该模式按列应用：为每个高重复的字符串列构建一个维度表。在此数据集中，station_name 和服务 type 都符合条件。然后每个键获得自己的整数类型，大小按其列的基数确定，查询只连接回它需要的维度。type 列只有 15 个不同值，因此它的键适合 UTINYINT，而 station_name 仍然需要 USMALLINT：

CREATEORREPLACETABLEservice_typesASSELECTtype,(row_number()OVER(ORDERBYtype))::UTINYINTAStype_idFROM(SELECTDISTINCTtypeFROMtrain_servicesWHEREtypeISNOTNULL);CREATEORREPLACETABLEtrain_services_encodedASSELECTts.*EXCLUDE(station_name,type),s.station_id,t.type_idFROMtrain_servicestsLEFTJOINstationssUSING(station_name)LEFTJOINservice_typestUSING(type);

事实表现在携带两个键，查询只连接回它读取的维度。按车站统计通话次数需要 stations，而按服务类型细分则需要 service_types。

如果两列总是同时出现，例如 station_code 和 station_name，那么以组合为键的单个维度表通常更简单。然后事实表存储一个键而不是两个，这使它更加狭窄。

保持维度表最新

当新数据到达时，添加未见过的字符串，其键延续当前最大值：

INSERTINTOstationsSELECTn.station_name,((SELECTmax(station_id)FROMstations)+row_number()OVER(ORDERBYn.station_name))::USMALLINTASstation_idFROM(SELECTDISTINCTstation_nameFROMnew_train_servicesWHEREstation_nameISNOTNULL)nANTIJOINstationsUSING(station_name);

这个 ANTI JOIN 只保留尚未存在于 stations 中的名称，因此现有键保持不变，每个真正的新名称获得一个延续当前最大值的键。

然后像第 3 步那样编码新行并追加它们：

INSERTINTOtrain_services_encodedSELECTn.*EXCLUDE(station_name),s.station_idFROMnew_train_servicesnLEFTJOINstationssUSING(station_name);

追加的键不再遵循字母顺序。如果你的查询依赖 ORDER BY station_id 与 ORDER BY station_name 匹配，请定期重建维度表并重新为事实表设置键，或者在最终连接后按字符串排序。

窄键不会减少分组数量

字典编码使每个分组更小。它不会减少有多少个分组，而这对于极高基数的聚合很重要。

促成这篇文章的报告 duckdb/duckdb#14584 展示了这一点。它将 92 亿行分组为 3.2 亿个不同分组，并使用了远超预期的内存。分组键已经是 UBIGINT，因此没有字符串需要编码。

原因在于 DuckDB 如何并行化聚合。每个线程先在自己的线程本地哈希表中聚合其负责的那部分行，最后再将部分结果合并。当每个线程看到同一分组的大量重复时，这种方法效果很好，而这在真实世界数据中很常见。

在报告中，使用 8 个线程时，每个线程看到约 11 亿行：仅约为不同值数量的 3 倍，且没有任何有用的分布模式。几乎每个分组都出现在几乎每个线程的表中，因此内存使用量接近线程数乘以分组数。

窄键使每个条目更小，但无法防止这种重复。当分组数接近每个线程处理的行数时，减少线程更有帮助，因为每个线程都持有每个分组的自己的副本。

SETthreads=1;

这会以速度换取内存，因此应将其保留给那些否则会耗尽内存或将大量数据溢出到磁盘的聚合。按分组键聚簇的数据也有帮助，因为这样每个线程看到的是一组更小、更不同的分组。

当该模式没有帮助时

该模式使模式和查询更复杂，因此并不总是值得。

在以下情况下不要使用它：

• 字符串很短。 最多 12 字节的值已经内联存储，因此与整数键的差距要小得多。
• 该列几乎唯一。 如果大多数值都是不同的，例如 ID 或自由文本，则维度表的行数几乎与事实表一样多，节省的很少。
• 你只查询一次数据。 构建维度表并重写事实表需要对数据完整扫描一遍。只有在你重复查询数据时，才值得付出这个代价。
• 你不基于该列进行聚合。 如果你只是对该字符串进行过滤或显示，收益是有限的。

在这些情况下，保持字符串列不变。如果你不确定，请按照 衡量效果 中所述比较两个版本。

结论

对重复字符串进行分组代价高昂。通过将它们移入一个带有已排序、窄整数键的小维度表，DuckDB 可以基于固定宽度整数进行聚合，并保持其哈希表紧凑。字符串会通过一次最终连接与已经很小的结果重新关联。

当你反复对具有少量不同值的长字符串进行聚合时，这种方法最有帮助。你可以在 性能指南 中找到本技巧的浓缩版本。