KAL
Menu

Indeks Komposit

Aturan prefiks kiri, urutan kolom, dan keputusan desain indeks multi-kolom.

Daftar isi

Satu indeks tunggal menjawab satu pola pencarian, sedangkan query nyata sering menyaring dua kolom sekaligus. Topik ini membahas indeks komposit (composite index), yaitu indeks yang kuncinya tersusun atas beberapa kolom, aturan prefiks kiri yang menentukan kapan indeks itu dapat dipakai, dan pertimbangan urutan kolom pada saat perancangan. Latihan memakai tabel peminjaman berisi 100000 baris pada basis data perpustakaan_komposit, dan setiap klaim dibuktikan dengan keluaran EXPLAIN dari server MySQL 8.0. Setelah topik ini, keputusan membuat indeks multi-kolom dapat diambil berdasarkan pola akses, bukan berdasarkan kebiasaan.

Data latihan#

Berkas berikut membuat ulang basis data perpustakaan_komposit dari nol. Tabel peminjaman berisi 100000 baris yang terbagi rata, yaitu setiap 40 baris berturut-turut milik satu anggota sehingga terdapat 2500 anggota, sedangkan buku_id tersebar merata di antara 500 buku. Indeks komposit idx_anggota_buku dengan kunci (anggota_id, buku_id) dibuat setelah seluruh data dimuat, lalu ANALYZE TABLE memperbarui statistiknya.

sql skema-komposit.sql 
-- tidak-dijalankan
-- Skema basis data latihan "perpustakaan_komposit" untuk topik indeks komposit.
-- Menjalankan ulang berkas ini selalu menghasilkan isi yang sama.

DROP DATABASE IF EXISTS perpustakaan_komposit;
CREATE DATABASE perpustakaan_komposit;
USE perpustakaan_komposit;

SET SESSION cte_max_recursion_depth = 1000000;

CREATE TABLE peminjaman (
  peminjaman_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  anggota_id INT UNSIGNED NOT NULL,
  buku_id INT UNSIGNED NOT NULL,
  tanggal_pinjam DATE NOT NULL,
  status VARCHAR(10) NOT NULL
) STATS_SAMPLE_PAGES=1024;

INSERT INTO peminjaman (anggota_id, buku_id, tanggal_pinjam, status)
WITH RECURSIVE urut AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM urut WHERE n < 100000
)
SELECT
  ((n - 1) DIV 40) + 1,
  (n MOD 500) + 1,
  DATE_ADD('2024-01-01', INTERVAL (n MOD 730) DAY),
  ELT((n MOD 3) + 1, 'dipinjam', 'kembali', 'terlambat')
FROM urut;

CREATE INDEX idx_anggota_buku ON peminjaman (anggota_id, buku_id);

ANALYZE TABLE peminjaman;
bash 
# membuat ulang basis data latihan beserta statistiknya
mysql -t -u root < skema-komposit.sql
text Keluaran 
+----------------------------------+---------+----------+----------+
| Table                            | Op      | Msg_type | Msg_text |
+----------------------------------+---------+----------+----------+
| perpustakaan_komposit.peminjaman | analyze | status   | OK       |
+----------------------------------+---------+----------+----------+

Baris status OK menandakan statistik indeks sudah diperbarui, dan statistik inilah bahan keputusan optimizer. Opsi STATS_SAMPLE_PAGES pada definisi tabel memperbesar jumlah halaman yang disampel saat statistik dihitung, sehingga angka perkiraan pada keluaran EXPLAIN stabil dari eksekusi ke eksekusi.

Urutan entri pada indeks komposit#

Entri indeks komposit diurutkan menurut kolom pertama, kemudian menurut kolom kedua untuk nilai kolom pertama yang sama, dan primary key menutup urutan sebagai pemecah seri. Pada idx_anggota_buku, seluruh entri milik satu anggota tersusun rapat dalam satu kelompok dan di dalam kelompok itu buku_id meningkat teratur. Query berikut membaca rentang buku milik anggota 42 untuk memastikan pola tersebut pada data nyata.

bash 
# rentang buku yang dipinjam oleh anggota 42
mysql -u root perpustakaan_komposit -t -e "SELECT MIN(buku_id) AS buku_pertama, MAX(buku_id) AS buku_terakhir, COUNT(*) AS jumlah FROM peminjaman WHERE anggota_id = 42;"
text Keluaran 
+--------------+---------------+--------+
| buku_pertama | buku_terakhir | jumlah |
+--------------+---------------+--------+
|          142 |           181 |     40 |
+--------------+---------------+--------+

Keluaran menunjukkan 40 nilai buku_id berbeda, yaitu 142 sampai 181, yang tersusun rapat di dalam kelompok anggota 42. Diagram berikut memperlihatkan susunan kelompok tersebut beserta akibatnya bagi tiga pola WHERE yang berbeda.

Entri idx_anggota_buku (anggota_id, buku_id)anggota_id 42(42, 142) (42, 150) (42, 181)anggota_id 43(43, 182) (43, 183) (43, 184)Buku diurutkan di dalam setiap anggota.Pola WHERE dan akibatnyaanggota_id = 42: loncat ke kelompoknyaanggota_id = 42 DAN buku_id = 150: loncat tepatbuku_id = 150: urutan prefiks kiri terlanggarTanpa prefiks kiri, seluruh urutan dipindaidari awal sampai akhir (type ALL).
Urutan entri indeks komposit dan akibat aturan prefiks kiri

Urutan bertingkat ini menjadi dasar satu aturan penting. Pencarian dapat meloncat ke posisi yang tepat hanya apabila dimulai dari kolom terkiri, karena hanya kolom itulah yang terurut secara global di dalam indeks.

Aturan prefiks kiri#

Aturan prefiks kiri (leftmost prefix) menyatakan bahwa indeks (anggota_id, buku_id) hanya dapat dipakai apabila query mencari dengan kolom paling kiri, yaitu anggota_id, baik sendiri maupun diikuti kolom-kolom berikutnya. Apabila query hanya menyaring buku_id, urutan entri indeks tidak dapat dimanfaatkan karena buku_id hanya terurut di dalam kelompok anggota_id. Dua keluaran EXPLAIN berikut membandingkan kedua keadaan tersebut. Pada keluaran EXPLAIN, kolom key menunjukkan indeks yang dipilih dan kolom rows menunjukkan perkiraan jumlah baris yang diperiksa, dan keduanya dibahas lebih rinci pada topik tersendiri.

bash 
# prefiks kiri saja: indeks komposit tetap dipakai
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE anggota_id = 42 \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: ref
possible_keys: idx_anggota_buku
          key: idx_anggota_buku
      key_len: 4
          ref: const
         rows: 40
     filtered: 100.00
        Extra: NULL
bash 
# kolom kedua saja: urutan indeks tidak dapat dimanfaatkan
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE buku_id = 150 \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 100000
     filtered: 10.00
        Extra: Using where

Query pertama mendapat key: idx_anggota_buku dengan rows: 40, yaitu seluruh kelompok anggota 42. Query kedua mendapat key: NULL dan type: ALL, yang berarti seluruh 100000 baris dipindai. Nilai key_len juga bermakna, yaitu 4 byte untuk satu kolom INT UNSIGNED yang ikut mencari, dan angka ini kembali muncul pada bagian berikutnya.

Dua kolom sekaligus dan urutan penulisan#

Apabila kedua kolom dicari sekaligus, indeks dimanfaatkan sampai kolom terakhirnya, dan titik potongnya, yaitu rentang entri indeks yang lolos saringan, menjadi paling ketat. Keluaran berikut menunjukkan key_len naik menjadi 8, yang berarti kedua kolom kunci ikut mencari, serta ref: const,const yang berarti kedua kolom dibandingkan dengan konstanta.

bash 
# kedua kolom dicari sekaligus
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE anggota_id = 42 AND buku_id = 150 \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: ref
possible_keys: idx_anggota_buku
          key: idx_anggota_buku
      key_len: 8
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: NULL

Perhatikan juga urutan penulisan predikat pada WHERE. Query berikut menuliskan buku_id lebih dahulu, tetapi rencananya tetap identik dengan keluaran sebelumnya.

bash 
# urutan penulisan WHERE dibalik
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE buku_id = 150 AND anggota_id = 42 \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: ref
possible_keys: idx_anggota_buku
          key: idx_anggota_buku
      key_len: 8
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: NULL

Kedua keluaran sama persis karena optimizer menata ulang predikat kesetaraan sebelum memilih indeks. Urutan yang menentukan adalah urutan definisi indeks, bukan urutan penulisan kolom pada WHERE.

Keputusan desain indeks multi-kolom#

Urutan kolom pada definisi indeks sebaiknya mengikuti pola aksesnya. Kolom yang selalu dicari dengan kesetaraan diletakkan lebih dulu, sedangkan kolom yang dicari dengan jangkauan diletakkan belakangan. Apabila jangkauan diletakkan pada kolom pertama, sisa entri tidak lagi terurut penuh menurut kolom kedua, sehingga penyaringannya menjadi pekerjaan tambahan per baris. MySQL 8 masih dapat menyusun beberapa jangkauan kecil sekaligus, tetapi semakin banyak nilai di dalam jangkauan semakin mahal pencariannya.

Pada indeks latihan ini, anggota selalu dicari dengan kesetaraan dan buku kadang-kadang dengan jangkauan, sehingga urutan (anggota_id, buku_id) sudah tepat. Keluaran berikut menunjukkan jangkauan pada kolom kedua tetap dimanfaatkan penuh, dengan type: range, key_len: 8, dan perkiraan 31 baris.

bash 
# jangkauan pada kolom kedua
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE anggota_id = 42 AND buku_id > 150 \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: range
possible_keys: idx_anggota_buku
          key: idx_anggota_buku
      key_len: 8
          ref: NULL
         rows: 31
     filtered: 100.00
        Extra: Using index condition
bash 
# jumlah baris nyata untuk jangkauan yang sama
mysql -u root perpustakaan_komposit -t -e "SELECT COUNT(*) AS jumlah FROM peminjaman WHERE anggota_id = 42 AND buku_id > 150;"
text Keluaran 
+--------+
| jumlah |
+--------+
|     31 |
+--------+

Perkiraan 31 cocok dengan hitungan nyata karena jangkauan ini ditakar langsung di dalam indeks. Indeks komposit juga menyuplai urutan. Query berikut menambahkan ORDER BY buku_id pada pencarian prefiks kiri.

bash 
# urutan buku tanpa pengurutan tambahan
mysql -u root perpustakaan_komposit -e "EXPLAIN SELECT status FROM peminjaman WHERE anggota_id = 42 ORDER BY buku_id \G"
text Keluaran 
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: peminjaman
   partitions: NULL
         type: ref
possible_keys: idx_anggota_buku
          key: idx_anggota_buku
      key_len: 4
          ref: const
         rows: 40
     filtered: 100.00
        Extra: NULL

Keluaran menunjukkan Extra: NULL, yang berarti tidak ada pengurutan tambahan, karena entri kelompok anggota 42 memang sudah terurut menurut buku_id. Sebaliknya, permintaan urutan menurut kolom lain, misalnya tanggal_pinjam, akan muncul sebagai Using filesort pada Extra karena urutannya tidak tersedia di indeks mana pun.

Kesalahan umum#

Kesalahan pertama adalah membuat satu indeks tunggal untuk setiap kolom alih-alih satu indeks komposit. Untuk satu langkah pembacaan tabel, MySQL biasanya memilih satu indeks saja, sehingga query dengan dua syarat tetap menyaring baris demi baris setelah indeks pertama dipakai. Perbaikannya adalah menyusun satu indeks komposit sesuai pola akses. Kesalahan kedua adalah meletakkan kolom jangkauan sebelum kolom kesetaraan, misalnya (tanggal_pinjam, anggota_id) untuk query yang selalu menyaring anggota secara pasti. Titik potongnya menjadi longgar karena rentang tanggal membawa banyak anggota sekaligus. Perbaikannya adalah menukar urutan kolom pada definisi indeks. Kesalahan ketiga adalah mengira urutan penulisan kolom pada WHERE memengaruhi rencana eksekusi. Optimizer menata ulang predikat kesetaraan dengan sendirinya, sehingga energi perbaikan sebaiknya diarahkan pada urutan definisi indeks, bukan pada urutan menulis query.

Ringkasan#

  • Entri indeks komposit terurut menurut kolom pertama, lalu kolom kedua di dalamnya, sehingga satu indeks melayani pencarian prefiks dan pencarian lengkap.
  • Aturan prefiks kiri: query tanpa kolom terkiri tidak dapat memanfaatkan urutan indeks dan berakhir pada pemindaian tabel dengan key: NULL.
  • key_len dan rows pada EXPLAIN memperlihatkan berapa banyak kolom yang ikut mencari dan berapa baris yang diperiksa, misalnya 4 byte untuk satu kolom dan 8 byte untuk dua kolom.
  • Urutan kolom mengikuti pola akses, yaitu kesetaraan dulu dan jangkauan belakangan, sedangkan urutan penulisan WHERE tidak berpengaruh.

Referensi#