ギャップ・アンド・アイランド(Gaps and Islands)問題

SQLにおいてたまに出くわす典型問題たち

普段Pythonなどのスクリプト言語を使うことに慣れていると簡単にできることでも、SQLだと少し処理の仕方を考えてあげなくてはならないような典型的な問題がいくつかあります。

たとえば、SQLは GROUP BY を使うことで値に基づいたグルーピングを行うのは得意ですが、「連続していること」のような状態を扱うのは苦手だったりします。

今回扱う ギャップ・アンド・アイランド (Gaps and Islands) 問題 はまさにその特徴を踏まえて対応する必要がある問題の1つです。 (実はそんな名前があると知りませんでしたが、生成AIさんにこの問題には名前があると最近教えて貰いました…)

パッと見た感じ簡単そうですが、なかなか解けない経験をした方もいらっしゃるかもしれません。

ギャップ・アンド・アイランド (Gaps and Islands) 問題とは

では早速、ギャップ・アンド・アイランド問題について説明します。

ギャップ・アンド・アイランド問題とは、連続した期間での集計を行う問題です。

ギャップ: 連続していない期間
アイランド: 連続している期間

ということで、 「アイランド」の部分を一つのレコードにまとめていきたい… ということです。

連続してログインした日数の計算 などに使えます。

たまには放送業界の会社であることを踏まえた例を出すと、 番組表データ などでも頻出します。

5分おきに番組情報が入っているテーブル があったとしましょう。

その中で、20:00〜21:30 のバラエティ番組で、20:55〜21:00 の間はニュースが入っているとします。

すると、データとしては下記のようになります。

このとき、迂闊に program_name で MIN および MAX をとって番組放送時間をとってしまうと、それらの差から番組尺の長さを計算したりした際に5分の誤差を生じさせてしまう原因になり得ます。

なので、理想的にはこのテーブルから番組情報をサマライズする場合は、きちんと間の番組を抜いた時刻でまとめて

このような形を作りたいところです。

ギャップ・アンド・アイランド問題の解法

そのようなギャップ・アンド・アイランド問題を解く場合はどのようにすべきかというと、まず、連続性の検証から行っていきます。

LAGを使って連続性を検証する

連続性の検証に欠かせないのが LAG関数 です。一個上の行の値を引っ張ってくる…というものですね。

たとえば先ほどの例だと、

  SELECT *,
    LAG(end_time) OVER (ORDER BY start_time) AS prev_end_time,
    LAG(program_name) OVER (ORDER BY start_time) AS prev_program_name
  FROM raw_data

とすれば

このようなテーブルが得られます。

start_time と prev_end_time が一致していて、かつ、 prev_program_name が一致している場合は連続と見なせるわけですね。

このデータをもとに、各データをグループに仕分けていくことになります。

ウィンドウ関数としての SUM を使ってグループ化する

先ほどの条件をもとに、連続でない場合に「1」連続な場合に「0」とした上で、

ウィンドウ関数としてのSUM関数 を利用してグルーピングを行います。

WITH with_lag AS (
  SELECT *,
    LAG(end_time) OVER (ORDER BY start_time) AS prev_end_time,
    LAG(program_name) OVER (ORDER BY start_time) AS prev_program_name
  FROM raw_data
),
SELECT *,
  SUM(
    CASE
      WHEN start_time = prev_end_time AND program_name = prev_program_name THEN 0
      ELSE 1
    END
  ) OVER (ORDER BY start_time ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS grp
FROM with_lag

こうすることで、今ある行までの和をレコードとして保持できるようになります。

SUMのような関数には、 GROUP BY で集計を行う 集約関数(Aggregate Function) と、このような ウィンドウ関数 で同じ関数名ですが2種類の使い方があることに注意が必要です。

(このあたりはかなり初学者が詰まりやすいポイントだと思います)

GROUP BY による集約を行う

ここまでくれば、あとはこのグループIDをもとに集約を行えば良い、ということになります。

MAX関数および MIN関数を使って集計してみます。

WITH with_lag AS (
  SELECT *,
    LAG(end_time) OVER (ORDER BY start_time) AS prev_end_time,
    LAG(program_name) OVER (ORDER BY start_time) AS prev_program_name
  FROM raw_data
),
with_grp AS (
  SELECT *,
    SUM(
      CASE
        WHEN start_time = prev_end_time AND program_name = prev_program_name THEN 0
        ELSE 1
      END
    ) OVER (ORDER BY start_time ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS grp
  FROM with_lag
)
SELECT
  MIN(start_time) AS start_time,
  MAX(end_time) AS end_time,
  program_name
FROM with_grp
GROUP BY program_name, grp

これによって目的の結果が得られることが確認出来ました！

このように、 段階を踏んで考えることが重要な問題 と言えますね。

まとめ

今回はSQLで解く際に特有の考え方を必要とする「ギャップ・アンド・アイランド問題」について扱いました。

このような問題は実際に直面して解いた経験があれば簡単に解けるようになっていきますが、特に初学者、かつ、スクリプト言語などに慣れている場合は簡単そうで難しくて面喰らうことが多いのではないでしょうか。

一方で、ウィンドウ関数と集約関数の違いなど、やや発展的なSQLの内容について理解する場合はとても良い題材かもしれません。

今は生成AIに助けて貰うと一気に解いて貰うこともできますが、たまにはじっくり段階を踏んで考えてみるのも良いのではないでしょうか。