プログラミング

GROUP BYは長年最適化されてきたが、まだ最適化の余地はあるか？

Can GROUP BY still be optimized after all these years? (pivotlake.io)

111 pointsby ntur13372026年11月4日17 コメント

要約

データベースにおけるGROUP BYクエリの最適化、特にトップK集計のパフォーマンス向上について解説しています。従来のGROUP BY処理では不要な計算が多く発生していましたが、パーティションごとにスロットを設けて集計値を管理する新しい手法により、不要なパーティションのマージを大幅に削減し、クエリパフォーマンスを向上させる方法を提案しています。

全文翻訳

GROUP BYは長年最適化されてきたが、まだ最適化の余地はあるか？

データベースの世界で私が最も好きなことの一つは、単純な操作がいかにして最高レベルで最適化されると極めて複雑になりうるか、ということです。

その考えに基づき、最近発見したPivotのパフォーマンスを大幅に向上させた、集計値でトップKグループを見つけるGROUP BYクエリに関する新しい最適化について共有するのは、興味深く楽しいことだろうと思いました。例えば、「最も注文が多い上位10件のアイテムはどれか？」といったクエリです。

SELECT item_id, COUNT(*) AS c
FROM orders
GROUP BY item_id
ORDER BY c DESC
LIMIT 10;

アナリティカルデータベースでは「通常の」GROUP BYはどのように実行されるか？

どのデータベースもユニークでありたいと思っていますが、ほとんどのデータベース（Pivotも含む ;)）は、グルーピングキーのカーディナリティが高い場合（つまり、GROUP BYに多くのグループがある場合）には、非常に似た方法でGROUP BYを実行します。

まず、データベースの各CPUスレッドは、ディスクからデータを読み込み、デコードし、集計の準備をするためのデータスライスを受け取ります。

BASE DATAslice 1slice 2slice 3slice 4CPU thread 1fetch + decodedecoded rowsCPU thread 2fetch + decodedecoded rowsCPU thread 3fetch + decodedecoded rowsCPU thread 4fetch + decodedecoded rows

次に、各スレッドはデコードしたデータをグルーピングキーに基づいてX個のパーティションに分割し、各パーティションを個別に集計します。例えば、ClickHouseは256個のパーティションを使用するため、各スレッドはパーティションごとに1つずつ、256個のハッシュテーブルのセットを維持します。

decoded rowsCPU thread 1P0hash tableitem_3f1a12item_c91d4……P1hash tableitem_5d489item_a81c2……P2hash tableitem_9b037item_02be1……⋮P15hash tableitem_d81e3item_7a468……decoded rowsCPU thread 2P0hash tableitem_d2a46item_42d12……P1hash tableitem_9ab78item_f36c1……P2hash tableitem_71d93item_0e8511……⋮P15hash tableitem_7e205item_e4c73……decoded rowsCPU thread 3P0hash tableitem_6e7f10item_b05e1……P1hash tableitem_a9135item_c0582……P2hash tableitem_2f4a3item_7d616……⋮P15hash tableitem_b7d22item_5c6f4……decoded rowsCPU thread 4P0hash tableitem_8f3a4item_1c772……P1hash tableitem_40bd7item_ee911……P2hash tableitem_35af2item_c6d05……⋮P15hash tableitem_9c3b1item_e1a89……

Pivotはここでハッシュテーブルの代わりに異なる手法を使用していますが、それは別のブログ記事のネタです ;)

これらのハッシュテーブルを各スレッドにプライベートに保つことで、スレッドはロックを取得したり同じメモリ位置に書き込んだりすることなく、データを独立して集計できます。これにより、CPUキャッシュ間の競合が発生しなくなります。

すべてのスレッドがこの初期集計を完了すると、各ワーカーにはマージするパーティションの範囲が割り当てられます。各パーティションについて、ワーカーはすべてのスレッドによって生成された部分的な集計値を収集し、それらをそのパーティションのグループの最終的な集計値と結合します。

PARTITIONSmergedmergingwaitingP0P1P2P3range P0–P3P4P5P6P7range P4–P7P8P9P10P11range P8–P11P12P13P14P15range P12–P15CPU thread 1merging P1CPU thread 2merging P5CPU thread 3merging P9CPU thread 4merging P13

すべてのパーティションがマージされると、データベースはすべてのパーティションの結果を連結することで、完全なGROUP BY結果を生成します。

CPU thread 1merged P0–P3P0P1P2P3CPU thread 2merged P4–P7P4P5P6P7CPU thread 3merged P8–P11P8P9P10P11CPU thread 4merged P12–P15P12P13P14P15groupCOUNT(*)
user_8f3a1c41user_02be777user_c91d4018……

これらの作業は本当に必要か？

このプロセスは確かに正しい結果を出力しますが、いくつかの（非常に一般的な）クエリパターンでは、このGROUP BYアルゴリズムは実際には必要以上に多くの作業を実行します。具体的には、集計結果のすべてが最終的な回答で使用されないクエリでは、多くのグループやパーティションが集計されますが、実際には必要ありません。

先ほどの例を挙げましょう。「最も注文が多い上位10件のアイテムはどれか？」

SELECT item_id, COUNT(*) AS c
FROM orders
GROUP BY item_id
ORDER BY c DESC
LIMIT 10;

システムが4,096個のパーティションを使用している場合、上位10件のアイテムは最大でも10個のパーティションに属する可能性があります。これは、少なくとも4,086個のパーティションの結果が最終的な回答に全く貢献しないことを意味します。それにもかかわらず、それらをマージするために多くの時間と計算リソースを費やしています。

このパターンのクエリは、私たちが目にするワークロードではかなり一般的です。「倉庫にある上位100件のアイテムのレビュー評価は最も高いか？」「最も多く支払っている上位50名の顧客は誰か？」「過去24時間で最も多くの「いいね！」を獲得したプラットフォーム上の投稿はどれか？」これらを考慮すると、これらのクエリを最適化できるかどうかを検討する価値があると考えました！

では、どのようにしてこれらの作業を回避できるか？

この冗長な作業の問題を解決するために、集計フェーズを進めながらパーティションをいくつか枝刈りするのに役立つ構造を探しました。ブルームフィルター（そしてi-love-bloom-filters.comの誇り高い所有者！）を大いに愛している私たちは、確率的でハッシュベースの構造がこの目標を達成するのに役立つと考えました。

私たちが考えた最も「素朴な」実装は、単に各パーティションのグローバルカウンターまたは集計値を維持し、後でどのパーティションをスキップするかを決定するためにそれを使用することでした。

「注文が多いアイテム」クエリの場合、これは各パーティションの注文総数をカウントすることを意味します。

PARTITIONSP0orders1,284P1orders1,500P2orders3,402P3orders2,130P4orders1,500P5orders1,116P6orders977P7orders1,221P8orders1,498P9orders2,017P10orders1,133P11orders1,390P12orders1,725P13orders1,033P14orders1,508P15orders1,377

マージステージ中に、新しいパーティションをマージする前に、その総注文数を現在のトップK結果の最小値と比較できます。

パーティションの合計がそれより小さい場合、マージを完全にスキップしても安全です。なぜなら、個々のグループの注文数がパーティション全体よりも多くなることはないため、そのグループのどれも現在のトップK結果に影響を与えることはないからです。

PARTITIONSwaitingprunedmergingmergedP0orders1,284P1orders1,500P2orders3,402P3orders2,130P4orders1,500P5orders1,116P6orders977P7orders1,221P8orders1,498P9orders2,017P10orders1,133P11orders1,390P12orders1,725P13orders1,033P14orders1,508P15orders1,377CPU thread 2Current TopKORDER BY c DESC LIMIT 10#itemc#1item_3b6d1,300#2item_e9a11,271………#10item_7b2f1,000P6: 977 < 1,000→ pruned, never merged

ただし、パーティションの合計が大きい場合は、それをマージして重いCPU作業を行い、そのグループのいずれかが実際にトップK結果に影響を与えるのに十分大きいかどうかを見つける必要があります。

このアプローチは非常にクールで、一部のシナリオではパーティションを枝刈りするのに役立ちますが、集計値がグループ間で非常に偏っている必要があります。

パーティションを枝刈りするには、そのグループ全体の平均集計値が、現在のトップKの最小値よりも桁違いに小さくなければなりません。

例えば、計算された上位10件の注文数が現在1,000から1,300の範囲にあると仮定します。各アイテムがちょうど15件の注文を持つ100個のアイテムを含むパーティションがあるとします。このパーティションの合計は1,500件の注文であり、私たちのトップKの最小値を超えています。しかし、そのグループのどれもそれに近づいていません。このため、私たちの枝刈りロジックではスキップできません。

私たちの枝刈りロジックは各パーティションの総注文数のみを考慮するため、2つのケースを区別できません。1. 各アイテムが15件の注文を持つ100個のアイテム（安全に枝刈りできるはず）と、2. 各アイテムが1件の注文を持つ99個のアイテムと、1件のアイテムが1,401件の注文を持つ1個のアイテム（このアイテムがトップKに含まれる可能性があるため、マージする必要がある）。両方のパーティションには1,500件の注文が含まれていますが、2番目のパーティションのみが結果を変更する可能性のあるアイテムを含んでいます。

Current TopKORDER BY c DESC LIMIT 10#itemc#1item_3b6d1,300#2item_e9a11,271………#10item_7b2f1,000Partition A100 items × 15 ordersitemordersitem_42d115item_9ab715item_f36c15item_71d915……NOT PRUNABLEtotal 1,500 ≥ 1,000Partition B99 items × 1 + 1 item × 1,401itemordersitem_0e851item_b7d21item_a9131,401item_5c6f1……NOT PRUNABLEtotal 1,500 ≥ 1,000

これを克服するために、同じアイデアに基づいた方法を探しましたが、枝刈りの粒度についてより多くの制御ができるようにしました。

私たちが考案した方法は、各パーティションに固定数の「スロット」を与えることでした。各グループは1つのスロットにマッピングされ、そのスロットはマッピングされたすべてのグループの合計注文数を追跡します。グループのカウントがそのスロットの合計を超えることはないため、すべてスロットの合計が現在のトップKの最小値よりも小さい場合にパーティションを安全に枝刈りできます。

例えば、現在のトップ注文数が再び1,000から1,300の範囲にあると仮定します。各アイテムが15件の注文を持つ100個のアイテムを含むパーティションは合計1,500件の注文を持つため、パーティションレベルのカウンターだけでは枝刈りできません。しかし、それらのアイテムが8つのスロットにほぼ均等に分散されている場合、各スロットには約180〜195件の注文しか含まれず、これによりパーティション全体を枝刈りできるようになります :)

Current TopKORDER BY c DESC LIMIT 10#itemc#1item_3b6d1,300#2item_e9a11,271………#10item_7b2f1,000Partition A100 items × 15 ordersslotcounterwhat each counter adds up (not stored)00019513 items × 15 orders00118012 items × 15 orders01019513 items × 15 orders01118012 items × 15 orders10019513 items × 15 orders10118012 items × 15 orders11019513 items × 15 orders11118012 items × 15 ordersPRUNABLElargest slot 195 < 1,000Partition B99 items × 1 + 1 item × 1,401slotcounterwhat each counter adds up (not stored)0001212 items × 1 order0011313 items × 1 order0101,41312 items × 1 + item_a913 (1,401)0111212 items × 1 order1001313 items × 1 order1011212 items × 1 order1101212 items × 1 order1111313 items × 1 orderNOT PRUNABLElargest slot 1,413 ≥ 1,000

パーティションの枝刈りに使用するのと同じハッシュを使用して、グループをスロットに割り当てることができます。例えば、グループIDのハッシュの最初の3ビットが8つのパーティションのいずれかを選択する場合、次の3ビットはそのパーティション内の8つのスロットのいずれかを選択できます。

rowitemhash: partition | slot1item_3f1a101 011…2item_c91d101 000…3item_5d48101 110…4item_3f1a101 011…5item_a81c101 000…6item_9b03101 101…7item_02be101 011…8item_7e20101 110…9item_c91d101 000…10item_e4c7101 111…11item_3f1a101 011…12item_a81c101 001…13item_5d48101 110…14item_9b03101 101…15item_d2a4101 011…………slotcounter00030011010001151000101211031111ROWS OF PARTITION P5 (hash bits 101…)P5's vector: 2³ = 8 slots

面白いのは、スロットの数はパーティションの数とは独立していることです。パーティションが多すぎるオーバーヘッドを維持することなく、値の「広がり」の度合いに基づいた、より細かい粒度のカウントビューを得るために、より多くのスロットを追加できます。

値の分布が非常に平坦なシナリオ（例えば、すべてのアイテムが同じ注文数を持つ場合など）では、この最適化が全く効果がない場合があり、エンジンはこの種のデータセット分布を検出したときにこの最適化を無効にすべきです。

結果

理論は常に楽しいですが、今はお金の話をしましょう。

内部ワークロードでの大幅な改善に加えて、このアプローチの利点は公開ベンチマークでも現れています。例えば、ClickBenchのクエリのほとんど（63%！）は、GROUP BYの後に集計結果に対するORDER BYが続くこのパターンを含んでおり、Pivotではこの最適化によってパフォーマンスが向上します。

例えば、このパターンを持つ最も単純なクエリの1つ（Q16）では、次のようになります。

SELECT UserID, SearchPhrase, COUNT(*)
FROM hits
GROUP BY UserID, SearchPhrase
ORDER BY COUNT(*) DESC
LIMIT 10;

このアプローチにより、35.6ミリ秒から22.2ミリ秒へと1.6倍の速度向上が見られ、実行中に70%以上のパーティションが枝刈りされました。

before35.6 mswith partition pruning22.2 ms1.6× faster· more than 70% of the partitions were pruned without being merged

このアプローチは、集計が完全にメモリに収まる場合にすでに大きなブーストをもたらしますが、PivotがMPPとディスクへのスピル機能を追加すると、さらに大きなメリットが得られると考えています。なぜなら、パーティション全体をスキップすることは、シャッフルとディスクI/Oを大幅に節約することにもなるからです！