Algoritma Join dan Urutan Join

Dataset untuk artikel ini — perf_sales dan employee

Ketika kamu menggabungkan dua tabel, database memilih algoritma join secara internal — prosedur yang dipakainya untuk mencocokkan baris dari dua tabel.

Metode join berbeda datang dengan biaya berbeda.

Dataset-nya adalah tabel penjualan perf_sales (50.000 baris; emp_id menunjuk ke sales rep) dan tabel karyawan employee (30 baris; emp_id efektif sebagai primary key).

Ketika kamu menggabungkan keduanya pada emp_id, kamu akan memperhatikan mana yang muncul sebagai loop luar di plan dan bagaimana urutan join bergeser tergantung apakah indeks ada.

Sebelum masuk ke latihan, periksa definisi kolom dan sampel data untuk dua tabel yang dipakai artikel ini — perf_sales dan employee. Generasi perf_sales butuh waktu, jadi eksekusi pertama mungkin terhenti beberapa detik.

① Pakai PRAGMA table_info(perf_sales); dan PRAGMA table_info(employee); untuk melihat definisi kolom kedua tabel.

② Pakai SELECT * FROM perf_sales LIMIT 5; dan SELECT * FROM employee LIMIT 5; untuk mengintip 5 baris pertama masing-masing.

③ Pakai SELECT COUNT(*) FROM perf_sales; dan SELECT COUNT(*) FROM employee; untuk mengonfirmasi celah jumlah baris di antara keduanya (50.000 vs 30).

Nested loop join dan urutan join

Nested loop join menelusuri tabel luar satu baris pada satu waktu dan, untuk setiap baris, mencari baris di tabel inner yang memenuhi kondisi join — loop yang bersarang dua kali.

-- Bandingkan kueri join yang sama di tiga metode join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Alur internal nested loop join
-- for each e in employee:        -- loop luar (30 baris)
--   for each s in perf_sales:    -- inner (tanpa indeks, scan semua 50.000 baris)
--     if s.emp_id = e.emp_id then tambahkan ke hasil join

• Loop luar berjalan sebanyak baris yang dimiliki tabel, jadi taruh tabel yang lebih kecil di luar
• Sisi inner dicari berulang kali dari setiap baris luar, jadi indeks join key untuk menjadikannya pencarian sekali-tembak
• Di plan, tabel yang muncul pertama adalah luar, dan yang muncul berikutnya adalah inner
• Optimizer memilih outer / inner secara otomatis dari statistik, jadi urutan yang kamu tulis di FROM belum tentu dihormati

-- Gabungkan perf_sales dan employee pada emp_id (total penjualan per karyawan di dept 1)
-- Tanpa indeks pada perf_sales.emp_id, plan cenderung scan perf_sales inner secara penuh
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SCAN perf_sales AS s   (tanpa indeks, jadi inner juga full-scan)

-- Tambahkan indeks pada perf_sales.emp_id dan inner bisa dicari lewat indeks
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Lihat plan untuk kueri join yang menghitung penjualan per sales rep, dan baca tabel mana yang ada di loop luar. (Jalankan dengan benar dan penjelasan akan muncul.)

① Tambahkan EXPLAIN QUERY PLAN di depan kueri yang menggabungkan employee dan perf_sales pada emp_id dan menghitung baris per nama karyawan dengan GROUP BY, dan periksa plan-nya.

② Tabel yang muncul pertama di output adalah loop luar, dan yang muncul berikutnya adalah inner. Tanpa indeks pada perf_sales.emp_id, baca mana yang berakhir di luar dan bagaimana inner sedang dibaca.

Buat tabel inner dari join bisa dicari lewat indeks dan konfirmasi bahwa plan beralih dari SCAN ke SEARCH ... USING INDEX. Bungkus pembuatan indeks dan pemeriksaan plan dalam satu eksekusi.

① Buang indeks bernama sama dengan DROP INDEX IF EXISTS, lalu buat indeks pada kolom emp_id perf_sales dengan CREATE INDEX.

② Tambahkan EXPLAIN QUERY PLAN di depan kueri yang menggabungkan employee dan perf_sales pada emp_id dan menghitung baris per nama karyawan, dan periksa plan-nya. Konfirmasi bahwa employee (30 baris) tetap di loop luar sementara perf_sales inner sekarang dicari lewat indeks.

Optimizer memilih urutan join secara otomatis dari statistik

Urutan join — tabel mana yang ke loop luar — sebagai aturan, dipilih secara otomatis oleh optimizer berdasarkan statistik.

Kalau kamu telah mengumpulkan statistik dengan ANALYZE (dibahas di artikel sebelumnya), optimizer bisa lebih akurat mengestimasi "tabel mana yang lebih kecil" dan "apakah inner bisa dicari lewat indeks" dan mengoptimalkan penugasan outer / inner.

Urutan yang kamu tulis di FROM mungkin saja disusun ulang oleh optimizer.

Trik untuk membaca urutan join: di output EXPLAIN QUERY PLAN, tabel yang lebih atas lebih dekat ke loop luar.

Ketika tabel yang salah berakhir di loop luar dan hal-hal menjadi lambat, hal pertama yang diperiksa adalah apakah join key pada tabel yang kamu inginkan sebagai inner punya indeks.

-- Setelah ANALYZE, outer / inner diputuskan lebih akurat dari statistik
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
ANALYZE;

-- Bahkan dengan perf_sales pertama di FROM, optimizer mungkin menaruh employee yang lebih kecil di luar
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM perf_sales s
JOIN employee e ON e.emp_id = s.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Konfirmasi bahwa optimizer memilih urutan join yang sama bahkan ketika kamu membalik urutan tabel di FROM. Bungkus pembuatan indeks, pengumpulan statistik, dan pemeriksaan plan dalam satu eksekusi.

① Buang indeks bernama sama dengan DROP INDEX IF EXISTS, buat indeks pada emp_id perf_sales, lalu jalankan ANALYZE; untuk mengumpulkan statistik.

② Tambahkan EXPLAIN QUERY PLAN di depan kueri yang FROM-nya sekarang adalah FROM perf_sales s JOIN employee e ON ... (tabel yang lebih besar ditulis pertama di FROM) dan menghitung baris per nama karyawan, dan periksa plan-nya. Baca apakah optimizer masih memilih employee 30 baris untuk loop luar bahkan dengan urutan FROM dibalik.

Hash join dan sort-merge join — metode join yang dipakai database lain

Database besar (PostgreSQL / Oracle / SQL Server dan sebagainya) juga memakai hash join (bangun hash table dari sisi yang lebih kecil dan probe sisi lain terhadapnya) dan sort-merge join (urutkan kedua sisi berdasarkan join key dan telusuri bersama-sama) di samping nested loop join.

Engine yang menggerakkan konsol browser kursus ini hanya memakai nested loop, jadi bagian ini membahas dua metode lain di tingkat diagram-dan-konsep.

Hash join — ubah sisi yang lebih kecil menjadi hash table dan alirkan yang lain melaluinya

-- Kueri sama, secara konseptual berjalan sebagai hash join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Alur internal hash join
-- H := { e.emp_id => e | e in employee }    -- (1) Build (ubah employee menjadi hash table)
-- for each s in perf_sales:                  -- (2) Probe (alirkan perf_sales melalui)
--   if H[s.emp_id] exists: tambahkan ke hasil join

• Menaruh tabel yang lebih kecil di sisi build menjaga hash table cukup kecil untuk masuk ke memory, yang membuat hal-hal cepat
• Hanya bekerja untuk equality join (=); kondisi rentang (< / BETWEEN) tidak bisa di-join dengan cara ini
• Bisa menggabungkan jumlah baris besar di kedua sisi dengan satu pass masing-masing bahkan tanpa indeks inner, jadi sering lebih cepat daripada nested loop
• Muncul sebagai sesuatu seperti Hash Join di EXPLAIN database produksi

Sort-merge join — urutkan kedua sisi, lalu telusuri bersama

-- Kueri sama, secara konseptual berjalan sebagai sort-merge join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Alur internal sort-merge join
-- E := sort(employee by emp_id)        -- (1) Sort (urutkan keduanya berdasarkan emp_id)
-- S := sort(perf_sales by emp_id)
-- i, j := 0, 0
-- while i < |E| and j < |S|:            -- (2) Merge
--   if E[i].emp_id = S[j].emp_id: tambahkan ke hasil join, j++
--   else if E[i].emp_id < S[j].emp_id: i++
--   else: j++

• Kalau kedua sisi sudah terurut (berbaris dengan indeks, misalnya), biaya sort pada dasarnya nol dan sangat cepat
• Menangani range join (kondisi join termasuk < atau BETWEEN) juga — kekuatan yang tidak dimiliki hash join
• Hasil muncul terurut berdasarkan join key, yang nyaman untuk agregasi dan merge hilir
• Muncul sebagai sesuatu seperti Merge Join di EXPLAIN database produksi

Hash join dan sort-merge join adalah metode join dari RDBMS lain

Hash join dan sort-merge join adalah metode join yang disediakan database besar seperti PostgreSQL / Oracle / SQL Server.

Engine yang menggerakkan konsol browser kursus ini hanya memakai nested loop sebagai algoritma join-nya (ia bisa membuat indeks internal sementara untuk membantu join kalau perlu), jadi hash join dan sort-merge join tidak bisa didemonstrasikan secara live di konsol ini.

Untuk itu kita puas dengan diagram dan kode read-only di atas untuk menangkap idenya.

Sementara itu, loop outer / inner nested loop join, urutan join, dan pembalikan SCAN ke SEARCH yang didorong indeks di sisi inner, semua dibahas sebelumnya di artikel ini, bisa diamati secara nyata.

Kemampuan membaca metode join mana yang dipilih database bersandar pada pemahaman nested loop dan urutan join yang sama.

Database produksi akan menampilkan istilah seperti Hash Join / Merge Join di EXPLAIN mereka, jadi mulai dengan menjadi nyaman membaca plan nested loop di kursus ini.

-- Di bawah ini seperti apa EXPLAIN mungkin terlihat di PostgreSQL (read-only; tidak dieksekusi di konsol kursus ini)
-- EXPLAIN SELECT e.name, SUM(s.amount) FROM employee e
--   JOIN perf_sales s ON s.emp_id = e.emp_id GROUP BY e.name;
-- Contoh plan:
--   Hash Join  (bangun hash table dari employee, lalu alirkan perf_sales)
--   atau Merge Join (urutkan keduanya berdasarkan emp_id, lalu cocokkan)
-- PostgreSQL memilih di antara metode-metode ini secara otomatis berdasarkan statistik dan biaya

-- Apa yang konsol kursus ini sebenarnya bisa demonstrasikan adalah ini (nested loop):
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee / SEARCH perf_sales USING INDEX ix_sales_emp (emp_id=?)

Sebagai penutup untuk artikel ini, periksa plan join sekali lagi dengan indeks di tempat dan baca loop luar, akses indeks inner, dan arti hasilnya. Bungkus pembuatan indeks, pemeriksaan plan, dan pemeriksaan hasil dalam satu eksekusi.

① Buang indeks bernama sama dengan DROP INDEX IF EXISTS, lalu buat indeks pada emp_id perf_sales.

② Tambahkan EXPLAIN QUERY PLAN di depan kueri yang menggabungkan employee dan perf_sales pada emp_id dan menghitung penjualan per nama rep, dan periksa plan-nya.

③ Jalankan kueri agregasi yang sama (tanpa EXPLAIN QUERY PLAN) dengan ORDER BY cnt DESC LIMIT 5; untuk menarik 5 rep teratas berdasarkan jumlah. Baca plan dan hasil sebenarnya.