TopK：LIMIT 和近似 TopK 的差别

做的事：真实构造一批访问量近似的"头部用户"，对比两种TopK

代码CREATE TABLE demo.topkhi (k UInt64, uid UInt64) ENGINE=MergeTree ORDER BY k; -- 50%流量集中在20个uid上(近似均分)，另外50%流量分散到468万个uid INSERT INTO demo.topkhi SELECT number, if(rand()%100<50, number%20, number%5000000) FROM numbers(20000000); -- 精确TopK SELECT uid, count() AS c FROM demo.topkhi GROUP BY uid ORDER BY c DESC LIMIT 5; -- 近似TopK SELECT topK(5)(uid) FROM demo.topkhi;

验证：内存真实相差565倍，耗时也更快

实测 · 本机执行输出（2000万行，468万个不同uid）

精确TopK(GROUP BY全部468万uid，排序取前5)：
  memory_usage: 267303168 字节（约267MB）
  query_duration_ms: 94

近似topK(5)：
  memory_usage: 484120 字节（约473KB）
  query_duration_ms: 51

真实内存差距：267303168 / 484120 ≈ 565倍

精确版真实必须先把全部468万个uid各自的计数都算出来、放进内存，才能知道哪5个是最大的；近似版的topK函数内部用的是有界大小的近似算法（Filtered Space-Saving），全程只维护一个固定大小的候选集合，不需要真实记住每一个见过的uid，这正是565倍内存差距的真实来源。

诚实的代价：真实的答案不完全一样

实测 · 本机执行输出（两种方法真实给出的Top5，不完全相同）

精确TopK（真实的排名和计数）：
  uid=1   count=501080
  uid=4   count=501059
  uid=3   count=500823
  uid=12  count=500598
  uid=6   count=500579

近似topK(5)（真实返回的结果）：
  [13, 16, 18, 6, 1]   ← 只有uid=6和uid=1真实命中了精确的Top5

这组对比诚实地暴露了近似TopK真实的代价：本文构造的数据里，"头部"的20个uid访问量真实非常接近（500579到501080之间，差距不到0.1%），这种势均力敌的场景恰恰是近似算法最容易给出不同排名的地方——Filtered Space-Saving算法真实靠维护一个有限大小的候选集合和近似计数器来工作，候选集合里的计数存在真实的误差范围，当多个候选的真实计数彼此差距小于这个误差范围时，近似算法给出的先后顺序、甚至具体哪几个能挤进候选集合，都可能和精确统计的结果对不上。topK真实适合的场景是"头部特征本来就很悬殊"的分布（比如访问日志里少数几个URL占了绝大多数流量，头部和尾部计数差着几个数量级），这时候近似算法几乎不会犯错，还能省下本文验证过的数百倍内存；但如果业务需要精确的排名（比如"这个月销量前5的商品是谁"这种要拿去做奖励发放的场景），近似算法给出的顺序不能直接当作真实结果使用，本文这组头部势均力敌的测试数据就是一个真实的反例。

分步演示：从565倍内存差距到诚实的排名误差

每一步都是本文上面用真实数据跑出来的原始结果。

565倍内存差距，但势均力敌时答案真实会不一样

这一步新验证的方法

本文用到的工具

本机 ClickHouse 26.9.4（单节点），真实对比 GROUP BY+ORDER BY+LIMIT 与 topK()
诚实展示头部势均力敌场景下近似算法真实给出不同排名的具体例子

下一篇 · CLICKHOUSE 内部原理 38

ClickHouse JOIN 的几种算法