ぱと隊長日誌

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

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

目的

テーブル結合の外部表(駆動表)はデータセットの小さい方を選ぶ可能性が高いです。データセットの小さい方を選ぶことで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

まとめ

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

PostgreSQLの検査制約におけるNULLの扱い

はじめに

PostgreSQLを基準とした資格試験の問題集「徹底攻略 OSS-DB Silver問題集[OSDBS-01]対応」にて、以下の検査制約を設定したテーブルに対して、値にNULLを含んだINSERTが成功するか?という問題がありました。

CREATE TABLE points (
  col1 INTEGER PRIMARY KEY,
  col2 INTEGER,
  CHECK (
  col1 > 0
  AND col2 < 0
  )
);

INSERT INTO points
VALUES
  (3, NULL);

答えは「成功する」なのですが、これを理解するには検査制約におけるNULLの扱いがポイントとなります。
本エントリで解説します。

NULLと比較述語

NULLと比較述語について「達人に学ぶSQL徹底指南書」の「1-3 3値論理とNULL」からまとめます。

NULLに比較述語を適用した結果は常に真理値unknownとなります。これはNULLが値でも変数でもなく、値を対象とする比較述語を適用できないためです。

これに伴い、以下の式は全部unknownとなります。
1 = NULL
1 > NULL
1 < NULL
1 <> NULL
NULL = NULL

真理値には以下の優先順位があります。
ANDの場合:false > unknown > true
ORの場合 :true > unknown > false
"true AND unknown"なら結果はunknownです。
"true OR unknown"なら結果はtrueです。

PostgreSQLの仕様

前節で説明したNULLと比較述語の関係はPostgreSQLについても成り立ちます。

入力のどちらかがNULLの場合、通常の比較演算子は真や偽ではなく(「不明」を意味する)nullを生成します。 例えば7 = NULLはnullになります。7 <> NULLも同様です。

9.2. 比較関数および演算子

そして、検査制約のNULLの扱いについて以下の説明をしています。

検査制約では、検査式が真またはNULL値と評価された場合に、条件が満たされることに注意して下さい。 ほとんどの式は、演算項目に一つでもNULLがあればNULLと評価されるので、検査制約では制約対象の列にNULL値が入るのを防げません。

5.3. 制約

検査制約でNULLを評価する

冒頭のSQLを再掲します。

CREATE TABLE points (
  col1 INTEGER PRIMARY KEY,
  col2 INTEGER,
  CHECK (
  col1 > 0
  AND col2 < 0
  )
);

INSERT INTO points
VALUES
  (3, NULL);

INSERT実行時、検査式は以下の通り評価されます。
(3 > 0) AND (NULL < 0)
= true AND null
= null

PostgreSQLは検査式がNULLと評価された場合も条件を満たすため、このINSERTは成功します。

非NULL制約(NOT NULL)

PostgreSQLで列にNULL値を含ませないためには非NULL制約(NOT NULL)が推奨されています。

非NULL制約は常に列制約として記述されます。 非NULL制約はCHECK (column_name IS NOT NULL)という検査制約と機能的には同等ですが、PostgreSQLでは、明示的に非NULL制約を作成する方がより効果的です。

5.3. 制約

参考

達人に学ぶ SQL徹底指南書 (CodeZine BOOKS)

達人に学ぶ SQL徹底指南書 (CodeZine BOOKS)

SQLを書くときに常に手元へ置いておきたい一冊。
こんな時はどうなるのだっけ?というヒントがまとめられています。

徹底攻略 OSS-DB Silver問題集[OSDBS-01]対応 (ITプロ/ITエンジニアのための徹底攻略)

徹底攻略 OSS-DB Silver問題集[OSDBS-01]対応 (ITプロ/ITエンジニアのための徹底攻略)

この問題集を解くことで、今回のエントリのようにわかっているようでわかってないことに気づくチャンスとなるかも。

OSS-DB Silver [OSDBS-01] 受験対策教材集

はじめに

OSS-DB Silver [OSDBS-01] 受験対策の教材はあまり多くありません。ですが、よく探してみると、自習で役立つ資料が公開されていたりします。
このエントリでは私が受験対策のために実際に使い、参考になったものをご紹介いたします。

テキスト

OSS教科書 OSS-DB Silver

試験対策の最初の1冊としてPostgreSQLの全体像を知るためによいと思います。最後の章に模擬試験が付いています。
ただ、出題範囲の全てをカバーはできておらず、問題集で取り上げられた内容が本書には説明のないことがあります。また、出版されてから日が経っていることもあり、その後のアップデートをカバーできていません。
受験対策としても、そして業務に活かすためにも、この1冊を足がかりに公式ドキュメントや関連記事を読み込んだり、実際に環境を構築して触ってみることが必須です。

PostgreSQL日本語ドキュメント

PostgreSQL日本語ドキュメント
日本PostgreSQLユーザ会が翻訳・公開しています。
全てを読む必要はありませんが、テキストや問題集でわからなかったところはこまめに調べましょう。
ドキュメントはバージョン毎に用意されていますが、Silverの出題範囲を踏まえるとバージョン毎に大きく異なることはないと思われます。出題範囲に記載されている対応バージョンを参考にするか、悩んだら最新版でも問題ないと思われます。

OSS-DB Silverの出題範囲(対応バージョン含む)はこちらを参照ください。
http://www.oss-db.jp/outline/examarea.shtml

LPIセミナー(技術解説資料あり)

http://www.oss-db.jp/news/event/
OSS-DB Exam Silver 技術解説無料セミナー』が目印です。イベント詳細ページに資料がアップされています(されていない場合もあります)。
ここでポイントなのが、このセミナーは担当講師が時折入れ替わっており、それに応じて資料の内容も入れ替わっています。時間が許せば複数読んでみるのもよいかもしれません。

OSS-DB道場

http://www.oss-db.jp/measures/dojo.shtml
LPIが公開しているPostgreSQLに関するコラムです。
各コラムはさくっと読める分量ですので、隙間時間や気分転換に読んでみてはいかがでしょうか。

問題集

徹底攻略 OSS-DB Silver問題集

現時点にて、書店で入手可能な唯一の問題集と思われます。
テキスト付属の例題や無償公開されている問題集もありますが、出題範囲に対する網羅度や解説の丁寧さを考慮すると、この問題集をベースに学習を進めるのがよいと考えています。

解説は丁寧ですが、一部補足したほうが分かりやすい箇所があり、別エントリにてまとめました。よろしければご参照ください。
OSS-DB silver問題集 [OSDBS-01]対応 補足 - ぱと隊長日誌

LPI公式サンプル問題

http://www.oss-db.jp/measures/sample.shtml
公式によるサンプル問題との位置付けですが、サンプルとは思えない問題数及び解説の内容となっています。
一般の問題集では出題傾向や内容に本番と差異の心配がありますが、公式であればそういった心配はないでしょう。受験前に取り組まれることをお勧めします。

ITトレメ

@ITラーニングカレンダー、ITトレメ終了のお知らせ - @IT
@ITが無償公開しているOSS-DB Silverの問題集です。
解説はあっさりした量ですが、99問が提供されているため、隙間時間の活用や最後の腕試しに良いかと思われます。

その他

LPIのサイトではOSS-DB Silver対応認定教材として、本エントリに含めていない教材についても紹介があります。よろしければご参照ください。
http://www.oss-db.jp/measures/learning.shtml