Algoritme Penggabungan: Nested Loop, Hash, Merge

Anda sudah mengenal INNER JOIN sebagai sintaks. Pada tingkat senior, pewawancara menanyakan bagaimana basis data menjalankan penggabungan secara fisik. Ada tiga algoritme:

• Penggabungan Perulangan Bersarang
• Penggabungan Hash
• Penggabungan dengan Pengurutan (pengurutan-penggabungan)

Jenis penggabungan logis (INNER, LEFT) tidak bergantung pada algoritmenya. Perencana memilih algoritme berdasarkan ukuran tabel, indeks, dan urutan pengurutan. Mengetahui kapan masing-masing algoritme unggul merupakan inti pelajaran ini.

Perulangan Bersarang adalah algoritme paling sederhana: untuk setiap baris tabel luar, pindai tabel dalam untuk mencari kecocokan. Dalam kode semu, ada dua perulangan, satu di dalam yang lain.

Secara naif, kompleksitasnya adalah O(luar * dalam), sehingga sangat buruk untuk tabel besar. Namun, algoritme ini menjadi sangat baik ketika sisi dalam memiliki indeks pada kunci penggabungan: setiap baris luar memicu pencarian indeks yang murah, bukan pemindaian penuh pada tabel dalam.

Algoritme ini menjadi pilihan favorit perencana ketika tabel luar berukuran kecil dan kolom penggabungan di tabel dalam memiliki indeks.

Tanda khas perulangan bersarang adalah adanya loops pada simpul dalam. Contoh ini menampilkan loops=3 karena sisi luar menghasilkan 3 baris, sehingga pemindaian indeks di sisi dalam berjalan 3 kali.

Bahaya muncul ketika sisi luar berukuran besar. Jika sisi luar menghasilkan 2 juta baris, sisi dalam berjalan 2 juta kali. Bahkan pencarian cepat selama 0.01ms pun menjadi 20 detik.

Dalam wawancara, tandai setiap perulangan bersarang yang nilai loops-nya besar pada tabel dalam tanpa indeks yang baik; itulah kueri yang lambat.

Penggabungan Hash cocok untuk tabel besar yang belum diurutkan. Algoritme ini berjalan dalam dua fase:

• Pembangunan: baca tabel yang lebih kecil dan muat ke dalam tabel hash di memori, dengan kunci kolom penggabungan.
• Penyelidikan: pindai tabel yang lebih besar; untuk setiap baris, buat hash dari kunci penggabungan lalu cari hasilnya di tabel hash.

Setiap tabel hanya dibaca sekali, sehingga kompleksitasnya kira-kira O(luar + dalam). Algoritme ini tidak memerlukan indeks maupun masukan yang sudah diurutkan, sehingga menjadi pilihan utama untuk penggabungan analitik berukuran besar dengan kondisi kesetaraan.

Ada dua hal yang harus Anda sebutkan tentang penggabungan hash:

• Algoritme ini hanya bekerja untuk kondisi penggabungan berupa kesetaraan (a.id = b.id). Kondisi rentang seperti a.x < b.y tidak dapat menggunakan penggabungan hash.
• Sisi pembangunan harus dapat dimuat dalam work_mem. Jika tidak, Postgres menulis batch sementara ke disk (Anda akan melihat Batches: > 1 dan penggunaan disk), sehingga penggabungan menjadi sangat lambat.

Jadi, penggabungan hash dengan sisi pembangunan yang sangat besar dan work_mem yang sangat kecil merupakan bug kinerja di dunia nyata yang perlu Anda soroti.

Penggabungan dengan Pengurutan (pengurutan-penggabungan) memerlukan kedua masukan sudah diurutkan berdasarkan kunci penggabungan. Algoritme ini kemudian menelusuri keduanya secara beriringan, seperti menggabungkan dua daftar terurut, dengan memajukan penunjuk yang masih tertinggal.

Algoritme ini efisien ketika masukan sudah diurutkan, misalnya langsung berasal dari indeks dalam urutan kunci, karena tidak diperlukan langkah pengurutan. Algoritme ini juga mendukung penggabungan rentang dan ketidaksetaraan, tidak seperti penggabungan hash.

Jika masukan belum diurutkan sebelumnya, perencana menambahkan simpul Sort secara eksplisit, dan biaya pengurutan tersebut mungkin membuat penggabungan hash lebih murah.

Hafalkan kapan masing-masing algoritme unggul:

• Perulangan Bersarang, untuk tabel luar berukuran kecil dan kunci penggabungan di tabel dalam yang memiliki indeks; juga merupakan satu-satunya pilihan untuk penggabungan non-kesetaraan tanpa masukan yang sudah diurutkan.
• Penggabungan Hash, untuk tabel besar yang belum diurutkan dan digabungkan berdasarkan kesetaraan; tidak memerlukan indeks.
• Penggabungan dengan Pengurutan, ketika kedua masukan sudah diurutkan berdasarkan kuncinya, sering kali melalui indeks, atau untuk penggabungan rentang; sangat baik untuk kumpulan data yang sangat besar dan sudah diurutkan.

Perencana memperkirakan biaya setiap algoritme dan memilih yang termurah berdasarkan perkiraan jumlah barisnya.

Penggunaan sumber daya sangat berbeda, dan pewawancara sering menguji pemahaman ini:

• Perulangan Bersarang, memerlukan memori minimal; biayanya didominasi oleh pencarian di sisi dalam yang dilakukan berulang kali.
• Penggabungan Hash, memerlukan memori untuk tabel hash; menulis data sementara ke disk jika ukurannya terlalu besar.
• Penggabungan dengan Pengurutan, murah saat penggabungan, tetapi mahal jika harus mengurutkan terlebih dahulu; pengurutan juga menggunakan work_mem dan dapat menulis data sementara ke disk.

Jadi, menaikkan work_mem dapat mengubah penggabungan hash atau pengurutan yang lambat karena menulis ke disk menjadi operasi dalam memori. Ini merupakan jawaban optimasi yang konkret.

Kasus klasik: sebuah kueri cepat di lingkungan pengembangan, tetapi lambat di produksi. Rencana menunjukkan Perulangan Bersarang dengan loops=3000000.

Perencana meremehkan jumlah baris luar (statistik usang menyatakan 3 baris, sedangkan kenyataannya 3 juta), sehingga memilih perulangan bersarang. Dengan statistik yang akurat, perencana akan memilih penggabungan hash.

Jawaban Anda dalam wawancara: jalankan ANALYZE agar perkiraannya benar; perencana kemudian akan beralih ke penggabungan hash dan kueri akan menjadi jauh lebih cepat.

Biasanya Anda sebaiknya tidak memaksa algoritme, tetapi Anda dapat melakukannya saat pengujian untuk membandingkan hasilnya. Postgres menyediakan sakelar per metode:

SET enable_nestloop = off; dan sakelar serupa untuk enable_hashjoin serta enable_mergejoin. Matikan salah satunya, jalankan kembali EXPLAIN ANALYZE, lalu amati apakah alternatif tersebut benar-benar lebih cepat.

Perbaikan yang tepat tetap meliputi statistik terbaru, indeks yang sesuai, work_mem yang memadai, dan predikat selektif. Pemaksaan hanya untuk diagnosis.

Satukan semuanya untuk beban kerja analitik yang menggabungkan dua tabel fakta dan dimensi berukuran besar berdasarkan sebuah pengenal:

• Jika tabel dimensi dapat dimuat ke memori, perkirakan Penggabungan Hash, yang sering kali menjadi pilihan terbaik.
• Jika keduanya datang dalam keadaan terurut dari indeks, Penggabungan dengan Pengurutan dapat menghindari pembangunan tabel hash.
• Perulangan Bersarang dalam situasi ini merupakan tanda bahaya, yang biasanya disebabkan oleh perkiraan yang buruk.

Membaca penggabungan mana yang dipilih perencana dan menilai apakah pilihan itu seharusnya demikian merupakan sinyal tingkat senior yang tepat yang diuji oleh pertanyaan-pertanyaan ini.

Anda menggabungkan dua tabel besar yang belum diurutkan berdasarkan kondisi kesetaraan a.id = b.id, tidak ada yang memiliki indeks yang berguna, dan statistiknya akurat. Algoritme penggabungan mana yang kemungkinan besar akan dipilih perencana?

Tiga algoritme penggabungan:

• Perulangan Bersarang, jumlah baris luar dikalikan pencarian di sisi dalam; sangat baik jika sisi luar kecil dan kunci sisi dalam memiliki indeks, tetapi berbahaya ketika loops sangat besar.
• Penggabungan Hash, pembangunan dan penyelidikan; terbaik untuk penggabungan kesetaraan pada tabel besar yang belum diurutkan, hanya berlaku untuk kesetaraan dan dibatasi oleh work_mem.
• Penggabungan dengan Pengurutan, menelusuri masukan yang sudah diurutkan secara beriringan; ideal ketika data sudah diurutkan atau untuk penggabungan rentang.

Perencana memilih berdasarkan biaya dan statistik. Perulangan bersarang yang mengejutkan dengan jumlah perulangan sangat besar hampir selalu berarti perkiraan jumlah baris yang buruk; perbaiki statistiknya.