使用维度表加速字符串聚合DuckDB 团队2026-10-02 | 16 分钟摘要当查询按冗长、重复的字符串进行分组时将这些字符串移入一个带有已排序、窄整数键的小型维度表中。在键上进行聚合最后再将字符串连接回来。查询的工作方式与之前相同只不过操作的是小型定宽整数而非变长文本。分析型工作负载中充满了重复的字符串产品名称、国家名称、车站名称、用户代理、类别标签。以 DuckDB 的公开列车服务数据集为例该数据集为荷兰铁路列车停靠的每一站都记录了一行。数据来自 Rijden de Treinen“列车在运行吗”应用程序发布的开放数据集⁠。你可以直接从其 URL 查询SELECTdeparture_time,station_name,typeFROMhttps://blobs.duckdb.org/train_services.parquetLIMIT5;departure_timestation_nametype2023-05-15 00:00:00Rotterdam CentraalIntercity2023-05-15 00:13:00DelftIntercity2023-05-15 00:29:00Den Haag HSIntercity2023-05-15 00:45:00Leiden CentraalIntercity2023-05-15 01:03:00Schiphol AirportIntercity该表有 380,959 行但只有 537 个不同的车站名称因此每个名称都在数千行中重复存储仅 Amsterdam Centraal18 字节就出现在其中的 7,591 行里。将其加载到表中以便跟随操作可在 Web Shell 或 DuckDB CLI 中执行CREATETABLEtrain_servicesASFROMhttps://blobs.duckdb.org/train_services.parquet;当你按车站名称进行GROUP BY时DuckDB 必须为每一行处理完整的字符串。例如以下查询统计每个车站有多少趟列车停靠SELECTstation_name,count(*)AScallsFROMtrain_servicesGROUPBYstation_name;考虑一下对于仅停靠两个车站的几行数据会发生什么行station_name按 station_name 分组时的工作1Amsterdam Centraal对 18 字节进行哈希新分组因此将 18 字节复制到哈希表中2Rotterdam Centraal对 18 字节进行哈希新分组因此将 18 字节复制到哈希表中3Amsterdam Centraal对 18 字节进行哈希已存在分组因此比较 18 字节4Amsterdam Centraal对 18 字节进行哈希已存在分组因此比较 18 字节5Rotterdam Centraal对 18 字节进行哈希已存在分组因此比较 18 字节即使这里只有两个不同的车站整张表也只有 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、日期、服务类型、train_number、station_code和station_name以及departure_time和arrival_time。我们想要编码的重复字符串是station_name。第 1 步测量基数首先找出该列有多少个不同的值因为这个数量决定了键可以有多窄。SELECTcount(DISTINCTstation_name)ASnum_stationsFROMtrain_services;这返回 537这个数量决定了键需要多宽。你需要最窄的整数类型其范围仍能覆盖所有不同的值因为更窄的键意味着事实表中每行占用的字节更少你要分组用的哈希表条目也更小。键来自row_number()它从 1 开始且只向上计数因此无符号类型是合适的选择不会将任何范围浪费在负值上。UTINYINT1 字节最多容纳 255 个不同值USMALLINT2 字节最多 65,535 个UINTEGER4 字节最多约 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_services tsLEFTJOINstations sUSING(station_name);stations维度表按字母顺序为每个名称存储一次station_idstation_name1s-Hertogenbosch2s-Hertogenbosch Oost3t Harde4Aachen Hbf事实表现在存储 2 字节的USMALLINT键因此按它分组很廉价行station_id按 station_id 分组时的工作128对 2 字节进行哈希新分组因此存储 2 字节2403对 2 字节进行哈希新分组因此存储 2 字节328对 2 字节进行哈希已存在分组因此比较 2 字节428对 2 字节进行哈希已存在分组因此比较 2 字节5403对 2 字节进行哈希已存在分组因此比较 2 字节键遵循字符串顺序Amsterdam Centraal 排在 Rotterdam Centraal 之前因此获得较小的键28 对 403。键范围如此小且密集DuckDB 可以使用完美哈希聚合直接按键索引而不是进行哈希。你也可以省略这一步在每个查询中即时连接维度表。这仍然使聚合的哈希表保持窄小但每个查询随后都要在连接中为字符串哈希付出一次代价。将键存储在事实表中则从查询中移除了字符串处理。查询编码后的表键就位后查询在整数上聚合仅在结果变小时才查找字符串。LEFT JOIN保留没有车站的分组。WITH rollupAS(SELECTstation_id,date,count(*)AScallsFROMtrain_services_encodedGROUPBYALL)SELECTs.station_name,rollup.*EXCLUDE(station_id)FROMrollupLEFTJOINstations sUSING(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_stationsLEFTJOINstations sUSING(station_id)ORDERBYcallsDESC;station_namecallsUtrecht Centraal7663Amsterdam Centraal7591Zwolle5013Schiphol Airport4961Amsterdam Sloterdijk4854……若要按字符串过滤请在维度表中查找其键然后按整数过滤事实表。SELECTcount(*)FROMtrain_services_encodedWHEREstation_idIN(SELECTstation_idFROMstationsWHEREstation_nameLIKE%Centraal%);衡量效果你能获得多少收益取决于数据主要取决于字符串有多长以及有多少个不同值。在这个 380,000 行的样本上差异很小但随着行数和字符串长度的增加差异会增大。要了解你自己的数据请用两种方式运行相同的聚合并比较.timeron-- 按字符串分组SELECTstation_name,count(*)AScallsFROMtrain_servicesGROUPBYstation_name;-- 按键分组然后将字符串连接回来WITH rollupAS(SELECTstation_id,count(*)AScallsFROMtrain_services_encodedGROUPBYstation_id)SELECTs.station_name,rollup.callsFROMrollupLEFTJOINstations sUSING(station_id);要查看时间花在哪里请在每个查询前加上EXPLAIN ANALYZE并比较聚合算子的耗时。要比较内存使用请用SET设置较低的内存限制并检查哪个查询先开始溢出到磁盘。变体到目前为止示例使用的是具有固定值集合的单个字符串列。以下变体涵盖了手动维度表的内置替代方案、编码多个字符串列以及在新数据到达时保持键最新。与 ENUM 的比较DuckDB 的ENUM类型是内置于类型系统中的字典编码值存储为小整数DuckDB 为你选择整数宽度。《枚举之王》博客文章2021 年对此进行了基准测试对ENUM列进行GROUP BY比对原始字符串进行相同分组更快。你可以从查询创建CREATETYPEstation_enumASENUM(SELECTDISTINCTstation_nameFROMtrain_servicesWHEREstation_nameISNOTNULLORDERBYstation_name);如果值集合是预先已知且很少变化ENUM可以让你获得大部分好处而无需额外的连接。在以下情况下维度表是更好的选择新值不断到达。ENUM的值在类型创建时固定因此插入未知值会失败。维度表可以增长。你需要属性。维度表可以携带额外列例如车站所在城市或所在线路你可以按这些列分组或过滤而无需解析字符串。数据离开 DuckDB。整数键和查找表可以导出为 Parquet 或 CSV并在其他工具中使用。多个字符串列该模式按列应用为每个高重复率的字符串列构建一个维度表。在此数据集中station_name和服务类型都符合条件。每个键随后获得自己的整数类型按其列的基数确定大小查询只连接回它需要的维度。type列只有 15 个不同值因此其键适合UTINYINT而station_name仍需要USMALLINTCREATEORREPLACETABLEservice_typesASSELECTtype,(row_number()OVER(ORDERBYtype))::UTINYINTAStype_idFROM(SELECTDISTINCTtypeFROMtrain_servicesWHEREtypeISNOTNULL);CREATEORREPLACETABLEtrain_services_encodedASSELECTts.*EXCLUDE(station_name,type),s.station_id,t.type_idFROMtrain_services tsLEFTJOINstations sUSING(station_name)LEFTJOINservice_types tUSING(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)n ANTIJOINstationsUSING(station_name);ANTI JOIN仅保留尚未在stations中的名称因此现有键保持不变每个真正的新名称获得一个延续当前最大值之后的键。然后像第 3 步一样编码新行并追加INSERTINTOtrain_services_encodedSELECTn.*EXCLUDE(station_name),s.station_idFROMnew_train_services nLEFTJOINstations sUSING(station_name);追加的键不再遵循字母顺序。如果你的查询依赖ORDER BY station_id匹配ORDER BY station_name请定期重建维度表并重新为事实表分配键或在最终连接后按字符串排序。窄键不会减少分组数量字典编码使每个分组更小。它不会减少有多少个分组这在非常高基数的聚合中很重要。促使本文撰写的报告 duckdb/duckdb#14584⁠ 展示了这一点。它将 92 亿行分组为 3.2 亿个不同的组使用的内存远超预期。分组键已经是UBIGINT因此没有字符串需要编码。原因在于 DuckDB 并行化聚合的方式。每个线程首先在自己的线程本地哈希表中聚合其份额的行部分结果在最后合并。当每个线程看到同一分组的许多重复时这效果很好这对真实世界数据是典型的。在报告中使用 8 个线程时每个线程看到约 11 亿行仅为不同值数量的约 3 倍且分布没有任何有用模式。几乎每个分组最终都出现在几乎每个线程的表中因此内存使用接近线程数乘以分组数。窄键使每个条目更小但无法防止这种重复。当分组数量接近每个线程处理的行数时减少线程数帮助更大因为每个线程都持有每个分组的自己的副本。SETthreads1;这以速度换取内存因此请保留给否则会耗尽内存或将大量数据溢出到磁盘的聚合。按分组键聚类的数据也有帮助因为每个线程随后看到更小、更不同的分组集合。该模式何时没有帮助该模式使模式和查询更复杂因此并不总是值得。在以下情况下不要使用它字符串很短。最多 12 字节的值已经内联存储因此与整数键的差距要小得多。该列几乎唯一。如果大多数值都不同例如 ID 或自由文本维度表的行数几乎与事实表一样多节省很少。你只查询一次数据。构建维度表和重写事实表需要完整遍历数据一次。只有在你反复查询数据时这个成本才值得付出。你不按该列聚合。如果你只是过滤或显示字符串好处有限。在这些情况下保持字符串列原样。如果不确定请按“衡量效果”中所述比较两个版本。结论按重复字符串分组代价高昂。通过将它们移入一个带有已排序、窄整数键的小型维度表DuckDB 可以在定宽整数上聚合并保持其哈希表紧凑。字符串在最后针对已经变小的结果进行连接时返回。当您反复对具有少量不同值的长字符串进行聚合时这种方法帮助最大。你可以在性能指南中找到此提示的精简版本。