Gaps and Islands:把連續區間抓出來

· tech

#sql#data-engineering

Window function 學會之後,這篇是它最漂亮的一個實戰。「連續登入幾天」「把連續的日期收成一段段區間」「找出序號的斷點」——這些看起來各不相同的需求,其實是同一個經典題:gaps and islands(缺口與島)。名字聽起來嚇人,但有一招優雅到會讓你「喔!」出聲的解法。

什麼是 gaps and islands

先把畫面建立起來。把一串有序的資料(日期、序號)攤在時間軸上,連續的一段就是一座「島」(island),島跟島中間的空缺就是「缺口」(gap):

島 A:連 3 天 島 B:連 2 天 島 C:1 天 缺口 缺口 7/1 7/3 7/7 7/12 日期 →
目標:把散落的連續點,收合成一座座「島」(例如算出每段連續登入的起訖與天數)。難的地方是——SQL 沒有現成的「連續」概念,你得自己造一個

招式一:value − ROW_NUMBER 的魔法

最優雅的解法只有一個念頭:連續的值每次 +1,而 ROW_NUMBER 也每次 +1,所以「值 − row_number」在同一座島裡會是固定的常數;一遇到缺口,值跳了、row_number 沒跳,差就變了。那個常數,就成了島的身分證:

value ROW_NUMBER value − rn 島 110A 220A 330A 743B 853B 1266C value − ROW_NUMBER 在同一島內固定不變 → GROUP BY 它,就把每座島切出來
連續值 +1、row_number 也 +1,兩者相減在同一島內是常數(0、3、6);缺口讓它跳號。這個常數就是「島 id」——GROUP BY 它即可

翻成 SQL,把連續登入的日期收成一段段區間:

SELECT user_id, MIN(login_date) AS start_date, MAX(login_date) AS end_date, COUNT(*) AS days
FROM (
  SELECT user_id, login_date,
         login_date - (ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date))::int AS grp
  FROM logins
) t
GROUP BY user_id, grp;   -- grp 就是那個「島 id」:同一段連續日期,grp 相同

login_date − row_number 在同一段連續日期裡會是同一個日期(常數),斷一天就跳掉。GROUP BY user_id, grp 一下去,每座島就收成一列,MIN/MAX 給你起訖、COUNT 給你天數。

招式二:LAG 抓斷點 + 累計加總(更通用)

差值法很美,但它有前提:「連續」必須是嚴格的 +1。如果你的「連續」定義比較鬆(例如「隔不到 3 天就算同一段」「同一個 session 內」),就用更通用的第二招——LAG 比對前一列抓出斷點,再用累計加總把斷點編號:

SELECT user_id, MIN(login_date) AS start_date, MAX(login_date) AS end_date
FROM (
  SELECT user_id, login_date,
         SUM(is_new) OVER (PARTITION BY user_id ORDER BY login_date) AS island
  FROM (
    SELECT user_id, login_date,
           CASE WHEN login_date - LAG(login_date) OVER (PARTITION BY user_id ORDER BY login_date) > 1
                THEN 1 ELSE 0 END AS is_new     -- 跟前一筆差超過 1 天 → 新島開始
    FROM logins
  ) a
) b
GROUP BY user_id, island;

三層拆開看:最內層用 LAG 跟前一筆比,超過門檻就標 is_new = 1(新島的第一天);中層用累計 SUM把這些旗標加起來——每遇到一個新島 +1,於是 island 就成了 1、1、1、2、2、3…的島 id;外層 GROUP BY 它收成區間。門檻(> 1)想放多鬆就多鬆,這是它比差值法通用的地方。

反思

換一個表示法,難題就消失了

value − row_number 這招之所以讓我著迷,是它示範了一件事:很多難題不是解法難,是你用錯了表示法。 「連續」這個性質,直接在 SQL 裡很難表達(沒有 IS CONSECUTIVE 這種東西);但你只要把它轉換成「一個固定的常數」,難題立刻塌縮成一個再普通不過的 GROUP BY。這種「找到對的表示法,問題就自己解開」的體驗,是我覺得寫 SQL——其實是所有分析型思考——最爽的時刻。遇到卡住的問題,我現在會先退一步問:「有沒有辦法把這個怪性質,換成一個我已經會處理的東西?」

優雅的解法要認得出它的前提

差值法很漂亮,但只在「嚴格 +1」時成立;真實資料常常沒那麼乖(跨週末、容忍幾天、不規則的 session)。這時硬套差值法就會出錯,得換成 LAG + 累計加總那招——醜一點,但門檻可調、通吃各種「連續」定義。這讓我學到:優雅的解法通常有嚴格的前提,用之前要先確認前提成立。 工程上我的判斷很簡單——先問「我的連續是不是嚴格 +1」,是就用差值法的優雅,不是就用 LAG 的通用。選哪招,看資料的形狀,不看哪招比較炫。

認得出 pattern,比會寫更值錢

Gaps and islands 最難的往往不是寫,是認出來——「連續在線的時段」「把相鄰的相同狀態合併成一段」「找出中斷的序號」表面看八竿子打不著,骨子裡全是同一題。認得出這個 pattern,你就能直接套招,而不是每次從零硬幹、還未必寫對。這也是為什麼我把它獨立成一篇:window function 的價值,一半在「會用」,一半在「認得出什麼問題該用它」。把常見的問題形狀記進腦子,遇到時就從『重新發明』變成『套用』——這是我覺得資料工程功力進階最實在的一步。