Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Cara kerja database index dan alasan B-tree mendominasi: hitungan fanout page, output EXPLAIN Postgres asli, urutan kolom composite index, dan biaya write setiap index.
Matthews Wong
Software Engineer
Ringkasan Utama
Database index adalah struktur terurut terpisah, biasanya B-tree, yang menemukan baris lewat key dengan beberapa kali baca page, bukan memindai seluruh tabel. B-tree mendominasi karena page lebar membuat tree tetap dangkal, leaf terurut melayani range dan ORDER BY, dan setiap index tambahan menambah biaya write.
Kebanyakan layar daftar yang lambat di sistem ERP atau POS bermuara pada satu pertanyaan: apakah database membaca seluruh tabel hanya untuk menemukan dua puluh baris? Halaman yang memfilter order berdasarkan customer dan status, terbaru dulu, cepat dengan seribu baris dan menyakitkan dengan sejuta baris, dan solusinya biasanya satu index.
Artikel ini menjelaskan apa itu index tersebut, kenapa hampir semua database relasional membangunnya sebagai B-tree, dan di mana ia berhenti membantu. Angkanya berasal dari dua tempat: dokumentasi PostgreSQL, dan tabel 1.000.000 baris sekali pakai yang saya buat di PostgreSQL 16.15 untuk artikel ini. Setiap angka dikutip dari sumber, dihitung dengan aritmetika yang ditampilkan, atau dibaca dari satu run lokal itu. Ini bukan benchmark production.
Index adalah salinan kedua dari beberapa kolom, disimpan terurut, dengan pointer kembali ke baris. Tanpa index, mencari satu customer berarti membaca setiap page tabel. Dengan index, database menyusuri jalur pendek di salinan terurut itu lalu mengambil satu baris yang cocok. Tabel uji di bawah berukuran 8.334 page, dan lookup primary key yang sama hanya menyentuh 7 buffer.
-- The test table: 1,000,000 rows, PostgreSQL 16.15 on a laptop.
CREATE TABLE orders (
id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
customer_id int NOT NULL, -- 10,000 distinct customers
status text NOT NULL, -- paid / pending / void
created_at timestamptz NOT NULL,
total numeric(12,2) NOT NULL
);
-- Same lookup, before and after the primary key is used:
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM orders WHERE id = 777777;
-- Index Scan using orders_pkey on orders (actual rows=1 loops=1)
-- Index Cond: (id = 777777)
-- Buffers: shared hit=7
-- Table is 8,334 pages (a parallel seq scan reported hit=8334 in total).
-- Reading all of them to find one row: 8,334 / 7 = about 1,190 times more pages.Index tidak gratis untuk dipelihara. Ia memakan disk, harus diperbarui oleh setiap write, dan planner tetap akan mengabaikannya ketika query mengembalikan porsi besar dari tabel. Semua bagian setelah ini membahas trade-off itu: seperti apa strukturnya, cara memastikan index dipakai, dan berapa biayanya.
Postgres menyimpan setiap tabel dan index sebagai array page berukuran tetap, biasanya 8 kB. B-tree index adalah tree dari page-page itu: leaf page menyimpan key terurut dengan pointer ke baris tabel, dan internal page menyimpan key yang mengarahkan pencarian ke child yang tepat. Rancangan aslinya dari Bayer dan McCreight tahun 1972, dan abstraknya menyebut lookup, insert, dan delete berbiaya sebanding log basis k dari ukuran index, dengan utilisasi penyimpanan minimal 50 persen.
-- Fanout, worked by hand for a bigint primary key (assumptions marked).
page size = 8192 bytes (Postgres default)
bytes per index entry = 8 key + 8 tuple header + 4 item pointer
= 20 bytes (assumption)
default leaf fillfactor = 90% (CREATE INDEX docs)
entries per leaf page = 8192 * 0.90 / 20 = about 368
leaf pages for 1,000,000 = 1,000,000 / 368 = about 2,717
size on disk = 2,717 * 8 KB = about 21.2 MB
measured orders_pkey = 21 MB (pg_relation_size)
internal level = 2,717 pages / ~400 children each = about 7 pages
root = 1 page pointing at those 7
-- bt_metap('orders_pkey') reported level = 2:
-- root -> internal -> leaf, three pages on every lookup path.
-- Growth: each extra level multiplies capacity by the fanout.
-- level 1 (root + leaves): ~400 * 368 = about 147,000 rows
-- level 2 (root, internal, leaves): ~400^2 * 368 = about 59 million rows
-- level 3 (one more internal layer): ~400^3 * 368 = about 23 billion rowsAkibatnya, tinggi tree nyaris tidak bergerak saat tabel tumbuh berorde-orde besar. Untuk key bigint saya mengasumsikan 20 byte per entry, yang merupakan estimasi dan bukan angka kutipan, dan hasilnya memprediksi primary key terukur 21 MB dengan selisih sekitar setengah megabyte. Level ketiga menampung sekitar 59 juta baris. Inilah sebabnya menambah index pada tabel sepuluh juta baris tidak membuat lookup sepuluh kali lebih lambat dibanding sejuta baris.
Tiga sifat struktur ini selaras dengan apa yang benar-benar diminta aplikasi dari database. Binary tree untuk 1.000.000 key sedalam sekitar 20 level, karena log basis 2 dari 1.000.000 kira-kira 19,9, dan tiap level bisa berupa pembacaan page terpisah. B-tree memuat ratusan key dalam satu page, jadi data yang sama cukup tiga page.
| Sifat B-tree | Konsekuensi | Query yang terlayani |
|---|---|---|
| Ratusan entry per page 8 kB | Kedalaman tiga page untuk 1.000.000 baris | Point lookup: WHERE id = 777777 |
| Key tetap terurut di sepanjang level leaf | Scan berjalan ke entry tetangga, tanpa pencarian ulang | Range, BETWEEN, ORDER BY dengan LIMIT |
| Seimbang: semua leaf di kedalaman sama | Biaya lookup tetap terprediksi saat data tumbuh | Tabel yang hanya bertambah, seperti order dan ledger |
| Page penuh di-split, tree tidak ditulis ulang | Insert tetap lokal, tetapi menambah write | Traffic write stabil, dengan harga yang ditunjukkan nanti |
Leaf yang terurut adalah bagian yang sering diremehkan. Index yang hanya bisa menjawab equality tidak bisa mengembalikan dua puluh order terbaru tanpa membaca dan mengurutkannya. B-tree bisa berjalan ke ujung range key yang tepat lalu membaca mundur, yaitu plan yang ditampilkan di bagian berikutnya. Saya tidak membahas index hash, GIN, atau BRIN di sini; mereka ada untuk bentuk query lain, dan artikel ini hanya mengklaim apa yang dilakukan B-tree.
Jalankan EXPLAIN dengan ANALYZE dan BUFFERS, lalu bandingkan jumlah page yang disentuh, bukan milidetiknya, karena jumlah page stabil antar run sedangkan timing tidak. Tiga plan di bawah adalah query yang sama terhadap 1.000.000 baris yang sama. Hanya index-nya yang berubah.
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM orders
WHERE customer_id = 4242 AND status = 'paid'
ORDER BY created_at DESC LIMIT 20;
-- 1) No index on customer_id yet:
-- Parallel Seq Scan on orders
-- Filter: ((customer_id = 4242) AND (status = 'paid'))
-- Rows Removed by Filter: 333316 (per worker)
-- Buffers: shared hit=8334
-- + Sort (top of the plan) total hit=8448
-- 2) CREATE INDEX orders_customer_idx ON orders (customer_id);
-- Sort Method: top-N heapsort
-- -> Bitmap Heap Scan on orders (Heap Blocks: exact=129)
-- Filter: (status = 'paid') Rows Removed by Filter: 77
-- -> Bitmap Index Scan on orders_customer_idx
-- total Buffers: shared hit=129 read=3 (132 pages)
-- 3) CREATE INDEX ... ON orders (customer_id, status, created_at);
-- Limit
-- -> Index Scan Backward using orders_cust_status_created_idx
-- Index Cond: ((customer_id = 4242) AND (status = 'paid'))
-- total Buffers: shared hit=20 read=3 (23 pages, no Sort node)Turun dari 8.448 page ke 132 cukup dengan satu single-column index. Turun ke 23 page dan menghilangkan node Sort membutuhkan composite index di bagian berikutnya. Timing di laptop hanya noise di sini, jadi saya hanya mengutip jumlah buffer.
| Yang tampak di plan | Artinya | Yang dicoba |
|---|---|---|
| Seq Scan dengan Rows Removed by Filter besar | Tidak ada index yang cocok dengan filter, jadi setiap page dibaca | Index kolom yang difilter, jika query mengembalikan sedikit baris |
| Bitmap Heap Scan, lalu node Sort | Index menemukan baris tetapi tidak bisa mengirimkannya berurutan | Perluas index agar kolom sort berada paling akhir |
| Index Scan atau Index Scan Backward, tanpa Sort | Index mengirim baris yang sudah berurutan sesuai permintaan | Tidak ada. Ini bentuk target |
Seq Scan tidak selalu bug. Ketika query mengembalikan porsi besar dari tabel, membacanya berurutan lebih murah daripada melompat lewat index. Pada run saya, status = 'paid' cocok dengan sepertiga baris dan plan-nya sequential scan, dan itu benar.
Ya, dan inilah kesalahan yang paling banyak menyia-nyiakan index. Dokumentasi PostgreSQL menyatakan aturannya: constraint equality pada kolom depan, ditambah inequality pada kolom pertama yang tidak punya equality, membatasi bagian index yang dipindai. Kondisi pada kolom di sebelah kanan hanya diperiksa di dalam index. Jadi taruh kolom yang dibandingkan dengan sama dengan di depan, dan kolom range atau sort di paling akhir.
-- Right: equality columns first, the sort/range column last.
CREATE INDEX orders_cust_status_created_idx
ON orders (customer_id, status, created_at);
-- Served by it: WHERE customer_id = ?
-- WHERE customer_id = ? AND status = ?
-- WHERE customer_id = ? AND status = ? ORDER BY created_at DESC
-- Not narrowed by it: WHERE status = ? AND created_at < ? (no customer_id)
-- Measured on PostgreSQL 16.15, 1M rows, for that last query:
-- Parallel Seq Scan on orders, Buffers: shared hit=8334
-- The index was ignored. Docs for current Postgres (18) describe a skip scan
-- that can help when the leading column has very few distinct values;
-- customer_id has 10,000, so do not count on it.
-- Size: single-column index 6,960 kB vs three-column index 39 MB,
-- about 5.7 times larger (39 MB = 39,936 kB; 39,936 / 6,960 = 5.7) for the same table.Index juga punya biaya yang sebanding dengan lebarnya. Index tiga kolom berukuran sekitar 5,7 kali lebih besar daripada index satu kolom, karena setiap entry kini membawa tiga key. Jangan melebarkan index untuk menutup semua query. Lebarkan untuk beberapa query yang paling sering dipakai, dan biarkan sisanya dilayani index lebih sempit yang sudah ada.
Untuk layar daftar yang difilter satu owner dan satu status lalu diurutkan terbaru, polanya adalah (owner_id, status, created_at). Saya memakainya sebagai hipotesis awal untuk tabel ERP berbasis tenant, lalu memastikannya dengan EXPLAIN pada salinan data asli sebelum mempertahankannya.
Setiap INSERT harus menambahkan entry ke setiap index pada tabel, dan setiap entry itu juga ditulis ke write-ahead log. Saya mengukurnya dengan memasukkan 100.000 baris ke empat tabel yang identik selain index-nya, lalu membaca posisi WAL sebelum dan sesudah. Tabel menunjukkan byte WAL yang dihasilkan.
| Setup tabel (100.000 baris di-insert) | Byte WAL tertulis | Dibanding tanpa index |
|---|---|---|
| Tanpa index | 9,628,240 | 1.00x |
| 1 index (customer_id) | 16,863,912 | 1.75x |
| 3 index | 31,044,280 | 3.22x |
| 4 index | 37,675,888 | 3.91x |
-- How the numbers were taken (one session per table, after CHECKPOINT):
SELECT pg_current_wal_lsn() AS before \gset
INSERT INTO w3
SELECT g, (random()*9999)::int + 1, 'paid', now() + g * interval '1 second', 1
FROM generate_series(1, 100000) g;
SELECT pg_wal_lsn_diff(pg_current_wal_lsn(), :'before') AS wal_bytes;
-- Ratios are plain division: 16,863,912 / 9,628,240 = 1.75
-- 31,044,280 / 9,628,240 = 3.22
-- 37,675,888 / 9,628,240 = 3.91
-- Updates: an UPDATE that touches no indexed column can be a HOT update
-- (needs free space on the same page) and adds no index entries.
SELECT n_tup_upd, n_tup_hot_upd FROM pg_stat_user_tables WHERE relname = 'orders';Ini satu run lokal, jadi anggap rasionya sebagai bentuk biayanya, bukan konstanta. Update punya aturan kedua. Menurut dokumentasi PostgreSQL, update heap-only tuple menghindari entry index baru ketika update tidak mengubah kolom ber-index dan masih ada ruang kosong di page yang sama. Meng-index kolom yang sering berubah, seperti status atau timestamp terakhir dilihat, menghilangkan jalan pintas itu untuk setiap update.
Jangan meng-index kolom hanya karena ia muncul di suatu klausa WHERE. Setiap index yang Anda pertahankan dibayar pada setiap insert, dan pada setiap update yang mengubah kolomnya, entah ada query yang memakainya atau tidak.
Jalankan lima pengecekan ini berurutan. Kebanyakan index yang gagal di langkah satu atau dua sebaiknya tidak dibuat sama sekali.
Pada satu VPS yang menjalankan Postgres bersama aplikasi, disiplin ini lebih penting daripada di cluster besar, karena disk dan WAL yang sama menanggung read yang Anda percepat sekaligus write yang Anda perlambat.
Index adalah salinan terurut yang menukar biaya write dengan kecepatan read, dan B-tree menang karena page-nya yang lebar menjaga salinan itu tetap sedalam tiga page untuk sejuta baris. Taruh kolom equality di depan dan kolom sort di belakang, buktikan hasilnya dengan jumlah buffer di EXPLAIN, dan perlakukan setiap index sebagai biaya tetap pada setiap insert.