この記事の趣旨
2013年に発表された"Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited"という論文を読みました。 当時最新のアルゴリズムとハードウェアにおける、ソートとハッシュによる結合のパフォーマンスを比べた論文です。
Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited
著者について
Cagri Balkesen、Gustavo Alonso、Jens Teubner、M. Tamer Ozsuらのグループによる論文 いずれもDBMSにおけるクエリ最適化やビッグデータにおけるパフォーマンスを研究している。 またGustavo Alonsoはハードウェアや分散システムもメインのフィールドとしている。
問題意識
DBMSにおいて常にソートマージとハッシュ結合の性能比較が行われており、 最新の研究ではSIMDやNUMAへの適正に基づいてソートマージがより優れている と結論づけられていた。
しかしこれらの分野は常に研究が重ねられ、過去の検証時には登場していなったハッシュ結合の 最適化手法が生れた。
この論文ではそれらを適用し再度ソートマージとハッシュ結合の性能比較を行なう。
手法
本論文では以下に分けて結合手法の評価を行なっている。 1. ソートフェーズの評価 AVXを用いて実装したSIMDソートアルゴリズムとC++のSTLソートアルゴリズムを比較している。
マージフェーズの評価 異なる入力サイズにおけるマージのパフォーマンスを検証している。
入力サイズの調整によるマージフェーズの最適化 入力サイズとパーティショニングによるソートのパーマンスを検証している。
ソートマージジョインにおける影響要因の特定 ソートマージジョインにおける性能に影響を与える要因を特定し、あらたな最適化方法を 検討している。
結果
結合対象のデータサイズに拘わらずハッシュによる結合がソートベースの結合のパフォーマンスを上回っている。
Figure 14 ソートマージによる結合は入力サイズが著しく大きくなったときのみハッシュ結合のパフォーマンスに近づく。
Figure 15 ソートマージ、ハッシュ結合におけるデータの偏りはパフォーマンスに大きな影響を及ぼさなかった。
Figure 16 いずれのアルゴリズムも物理的なコア数では線形にスケールした。
Figure 17
作業時間
- read
- 23:11
- 23:11
- author
- 27:09
- 3:58
- summary
- 60:12
- 32:57
