「メインメモリ上での13の等価結合手法の実験的比較」を読む

日本におけるデータベースの大家である kumagi さんが「An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory」という論文を紹介していた。

13種類のJoinアルゴリズムを比較ベンチしたよという論文。800万行以上ではパーティション分割を使うべき。HugePageやSWWBなどのテクニックは侮れない。NUMA環境対応の奴はでかいJOINで特に速い。マテリアライズ等のJOIN以外の計算コストでクエリ全体では遅くなったりする。 https://t.co/i2kSE8fF4w pic.twitter.com/igbgJTA3Vm

— kumagi (@kumagi_bot) 2023年2月2日

システム開発の実務においても、プロジェクト後半になると著しくパフォーマンスの悪いクエリが見つかりパフォーマンス・チューニングをせざるをえない状況が多く発生する。このような場合、ヒント句を使い結合方法を変更するというのは割と重要なテクニックのひとつであるため、大変興味をそそられる内容だ。*1

論文中では詳細な分析がなされているが、結論的なものが「LESSONS LEARNED（教訓）」という節にまとまっているので、その部分を抜粋しておく（ほとんど kumagi さんの要約で尽きてる感はありますが）。

1. 小さい入力に対し CRP* アルゴリズム（パーティションを使い並列で結合する手法群）を使うな
   
   • 800万件以下だとスレッド化やデータが複数のページに分かれるコストの方が大きくなる
2. 実験に使う設定は明確にしろ（省略）
3. 大規模な結合に際し、パーティション化すべきか迷うようならパーティション化しろ
   • パーティション化することでパフォーマンスが劣化することはほとんどない。
4. 結合に使うページサイズは大きくしろ
   • 4KB から 2MB に変えると 10～20%ほどスループットが向上
5. ソフトウェアベースの Write Combine Buffer を使え（省略）
6. パーティションベースのためのアルゴリズムには適切なパーティションビット数を使え（省略）
7. 可能な限りシンプルなアルゴリズムを使え
   • シンプルなアルゴリズムを使った方が、結果的に高速でメモリ消費も少ないとのこと
     （大量件数を処理するので、そういう結果になるのもわかる気がします）
8. NUMA を意識しろ（省略）
9. 結合時間がクエリの時間というわけではないので注意しろ
   • 結合時間は全体の10～15%しか占めない
     （一般論としてはそうだけど、これは場合によるのでは。索引なしの結合から索引のありの結合に変えれば大きく変わるし、Oracle Exadataだとネステッドループ結合をハッシュ結合に変えただけで劇的に高速化することもよくある）

*1:オーソドックスな改善手法としては結合項目にインデックスを張れだけど、それ以上にパフォーマンス改善が必要な場合には、クエリの改善、インデックスの固定、結合方法の変更、結合順序の固定、パーティション化などの方法を取るのが一般的な流れだと思う。