GROUP BYは今なお高速化できるのか、PivotがTop-K集計で70%のパーティションを削減
Can GROUP BY still be optimized after all these years?
Pivotのエンジニアが、GROUP BYとORDER BY ... LIMITを組み合わせたTop-K集計クエリの新最適化を紹介。各パーティションに固定数の「スロット」を持たせ、全スロットの合計が現在のTop-Kの最小値より小さければパーティション全体のマージを省略する仕組みだ。ClickBenchのQ16では35.6msから22.2msへと1.6倍高速化し、70%以上のパーティションを枝刈りできたという。
もしそのパーティションの合計が小さければ、マージを完全にスキップできます。個々のグループがパーティション全体より多くの注文を持つことはあり得ないため、そのグループのどれも現在のTop-K結果に影響を与えられません。
- malisper
いいね！他の人のために言うと、彼らが説明しているデータ構造はcount-min sketchだ。これを使ってgroup-byに入れる要素の上限を設定し、余計な作業をたくさんスキップしているようだ。
- ozgrakkurt
彼らのclickbenchの結果は本当に良さそうだ。
https://benchmark.clickhouse.com/#system=+liH|Hoaus|DcD|ucqs...
- toddbandrowsky
いやあ、データセットをネットワーク越しに流すよりも、グループ化した結果だけを送る方が安く済むなんて、どうにも想像しにくいんだよな。そこが本当の問題なんだ。つまり、あるマシン上でgroup byするのに100nsかかるとして、そのデータがそこに届いて戻ってくるのに10倍かかるなら、誰が気にするんだって話だ。
可能な限り最速のgroup byは、そのマシン上のシーケンシャルメモリ内で、NVMeから取得したデータに対して行うものだ。
だから、group byパーティショニングを行うとき、私たちは実際にはグループ自体を別々のマシンに置き、そのgroup byをグループ化しようと言っているわけだ。それがとんでもない巨大データセットなら、置くべき場所はメインフレームで、それは基本的に馬鹿げた大きさのデータセットに対するgroup byのために作られたものだ。