並列ハッシュ結合
avashe.icon
並列データベ ースの概念と原理
がエモかったのでシェア
データベース
において、一つの
SQL
文は、あるテーブルに対して一つの木構造を成す
木が分かれている経路はカラム毎に並列処理できる
合流している所、つまり
join
(
結合処理
)はどうするか?
並列
ハッシュ
結合(
Parallel Hash Join
)を使う
結合時の比較回数を減らすハッシュ結合という手法に偏りが少ないハッシュを適用すれば直ちに並列化できる
ハッシュ値の偏りに対処した
手法の提案
もあるらしい
このまま
分散システム
に応用することもできる
ハッシュの性質により
Bin packing probrem
をあまり気にせず解決できるのが強い
ただしハッシュによってbinに分散する方法(Hash partitioning)は範囲問い合わせを難しくする
並列ハッシュ結合は更に
MapReduce
に帰着する
Apache Hive
は
Apache Hadoop
にこの辺の知見を併せることでSQL処理系を実現しているらしい
他には
Google BigQuery
なども
#Algorithm
#Distributed_Systems