2006/1/23
さて，今回からは…（１）
さて，今回からは…（１）zデータベース処理の高速化単にディスクアクセスの速度や，演算処理の速度を向上させるだけでなく，以下のような機能も重要• 大規模データベースの中から目的のレコードだけを高速に読み書きする機能• メモリには納まりきれないほどのデータ（＝メモリにすべて読み込んでしまうことはできないようなデータ）を扱う機能• 頻繁な挿入・削除を効率よく処理する機能• 複数のリクエストを並行処理する場合の一貫性制御
これらを解決するために• データベースに特有のデータ構造• データベースに特有のアルゴリズム

データ工学特論（８）
情報基盤センター
天野 浩文
この講義の webサイトを作りました．
http://isabelle.cc.kyushu-u.ac.jp/~amano/data-engineering/index.html
レポート課題も掲示しましたので，参照してください．

1

2

さて，今回からは…（２）
さて，今回からは…（２）

さて，今回からは…（３）
さて，今回からは…（３）z大規模データベースにおけるディスクアクセス
複数のファイルを同時に扱う
すべてをメモリに読み込むことはできないので，それぞれのファイルから少しずつ読んでは結果（中間データ）を生成する
ディスクアクセス回数を減らしたり，中間データのサイズを小さくしたりするために，さまざまなアルゴリズムを用いる
zこの場合のディスクアクセスのパターンを詳細に分析すると．．．
一見ランダムに見えるが，実はある一定のパターンでデータの全体にアクセスしている場合がある特定のデータに繰り返しアクセスするような場合もある

zホスト側（ＯＳ）に行わせてもよいのだが，ディスクの機能を高めて，処理を分担させることも効果がある
zより「賢い」ディスクを目指して
高機能ディスク自律ディスクディスクの機能？

通常のファイルアクセスの場合とは異なる特殊な先読みやキャッシングが有効になることもある
3

データ工学特論（７）412006/1/23
さて，今回からは…（４）
さて，今回からは…（４）z並列処理による高速化
（並列）データベースマシン• 専用ハードウェアで実現されるもの• 残念ながら，あまり価格が下がらなかった• 商業的には失敗…1990年代半ばまでにすたれてしまった
並列データベースシステム• 汎用的な並列計算機やPCクラスタ上にソフトウェアで実現されるもの• 「売れ筋」のハードウェアに載れば，価格も下がる• 現在の主流…さまざまな商用システムが登場

データベースの基礎
データベースの基礎

そこで用いられる高速化手法について紹介

5

6

データベース処理の基礎（１）
データベース処理の基礎（１）

データベース処理の基礎（２）データベース処理の基礎（２）zリレーショナルデータベース
レコード（タプル）からなるテーブルの集まりデータベースに対する問い合わせ
基本的なデータベース演算で表せる
テーブルを入力とする演算の出力もまたテーブル

zリレーショナルデータベースから，求める情報を引き出すための基本的な処理選択(selection)• 条件を満たすレコードだけを抜き出す
射影(projection)• テーブルから必要なフィールドだけを切り出す
結合(join)• 共通のフィールドを仲立ちにして複数のテーブルを横につなぐ• 基本リレーショナルデータベース演算の中では最もコストが高い

製品番号

伝票番号

製品番号

10000000001

000001

100000002 ナット

10000000002

0000011000：：：：：：

価格

フィールド000001 ボルト：：

品名レコード：：

：
：

数量

7

データ工学特論（７）822006/1/23
データベース処理の基礎（３）データベース処理の基礎（３）データベース処理の基礎（４）データベース処理の基礎（４）zデータベースにおける高性能化のテクニック
結合処理の効率化• 最もコストのかかる処理をより速くする問い合わせ最適化• よりコストのかからない形式に問合わせを等価変換する
並行処理・並列処理• 複数の問合わせを並行に処理することによって，スループッ
トを上げる

z結合処理の高速化
各テーブルをソートしてから結合する(sort-merge join)
ハッシュを用いてテーブルを分割し探索のコストを下げる(hash join)
結合に用いられるフィールドだけ射影して送り，結合する相手のあるレコードだけ送り返す(semi-join)⇒通信量の削減

sort-merge joinhash-joinsemi-join

サイトA

サイトB

910

結合処理のいろいろ（１）
結合処理のいろいろ（１）

結合処理のいろいろ（２）結合処理のいろいろ（２）z入れ子ループ(nested-loop)結合前処理や補助的なデータ構造を必要としない処理法
O (M×N )for ri in R dofor rj in S do[A]Step 1NM
if ri [A] = rj [A]thenri と rj を結合してStep 2NM
出力に入れるzソート・マージ(sort-merge)結合
２つのテーブルを結合フィールドでソートする
それぞれのテーブルを先頭からスキャンしながら結果を生成各テーブルのソートにO (N log N )．ソート後はO (N )Step 1 O ( N log N )元のテーブルがすでにソートされている場合には，非常に効率がよい上のR をouter table，S をinner tableなどというStep NNM

Step 2 O ( N )現実には，１レコードごとにではなく，ブロック単位でスキャンが繰り返される
11

データ工学特論（７）1232006/1/23
ハッシュ（１）ハッシュ（１）ハッシュ（２）
ハッシュ（２）zもともとは，レコードの特定のフィールドの値が与えられたとき，そのレコードのありかを高速に求めるデータ構成法
フィールドの値に応じて，レコードをいくつかのバケット(bucket)に分割して格納しておく
逆に，値を決めると，そのフィールド値を持つレコードはすべてそのバケットの中にある

zハッシュ結合の利点
結合のために比較すべきレコードを探す手間が少ない
name="Smith"
name="Smith"

ハッシュ構造の一例
テーブル１の中のレコード

フィールド値valueiのレコードは？

"Smith"ハッシュ関数フィールドの値からレコードの存在する場所（範囲）を一意に決定する関数

name="Brown"

バケット
name="Brown"m（固定）"Brown"

テーブル２

総レコード数 N のとき平均 N / m
1314

結合処理のいろいろ（３）結合処理のいろいろ（３）データベース用のデータ構造（１）データベース用のデータ構造（１）z単純ハッシュ結合(simple hash join) [DeWitt 1984]
テーブル１の全レコードの結合フィールドにハッシュ関数を適用し，ハッシュ値に基づいてハッシュ表に登録
テーブル２の各レコードの結合フィールドにハッシュ関数を適用し，そのハッシュ値がハッシュ表に登録されていたら，そこのタプルと結合
O(M＋N)zデータベースには，データの追加・削除が発生
平坦なファイルにレコードをぴっちり詰めて格納すると，削除により「すき間」が発生• 記憶効率の低下は困る→動的なデータ構造が必要
大量のレコードの中から，特定のレコードを高速に見つける必
要がある• 毎回先頭から順にスキャンするのはばかばかしい→何らかの索引構造が必要• どのレコードにもだいたい同じくらいの時間で到達できることが望ましい→たとえば，単純な二分木ではアクセス時間に大きなばらつきが出る

Step 1

Step 2

NM

ハッシュ表（キー値とファイル上のレコードへのポインタだけにすることもある）
15

データ工学特論（７）1642006/1/23
データベース用のデータ構造（２）データベース用のデータ構造（２）データベース用のデータ構造（３）データベース用のデータ構造（３）z単純な二分木にレコードを格納すると…
レコードの挿入順序によっては，木の高さ（深さ）が平衡しない

zB木 (B-Tree) m 分木の一種
 ノードはすべて同じ形（ただし，空の部分も残る）
 ノード内では，レコードは小さい順に整列している
 木の高さが平衡する（どの葉までの距離も等しい）ように挿入・削除を行う

それより大きい
値はこっち

それより小さい
値はこっち×18
このレコードにたどり着くのは大変×10

ファイルの中では以下のように配置されている．
先頭のレコードからリンクをたどって目的のレコードまで行く．

5

7×28

131622

25×33

1718

データベース用のデータ構造（４）データベース用のデータ構造（４）データベース用のデータ構造（５）データベース用のデータ構造（５）zB木 (B-Tree)への挿入
挿入は葉の部分から始める
あふれるときは，ノードを分割し，木を再構築
あふれが治まるまで上に波及

zB木 (B-Tree)からの削除
 削除によりノードが空になるときは，近隣のノードのデータと合わせて再配分
し，木を再構築 再配分で空になるノードが出れば，同様に上に波及前ページの例から「22」を削除する
18 ×
場合，「25」は下に押し上げられ，「26」と同じノード10 ×
25 28にまとめられる．

18105

7

前ページの例に「26」を挿入した例．「22」と「26」のノードに分割され，「25」は上に押し上げられる．

××

13

25

1622×28

26

5×

33

1316

22×28

近隣ノードとデータを再配分した後…
2519×26

×

2つのノードに分割

データ工学特論（７）

7

26

33×33

××20

5

2006/1/23
データベース用のデータ構造（６）データベース用のデータ構造（６）データベース用のデータ構造（７）データベース用のデータ構造（７）zB木の問題点
全レコードをキー値の小さい順にスキャンするのが面倒実際には，レコードは単一の値からなるわけではないので，「キー」となるフィールドの値で索引付けされ，残りのフィールドもノードの中に納めなければならない中間ノードにレコード全体が入るので，木の上のほうもメモリの納まりきれない木の中間ノードにレコードそのものを入れる必要はないのではないか？

zB+木 (B+-Tree)中間ノードにはキー値のみ入れる
レコード本体は葉ノードに入れる葉ノードには，葉ノードどうしを水平に結ぶリンクも付ける

1810

紙面の都合でとが同じ大きさに見えるが，実際はのほうがずっと大きいことに注意

××

25

33

索引部
データ部

5

7

10 13

16 18 22

25 28

2122

データベース用のデータ構造（８）データベース用のデータ構造（８）データベース用のデータ構造（９）データベース用のデータ構造（９）zB+木の利点
中間ノードが小さくなるので，その分，同じノードサイズで m（枝分かれの数）を大きくできる• 枝分かれの数が大きくなると，木は横幅が広がり，高さが小さくなる• 高さが小さくなると，任意のレコードに到達できるまでの最大ディスクアクセス回数が小さくなる中間ノードが小さくなると，索引部がメモリに収まる可能性も出てくるデータ部（末端の葉ノード群）は，索引部と無関係に先頭からスキャン可能

zB木，B+木単一のフィールド（キー）による索引構造
z複数のフィールドに索引が必要な場合
別のファイルとして作成
データ構造は別のものでも構わないただし，挿入・削除の際の処理コストは増える

23

データ工学特論（７）

33 35

24

6

2006/1/23
データベース処理の特性
データベース処理の特性
zリレーショナルデータベース
論理構造（テーブル，レコード）
物理データ構成法（B木，B+木）基本データベース演算（選択，射影，結合）結合処理（入れ子ループ，ソート・マージ，ハッシュ）zデータベース処理特有のディスクアクセスパターンの例
一見ランダムに見えて，実は巨大なデータの全体にアクセス• メモリ容量の制約で，全データをメモリに読み込んで処理できない• 論理的には全レコードのスキャンでよいのに，物理的にはディスクの中を行ったり来たり特定のデータ（索引ファイル，B木の根に近いレコードなど）には，繰り返しアクセス

ディスクの高機能化
ディスクの高機能化

25

今のドライブは何でできている？
今のドライブは何でできている？
z典型的なハードディスクドライブ
プラッタとモータ
ヘッドとサーボ機構
ディスクコントローラチップキャッシュメモリ
zディスクコントローラチップの役割
サーボ機構の制御
エラー訂正SCSIコマンドの処理
z専用チップから汎用のチップへ
zキャッシュの大容量化

プロセッサの比較
プロセッサの比較
約10cm

約14.5cm

zデスクトップ用プロセッサ
最先端の性能
消費電力は多少大きくても構わない複数レベルキャッシュ，分岐予測，複数命令の同時実行やout-of-order実行といった高度な機能を駆使
zディスクコントローラ用プロセッサ数世代前のデスクトップ機なみの性能
消費電力は低い（最新のデスクトップ用の1割以下）
z将来，現在のデスクトップ機並みのCPUとメモリがディスクドライブ内に搭載できるようになると…
OSやアプリケーションまでもディスク側にダウンロード可能？

富士通製 IDE HDDの裏側（1996年製，1GB，厚さ約2.5cm）
古いものなので，まだたくさんのチップが載っているが…

27

データ工学特論（７）

26

28

7

2006/1/23
高機能ディスクの基本的なアイディア
高機能ディスクの基本的なアイディアz現在ホスト側CPUで行われている処理を，ディスク側CPUに肩代わりさせる
キャッシュ管理• 繰り返し読まれる索引ファイ
ルとそれ以外のファイルの差異を考慮データベースレコードに対するスキャン演算• 不要なデータはホストに送らないノード間の通信（！）

高機能ディスク：いくつかの研究
高機能ディスク：いくつかの研究
zアプリケーションの性質に応じたプリフェッチを行う高機能ディスク（東大・喜連川）zディスク側の相互結合網と特殊なデータ構造を利用して負荷分散を行う自律ディスク（東工大・横田）z主にスキャン演算を肩代わりする Active Disk（CMU・Riedel他）
zソーティングやデータキューブ演算まで行う Active Disk（UCSB・Acharya）
z何でもかんでもやるIDISK（UCB・Patterson）

ホスト

CPU

メモリ

メモリ

コントローラディスクドライブ
29

30

アプリケーションに応じたプリフェッチ（２）アプリケーションに応じたプリフェッチ（２）zある問い合わせ処理のためのディスクアクセスパターン（Oracle8）

z何が起きているか？
あるテーブルの索引とデータに交互にアクセスしているため，しじゅうシークを繰り返しているしかも，ホストがデータを受け取ってから次のコマンドを出すまで，ディスク（コントローラ）はヒマになる

論理ブロックアドレス

アプリケーションに応じたプリフェッチ（１）アプリケーションに応じたプリフェッチ（１）次のコマンド発行

コマンド発行
ホスト
データを読むディスク
コントローラ

切断

再接続

転送
ヒマ

デコード
ディスク
経過時間（秒）

データ工学特論（７）

31

シーク

回転待ち

時間
328

2006/1/23
アプリケーションに応じたプリフェッチ（３）アプリケーションに応じたプリフェッチ（３）アプリケーションに応じたプリフェッチ（４）アプリケーションに応じたプリフェッチ（４）zそういうことなら，ホスト側からディスクに対して
このあとどのファイルにアクセスするのか（アクセスプラン）を教えてやるコントローラはヒマな時間にそれをプリフェッチしておく

zプリフェッチ機構を有する高機能ディスク
ディスク側にアクセスポート，コントローラを２つ用意する
外付け

通知

次のコマンド発行

コマンド発行
データを読む切断

ホスト
キャッシュにヒット

再接続 転送

デバイス
ドライバ

DBMS
プロセス

ホスト

ディスク
コントローラデバイス
ドライバ

プリフェッチプロセス

従来のDBMSには変更不要

コントローラコントローラ

キャッシュ

デコード
ディスク

プリフェッチポートDBMSポート

シーク

回転待ち

プリフェッチ

時間

3334

自律ディスク（１）自律ディスク（１）自律ディスク（２）自律ディスク（２）zSAN環境下での運用を想定
各ディスクは，SAN内で相互に（ホストを介さずに）通信できるホストはどれかのディスク（どれでもよい）に処理を依頼
自律ディスクは，自分が持つレコードは自分で処理し，他の自律ディスクが持つレコードは相手に処理を依頼レコードを持つ自律ディスクは，処理の結果をホストに直接返信

zFat B-Tree自律ディスクのための物理データ構造
B木をそのままPEに分散させると，根に近いページを抱えたPEがボトルネックになる
複製を配置• 根に近いノードは多くのPEに複製を配置• 葉に近いページは一部のPEにのみ複製を配置

LAN

SAN

ルートページ第2段
インデックスページ
最終段
インデックスページ

自律ディスク

データページ

PE035

データ工学特論（７）

PE1

PE2

PE3
369

2006/1/23
自律ディスク（３）自律ディスク（３）CMUのCMUの Active
Active Disk
Disk

zホストは，Insert，Delete，Searchといった「高級な」コマンドを発行
zどの自律ディスクもルートページを持っているので，自分のところで検索を始めることができる

z基本的な考え方（Riedel el al.）
特定の応用（データマイニング，画像処理）に必要な，ごく単純な演算をディスク側で実行する
ディスクどうしは直接通信しない

Host 1

直接返答

Host 2

Host 3

ホスト

SAN

カウント，
画像処理 etc.

ホスト

処理済み
データ

処理済み
データ
カウント，
画像処理 etc.

未処理のデータController

Controller

Controller

Controller

Index
Data

Index
Data

Index
Data

Index
Data

CPU
CPU

メモリ

CPU

メモリ

CPU

メモリ

メモリ
未処理のデータ

未処理のデータ

ここにはない！
37

38

UCSBの
UCSBの Active
Active Disk
Disk

UCBの
UCBの IDISKIDISKz基本的な考え方（Acharya et al.）
ホスト側（host-resident）コードとディスク側（disk-resident）コードが協調しながら処理を進めるホスト経由の限定されたものではあるが，ディスク対ディスクの通信も許す
このため，CMU active disk に比べるとさらに複雑な演算も可能になる• 例：ソーティング，グルーピング

z基本的な考え方（Patterson et al.）
分散メモリ型並列計算機上で実行されるプログラムコードを一切合切ディスク側に押し込む
ネットワークネットワーク
CPU

CPU

メモリ

メモリ

CPU

プログラム
メモリ

CPU

CPU

メモリ

メモリ

CPU

プログラム

データ工学特論（７）

CPU

CPU

メモリ

メモリ

メモリ

メモリ

IDISK

ディスク

39

CPU

40

10

2006/1/23
高機能ディスクの比較
高機能ディスクの比較
zCMU，UCSB，UCBの高機能ディスクの比較[Patterson 98]
ディスクで行われる処理の複雑さ

現在はISTOREUCSB
Active Disk

CMU
Active DiskUCBIDISKzOS
zDBMS
z何でもかんでも並列データベースシステム
並列データベースシステム

zフィルタリングzグループ化
zデータキューブ演算zソーティング
z画像処理

zフィルタリングzシーク・アクセススケジューリング

ディスクに追加されるリソースの量
4142

データベースシステムの高性能化の背景（１）データベースシステムの高性能化の背景（１）問い合わせ最適化(query
問い合わせ最適化(query optimization)
optimization)zデータベースにおける高性能化のテクニック
結合処理の効率化• 最もコストのかかる処理をより速くする

z演算の適用順序を変更することにより最適な問い合わせ処理プランを選択処理時間や中間結果の大きさで処理コストを見積もる
問い合わせを等価な他の形式（処理コストの低い形式）に変換
z並列化以前から行われてきた結合演算を遅らせて，中間結果のサイズを小さくする例：– ソートマージ結合– ハッシュ結合

問い合わせ最適化• よりコストのかからない形式に問合わせを等価変換する
並行処理・並列処理• 複数の問合わせを並行・並列に処理することによって，スループットを上げる

43

データ工学特論（７）44112006/1/23
データベースシステムの高性能化の背景（２）データベースシステムの高性能化の背景（２）データベースにおける並列化の目標（１）データベースにおける並列化の目標（１）zデータベースの大規模化・要求の高度化
より大規模でより高性能のデータベースシステムが必要
zハードウェア技術の進歩
CPU ・メモリ・ディスクの高速化・大容量化
急速に進んではいるが，無限に速く無限に大きなものは実現不可能

zスピードアップとスケールアップ
スピードアップ
同じサイズの処理をより短時間で実行できる
理想的には，N 倍のハードウェアを投入して，1 / N の時間で処理したい (linear speedup)
スケールアップ
同じ時間でより大きなサイズの処理が実行できる
理想的には，N 倍のハードウェアを投入して，N 倍の処理を行いたい (linear scaleup)z有限の容量と速度を持つ（安価な）構成要素を無数に集めて，「無限に速く無限大の容量を持つシステム」を構築することはできないか？
z並列性の追求

45

46

データベースにおける並列化の目標（２）データベースにおける並列化の目標（２）

最近のデータベースの使われ方
最近のデータベースの使われ方

zスケールアップの分類
トランザクションスケールアップ
同じ時間でより大きなデータベースに対するより多くの処理要求に対処できる⇒ オンライントランザクション処理（on-line transactionprocessing, OLTP)
バッチスケールアップ
同じ時間でより大きなデータベースに対するより大きな問題に対処できる⇒ オンライン分析処理 (on-line analytical processing, OLAP),
意思決定支援システム (decision-support system)

z意思決定支援企業の経営者が業務内容を分析して，経営戦略の立案に生かす
例：POSデータから消費の動向を探り，商品の企画に生かすz特徴
大量のデータ（ときにはデータベースの全体）をスキャンしなくてはならない
コストの高い演算（テーブルの結合）が多数含まれる
蓄積されるデータが年々巨大化していく
かと言って，毎年システムをリプレースできるほど予算があるわ
けではない
z必要条件
予算を追加すればするほど，その分だけ規模・性能を向上させることができる（スケーラビリティが高い）こと

z今回は，スピードアップやバッチスケールアップのためのアプロー
チを取り上げる
47

データ工学特論（７）48122006/1/23
最も安価でスケーラブルなシステムとは最も安価でスケーラブルなシステムとはクラスタの弱点
クラスタの弱点

zPCクラスタ（PC cluster）通常のPC（もしくはハイエンドPC）をノードとして，高速ネットワー
クにより多数結合するハードウェア的には，デスクトップやラックマウント型のPCとディスクを買ってきて，既設のシステムに追加するだけこのようなシステム（分散メモリ・分散ディスク型，あるいは 完全無共有型 shared-nothing）に適した各種データベースアルゴリズ
ムも開発・実装されてきたzSMPクラスタ（SMP cluster）
シングルCPUのPCの代わりに，SMPをノードに用いる
やや高価

zI/Oバスのボトルネック
SバスやPCIバスの規格がディスクドライブの転送速度の高速化に今後も追いついていけるのか？（技術的な問題というよりは，標準化のスピードの問題）
zシステム管理の手間
z台数が増えたときのパッケージング
ラックマウント型で少し解決
消費電力の問題

4950

データベース処理に内在する並列性
データベース処理に内在する並列性

パーティション型パラレリズムによる並列処理
パーティション型パラレリズムによる並列処理

zデータフローアーキテクチャとの親和性
テーブルを入力とするデータベース演算の出力もまたテーブル
１つの演算の出力を次の演算の入力に
zパイプライン型パラレリズム演算を「縦に」つなぐ
zパーティション型パラレリズム
独立に実行できる
Merge
演算を「横に」並べる
Sort
Sort
Sort
zパーティション型のほうが並列性を抽出しやすい
Scan
Scan
Scan

zデータ分割→データを複数のディスクに分割して格納z分割されたデータの上で，従来の手法を用いて 結合処理

データ

データ

データ

insert into C
select *from
A,Bwhere A.x=B.y

Sort
Scan
データ

非並列の場合の非並列の場合のデータフローグラフ
データフローグラフ
選択と射影は単一の演算としてまとめて処理できる (scan)

Sort
Scan
データ51

データ工学特論（７）

C1

C2

C3

insertinsertinsert

join
join
join

C

元の結合の1/3を担当．
アルゴリズムは非並列のときと同じでよい．

insert
join

scan

scan

AB

scan
scan
scan
A1
A2
A3

並列の場合の並列の場合のデータフローグラフ
データフローグラフ

scan
scan
B1

B2

52

13

2006/1/23
並列処理に適した結合処理方式とは並列処理に適した結合処理方式とはハッシュ結合の並列化
ハッシュ結合の並列化

zデータ分割によって並列性を抽出しようとすると…
入れ子ループ結合• outer tableを分割・分配することはできるが，inner tableは分割できないソート・マージ結合• ソート前に分割しても，結合処理の手間は減らない（結局総あたりになってしまう）• ソート後の分割には，マージそのものと同じくらいコストがかかってしまう

zハッシュ分割結合(hash-partitioned join) の基本的な考え方
それぞれのテーブルを同一のハッシュ関数で分割（初期データが分割されていれば，ここは並列に処理できる）
対応するバケット毎に結合（ここは並列に処理できる）
データの偏りに強いと言われている
Step 3
Step 1

Step 2zもっとうまくデータ分割を行うには…
ハッシュ分割結合

5354

ハッシュ分割結合の処理負荷
ハッシュ分割結合の処理負荷

ハッシュ分割結合のいろいろ（１）ハッシュ分割結合のいろいろ（１）z入れ子ループが O(M×N) の直積空間をくまなく探索するのに対して，ハッシュ分割結合では，対応するバケット同士の部分のみを探索している

z単純ハッシュ分割結合(simple hash-partitioned join)[Gerber 1986]すべてのハッシュ分割を一度には作らず，一対ごとに作っては結合するハッシュ表に登録できなかったレコードは，一時ファイルに登録する
次のハッシュ分割を作るときは一時ファイルから読み出す

入れ子ループの結合処理負荷
結合フィールド１による分割

結合フィールド１の値
結合フィールド２の値

分割ハッシュ結合の処理負荷S
hashjoinR'(⊆R)

R''

hashjoinS' (⊆S)

S''

結合フィールド２による分割
55

データ工学特論（７）

R56

14

2006/1/23
ハッシュ分割結合のいろいろ（２）ハッシュ分割結合のいろいろ（２）GRACEハッシュ結合の並列処理の例
GRACEハッシュ結合の並列処理の例

zGRACEハッシュ結合(GRACE hash join)[喜連川1983]分割フェーズ
各テーブルを同一の関数でハッシュしバッファに格納し，それぞれをディスクに書き込む
照合フェーズ• 一方のテーブルのハッシュ分割をディスクから読み，ハッシュ表を構築• 他方のテーブルの対応するハッシュ分割を１レコード毎にハッシュし，同一のハッシュ値が先のハッシュ表に見つかれば照合を行い，結果を生成する

hash

hash

hash table 1

hash table 2

hash

hash

hash

hash

hash table 3
照合フェーズ
照合フェーズ

hash

HS1
S1

HR1

Result1

R2

hash

HS2
S2

HR2

Result2hashhash table 4hash

hash
hash

分割フェーズ分割フェーズ
hash
hash

R157

hash

hash

R3

HS3
S3

HR3

Result3

R4

HS4
S4

HR4

Result4プロセッサ１でのデータの流れのみ示している．また，プロセッサ間通信もR1の分割のみ表示．

58

ハッシュ分割結合のいろいろ（３）ハッシュ分割結合のいろいろ（３）ハッシュ分割結合のいろいろ（４）ハッシュ分割結合のいろいろ（４）zハイブリッドハッシュ結合(hybrid hash join)[DeWitt&Gerber1984]
分割フェーズで全分割をディスクに書くのではなく，１つはハッシュ表とともにメモリ上に残しておく

zハッシュ分割ループ結合(hashed loops join)[Gerber1986]
入れ子ループ結合の変種• outer table を適当な大きさに分割する• 各分割をひとつずつメモリに読み込み，そのハッシュ表を構築する– inner table のレコードを１つ読み込んではハッシュし，現在メモリ上にあるハッシュ分割と一致するものは結合する

メモリ上のハッシュバケット

• すべての分割について上記の処理を繰り返す
outer tableの各分割について，inner table の全レコードがスキャンされる
ディスク上のハッシュバケット

59

データ工学特論（７）6015