PolarDB:インメモリ列指向インデックスにおける GroupJoin オペレーターの実装

INNER JOIN、左側での GROUP BY

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

以下の説明では、SQL ステートメントが示された順序で実行され、結合対象が動的に切り替わらないものと仮定しています。

1. 左側テーブルからハッシュテーブルを構築し、左側データに対して集計関数を実行します。各ハッシュテーブルエントリに対して、右側テーブルのマッチ行数をカウントする「繰り返し回数」を記録します。

2. 右側テーブルでハッシュテーブルを検索します。マッチした各行について、繰り返し回数を 1 増加させ、右側データに対して集計関数を実行します。マッチしなかった行は破棄されます。

3. 結合完了後、マッチしたハッシュテーブルエントリのみを出力します。マッチしなかったエントリは破棄されます。

4. 最終的な集約結果は SUM(expr) × 繰り返し回数 と等しくなります。たとえば、SUM(expr) が 200 で繰り返し回数が 5 の場合、結果は 1,000 になります。

INNER JOIN、右側での GROUP BY

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

INNER JOIN では l_table.key1 と r_table.key1 が等しいため、このシナリオは左側での GROUP BY を伴う INNER JOIN と等価です。

LEFT OUTER JOIN、左側での GROUP BY

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

1. 左側テーブルからハッシュテーブルを構築し、左側データに対して集計関数を実行します。右側集約用に繰り返し回数を使用します。

2. 右側テーブルでハッシュテーブルを検索します。マッチしたエントリについては繰り返し回数を増加させ、右側の集計関数を実行します。マッチしなかった右側の行は破棄されます。

3. 結合完了後、マッチしたエントリを出力します。マッチしなかったハッシュテーブルエントリは、右側の集計関数の入力として NULL を指定した別グループに収集されます。

LEFT OUTER JOIN、右側での GROUP BY

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

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

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

r_table.key1 は一意である必要があります。一意性が保証できない場合は、オプティマイザーを使用して JOIN を LEFT OUTER JOIN に変換するか、GROUP BY を左側に変更してください。

1. 左側テーブルからハッシュテーブルを構築し、左側データに対して集計関数を実行します。右側集約用に繰り返し回数を使用します。

2. 右側テーブルでハッシュテーブルを検索します。マッチしたエントリについては、左側および右側の集計結果の両方を出力します。マッチしなかった右側の行については、左側の集計関数の結果として NULL 値を出力します。

3. 結合完了後、GroupJoin の処理は終了します。これ以降、ハッシュテーブルエントリの管理は不要です。

Q13

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;

GroupJoin を使用しない実行計画：

GroupJoin を使用した実行計画：

Q3

Q3 は GroupJoin を使用する前に GROUP BY の書き換えが必要です：

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 における元の実行計画：

GROUP BY キー（l_orderkey、o_orderdate、o_shippriority）は、すべての結合キーと異なり、GroupJoin は直接適用できません。以下の関数従属性の連鎖により、書き換えが可能になります：

1. 結合述語 l_orderkey = o_orderkey により、任意の結果行において l_orderkey と o_orderkey は等しくなります。

2. したがって、GROUP BY l_orderkey, o_orderdate, o_shippriority は GROUP BY o_orderkey, o_orderdate, o_shippriority と等価です。

3. o_orderkey は orders テーブルのプライマリキーであるため、o_orderdate および o_shippriority は o_orderkey に対して関数従属性を有します。

4. したがって、GROUP BY o_orderkey, o_orderdate, o_shippriority は GROUP BY o_orderkey に簡約されます。

GROUP BY 句を GROUP BY o_orderkey に置き換えることで、GroupJoin を有効化できます：

MySQL オプティマイザーは関数従属性を部分的に導出できますが、GROUP BY o_orderkey への完全な簡約は自動的には行えません。SQL Server では理論上完全な導出が可能ですが、IMCI 有効化環境における実証はまだ行われていません。この関数従属性の導出は、Q3、Q4、Q10、Q13、Q18、Q20、Q21 にも同様に適用されます。オプティマイザーが完全な導出を行える場合、GROUP BY キーが短縮され、集約処理が高速化されます。

Q10

Q10 は GroupJoin を使用する前に 2 つの修正が必要です：

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;

1. Q3 と同じ関数従属性の推論を用いて、集約キーを c_custkey（customer テーブルのプライマリキー）に置き換えます。

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

最初の修正は常にパフォーマンスを向上させます。2 番目の修正は、場合によって副作用を引き起こすことがあります。

Q17

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
    );

2 つの非相関化アルゴリズムにより、GroupJoin を使用しない実行計画が生成されます：

非相関化に MagicSet を使用すると、GroupJoin と互換性のある中間状態が導入されます：

このアプローチは、論文 2 の図 3 にも示されています：

PolarDB は、IMCI 有効化シナリオにおいて MagicSet を非相関化手法として部分的にサポートしていますが、共有子オブジェクトを含む実行計画はまだ生成されていません。その結果、IMCI 有効化シナリオでは Q17 に対して GroupJoin を使用できません。

Q18

Q18 は GROUP BY の簡略化後に 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 はそれに関数従属性を有します。o_orderkey は orders のプライマリキーであるため、o_orderdate および o_totalprice はそれに関数従属性を有します。したがって、GROUP BY c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice は GROUP BY c_custkey, o_orderkey に簡約されます。

2. 結合述語 c_custkey = o_custkey により、結果には c_custkey = o_custkey となる行のみが含まれます。したがって、GROUP BY c_custkey, o_orderkey は GROUP BY o_custkey, o_orderkey に簡約されます。

3. o_orderkey が o_custkey を一意に決定するため、GROUP BY o_custkey, o_orderkey は 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 を使用しない実行計画：

GroupJoin を使用した実行計画：

GROUP BY キーの短縮は、GroupJoin を使用しない通常の実行計画に対してもメリットがあります。

Q20

Q20 には Q17 と同様の相関サブクエリが含まれています。MagicSet 非相関化は、MagicSet が除去される前に GroupJoin と互換性のある中間状態を導入します：

...
AND ps_availqty > (
    SELECT
        0.5 * sum(l_quantity)  /* スカラー集約 */
    FROM
        lineitem
    WHERE
        l_partkey = ps_partkey         /* 相関述語 1 */
        AND l_suppkey = ps_suppkey     /* 相関述語 2 */
        AND l_shipdate >= '1993-01-01'
        AND l_shipdate < DATE_ADD('1993-01-01', INTERVAL '1' YEAR)
)

その他のクエリ

論文 1 および論文 2 によると、Q5、Q9、Q16、Q21 についても修正後に GroupJoin が適用可能ですが、これらの論文では具体的な修正手順は記述されていません。これらのクエリに対する GroupJoin の実行計画は、HyPer WebInterface（https://hyper-db.de/interface.html#）でも利用できません。

クエリパフォーマンス

多くの TPC-H クエリは JOIN と GROUP BY を組み合わせており、GroupJoin の最適化対象となります。

論文 1 では、1 GB のデータを用いて Q3、Q5、Q9、Q10、Q13、Q16、Q17、Q20、Q21 のクエリパフォーマンスを比較しました。GroupJoin を使用することで、これらのクエリの合計遅延が 1,932 ms から 1,295 ms に短縮されました。

論文 2 では、1 GB のデータを用いて Q3、Q13、Q17、Q18 のパフォーマンスを 3 つの戦略で比較しました：

• Separate（分離） — 標準の JOIN の後に GROUP BY を実行

• Eager（即時） — eager aggregation を使用した GroupJoin

• Memoizing（メモ化） — メモ化最適化を適用した GroupJoin

論文の折れ線グラフでは、Q3、Q13、Q17、Q18 のいずれにおいても以下の 2 つのパターンが見られます：

• メモ化のパフォーマンスは、HASH JOIN ＋ HASH GROUP BY とほぼ同等です。

• eager aggregation は、Q13 のみで他の手法より優れたパフォーマンスを発揮します。

これらの結果は、最適な GroupJoin 戦略がクエリの特性に依存し、オプティマイザーが選択性およびカーディナリティの推定に基づいて実行計画を選択すべきであるという論文の結論を裏付けています。

PolarDB の実験では、異なる結論が得られています。同じ 1 GB のデータセットを用いた実験において、PolarDB では GroupJoin が一貫してスループットを向上させていること（関連論文 の表を参照）、および TPC-H クエリにおける競合が最小限であることが示されています。メモ化によって作成されるローカルハッシュテーブルはほとんど必要とされず、そのためメモ化のパフォーマンスは PolarDB の実装において HASH JOIN ＋ HASH GROUP BY と同等です。