📦

SQL で連続区間を検出してグルーピングする

2022/04/19に公開

やりたいこと

例えば、下記のようなデータがあるとします。

user_id login_date
1 2022-01-01
1 2022-01-02
1 2022-01-03
1 2022-01-11
1 2022-01-13
1 2022-01-14
2 2022-01-01
2 2022-01-03
2 2022-01-04

ここで login_date にはユニーク制約がある (値が重複しない) とします。

このデータについて、下記のように「user_id ごとに連続ログイン区間それぞれの開始日と終了日を取得したい」場合、どうしたらいいでしょうか。

user_id start_date end_date
1 2022-01-01 2022-01-03
1 2022-01-11 2022-01-11
1 2022-01-13 2022-01-14
2 2022-01-01 2022-01-01
2 2022-01-03 2022-01-04

TL;DR

あるカラムの値が連続する区間は、行番号と前行差分の積算合計の差を取ることで検出できます。

上記を変形して、一定のルールに沿って同一グループかどうかを判定して 10 を返す式が記述できれば、上記を応用して任意のルールでグルーピングすることができます。

解答

user_id ごとに連続ログイン区間それぞれの開始日と終了日を取得したい」という仕様を満たすためには、user_id ごとに連続する login_date 値ごとにグルーピング (集約) する必要があります。

「連続区間でグルーピングする」場合、自分は下記のどちらかの方法を取ります。

1. 起点からの差分でグルーピングする

特定の日付や番号、もしくはパーティション (この例では user_id) 内の最小値を起点として、そこからの差分でグルーピングします。

具体的には、

  1. 行番号を振る
  2. 起点からの差分を計算する
  3. 行番号と起点差分の差でグルーピングする

という形となります。

例えば「すべてのデータが連続である」とすると、起点からの差分はすべて 1 ずつ増加していくことになり、これは行番号と同じ間隔になります。

user_id login_date 行番号 起点差分
1 2022-01-01 1 0
1 2022-01-02 2 1
1 2022-01-03 3 2

すなわち、連続であり続ける限り、下記のように行番号と起点差分の差は同じ値となります。

user_id login_date 行番号 起点差分 左 2 つの差
1 2022-01-01 1 0 1
1 2022-01-02 2 1 1
1 2022-01-03 3 2 1

ここで連続でない値が出現すると、そこで「行番号と起点差分の差」がズレる形となり、そのズレはそれ以降の行にも残り続けます。

user_id login_date 行番号 起点差分 左 2 つの差
1 2022-01-01 1 0 1
1 2022-01-02 2 1 1
1 2022-01-03 3 2 1
1 2022-01-11 4 10 -6
1 2022-01-12 5 11 -6

この特性を利用して、連続区間でのグルーピングをすることができます。

下記は Snowflake で上記を実装したクエリの例です。

create or replace table logins (user_id int, login_date date) as
select *
from values
    (1, '2022-01-01'),
    (1, '2022-01-02'),
    (1, '2022-01-03'),
    (1, '2022-01-11'),
    (1, '2022-01-13'),
    (1, '2022-01-14'),
    (2, '2022-01-01'),
    (2, '2022-01-03'),
    (2, '2022-01-04')
;

with
logins_numbered as (
    select *, row_number() over (partition by user_id order by login_date asc) rn
    from logins
),
first_logins as (
    select user_id, min(login_date) first_login_date
    from logins
    group by user_id
)
select
    l.user_id,
    min(l.login_date) start_date,
    max(l.login_date) end_date
from logins_numbered l
join first_logins f using (user_id)
group by user_id, l.rn - datediff(day, f.first_login_date, l.login_date)
order by user_id, l.rn - datediff(day, f.first_login_date, l.login_date)
;
/*
USER_ID    START_DATE    END_DATE
1    2022-01-01    2022-01-03
1    2022-01-11    2022-01-11
1    2022-01-13    2022-01-14
2    2022-01-01    2022-01-01
2    2022-01-03    2022-01-04
*/

手順としては、

  1. CTE logins_numberedROW_NUMBER 関数を使用して行番号 rn を振る
  2. CTE first_loginsMIN 関数を使用して、パーティション user_id ごとの起点 first_login_date を取得する
  3. DATEDIFF 関数で起点 first_login_date とその行の時刻 login_date の差分を取り、さらに rn との差を計算し、その値とパーティション user_idGROUP BY する

という形になります。

ちなみに、今回は行番号が振られていないため ROW_NUMBER 関数を使用して振っていますが、元々連番の ID や行番号のカラムがあるのであれば、そちらを使用するのが簡単です。

2. 前行差分の積算合計でグルーピングする

別解として、前行との差分からでもグルーピングすることができます。

具体的には、

  1. 行番号を振る
  2. 前行との差分を計算する (連続値のときに 1 になるように調節する)
  3. 上記前行差分の積算合計 (running total) を計算する
  4. 行番号と前行差分の積算合計の差でグルーピングする

という形になります。

例えば「すべてのデータが連続である」とすると、前行差分はすべて 1 になります。最初の行は便宜上 1 とします。

user_id login_date 行番号 前行差分
1 2022-01-01 1 1
1 2022-01-02 2 1
1 2022-01-03 3 1

そのため、前行差分の積算合計 (running total: その行までの値の合計) を計算すれば、行番号と一致します。

user_id login_date 行番号 前行差分 左の積算合計 行番号と積算合計の差
1 2022-01-01 1 1 1 0
1 2022-01-02 2 1 2 0
1 2022-01-03 3 1 3 0

ここで連続でない値が出現すると、積算合計もズレる形となり、そのズレはそれ以降の行にも残り続けます。

user_id login_date 行番号 起点差分 左の積算合計 行番号と積算合計の差
1 2022-01-01 1 1 1 0
1 2022-01-02 2 1 2 0
1 2022-01-03 3 1 3 0
1 2022-01-11 4 8 9 5
1 2022-01-12 5 1 10 5

この特性を利用して、連続区間でのグルーピングをすることができます。

下記は Snowflake で上記を実装したクエリの例です。

with
logins_numbered as (
    select *, row_number() over (partition by user_id order by login_date asc) rn
    from logins
),
logins_diff as (
    select
        *,
        coalesce(datediff(
            day,
            lag(login_date) over (partition by user_id order by rn asc),
            login_date
        ), 1) diff
    from logins_numbered
),
logins_bucketed as (
    select *, rn - sum(diff) over (partition by user_id order by rn asc) bucket
    from logins_diff
)
select
    user_id,
    min(login_date) start_date,
    max(login_date) end_date
from logins_bucketed
group by user_id, bucket
order by user_id, start_date, end_date
;

/*
USER_ID    START_DATE    END_DATE
1    2022-01-01    2022-01-03
1    2022-01-11    2022-01-11
1    2022-01-13    2022-01-14
2    2022-01-01    2022-01-01
2    2022-01-03    2022-01-04
*/

手順としては、

  1. CTE logins_numberedROW_NUMBER 関数を使用して行番号を払い出す
  2. CTE logins_diffDATEDIFF 関数に LAG 関数で取得した前行の login_date と現在行の login_date を渡すことで前行差分を計算する
    • 最初の行では LAG 関数が NULL を返すため、DATEDIFF 関数の結果も NULL になるので、COALESCE 関数で 1 にする
  3. CTE log_bucketed で行番号と SUM ウィンドウ関数で計算した diff の積算合計の差を取ってグループ番号 bucket を払い出す
  4. パーティション user_id とグループ番号 bucketGROUP BY する

という形になります。

応用: 変化点で区切ってグルーピングする

ここまでは「前後の差分が数値として計算できる」かつ「連続」の場合のみを考えていましたが、例えば、

  • 重複値も連続とみなしてグルーピングしたい
  • 1 日空いても連続であるとみなしてグルーピングしたい
  • 文字列値の連続区間でグルーピングしたい

などのケースは、「差分が 1 になる」という特性を活かすことができないため、少し工夫が必要になります。

ここで有効なのが 2. の「前行差分の積算合計でグルーピングする」パターンです。

このパターンでは、

  • 連続区間では常に 1 が返る
  • 不連続になるところ (変化点) で 1 以外の値が返って積算合計が行番号とズレる

という特性を利用しています。

そのため、

  • 前行と比較して同一グループであれば 1 を返す
  • そうでなければで 0 を返す

ような式を記述して、その積算合計を使用すれば、任意のルールでグルーピングすることができることになります。


例えば、「重複値も連続とみなしてグルーピングしたい」ケースを考えると、2. のサンプルクエリの DATEDIFF 関数で差分を取得する式を拡張して、「差分が 1 以下だったら 1 を返す」ようにすることで実現することができます。

with
logins_numbered as (
    select *, row_number() over (partition by user_id order by login_date asc) rn
    from logins
),
logins_diff as (
    select
        *,
        datediff(
            day,
            lag(login_date) over (partition by user_id order by rn asc),
            login_date
        ) diff,
        iff(diff > 1, 0, 1) is_contiguous
    from logins_numbered
),
logins_bucketed as (
    select *, rn - sum(is_contiguous) over (partition by user_id order by rn asc) bucket
    from logins_diff
)
select
    user_id,
    min(login_date) start_date,
    max(login_date) end_date
from logins_bucketed
group by user_id, bucket
order by user_id, start_date, end_date
;

/*
USER_ID    START_DATE    END_DATE
1    2022-01-01    2022-01-03
1    2022-01-11    2022-01-11
1    2022-01-13    2022-01-14
2    2022-01-01    2022-01-01
2    2022-01-03    2022-01-04
*/

diff 直接ではなく、diff を元に IFF 関数で分類した is_contiguous の積算合計を取ることで、重複値のケアをしています。

ここで iff(diff <= 1, 1, 0) ではなく iff(diff > 1, 0, 1) とすることで、diffNULL になる最初の行も 1 に分類することができます[1]。意味的にも「変化点のみを 0 にする」という形になり、わかりやすいかと思います。

「1 日空いても連続であるとみなしてグルーピングしたい」というケースもまったく同じで、ただ IFF 関数の条件を diff > 2 に変えるだけです。

with
logins_numbered as (
    select *, row_number() over (partition by user_id order by login_date asc) rn
    from logins
),
logins_diff as (
    select
        *,
        datediff(
            day,
            lag(login_date) over (partition by user_id order by rn asc),
            login_date
        ) diff,
        iff(diff > 2, 0, 1) is_contiguous
    from logins_numbered
),
logins_bucketed as (
    select *, rn - sum(is_contiguous) over (partition by user_id order by rn asc) bucket
    from logins_diff
)
select
    user_id,
    min(login_date) start_date,
    max(login_date) end_date
from logins_bucketed
group by user_id, bucket
order by user_id, start_date, end_date
;

/*
USER_ID    START_DATE    END_DATE
1    2022-01-01    2022-01-03
1    2022-01-11    2022-01-14
2    2022-01-01    2022-01-04
*/

上記と同様に「文字列値の連続区間でグルーピングしたい」ケースも考えられます。

例えば、下記のようなデータがあったとします。

message log_date
success 2022-01-01
success 2022-01-02
failure 2022-01-03
success 2022-01-04
failure 2022-01-05
failure 2022-01-06

このデータについて「同じ message が継続した区間それぞれの開始日と終了日を取得したい」場合、下記のように実装することができます。

create or replace table log (message varchar, log_date date) as
select *
from values
    ('success', '2022-01-01'),
    ('success', '2022-01-02'),
    ('failure', '2022-01-03'),
    ('success', '2022-01-04'),
    ('failure', '2022-01-05'),
    ('failure', '2022-01-06')
;

with
log_numbered as (
    select *, row_number() over (order by log_date asc) rn
    from log
),
log_contiguous as (
    select *, iff(coalesce(lag(message) over (order by rn), message) = message, 1, 0) is_contiguous
    from log_numbered
),
log_bucketed as (
    select *, rn - sum(is_contiguous) over (order by rn asc) bucket
    from log_contiguous
)
select
    message,
    min(log_date) start_date,
    max(log_date) end_date
from log_bucketed
group by message, bucket
order by start_date
;

/*
MESSAGE    START_DATE    END_DATE
success    2022-01-01    2022-01-02
failure    2022-01-03    2022-01-03
success    2022-01-04    2022-01-04
failure    2022-01-05    2022-01-06
*/

手順としては、

  1. CTE log_contiguousIFF 関数を使用して LAG 関数で取得した前行の message と現在行の message が同一かを確認し、同一であれば 1、異なる値であれば 0 を返す (is_contiguos 式)
    • 最初の行では LAG 関数が NULL を返すので、便宜上「それまでも連続していた」という扱いで 1 を返すように、現在行の message 同士で比較する形にする (常に true)
  2. CTE log_bucketedROW_NUMBER 関数で払い出した行番号と SUM ウィンドウ関数で計算した is_contiguos の積算合計の差を取ってグループ番号 bucket を払い出す
  3. message とグループ番号 bucketGROUP BY する

となり、差分ではなく、同値性チェックで 0/1 を返す式を使用している点を除けば、2. の例とまったく同じとなります。

まとめ

1 の方法のほうがシンプルに記述することができますが、基本的には対象列がユニークかつ連続である場合にしか使えないため、いろいろな連続条件を試しながらデータマイニングしたい場合には、2 の方法のほうが書き換えが聞きやすいので使いやすいと思います。

何かもっといい方法がある、という方は教えてもらえるとうれしいです。

Appendix: 練習問題

すべて LeetCode Premium のサブスクリプションが必要な問題ですが、特に "Report Contiguous Dates" はいい問題なのでオススメです。

脚注
  1. IFF 関数は、第 1 引数が TRUE のときに第 2 引数の値を返し、FALSE または NULL のときに第 3 引数の値を返すので、diffNULL のときは diff > 1NULL になり第 3 引数が返ります。 ↩︎

Discussion