Netflix 面试：找出连续观看同一剧集 5 集以上的用户。

考察要点

这道题是“连续性问题”或“Gaps and Islands Problem”的经典变体，面试官想看你是否能熟练运用现代 SQL 的核心利器——窗口函数来解决复杂的序列分析问题。同时，考察你对 SQL 逻辑的抽象能力，即将“连续的集数”转化为“一个具有相同值的数学分组”的能力。

核心概念

解决本题的核心是创造一个“分组标识”，使得连续的集数落在同一个组里，而不连续的则被分开。最经典的方法是**“数值减序列”**。

假设一个用户观看了某剧集的 1, 2, 3, 5, 6, 7, 8, 9 集。

1. 原始数据: episode_id 是观看的集数。
2. 生成序列: 我们使用窗口函数 ROW_NUMBER() OVER (PARTITION BY user_id, show_id ORDER BY episode_id) 为每个用户、每个剧集的观看记录生成一个从 1 开始的连续排名 rn。
3. 计算差值: 计算 grp = episode_id - rn。

数据示例

• 原始数据 (watching_history)

  user_id	show_id	episode_id
  101	1	1
  101	1	2
  101	1	3
  101	1	5
  101	1	6
  101	1	7
  101	1	8
  101	1	9

• 中间计算过程

  user_id	show_id	episode_id	rn (ROW_NUMBER)	grp (episode_id - rn)
  101	1	1	1	0
  101	1	2	2	0
  101	1	3	3	0
  101	1	5	4	1
  101	1	6	5	1
  101	1	7	6	1
  101	1	8	7	1
  101	1	9	8	1

可以看到，连续的 episode_id (1, 2, 3) 产生了相同的 grp 值 (0)，而另一段连续的 episode_id (5, 6, 7, 8, 9) 产生了另一组相同的 grp 值 (1)。这个 grp 就是我们梦寐以求的分组标识。

最后，我们只需按 user_id, show_id, grp 分组，并统计每组的数量即可。

多种解法

解法 1：窗口函数 ROW_NUMBER() (现代标准解法)

• 适用版本: ✅ MySQL 8.0+ / PostgreSQL / SQL Server / Oracle；❌ MySQL 5.7 及以下版本不支持。
• 思路: 这是解决此类问题的最优且最通用的方法。利用 episode_id 和 ROW_NUMBER() 的差值来创建分组键。

 1WITH NumberedEpisodes AS (
 2    -- 步骤1: 为每个用户和剧集的观看记录，按集数排序，生成一个连续的行号
 3    SELECT
 4        user_id,
 5        show_id,
 6        episode_id,
 7        ROW_NUMBER() OVER(PARTITION BY user_id, show_id ORDER BY episode_id) AS rn
 8    FROM
 9        watching_history
10),
11ConsecutiveGroups AS (
12    -- 步骤2: 用集数减去行号，为连续的观看序列创建分组标识
13    SELECT
14        user_id,
15        show_id,
16        (episode_id - rn) AS grp
17    FROM
18        NumberedEpisodes
19)
20-- 步骤3: 按分组标识进行分组计数，并筛选出数量大于等于5的
21SELECT
22    user_id
23FROM
24    ConsecutiveGroups
25GROUP BY
26    user_id, show_id, grp
27HAVING
28    COUNT(*) >= 5
29-- 使用 DISTINCT 确保每个用户只返回一次
30-- 也可以在最外层 SELECT DISTINCT user_id FROM (...)
31;

• 时间复杂度: $O(N \log N)$，主要开销在于窗口函数内的排序 (ORDER BY)。$N$ 是 watching_history 表的总行数。
• 空间复杂度: $O(N)$，因为 CTE (Common Table Expressions) 需要存储中间结果。
• 索引依赖: 在 (user_id, show_id, episode_id) 上建立复合索引是性能的关键。该索引可以被窗口函数中的 PARTITION BY 和 ORDER BY 子句完美利用，避免昂贵的外部排序（filesort）。

解法 2：自连接 (Self-Join)

• 适用版本: ✅ 所有 SQL 版本均支持，兼容性好。
• 思路: 对于每一条观看记录，都尝试向后连接 4 次，看是否存在 episode_id+1, episode_id+2, episode_id+3, episode_id+4 的记录。如果都能连接成功，则说明找到了一个长度为 5 的连续序列。

 1SELECT DISTINCT
 2    t1.user_id
 3FROM
 4    watching_history AS t1
 5JOIN
 6    watching_history AS t2 ON t1.user_id = t2.user_id AND t1.show_id = t2.show_id AND t2.episode_id = t1.episode_id + 1
 7JOIN
 8    watching_history AS t3 ON t1.user_id = t3.user_id AND t1.show_id = t3.show_id AND t3.episode_id = t1.episode_id + 2
 9JOIN
10    watching_history AS t4 ON t1.user_id = t4.user_id AND t1.show_id = t4.show_id AND t4.episode_id = t1.episode_id + 3
11JOIN
12    watching_history AS t5 ON t1.user_id = t5.user_id AND t1.show_id = t5.show_id AND t5.episode_id = t1.episode_id + 4;

• 时间复杂度: 在没有索引的情况下，复杂度接近 $O(N^5)$，是灾难性的。但在有合适索引的情况下，每次 JOIN 都是高效的索引查找，性能会显著提升，但多次 JOIN 的固定开销仍然存在。
• 空间复杂度: $O(K)$，其中 $K$ 是满足条件的起始记录数，通常远小于 $N$。
• 索引依赖: 必须在 (user_id, show_id, episode_id) 上建立复合索引。否则，该查询将导致多次全表扫描，无法在生产环境使用。此解法在小数据量或需要兼容老版本数据库时可以考虑。

常见低分回答

1. 忽略连续性，直接分组计数：这是最常见的错误，完全误解了题意。
   sql

   ⧉⛶

    1-- 错误：只统计了总观看集数，没有检查连续性
    2SELECT user_id FROM watching_history GROUP BY user_id, show_id HAVING COUNT(*) >= 5;

2. 使用 MAX-MIN 来判断连续性：这种方法无法处理序列中间的“空洞”。例如，对于 1, 2, 6, 7, 8，MAX-MIN 结果是 7，COUNT 是 5，但它不是连续的。
   sql

   ⧉⛶

    1-- 错误：无法处理内部断连
    2SELECT user_id FROM watching_history GROUP BY user_id, show_id HAVING MAX(episode_id) - MIN(episode_id) + 1 >= 5 AND COUNT(*) >= 5;

3. 窗口函数 PARTITION BY 子句不完整：忘记在 PARTITION BY 中包含 user_id 和 show_id，导致 ROW_NUMBER 在全局数据上排序，失去了分组的意义。
   sql

   ⧉⛶

    1-- 错误：窗口范围定义错误
    2ROW_NUMBER() OVER(ORDER BY episode_id) -- 应该是 PARTITION BY user_id, show_id ...

4. 自连接时忘记 show_id 条件：在自连接解法中，如果 JOIN 条件只写了 user_id 和 episode_id，可能会错误地将用户观看的不同剧集的集数连接起来。
   sql

   ⧉⛶

    1-- 错误：连接条件不严谨
    2... ON t1.user_id = t2.user_id AND t2.episode_id = t1.episode_id + 1 -- 缺少 t1.show_id = t2.show_id

工程实践与优化

• 执行计划分析:
  • 对于窗口函数解法，使用 EXPLAIN 查看执行计划。关键是看 Extra 列是否出现 Using filesort。如果 (user_id, show_id, episode_id) 索引存在，理想情况下不会出现 filesort，MySQL 可以利用索引的有序性来高效完成窗口计算。
  • 对于自连接解法，EXPLAIN 会显示多层嵌套的 JOIN。检查每一层的 type 是否为 ref 或 eq_ref，key 是否为你创建的复合索引。如果 type 是 ALL，说明索引失效，查询性能会极差。
• 大数据场景: 在 Netflix 这种 PB 级数据量的场景下，直接对线上生产表执行此查询是不可接受的。这类分析任务通常在数据仓库（如 Hive, Spark, BigQuery, Snowflake）中离线执行。
  • 批处理与物化：每天或每小时运行一个批处理作业，使用 Spark SQL 或 Hive SQL（同样使用窗口函数）计算出结果，并将结果存入一张汇总表（例如 user_consecutive_watch_summary）。线上的应用或 BI 报表直接查询这张轻量的汇总表。
• 锁与并发: 这种查询是只读的分析型查询（AP），在 InnoDB 的 MVCC 机制下，它不会阻塞线上的写入操作（OLTP）。但它会消耗大量 CPU 和 IO 资源，可能影响数据库整体性能，因此应在业务低峰期执行，或在只读从库上执行。

常见追问与延伸题目

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

   • 回答要点 1 (性能评估)：窗口函数解法的性能主要受限于排序，复杂度为 $O(N \log N)$。数据量增大 100 倍，执行时间会恶化超过 100 倍。自连接解法性能会更差。单机 MySQL 很快会达到瓶颈。
   • 回答要点 2 (优化方案)：必须转向分布式计算。使用 Spark SQL 在大数据平台上执行此查询。Spark 会将数据按 user_id 和 show_id 进行分区（Shuffle），然后在多个工作节点上并行执行窗口函数计算，利用集群的水平扩展能力来应对数据量的增长。最终的优化方案仍然是离线批处理 + 结果物化。

2. 追问：如果 episode_id 不是整数，而是像 S02E05 (季+集) 这样的字符串，怎么办？

   • 回答要点 1 (数据预处理)：需要在 SQL 查询内部对这个字符串进行解析，提取出季（Season）和集（Episode）的数字。可以使用 SUBSTRING、CAST 等字符串和类型转换函数。
   • 回答要点 2 (生成可排序键)：为了正确排序，需要综合考虑季和集。可以生成一个统一的排序值，例如 season * 1000 + episode_num（假设每季不超过 1000 集）。然后，在 ROW_NUMBER() 的 ORDER BY 子句中使用这个新生成的排序键，后续逻辑不变。

3. 追问：如果要求找出最长的连续观看序列，而不是满足 >=5 的所有用户，该如何修改？

   • 回答要点 1 (修改分组聚合逻辑)：在解法 1 的基础上，我们已经得到了每个连续片段的长度 COUNT(*)。我们不需要 HAVING 子句了。
   • 回答要点 2 (使用排名窗口函数)：可以对每个用户的所有连续观看片段的长度进行排名。使用 RANK() OVER (PARTITION BY user_id ORDER BY COUNT(*) DESC)。最后筛选出排名为 1 的记录，即为每个用户的最长连续观看记录。
     sql

     ⧉⛶

      1-- 找出每个用户最长的连续观看记录
      2WITH ... (前面的 CTE 不变)
      3, UserSeriesLength AS (
      4    SELECT user_id, show_id, grp, COUNT(*) as series_length
      5    FROM ConsecutiveGroups
      6    GROUP BY user_id, show_id, grp
      7)
      8, RankedSeries AS (
      9    SELECT *, RANK() OVER(PARTITION BY user_id ORDER BY series_length DESC) as rnk
     10    FROM UserSeriesLength
     11)
     12SELECT user_id, show_id, series_length
     13FROM RankedSeries
     14WHERE rnk = 1;