Algoritma Operasi Join

Back to IF3140 Sistem Basis Data

Topic

Questions/Cues

• Apa saja algoritma join utama?

• Bagaimana cara kerja Nested-Loop Join?

• Apa itu Block Nested-Loop Join?

• Kapan Indexed Nested-Loop Join efisien?

• Bagaimana prinsip Merge-Join?

• Apa itu Hash-Join?

• Fase Partisi vs. Build/Probe di Hash-Join?

• Bagaimana menangani overflow pada Hash-Join?

• Apa itu Hybrid Hash-Join?

• Cara menangani join kompleks (AND/OR)?

Reference Points

• Slides 26-44

Nested-Loop Join

Ini adalah algoritma join yang paling dasar dan sederhana.

• Cara Kerja: Untuk setiap tuple di relasi luar (r), pindai seluruh relasi dalam (s) untuk mencari pasangan yang memenuhi kondisi join.

• Kelebihan: Dapat digunakan untuk semua jenis kondisi join (tidak hanya kesetaraan) dan tidak memerlukan indeks.

• Kekurangan: Sangat tidak efisien dan mahal.

• Estimasi Biaya (Worst Case): $(n_r\ast b_s+b_r)$ blok $+(n_r+b_r)$ seek time, di mana $n_r$ adalah jumlah record di relasi r dan $b_s$ adalah jumlah blok di relasi s.

• Best Case: Jika relasi luar $r$ sangat kecil.

• Worst Case: Jika $r$ dan $s$ sama-sama besar.

Block Nested-Loop Join

Merupakan variasi dari Nested-Loop Join yang bekerja pada level blok, bukan tuple.

• Cara Kerja: Untuk setiap blok di relasi luar (r), pindai seluruh blok di relasi dalam (s). Kemudian, untuk setiap pasang blok, semua kombinasi tuple di dalamnya akan diperiksa.

• Estimasi Biaya (Worst Case): $(b_r\ast b_s+b_r)+(2\ast b_r)$

• Optimasi: Alokasikan $M-2$ blok memori untuk relasi luar, sehingga dapat membaca $M-2$ blok sekaligus dan mengurangi jumlah pemindaian relasi dalam. Biaya menjadi $\lceil b_r/(M-2)\rceil \ast b_s+b_r$.

• Best Case: Jika relasi luar $r$ yang dipilih sangat kecil, sehingga muat dalam memori yang tersedia ($b_r\le M-2$).

• Worst Case: Jika $r$ dan $s$ sama-sama besar.

Indexed Nested-Loop Join

Algoritma ini memanfaatkan indeks pada atribut join dari relasi dalam untuk mempercepat pencarian.

• Syarat: Kondisi join harus berupa equi-join (atau natural join) dan harus ada indeks pada atribut join relasi dalam.

• Cara Kerja: Untuk setiap tuple di relasi luar (r), gunakan indeks pada relasi dalam (s) untuk langsung menemukan tuple yang cocok, tanpa perlu memindai seluruh relasi s.

• Estimasi Biaya: $b_r(t_t+t_s)+n_r\ast c$, di mana c adalah biaya untuk mencari dan mengambil semua tuple yang cocok di s untuk satu tuple r menggunakan indeks.

• Best Case: Jika relasi luar $r$ sangat kecil DAN indeks yang dipilih sangat selektif pada atribut join di relasi dalam $s$.

• Worst Case: Jika indeks relasi dalam $s$ TIDAK selektif.

Merge-Join

Algoritma ini efisien untuk equi-joins dan natural joins.

• Cara Kerja:

  1. Sort: Urutkan kedua relasi (r dan s) berdasarkan atribut join mereka.

  2. Merge: Pindai kedua relasi yang sudah terurut secara bersamaan (mirip fase merge pada External Sort-Merge) untuk menemukan tuple yang cocok. Pointer akan bergerak maju secara sinkron di kedua relasi.

• Estimasi Biaya (jika relasi sudah terurut): $b_r+b_s$ transfer blok, karena setiap blok hanya perlu dibaca sekali. Jika belum terurut, biaya sorting harus ditambahkan.

• Best Case: Jika relasi luar $r$ dan relasi dalam $s$ sudah terurut.

• Worst Case: Jika $r$ dan $s$ tidak terurut.

• Secara umum: $b_r+b_s+\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil$

Hash-Join

Ini adalah algoritma yang sangat efisien untuk equi-joins, terutama pada data besar.

• Cara Kerja:

  1. Fase Partisi (Partition Phase):

     • Pilih relasi yang lebih kecil sebagai build input (misalnya s).

     • Gunakan fungsi hash h1 pada atribut join untuk mempartisi s dan r ke dalam n bucket atau partisi ($s_0,s_1,...$ dan $r_0,r_1,...$).

     • Tulis partisi-partisi ini ke disk. Keuntungannya adalah tuple di $r_i$ hanya mungkin cocok dengan tuple di $s_i$.

  2. Fase Build & Probe (Matching Phase):

     • Untuk setiap partisi i:

       1. Build: Baca partisi $s_i$ ke memori dan bangun hash table di memori menggunakan fungsi hash kedua ($h_2$).

       2. Probe: Baca partisi $r_i$ blok per blok, dan untuk setiap tuple, gunakan h2 untuk mencari pasangannya di hash table $s_i$.

• Penanganan Overflow: Jika partisi $s_i$ tidak muat di memori, partisi tersebut dapat dipartisi ulang secara rekursif menggunakan fungsi hash lain, atau gunakan Block Nested-Loop Join untuk partisi yang meluap tersebut.

• Estimasi Biaya (tanpa rekursi): Sekitar $(3(b_r+b_s)+4n_h)+2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )$

• Best Case: Paling baik untuk operasi equi-join pada data besar dengan memori yang cukup, dan ketika fungsi hash mampu mendistribusikan kunci join secara merata ke semua partisi. Distribusi yang merata memastikan tidak ada partisi yang “meluap” (overflow) dan setiap partisi dari relasi build ($s_i$​) bisa dimuat ke memori saat fase probe. Varian Hybrid Hash-Join memberikan optimasi lebih lanjut dalam skenario ini.

• Worst Case: Ketika terjadi kemiringan data (data skew) yang signifikan pada atribut join. Ini berarti banyak sekali record memiliki nilai atribut join yang sama. Akibatnya, fungsi hash akan menempatkan semua record tersebut ke dalam satu partisi yang sama.

Hybrid Hash-Join

Sebuah optimasi dari Hash-Join ketika memori cukup besar.

• Cara Kerja: Selama fase partisi build input (s), partisi pertama ($s_0$) tidak ditulis ke disk, melainkan langsung disimpan di memori sebagai hash table. Ketika probe input (r) dipartisi, tuple yang masuk ke partisi $r_0$ tidak ditulis ke disk, melainkan langsung digunakan untuk mencari pasangan di hash table $s_0$. Ini menghemat I/O untuk satu partisi penuh.

Complex Joins

• Join dengan Kondisi Konjungtif (AND): $r{\bowtie }_{{\theta }_1\wedge {\theta }_2}s$

  • Hitung join untuk kondisi yang paling selektif (misalnya ${\theta }_1$), lalu terapkan kondisi sisanya (${\theta }_2$) sebagai filter pada hasilnya.

• Join dengan Kondisi Disjungtif (OR): $r{\bowtie }_{{\theta }_1\vee {\theta }_2}s$

  • Hitung hasil join untuk setiap kondisi secara terpisah ($r{\bowtie }_{{\theta }_1}s$dan$r{\bowtie }_{{\theta }_2}s$).

  • Gabungkan hasilnya menggunakan operasi UNION.

Summary

Pemilihan algoritma join adalah salah satu keputusan paling kritis dalam optimasi query, dengan setiap algoritma memiliki kelebihan pada skenario yang berbeda. Nested-Loop Join adalah metode universal tetapi lambat. Block Nested-Loop Join memberikan perbaikan sederhana. Indexed Nested-Loop Join sangat cepat jika tersedia indeks yang sesuai. Merge-Join efisien untuk equi-join pada data yang sudah atau dapat diurutkan dengan mudah. Terakhir, Hash-Join seringkali menjadi pilihan tercepat untuk equi-join pada data besar, dengan varian Hybrid Hash-Join yang lebih lanjut mengoptimalkan penggunaan memori untuk mengurangi I/O disk.

Additional Information

Tabel Perbandingan Algoritma Join

Algoritma	Kapan Digunakan Terbaik	Persyaratan	Kelemahan
Nested-Loop	Relasi sangat kecil atau sebagai fallback	Tidak ada	Sangat lambat untuk data besar
Block Nested-Loop	Salah satu relasi kecil, memori terbatas	Tidak ada	Kurang efisien dibanding hash/merge
Indexed Nested-Loop	Relasi luar kecil, ada indeks efisien di relasi dalam	Indeks pada atribut join	Performa buruk jika indeks tidak selektif
Merge-Join	Kedua relasi sudah terurut atau output perlu diurutkan	Equi-join, data terurut	Biaya sorting awal bisa mahal
Hash-Join	Equi-join pada data besar, memori cukup	Equi-join	Sensitif terhadap data miring (skew) dan ukuran memori

Dampak Data Skew (Kemiringan Data) pada Hash-Join

Kelemahan utama Hash-Join adalah jika data pada atribut join tidak terdistribusi merata (miring). Misalnya, jika banyak sekali tuple memiliki nilai yang sama pada atribut join, maka fungsi hash akan menempatkan semua tuple tersebut ke dalam satu partisi yang sama. Partisi ini akan menjadi sangat besar dan menyebabkan overflow, yang akan memaksa sistem menggunakan algoritma yang lebih lambat seperti Block Nested-Loop Join pada partisi tersebut, sehingga mengurangi efisiensi keseluruhan.

Eksplorasi Mandiri

Gunakan perintah EXPLAIN atau EXPLAIN ANALYZE pada DBMS favorit Anda untuk melihat bagaimana query optimizer memilih algoritma join.

1. Buat dua tabel, A dan B.

2. Lakukan JOIN tanpa membuat indeks apa pun. Kemungkinan besar optimizer akan memilih Hash Join atau Merge Join.

3. Buat indeks B-Tree pada kolom join di tabel B.

4. Jalankan kembali query JOIN. Jika tabel A cukup kecil, optimizer mungkin akan beralih ke Indexed Nested-Loop Join dengan A sebagai relasi luar dan B sebagai relasi dalam. Ini menunjukkan bagaimana optimizer secara dinamis memilih strategi terbaik berdasarkan struktur data yang tersedia.