10 Tahun Peningkatan Optimizer PostgreSQL

• Membandingkan latensi kueri persentil ke-90 dengan Join Order Benchmark dari PostgreSQL 8 hingga 16, dan secara empiris mengonfirmasi peningkatan kinerja tail jangka panjang
• Dibandingkan PostgreSQL 8, PostgreSQL 16 memangkas latensi tail hampir setengahnya, sementara rentang 13–16 secara umum tetap berada pada level yang stabil
• Dalam analisis regresi, setiap kenaikan satu versi mayor menunjukkan rata-rata peningkatan kinerja 15%, tetapi model linear mungkin tidak menjelaskan pola perubahannya dengan baik
• Eksperimen menetapkan kondisi tetap: GCC 13.2, Arch Linux Docker, shared_buffers 8GB, work_mem 8MB, untuk berfokus pada kualitas query optimizer
• Saat menafsirkan besarnya peningkatan, perubahan pada execution engine seperti parallel worker dan kompilasi JIT juga perlu dipertimbangkan, bukan hanya optimizer

---

Konfigurasi Benchmark PostgreSQL 8–16

• Objek analisis adalah versi mayor 8 hingga 16 dari PostgreSQL, query optimizer open source
• Benchmark yang digunakan adalah Join Order Benchmark, kumpulan kueri dengan banyak join kompleks
  • Benchmark ini diperkenalkan dalam makalah “How Good are Query Optimizers, Really?”
• Setiap versi PostgreSQL dibangun dengan GCC 13.2 di dalam container Arch Linux Docker
• Lingkungan pengukuran disesuaikan untuk melihat kualitas query optimizer, bukan kinerja indeks atau I/O
  • shared_buffers disetel ke 8GB, cukup besar untuk menampung seluruh database
  • work_mem ditetapkan 8MB pada semua versi
• Setiap kueri dijalankan sekali untuk pemanasan cache, lalu latensi median dari 5 eksekusi tambahan dicatat
• Untuk setiap versi mayor, digunakan versi minor terbaru
  • Misalnya, untuk PostgreSQL 8, yang diuji adalah 8.4.22
  • Versi-versi minor tersebut biasanya dirilis setelah versi mayor baru, tetapi umumnya hanya berisi perbaikan bug dan tidak mencakup fitur baru atau peningkatan kinerja

Hasil Pengukuran dan Interpretasi

• Kinerja tail PostgreSQL secara keseluruhan meningkat besar
  • Jika membandingkan PostgreSQL 8 dan 16, latensi tail berkurang hampir setengahnya
  • Dari PostgreSQL 13 hingga 16, levelnya secara umum tetap stabil
• Analisis regresi digunakan untuk memeriksa apakah tren penurunan antara nomor versi mayor dan latensi kueri signifikan, serta mengkuantifikasi besarnya peningkatan per versi
  • Berdasarkan regresi linear, setiap versi mayor baru menunjukkan rata-rata peningkatan kinerja 15% pada Join Order Benchmark
  • Namun, model linear mungkin kurang tepat untuk mengukur pola perubahan sebenarnya
• Sulit menjelaskan seluruh peningkatan hanya dengan query optimizer
  • Peningkatan execution engine seperti parallel worker dan kompilasi JIT juga memengaruhi kinerja
  • Bagaimana query plan untuk setiap kueri JOB berubah dari tahun ke tahun masih menjadi subjek analisis terpisah
• Jika meningkatkan dari PostgreSQL 8 ke 16, latensi tail workload kemungkinan dapat berkurang secara signifikan
• Dalam perbandingan riset, penting untuk melihat bahwa PostgreSQL sendiri adalah baseline yang terus menguat
  • Neo dan Bao dibandingkan dengan PostgreSQL 11, sedangkan riset yang lebih baru dibandingkan dengan PostgreSQL 14, 15, 16
  • Meskipun teknik lama meningkat 30% dibandingkan PostgreSQL dan teknik terbaru meningkat 25%, teknik terbaru mungkin dibandingkan dengan PostgreSQL yang lebih kuat
• Nilai pengukuran asli dapat dilihat di raw data

[GN⁺]

Komentar Hacker News

• Saya sudah memakai Postgres selama 15 tahun, dan sebagian besar karier saya dihabiskan untuk memodelkan serta menyelesaikan masalah optimisasi matematis; menurut saya ada tiga hal inti dalam topik ini
  Semua masalah optimisasi membutuhkan data biaya, dan makin banyak serta makin baik datanya, makin bagus hasilnya. Postgres memang sudah mengalami perbaikan seperti statistik lintas kolom, tetapi masih ada celah besar seperti latensi system call. Latensi membaca halaman dari disk sangat berbeda antar sistem, tetapi Postgres tidak mengukurnya secara langsung dan malah bergantung pada nilai konfigurasi. Statistik foreign key juga masih belum ada, sehingga join yang mengikuti foreign key seharusnya tidak menghasilkan rencana yang buruk, tetapi kadang masih terjadi
  Terutama untuk kueri yang besar dan mahal, dibutuhkan perencanaan yang ditunda atau rencana skenario alternatif. Saat ini rencana ditetapkan sebelum eksekusi, tetapi jumlah baris atau estimasi kardinalitas yang didapat pada tahap awal eksekusi bisa sangat memperbaiki rencana tahap berikutnya
  Machine learning juga merupakan area yang masih bisa ditingkatkan, tetapi upaya-upaya yang saya lihat sejauh ini belum mengesankan. Alih-alih memakai machine learning untuk rencana itu sendiri, sebaiknya digunakan untuk penemuan dan estimasi biaya. Buat model biaya yang lebih baik, lalu biarkan mesin optimisasi memanfaatkan data itu

  • Ingin mendengar pendapat lebih lanjut. Misalnya, cukup mengejutkan bahwa latensi system call ada di daftar teratas. Pandangan umum di komunitas database tampaknya adalah bahwa model biaya umumnya lumayan, sedangkan estimasi kardinalitaslah yang benar-benar buruk
    Untuk perencanaan yang ditunda/alternatif, saya penasaran apakah adaptive query execution adalah pendekatan yang masuk akal. Informasi dari awal eksekusi kueri memang bisa memengaruhi rencana berikutnya, tetapi jika beberapa join pertama sudah dipilih dengan buruk—dan itu sering terjadi—ada kekhawatiran bahwa tanpa hal seperti Yannakakis/SIPs akan sulit untuk pulih
    Soal “machine learning untuk optimisasi kueri”, jelas saya punya bias. Namun, semua pendekatan “machine learning untuk perencanaan” yang pernah saya lihat pada akhirnya secara internal memakai machine learning untuk penemuan/estimasi biaya. Pendekatan-pendekatan ini mencoba menyeimbangkan antara kualitas data yang dikumpulkan, yaitu eksplorasi, dan kualitas rencana yang dihasilkan, yaitu eksploitasi. Menariknya, jika machine learning dipakai dengan cara yang sepenuhnya dipisahkan dari perencanaan, estimasinya memang jadi lebih akurat, tetapi rencana kueri yang sebenarnya justru memburuk: https://people.csail.mit.edu/tatbul/publications/flowloss_vl...
    Saya punya kepentingan di bidang ini, jadi harap pertimbangkan itu saat membaca pendapat saya
  • Rencana alternatif memang terdengar sangat bagus. Belum lama ini saya melihat sebuah rencana kueri yang memperkirakan sekitar 1.000 baris akan keluar dari suatu subkueri, lalu memasangkan nested loop ke index scan, padahal kenyataannya sekitar 1 miliar baris
    Saya masih belum tahu kenapa estimasinya bisa meleset separah itu, tetapi jika ketika jumlah baris melewati ambang tertentu bisa berpindah dari nested loop ke hash join, itu tampaknya akan sangat membantu menghindari rencana yang katastrofik
  • Saya penasaran apa tepatnya maksud pernyataan bahwa statistik foreign key belum ada. Postgres, seperti banyak database relasional lain, memang tidak otomatis membuat indeks pada foreign key, jadi saya rasa itu sudah diketahui
    Apakah yang dimaksud adalah masalah urutan join?
  • Saya penasaran apakah MSSQL dianggap lebih baik dalam hal ini

• Pengoptimal kueri Postgres berusaha mengurangi jumlah halaman yang dibaca dari disk dan jumlah halaman yang ditulis ke disk sebagai hasil antara. Jadi tampaknya keliru jika shared buffers dibuat sangat besar hingga memuat semua data lalu dipakai untuk benchmark pengoptimal kueri
  Dengan begitu, yang diukur bukan kualitas rencana kueri yang dihasilkan, melainkan kecepatan pengoptimal kueri dan pemroses join. Bahkan tidak mengejutkan kalau sebenarnya rencana yang dihasilkan di setiap versi sama saja, dan yang diukur hanya kecepatan eksekusinya

  • Tidak begitu. Yang dioptimalkan adalah biaya yang juga mencakup hal-hal seperti penggunaan CPU, bukan hanya halaman yang dibaca dari disk
    Biaya adalah satuan arbitrer yang dibuat agar berkorelasi dengan waktu yang dibutuhkan, bukan jumlah pembacaan disk, jadi membandingkan rencana saat semuanya ada di RAM pun tetap sepenuhnya valid. Secara konvensi, satu pembacaan halaman dari disk diskalakan sebagai 1.0, tetapi itu berbeda dari mengatakan “pengoptimal meminimalkan jumlah pembacaan halaman disk”. Kita juga bisa saja menetapkan 1ms pada mesin tertentu sebagai 1.0
  • Memang mungkin saja rencananya mirip dan yang diukur adalah perbaikan pada mesin eksekusi. Join Order Benchmark dirancang untuk menguji kualitas pengoptimal
    Pengoptimal PG berusaha mengurangi bukan hanya jumlah halaman yang dibaca dari disk, tetapi juga jumlah tuple yang diperiksa CPU, jumlah evaluasi ekspresi kondisi, dan sebagainya; semua angka itu digabung menjadi “biaya”, yang menjadi fungsi yang diminimalkan pengoptimal
    Pengukuran performa cold cache dan warm cache bisa menghasilkan hasil yang berbeda, dan eksperimen ini jelas merupakan skenario warm cache. Namun, cold cache pun punya masalah yang disebut tadi. Pada ukuran data Join Order Benchmark, penghematan beberapa I/O dari perbaikan B-tree PG bisa jadi lebih dominan daripada perbaikan berbasis CPU
    Sebagai referensi, rencana untuk kueri latensi P90 berubah dari rencana yang memakai loop join dan merge join di PG 8.4 menjadi rencana yang memakai hash join di PG 16, dan kueri ini tidak lagi menjadi kueri P90. Setidaknya ini bisa dilihat sebagai bukti adanya sebagian perbaikan pada pengoptimal

• Tulisan itu menyebut kompiler JIT PostgreSQL, tetapi sejauh ini saya hanya melihatnya menurunkan performa kueri. Saya memasukkan penonaktifannya ke checklist instalasi

  • Seorang pelanggan mengalami masalah performa terburuk setelah pindah ke Postgres. Anehnya, itu hanya terjadi pada Docker dan konfigurasi server uji, tidak pada mesin developer. Developer tersebut menjalankan Postgres dari Homebrew
    Ternyata Homebrew menginstal Postgres tanpa dukungan JIT, dan pada mesin developer suatu kueri selesai dalam 200ms, sedangkan di lingkungan dengan JIT aktif butuh 4–5 detik. Saya bukan pengguna Postgres yang terlalu mendalam, jadi butuh waktu untuk menemukan penyebabnya, dan sejak itu saya selalu mematikan JIT dan tidak pernah menoleh lagi
  • Kompiler JIT sangat bagus untuk kueri analitis
    Di PostgreSQL, ambang aktivasi JIT juga bisa diatur, jadi ambang kapan JIT menyala bisa dinaikkan
  • JIT di pg cukup menunjukkan bahwa LLVM tidak terlalu bagus untuk JIT, dan keadaan makin buruk karena Postgres tidak punya cache kueri bersama yang persisten
    Mungkin akan lebih tidak merugikan jika bisa melakukan kompilasi asinkron untuk kueri-kueri berikutnya. Sebenarnya JIT pada umumnya, terutama backend optimisasi, lebih dekat ke cara itu
  • Apakah Postgres memang tidak bisa melakukan JIT compile sebuah kueri sekali saja lalu menjalankan kueri yang sudah dikompilasi itu berkali-kali?

• Menarik, tetapi sistem penomoran versi Postgres berubah di v10. 9.6, 9.5, 9.4, 9.3, 9.2, 9.1, 9.0, 8.4, 8.3, 8.2, 8.1, 8.0 pada dasarnya semuanya adalah versi mayor yang berbeda
  Akan menarik juga melihat bagaimana performa berubah di versi-versi tersebut

  • Meski begitu, saya tetap berterima kasih karena dari v9.0 sampai 9.6 mereka mempertahankan kompatibilitas filesystem versi mayor agar upgrade in-place yang lebih cepat bisa dilakukan hanya dengan mengganti biner
    Mungkin hal itu juga membatasi mereka, tetapi update tahunan yang membutuhkan downtime lebih lama atau reindexing tambahan jelas tidak menyenangkan, dan mungkin inilah alasan banyak situs menunda upgrade sampai dukungan versi sebelumnya berakhir. Terutama bagi pengguna AWS RDS
    Upgrade replikasi logis sejak v10 memang punya kelebihan dari sisi ketersediaan, tetapi jika skemanya tidak cukup sederhana, itu adalah proyek besar dengan biaya yang tak terhindarkan dan risiko yang besar
  • Sepenuhnya setuju. Saya memilih versi terbaru dari tiap versi mayor dengan menafsirkan nomor versi dalam gaya semver, tetapi itu berbeda dari cara PostgreSQL secara tradisional memperlakukan nomor versi mayor
    Misalnya, PG 8.2 dan 8.1 adalah versi mayor yang berbeda, tetapi saya menafsirkannya seperti versi minor. Alasan utama saya melakukan ini adalah untuk mengurangi jumlah versi yang harus diuji, dan saya setuju bahwa analisis yang lebih lengkap seharusnya menguji setiap versi mayor yang sebenarnya

• Dia mengatakan, “tentu saja peningkatan ini tidak semuanya berkat pengoptimal kueri”, dan akan menarik jika melihat apakah ada perubahan execution plan antar versi

• Mengingatkan pada Hukum Proebsting: https://proebsting.cs.arizona.edu/law.html

  • Hal baik dari optimisasi kompiler adalah kita bisa meningkatkan performa tanpa menyentuh CPU yang sudah ada secara fisik. Setiap tahun kita memeras lebih banyak performa dari mesin yang dirancang seseorang, dan akumulasinya menjadi besar
    Bayangkan dampak lingkungan jika performa Python dioptimalkan 1%. Berapa banyak CO2 di atmosfer yang berkurang? Mungkin lebih besar daripada gabungan jejak lingkungan diri sendiri, keluarga, dan teman-teman. Mungkin bahkan setara dengan seluruh kota tempat tinggal. Semua itu terjadi hanya karena seseorang meluangkan waktu untuk menerapkan beberapa trik operasi bit
  • Saya tidak paham alasannya. Hukum itu tampaknya mengatakan bahwa peningkatan performa perangkat lunak tidak terlalu berarti, padahal tulisan ini justru menunjukkan bahwa peningkatan Postgres cukup besar
    Apakah karena 15% dianggap kecil? Dalam konteks ini sama sekali tidak kecil. Memang lebih kecil dari 60% pada hukum yang ditautkan, dan jika dibagi seperti 15/10 hasilnya lebih kecil lagi, tetapi performa Postgres tidak seharusnya dibandingkan dengan peningkatan hardware. Untuk menyamai peningkatan performa 1% pada hal yang diukur di sini, dibutuhkan peningkatan hardware yang sangat besar
    Menurut saya hukum itu tidak selucu yang dikatakan sebagian orang, tetapi itu berbicara tentang waktu kompilasi bahasa pemrograman. Saya tidak akan membandingkan sesuatu yang relatif kurang penting itu dengan penyimpanan dan konsumsi data, yang bisa dibilang merupakan salah satu hal terpenting dalam ilmu komputer
  • Dalam kasus ini, peneliti membangun semua versi PostgreSQL dengan GCC 13.2 yang sama dan mengujinya pada sistem operasi yang sama
  • Kelihatannya seperti “hukum” yang cukup lemah. Apakah itu dibuat sebagai lelucon? Angkanya seperti muncul entah dari mana, setingkat “anggap saja”, dan kesimpulannya juga meleset jauh. Seolah-olah menyiratkan bahwa optimisasi yang meningkatkan performa banyak perangkat lunak di dunia sebesar 4% per tahun adalah pemborosan waktu
    Sebagai pembanding, yang disebut hanya Hukum Murphy. Saya penasaran seberapa besar perbedaan biaya antara mengembangkan hardware yang lebih cepat dan terus meningkatkan kompiler. Jika ROI dibandingkan sebagai dolar per persen peningkatan performa atau cara serupa, mungkin “hukum” ini punya bobot sampai tingkat tertentu
    Di sisi lain, tulisan Postgres ini justru tampak menunjukkan diminishing returns dalam optimisasi, yang membantah asumsi “hukum” itu bahwa keuntungan tiap tahun tetap konstan. Pada saat yang sama, itu juga bisa membuktikan sindiran Proebsting bahwa dalam jangka panjang optimisasi adalah investasi yang buruk

• Analisis ini agak membingungkan. Saya tidak mengerti bagaimana mereka memastikan adanya tren penurunan dari data yang tidak terlihat di grafik
  Median tampak sedikit turun di beberapa versi awal, lalu naik lagi di beberapa versi terbaru. R² sangat rendah, jadi korelasinya tidak terasa meyakinkan. Pada dasarnya, yang terlihat adalah tail latency membaik, sementara sisanya bergantung pada lingkungan

  • Saya penulis postingan blognya
    Tafsiran bahwa “tail latency membaik dan sisanya bergantung pada lingkungan” itu masuk akal, tetapi menurut saya itu pembacaan yang konservatif. Tentu saja, bagi banyak aplikasi, bahkan mungkin sebagian besar, tail latency sangat penting. Selain itu, tail latency juga merupakan sasaran utama para engineer pengoptimal, yaitu mengurangi waktu eksekusi kueri yang paling lama berjalan

• Seperti apa bentuk optimasi kueri? Saya penasaran apakah optimasinya dilakukan di level SQL, atau di level algoritme

  • Selain PostgreSQL, pada basis data yang pernah saya pakai, sebagian besar optimasi terjadi di level algoritme. Artinya memilih algoritme dan urutan eksekusi terbaik untuk kueri tertentu.
    Beberapa kueri SQL yang berbeda bisa diubah menjadi “perintah” atau rencana eksekusi yang sama, dan tampaknya semantik SQL sendiri tidak banyak memberi ruang untuk optimasi di level bahasa.
    Seperti yang disebut di balasan lain, salah satu keputusan penting adalah apakah full table scan bisa diganti menjadi index lookup atau index scan.
    Misalnya jika full table scan diperlukan, dan untuk setiap baris perlu perhitungan yang cukup besar untuk menentukan apakah baris itu masuk ke himpunan hasil, optimizer bisa mengubah full table scan menjadi parallel table scan lalu menggabungkan hasil dari tiap pekerjaan paralel.
    Saat menulis kode performa tinggi untuk compiler, kita perlu tahu bagaimana optimizer compiler mengubah source code menjadi machine code. Dengan begitu kita bisa lebih memilih kode yang ditangani baik oleh optimizer, dan menghindari pola yang menghasilkan machine code yang lebih lambat. Pada akhirnya optimizer diprogram untuk mendeteksi pola tertentu lalu mentransformasikannya.
    Hal yang sama berlaku untuk query optimizer dan execution plan. Kita perlu mempelajari pola seperti apa yang bisa ditangani query optimizer dari basis data yang kita gunakan agar dapat membuat execution plan yang efisien
  • Ia mendeskripsikan semua cara untuk mengeksekusi SQL lalu memilih rencana yang lebih cepat. Misalnya jika ingin mencari baris pengguna dengan user_id xx, pilihannya adalah membaca seluruh tabel lalu memfilter, atau memakai struktur data khusus.
    Dengan indeks, pencarian bisa dilakukan dalam waktu logaritmik terhadap jumlah baris. Selain itu juga bisa memilih urutan join, memilih strategi join, mendorong kondisi filter ke sisi sumber, dan banyak hal lain. Inilah ranah luas dari optimasi SQL
  • Pada level yang sangat tinggi, tujuan query planner adalah meminimalkan biaya membaca data dari disk. Ia mengumpulkan statistik kolom yang telah dihitung sebelumnya, seperti jumlah baris dan jumlah nilai unik, untuk memperkirakan berapa banyak baris yang akan cocok dengan kueri.
    Informasi ini dipakai untuk menentukan urutan join, memilih indeks, dan sebagainya. Join bisa dilakukan dengan berbagai algoritme seperti hash, loop, dan merge. Pilihan termurah akan berbeda tergantung faktor seperti apakah salah satu sisi muat di working memory, apakah kedua sisi sudah terurut, misalnya berkat index scan, dan sebagainya
  • Optimasi kueri adalah proses memilih algoritme yang memberikan hasil yang diminta SQL

• Karena situsnya tampaknya sedang tidak aktif, sebagai gantinya bisa lihat ini: https://web.archive.org/web/20240417050840/https://rmarcus.i...