PolarDB:Implementasi operator GroupJoin dalam Indeks Kolom dalam Memori

INNER JOIN, GROUP BY sisi kiri

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

Deskripsi berikut mengasumsikan pernyataan SQL dieksekusi sesuai urutan yang ditunjukkan, dan objek join tidak dialihkan secara dinamis.

1. Membangun tabel hash dari tabel kiri, menjalankan fungsi agregat pada data sisi kiri. Penghitung ulang melacak berapa banyak baris sisi kanan yang cocok dengan setiap entri tabel hash.

2. Menjalankan probing terhadap tabel hash menggunakan tabel kanan. Untuk setiap baris sisi kanan yang cocok, tambahkan penghitung ulang sebesar 1 dan jalankan fungsi agregat pada data sisi kanan. Buang baris yang tidak cocok.

3. Setelah penggabungan, keluarkan hanya entri tabel hash yang cocok. Buang entri yang tidak cocok.

4. Hasil agregasi akhir sama dengan SUM(expr) × repeat count. Misalnya, jika SUM(expr) bernilai 200 dan penghitung ulang bernilai 5, hasilnya adalah 1.000.

INNER JOIN, GROUP BY sisi kanan

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

Karena l_table.key1 sama dengan r_table.key1 dalam INNER JOIN, skenario ini setara dengan INNER JOIN dengan GROUP BY pada sisi kiri.

LEFT OUTER JOIN, GROUP BY sisi kiri

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

1. Membangun tabel hash dari tabel kiri dan menjalankan fungsi agregat pada data sisi kiri. Gunakan penghitung ulang untuk agregasi sisi kanan.

2. Menjalankan probing terhadap tabel hash menggunakan tabel kanan. Entri yang cocok menambah penghitung ulang dan menjalankan fungsi agregat sisi kanan. Baris sisi kanan yang tidak cocok dibuang.

3. Setelah penggabungan, keluarkan entri yang cocok. Kumpulkan entri tabel hash yang tidak cocok ke dalam kelompok terpisah dengan input NULL untuk semua fungsi agregat sisi kanan.

LEFT OUTER JOIN, GROUP BY sisi kanan

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

1. Membangun tabel hash dari tabel kiri dan menjalankan fungsi agregat pada data sisi kiri. Gunakan penghitung ulang untuk agregasi sisi kanan.

2. Menjalankan probing terhadap tabel hash menggunakan tabel kanan. Entri yang cocok menambah penghitung ulang dan menjalankan fungsi agregat sisi kanan. Baris sisi kanan yang tidak cocok dibuang.

3. Setelah penggabungan, keluarkan entri yang cocok. Kumpulkan entri yang tidak cocok ke dalam kelompok terpisah dengan input NULL untuk semua fungsi agregat sisi kanan.

RIGHT OUTER JOIN, GROUP BY sisi kiri

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

1. Membangun tabel hash dari tabel kiri dan menjalankan fungsi agregat pada data sisi kiri. Gunakan penghitung ulang untuk agregasi sisi kanan.

2. Menjalankan probing terhadap tabel hash menggunakan tabel kanan. Untuk entri yang cocok, tambahkan penghitung ulang dan jalankan fungsi agregat sisi kanan. Kumpulkan semua baris sisi kanan yang tidak cocok ke dalam kelompok terpisah dengan hasil NULL untuk fungsi agregat sisi kiri.

3. Setelah penggabungan, keluarkan entri tabel hash yang cocok. Buang entri yang tidak cocok.

RIGHT OUTER JOIN, GROUP BY sisi kanan

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

r_table.key1 harus unik. Jika keunikan tidak dapat dijamin, gunakan pengoptimal untuk mengubah JOIN menjadi LEFT OUTER JOIN atau ubah GROUP BY ke sisi kiri.

1. Membangun tabel hash dari tabel kiri dan menjalankan fungsi agregat pada data sisi kiri. Gunakan penghitung ulang untuk agregasi sisi kanan.

2. Menjalankan probing terhadap tabel hash menggunakan tabel kanan. Untuk entri yang cocok, keluarkan hasil agregasi sisi kiri dan sisi kanan. Untuk baris sisi kanan yang tidak cocok, keluarkan hasil dengan nilai NULL untuk agregat sisi kiri.

3. Setelah penggabungan, GroupJoin selesai. Tidak diperlukan lagi manajemen entri tabel hash.

Q13

GroupJoin berlaku langsung untuk Q13 tanpa modifikasi:

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;

Rencana eksekusi tanpa GroupJoin:

Rencana eksekusi dengan GroupJoin:

Q3

Q3 memerlukan penulisan ulang GROUP BY sebelum GroupJoin dapat digunakan:

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;

Rencana eksekusi asli dalam IMCI:

Kunci GROUP BY (l_orderkey, o_orderdate, o_shippriority) berbeda dari semua kunci gabungan, sehingga GroupJoin tidak berlaku secara langsung. Rantai ketergantungan fungsional berikut memungkinkan penulisan ulang:

1. Predikat gabungan l_orderkey = o_orderkey berarti bahwa dalam setiap baris hasil, l_orderkey dan o_orderkey bernilai sama.

2. Oleh karena itu, GROUP BY l_orderkey, o_orderdate, o_shippriority setara dengan GROUP BY o_orderkey, o_orderdate, o_shippriority.

3. Karena o_orderkey adalah primary key tabel orders, o_orderdate dan o_shippriority secara fungsional bergantung pada o_orderkey.

4. Oleh karena itu, GROUP BY o_orderkey, o_orderdate, o_shippriority direduksi menjadi GROUP BY o_orderkey.

Mengganti klausa GROUP BY dengan GROUP BY o_orderkey mengaktifkan GroupJoin:

Pengoptimal MySQL dapat sebagian menurunkan ketergantungan fungsional tetapi tidak dapat sepenuhnya mereduksi ini menjadi GROUP BY o_orderkey secara otomatis. SQL Server secara teoretis dapat melakukan deduksi lengkap, meskipun hal ini belum sepenuhnya divalidasi dalam praktik yang diaktifkan IMCI. Deduksi ketergantungan fungsional yang sama berlaku untuk Q3, Q4, Q10, Q13, Q18, Q20, dan Q21. Ketika pengoptimal dapat melakukan deduksi lengkap, kunci GROUP BY dipersingkat dan agregasi menjadi lebih cepat.

Q10

Q10 memerlukan dua modifikasi sebelum GroupJoin dapat digunakan:

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. Ganti kunci pengelompokan dengan c_custkey (primary key tabel customer), menggunakan penalaran ketergantungan fungsional yang sama seperti Q3.

2. Sesuaikan urutan penggabungan agar penggabungan tabel customer berada di luar.

Modifikasi pertama selalu meningkatkan performa. Modifikasi kedua terkadang menimbulkan efek samping.

Q17

Q17 berisi subkueri berkorelasi:

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

Dua algoritma dekorrelasi menghasilkan rencana eksekusi yang tidak menggunakan GroupJoin:

Menggunakan MagicSet untuk dekorrelasi memperkenalkan keadaan antara yang kompatibel dengan GroupJoin:

Pendekatan ini juga ditunjukkan dalam Gambar 3 makalah 2:

PolarDB sebagian mendukung MagicSet sebagai metode dekorrelasi dalam skenario yang diaktifkan IMCI, tetapi belum menghasilkan rencana eksekusi dengan objek anak bersama. Akibatnya, GroupJoin tidak dapat digunakan untuk Q17 dalam skenario yang diaktifkan IMCI.

Q18

Q18 menerapkan GroupJoin setelah menyederhanakan GROUP BY. Contoh berikut menghilangkan subkueri IN dan klausa ORDER BY demi kejelasan:

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

Terapkan reduksi berikut:

1. c_custkey adalah primary key customer, sehingga c_name secara fungsional bergantung padanya. o_orderkey adalah primary key orders, sehingga o_orderdate dan o_totalprice secara fungsional bergantung padanya. Oleh karena itu, GROUP BY c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice direduksi menjadi GROUP BY c_custkey, o_orderkey.

2. Predikat gabungan c_custkey = o_custkey berarti hasil hanya berisi baris di mana c_custkey = o_custkey. Oleh karena itu, GROUP BY c_custkey, o_orderkey direduksi menjadi GROUP BY o_custkey, o_orderkey.

3. Karena o_orderkey secara unik menentukan o_custkey, GROUP BY o_custkey, o_orderkey direduksi menjadi GROUP BY o_orderkey.

Kueri yang ditulis ulang:

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

Rencana eksekusi tanpa GroupJoin:

Rencana eksekusi dengan GroupJoin:

Memperpendek kunci GROUP BY juga bermanfaat bagi rencana eksekusi reguler yang tidak menggunakan GroupJoin.

Q20

Q20 berisi subkueri berkorelasi mirip Q17. Dekorrelasi MagicSet memperkenalkan keadaan antara yang kompatibel dengan GroupJoin sebelum MagicSet dihapus:

...
AND ps_availqty > (
    SELECT
        0.5 * sum(l_quantity)  /* scalar aggregation */
    FROM
        lineitem
    WHERE
        l_partkey = ps_partkey         /* correlated predicate 1 */
        AND l_suppkey = ps_suppkey     /* correlated predicate 2 */
        AND l_shipdate >= '1993-01-01'
        AND l_shipdate < DATE_ADD('1993-01-01', INTERVAL '1' YEAR)
)

Kueri lainnya

Menurut makalah 1 dan makalah 2, GroupJoin juga berlaku untuk Q5, Q9, Q16, dan Q21 setelah modifikasi, tetapi langkah modifikasi spesifik tidak dijelaskan dalam makalah tersebut. Rencana eksekusi untuk GroupJoin pada kueri-kueri ini juga tidak tersedia di HyPer WebInterface (https://hyper-db.de/interface.html#).

Performa kueri

Banyak kueri TPC-H menggabungkan JOIN dan GROUP BY, menjadikannya kandidat untuk optimasi GroupJoin.

Makalah 1 membandingkan performa kueri untuk Q3, Q5, Q9, Q10, Q13, Q16, Q17, Q20, dan Q21 menggunakan data 1 GB. GroupJoin mengurangi latensi total dari 1.932 ms menjadi 1.295 ms pada kueri-kueri tersebut.

Makalah 2 membandingkan Q3, Q13, Q17, dan Q18 menggunakan data 1 GB, dengan tiga strategi:

• Separate — JOIN standar diikuti oleh GROUP BY

• Eager — GroupJoin dengan eager aggregation

• Memoizing — GroupJoin dengan optimasi memoizing

Grafik garis dalam makalah menunjukkan dua pola pada Q3, Q13, Q17, dan Q18:

• Performa memoizing mirip dengan HASH JOIN + HASH GROUP BY.

• Eager aggregation mengungguli metode lain hanya pada Q13.

Hasil ini mendukung kesimpulan makalah bahwa strategi GroupJoin optimal bergantung pada karakteristik kueri dan bahwa pengoptimal harus memilih rencana eksekusi berdasarkan perkiraan selektivitas dan kardinalitas.

Eksperimen PolarDB mencapai kesimpulan berbeda. Dengan dataset 1 GB yang sama, PolarDB menunjukkan bahwa GroupJoin secara konsisten meningkatkan throughput (lihat tabel di Makalah terkait), dan kontensi minimal terjadi dalam kueri TPC-H. Tabel hash lokal yang dibuat oleh memoizing jarang diperlukan, sehingga memoizing memberikan performa sebanding dengan HASH JOIN + HASH GROUP BY dalam implementasi PolarDB.