📦

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

2022/04/19に公開

SQL

Snowflake

DataEngineering

tech

やりたいこと

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

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

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

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

解答

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

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

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

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

具体的には、

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

という形となります。

例えば「すべてのデータが連続である」とすると、起点からの差分はすべて 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
*/

手順としては、

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

という形になります。

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

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

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

具体的には、

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

という形になります。

例えば「すべてのデータが連続である」とすると、前行差分はすべて 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
1	2022-01-02	2	1	2
1	2022-01-03	3	1	3

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

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
*/

手順としては、

CTE logins_numbered で ROW_NUMBER 関数を使用して行番号を払い出す
CTE logins_diff で DATEDIFF 関数に LAG 関数で取得した前行の login_date と現在行の login_date を渡すことで前行差分を計算する
- 最初の行では LAG 関数が NULL を返すため、DATEDIFF 関数の結果も NULL になるので、COALESCE 関数で 1 にする
CTE log_bucketed で行番号と SUM ウィンドウ関数で計算した diff の積算合計の差を取ってグループ番号 bucket を払い出す
パーティション user_id とグループ番号 bucket で GROUP 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) とすることで、diff が NULL になる最初の行も 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
*/

手順としては、

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

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

まとめ

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

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

Appendix: 練習問題

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

Report Contiguous Dates - LeetCode (Hard)
Consecutive Numbers - LeetCode (Medium)
Find the Start and End Number of Continuous Ranges - LeetCode (Medium)

脚注

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

やりたいこと

TL;DR

解答

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

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

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

まとめ

Appendix: 練習問題

Discussion