Pivot 发现 GROUP BY 查询新优化方法，显著提升 Top-K 聚合性能

数据库世界最让我着迷的一点是：一个看似简单的操作，在被优化到极致时，竟能变得极其复杂。

顺着这个思路，我想分享一个我们最近发现的新颖优化，它显著提升了 Pivot 在处理“按聚合值取前 K 组”的 GROUP BY 查询时的性能。举个例子：“哪 10 个商品的订单数最多？”：

SELECT item_id, COUNT(*) AS c FROM orders GROUP BY item_id ORDER BY c DESC LIMIT 10;

“常规”GROUP BY 在分析型数据库中如何执行？

尽管每个数据库都觉得自己独一无二，但大多数数据库（包括 Pivot ;)）在分组键基数很高时（即 GROUP BY 中有很多组），执行 GROUP BY 的方式非常相似。

首先，数据库中的每个 CPU 线程分到一片输入数据，负责从磁盘读取、解码，并为聚合做准备：

BASE DATAslice 1slice 2slice 3slice 4CPU thread 1fetch + decodedecoded rowsCPU thread 2fetch + decodedecoded rowsCPU thread 3fetch + decodedecoded rowsCPU thread 4fetch + decodedecoded rows

然后，每个线程根据自己的解码数据，按分组键将其划分为 X 个分区，并分别聚合每个分区。例如，ClickHouse 使用 256 个分区，因此每个线程维护自己的一套 256 个哈希表，每个分区一个：

decoded rowsCPU thread 1P0hash tableitem_3f1a12item_c91d4……P1hash tableitem_5d489item_a81c2……P2hash tableitem_9b037item_02be1……⋮P15hash tableitem_d81e3item_7a468……decoded rowsCPU thread 2P0hash tableitem_d2a46item_42d12……P1hash tableitem_9ab78item_f36c1……P2hash tableitem_71d93item_0e8511……⋮P15hash tableitem_7e205item_e4c73……decoded rowsCPU thread 3P0hash tableitem_6e7f10item_b05e1……P1hash tableitem_a9135item_c0582……P2hash tableitem_2f4a3item_7d616……⋮P15hash tableitem_b7d22item_5c6f4……decoded rowsCPU thread 4P0hash tableitem_8f3a4item_1c772……P1hash tableitem_40bd7item_ee911……P2hash tableitem_35af2item_c6d05……⋮P15hash tableitem_9c3b1item_e1a89……

• Pivot 在这里采用了不同的方法，而不是哈希表，但那是另一篇博客文章的故事了 ;)

让这些哈希表对每个线程私有，可以让线程独立聚合数据，无需加锁或写入相同的内存位置，从而避免 CPU 缓存之间的争用。

当所有线程完成这一初始聚合后，每个 worker 被分配一个分区范围进行合并。对于每个分区，worker 收集所有线程产生的部分聚合结果，并将它们合并为该分区各组的最终聚合结果：

PARTITIONSmergedmergingwaitingP0P1P2P3range P0–P3P4P5P6P7range P4–P7P8P9P10P11range P8–P11P12P13P14P15range P12–P15CPU thread 1merging P1CPU thread 2merging P5CPU thread 3merging P9CPU thread 4merging P13

一旦所有分区都合并完成，数据库将所有分区结果拼接起来，生成完整的 GROUP BY 结果：

CPU thread 1merged P0–P3P0P1P2P3CPU thread 2merged P4–P7P4P5P6P7CPU thread 3merged P8–P11P8P9P10P11CPU thread 4merged P12–P15P12P13P14P15groupCOUNT(*)user_8f3a1c41user_02be777user_c91d4018……

所有这些工作真的必要吗？

虽然这个过程确实能输出正确的结果，但在某些（非常常见的）查询模式中，这个 GROUP BY 算法做了远超实际需要的工作。具体来说，在最终答案并未使用全部聚合结果的查询中，许多组和分区在并不需要的情况下被聚合了。

以我们之前的例子为例：“哪 10 个商品的订单数最多？”

SELECT item_id, COUNT(*) AS c FROM orders GROUP BY item_id ORDER BY c DESC LIMIT 10;

如果我们的系统使用 4,096 个分区，前 10 个商品最多只能属于其中 10 个分区。这就剩下至少 4,086 个分区，它们的结果对最终答案毫无贡献——然而我们仍然花费大量时间和计算来合并它们。

这种模式的查询在我们见到的工作负载中相当常见：“我们仓库中评分最高的 100 个商品是哪些？”、“我们最大的 50 个付费客户是谁？”、“过去 24 小时内我们平台上哪些帖子获得的点赞最多？”。鉴于此，我们认为值得探索这些查询是否可以被优化！

为了解决这种冗余工作的问题，我们寻找一种结构，能够在聚合阶段推进过程中帮助剪枝部分分区。作为 Bloom filter 的忠实爱好者（以及 i-love-bloom-filters.com 的自豪拥有者！），我们认为一种基于哈希的概率性结构可能有助于实现这一目标。

我们能想到的最“朴素”的实现，就是简单地为每个分区维护一个全局计数器或聚合值，之后用它来决定跳过哪些分区。

对于我们的“订单数最多的商品”查询，这意味着为每个分区维护一个订单总数计数器：

PARTITIONSP0orders1,284P1orders1,500P2orders3,402P3orders2,130P4orders1,500P5orders1,116P6orders977P7orders1,221P8orders1,498P9orders2,017P10orders1,133P11orders1,390P12orders1,725P13orders1,033P14orders1,508P15orders1,377

在合并阶段，在合并每个新分区之前，我们可以将其订单总数与当前 TopK 结果中的最小计数进行比较。

如果该分区的总数更小，我们就可以安全地完全跳过合并它：任何单个组的订单数都不可能超过整个分区，因此它的任何组都无法影响我们当前的 TopK 结果。

PARTITIONSwaitingprunedmergingmergedP0orders1,284P1orders1,500P2orders3,402P3orders2,130P4orders1,500P5orders1,116P6orders977P7orders1,221P8orders1,498P9orders2,017P10orders1,133P11orders1,390P12orders1,725P13orders1,033P14orders1,508P15orders1,377CPU thread 2Current TopKORDER BY c DESC LIMIT 10#itemc#1item_3b6d1,300#2item_e9a11,271………#10item_7b2f1,000P6: 977 → pruned, never merged

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）