PolarDB:IMCI における GroupJoin 演算子の実装

背景情報

SELECT
  key1,
  SUM(sales) as total_sales
FROM
  fact_table LEFT JOIN dimension_table ON fact_table.key1 = dimension_table.key1
GROUP BY
  fact_table.key1
ORDER BY
  total_sales
LIMIT 100;

PolarDB IMCI では、上記のようなクエリの実行計画は、通常、最初に HASH JOIN を実行し、次に key1 に対して HASH GROUP BY を実行します。どちらの操作も key1 上にハッシュテーブルを構築します (fact_table.key1 = dimension_table.key1 であることに注意してください)。実行計画は以下の通りです：

1. HASH JOIN：dimension_table.key1 上にハッシュテーブルを構築し、fact_table.key1 でプローブして、一致するデータを出力します。

2. HASH GROUP BY：fact_table.key1 上に別のハッシュテーブルを構築し、ハッシュテーブルへの書き込み中に集約を実行します。

パフォーマンスの観点から、これら 2 つの操作は 1 つに融合できます。つまり、集約を実行しながら dimension_table.key1 上にハッシュテーブルを構築し、次に fact_table.key1 でプローブして集約を続行します。 これにより、fact_table.key1 上にハッシュテーブルを構築するために必要な時間が節約されます。HASH JOIN と HASH GROUP BY 演算子をマージしたこの融合操作は、GroupJoin 演算子と呼ばれます。

これら 2 つの操作を融合することで、ハッシュテーブルの構築が 1 回不要になります。また、中間結果のサイズも削減されます。JOIN 操作は、あるテーブルの 1 行が別のテーブルの複数行に一致する可能性があるため、結果セットを拡張する可能性があります。最悪のシナリオでは、デカルト積が発生します。つまり、N 行のテーブルと M 行のテーブルを結合すると、最大で N×M の結果セットが生成される可能性があります。標準的な HASH JOIN の後に HASH GROUP BY を実行する場合、N 行のハッシュテーブルから N×M×S 行 (S は選択性、0 ≤ S ≤ 1) が出力される可能性があります。これらの行はその後、新しいハッシュテーブルに集約され、リソースの無駄遣いになります。前述の例のように、大きなファクトテーブル (M 行) と小さなディメンションテーブル (N 行) の間で key1 が一意キーである LEFT OUTER JOIN を行う場合でも、HASH JOIN からは M 行が出力され、それらが新しいハッシュテーブルに集約されます。対照的に、GroupJoin 演算子は、最初の N 行のハッシュテーブル内で結合と集約を完了させるため、中間結果とメモリ消費の両方を削減します。

これらの考慮事項に基づき、PolarDB for MySQL は PolarDB IMCI に GroupJoin 演算子を追加しました。

アルゴリズム設計

概要

IMCI の GroupJoin 実装は、HASH JOIN と HASH GROUP BY 演算子を融合します：

1. まず、左テーブル (小さい方) からハッシュテーブルが構築されます。左テーブルを参照する集計関数は、このビルドフェーズで評価されます。このプロセスは、左テーブルの集約 (例：HASH GROUP BY left_table) と同等です。

2. 次に、右テーブル (大きい方) を使用してハッシュテーブルがプローブされます。一致した場合、右テーブルを参照する集計関数が対応するハッシュテーブルエントリで評価されます。それ以外の場合、行は結合タイプに応じて破棄されるか、直接出力されます。

以下のセクションでは、IMCI の GroupJoin アルゴリズムについて詳しく説明し、考えられる簡略化について議論します。

制限事項

実装を管理しやすくするため、PolarDB for MySQL の GroupJoin 実装には、完全に一般化された実装と比較して、以下の制限があります：

1. GROUP BY キーは結合キーでなければならず、どちらか一方のテーブルのキーと完全に一致する必要があります。結合キーのサブセットがキーを一意に識別できる場合 (つまり、関数従属性) はサポートされていません。

2. RIGHT JOIN, GROUP BY RIGHT のシナリオでは、右側のキーは一意でなければなりません。そうでない場合、オプティマイザーはクエリを LEFT JOIN, GROUP BY LEFT に書き換えるか、GroupJoin 演算子の使用を避ける可能性があります。

3. 任意の集計関数は、左テーブルまたは右テーブルのいずれかの列のみを参照でき、両方を参照することはできません。SELECT リスト内の集計関数が SUM(t1.a + t2.a) のように両方のテーブルの列を参照する場合、GroupJoin 演算子は適用されません。

アルゴリズム

INNER JOIN/GROUP BY LEFT

このシナリオは、次の SQL ステートメントで示されます：

l_table INNER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

1. 左テーブルからハッシュテーブルを構築し、ビルド中に左テーブルを参照する集計関数を評価します。右テーブルを参照する集計関数については、「リピートカウント」を維持します。これは、特定のハッシュテーブルエントリに対して一致するプローブ側の行数を表します。

2. 結合中に、右テーブルでハッシュテーブルをプローブします。右テーブルの行が一致を見つけられない場合、その行は破棄されます。一致が見つかった場合は、左テーブルの集約コンテキストでリピートカウントを増分し、右テーブルを参照する集計関数を評価します。

3. 結合が完了した後、一致したハッシュテーブルエントリに対してのみ集約結果を出力します。一致しなかったエントリは無視されます。

4. 集約結果を出力する際、リピートカウントを考慮します。たとえば、左テーブルの SUM(expr) の結果が 200 で、そのリピートカウントが 5 の場合、最終結果は 1000 になります。

INNER JOIN/GROUP BY RIGHT

このシナリオは、次の SQL ステートメントで示されます：

l_table INNER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

l_table.key1 = r_table.key1 であるため、このケースは INNER JOIN/GROUP BY LEFT シナリオとして処理されます。

LEFT OUTER JOIN/GROUP BY LEFT

このシナリオは、次の SQL ステートメントで示されます：

l_table LEFT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

1. 左テーブルからハッシュテーブルを構築し、ビルド中に左テーブルの集計関数を評価します。右テーブルの集計関数については、リピートカウントを維持します。

2. 結合中に、右テーブルでハッシュテーブルをプローブします。右テーブルの行が一致を見つけられない場合、その行は破棄されます。一致が見つかった場合は、左テーブルの集約コンテキストでリピートカウントを増分し、右テーブルを参照する集計関数を評価します。

3. 結合が完了した後、一致したハッシュテーブルエントリの集約結果を出力します。INNER JOIN とは異なり、一致しなかった各ハッシュテーブルエントリも結果を生成します。それは別のグループを形成し、右テーブルを参照する対応する集計関数の入力は NULL になります。

LEFT OUTER JOIN/GROUP BY RIGHT

このシナリオは、次の SQL ステートメントで示されます：

l_table LEFT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

1. 左テーブルからハッシュテーブルを構築し、ビルド中に左テーブルの集計関数を評価します。右テーブルの集計関数については、リピートカウントを維持します。

2. 結合中に、右テーブルでハッシュテーブルをプローブします。右テーブルの行が一致を見つけられない場合、その行は破棄されます。一致が見つかった場合は、左テーブルの集約コンテキストでリピートカウントを増分し、右テーブルを参照する集計関数を評価します。

3. 他のシナリオとは異なり、結合が完了した後、一致したハッシュテーブルエントリの集約結果を出力します。一致しなかったすべてのハッシュテーブルエントリは単一のグループを形成し、右テーブルを参照する対応する集計関数の入力は NULL になります。

RIGHT OUTER JOIN/GROUP BY LEFT

このシナリオは、次の SQL ステートメントで示されます：

l_table RIGHT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

1. 左テーブルからハッシュテーブルを構築し、ビルド中に左テーブルの集計関数を評価します。右テーブルの集計関数については、リピートカウントを維持します。

2. 他のシナリオとは異なり、結合中に右テーブルでハッシュテーブルをプローブします。一致が見つかった場合は、左テーブルの集約コンテキストでリピートカウントを増分し、右テーブルを参照する集計関数を評価します。一致がない場合は、すべての右テーブルの一致しなかった行が単一のグループを形成し、左テーブルの集計関数の結果は NULL になります。

3. また、他のシナリオとは異なり、結合が完了した後、一致したハッシュテーブルエントリの集約結果を直接出力します。一致しなかったハッシュテーブルエントリはすべて無視されます。

RIGHT OUTER JOIN/GROUP BY RIGHT

このシナリオは、次の SQL ステートメントで示されます：

l_table RIGHT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

制限事項

キー r_table.key1 は一意でなければなりません。そうでない場合、この結合は無効です。r_table.key1 が一意であることを保証できない場合、オプティマイザーはこの結合とグループ化操作を LEFT OUTER JOIN と GROUP BY LEFT に変換する必要があります。

手順

1. 左テーブルからハッシュテーブルを構築し、ビルド中に左テーブルの集計関数を評価します。右テーブルの集計関数については、リピートカウントを維持します。

2. 他のシナリオとは異なり、結合中に右テーブルでハッシュテーブルをプローブします。一致が見つかった場合は、両方のテーブルの集約結果を直接出力します。一致がない場合も集約結果を出力しますが、左テーブルの集計結果はすべて NULL になります。

3. 他のシナリオとは異なり、GroupJoin 操作は結合が終了した直後に完了します。ハッシュテーブルエントリのさらなる処理は必要ありません。

ランタイムスピリングの処理

GroupJoin のスピリングは、HASH JOIN および HASH GROUP BY 演算子で使用されるパーティションベースのスピリングに似ています。メソッドは次のとおりです：

1. 全体的な GroupJoin アルゴリズムは、パーティションベースのアプローチを使用します。

2. 左テーブルからハッシュテーブルを構築する際、インメモリパーティションのアルゴリズムは「アルゴリズム」セクションで説明したものと同じです。

3. ハッシュテーブルのビルド中に、メモリに収まらないパーティションはディスク上の対応する一時ファイルにスピルされます。これらのパーティションの新しいデータも直接これらのファイルに書き込まれます。スピルされた各パーティションに対してブルームフィルターが作成され、プローブフェーズで一致する可能性のない右テーブルのデータを迅速にフィルタリングします。

4. 左テーブルのハッシュテーブルが構築された後、右テーブルのデータを使用してプローブします：

   1. プローブ中に、対応するパーティションがメモリ内にある場合、「アルゴリズム」セクションで説明されているように処理されます。パーティションがメモリ内にない場合は、まずブルームフィルターを確認します。データがブルームフィルターと一致しない場合は、破棄するか直接出力します。それ以外の場合は、データをそのパーティションの一時ファイルにスピルします。

   2. すべてのインメモリパーティションが処理された後、ディスク上のパーティションを 1 つずつ処理します。これは、少なくとも 1 つのパーティションがメモリに収まることを前提としているため、さらなる再パーティション分割は必要ありません。処理アルゴリズムは、「アルゴリズム」セクションで説明されているものと同じです。

関連研究

2011 年の論文、Accelerating Queries with Group-By and Join by Groupjoin (paper_1 と呼ぶ) は、さまざまな実行計画における GroupJoin 演算子の理論的な実現可能性について議論していますが、実装の詳細はほとんど提供されていません。この論文では、制約や適用可能なシナリオ (さまざまな集計関数の処理方法など) が説明されていますが、その表現は抽象的で読みにくいです。

2021 年の論文、A Practical Approach to Groupjoin and Nested Aggregates (paper_2 と呼ぶ) は、インメモリデータベースで GroupJoin 演算子を効率的に実装する方法について説明しています。主なポイントは次のとおりです：

1. サブクエリのデカップリングにおける GroupJoin の使用

GROUP BY が相関述語の上にある相関サブクエリを処理するには、「マジックセット」操作 (table distinct の一種) を導入し、その上に GROUP BY を持つ JOIN を追加するというアプローチがあります。これにより、サブクエリがデカップリングされます。この形状の実行計画は、GroupJoin 演算子に最適です。IMCI は同様のサブクエリデカップリングメソッドを使用しますが、まだ共有の子を持つ実行計画を生成することはできません。

2. Eager aggregation

本質的に、これはハッシュ結合のビルド側で、ビルドプロセス中に集計関数を評価することを意味します。各ハッシュテーブルエントリの完全なペイロードを保存して後で関数を計算するのではなく、このアプローチは IMCI の実装でも使用されています。

3. 同時プロービングと集約中の競合を処理するためのメモ化の使用

極端なケースを考えてみましょう：ハッシュプローブ中に、すべてのデータがハッシュテーブルの同じエントリにマッピングされます。これにより、この単一のエントリで集約 (例：SUM(2 * col)) を実行する必要があり、多くのスレッドが同じ「集約コンテキスト」を更新しようとします。SUM() 関数の場合、これは同じ合計値に繰り返し加算することを意味します。アトミックな加算でさえ、激しい競合下ではパフォーマンスが低下し、一般的な集計関数はさらに悪化します。この論文では、Compare-and-Swap (CAS) 命令を使用して各エントリにオーナー スレッドを割り当てるソリューションを提案しています。所有権の取得に失敗したスレッドは、データをプライベートなローカルハッシュテーブルに集約します。これらのローカルハッシュテーブルは、最後にグローバルハッシュテーブルにマージされます。

4. GroupJoin はすべてのシナリオに適しているわけではない

場合によっては、個別の JOIN と GROUP BY の方がパフォーマンスが向上します。たとえば、ハッシュビルド側の選択性が非常に低いと仮定します。ハッシュプローブ後、ビルド側のほとんどの行は選択されません。これにより、ジレンマが生じます：

• ビルドフェーズで eager aggregation を使用すると、ペイロードを保存しないことでメモリを節約できます。ただし、結合の選択性が低い場合、この事前計算された集約作業のほとんどは、最終的に破棄される行に対して無駄になります。

• 事前に集約を実行しない場合、より多くのメモリを使用します。ただし、結合の選択性が高い場合、この余分なメモリは eager aggregation を使用することで節約できたはずです。

したがって、結合の選択性が低い場合、より良いアプローチは、結合を完了して非常に少数のグループを取得し、その後 HASH GROUP BY を使用して高度にローカライズされた集約を実行することです。この論文では、さまざまなシナリオに対して異なる実装を提案しています。クエリがどのシナリオに該当するかを判断するために、オプティマイザーは選択性とカーディナリティの推定値を提供する必要があり、この論文ではこれをサポートするためのいくつかの推定方法を提供しています。

実装者の観点から見ると、この「ジレンマ」は 2 つの理由から大きな問題ではありません：

• PolarDB IMCI は、ほとんどの場合、小さい側 (小さいテーブル) にハッシュテーブルを構築します。

• 結合の選択性が低い場合でも、eager aggregation を使用すると、小さいテーブルでの計算が一部無駄になる可能性がありますが、常にメモリを節約できます。この状況では、個別の HASH JOIN と HASH GROUP BY と比較して、時間と空間の合理的なトレードオフです。

IMCI の実装では、前述の RIGHT JOIN, GROUP BY RIGHT シナリオを除き、PolarDB IMCI は、GroupJoin 演算子が個別の HASH JOIN と HASH GROUP BY よりも効率的であるとほとんどの場合見なします。

著者と引用された実験に基づくと、両方の論文はミュンヘン大学の HyPer データベースチームによるものと思われます。HyPer 以外では、他のデータベースが GroupJoin 演算子を実装していることは知られていません。ただし、「共有ハッシュテーブル」操作の他の実装が存在する可能性があり、これは将来の議論のトピックです。

TPC-H における GroupJoin のユースケース

TPC-H は、AP システムの分析クエリ能力をテストするための一般的なベンチマークです。TPC-H の 22 のクエリの多くは、GroupJoin 演算子に適しています。ただし、TPC-H Q13 を除き、ほとんどのクエリは GroupJoin を適用する前に書き換えが必要です。

Q13

TPC-H Q13 は、GroupJoin 演算子を直接使用できます：

select
    c_count,
    count(*) as custdist
from
    (
        select
            c_custkey,
            count(o_orderkey) as c_count
        from
            customer
            left outer join orders on c_custkey = o_custkey
            and o_comment not like '%pending%deposits%'
        group by
            c_custkey
    ) c_orders
group by
    c_count
order by
    custdist desc,
    c_count desc;

• IMCI では、GroupJoin 演算子がない場合、実行計画は次のようになります：

  1 Project | Exprs: temp_table4.temp_table2.COUNT(orders.o_orderkey), temp_table4.COUNT(0)
  2   Sort | Exprs: temp_table4.COUNT(0) DESC,temp_table4.temp_table2.COUNT(orders.o_orderkey) DESC
  3     HashGroupby | OutputTable(4): temp_table4 | Grouping: temp_table2.COUNT(orders.o_orderkey) | Output Grouping: temp_table2.C
  4       HashGroupby | OutputTable(2): temp_table2 | Grouping: customer.c_custkey | Output Grouping: customer.c_custkey | Aggrs: C
  5         HashJoin | HashMode: DYNAMIC | JoinMode: LEFT_OUTER | JoinPred: customer.c_custkey = orders.o_custkey
  6           CTableScan | InputTable(0): customer | Pred: (TRUE PRED)
  7           CTableScan | InputTable(1): orders | Pred: ( NOT (orders.o_comment LIKE "%pending%deposits%"))

• GroupJoin 演算子を使用する場合、実行計画は次のようになります：

  9 Project | Exprs: temp_table4.temp_table2.COUNT(orders.o_orderkey), temp_table4.COUNT(0)
  10   Sort | Exprs: temp_table4.COUNT(0) DESC,temp_table4.temp_table2.COUNT(orders.o_orderkey) DESC
  11     HashGroupby | OutputTable(4): temp_table4 | Grouping: temp_table2.COUNT(orders.o_orderkey) | Output Grouping: temp_table2.C
  12       GroupJoin | Grouping: customer.c_custkey (unique) | JoinMode: LEFT OUTER | JoinPred: customer.c_custkey = orders.o_custke
  13         CTableScan | InputTable(0): customer | Pred: (TRUE PRED)
  14         CTableScan | InputTable(1): orders | Pred: ( NOT (orders.o_comment LIKE "%pending%deposits%"))

Q3

TPC-H Q3 で GroupJoin 演算子を有効にするには、一連の等価変換が必要です：

select
    l_orderkey,
    sum(l_extendedprice * (1 - l_discount)) as revenue,
    o_orderdate,
    o_shippriority
from
    customer,
    orders,
    lineitem
where
    c_mktsegment = 'BUILDING'
    and c_custkey = o_custkey
    and l_orderkey = o_orderkey
    and o_orderdate < date '1995-03-15'
    and l_shipdate > date '1995-03-15'
group by
    l_orderkey,
    o_orderdate,
    o_shippriority
order by
    revenue desc,
    o_orderdate
limit
    10;

IMCI での Q3 の実現可能な実行計画は次のとおりです：

1  Project | Exprs: temp_table3.lineitem.l_orderkey, temp_table3.SUM(lineitem.l_extendedprice * 1.00 - lineitem.l_discount), temp_...
2    TopK | Limit = 10 | Exprs: temp_table3.SUM(lineitem.l_extendedprice * 1.00 - lineitem.l_discount) DESC,temp_table3.orders.o_orderdate
3      HashGroupby | OutputTable(3): temp_table3 | Grouping: lineitem.l_orderkey orders.o_orderdate orders.o_shippriority | Output: lineitem.l_orderkey, orders.o_orderdate, orders.o_shippriority, SUM(lineitem.l_extendedprice * 1.00 - lineitem.l_discount)
4        HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_orderkey = lineitem.l_orderkey
5          HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_custkey = customer.c_custkey
6            CTableScan | InputTable(0): orders | Pred: (orders.o_orderdate < 03/15/1995 00:00:00.000000)
7            CTableScan | InputTable(1): customer | Pred: (customer.c_mktsegment = "BUILDING")
8          CTableScan | InputTable(2): lineitem | Pred: (lineitem.l_shipdate > 03/15/1995 00:00:00.000000)

グループ化キーは l_orderkey、o_orderdate、および o_shippriority であり、単一の結合キーと一致しないため、GroupJoin は直接適用されません。ただし、等価性の推論を通じて以下を導き出すことができます：

1. lineitem テーブルと orders テーブル間の結合述語は l_orderkey = o_orderkey であり、これは INNER JOIN です。したがって、結果セット全体で l_orderkey = o_orderkey が成り立ちます。

2. l_orderkey = o_orderkey であるため、GROUP BY l_orderkey, o_orderdate, o_shippriority は GROUP BY o_orderkey, o_orderdate, o_shippriority と等価です。

3. o_orderkey は orders テーブルのプライマリキーであるため、各 o_orderkey はo_orderdate と o_shippriority を一意に決定します (つまり、o_orderdate と o_shippriority は o_orderkey に関数従属しています)。

4. o_orderkey が o_orderdate と o_shippriority を一意に決定するため、GROUP BY o_orderkey, o_orderdate, o_shippriority は GROUP BY o_orderkey と等価です。

これらの推論により、Q3 の GROUP BY 句は GROUP BY o_orderkey に書き換えることができ、これにより GroupJoin が適用可能になります：

Project | Exprs: temp_table3.lineitem.l_orderkey, temp_table3.SUM(lineitem.l_extendedprice * 1.00 - lineitem.l_discount), temp_
TopK | Limit = 10 | Exprs: temp_table3.SUM(lineitem.l_extendedprice * 1.00 - lineitem.l_discount) DESC,temp_table3.ANY_VALUE(orders.o_orderdate)
  GroupJoin | Grouping: lineitem.l_orderkey | JoinMode: INNER | JoinPred: orders.o_orderkey = lineitem.l_orderkey
    HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_custkey = customer.c_custkey
      CTableScan | InputTable(0): orders | Pred: (orders.o_orderdate < 03/15/1995 00:00:00.000000)
      CTableScan | InputTable(1): customer | Pred: (customer.c_mktsegment = "BUILDING")
    CTableScan | InputTable(2): lineitem | Pred: (lineitem.l_shipdate > 03/15/1995 00:00:00.000000)

この種の「関数従属性」の推論には、高度なオプティマイザーのサポートが必要です。MySQL オプティマイザーは現在、部分的な関数従属性の推論を実装していますが、上記で示された GROUP BY o_orderkey の書き換えを導出することはできません。実験によると、SQL Server はこの変換を実行できます。理論は十分に確立されていますが、IMCI はまだそれを完全に実装していません。TPC-H では、クエリ Q3、Q4、Q10、Q13、Q18、Q20、および Q21 がこのパターンを共有しています。これらの等価書き換えを適用すると、GROUP BY キーが短縮され、集約が高速化されます。

Q10

TPC-H Q10 も GroupJoin 演算子を直接使用することはできません：

select
    c_custkey,
    c_name,
    sum(l_extendedprice * (1 - l_discount)) as revenue,
    c_acctbal,
    n_name,
    c_address,
    c_phone,
    c_comment
from
    customer,
    orders,
    lineitem,
    nation
where
    c_custkey = o_custkey
    and l_orderkey = o_orderkey
    and o_orderdate >= date '1993-10-01'
    and o_orderdate < date '1993-10-01' + interval '3' month
    and l_returnflag = 'R'
    and c_nationkey = n_nationkey
group by
    c_custkey,
    c_name,
    c_acctbal,
    c_phone,
    n_name,
    c_address,
    c_comment
order by
    revenue desc
limit
    20;

GroupJoin 演算子を使用するには、2 つの変換が必要です：

1. Q3 の変換と同様に、グループ化キーを c_custkey (customer テーブルのプライマリキー) に書き換えます。

2. customer テーブルを含む結合が最も外側の結合になるように、結合順序を調整します。

最初の変換は常に有益ですが、結合順序の調整は必ずしも全体的にプラスになるとは限りません。

Q17

TPC-H Q17 には相関サブクエリが含まれています：

select
    sum(l_extendedprice) / 7.0 as avg_yearly
from
    lineitem,
    part
where
    p_partkey = l_partkey
    and p_brand = 'Brand#44'
    and p_container = 'WRAP PKG'
    and l_quantity < (
        select
            0.2 * avg(l_quantity)
        from
            lineitem
        where
            l_partkey = p_partkey
    );

サブクエリのデカップリングを実行する方法は複数あります。IMCI では、スカラー集計のための 2 つの異なるデカップリングアルゴリズムが次の実行計画を生成しますが、どちらも GroupJoin 演算子を使用できません：

Project | Exprs: temp_table7.temp_table6.SUM(temp_table3.ANY_VALUE(lineitem.l_extendedprice)) / 7.0
  ComputeScalar | Exprs: temp_table6.SUM(temp_table3.ANY_VALUE(lineitem.l_extendedprice)) / 7.0
    HashGroupby | OutputTable(6): temp_table6 | Grouping: None | Output Grouping: None | Aggrs: SUM(temp_table3.ANY_VALUE(lineitem.l_extendedprice))
      FILTER | Pred: ((CAST temp_table3.ANY_VALUE(lineitem.l_quantity)/DECIMAL(15, 2) as DECIMAL(38, 12)) < 0.2 * temp_table3.AVG(lineitem.l_quantity))
        HashGroupby | OutputTable(3): temp_table3 | Grouping: temp_sequence.SEQUENCE_VALUE | Output Grouping: None | Aggrs: AVG(lineitem.l_quantity)
          HashJoin | HashMode: DYNAMIC | JoinMode: LEFT_OUTER | JoinPred: part.p_partkey = lineitem.l_partkey
            SEQUENCE | SequenceID: (55440)
              HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: lineitem.l_partkey = part.p_partkey
                CTableScan | InputTable(0): lineitem | Pred: (TRUE PRED)
                CTableScan | InputTable(1): part | Pred: ((part.p_brand = "Brand#44") AND (part.p_container = "WRAP PKG"))
            CTableScan | InputTable(2): lineitem | Pred: (TRUE PRED)

Project | Exprs: temp_table7.temp_table6.SUM(lineitem.l_extendedprice) / 7.0
  ComputeScalar | Exprs: temp_table6.SUM(lineitem.l_extendedprice) / 7.0
    HashGroupby | OutputTable(6): temp_table6 | Grouping: None | Output Grouping: None  | Aggrs: SUM(lineitem.l_extendedprice)
      FILTER | Pred: ((CAST lineitem.l_quantity/DECIMAL(15, 2) as DECIMAL(38, 12)) < 0.2 * temp_table3.AVG(lineitem.l_quantity))
        HashMatch | HashMode: DYNAMIC | JoinMode: LEFT_OUTER | JoinPred: part.p_partkey = temp_table3.lineitem.l_partkey
          HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: lineitem.l_partkey = part.p_partkey
            CTableScan | InputTable(0): lineitem | Pred: (TRUE PRED)
            CTableScan | InputTable(1): part | Pred: ((part.p_brand = "Brand#44") AND (part.p_container = "WRAP PKG"))
          HashGroupby | OutputTable(3): temp_table3 | Grouping: lineitem.l_partkey | Output Grouping: lineitem.l_partkey | Aggr
            CTableScan | InputTable(2): lineitem | Pred: (TRUE PRED)

ただし、MagicSet ベースのデカップリング戦略を使用すると、MagicSet 演算子が削除される前に、GroupJoin に適した中間計画形状を生成できます：

これは paper_2 で説明されているプロセスです：

IMCI は MagicSet ベースのデカップリングを部分的に実装していますが、まだ共有の子を持つ実行計画を生成しません。したがって、IMCI は TPC-H Q17 に GroupJoin 演算子を適用できません。

Q18

TPC-H Q18 も GroupJoin 演算子を使用できますが、適切な実行計画を生成するには等価変換が必要です。簡単にするため、一般性を失うことなく、このセクションでは元のクエリから IN サブクエリと最後の ORDER BY 句を削除します：

select
    c_name,
    c_custkey,
    o_orderkey,
    o_orderdate,
    o_totalprice,
    sum(l_quantity)
from
    customer,
    orders,
    lineitem
where
    c_custkey = o_custkey
    and o_orderkey = l_orderkey
group by
    c_name,
    c_custkey,
    o_orderkey,
    o_orderdate,
    o_totalprice

このクエリに対して、次の等価性の推論を適用できます：

1. c_custkey は customer テーブルのプライマリキーであるため、c_name は c_custkey に関数従属します。同様に、o_orderkey は orders テーブルのプライマリキーであるため、o_orderdate と o_totalprice は o_orderkey に関数従属します。したがって、GROUP BY 句は GROUP BY c_custkey, o_orderkey と等価です。

2. customer テーブルと orders テーブル間の結合述語は c_custkey = o_custkey であるため、結合結果セットで c_custkey = o_custkey であると断定できます。

3. c_custkey = o_custkey であるため、GROUP BY 句はさらに GROUP BY o_custkey, o_orderkey に変換できます。

4. o_orderkey は orders テーブルのプライマリキーであるため、o_custkey を一意に決定します。したがって、GROUP BY 句は最終的に GROUP BY o_orderkey と書き換えることができます。

これらの変換後、クエリは次のものと等価になります：

select
    ANY_VALUE(c_name),
    ANY_VALUE(c_custkey),
    o_orderkey,
    ANY_VALUE(o_orderdate),
    ANY_VALUE(o_totalprice),
    sum(l_quantity)
from
    customer,
    orders,
    lineitem
where
    c_custkey = o_custkey
    and o_orderkey = l_orderkey
group by
    o_orderkey

• GroupJoin なしの実行計画

  1  Project | Exprs: temp_table3.ANY_VALUE(customer.c_name), temp_table3.ANY_VALUE(customer.c_custkey), temp_table3.orders.o_orderkey, temp_table3.ANY_VALUE(orders.o_orderdate), temp_table3.ANY_VALUE(orders.o_totalprice), temp_table3.SUM(lineitem.l_quantity)
  2    HashGroupby | OutputTable(3): temp_table3 | Grouping: orders.o_orderkey | Output Grouping: orders.o_orderkey | Aggrs: ANY_VALUE(customer.c_name), ANY_VALUE(customer.c_custkey), ANY_VALUE(orders.o_orderdate), ANY_VALUE(orders.o_totalprice), SUM(lineitem.l_quantity)
  3      HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_orderkey = lineitem.l_orderkey
  4        HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_custkey = customer.c_custkey
  5          CTableScan | InputTable(0): orders | Pred: (TRUE PRED)
  6          CTableScan | InputTable(1): customer | Pred: (TRUE PRED)
  7        CTableScan | InputTable(2): lineitem | Pred: (TRUE PRED)

• GroupJoin ありの実行計画

  1 Project | Exprs: temp_table4.ANY_VALUE(customer.c_name), temp_table4.ANY_VALUE(customer.c_custkey), temp_table4.orders.o_orderkey
  2   GroupJoin | Grouping: orders.o_orderkey | JoinMode: INNER | JoinPred: orders.o_orderkey = lineitem.l_orderkey
  3     HashJoin | HashMode: DYNAMIC | JoinMode: INNER | JoinPred: orders.o_custkey = customer.c_custkey
  4       CTableScan | InputTable(0): orders | Pred: (TRUE PRED)
  5       CTableScan | InputTable(1): customer | Pred: (TRUE PRED)
  6     CTableScan | InputTable(2): lineitem | Pred: (TRUE PRED)

これらの等価性の推論は、GROUP BY キーを短縮するため、従来の実行計画にも有益です。

Q20

TPC-H Q20 の相関サブクエリのパターンは Q17 のものと似ています。MagicSet ベースのデカップリングアプローチを使用すると、MagicSet 演算子が削除される前に、GroupJoin に適した中間計画形状が生成されます。

select
...
and ps_availqty > (
    select
        0.5 * sum(l_quantity) < ! --- scalar aggr --->
    from
        lineitem
    where
        l_partkey = ps_partkey         < ! --- correlated item 1 --->
        and l_suppkey = ps_suppkey     < ! --- correlated item 2 --->
        and l_shipdate >= '1993-01-01'
        and l_shipdate < date_add('1993-01-01', interval '1' year)
)

その他のクエリ

paper_1 と paper_2 によると、クエリ Q5、Q9、Q16、および Q21 も GroupJoin 演算子に適していますが、適切な変換パスはまだ見つかっていません。HyPer データベース (https://hyper-db.de/interface.html#) の実行計画を調べると、そのオプティマイザーもこれらのクエリに対して GroupJoin を含む実行計画を生成しないことがわかります。

クエリのパフォーマンス

TPC-H ベンチマークの多くのクエリは JOIN + GROUP BY パターンを使用しており、GroupJoin 最適化の候補となります。paper_1 では、著者らは GroupJoin 演算子ありとなしで、クエリ Q3、Q5、Q9、Q10、Q13、Q16、Q17、Q20、および Q21 のパフォーマンスを報告しています。

このテストでは 1 GB の TPC-H データセットを使用しています。結果は、GroupJoin 演算子が TPC-H クエリのパフォーマンスにプラスの影響を与え、総レイテンシーを 1,932 ms から 1,295 ms に削減することを示しています。

paper_2 では、著者らは 10 GB の TPC-H データセットを使用し、いくつかのアプローチにわたってクエリ Q3、Q13、Q17、および Q18 のより詳細なパフォーマンスの内訳を提供しています：

図の線グループは次のことを表しています：

1. 「separate」は、JOIN と GROUP BY を別々に実行すること、つまり GroupJoin 演算子を使用しないことを指します。

2. 「eager」は、前述の「eager aggregation」最適化を指します。

3. 「memoizing」は、同時ハッシュテーブルプローブと集約を処理するための最適化を指します。クエリ Q3、Q13、Q17、および Q18 の場合：

   1. 「memoizing」アプローチは、ほとんどの場合、標準の HASH JOIN + HASH GROUP BY メソッドと同様のパフォーマンスを示します。

   2. 「eager」集約アプローチは、Q13 でのみ利点を示します。

データは、パフォーマンスがシナリオによって大きく異なることを示しています。これは、この論文の主なポイント、つまりGroupJoin の実行戦略は、単一の GroupJoin アルゴリズムを無差別に選択したり、そもそも GroupJoin 演算子を使用したりするのではなく、最適なメソッドを選択するためにオプティマイザーからの正確な統計情報を必要とするということを裏付けています。

しかし、PolarDB はこの結論に対して異なる見解を持っています：

1. この論文ではパフォーマンスメトリックとしてタプル/秒を使用していますが、PolarDB IMCI での調査結果は異なります。同時実行数 32 で、クエリ Q3、Q13、および Q18 の GroupJoin 演算子のスループット (タプル/秒) をテストしました。結果は次のとおりです：

   クエリ	Hash join + hash group by	GroupJoin
   Q3	130 MB/s	152 MB/s
   Q13	11 MB/s	33 MB/s
   Q18	315 MB/s	1 GB/s

   説明

   現在、IMCI では Q17 に GroupJoin 演算子を適用できません。

   このテストデータは論文のデータと規模が似ていますが、各クエリの結果はわずかに異なります。おそらく実装の違いによるものですが、PolarDB からのテストデータは、RIGHT JOIN, GROUP BY RIGHT のケースを除き、GroupJoin 演算子が HASH JOIN + HASH GROUP BY よりもほとんどの場合優れていることを示しています。

2. 上記の 3.a の結論、つまり「memoizing」メソッドはほとんどの場合、標準の HASH JOIN + HASH GROUP BY メソッドと同様のパフォーマンスを持つという点に関して、私たちの観測では、これらの特定の TPC-H クエリは競合が非常に少ないことが示されています。その結果、memoizing メソッドで使用されるローカルハッシュテーブルなどのコンポーネントは、ランタイムでほとんど使用されません。これが、これらのクエリでのアルゴリズムのパフォーマンスが HASH JOIN + HASH GROUP BY のパフォーマンスと似ている理由です。したがって、論文でこれらのクエリのパフォーマンスを比較に使用することは、意味のある比較ではありません。PolarDB は、明示的なロックを使用してランタイムの競合をテストします。

結論

実際には、GroupJoin 演算子はランタイムでの冗長な作業を回避し、特定のシナリオで大幅なパフォーマンス向上をもたらすことができます。この利点は、本番ワークロードで検証されています。結果指向の観点から見ると、GroupJoin 演算子は実装する価値のあるものです。

しかし、GroupJoin は汎用的な最適化ではありません。これは、グループ化キーが片側の結合キーと一致する EQUAL JOIN と GROUP BY にのみ適用され、集計関数や実装の選択に多くの制約を課します。これは、実装とメンテナンスのコストが高い特殊な機能です。開発の観点からは、狭いパターンのためのカスタムソリューションを構築するよりも、「一般的なパス」を最適化して SQL パフォーマンスを広範囲に向上させることに投資する方が効果的です。この観点からすると、GroupJoin は理想的なメソッドではありません。

したがって、GroupJoin を実装する際には、簡略化とトレードオフを行うことが賢明です。目標は、最も完全でフル機能のバージョンを構築することではなく、最も一般的で影響の大きいシナリオでパフォーマンスと実用性を最大化することであるべきです。