大数据：COUNT(DISTINCT) 为什么这么慢？SQL 改写技巧与 HyperLogLog 近似去重

一、问题的本质：COUNT(DISTINCT) 到底慢在哪

先抛一个反直觉的事实：COUNT(*) 在列存引擎里往往能靠元数据或轻量扫描在毫秒级返回，而 COUNT(DISTINCT user_id) 在千万级基数的表上动辄几十秒甚至超时。两者差在哪？差在"可加性"。

COUNT(*) 是可加的：分区 A 有 100 万行、分区 B 有 200 万行，总数直接相加得 300 万。而 COUNT(DISTINCT) 是不可加的：分区 A 的去重集合 {1,2,3} 与分区 B 的 {3,4,5} 合并后去重结果是 5，而不是 3+3=6。这个"不可加性"决定了它无法在分区级别简单汇总，必须保留中间状态（集合或哈希表）并在合并阶段做真正的去重运算。这就是所有性能问题的根源。

本文评述：很多工程师把 COUNT(DISTINCT) 慢归咎于"数据量大"，这其实是误判。真正的瓶颈是"去重状态无法压缩合并"。理解了不可加性，你才会明白为什么预聚合、位图、HLL 这三类优化本质上都在做同一件事——把不可加的全局状态，转换成可加或可合并的局部状态。

从信息论角度看，精确去重所需的状态空间下界与基数本身成正比：要精确判断一个元素是否出现过，最坏情况下必须记住所有出现过的元素（或它们的某种无碰撞编码）。这意味着精确去重的内存开销是 Ω(n)（n 为去重基数），无法用亚线性空间完成。而 HyperLogLog 之所以能用固定几 KB 估算上亿基数，正是因为它放弃了"记住每个元素"，只保留"基数规模的统计指纹"。这条"精确-近似"的分界线，是全文的分析主轴。

二、执行计划解剖：从逻辑算子到物理代价

2.1 逻辑层：Aggregate 算子里的 Distinct 语义

在关系代数里，COUNT(DISTINCT x) 等价于对 x 做投影去重后再计数。多数优化器会把它表达为 Aggregate[count] ∘ Distinct[x] 的组合。注意这里的 Distinct 是一个独立的逻辑算子，它需要物化去重后的中间结果。当查询里同时出现多个 COUNT(DISTINCT)（例如同时统计去重用户数、去重商品数、去重会话数），优化器往往要为每个 distinct 列维护独立的去重状态，内存与 CPU 开销成倍叠加。

2.2 物理层：排序去重 vs 哈希去重

物理执行上，去重通常有两种实现：

哈希去重看似期望 O(n) 更快，但它有一个致命弱点：必须把全部 distinct 值装进内存哈希表。当基数达到千万甚至上亿（例如去重 UV、去重设备号），哈希表膨胀导致频繁 rehash 与 GC，甚至直接 OOM 触发 spill，性能断崖式下跌。排序去重虽然复杂度更高，但可以借助外部排序把内存压到可控范围，在超大基数下反而更稳。这就是为什么同一个 COUNT(DISTINCT) 在不同数据分布下表现差异巨大——它慢不慢，取决于基数与内存的比值，而不只是数据行数。

2.3 分布式下的 Shuffle 放大

在分布式引擎中，COUNT(DISTINCT) 通常需要按 distinct 列做 shuffle，把相同值汇聚到同一节点才能全局去重。这一步的网络传输量约等于"去重列的基数 × 编码长度"，当基数上亿时，shuffle 数据量可达数十 GB，成为真正的瓶颈。更糟的是，如果查询里有多个 COUNT(DISTINCT)，可能触发多轮 shuffle。笔者在实际排查中见过一个典型案例：某报表同时统计 5 个维度的去重数，单次查询触发 5 轮 shuffle，耗时从 8 秒涨到 4 分钟——问题不在计算，而在数据搬运。

笔者认为：诊断 COUNT(DISTINCT) 性能问题时，第一步永远应该是看执行计划里的 shuffle 数据量与去重算子的峰值内存，而不是盲目加资源。很多"慢查询"其实是 shuffle 放大与内存溢出两个问题叠加，加机器只能缓解不能根治。

三、精确去重的 SQL 改写路径（上）：预聚合与分组两阶段

3.1 预聚合：把去重提前到 ETL 层

最朴素也最有效的思路：如果业务允许，把"明细去重"变成"预聚合去重"。例如按天统计 UV，不必每次查询都对全量明细做 COUNT(DISTINCT)，而是在每日 ETL 中先算出当天的去重集合（或去重数），查询时再对结果做合并。但如前所述，去重数不可加，所以预聚合必须保留"可合并的中间状态"而非最终数字。

一种常见做法是保留每日的 bitmap 或 HLL 中间态（后文详述），另一种是保留"用户-天"维度的去重明细表，查询时再对更小粒度做去重。后者的代价是存储放大，但换来查询时的数据量骤减。笔者建议：预聚合的粒度选择应遵循"查询最细粒度 + 一层汇总"原则，即预聚合到比查询粒度细一级，既保留灵活性又控制数据量。

3.2 分组两阶段：先 GROUP BY 再 COUNT

当无法预聚合时，可以把单次全局去重拆成"局部去重 + 全局合并"两阶段。核心改写模式如下：

-- 原始写法：全局去重，shuffle 放大
SELECT COUNT(DISTINCT user_id) FROM events WHERE dt = '2024-06-01';

-- 改写一：两阶段聚合（利用引擎自动优化，显式写出更可控）
SELECT COUNT(*) FROM (
  SELECT user_id
  FROM events
  WHERE dt = '2024-06-01'
  GROUP BY user_id
) t;

-- 改写二：按分桶列局部去重后再合并（适合超大基数）
SELECT SUM(cnt) FROM (
  SELECT bucket_id, COUNT(DISTINCT user_id) AS cnt
  FROM events
  WHERE dt = '2024-06-01'
  GROUP BY bucket_id
) t;
-- 注意：改写二仅在 user_id 不跨桶时精确，跨桶需去重合并，见下文

改写一本质是让优化器把 Distinct 算子显式化为 GroupBy，很多引擎（如 Spark 3.x、Trino）对 GROUP BY 的两阶段聚合（partial + final）优化比 COUNT(DISTINCT) 更成熟，能显著降低单节点状态。改写二则是把全局去重降维到分桶局部去重，但必须警惕"跨桶重复"问题——如果同一个 user_id 落在多个桶，直接 SUM 会重复计数。正确做法是分桶后仍需按 user_id 二次去重，或确保分桶键与去重键一致（即按 user_id 哈希分桶），此时每个 user_id 只落一个桶，SUM 才精确。

本文评述：改写二是一个高频踩坑点。很多文章笼统说"分桶后 SUM 即可"，却忽略了分桶键与去重键的一致性前提。笔者强调：只有当分桶函数对去重键是确定性映射（同一去重键必落同一桶）时，局部去重结果才可加。否则必须回到全局去重，或改用位图/HLL 这类可合并结构。

3.3 多列去重的拆分技巧

当需要 COUNT(DISTINCT a, b) 时，可先拼接成复合键再计数，避免引擎对多列分别维护状态：

-- 多列去重：拼接为单键，减少状态数
SELECT COUNT(DISTINCT concat(a, '|', b)) FROM t;

-- 若引擎支持，用结构化组合更安全（避免分隔符冲突）
SELECT COUNT(DISTINCT (a, b)) FROM t;  -- ClickHouse 支持 tuple 去重

拼接法要注意分隔符冲突与类型转换开销，字符串拼接本身也有成本。ClickHouse 的 tuple 去重、Doris 的多列 bitmap 是更原生的方案。笔者认为，多列去重的优化优先级应低于单列——因为多列组合的基数通常远高于单列，此时更应考虑是否真的需要精确值，还是可以接受 HLL 近似。

四、精确去重的 SQL 改写路径（下）：位图与窗口去重

4.1 位图（Bitmap）：整数 ID 去重的利器

当去重键是连续或可映射的整数 ID（如自增用户 ID、商品 ID），位图是最优雅的精确去重方案。核心思想：用一个 bit 表示一个 ID 是否出现，去重即按位或（OR），计数即统计置位数（popcount）。位图天然可合并——多个分区的位图做 OR 即得全局去重集合，完美解决不可加性问题。

以 Roaring Bitmap 为代表的压缩位图，通过容器分桶（array/bitmap/run 三种容器）在稀疏与稠密场景下都能保持高压缩比。Doris 的 BITMAP 类型、ClickHouse 的 groupBitmap、StarRocks 的 bitmap_union 都基于此。一个亿级用户 ID 的位图，压缩后通常仅几 MB 到几十 MB，远小于哈希表。

位图的局限也很明确：只适用于整数 ID，且 ID 空间不能过于稀疏（否则压缩效果打折）。对于字符串 ID（如 UUID、设备号），需先做全局字典编码映射为整数，这又引入了字典维护成本。笔者在实践中发现，位图方案的最大收益往往不在查询本身，而在"预计算位图 + 查询时 OR 合并"的架构——把去重成本前移到 ETL，查询时只做轻量合并。

4.2 窗口去重：用 ROW_NUMBER 替代 DISTINCT

在需要"去重后取某些列"而非单纯计数的场景，ROW_NUMBER() OVER (PARTITION BY key ORDER BY ...) 是比 DISTINCT 更可控的写法：

-- 去重取最新一条记录
SELECT * FROM (
  SELECT *, ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY update_time DESC) AS rn
  FROM events
) t WHERE rn = 1;

相比 SELECT DISTINCT *，窗口函数能明确指定"保留哪一条"，避免 DISTINCT 对全列去重导致的语义模糊与性能浪费。但要注意，窗口函数同样需要按 key 分区 shuffle，代价不一定更低，需结合执行计划判断。

五、HyperLogLog：用概率换性能的经典范式

5.1 算法直觉：从"看哈希前缀"到"估算基数"

HyperLogLog（HLL）的核心洞察极其优雅：对每个元素做均匀哈希，观察哈希值的二进制表示中"第一个 1 出现的位置"（即前导零个数）。如果随机抛硬币，连续出现 k 个反面（前导零）的概率是 2^(-k)，那么在一批随机数中观察到的最长前导零为 k，就暗示这批数的规模大约在 2^k 量级。单个观察噪声极大，但把哈希空间分成 m 个桶、每桶记录最大值、再对 m 个估计做调和平均，就能把误差压到约 1.04/√m。

这个"分桶+调和平均"的设计是 HLL 相对更早的 Linear Counting、LogLog 的关键改进。调和平均对异常值不敏感，使得 HLL 在宽基数范围内保持稳定误差。标准 HLL 使用 m = 2^p 个寄存器（p 通常取 10~16），每个寄存器只需 6 bit 存前导零计数，总空间约 m×6/8 字节。p=14 时约 12 KB，可估算上亿基数，误差约 0.81%。

本文评述：HLL 常被误解为"随机采样"，其实它是确定性的——同一组输入、同一哈希函数，输出永远相同。它的"近似"来自信息压缩（只保留前导零统计），而非随机性。理解这一点，才能正确看待 HLL 的可重复性与可合并性：寄存器取 max 合并是确定性的，所以分布式合并结果稳定可复现。

5.2 可合并性：HLL 真正的工程价值

HLL 最被低估的特性是可合并性。两个 HLL 结构合并，只需对每个寄存器取 max，无需重新扫描原始数据。这意味着：可以按天预计算 HLL 并存储，查询任意时间范围时只需合并对应天数的 HLL 寄存器，复杂度与天数成正比而非数据量。这正是 ClickHouse 的 uniqCombined、Doris 的 HLL_UNION、Presto 的 approx_distinct 能在大宽表上秒级返回 UV 的根本原因。

-- ClickHouse：预计算每日 HLL，查询时合并
CREATE TABLE uv_daily (
  dt Date,
  hll AggregateFunction(uniq, UInt64)
) ENGINE = AggregatingMergeTree()
ORDER BY dt;

-- 写入时聚合
INSERT INTO uv_daily
SELECT dt, uniqState(user_id) FROM events GROUP BY dt;

-- 查询任意范围 UV：合并 HLL 状态
SELECT uniqMerge(hll) FROM uv_daily WHERE dt BETWEEN '2024-06-01' AND '2024-06-30';

这段 SQL 展示了 HLL 的典型工程范式：状态（State）与合并（Merge）分离。写入时只做局部聚合生成状态，查询时合并状态得到结果。相比每次都扫明细，数据量从"行数"降到"天数×12KB"，性能提升可达几个数量级。

5.3 HLL 的边界：小基数偏差与修正

原始 HLL 在小基数（远小于 m）时误差急剧放大，因为大量寄存器为 0，调和平均失效。标准做法是引入偏差修正：小基数时退化为 Linear Counting（统计空寄存器比例），大基数时用 HLL 估计，中间区间用经验修正。这也是为什么很多引擎的实现叫 "uniqCombined" 或 "HLL++"——它们组合了多种估计器。Google 的 HLL++ 论文（Heule et al., 2013）系统解决了稀疏表示与偏差修正问题，至今仍是工程实现的参考基准。

六、误差模型与工程参数：HLL 到底能信几分

6.1 标准误差公式与参数选择

HLL 的相对标准误差约为 1.04 / √m，其中 m = 2^p。据此可反推所需精度对应的 p 值：

需要强调：这是标准误差，不是最大误差。实际单次估计的偏差约 68% 落在 ±1σ 内，95% 落在 ±2σ 内。也就是说 p=14 时，单次查询有约 5% 概率偏差超过 1.6%。对于 UV 这类百万级指标，1.6% 意味着上万人的误差，是否可接受必须由业务方确认，而非技术方单方面决定。

笔者认为：HLL 落地的最大障碍往往不是技术，而是"误差沟通"。工程师需要把"0.81% 标准误差"翻译成业务语言："100 万 UV 可能显示为 99.2 万到 100.8 万之间"。如果业务方无法接受，就该回到精确方案；如果能接受，就应明确写入数据口径文档，避免后续对账纠纷。

6.2 误差的叠加：合并多个 HLL 的影响

合并多个 HLL 时，误差不会简单相加，但会因各分片基数不同而复杂化。理论上，合并后的误差仍约 1.04/√m（寄存器数不变），但当各分片基数极不均衡时，小分片的估计噪声可能被大分片掩盖，反之亦然。工程上建议：同一指标的所有分片使用相同的 p 值与哈希函数，否则合并结果不可信。这也是为什么跨引擎（如 ClickHouse 与 Doris）的 HLL 结果通常不能直接合并——哈希算法与寄存器布局不同。

6.3 与精确值的对账策略

生产环境中，建议保留一条"精确对账"链路：对关键指标（如付费用户数）用精确去重，对海量 UV 用 HLL，并定期抽样比对两者偏差是否在预期范围内。若偏差持续超出 2σ，需排查哈希函数是否均匀、是否有数据倾斜或 p 值配置错误。这种"近似为主、精确校验"的双轨制，是笔者推荐的稳妥落地方式。

七、主流引擎实现对比与调优实操

7.1 ClickHouse：uniq 家族的分层设计

ClickHouse 提供了 uniq（自适应，小基数精确、大基数 HLL）、uniqExact（精确）、uniqCombined（组合 HLL+精确）、uniqHLL12（经典 HLL）等多种实现。默认的 uniq 在基数小于约 10 万时用精确哈希，超过后切换 HLL，兼顾小基数精度与大基数性能。调优要点：

• 对精度敏感且基数可控的指标，显式用 uniqExact，避免自适应切换带来的不确定性；
• 用 AggregatingMergeTree 预存 uniqState，查询时 uniqMerge，这是 ClickHouse 做 UV 的标准姿势；
• 注意 uniq 的精度参数不可调，若需更高精度用 uniqCombined(16) 指定更大寄存器。

7.2 Apache Doris / StarRocks：Bitmap 与 HLL 双支持

Doris 与 StarRocks 同时支持 BITMAP 与 HLL 类型。BITMAP 适合整数 ID 的精确去重，配合物化视图可做到查询时仅做 bitmap_union；HLL 适合字符串 ID 的近似去重。关键调优点是利用物化视图预聚合：在明细表上建带 bitmap_union 或 hll_union 的物化视图，查询自动改写命中，无需改 SQL。笔者实测（模拟数据，基于公开 benchmark 配置）在亿级明细上，物化视图可将 UV 查询从数十秒降到亚秒级。

7.3 Presto/Trino 与 Spark：approx_distinct 与自适应执行

Trino 的 approx_distinct 基于 HLL，默认误差约 2.3%，可通过 approx_set 与 merge 做预聚合。Spark 3.x 引入了自适应查询执行（AQE），能在运行时根据 shuffle 统计动态合并分区、切换 join 策略，对 COUNT(DISTINCT) 的 shuffle 放大有一定缓解，但不能改变去重状态本身的代价。Spark 的 approx_count_distinct 基于 HyperLogLog++，误差约 1-2%。

本文评述：引擎选型时，不要只看"支持不支持 HLL"，而要看"是否支持状态预存与合并"。支持 State/Merge 语义的引擎（ClickHouse、Doris）能把去重成本前移，而只提供函数级 approx_distinct 的引擎（如 Trino）每次仍需扫明细。这是架构层面的差异，比函数名更重要。

八、前沿进展：近三年研究与工程演进

8.1 基数估计的持续改进

HLL 并非终点。近三年，学术界与工业界在基数估计上持续推进：Ertl 提出的更精确估计器（如 Ertl 2017 的改进版，后续被广泛引用与工程化）显著降低了小基数偏差；稀疏表示与压缩寄存器方案在保持精度的同时进一步压缩空间；针对流式场景的滑动窗口基数估计也有新工作。这些改进大多已进入开源引擎实现，例如 ClickHouse 与 Doris 的 HLL 实现都吸收了偏差修正的工程经验。

另一条路线是"精确与近似的自适应融合"：根据数据分布动态选择精确哈希、位图或 HLL，并在查询计划阶段估算基数以决定策略。这类"代价感知的去重"是查询优化器研究的热点，Trino 与 Spark 的 CBO（基于代价的优化）都在向此演进。

8.2 Lakehouse 与实时场景的新挑战

随着 Iceberg、Hudi、Delta Lake 等开放表格式的普及，去重优化面临新问题：开放格式缺乏引擎原生的聚合状态类型，HLL/位图中间态难以直接落表。近年的工程实践多采用"旁路聚合表"或"预计算指标层"来规避，也有研究探索在表格式层引入 sketches 列类型。笔者认为，Lakehouse 场景下的去重优化，短期内仍会以"预计算 + 近似"为主，标准化 sketches 类型尚需生态协同。

实时场景（Flink + 实时数仓）中，去重还面临状态后端压力。Flink 的 COUNT(DISTINCT) 若用状态存储全部 key，状态会无限膨胀。工程上常用"状态 TTL + HLL 近似"或"位图状态"来控制，这也是流批一体去重口径一致性的难点。

8.3 可扩展阅读与教程

• ClickHouse 官方文档 uniq 函数族：clickhouse.com/docs（uniq 系列）
• Apache Doris BITMAP/HLL 使用指南：doris.apache.org/docs
• Trino approx_distinct 文档：trino.io/docs
• Roaring Bitmap 官方与论文：roaringbitmap.org
• HyperLogLog 原始论文与 HLL++ 论文可在 ACM/IEEE 数字图书馆检索（Flajolet et al., 2007；Heule et al., 2013）。

九、决策框架：什么场景该用哪种去重

把前文所有路径收敛成一张决策表，是本文的落地目标。核心判断维度有三个：基数规模、精度要求、去重键类型。

具体操作路径建议按以下步骤执行：

1. 量化基数：先用 approx_distinct 或采样估算去重键基数，这是所有决策的前提；
2. 确认精度：与业务方明确可接受的误差范围，写入数据口径；
3. 看执行计划：定位瓶颈是 shuffle、内存还是计算，对症下药；
4. 优先预聚合：能前移到 ETL 的绝不放到查询时；
5. 再选数据结构：整数 ID 优先位图，字符串大基数优先 HLL；
6. 建立对账：近似指标保留精确抽样校验，持续监控偏差。

笔者认为：去重优化的最高境界不是"用上 HLL"，而是"让业务接受近似"。技术方案再优雅，若业务方坚持精确，最终仍要回到位图或两阶段聚合。因此，沟通精度预期与设计数据结构同等重要，这往往是项目成败的分水岭。

十、结语与延伸阅读

回到开头那条主线：COUNT(DISTINCT) 慢的根源是不可加性，而所有优化都在把不可加的全局状态转化为可合并的局部状态——预聚合是空间换时间，位图是编码换合并，HLL 是精度换空间。三者不是互斥选项，而是同一条"精确-近似"光谱上的不同刻度。工程决策的本质，是在这条光谱上找到业务可接受的那个点。

本文刻意没有堆砌公式推导，而是把重点放在"为什么"与"怎么选"。因为笔者相信，掌握原理后，具体函数的用法查文档即可；而选错方向，再多的调优技巧也是徒劳。希望这条分析主线，能帮你在下一次面对慢查询时，先问对问题，再动手改写。