最近小红书讨论很火的一道SQL面试题，我用追赶指标法秒了

目录

一、引言

二、用追赶指标法解决动态长度孤岛与间隙问题

1.什么是孤岛与间隙算法？

1.1 核心定义

1.2 数学原理（行号差值法）

1.3 算法优势

2. 问题的本质

2.1 动态长度 vs 普通孤岛

2.2 核心原理：追赶指标法

2.2.1 核心假设

2.2.2 关键指标定义

2.2.3 逻辑推导

2.2.4 连续区间判定规则

2.2.5 算法步骤

三、分布实现

步骤 1：数据准备与基础指标计算

步骤 2：计算追赶指标（核心）

步骤 3：生成唯一分组 ID

步骤 4：分组聚合得到连续区间

完整SQL如下

四、算法优势与适用场景

核心优势

适用场景

总结与展望

一、引言

原文链接：【听说小红书SQL大佬很多，求帮我解这道题 – 一只子韵 | 小红书 – 你的生活兴趣社区】 😆 BsVXmGX9fDWbWQt 😆 https://www.xiaohongshu.com/discovery/item/696bb908000000002200878c?source=webshare&xhsshare=pc_web&xsec_token=AB-PpLZiSzbiyn3lpqKCn8kn08U45cvYlehyvP4pf7-TA=&xsec_source=pc_share

一张表有三列，uid，d，m
uid是用户id
d是充值会员的日期
m是充值了几个月会员
请写一段HiveSQL，计算会员连续时间段：uid，start_date，end_date
要求：不用UDF/UDAF，不允许穷举历史所有日期/月份记录，除了示例可能会再测几个输入要正确输出
示例输入：
uid d m
1 2025-01-01 2
1 2025-02-01 1
1 2025-05-01 1
1 2025-10-01 3
1 2025-11-01 1
2 2025-01-01 2
2 2025-02-01 2
2 2025-04-15 2
2 2025-06-20 2
示例输出：
uid start_date end_date
1 2025-01-01 2025-04-01
1 2025-05-01 2025-06-01
1 2025-10-01 2026-02-01
2 2025-01-01 2025-09-01 题目如上请用HiveSQL完成上述问题，且不能使用递归。在实际输出前需要构建你的思维链，仔细思考且检查无误后再输出

针对该问题引起了网友的广泛讨论，大家关注的点在于如何不使用递归的情况下完成该问题。

以下是网友的讨论：

如果大家关注了我的公众号，会发关于现该问题在我的专栏“SQL进阶实战技巧”，“SQL精要”中讲的比较多，此类问题连续区间合并问题或孤岛与间隙问题，解决此类问题的方法我们总结为状态标记法、断点分组法、水位线法等等，但今天这个问题有点特殊，它不像之前的连续问题，连续的长度是定值，而这个长度是动态的，我们将此类问题定义为：动态长度的孤岛与间隙问题，或动态长度的连续区间问题。

SQL进阶技巧：如何计算重叠区间合并问题？

3分钟学会SQL中的断点去重技术，轻松搞定连续相同状态数据去重问题？3分钟学会SQL中的流式状态分析技术，轻松搞定离散事件流处理问题

3分钟学会SQL中的序列分析技术，轻松搞定时间序列状态流转问题？

3分钟学会SQL中的断点分组技术，轻松搞定连续相同状态数据分组问题？

SQL进阶技巧：断点缝合问题【如何按照业务规则对相邻行数据进行合并】

在数仓开发中，「孤岛与间隙问题（Islands and Gaps）」是高频场景 —— 比如计算用户的连续会员有效期、连续登录天数等。但如果遇到动态长度的孤岛问题（比如会员充值的连续区间长度由累计充值月份动态决定，且支持乱序、重叠的充值记录），传统的递归 CTE 或穷举日期的方法就会遇到性能瓶颈或逻辑复杂的问题。

今天我要分享的追赶指标法，仅用窗口函数 + 聚合就能高效解决这类动态长度的孤岛问题，无需递归、无需穷举日期，性能更优且逻辑贴合业务语义。

二、用追赶指标法解决动态长度孤岛与间隙问题

1.什么是孤岛与间隙算法？

1.1 核心定义

孤岛与间隙算法是解决“有序数据集内连续区间识别”的经典算法，核心概念分为两类：

• 孤岛（Islands）：数据集按指定维度排序后，连续且满足业务规则的行集合（如用户连续的会员月份区间）；

• 间隙（Gaps）：两个孤岛之间的非连续间隔（如用户会员断档的时间段）。

该算法的核心目标是识别所有“孤岛”并聚合为连续区间，忽略间隙，最终输出每个孤岛的起止边界。

1.2 数学原理（行号差值法）

算法的核心逻辑基于“有序序列的行号与业务日期的同步性”：

假设数据集按业务日期排序后，为每行分配行号rn，对“业务日期 – rn×时间单位”计算结果（下称“锚点值”）：

• 若行属于同一孤岛（连续区间），则业务日期的增长速度与行号增长速度完全同步，锚点值保持不变；

• 若行属于不同孤岛（存在间隙），则业务日期的增长速度快于行号增长速度，锚点值发生变化。

以会员区间为例，时间单位为“月”，数学表达式为：

同一孤岛内所有行的anchor值相同，不同孤岛的anchor值不同，以此作为孤岛的唯一标识。

1.3 算法优势

2. 问题的本质

本题是一道动态长度的孤岛与间隙问题（岛屿长度由购买的月份数动态决定），核心需求：将用户的充值记录合并为连续的会员区间，即使充值记录乱序、重叠，也要正确合并。

2.1 动态长度 vs 普通孤岛

先明确动态长度孤岛问题的核心特点，和普通孤岛问题做个对比：

以会员充值场景为例：用户在 2025-01-01 充值 2 个月、2025-02-01 充值 2 个月、2025-04-15 充值 2 个月，这三条记录的有效期是重叠的，需要合并为2025-01-01 ~ 2025-09-01的连续区间 —— 这就是典型的动态长度孤岛问题。

2.2 核心原理：追赶指标法

追赶指标法的核心思想是通过 「时间推进速度」与「行为量累计速度」的追赶关系 ，动态识别连续区间。

2.2.1 核心假设

当业务行为连续无断档时，「时间推进的月数」与「累计充值的月数」完全同步；当行为断档时，时间推进的月数会大于累计充值的月数，两者的差值会发生跳变。

2.2.2 关键指标定义

我们定义「追赶指标」来量化这种同步关系：

Y = 日期的月索引−累计前序充值月份（不含当前记录）

月索引：将日期转换为「距离某一基准日期（如 1970-01-01）的月数」，把离散日期转为连续数值，便于数学计算。

累计前序充值月份：当前记录之前，用户已累计的充值月份数（不含当前记录的充值月数）。

2.2.3 逻辑推导

假设一个连续区间的起始日期为StartDate，该区间之前累计购买了M_prev个月。新记录如果属于当前区间，必须满足：

移项得到关键恒等式：

定义追赶指标：

日期月索引累计已购买月份不含当前​

• 若Y不变或变小 → 新购买在有效期内，属于同一区间；

• 若Y突然变大 → 日期超出累计有效期，产生间隙，开启新区间。

2.2.4 连续区间判定规则

• 连续区间：若Y保持不变或变小 → 说明当前充值发生在累计有效期内（时间推进速度 ≤ 行为量累计速度），属于同一连续区间。

• 断档区间：若Y突然变大 → 说明当前充值的日期超出了累计有效期（时间推进速度 > 行为量累计速度），产生了间隙，开启新的连续区间。

2.2.5 算法步骤

三、分布实现

以「会员充值记录合并为连续会员区间」为例，完整实现追赶指标法：

步骤 1：数据准备与基础指标计算

先计算每条记录的「月索引」和「累计前序充值月份」，为追赶指标提供基础。

WITH base_metrics AS (
   SELECT
      uid,
      d,
      m,
       — 将日期转为“距离1970-01-01的月数”，作为月索引（取整避免小数干扰）
      FLOOR(months_between(d, '1970-01-01')) AS month_index,
       — 计算当前记录之前（不含当前）的累计充值月份，第一行默认0
      COALESCE(
          SUM(m) OVER (PARTITION BY uid ORDER BY d ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING),
           0
      ) AS prev_m_sum
   FROM
      vip_log
)

步骤 2：计算追赶指标（核心）

用「月索引 – 累计前序充值月份」得到追赶指标，初步标记连续区间的断点。

, gap_detection AS (
   SELECT
      uid,
      d,
      m,
      month_index,
      prev_m_sum,
       — 核心追赶指标：判断时间与行为量的同步性
      (month_index – prev_m_sum) AS gap_val
   FROM
      base_metrics
)

步骤 3：生成唯一分组 ID

通过「累计最大值锁定组头」的方式，将同一连续区间的记录归为一组：

• 新的连续区间开始时，gap_val会跳变到一个新高值；

• 同一区间内后续记录的gap_val会因为累计前序月份增加而变小；

• 用MAX(gap_val) OVER()可以锁定组头的gap_val作为分组 ID，确保同一区间的记录拥有相同的分组 ID。

, group_generation AS (
   SELECT
      uid,
      d,
      m,
       — 累计最大值作为分组ID，锁定组头的gap_val
      MAX(gap_val) OVER (PARTITION BY uid ORDER BY d) AS group_id
   FROM
      gap_detection
)

步骤 4：分组聚合得到连续区间

按「用户 + 分组 ID」聚合，计算每个连续区间的起止日期：

• 起始日期：组内最早的充值日期；

• 结束日期：组内最早日期 + 组内累计充值月份（动态计算区间长度）。

SELECT
  uid,
  MIN(d) AS start_date,
   — 结束日期 = 组内最早日期 + 组内累计充值月份（动态长度）
  add_months(MIN(d), SUM(m)) AS end_date
FROM
  group_generation
GROUP BY
  uid,
  group_id
ORDER BY
  uid,
  start_date;

完整SQL如下

— =============================================
— 1. 创建测试表（会员充值记录表）
— =============================================
DROP TABLE IF EXISTS vip_log;
CREATE TABLE vip_log (
  uid INT COMMENT '用户ID',
  d STRING COMMENT '充值日期（格式：yyyy-MM-dd）',
  m INT COMMENT '单次充值月数'
)
ROW FORMAT DELIMITED
FIELDS TERMINATED BY '\\t'
STORED AS TEXTFILE
COMMENT '用户会员充值日志表';
​
— =============================================
— 2. 插入测试数据（覆盖乱序、重叠、断档场景）
— =============================================
INSERT INTO vip_log VALUES
— uid=1：有断档的场景
(1, '2025-01-01', 2),
(1, '2025-02-01', 1),
(1, '2025-05-01', 1),
(1, '2025-10-01', 3),
(1, '2025-11-01', 1),
— uid=2：重叠+跨日充值的场景（核心测试用例）
(2, '2025-01-01', 2),
(2, '2025-02-01', 2),
(2, '2025-04-15', 2),
(2, '2025-06-20', 2),
— uid=3：乱序充值的场景
(3, '2025-03-01', 3),
(3, '2025-01-01', 2),
(3, '2025-02-01', 2);
​
— =============================================
— 3. 核心逻辑：追赶指标法计算连续会员区间
— 优化点：日期标准化（转当月1号）、类型安全（取整）、去重
— =============================================
WITH
— 步骤1：数据预处理（去重+日期标准化）
preprocess AS (
   SELECT DISTINCT
      uid,
       — 日期标准化：转为当月1号，避免“日”对月索引的干扰
      TRUNC(TO_DATE(d), 'MM') AS recharge_date,
      m AS recharge_months
   FROM vip_log
),
— 步骤2：基础指标计算（月索引+累计前序充值月份）
base_metrics AS (
   SELECT
      uid,
      recharge_date,
      recharge_months,
       — 月索引：距离1970-01-01的月数（取整，避免小数干扰）
      FLOOR(MONTHS_BETWEEN(recharge_date, '1970-01-01')) AS month_index,
       — 累计前序充值月份：当前记录之前的总充值月数（不含当前）
      COALESCE(
          SUM(recharge_months) OVER (
              PARTITION BY uid
               ORDER BY recharge_date
              ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING
          ),
           0
      ) AS prev_m_sum
   FROM preprocess
),
— 步骤3：计算追赶指标（核心：判断连续/断档）
gap_detection AS (
   SELECT
      uid,
      recharge_date,
      recharge_months,
      month_index,
      prev_m_sum,
       — 追赶指标：月索引 – 累计前序充值月份
      (month_index – prev_m_sum) AS gap_val
   FROM base_metrics
),
— 步骤4：生成唯一分组ID（累计最大值锁定组头）
group_generation AS (
   SELECT
      uid,
      recharge_date,
      recharge_months,
       — 累计最大值作为分组ID，确保同一连续区间ID唯一
      MAX(gap_val) OVER (PARTITION BY uid ORDER BY recharge_date) AS group_id
   FROM gap_detection
)
— 步骤5：最终聚合（计算连续区间）
SELECT
  uid,
  MIN(recharge_date) AS start_date,  — 区间起始日期（组内最早充值日）
   — 区间结束日期：最早日期 + 组内累计充值月数（匹配业务预期）
  ADD_MONTHS(MIN(recharge_date), SUM(recharge_months)) AS end_date
FROM group_generation
GROUP BY uid, group_id
ORDER BY uid, start_date;

Doris SQL（2.1）

SELECT uid,
MIN(recharge_date) AS start_date,
add_months(to_date(MIN(recharge_date)), SUM(recharge_months)) AS end_date
FROM (
— group_generation层：生成唯一分组ID
SELECT uid,
recharge_date,
recharge_months,
— 累计最大值锁定组头作为分组ID
MAX(gap_val) OVER (PARTITION BY uid ORDER BY recharge_date) AS group_id
FROM (
— gap_detection层：计算追赶指标
SELECT uid,
recharge_date,
recharge_months,
month_index,
prev_m_sum,
(month_index – prev_m_sum) AS gap_val — 核心追赶指标
FROM (
— base_metrics层：基础指标计算（手动实现月索引）
SELECT uid,
recharge_date,
recharge_months,
— 手动计算月索引（替代months_between）：距离1970-01-01的总月数
(year(to_date(recharge_date)) – 1970) * 12 +
(month(to_date(recharge_date)) – 1) AS month_index,
— 累计前序充值月数（不含当前行），第一行默认0
COALESCE(
SUM(recharge_months) OVER (
PARTITION BY uid
ORDER BY recharge_date
ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING
),
0
) AS prev_m_sum
FROM (
SELECT DISTINCT uid,
date_format(to_date(d), '%Y-%m-01') AS recharge_date,
m AS recharge_months
FROM vip_log
) preprocess
) base_metrics
) gap_detection
) group_generation
GROUP BY uid, group_id
ORDER BY uid, start_date;

结果如下：

四、算法优势与适用场景

核心优势

适用场景

• 会员 / 订阅类连续有效期计算（如本文示例）

• 按时间维度的「购买 – 消耗」连续区间识别

• 连续消费、连续登录等行为的连续区间计算

• 设备租赁、工单处理等动态长度的连续场景

总结与展望

追赶指标法是解决动态长度孤岛与间隙问题的高效方案，它通过「时间与行为量的追赶关系」动态识别连续区间，无需递归、无需穷举日期，性能与业务贴合度都更优。

除了会员充值场景，该算法还可以扩展到连续登录、连续消费、设备在线状态等场景。如果你有其他解决动态孤岛问题的思路，欢迎在评论区交流～

往期精彩

面试提问：如何进行指标梳理？具体从哪些方式展开

面试提问：一个新的业务如何设计数据域？

面试提问：数仓中DWD层建设最大困难是什么？

数仓之DWB层完整设计方案与实战

数据开发：如何深入理解业务并高于业务视角？

SQL腾讯面试真题：玩家战败场次中点位占领统计问题

共享单车用户行为分析

用领域驱动设计（DDD）构建业务对齐的数仓数据模型

技术实战：基于 RFM 模型识别低价值用户并追踪其最后一次下单餐厅

如何从多源业务表对商家进行综合评估？