Closed stonewhitener closed 1 year ago
分析データベースにおけるリレーショナルデータのソートについてマイクロベンチマークを行い，効率的なソート戦略を検討．カラムでソートするよりも行でソートするほうがキャッシュを効率的に使うことができ，また，条件分岐を減らせることを明らかにした．マイクロベンチマークの結果を踏まえて効率的なソートを DuckDB に実装．ベクトル形式をキーとペイロードでそれぞれ行形式に変換し，文字列を含む場合は pattern-defeating quicksort，含まない場合は radix sort を使用して，パイプラインで並列にマージソートを実行し，ベクトル形式に戻す．カラム形式の MonetDB や ClickHouse，実行時コンパイルと行形式を採用する Umbra や HyPer と比較して，高性能あるいは同等の性能となることを示した．
Resources
Summary
分析データベースにおけるリレーショナルデータのソートについてマイクロベンチマークを行い，効率的なソート戦略を検討．カラムでソートするよりも行でソートするほうがキャッシュを効率的に使うことができ，また，条件分岐を減らせることを明らかにした．マイクロベンチマークの結果を踏まえて効率的なソートを DuckDB に実装．ベクトル形式をキーとペイロードでそれぞれ行形式に変換し，文字列を含む場合は pattern-defeating quicksort，含まない場合は radix sort を使用して，パイプラインで並列にマージソートを実行し，ベクトル形式に戻す．カラム形式の MonetDB や ClickHouse，実行時コンパイルと行形式を採用する Umbra や HyPer と比較して，高性能あるいは同等の性能となることを示した．