Statistik Multivariat untuk Kolom Berkorelasi

Ketika PostgreSQL mengestimasi jumlah baris yang akan dikembalikan oleh suatu kueri, PostgreSQL mengandalkan statistik per kolom yang disimpan dalam pg_statistic. Untuk menggabungkan predikat pada beberapa kolom, perencana membuat asumsi penyederhanaan yang penting: kolom-kolom tersebut independen secara statistik.

Dengan asumsi independensi, selektivitas WHERE a = 1 AND b = 2 dihitung sebagai sel(a=1) * sel(b=2). Perkalian tersebut cepat dan benar — tetapi hanya jika kolom-kolom tersebut benar-benar tidak berkaitan.

Dalam skema nyata, kolom sering berkorelasi: sebuah kota menunjukkan kode pos, sebuah produk menunjukkan kategori, dan tanggal pesanan menunjukkan kuartal fiskal. Ketika perencana mengalikan selektivitas untuk kolom yang berkorelasi, estimasinya dapat jatuh jauh di bawah kenyataan.

Estimasi jumlah baris yang meleset beberapa orde besarnya dapat mengarahkan perencana ke rencana yang salah:

• Perkiraan terlalu rendah → perencana memilih loop bersarang dengan harapan 3 baris, tetapi 300.000 baris tiba → loop menjalankan sisi dalamnya ratusan ribu kali.
• Perkiraan terlalu rendah → perencana memilih pemindaian indeks + pengambilan dari heap, bukan satu pemindaian sekuensial yang seharusnya lebih murah.
• Urutan gabungan buruk → hasil antara yang besar diwujudkan terlalu awal, sehingga penggunaan memori melonjak dan data meluber ke disk.

Gejala yang terlihat dalam EXPLAIN ANALYZE adalah kesenjangan lebar antara rows= (estimasi) dan actual rows=. Kesenjangan tersebut merupakan tanda bahwa korelasi mungkin menjadi penyebabnya.

Perhatikan tabel addresses yang kolom city-nya menentukan state secara fungsional — setiap baris dengan city = 'New York' juga memiliki state = 'NY'. Kedua predikat memilih baris yang sama, sehingga selektivitas gabungannya sama dengan sel(city) saja.

Namun, perencana mengalikannya: sel(city) * sel(state), sehingga menghasilkan estimasi yang dapat 10× atau 100× terlalu kecil. Pada keluaran EXPLAIN ANALYZE di bawah ini, perhatikan kesenjangan antara jumlah baris yang diestimasi dan jumlah baris aktual pada simpul pemindaian.

PostgreSQL 10+ memungkinkan Anda mengajarkan hubungan antar kolom kepada perencana melalui objek statistik ekstensi, yang dibuat dengan CREATE STATISTICS.

Objek statistik ekstensi menetapkan sekumpulan kolom (atau ekspresi) pada satu tabel serta satu atau beberapa jenis statistik yang akan dikumpulkan untuk kolom-kolom tersebut. Setelah dibuat dan dianalisis, perencana menggunakan statistik multivariat ini, bukan mengalikan selektivitas per kolom secara membabi buta.

Ketiga jenis tersebut adalah:

• ndistinct — jumlah kombinasi berbeda dari kolom-kolom yang tercantum.
• dependencies — tingkat dependensi fungsional antar kolom.
• mcv — daftar nilai paling umum pada kelompok kolom.

Jenis dependencies menangkap dependensi fungsional: seberapa kuat nilai suatu kolom menyiratkan nilai kolom lain. PostgreSQL menyimpan tingkat antara 0 dan 1 untuk setiap arah.

Untuk tabel kita, city → state memiliki tingkat mendekati 1.0 (mengetahui kota sepenuhnya menentukan negara bagian), sedangkan state → city jauh lebih rendah (sebuah negara bagian memiliki banyak kota).

Ketika perencana mengevaluasi WHERE city = ? AND state = ? dan menemukan dependensi city → state yang kuat, perencana berhenti mengalikan dan sebagai gantinya mempertahankan selektivitas kolom penentu pada dasarnya.

Setelah ANALYZE, nilai yang dihitung berada dalam tampilan katalog pg_stats_ext (bentuk mentah) dan pg_stats_ext_exprs untuk statistik ekspresi. Kolom dependencies menampilkan tingkat untuk setiap arah.

Tingkat pada atau mendekati 1.000000 untuk "1 => 2" (kolom 1 menyiratkan kolom 2) mengonfirmasi dependensi fungsional yang hampir sempurna — tepat pada kasus ketika asumsi independensi merugikan Anda.

Jenis ndistinct mencatat jumlah kombinasi berbeda di seluruh kolom yang tercantum. Tanpanya, perencana mengestimasi kombinasi berbeda sebagai hasil kali jumlah nilai berbeda per kolom, yang dapat sangat berlebihan untuk kolom yang berkorelasi.

Hal ini paling penting untuk GROUP BY a, b, c (mengestimasi jumlah kelompok) dan untuk agregat berkelompok yang menjadi masukan agregat hash. Estimasi kelompok yang salah menyebabkan tabel hash berukuran terlalu kecil dan data meluber ke disk, atau menyebabkan agregat berbasis pengurutan dipilih secara keliru.

Dependensi fungsional mengasumsikan hubungan yang seragam di seluruh tabel. Namun, terkadang korelasinya spesifik terhadap nilai — kombinasi tertentu sangat umum, sementara kombinasi lainnya tidak pernah muncul. Di situlah jenis MCV (nilai yang paling umum) unggul.

Daftar MCV pada sekelompok kolom menyimpan kombinasi yang benar-benar sering muncul beserta frekuensinya, sehingga perencana dapat memperkirakan predikat seperti WHERE category = 'A' AND status = 'shipped' menggunakan frekuensi nyata yang diamati untuk pasangan tersebut, bukan perkiraan turunan.

MCV adalah jenis yang paling kuat, tetapi juga paling banyak menggunakan penyimpanan; gunakan jenis ini ketika dependensi saja belum memperbaiki perkiraan.

Anda dapat meminta beberapa jenis dalam satu objek statistik. Jika Anda menghilangkan seluruh daftar jenis, PostgreSQL akan membuat semua jenis yang berlaku untuk kumpulan kolom tersebut.

Pola yang umum dan praktis adalah mencantumkan ndistinct, dependencies, mcv sekaligus untuk sekumpulan kolom yang muncul bersama dalam klausa WHERE dan GROUP BY. Satu kali ANALYZE kemudian mengisi semuanya.

Perhatikan bahwa mcv dan dependencies hanya mendukung jumlah kolom yang terbatas, dan sebaiknya Anda memusatkan objek statistik pada kolom yang memang dikuerikan bersama — bukan setiap pasangan kolom dalam tabel.

PostgreSQL 14+ memperluas CREATE STATISTICS agar mendukung ekspresi, bukan hanya kolom biasa. Jika kueri Anda memfilter berdasarkan date_trunc('month', created_at) atau lower(email), biasanya perencana tidak memiliki statistik untuk nilai hasil perhitungan tersebut dan kembali menggunakan perkiraan umum.

Objek statistik dengan satu ekspresi memberikan statistik per ekspresi kepada perencana; objek dengan banyak kolom yang mencampurkan ekspresi dan kolom menangkap korelasi antara nilai hasil perhitungan dan kolom yang tersimpan.

Statistik tambahan tidak dibuat secara otomatis — Anda membuatnya dengan sengaja berdasarkan kesalahan perkiraan yang teramati. Alur kerja yang andal:

• Temukan kueri yang EXPLAIN ANALYZE-nya menunjukkan selisih besar antara perkiraan dan kenyataan pada predikat dengan banyak kolom.
• Buat objek statistik tepat pada kolom-kolom yang berkorelasi tersebut.
• Jalankan ANALYZE pada tabel (atau tunggu analisis oleh autovacuum) untuk mengisinya.
• Jalankan kembali EXPLAIN ANALYZE dan pastikan perkiraan tersebut kini mengikuti kenyataan.

Objek statistik diperbarui setiap kali ANALYZE dijalankan, sehingga setelah dibuat, objek tersebut tetap mutakhir secara otomatis. Hapus objek yang tidak lagi diperlukan dengan DROP STATISTICS agar Anda tidak perlu menanggung biaya ANALYZE-nya.

Perencana mengasumsikan kolom-kolom tidak saling bergantung dan mengalikan selektivitas tiap kolom — hal ini meremehkan jumlah baris ketika kolom saling berkorelasi, sehingga menghasilkan rencana yang buruk.

• CREATE STATISTICS mengajarkan perencana tentang hubungan antarkolom.
• dependencies memperbaiki perkiraan yang terlalu rendah pada filter kesetaraan akibat dependensi fungsional (misalnya city → state).
• ndistinct memperbaiki perkiraan kombinasi berbeda untuk GROUP BY dan agregat berkelompok.
• mcv menangkap kombinasi yang miring dan spesifik terhadap nilai untuk mendapatkan selektivitas per pasangan yang paling akurat.
• Buat statistik pada ekspresi (PG14+), perbarui melalui ANALYZE, verifikasi dengan EXPLAIN ANALYZE, dan periksa hasilnya di pg_stats_ext.

Sasar hanya kolom yang benar-benar dikuerikan bersama, lalu pastikan selisih antara perkiraan dan kenyataan menyusut.