相関サブクエリで行と行を比較する

集合指向言語としてのSQL：その3

オーバーラップする期間を調べる

　ホテルや旅館の予約状況を表す、次のようなテーブルを考えます。

Reservations

宿泊客（reserver）	投宿日（start_date）	出発日（end_date）
木村	2006/10/26	2006/10/27
荒木	2006/10/28	2006/10/31
堀	2006/10/31	2006/11/01
山本	2006/11/03	2006/11/04
内田	2006/11/03	2006/11/05
水谷	2006/11/06	2006/11/06

　部屋番号がありませんが、ある1室についての部分を抜き出したものと考えてください。さて、当然のことながら、同日の同じ部屋に2組以上の客が泊まることはできません。ところが、この予約状況を見ると、ダブルブッキングになっている期間が存在します。棒グラフにしてみるとよく分かります。

 

　これは問題です。すぐに部屋割の変更をせねばなりません。今回の問題は、宿泊期間がオーバーラップしている客をリストアップするというものです。

　では、まず期間が重なるパターンを分類しましょう。するとまず、以下の3つのケースが挙げられます。

パターン

　例えば、堀氏から荒木氏を見た場合は（1）に該当しますし、逆に荒木氏から堀氏を見れば（2）に該当します。また、山本氏は内田氏に完全に含まれるので、（3）のケースに該当します。従って、この3つの条件のいずれかに該当する宿泊客を選択すればよい、ということになります。しかも、少し考えると、（3）のケースは考えなくてよいことが分かります。というのも、（3）を満たすということは、（1）と（2）を共に満たしていることと同値だからです。

　従って、必要十分条件は（1）と（2）の少なくともどちらかを満たしていること。答えはこうです。

オーバーラップする期間を求める

SELECT reserver, start_date, end_date
  FROM Reservations R1
 WHERE EXISTS
       (SELECT *
          FROM Reservations R2
         WHERE R1.reserver <> R2.reserver  --自分以外の客と比較する
           AND ( R1.start_date BETWEEN R2.start_date AND R2.end_date
                                   --条件(1)：開始日が他の期間内にある
              OR R1.end_date  BETWEEN R2.start_date AND R2.end_date));
                                   --条件(2)：終了日が他の期間内にある

結果

reserver    start_date    end_date
----------  ------------  ----------
荒木        2006/10/28    2006/10/31
堀          2006/10/31    2006/11/01
山本        2006/11/03    2006/11/04
内田        2006/11/03    2006/11/05

　自分は自分とオーバーラップしているに決まっているので、「R1.reserver <> R2.reserver」という条件がないと全員出てきてしまう点に注意してください。また、反対に「どの期間ともオーバーラップしていない期間」を求めたいなら、EXISTSの代わりにNOT EXISTSを使えばOKです。

　ところで、もし山本氏の投宿日が11月3日ではなく、1日遅れの4日だった場合、クエリの結果から内田氏が消えます。これは、内田氏の投宿日と出発日が他の期間と接触しなくなるからです。つまり、このクエリでは、相手の期間を完全に含んでしまうような期間は選択できないということです。

　こういう期間も出力するには、条件を追加してやります。

応用版：相手を完全に含む期間も出力する

SELECT reserver, start_date, end_date
 FROM Reservations R1
WHERE EXISTS
       (SELECT *
          FROM Reservations R2
         WHERE R1.reserver <> R2.reserver
           AND (  (     R1.start_date BETWEEN R2.start_date 
                                          AND R2.end_date
                     OR R1.end_date   BETWEEN R2.start_date 
                                          AND R2.end_date)
                OR (    R2.start_date BETWEEN R1.start_date 
                                          AND R1.end_date
                    AND R2.end_date   BETWEEN R1.start_date 
                                          AND R1.end_date)));

　追加した条件は、ORとAND、R1とR2を入れ替えた、ちょうど最初の条件をひっくり返したような形になります。

おわりに

　以上で見てきたことから、相関サブクエリが非常に強力な演算であることがお分かりいただけたと思います。しかし最後に、公正を期してその欠点も挙げておきましょう。まず1つ目が、可読性の低いコードになることです。慣れの問題もありますが、相関サブクエリを駆使したクエリは、いずれも「ぱっと見てすぐ分かる」タイプのものにはなりません。特に、累計や移動平均のケースがその典型だったように、集約と組み合わせると、中の動作がとても見えにくくなります。そして第2の欠点は、パフォーマンスがよくないことです。特に、SELECT句でスカラ・サブクエリとして使う場合は、大きな速度低下を招くことがあるので、注意が必要です。セルコの言葉を借りるなら、相関サブクエリは「プログラマにもオプティマイザにも読みにくい」のです。

　どんな言語、どんな技術を使うにしてもそうでしょうが、オールマイティに通用する銀の弾というのはありません。私たちが手にしているのは、いつでも諸刃の剣です。相関サブクエリのように強力な力を持つ武器は、それと等価なデメリットも抱えています。その点を心得て、うまく力を引き出しましょう。

　それでは、今回の要点です。

1. 集合指向言語たるSQLでは、行同士の比較を行うときでもソートやループを記述しない。
2. 代わりに比較対象の集合を追加して、相関サブクエリ（または自己結合）で行を「ずらす」。
3. 累計や移動平均を求める際には、ノイマン型の再帰集合が基本形。
4. 相関サブクエリの欠点は、パフォーマンスと可読性が悪いこと。
5. 人生、何もかもうまくいく、ということはそうそうない。

参考資料

1. 『プログラマのためのSQL　第2版』 Joe Celko 著、ピアソンエデュケーション、2001年4月
   累計は「23.5.1 累積和」、累積差は「23.5.2　累積差」を参照。

2. 『Joe Celko's SQL Programming Style』 Joe Celko 著、Morgan Kaufmann Pub、2005年5月
   カーニハン＆パイクの『プログラミング作法』のSQL版といったおもむきの本。「6.9 Avoid Correlated Subqueries」では、可読性とパフォーマンスの観点から相関サブクエリの濫用を戒めています。
   他にも、テーブルや列の命名規則から始まって、インデントの下げ方、コメントの書き方に集合論的発想のススメまで網羅する良書。「四角を描くな、円を描け」というのは、本当に名言だと思う。

3. 『SQLパズル 第2版』 Joe Celko 著、ミック 訳、翔泳社、2007年11月
   移動平均は「第37問 A Moving Average」、オーバーラップする期間の検出は「第47問 Blocks Of Seats」を参照。

4. 「移動平均を求める」 明智重蔵
   OLAP関数と相関サブクエリを使って移動平均を求める方法が紹介されています。後者は、BETWEEN述語を使った簡潔な方法です。