中野智文のブログ

データ・マエショリストのメモ

BigQuery で最大最小が overlap しているものをまとめる(その最大最小を得る)

背景

最小と最大のペアの集合があるとする。

例えば、[最小, 最大]とすると、

[1, 2], [3, 4], [4, 5], [6, 7], [6, 8], [9, 10]

というような集合。

[3, 4], [4, 5]

は、まとめて、

[3, 5]

にしたい。

他にも、

[6, 7], [6, 8]

も、まとめて、

[6, 8]

にしたい。

最終的に、

[1, 2], [3, 5], [6, 8], [9, 10]

と出力したい。

つまり、ある要素の最大が、別の要素の最小値と同じかそれより大きい場合は、 その2つの要素を一つの要素にまとめたいということがある。

そのクエリ

WITH sample_data as (
  SELECT
    s.a AS a,
    s.z as z
  FROM (
    SELECT
      [
      STRUCT(1 as a, 2 AS z),
      STRUCT(3 as a, 4 AS z),
      STRUCT(4 as a, 5 AS z),
      STRUCT(6 as a, 7 AS z),
      STRUCT(6 as a, 8 AS z),
      STRUCT(9 as a, 10 AS z)
      ] _a)
  JOIN
  UNNEST(_a) s),
  w as (
  SELECT
    a,
    z,
    LAG(z) OVER (ORDER BY a, z) AS pre_z,
    LAG(a) OVER (ORDER BY z desc, a desc) AS post_a
  FROM sample_data
  ORDER BY a, z),
  head AS (
  SELECT DISTINCT
    a
  FROM
    w
  WHERE
    pre_z IS NULL OR
    a > pre_z),
  tail AS (
  SELECT DISTINCT
    z
  FROM
    w
  WHERE
    post_a IS NULL OR
    post_a > z),
  head_tail AS (
  SELECT
    a,
    MIN(z) AS z
  FROM
    head
  CROSS JOIN
    tail
  WHERE
    a <= z
  GROUP BY a
  ) --
--
SELECT
  *
FROM head_tail

解説

ウィンドウ関数を使って、並べた一つ上(もしくはひとつ下の)最大値(最小値)がその列の最小値より小さい(最大値より大きい)場合、まとめた要素の最小値(最大値)となる。