JOIN
用語
Driving Table (駆動表, 外部表)
JOIN において最初にアクセスされるテーブル
内部表
駆動表に対して結合される表
種類
Nested Loop Join
Block Nested Loop Join
Batched Key Access Join
Sort Merge Join
Hash Join
NLJ
NLJ の基本的なアルゴリズムはループである。例えば、table1 と table2 を JOIN する擬似コードは以下のようになる。
code:js
for row1 of table1 {
for row2 of table2 {
join row1 and row2
}
}
NLJ のアルゴリズムは、JOIN 開始前にその作業を削減すると効率が良くなる。もっとも良いのは、JOIN 前に駆動表に選択性の高い述語がいくつかあり、ほとんどのデータをフィルタリングできる場合。
code:js
for row1 of table1 matching condition {
for row2 of table2 matching condition {
join row1 and row2
}
}
逆にもっとも悪いのは、述語がテーブル間に散らばってしまっており、かつインデックスも聞いていない場合。このような場合には、非正規化 が役立つ場合がある。非正規化 は、駆動表のカラムを冗長に保持することで、複合インデックスを追加でき、行へのアクセス、あるいは他のテーブルとの結合前にフィルタリングを行える。
と、いう一方で、非正規化よりも前に考えることも色々ありそう。
BNLJ
NLJ では、駆動表から 1 行フェッチしたら、その 1 行と JOIN する行を内部表から抜き出して、JOIN する。このとき、内部表に対してインデックスが効いていればすぐに内部表から行をフェッチできるが、インデックスが効いていない場合、内部表をスキャンする必要がある。
つまり、内部表に対してインデックスが使えない場合、駆動表から 1 行フェッチする毎に内部表をスキャンする ことになる。これは非常に遅い。
BNLJ では、駆動表から 1 行フェッチしても、すぐには内部表を見に行かない。駆動表からフェッチした行は JOIN Buffer に順次溜め込まれる。そして、JOIN Buffer がいっぱいになったタイミングで、JOIN Buffer 内の各行と JOIN する行をフェッチするために、内部表をスキャンする。これによって、内部表をスキャンする回数を減らすことができる。
BNLJ は、I/O 負荷を軽減する。しかし、CPU 負荷を要する。また、行データが全てメモリに治る場合は寄与しない。JOIN Buffer は駆動表が全て入るサイズ以上に大きくしても性能はそれ以上上がらない。
BKAJ
MRR (Multi Range Read) は、ディスクの並び順にしたがってデータファイルを読み取る、という、RDBMS に古くからある最適化手法。一般に、データがメモリ上にある場合にはランダムアクセスでも問題にならないが、ディスク上にある場合はシーケンシャルアクセスした方が効率が良い。
例えば、セカンダリインデックスを利用したアクセスはランダムアクセスになる。が、セカンダリインデックスに対応する内部表の行の位置を、事前に全て取得しておき、データの並び順でソートして保持しておく。そして、実際にセカンダリインデックスでアクセスする際には、保持してあった行の位置情報データに基づいて内部表にアクセスする。すると、内部表にはデータの並び順にアクセスすることになるため、性能が良くなる。
MRR は、HDD では性能がでるが、SSD ではあまり効果がない。
BKAJ は、BNLJ と MRR の合わせ技で、JOIN Buffer がいっぱいになった後に、内部表ではなく MRR 最適化された内部表にアクセスする。これによって、内部表へのアクセスがデータの並び順に一致して、性能が良くなる。
semijoin マテリアライズ
## 用語
- 外部表: ループ元
- 内部表(駆動表): ループ先
## NLJ
- 内部表の結合キーに index があると、ループを省略できるため、外部表が小さいほど高速
- 一意ならさらに早い
- 1 レコードずつ確定するので、結果を順次返せる
## Hash Join
### 手順
- 小さい方の表をフルスキャンし、hash 表を作成
- 大きい方の表をフルスキャンし、hash 表と比較
- 結合キーをハッシュ関数にかけ、hash 表から結合可能なデータを探索
### 特徴
- 以下の場合に有効
- 外部表が大きい、あるいは結合条件に index がなくフルスキャンが必要
- 内部表の対象件数が多い
- hash 表を作成さえすれば結合は早いが、作成・保存のための十分なメモリが必要
- メモリが足りない場合、hash 表を一時表け書き出す必要があり、遅い
- 少なくとも小規模表をフルスキャンしてからでないと、最初の 1 レコードは返せない
- 等値結合にしか利用できない
## Sort Merge Join
### 手順
- 各種表を全件ソートし、フルスキャン
### 特徴
- ソート用のカラムにインデックスが貼られていると早い
- hash join よりも早い場合がある
- hash join と同様、表の大部分を結合する場合に早い
- 等値結合以外の不等式をつかった結合にも利用できる
# view のリファクタリング
- 対象テーブルの更新が少ない場合や、更新が 1 日 1 回で良い場合、集計結果を別テーブルとして保存した方が参照が高速
- materialized view
- 実体をもった view
- 集計処理に利用されることが多い
- 更新処理が DB 毎に高速化されている
- 手作業で作った summary table と比較して、リフレッシュ操作のみでデータを更新できるので、メンテナンスが楽