「データベースパフォーマンスアップの教科書」の「猶予ハッシュジョイン」説明補足

はじめに

「データベースパフォーマンスアップの教科書」（以下、書籍）はデータベースの内部処理を解説した数少ない本です。その解説にはややわかりづらい点があります。また、その中で取り上げられている「猶予ハッシュジョイン」はネットで情報を探しにくいです。

データベースパフォーマンスアップの教科書 基本原理編

そこで、本エントリでは「猶予ハッシュジョイン」の用語及びプロセスの説明を補足し、理解の一助となることを目指します。

前提

本エントリは書籍の該当章を事前に読んでいることを前提にまとめています。このため、書籍に記述されている説明は割愛しており、書籍無しでは理解し辛い点があることをご了承ください。

本エントリで明記無く「猶予ハッシュジョイン」と記述した場合、書籍で解説されている技法を指します。その詳細は書籍の「6.3.4.2 猶予ハッシュジョイン」を参照ください。

用語の補足

猶予ハッシュジョイン

ハッシュジョインの処理に必要なメモリ量を確保できないとき、ハードディスクなどの補助記憶装置も利用してハッシュジョインの処理を複数ステップに分けて行うのが猶予ハッシュジョインです。OSのスワップではなく、データベースの機能として実装されています。

猶予ハッシュジョインのことをMicrosoftのTechNetでは「猶予ハッシュ結合」と表記しています。
該当記事：ハッシュ結合について

また、TechNetでは同じ記事が英語版でも公開されています。
該当記事：Understanding Hash Joins
ここでは"Grace Hash Join"としています。

このことから、「猶予ハッシュジョイン」は"Grace Hash Join"と同義であるといえます。

「猶予ハッシュジョイン」の情報を探すときはネットで"Grace Hash Join"と検索すると参考になる記事や資料が多く見つかります。

1次ハッシュ関数、2次ハッシュ関数

「猶予ハッシュジョイン」のプロセス説明に「1次ハッシュ関数」「2次ハッシュ関数」という用語が出てきます。これらはそれぞれ、「スプリット関数」「ハッシュ関数」とも呼ばれています。

「1次ハッシュ関数（スプリット関数）」「2次ハッシュ関数（ハッシュ関数）」はそれぞれ用途が異なるため、異なるハッシュ関数を利用することができます。参考資料からハッシュ関数の用途説明を引用します。

本ハッシュ法では2種類のハッシュ関数（スプリット関数、ハッシュ関数）が用いられる。前者はリレーションを主記憶より小さな複数のバケットに分けるために、後者は主記憶上でタプルのつき合わせ処理を行うために用いられる。

共有メモリ型マルチプロセッサによる並列ハッシュ結合演算処理とその評価

ビルドフェーズ、プローブフェーズ

ビルドフェーズ(build phase)・プローブフェーズ(probe phase)はMicrosoftのTechNetの記事で使われている用語です。
該当記事：ハッシュ結合について

ビルドフェーズではビルドインプットのジョインキーにハッシュ関数を適用してハッシュ値を生成します（書籍の猶予ハッシュジョインのプロセス①～⑧に対応）。
プローブフェーズではプローブインプットのジョインキーにハッシュ関数を適用し、ビルドインプットのハッシュ値との突合せを実施します（書籍の猶予ハッシュジョインのプロセス⑨～⑮に対応）。

ビルドフェーズ・プローブフェーズを意味する表記は他にもあり、以下に表記例とそれが使われている資料を挙げます。

• ビルドフェーズ
  • スプリットフェイズ (*1)
  • Hash phase (*2)
  • partitioning phase (*3)
• プローブフェーズ
  • ジョインフェイズ (*1)
  • Merge phase (*2)
  • probing phase (*3)

(*1) 共有メモリ型マルチプロセッサによる並列ハッシュ結合演算処理とその評価

(*2) Datenbanksysteme II: Implementation of Database Systems

(*3) Hybrid Hybrid Grace Hash Join, v1.0 - Apache Hive - Apache Software Foundation

パーティション

ビルドインプットは1次ハッシュ関数によって複数パーティションに分割されます。このパーティションのことをバケット(bucket)と表記することもあります。

猶予ハッシュジョインのプロセス説明の補足

用語としての「猶予ハッシュジョイン」は"Grace Hash Join"と同義である、と説明しました。ですが、書籍で説明している「猶予ハッシュジョイン」のプロセスは"Hybrid Hash Join"の技法も取り込んだものとなっています。
ここではまず"Grace Hash Join"についての説明を行い、その後に"Hybrid Hash Join"及びそれが書籍でどのように解説されているかを説明します。

本節では引用する資料に倣い、表R, Sのジョインプロセスを例にします。

Grace Hash Join

ハッシュジョインでビルドインプットのハッシュテーブルが大きすぎてメモリに入りきらないのであれば、ハッシュテーブルをディスクに書き出せばよい、というのが Grace Hash Join のアイディアです。
この技法ではビルドフェーズで表R, Sのジョインキーから計算したハッシュテーブルをメモリからディスクへ全て書き出します。そしてプローブフェーズで処理に必要なハッシュテーブルをディスクからメモリに逐次読み込みます。

この処理の流れを解説した記事を引用します。

1. Small table R is scanned, and during the scan a hash function is used to distribute the rows into different output buffers (or partitions). The size of each output buffer should be specified as close as possible to the memory limit but no more than that. After R has been completely scanned, all output buffers are flushed to disk.
2. Similarly, big table S is scanned, partitioned and flushed to disk the same way. The hash function used here is the same one as in the previous step.
3. Load one partition of R into memory and build a hash table for it. This is the build phase.

Hybrid Hybrid Grace Hash Join, v1.0 - Apache Hive - Apache Software Foundation

別の資料でもハッシュテーブルを全て書き出すと説明しています。

Scan R, compute hash table, writing full blocks to disk immediately
Scan S, compute hash table, writing full blocks to disk immediately

Datenbanksysteme II: Implementation of Database Systems

Hybrid Hash Join

Grace Hash Join を改良し、I/O効率を高めたのが Hybird Hash Join です。ビルドフェーズでハッシュテーブルをディスクへ全て書き出すのではなく、一部をメモリ上に保持することで効率を高めています。

ハッシュテーブルをメモリ上に保持する手法には、今回参考にした資料で以下の2パターンがありました。資料の説明箇所の引用と併せて以下に挙げます。

(1) ハッシュテーブルの1つ目のパーティションをメモリ上に保持する（ディスクに書き出さない）

ハイブリッドハッシュ結合演算技法は単純なシンプルハッシュ法とGRAECハッシュ法を融合させた手法であり、その名称もこの事実に依っている。GRACEハッシュ結合演算技法では前処理としてのハッシュ分割時には主記憶を入出力バッファとしてしか使用していないため、その利用効率が低い。ハイブリッドハッシュ法ではこの点に着目し、1つ目のバケットをハッシュ分割時の余った主記憶空間を利用して処理することにより、主記憶に比べてそれほど大きくない比較的小規模なリレーションに対する処理性能の向上を図っている。
※"GRAEC"のスペルミスは原文ママ。

共有メモリ型マルチプロセッサによる並列ハッシュ結合演算処理とその評価

It is a hybrid of Classic Hash Join and GRACE Hash Join. The idea is to build an in-memory hash table for the first partition of R during the partitioning phase, without the need to write this partition to disk. Similarly, while partitioning S, the first partition does not have to be put to the disk since probing can be directly done against the in-memory first partition of R. So at the end of the partitioning phase, the join of the first pair of partitions of R and S has already been done.

Hybrid Hybrid Grace Hash Join, v1.0 - Apache Hive - Apache Software Foundation

(2) メモリ上に(a)全て保持するパーティションと(b)1ブロックのみ保持するパーティションにグループ分けして保持する

• Chose smaller relation (assume S)
• Chose a number k of buckets to build (with k<m)
  • Again, assuming perfect hash functions, each bucket has size b(S)/k
• When hashing S, keep first x buckets completely in memory, but only one block for each of the (k-x) other buckets
  • These x buckets are never written to disk

Datenbanksysteme II: Implementation of Database Systems

書籍の「猶予ハッシュジョイン」のプロセス説明は(2)に近いです。書籍より該当箇所を引用します。

⑦このような方式でビルドインプットの処理範囲を処理し、ハッシュ領域を超過したらパーティションテーブルに位置情報を残し、ディスクに移動する。パーティションテーブルにある情報は、後程パーティションペアを探し、連結作業を実行する時に使用する。
（中略）
⑩フィルタリングを通過したものは、2次ハッシュ関数を適用する。もし、この時プロブインプットに対応するビルドインプットがメモリ内に存在すれば、ハッシュテーブルを読み、連結を実行し、そうでなければ該当パーティションに保存する。

つまり、書籍の「猶予ハッシュジョイン」は単なる"Grace Hash Join"ではなく、"Hybrid Hash Join"の技法も取り入れて、より効率化したものといえます。

まとめ

「データベースパフォーマンスアップの教科書」の「猶予ハッシュジョイン」は"Grace Hash Join"より"Hybrid Hash Join"に近いプロセスを採用しています。他の資料や実装を調査する際にはこの点に留意しましょう。

更新情報

2017/05/14

• 猶予ハッシュジョインの用語説明に補記しました。

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

目的

テーブル結合の外部表（駆動表）はデータセットの小さい方を選ぶ可能性が高いです。データセットの小さい方を選ぶことで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を書くときに常に手元へ置いておきたい一冊。
こんな時はどうなるのだっけ？というヒントがまとめられています。

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

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