Google 面试：找出搜索词的长尾分布前 10%。

考察要点

这道题面试官想看你是否懂 窗口函数（Window Functions） 的高级用法，特别是如何进行 累积计算（Cumulative Calculation）。同时，它也考察你将一个商业概念（长尾分布）转化为精确的 SQL 逻辑的能力，以及使用 CTE (Common Table Expressions) 来组织复杂查询的工程素养。

核心概念

面试的核心是围绕“长尾分布”的计算展开的，这需要以下几个关键 SQL 概念的支撑。

1. 长尾分布 (Long Tail Distribution)

在搜索、电商等场景中，少数“头部”项目贡献了大部分的流量和收入，而大量“尾部”项目各自贡献很小，但加起来占据了不可忽视的比重。

• 头部 (Head): 少数高频搜索词，如 "天气", "特斯拉"。
• 尾部 (Tail): 大量低频、具体的搜索词，如 "北京朝阳区未来三小时降雨概率"。

图示 (ASCII):

 1  ^
 2频 |
 3率 | Head |
 4  |███
 5  |███
 6  |███|
 7  |███| Tail
 8  |███|█████████████████████████████████████████████████████████████
 9  +------------------------------------------------------------------->
10                                 搜索词 (按频率降序排列)

本题的“找出前 10%”通常指找出构成总搜索量前 10%的那些头部搜索词。

2. 窗口函数 SUM() OVER ()

窗口函数是解决此类问题的标准武器。它可以在不破坏原始行的情况下，对与当前行相关的“窗口”数据进行计算。

• 功能: 计算累积总和 (Cumulative Sum)。
• 语法: SUM(column) OVER (ORDER BY sort_column [ASC|DESC])
• 工作原理: 按照 ORDER BY 子句对数据进行排序，然后从第一行开始，逐行累加 column 的值。

数据示例: 假设我们已经统计好了搜索词频次。 原始数据 (query_counts)

SQL 示例:

 1SELECT
 2    query_text,
 3    frequency,
 4    SUM(frequency) OVER (ORDER BY frequency DESC) AS cumulative_frequency
 5FROM query_counts;

输出数据:

3. CTE (Common Table Expression)

CTE 使用 WITH 关键字定义一个临时的、命名的结果集，可以使复杂的多步骤查询逻辑更清晰、更易读。

• 优点:
  • 可读性: 将查询分解为逻辑上的步骤，如“第一步：计算频次”，“第二步：计算累积百分比”。
  • 可维护性: 修改逻辑时只需关注特定的 CTE。
  • 可重用性: 在同一个查询中可以被多次引用。

多种解法

假设我们有如下的搜索日志表 search_logs：

解法 1：使用窗口函数和 CTE (最优解)

这是最现代、最高效、可读性最好的解法。

• 版本: ✅ MySQL 8.0+ / PostgreSQL / SQL Server / Oracle；❌ MySQL 5.7 不支持窗口函数。

• 思路:

  1. CTE 1 (query_counts): 使用 GROUP BY 计算每个 query_text 的频次。
  2. CTE 2 (cumulative_dist): 在上一步结果的基础上，使用窗口函数 SUM() OVER () 计算累积频次和总频次。
  3. Final SELECT: 从 CTE 2 中筛选出累积频次百分比小于等于 10% 的记录。

• SQL 代码:

 1WITH query_counts AS (
 2    -- 步骤1: 计算每个搜索词的频次
 3    SELECT
 4        query_text,
 5        COUNT(1) AS frequency
 6    FROM
 7        search_logs
 8    GROUP BY
 9        query_text
10),
11cumulative_dist AS (
12    -- 步骤2: 计算累积频次和总频次
13    SELECT
14        query_text,
15        frequency,
16        -- 按频次降序计算累积和
17        SUM(frequency) OVER (ORDER BY frequency DESC) AS cumulative_frequency,
18        -- 计算总频次
19        SUM(frequency) OVER () AS total_frequency
20    FROM
21        query_counts
22)
23-- 步骤3: 筛选出构成总搜索量前10%的词
24SELECT
25    query_text,
26    frequency,
27    cumulative_frequency,
28    total_frequency,
29    -- 计算累积百分比
30    (cumulative_frequency * 1.0 / total_frequency) AS cumulative_percentage
31FROM
32    cumulative_dist
33WHERE
34    -- 筛选条件：累积频次首次超过10%之前的所有词
35    (cumulative_frequency - frequency) * 1.0 / total_frequency < 0.1
36ORDER BY
37    frequency DESC;

注意: WHERE 条件 (cumulative_frequency - frequency) < total_frequency * 0.1 是一个更精确的写法，它能确保即使某个词本身占比很大（如超过10%），只要它之前的累积占比小于10%，它也会被包含进来。

• 复杂度:
  • 时间复杂度: $O(N \log N)$，其中 N 是不同搜索词的数量。瓶颈在于 ORDER BY 操作（显式或在窗口函数内）。
  • 空间复杂度: $O(N)$，需要存储不同搜索词的频次和累积值。
• 索引依赖: 在 search_logs(query_text) 列上建立索引，可以极大地加速 GROUP BY 过程。

解法 2：使用自连接 (兼容老版本，性能较差)

在不支持窗口函数的旧版数据库（如 MySQL 5.7）中，可以使用自连接模拟累积求和。

• 版本: ✅ 几乎所有 SQL 版本；❌ 性能差，不推荐在大数据集上使用。

• 思路:

  1. CTE (query_counts): 同样先计算频次。
  2. Self-Join: 对于 query_counts 中的每一行 t1，连接所有频次大于等于 t1 的行 t2，然后对 t2 的频次求和，得到 t1 的累积频次。

• SQL 代码:

 1WITH query_counts AS (
 2    SELECT
 3        query_text,
 4        COUNT(1) AS frequency
 5    FROM
 6        search_logs
 7    GROUP BY
 8        query_text
 9)
10SELECT
11    qc1.query_text,
12    qc1.frequency
13FROM
14    query_counts qc1
15JOIN
16    query_counts qc2 ON qc2.frequency > qc1.frequency OR (qc2.frequency = qc1.frequency AND qc2.query_text <= qc1.query_text)
17GROUP BY
18    qc1.query_text, qc1.frequency
19HAVING
20    SUM(qc2.frequency) <= (SELECT SUM(frequency) FROM query_counts) * 0.1
21ORDER BY
22    qc1.frequency DESC;

注意: ON 条件中的 qc2.query_text <= qc1.query_text 是为了在频次相同时打破平局，确保累积和计算的确定性，否则结果可能不稳定。

• 复杂度:
  • 时间复杂度: 近似 $O(N^2)$，其中 N 是不同搜索词的数量。对于每个词，都需要扫描一次或多次频次表，性能极差。
  • 空间复杂度: $O(N)$。
• 索引依赖: query_counts 表（或 CTE）需要在 (frequency, query_text) 上有索引才能稍微缓解性能问题。

常见低分回答

1. 误解题目，计算 Top 10% 的行数:
   sql

   ⧉⛶

    1-- 错误: 这只是按频次排序后取前10%的词，而不是按累积量
    2SELECT query_text, COUNT(1) AS frequency
    3FROM search_logs
    4GROUP BY query_text
    5ORDER BY frequency DESC
    6LIMIT (SELECT COUNT(DISTINCT query_text) * 0.1 FROM search_logs);

2. 窗口函数使用错误:
   sql

   ⧉⛶

    1-- 错误: 在原始表上直接开窗，性能灾难
    2-- 这会导致对每一条日志记录都进行一次排序和计算，而不是先聚合
    3SELECT DISTINCT query_text
    4FROM (
    5    SELECT query_text, SUM(1) OVER (PARTITION BY query_text ORDER BY created_at) AS cume_freq
    6    FROM search_logs
    7) sub;

3. 忽略累积计算，只看单个词占比:
   sql

   ⧉⛶

    1-- 错误: 只找出了自身占比小于10%的词，完全没理解“累积”
    2SELECT query_text, COUNT(1) AS frequency
    3FROM search_logs
    4GROUP BY query_text
    5HAVING COUNT(1) / (SELECT COUNT(1) FROM search_logs) < 0.1;

4. 在 WHERE 子句中使用窗口函数:
   sql

   ⧉⛶

    1-- 语法错误: 窗口函数不能直接用在 WHERE 子句中
    2-- 因为 WHERE 在窗口函数计算之前执行
    3SELECT query_text, SUM(COUNT(1)) OVER (ORDER BY COUNT(1) DESC)
    4FROM search_logs
    5GROUP BY query_text
    6WHERE SUM(COUNT(1)) OVER (...) < 100; -- 这会直接报错

工程实践与优化

• 数据量级与预聚合: 在生产环境中，search_logs 表可能有数十亿甚至上万亿行。直接对原始日志表执行这种查询是不可接受的。通常会有一个离线或实时的ETL任务，将数据预聚合到一张天级/小时级的汇总表，如 query_frequency_hourly(hour, query_text, frequency)。我们的分析查询应该基于这张小得多的汇总表。
• 执行计划分析 (EXPLAIN):
  • 对于解法 1，EXPLAIN 的关键步骤应该是：
    1. search_logs 表扫描（最好是索引扫描）以完成 GROUP BY。如果 Extra 列出现 Using temporary; Using filesort，说明 query_text 列上缺少索引。
    2. 对聚合后的结果进行窗口函数计算，这里通常会涉及排序（Window aggregate with sort）。
• 近似计算: 对于 Google 级别的规模，精确计算可能成本太高或太慢。可以采用近似算法，如 HyperLogLog 来估算基数，或使用采样数据来估算分布。
• 避免大事务: 这个查询是只读的，不涉及事务。但要确保它不会长时间锁定元数据或消耗过多系统资源，影响线上业务。设置 statement_timeout 是一个好习惯。

常见追问与延伸题目

1. 追问：如果数据量增长 100 倍，这条 SQL 性能怎样？怎么优化？

   • 回答要点 1 (性能瓶颈): 性能会急剧下降。瓶颈主要在第一步的 GROUP BY 操作，它需要扫描 100 倍的数据。即使有索引，IO 和 CPU 消耗也会非常巨大，查询可能从几分钟变成几小时，甚至无法完成。
   • 回答要点 2 (优化方案): 必须放弃实时查询原始表的想法。架构上需要引入数据分层和预计算。
     • 批处理方案: 使用 Spark 或 MapReduce 等大数据框架，每天定时对新增日志进行计算，将结果（如 query_counts）存入一个专门用于分析的数据库（如 ClickHouse, Doris）或数据仓库（如 Hive, BigQuery）中。分析师的 SQL 直接查询这个结果表。
     • 流处理方案: 使用 Flink 或 Spark Streaming，实时地对搜索日志流进行聚合，并将结果（如每分钟的词频）更新到汇总表中。这可以提供更准实时的分析。

2. 追问：如果我想找到分布曲线的“拐点”（Elbow Point），而不是固定的前 10%，该怎么做？

   • 回答要点 1 (SQL 的局限性): 这是一个更复杂的数学/统计问题，单纯用 SQL 很难直接解决。“拐点”没有一个像“前10%”这样明确的定义。
   • 回答要点 2 (程序化解决方案): 通常的做法是：
     1. 使用 SQL 导出有序的频次列表（query_text, frequency）。
     2. 在 Python/R 等语言中加载数据。
     3. 使用特定算法库（如 kneed in Python）来寻找拐点。一种常见的启发式方法是：将累积分布曲线的起点和终点连成一条直线，找到曲线上离这条直线最远的点，该点即为“拐点”。这需要进行几何计算，超出了标准 SQL 的范畴。

3. 追问：如果换成 PostgreSQL 或 ClickHouse，答案有什么不同？

   • 回答要点 1 (PostgreSQL): PostgreSQL 拥有非常强大和标准的窗口函数实现。解法 1 的 SQL 代码几乎可以原封不动地在 PostgreSQL 上运行，并且性能通常很好。其查询优化器和执行引擎对这类分析查询支持非常成熟。
   • 回答要点 2 (ClickHouse): ClickHouse 是一个为 OLAP（在线分析处理）设计的列式数据库，它处理这种聚合和排序查询的速度极快。
     • 语法: SQL 语法与标准类似，解法 1 同样适用。
     • 性能: 由于其列式存储和向量化执行引擎，即使在非常大的数据集上，第一步的 GROUP BY 也会比传统行式数据库（如 MySQL）快几个数量级。整个查询的性能会远超 MySQL 或 PostgreSQL。对于这个问题，ClickHouse 是理想的数据库选型。