SQL で連続区間を検出してグルーピングする
やりたいこと
例えば、下記のようなデータがあるとします。
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 | 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
*/
手順としては、
- 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 引数が返ります。 ↩︎
Discussion