Yabu.log

ITなどの雑記

プログラマのためのSQL 読書会(31)に参加

今回は普段の会議室が取れなかったとかで和室でした。

プログラマのためのSQL 第4版

プログラマのためのSQL 第4版

32. 11 オーバーラップする被覆

期間(開始,終了)を扱うようなテーブルで、被覆していて切れ目のない範囲を抽出したいという趣旨のクエリです。

データ

CREATE TABLE Intervals
(x INTEGER NOT NULL,
 y INTEGER NOT NULL,
     CHECK (x <= y),
     PRIMARY KEY (x, y));

---

INSERT INTO Intervals
VALUES (1, 3),(2, 5),(4, 11),
       (10, 12), (20, 21),
       (120, 130), (120, 128), (120, 122),
       (121, 132), (121, 122), (121, 124), (121, 123),
       (126, 127);

実行結果

min_x max_y
1 12
20 21
120 132

例のごとく、何パターンも紹介されていますが、そのうち1つにpostgreSQLだけ実行結果が違うものがありました。

--パターン1:ディーター・ネース のウィンドウ 関数を使ったクエリ
SELECT min_x, MAX(y)
  FROM (SELECT x, y,
               MAX(CASE WHEN x <= MAX_Y THEN NULL ELSE x END)
                 OVER (ORDER BY x, y
                       ROWS UNBOUNDED PRECEDING) AS min_x
          FROM (SELECT x, y,
                       MAX(y)
                         OVER(ORDER BY x, y
                              ROWS BETWEEN UNBOUNDED PRECEDING
                                       AND 1 PRECEDING) AS max_y
                  FROM Intervals) AS DT) AS DT
 GROUP BY min_x;

---パターン2:自己 結合と3レベルの相関サブクエリを使うクエリ


SELECT I1.x, MAX(I2.y) AS y
  FROM Intervals AS I1
         INNER JOIN
           Intervals AS I2
    ON I2.y > I1.x
 WHERE NOT EXISTS
         (SELECT *
            FROM Intervals AS I3
           WHERE I1.x - 1 BETWEEN I3.x AND I3.y)
             AND NOT EXISTS
         (SELECT *
            FROM Intervals AS I4
           WHERE I4.y > I1.x
             AND I4.y < I2.y
             AND NOT EXISTS
                  (SELECT *
                     FROM Intervals AS I5
                    WHERE I4.y + 1 BETWEEN I5.x AND I5.y))
 GROUP BY I1.x;


--パターン3:サブクエリ の 代わりに左外部半結合を使ったクエリ
SELECT I1.x, MAX(I2.y) AS y
  FROM Intervals AS I1
         INNER JOIN
           Intervals AS I2
             ON I2.y > I1.x
               LEFT OUTER JOIN
                 Intervals AS I3
                   ON I1.x - 1 BETWEEN I3.x AND I3.y
                     LEFT OUTER JOIN
                       (Intervals AS I4
                          LEFT OUTER JOIN
                            Intervals AS I5
                              ON I4.y + 1 BETWEEN I5.x AND I5.y)
                      ON I4.y > I1.x
                     AND I4.y < I2.y
                     AND I5.x IS NULL
 WHERE I3.x IS NULL
   AND I4.x IS NULL
 GROUP BY I1.x;

---パターン4:トニー・アンドリュースのクエリ

SELECT Starts.x, Ends.y
  FROM (SELECT x, ROW_NUMBER() OVER(ORDER BY x) AS rn
          FROM (SELECT x, y,
                       LAG(y) OVER(ORDER BY x) AS prev_y
                  FROM Intervals) AS Foo
                 WHERE prev_y IS NULL
                    OR prev_y < x) AS Starts,
       (SELECT y, ROW_NUMBER() OVER(ORDER BY y) AS rn
          FROM (SELECT x, y,
                       LEAD(x) OVER(ORDER BY y) AS next_x
                  FROM Intervals) AS Boo
         WHERE next_x IS NULL
           OR y < next_x) AS Ends
 WHERE Starts.rn = Ends.rn;

このパターン4のクエリのみ実行結果が違って出ます。

  x  |  y  
-----+-----
   1 |  12
  20 |  21
 120 | 124

ご覧の通り最後の被覆範囲が(120,132)ではなく(120 ,124)と出てしまいました。