GN ハッシュ結合方式とその評価

概要

論文の詳細を見る
結合演算は関係データベースに特有な演算であり,単純な処理方式ではその処理負荷が高くなるため,近年,効率の良い結合演算処理方式として,演算対象リレーションをハッシュ関数を用いて互いに値の重ならない独立なクラスタに分割し,各クラスタごとに結合演算処理を行うハッシュ結合方式が提案されている.ハッシュ結合方式は,リレーションが主記憶よりはるかに大きい場合従来のネストループ結合方式と比較して,その処理コストは小さい,しかしながら,ネストループ結合方式の入出力コストがデータ分布の偏りによらず一定であるのに対し,ハッシュ結合方式では,ハッシュ関数による分割後のクラスタのサイズを予測することは難しい.本論文では,主記憶の数倍程度の比較的小容量のリレーションに対してはネストループ結合方式がハッシュ結合方式より性能が良いこと,結合演算処理コストのほとんどが入出力コストで占められていることに着目し,実行時にネストループ結合方式とGraceハッシュ結合方式の二つから入出力コストの小さい方式を選択するGNハッシュ結合方式を提案する.本方式では,データ分布の偏りによりクラスタが主記憶に収まるように均等に分割できない場合にも,主記憶から溢れたクラスタに対して再帰的に二つの方式から入出力コストの小さいものを適用するため,従来のGraceハッシュ結合方式やハイブリッドハッシュ結合方式と比較し,より高い性能が期待される.メモリの数十倍の大容量リレーションを用い,Zipf-like頻度分布を用いてメモリに収まらないクラスタが生ずる場合に関し性能評価を行い,GNハッシュ結合方式の有効性を明らかにした.また,GNハッシュ結合方式はバッファ管理が極めて簡単であり,現在多用されているハイブリッドハッシュ結合方式と比較して実装が容易であるという特徴を有する.
一般社団法人情報処理学会の論文
1994-09-15

GN ハッシュ結合方式とその評価

スポンサーリンク

概要

著者

関連論文

スポンサーリンク