找出某段时间内连续 N 次失败的支付订单。

考察要点

这道题面试官想看你是否掌握了处理序列数据和连续性问题的核心 SQL 技能。具体来说，考察的是：

1. 窗口函数：这是解决此类问题的最优解。面试官希望看到你熟练运用 ROW_NUMBER、LAG 等函数来识别连续的数据“岛屿”（Islands）。
2. 逻辑建模能力：能否将“连续 N 次”这个业务需求，转化为精确的、可执行的 SQL 逻辑（例如，著名的“Gaps and Islands”问题模式）。
3. 多解思维与性能权衡：除了窗口函数，是否了解如自连接等传统解法，并能清晰地分析不同解法在性能、通用性和版本兼容性上的优劣。

核心概念

解决此问题的核心是识别出连续的失败记录“块”。假设我们有如下订单数据，要找出连续失败 3 次的用户。

示例数据: payment_orders 表

目标：找出 user_id = 101，因为他有连续 3 次失败记录（订单 2, 3, 4）。

核心解法模式：Gaps and Islands

这是一种经典的 SQL 问题模式，用于识别数据序列中的连续子序列（Islands）和将它们隔开的间隙（Gaps）。

实现原理：通过两次 ROW_NUMBER() 的差值来为连续的块生成一个唯一的分组 ID。

1. rn_all: 对每个用户的所有订单，按时间顺序编号。
2. rn_failed: 只对每个用户的失败订单，按时间顺序编号。
3. group_key: rn_all - rn_failed。对于一个连续的失败块，这个差值是恒定的。

图解：

可以看到，对于 user_id=101 的连续失败记录，group_key 都是 1。我们可以通过对 (user_id, group_key) 进行分组计数，来找到长度为 N 的连续失败块。

多种解法

假设问题是：找出所有在某段时间内，有过连续 3 次或以上支付失败记录的用户 ID。

解法 1：窗口函数 (Gaps and Islands)

这是最高效、最通用的现代解法。

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

  ⧉⛶

   1WITH numbered_orders AS (
   2    SELECT
   3        user_id,
   4        status,
   5        -- 为每个用户的所有订单按时间排序编号
   6        ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY created_at) AS rn_all,
   7        -- 仅为每个用户的失败订单按时间排序编号
   8        ROW_NUMBER() OVER(PARTITION BY user_id, status ORDER BY created_at) AS rn_status
   9    FROM
  10        payment_orders
  11    -- 建议缩小时间范围，提高性能
  12    -- WHERE created_at BETWEEN '2023-01-01' AND '2023-01-31'
  13),
  14failure_groups AS (
  15    SELECT
  16        user_id,
  17        -- 这个差值对于连续的失败记录是恒定的
  18        (rn_all - rn_status) AS group_key
  19    FROM
  20        numbered_orders
  21    WHERE
  22        status = 'failed'
  23)
  24SELECT
  25    user_id
  26FROM
  27    failure_groups
  28GROUP BY
  29    user_id, group_key
  30HAVING
  31    COUNT(*) >= 3;

• 时间/空间复杂度：主要开销在于排序，为 $O(N \log N)$，其中 N 是处理的记录数。空间复杂度为 $O(N)$，用于存储 CTE 的中间结果。
• 索引依赖：在 (user_id, created_at) 上建立复合索引，可以极大地加速 PARTITION BY 和 ORDER BY 操作。如果 status 也加入索引 (user_id, created_at, status)，可能实现覆盖索引，性能更佳。

解法 2：窗口函数 (LAG/LEAD 累加求和)

另一种使用窗口函数的思路，通过识别状态变化点来分组。

• 版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server；❌ MySQL 5.7。
• SQL 代码：
  sql

  ⧉⛶

   1WITH status_changed AS (
   2    SELECT
   3        user_id,
   4        status,
   5        -- 如果当前状态与上一条记录不同，则标记为1，否则为0
   6        CASE
   7            WHEN status <> LAG(status, 1, 'none') OVER (PARTITION BY user_id ORDER BY created_at) THEN 1
   8            ELSE 0
   9        END AS is_new_group
  10    FROM
  11        payment_orders
  12),
  13grouped_orders AS (
  14    SELECT
  15        user_id,
  16        status,
  17        -- 对标记进行累加求和，为每个连续块生成一个唯一的组ID
  18        SUM(is_new_group) OVER (PARTITION BY user_id ORDER BY created_at) AS group_id
  19    FROM
  20        status_changed
  21)
  22SELECT
  23    user_id
  24FROM
  25    grouped_orders
  26WHERE
  27    status = 'failed'
  28GROUP BY
  29    user_id, group_id
  30HAVING
  31    COUNT(*) >= 3
  32-- DISTINCT 是因为一个用户可能有多组连续失败
  33-- 如果只需要用户ID，用 DISTINCT；如果需要知道有多少组，则不需要
  34-- 或者直接在最外层 SELECT DISTINCT user_id
  35;

• 复杂度与索引：同解法 1。这种方法逻辑更直观，适用于更广泛的“状态变化”类问题。

解法 3：自连接（兼容老版本）

在没有窗口函数的旧版数据库（如 MySQL 5.7）中，自连接是一种备选方案，但通常性能较差且 SQL 语句更复杂。

• 版本：✅ 所有 SQL 数据库。
• 思路：对于 N=3 的情况，我们可以将表自连接 3 次，找到 3 条连续的失败记录。但“连续”的定义很棘手，需要确保两两之间没有其他记录。这通常需要使用 NOT EXISTS，性能很差。一个更可行的（但仍不推荐）思路是：找到一个失败记录 p1，并检查它后面的第 N-1（即第 2）条记录 p3 是否也是失败，且它们之间恰好有 N-2 条记录。
• SQL 代码 (以 N=3 为例)：
  sql

  ⧉⛶

   1-- 警告：此查询性能较差，且难以扩展到任意 N，仅作演示
   2SELECT DISTINCT p1.user_id
   3FROM
   4    payment_orders p1
   5JOIN
   6    payment_orders p2 ON p1.user_id = p2.user_id AND p1.created_at < p2.created_at
   7JOIN
   8    payment_orders p3 ON p2.user_id = p3.user_id AND p2.created_at < p3.created_at
   9WHERE
  10    p1.status = 'failed'
  11    AND p2.status = 'failed'
  12    AND p3.status = 'failed'
  13    -- 核心：确保 p1 和 p3 之间只有 p2 这一条记录
  14    AND NOT EXISTS (
  15        SELECT 1
  16        FROM payment_orders p_inner
  17        WHERE p_inner.user_id = p1.user_id
  18          AND p_inner.created_at > p1.created_at
  19          AND p_inner.created_at < p3.created_at
  20          AND p_inner.order_id <> p2.order_id
  21    );

• 复杂度与索引：复杂度很高，可能达到 $O(N^3)$ 或更高，NOT EXISTS 子查询是性能瓶颈。即使在 (user_id, created_at) 上有索引，性能也远不如窗口函数。

常见低分回答

1. 误用 GROUP BY：SELECT user_id FROM payment_orders WHERE status = 'failed' GROUP BY user_id HAVING COUNT(*) >= 3;
   • 错误原因：这只计算了用户总的失败次数，完全忽略了“连续”这一核心要求。
2. 脆弱的 ID 连续假设：... FROM t1 JOIN t2 ON t1.id + 1 = t2.id AND t1.id + 2 = t3.id
   • 错误原因：严重依赖自增 ID 是连续且无间断的，这在生产环境中几乎不可能保证（事务回滚、删除操作都会产生不连续的 ID）。必须使用时间戳或业务序号来排序。
3. 函数包裹列：WHERE DATE_FORMAT(created_at, '%Y-%m-%d') = '...'
   • 错误原因：在 WHERE 子句中对索引列使用函数，会导致索引失效，数据库引擎被迫进行全表扫描。应改为 WHERE created_at >= '...' AND created_at < '...' 的范围查询。
4. 不处理用户分区：ROW_NUMBER() OVER (ORDER BY created_at)
   • 错误原因：在窗口函数中忘记使用 PARTITION BY user_id，会导致对全表数据进行统一排序和编号，将不同用户的订单混在一起，逻辑完全错误。

工程实践与优化

• 数据量级：当订单表达到亿级或以上时，即使是窗口函数，即席查询也会非常慢，并消耗大量数据库资源。对于这种体量，应考虑：
  • 离线计算：使用 Spark SQL / Hive 等大数据工具，在 T+1 的批处理任务中计算出结果，存入结果表或数仓中。
  • 实时计算：如果需要实时或准实时地发现此类用户，应采用 Flink 等流计算引擎，在数据流中维护用户状态并实时检测连续失败模式。
• 索引策略：payment_orders 表的核心索引是 (user_id, created_at)。这完美匹配了窗口函数中的 PARTITION BY user_id ORDER BY created_at，能极大提升排序性能。如果查询条件还包括 status，可以考虑建立 (user_id, status, created_at) 索引。
• 执行计划分析：
  • 使用 EXPLAIN（或 EXPLAIN ANALYZE）检查窗口函数解法的执行计划。关键看 Extra 列是否显示 Using window function。同时，确认对 payment_orders 表的访问 type 是 ref 或 range，而不是 ALL（全表扫描）。
  • 对于自连接解法，EXPLAIN 会显示多次访问 payment_orders 表，并且 rows 的乘积会非常大，Extra 列可能出现 Using where; Using join buffer，这些都是性能不佳的信号。
• 避免大事务：此查询是只读的，通常不会锁表。但如果在一个长事务中执行，它会持有元数据锁和 MVCC 快照，可能导致 InnoDB 的 undo 日志增长，影响系统整体性能。建议在独立的、短的会话中执行。

常见追问与延伸题目

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

   • 回答要点：
     • 性能瓶颈：窗口函数解法的性能瓶颈在于排序 ($O(N \log N)$)。数据量增长 100 倍，执行时间会远超 100 倍，内存消耗也会剧增，数据库可能无法完成查询。
     • 架构优化：必须放弃即席查询。离线方案：将数据同步到数据湖/数据仓库（如 HDFS/S3），使用 Spark 或 Hive 进行分布式计算，利用其强大的横向扩展能力处理 PB 级数据。实时方案：引入 Flink 或 Spark Streaming，在订单数据产生时就进行处理。每个用户的状态（如连续失败次数）可以维护在 Flink 的 state 中，一旦达到阈值 N，立即触发下游告警或写入结果存储（如 Kafka、Redis）。

2. 追问：如何修改你的查询，来找出每个连续失败块的开始时间、结束时间和具体长度？

   • 回答要点：解法 1（Gaps and Islands）的 failure_groups CTE 已经为我们提供了完美的分组键 (user_id, group_key)。我们只需在该分组上进行聚合即可。
     sql

     ⧉⛶

      1-- 在解法1的 failure_groups CTE 基础上
      2SELECT
      3    user_id,
      4    COUNT(*) AS consecutive_failures,
      5    MIN(created_at) AS failure_start_time,
      6    MAX(created_at) AS failure_end_time
      7FROM
      8    failure_groups_with_time -- 稍作修改，把 created_at 传进来
      9GROUP BY
     10    user_id, group_key
     11HAVING
     12    COUNT(*) >= 3;

3. 追问：如果需求变成“查找 5 分钟内失败了 3 次的用户”，而不是“连续 3 次”，该如何实现？

   • 回答要点：这是一个滑动窗口问题，比连续序列问题更复杂。
     • 标准 SQL (PostgreSQL/Oracle)：可以使用支持 RANGE 子句的窗口函数。COUNT(*) OVER (PARTITION BY user_id ORDER BY created_at RANGE BETWEEN '5 minutes' PRECEDING AND CURRENT ROW)。这会计算当前行及之前 5 分钟内的总行数。我们可以筛选出 status = 'failed' 的行，并找到这个计数值大于等于 3 的地方。
     • MySQL 8.0+：MySQL 的窗口函数对 RANGE 支持有限，不支持时间间隔。因此，需要用自连接。FROM orders t1 JOIN orders t2 ON t1.user_id = t2.user_id AND t2.created_at BETWEEN t1.created_at AND t1.created_at + INTERVAL 5 MINUTE。然后对 t1 分组，计算 t2 的数量。这种自连接在数据量大时性能堪忧。
     • 最佳实践：同样，对于大数据量，这类问题是流计算引擎（如 Flink 的 Tumbling Windows 或 Sliding Windows）的典型应用场景。