ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

テーブル結合における外部表・内部表の選択

目的

テーブル結合の外部表(駆動表)はデータセットの小さい方を選ぶ可能性が高いです。データセットの小さい方を選ぶことでI/Oコストの観点から有利になることを示します。また、オプティマイザの外部表・内部表選択基準の例を挙げます。

疑問

表Rと表Sの結合を行うとし、結合対象の行数をそれぞれ r(R), r(S) とします。Nested-Loop Join であれば組み合わせ数は r(R) * r(S) となり、表Rと表Sのいずれが外部表に選択されても組み合わせ数は変わりません。なぜデータセットの小さい表が外部表に選ばれやすいのでしょうか?

解説

I/Oコストの計算

以下の資料を参考に説明します。
https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf

例として以下のケースを想定します。
表R:A, B列
表S:B, C列
SQL:SELECT * FROM R, S WHERE R.B = S.B

Nested-Loop Join を疑似コードで表現します。

// ディスクから表Rの1ブロックを読み込む
FOR EACH block x IN R DO
   // ディスクから表Sの1ブロックを読み込む
   FOR EACH block y IN S DO
      // 表Rの1ブロックから1レコード読み込む
      FOR EACH r in x DO
         // 表Sの1ブロックから1レコード読み込む
         FOR EACH s in y DO
            // 読み込んだレコードのB列の値が等しければ結果に出力する
            IF (r.B=s.B) THEN OUTPUT RESULT

この処理でのI/Oコストを計算します。
表Rと表Sのブロック数をそれぞれ b(R), b(S) とします。

外部表(表R)は全てのブロックを1回だけ読み込みます。
内部表(表S)は全てのブロックを表Rのブロック数と同じ回数読み込みます。

ディスクからの読み込みはI/Oコストです。ディスクからの読み込みブロック数は以下の式となります。
b(R) + b(R) * b(S)
この式においてb(R)が支配的です。よって、小さい外部表を選ぶことがI/Oコストの低減になります。

ただし、表のブロック数が大きくなるほど、外部表の選択による差は小さくなります。このことを確認するため、外部表が表R, Sそれぞれの場合のI/Oコストとその比率を示します。

b(R) b(S) 外部表Rのコスト 外部表Sのコスト 外部表R/Sコスト比
1 10 11 20 0.550
10 100 1,010 1,100 0.918
100 1,000 100,100 101,000 0.991
1,000 10,000 10,001,000 10,010,000 0.999

オプティマイザの判断

I/Oコストの観点から結合の外部表はデータセットの小さい方が有利です。ですが、オプティマイザはデータセットの大小だけで判断しているわけではありません。例えばDB2の場合、以下の基準を用いて判断しています。

  • 表が小さければ小さいほど外部表として選択される可能性が高い。これにより、内部表を再アクセスする回数が減ります。
  • 選択述部を適用できる表は外部表として選択される可能性が高い。この場合、外部表に適用された述部を満足する行のだけが内部表からアクセスされるからです。
  • 表の1つに対して索引参照を実行できる場合は、その表が内部表の候補になる。表に索引がない場合は、内部表の候補になりません。これは、外部表の各行に対して、その都度内部表全体をスキャンする必要があるからです。
  • 重複項目が最も少ない表は、結合における外部表として選択される傾向がある。

もちろん、以上のどれも厳密な規則ではありません。最終的に、オプティマイザーは詳細なコスト見積りに基づいて外部表と内部表を選択します。

DB2 SQLアクセス・パスのチューニング

結合方式による違い

外部表・内部表の選択による影響は結合方式によっても異なります。外部表・内部表の選択によって、Nested-Loop Join ではI/Oコストに差異が現れますが、Sort-Merge Join ではI/Oコストに差異がありません。
詳細は以下の資料をご参照ください。
https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf

まとめ

結合の外部表選択によってコストに違いの出るケースがあります。オプティマイザはこのコスト差も判断したうえで、実行計画を立てています。