SQL緊急救命室

第1回サブクエリ・パラノイア~副問い合わせ乱用による性能劣化を治療せよ!

ここはとある街の総合病院。

ここには通常の診療科のほかに、一風変わった診療科が存在する。

何軒もの病院をたらいまわしにされた、手の施しようのないSQLや、今すぐに改善が必要なSQLが担ぎ込まれる救命室である。

それがSQL緊急救命室、略してSER(SQL Emergency Room⁠⁠。

そう、ここは国内でも唯一のプログラミング専門外来である。

ロバート

救命室部長。腕の立つエンジニアだが、口が悪く性格はもっと悪い四十オヤジ。

サブクエリ・パラノイア~サブクエリの功罪

(AM3:00:仮眠室。ソファーでロバートが熟睡しているところへワイリーがやってくる)

……先生、起きてください。


グーむにゃむにゃ。おうっ、そ、そこは。


……先生!


グー。うひゃひゃもっと下。


先生ってば!


うるさい。耳元で怒鳴るな。


先生のほうがずっとうるさいし不気味ですよ(何の夢見てんだ⁠⁠。起きてください。急患です!

今何時だと思ってる。ほっとけ、しばらく寝てりゃ自然に治ると伝えろ。

風邪じゃないんだから、ダメなコードは自然には治りませんよ。治療が必要なんです。かなり切羽詰まってるみたいですよ。

まったく、面倒な連中だ。…どれ、しかたない、行くぞ。


(救命室。雑然とした器具が散乱しているなか、天井の診察用ライトが寒々しい光を放つ。ロバートたちが入ると、すでにヘレンが診察を始めている)

遅いわよ。連絡を受けたら3分以内に来るのがルールでしょ。


3分で死ぬわけじゃあるまい。それで、患者の様態は。


典型的なサブクエリ・パラノイア(副問い合わせ強迫症)ね。しかも自己結合まで発生させて[1]⁠、これじゃクエリを遅くしてくださいとお願いしているようなものよ。

どれ…なるほど、こりゃひどい。おい、テーブル定義もよこせ。


はい、こちらに図1、2、リスト1⁠。


図1 テーブルのレイアウト
図1 テーブルのレイアウト
図2 リスト1の実行結果
cust_id | seq | price
--------+-----+-------
A       |   1 |   500
B       |   5 |   100
C       |  10 |   600
D       |   3 |  2000
リスト1 サブクエリ・パラノイア 患者1号
SELECT R1.cust_id, R1.seq, R1.price
  FROMReceiptsR1 ()
         INNER JOIN
          (SELECT cust_id, MIN(seq) AS min_seq
             FROMReceipts ※
            GROUP BY cust_id) R2
    ON R1.cust_id = R2.cust_id
   AND R1.seq = R2.min_seq;

 同一テーブルを結合する自己結合

さてワイリー、お前ならどうする。


ええっ、ちょっと待ってください。整理します。このReceipts テーブルは、顧客ごとの購入明細を記録するテーブルで、欲しい結果としては、顧客ごとに最小の枝番(seq)のレコードの金額を求めている、ということですよね。

そうね。この問題で難しいのは、連番の最小値が不確定なことね。必ず最小値が1とか決まっているなら単純にWHERE句で制限するだけでいいのだけど、動的に求めざるをえないの。

ヘレンの言うとおり、もし顧客ごとに必ずseq列の最小値が固定なら、この問題に難しいところはありません。しかし、動的にseq列の最小値を求めるため、患者は結合を使用しています。ここでのポイントは、一時的なビューR2です。これは顧客ごとに最小のseq列を求めています図3⁠。

図3 リスト1の動作イメージ
図3 リスト1の動作イメージ

相関サブクエリは解にならない

なるほどわかりました。よーし、これなら僕でも何とか…これでどうです!リスト2

リスト2 ワイリーの治療
SELECT cust_id, seq, price
  FROM Receipts R1
 WHERE seq = (SELECT MIN(seq)
                FROM Receipts R2
               WHERE R1.cust_id = R2.cust_id);

馬鹿者。これじゃ解決になっとらんぞ。


え? 間違ってました?


結果は元のクエリと同値よ。その意味で間違いではないわ。でも別の観点から不適切なの。

いいか、この患者の問題点は大きく2 つある。一つは可読性。要するに読みにくいコードだ。今患者は、顧客ごとに最小の連番のレコードだけのビュー(R2)を作り、それとオリジナルのテーブル(R1)と結合している。しかしこれは、書いた当人以外に意図が理解できない。当人も1ヵ月後には忘れて理解できなくなる。この点では、お前のクエリのほうがまだマシだ。教科書に載っている方法だから、誰にでも意図が通じる。

ええ、そうなんです。教科書の症例と同じだと思ったんですが…。


古い教科書だな。そんなもの読むと頭が悪くなるから捨てろ。お前の治療ではもう一つの問題に対処できていない。それはパフォーマンスだ。

なぜ自己結合はダメなのか~ディスクに触る者は不幸になる~

患者の実行計画

ロバートの言うことを確認するために、患者の実行計画をOracle図4とPostgreSQL図5で見てみましょう[2]⁠。テーブルの件数は少ない状態ですが、この問題に関しては、件数が増えた場合の実行計画でも同様です。

図4 患者の実行計画(Oracle)
------------------------------------------------------------------------------
| Id | Operation              | Name     | Rows | Bytes | Cost(%CPU)| Time     |
------------------------------------------------------------------------------
|  0 | SELECT STATEMENT       |          |    4 |    96 |     8 (25)| 00:00:01 |
|* 1 |  HASH JOIN             |          |    4 |    96 |     8 (25)| 00:00:01 |
|  2 |   VIEW                 |          |    4 |    64 |     4 (25)| 00:00:01 |
|  3 |    HASH GROUP BY       |          |    4 |    20 |     4 (25)| 00:00:01 |
|  4 |     TABLE ACCESS FULL| RECEIPTS |   13 |    65 |      3 (0)| 00:00:01 |
|  5 |   TABLE ACCESS FULL  | RECEIPTS |   13 |   104 |      3 (0)| 00:00:01 |
------------------------------------------------------------------------------
図5 患者の実行計画(PostgreSQL)
Hash Join (cost=1.35..2.58 rows=1 width=10)
   Hash Cond: ((r1.cust_id = receipts.cust_id) AND (r1.seq = (min(receipts.seq))))
   -> Seq Scan on receipts r1 (cost=0.00..1.13 rows=13 width=10)
   -> Hash (cost=1.28..1.28 rows=4 width=12)
        -> HashAggregate (cost=1.19..1.24 rows=4 width=6)
             -> Seq Scan on receipts (cost=0.00..1.13 rows=13 width=6)

問題は、Receiptsテーブルに対するテーブルアクセスが2回発生していることです。Oracle ならば「TABLEACCESS FULL⁠⁠、PostgreSQLならば「Seq Scan」が2度現れていることからわかります。サブクエリの内側と外側で、それぞれアクセスしているわけです[3]⁠。

テーブルの規模が小さいならこれでもかまいません。数百行程度のテーブルへのアクセスコストはとても小さく、一度読めばキャッシュにも乗り2回目はさらに速いでしょう。小規模テーブルに対する自己結合に大きな問題はないのです。でも、このReceiptsテーブルは名前からして膨大なレコード数を貯めこむトランザクションテーブルに違いありません。数百万から数千万行のオーダーのテーブルに対するアクセスは必ずディスクを触ることになります。不用意にアクセス回数を増やすべきではありません。

ワイリーの実行計画

次にワイリーの治療プランにおける実行計画を、同じようにOracle図6とPostgreSQL図7で見てみましょう。

図6 ワイリーの実行計画(Oracle)
------------------------------------------------------------------------------
| Id | Operation              | Name     | Rows | Bytes | Cost(%CPU)|     Time |
------------------------------------------------------------------------------
|  0 | SELECT STATEMENT       |          |    4 |    96 |     8 (25)| 00:00:01 |
|* 1 |  HASH JOIN             |          |    4 |    96 |     8 (25)| 00:00:01 |
|  2 |   VIEW                 | VW_SQ_1  |    4 |    64 |     4 (25)| 00:00:01 |
|  3 |    HASH GROUP BY       |          |    4 |    20 |     4 (25)| 00:00:01 |
|  4 |     TABLE ACCESS FULL| RECEIPTS |   13 |    65 |      3 (0)| 00:00:01 |
|  5 |   TABLE ACCESS FULL  | RECEIPTS |   13 |   104 |      3 (0)| 00:00:01 |
------------------------------------------------------------------------------
図7 ワイリーの実行計画(PostgreSQL)
Seq Scan on receipts r1 (cost=0.00..16.54 rows=1 width=10)
   Filter: (seq = (SubPlan 1))
   SubPlan 1
     -> Aggregate (cost=1.17..1.18 rows=1 width=4)
          -> Seq Scan on receipts r2 (cost=0.00..1.16 rows=3 width=4)
               Filter: ($0 = cust_id)

Oracle、PostgreSQLともに、やはりReceiptsテーブルへのアクセスが2度発生していることがわかります。これでは、ロバートも言うようにパフォーマンスの問題に対処できません。それでは、この点も考慮した本当の解法を見てみましょう。

結合をなくせ!

ポイントは、Receiptsテーブルへのアクセスを1回に減らすことよ。これにはウィンドウ関数参考資料4のROW_NUMBERを使うの。

そうだ。よく見とけリスト3⁠。


リスト3 ロバートの治療
SELECT cust_id, seq, price
  FROM (SELECT cust_id, seq, price,
               ROW_NUMBER() OVER (PARTITION BY cust_id
                                      ORDER BY seq) AS row_seq
          FROM Receipts ) WORK
 WHERE WORK.row_seq = 1;

うわあ、シンプル…。


ROW_NUMBERでレコードに連番を振り、常に最小値を1にすることで、seq列の最小値が不確定という問題に対処した。クエリもシンプルになり、可読性は格段に上がった。

ROW_NUMBERによってReceiptsテーブルにrow_seqという1から始まる連番を追加したのがWORKテーブルです図8⁠。これで顧客ごとの最小の枝番を持つレコードを限定することが容易になります。実行計画も見てみましょう図9、10⁠。Receiptsテーブルに対するアクセスが1回に減っていることがわかります。

図8 row_seqを追加
図8 row_seqを追加
図9 ロバートの実行計画(Oracle)
---------------------------------------------------------------------------------
| Id | Operation                  |     Name | Rows | Bytes | Cost(%CPU)|Time      |
---------------------------------------------------------------------------------
|  0 | SELECT STATEMENT           |          |   13 |   546 |     4 (25)| 00:00:01 |
|* 1 |  VIEW                      |          |   13 |   546 |     4 (25)| 00:00:01 |
|* 2 |   WINDOW SORT PUSHED RANK  |          |   13 |   104 |     4 (25)| 00:00:01 |
|  3 |    TABLE ACCESS FULL     | RECEIPTS |   13 |   104 |      3 (0)| 00:00:01 |
---------------------------------------------------------------------------------
図10 ロバートの実行計画(PostgreSQL)
Subquery Scan work (cost=1.37..1.79 rows=1 width=16)
   Filter: (work.row_seq = 1)
   -> WindowAgg (cost=1.37..1.63 rows=13 width=10)
           -> Sort (cost=1.37..1.40 rows=13 width=10)
                   Sort Key: receipts.cust_id, receipts.seq
                   -> Seq Scan on receipts (cost=0.00..1.13 rows=13 width=10)

長期的な視野を持て

患者やワイリーのクエリに比べて、ロバートのクエリがどの程度パフォーマンス向上するかは、使用するDBMSやDBサーバの性能、パラメータやインデックスといった環境要因によって大きく左右されるため、一概には言えません。しかし、ディスクアクセスの量を減らすことが、SQLチューニングにおける大方針であることは確かです。

また、結合を消去することには、単純なパフォーマンス向上だけでなくもう一つの利点が存在します。それは性能の安定性を確保できることです。

結合を使うクエリには次の2つの不安定要因があります。

  1. アルゴリズムの変動リスク
  2. 環境起因の遅延リスク(インデックス、メモリ、パラメータなど)

ワイリーの解で使われている相関サブクエリも、実行計画のアルゴリズム上は結合と似たものになることが多いため、このリスクも同様に該当すると考えてかまいません。

1.アルゴリズムの変動リスク

結合のアルゴリズムは、大きくNested Loops、SortMerge、Hashの3種類があります参考資料1⁠。これら3つのどれが選ばれるかは、テーブルのサイズなどを考慮してオプティマイザが決めます。大雑把に言うと、レコード数の少ないテーブルが含まれる場合にはNested Loopsが選ばれやすく、大きなテーブル同士の結合になるとSort MergeやHashが選ばれやすくなります。

すると、当初テーブルの件数が少なかったときはNested Loopsが選択されていたのに、運用中にレコードが増えて、ある閾値(いきち)を境に実行計画がほかの2つへ変動することがあります。このとき性能が大きく変化してしまうのです(良いほうに倒れることもあれば、悪いほうに倒れることもあります⁠⁠。結合を使うということは、この変動リスクを抱え込むことを意味します。

また、同じ実行計画が選択され続けていたとしても、データ量の増大によってSort MergeやHashの作業メモリが不足するようになると、一時的にディスクが使用され、やはり大きく性能劣化します[4]⁠。

2.環境起因の遅延リスク

こちらはもう少し簡単な話です。よく知られているように、結合キーにインデックスを張ることで、結合の性能が大きく改善します。また、Sort MergeやHashが選択されているときは、その作業メモリを増やすことでも性能改善が可能です。しかし、常に結合キーにインデックスが存在しているわけではありませんし、メモリチューニングは限られたリソース内でのトレードオフを発生させます。

結合を利用するときは注意

結合を使うということは、考慮すべき要因を増やしてしまうことになります図11⁠。

図11 結合クエリは性能が非線形で劣化するリスクを負う
図11 結合クエリは性能が非線形で劣化するリスクを負う

私たちは、なるべくオプティマイザが理解しやすいクエリを書いてあげる必要があるのです。

  • シンプルな実行計画ほど性能が安定する

このことを、ぜひ覚えておいてください。SQLは、ただ動けばよいというものではなく、可能な限り美しくシンプルなものであるべきです。

長期国債はお得?

なるほどー。先生の解はいろんなリスクに備えた、手堅い手段なのですね。長期国債みたいなものですね。

その喩えはあってるようなあってないような…


短期の金融商品にはリスクもあるが、それなりのメリットもある。だが今回は患者やお前の解にはっきりしたメリットはない。強いて言えば、MySQLはまだウィンドウ関数を実装していないので、お前の解がセカンドベストになるかもしれん。

うーん、それはメリットと呼ぶには消極的だなあ。


いずれにせよ、パフォーマンスについてはどんな実行計画が選択されるか見てみないことにはわからんな。

サブクエリ・パラノイア~応用版~

(救命室で3人がロバートの解をあれこれ論評していると、けたたましい救急車のサイレンが聞こえる)

あら、患者は2人いたのね。今度はさっきより酷いサブクエリ・パラノイアだこと!

今日は世間じゃサブクエリ記念日なのか? ワイリー、患者のカルテを。

は、はい、ただいまリスト4、図12⁠。


リスト4 サブクエリ・パラノイア 患者2号
SELECT TMP_MIN.cust_id, TMP_MIN.price - TMP_MAX.price
  FROM (SELECT R1.cust_id, R1.seq, R1.price
          FROM Receipts R1
                 INNER JOIN
                   (SELECT cust_id, MIN(seq) AS min_seq
                      FROM Receipts
                     GROUP BY cust_id) R2
            ON R1.cust_id = R2.cust_id
           AND R1.seq = R2.min_seq) TMP_MIN
       INNER JOIN
       (SELECT R3.cust_id, R3.seq, R3.price
          FROM Receipts R3
                 INNER JOIN
                   (SELECT cust_id, MAX(seq) AS min_seq
                      FROM Receipts
                     GROUP BY cust_id) R4
            ON R3.cust_id = R4.cust_id
           AND R3.seq = R4.min_seq) TMP_MAX
    ON TMP_MIN.cust_id = TMP_MAX.cust_id;

 テーブルのレイアウトとデータは図1と同じとする

図12 リスト4の実行結果
cust_id  | diff
---------+-------
A           -200
B           -900
C            550
D              0

行間比較でも結合は必要ない

またずいぶんな大作ね。どれだけサブクエリを使えば気が済むのかしら。ワイリー、このお馬鹿な患者のやろうとしていることはわかる?

えっと、今度は枝番の最小値だけじゃなく、最大値のレコードも求めてるんですよね。それが後半のTMP_MAX。で、それと最小値のレコードのprice列の差分を出している、と。

上出来だ。一種の行間比較をやりたいってわけだ。よくある話さ。では、このクエリの問題点は。

可読性はさっきの患者にも増して悪いですね。サブクエリの階層が深くて、追うだけで精一杯だ。さっきのクエリを2倍に膨らましたようなものだから、Receiptsテーブルへのアクセスはさらに増えて、パフォーマンスも悪くなります。

よくできました。それじゃ治療に入るわよ。いい、ポイントはさっきと同じでどれだけ無駄なサブクエリと結合を減らせるか。今度はウィンドウ関数に加えてCASE式参考資料2も使うわよリスト5⁠。サブクエリはWORKの1つだけ。結合も一切発生しないわ。

リスト5 ヘレンの解
SELECT cust_id,
       SUM(CASE WHEN min_seq = 1 THEN price ELSE 0 END)
           - SUM(CASE WHEN max_seq = 1 THEN price ELSE 0 END) AS diff
  FROM (SELECT cust_id, price,
               ROW_NUMBER() OVER (PARTITION BY cust_id
                                      ORDER BY seq) AS min_seq,
               ROW_NUMBER() OVER (PARTITION BY cust_id
                                      ORDER BY seq DESC) AS max_seq
          FROM Receipts ) WORK
 WHERE WORK.min_seq = 1
    OR WORK.max_seq = 1
 GROUP BY cust_id;

いやあこれは見事だ。いつ見てもヘレンのCASE式には惚れ惚れするな。

あ、あのすいません。全然ついていけないんですけど…。特にその、CASE式のあたりが。

なにい。お前ほんとに大学行ってるのか。今日は居残りだ。このクエリの意味を完全に理解するまで帰ることは許さん。

そ、そんなあ。


ウィンドウ関数の昇順ソートと降順ソートをうまく使おう

読者の中にも、ワイリーと同じくついていけなくなってしまった人がいるかもしれませんね。ヘレンの解では、最小値と最大値のレコードを特定するため、ROW_NUMBER関数を使っています。一工夫加えられているのは、最大値を出すために降順(ORDER BY seq DESC)でソートしていることです。こうすると、連番max_seqが1のレコードがseqの最大値を持っていることが保証されます。

あとは、min_seqまたはmax_seqが1のレコードだけに限定すれば、⁠真ん中」のレコードを除外できるわけです図13⁠。

図13 結合クエリは性能が非線形で劣化するリスクを負う
図13 「両端」のレコードにしか興味はない

残る問題は、2レコードにまたがるprice列について引き算を行う方法です。これをヘレンはCASE式によって実現していますが、この理論的理解を今回の課題としましょう[5]⁠。

稿末の参考資料をヒントに考えてください。なお、顧客IDが「D」の明細については、1つしかレコードが存在しないため、price列の値によらず差分はゼロになっています。

おわりに~困難は分割するな~

(AM7:00 夜は完全に明けた。休憩室でワイリーが何やら机に向かっている。課題に苦しんでいるようだ。そこへ、ヘレンがコーヒー片手に入ってくる)

はあはあ…。ようやく課題が終わった。難しかった。でもCASE式って便利だなあ。今度は僕も使ってみよう。それにしても、サブクエリがこんな危険なものだとは思わなかった。

別にサブクエリは絶対悪ではないわ。特に、最初にクエリを考えるときは、問題を分割して考えることができるから、思考の補助線としては有効よ。

そう、そうなんですよ! サブクエリって考えやすいんですよ。細かいパーツに分けて、それを組み合わせていけるから便利ですよね。

そうね。ただ非手続き型であるSQLの本質として、そういうボトムアップ型というか、モジュール型の思考とは相性が悪いの。最初に頭の中で考えるときは問題を細かくモジュール分割して考えてもいいわ。その方法論までは否定しない…。でも、最後に包括的に統合しなければ、本当にSQL的なコードにはならないの。困難を分割してもいいのは最初だけってこと。

うーん、ヘレンさんが言うと説得力あるなあ。誰かさんと違って。


(ロバートが休憩室のドアを乱暴に開けて入ってくる⁠

おい、2人ともこんなところで油を売ってるんじゃない。救急隊員から連絡が入った。新しい患者が来るぞ。かなり危険な状態らしい。

一難去ってまた一難ね。行くわよ、ワイリー。


そ、そんな。僕昨日から寝てないのに。


泣きごと言うな。永遠に寝られる薬打ってやろうか。行くぞ!


えーん。


(次号に続く)

【参考資料】

※すべて拙著

1.WEB+DB PRESS Vol.60連載「DBアタマアカデミー」第4回⁠クエリ評価エンジンと実行計画⁠

実行計画の読み方、DBMS内部でのSQLの実行のされ方、結合時のアルゴリズムなどについて知りたい方はこちらを読むと基礎的なことがわかります。

2.CASE式のススメ(前編)

患者2号に対するヘレンの解で、CASE式の使い方が理解できなかった人はこちらをどうぞ。このCASE式を集約関数の中で使う技術は、SQLをマスターするうえでは必須です。

3.自己結合の使い方

自己結合のイメージが湧かない人向け。自己結合は、使いこなせば便利な道具です。しかし、パフォーマンス上の問題点を抱えているため、乱用は危険。

4.本WEB+DB PRESS Vol.55 連載「SQL アタマアカデミー」最終回“OLAP関数で強力な統計処理を実現!”

ウィンドウ関数の使い方を勉強したい方はこちらをどうぞ。なお「OLAP関数」とは、ウィンドウ関数の(やや古い)別名です。

5.WEB+DB PRESS Vol.45連載「SQLアタマアカデミー」第1回“連番の特性を利用してデータ操作をもっと自由に”

ウィンドウ関数の中でも特にROW_NUMBER関数でレコードに連番を振る技術の応用方法を解説しています。

おすすめ記事

記事・ニュース一覧