ぱと隊長日誌

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

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

はじめに

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

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

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

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

前提

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

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

用語の補足

猶予ハッシュジョイン

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • ビルドフェーズ
    • スプリットフェイズ (*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

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