本页内容受版权保护 · 已添加水印 · 禁止任何形式转载
查询基础（SELECT / JOIN / 聚合 / 排序） · 聚合与分组

为什么 SELECT COUNT(DISTINCT col) 在大表上很慢？有哪些近似算法（HyperLogLog 等）？

Why is SELECT COUNT(DISTINCT col) slow on large tables? What are some approximation

答案语言

考察要点

这道题面试官想看你是否懂：

  1. COUNT(DISTINCT) 在数据库内核中的执行原理：面试官希望了解你是否清楚数据库为了完成精确去重，需要付出巨大的内存和 CPU 成本。
  2. 精确计数与近似计数之间的权衡（Trade-off）：这考察你的业务场景分析和架构设计能力。在海量数据下，能否接受一定的误差以换取数量级的性能提升，是区分初级和资深工程师的关键。
  3. 现代数据库和大数据系统中常用的近似计数算法：特别是 HyperLogLog (HLL) 的基本思想和应用场景。这部分知识展现了你的技术广度和深度。

核心概念

1. COUNT(DISTINCT col) 的精确计算原理与瓶颈

数据库为了得到一个精确的去重计数值，通常有两种内部实现策略：

策略一：排序（Sorting）

  1. 从表中读取所有 col 列的值。
  2. 对这些值进行排序。
  3. 遍历排序后的结果，相邻值如果不同则计数器加一。
  • 瓶颈：
    • CPU 密集：排序算法的时间复杂度通常是 O(Nlog⁡N)O(N \log N)，其中 N 是表的总行数。
    • I/O 密集：如果数据量巨大，无法全部加载到内存中（超过 work_mem 或 sort_buffer_size），数据库需要进行外部排序，即在磁盘上创建临时文件进行多路归并排序，这会产生大量的磁盘 I/O，性能急剧下降。

策略二：哈希（Hashing）

  1. 在内存中创建一个哈希表（Hash Table）。
  2. 遍历表中的每一行，获取 col 的值。
  3. 将 col 的值尝试放入哈希表。如果值已存在，则忽略；如果不存在，则插入。
  4. 最终，哈希表中元素的数量就是 COUNT(DISTINCT col) 的结果。
  • 瓶颈：
    • 内存密集：哈希表的空间复杂度是 O(Cardinality)O(\text{Cardinality})，其中 Cardinality 是去重后的基数。当 col 的唯一值非常多时（例如，用户 ID、设备 ID），哈希表会消耗巨量内存。
    • I/O 密集：同样，如果哈希表大小超过内存限制，其部分数据结构也可能需要交换到磁盘，导致性能问题。

索引优化： 如果 col 列上存在索引，MySQL/PostgreSQL 可以使用一种称为松散索引扫描（Loose Index Scan / Skip Scan） 的优化。它直接在索引的 B+ 树上进行跳跃式扫描，从一个唯一值直接跳到下一个唯一值，而无需读取所有行。这极大地提升了性能，因为它避免了全表扫描和在内存/磁盘中的排序/哈希操作。但当基数仍然非常大时（千万级以上），即使是索引扫描，其 I/O 开销和 CPU 计算成本依然不可忽视。

2. 近似计数算法：HyperLogLog (HLL)

当业务场景可以容忍微小误差时（例如，统计网站的日活跃用户 UV），近似算法是最佳选择。HyperLogLog 是其中的佼佼者。

  • 核心思想：HLL 不存储元素本身，而是通过对元素进行哈希，并观察哈希值的二进制表示中前导零（Leading Zeros） 的数量来估计基数。

    • 直觉：如果你随机生成一堆数字并对它们进行哈希，看到一个有很多前导零（如 00000000...1...）的哈希值是一个小概率事件。出现的次数越多，说明你尝试的原始数字就越多。HLL 正是利用这种概率现象来估算总共有多少个不同的数字。

  • 工作流程（简化版）：

    1. 分桶（Bucketing）：HLL 内部维护一个固定大小的数组，称为“桶”或“寄存器”（通常是 2k2^k 个，如 16384 个）。
    2. 哈希与分配：对于每一个输入值 item，计算其哈希值 hash(item)。
    3. 定位桶与更新：使用哈希值的一部分（如前 k 位）来确定它属于哪个桶。
    4. 计算前导零：使用哈希值的另一部分，计算其前导零的个数 p。
    5. 更新最大值：将 p 与该桶当前存储的值进行比较，只保留较大的那个。即 bucket[index] = max(bucket[index], p)。
    6. 估算：最后，通过对所有桶中的值进行一种特殊的平均（调和平均数），再乘以一个修正因子，得到最终的基数估算值。

  • 关键优势：

    • 空间恒定：HLL 的内存占用是固定的，与元素的基数无关，只与期望的精度有关。一个标准的 HLL 结构（如 Redis 中的实现）通常只需要 12KB 内存，就能在标准误差约为 0.81% 的情况下，估算上百亿的基数。
    • 可合并性：两个 HLL 结构可以进行合并（Merge），合并后的 HLL 代表了两个原始数据集的并集基数。这个特性在分布式计算中极为有用。HLL(A ∪ B) = merge(HLL(A), HLL(B))。

  • 支持情况：

    • MySQL/MariaDB: 原生不支持，但可以通过 UDF (User-Defined Function) 插件实现。
    • PostgreSQL: 通过 postgresql-hll 扩展支持。
    • Redis: 内置 PFADD, PFCOUNT, PFMERGE 命令。
    • ClickHouse, Presto, Trino, Spark, BigQuery: 原生支持 HLL 函数（如 approx_distinct, uniq）。

常见低分回答

  1. 回答过于笼统：“因为它要扫描全表，所以很慢。” —— 没有抓住重点。COUNT(*) 也要扫描全表，但通常比 COUNT(DISTINCT) 快得多。核心在于 DISTINCT 操作带来的排序或哈希的巨大开销。
  2. 只知其一不知其二：“数据库需要排序，排序很慢。” —— 只提到了排序，没有提到哈希也是一种常见的实现方式，并且忽略了两种方式共同的内存瓶颈。
  3. 忽略索引的作用：“COUNT(DISTINCT) 没法优化。” —— 这是一个错误的结论。对于精确计算场景，在列上添加索引是首选且最有效的优化手段，面试官很期待听到“松散索引扫描”这个关键词。
  4. 对近似算法一无所知：当被问到“如果可以接受误差，有什么办法”时，回答“不知道”或“只能分表分库”，这会错失展示技术广度的机会。
  5. 混淆 COUNT(DISTINCT col) 和 COUNT(col)：COUNT(col) 统计 col 列非 NULL 的行数，而 COUNT(DISTINCT col) 统计 col 列非 NULL 的唯一值的数量，两者语义和性能开销完全不同。

工程实践与优化

  1. 场景判断：精确 vs. 近似

    • 必须精确：订单数、用户账户余额、计费相关的统计。这些场景下，任何误差都是不可接受的。
    • 可以近似：网站 UV（Unique Visitor）、APP 日活/月活（DAU/MAU）、广告点击去重、搜索词热度分析。这些场景下，百万和百万零一百的差异对业务决策没有影响。

  2. 精确计算的优化策略

    • 加索引：最直接有效的方法。CREATE INDEX idx_col ON your_table(col);。通过 EXPLAIN 查看执行计划，确保 Extra 字段出现 Using index for group-by 或类似的提示，表明用上了松散索引扫描。
    • 预计算/物化视图：创建一张汇总表（Summary Table），通过定时任务（如每日凌晨）提前计算好前一天的 COUNT(DISTINCT) 结果并存储。查询时直接读取汇总表。这是典型的数据仓库思想。
    • 数据类型选择：在设计表时，如果某列需要频繁进行去重计数，且基数巨大（如各种 ID），应选择空间占用小且定长的数据类型（如 BIGINT 代替长字符串），以减少内存和 I/O 负担。

  3. 近似计算的落地

    • 应用层 + Redis：这是最常见的架构。业务代码在处理用户行为时，将用户 ID 通过 PFADD 命令添加到 Redis 的 HLL 结构中。需要查询 UV 时，使用 PFCOUNT 命令，毫秒级返回结果。
    sh
     1# 用户 123, 456, 789 访问了页面
     2PFADD page:1:uv user123 user456 user789
     3# 查询页面 1 的 UV
     4PFCOUNT page:1:uv
     5# (integer) 3
    • 使用支持 HLL 的数据库：如果数据已经存储在 ClickHouse、PostgreSQL（带扩展）等系统中，可以直接在 SQL 中使用其近似计数函数。
    sql
     1-- ClickHouse
     2SELECT uniq(UserID) FROM hits_table WHERE EventDate = '2023-10-26';
     3

     4-- PostgreSQL (with hll extension)
     5SELECT hll_cardinality(hll_agg(user_id)) FROM events WHERE event_date = '2023-10-26';

常见追问与延伸题目

  1. 追问：如果要对多个列进行去重计数，比如 COUNT(DISTINCT user_id, order_id)，情况有什么不同？

    • 回答要点：原理是相同的，但计算成本更高。数据库需要将 user_id 和 order_id 拼接成一个组合值，然后对这个组合值进行排序或哈希。
    • 优化：最佳优化方式是创建一个覆盖 (user_id, order_id) 的复合索引。这样数据库同样可以利用松散索引扫描来高效地统计。
    • HLL 方案：在应用层，可以将多个字段拼接成一个字符串（注意使用分隔符避免歧义，如 user_id + ":" + order_id），然后将这个拼接后的字符串添加到 HLL 结构中。

  2. 追问：COUNT(DISTINCT CASE WHEN ... END) 这种用法你了解吗？它有什么应用场景和性能特点？

    • 回答要点：这是一种非常强大的条件去重计数方法，常用于 BI 报表，可以在一次查询中计算多个维度的去重指标。
    • 示例：
      sql
       1SELECT
       2    COUNT(DISTINCT CASE WHEN platform = 'iOS' THEN device_id ELSE NULL END) AS ios_dau,
       3    COUNT(DISTINCT CASE WHEN platform = 'Android' THEN device_id ELSE NULL END) AS android_dau
       4FROM daily_logins
       5WHERE login_date = CURDATE();
    • 关键点：ELSE NULL 是核心，因为 COUNT(DISTINCT ...) 会忽略 NULL 值，从而巧妙地实现了按条件筛选。
    • 性能：这种查询通常无法有效利用 device_id 上的简单索引，因为它被包裹在 CASE 表达式中。如果性能瓶颈严重，最优的索引是 (login_date, platform, device_id)，这样可以快速定位到特定日期和平台下的设备 ID，并利用索引进行去重。

  3. 追问：除了 HyperLogLog，你还知道其他近似算法吗？它们有什么区别？

    • 回答要点：这表明面试官想考察你的知识广度。可以提另外两种常见的概率数据结构：
      • Bloom Filter（布隆过滤器）：主要用于判断“一个元素是否存在于一个集合中”。它有可能会误判（False Positive，即报告一个元素存在但实际不存在），但绝不会漏判（False Negative，即报告一个元素不存在但实际存在）。它不用于计数，而是用于高效的成员资格检查，例如在缓存穿透、爬虫 URL去重等场景。
      • Count-Min Sketch：主要用于估算数据流中元素的频率（即 GROUP BY ... COUNT(*) 的近似版），而不仅仅是基数。例如，可以用它来快速找到访问量 Top K 的 URL。它和 HLL 解决的问题不同，HLL 关注的是“有多少种”，Count-Min Sketch 关注的是“每一种有多少个”。
← Previous
如何统计每天每小时的活跃用户数？(date_format / hour() / 时间分桶)
Next →
MySQL 的 ORDER BY 内部使用什么算法？(filesort / index 排序 / 归并排序)