Dasar Index

Topik ini membangun mental model index pada SQLite, mulai dari bentuk datanya, perilakunya terhadap pencarian kesamaan dan rentang, batas-batasnya, sampai biaya yang menyertainya. Setelah membacanya, keputusan membuat index dapat dinilai dengan mekanisme yang jelas, bukan dengan kesan cepat atau lambat. Seluruh contoh menggunakan tabel buku berisi 20000 baris yang dibangun dengan WITH RECURSIVE, sehingga perilaku query planner, yaitu komponen yang memilih rencana eksekusi, teramati pada data yang cukup besar.

Index sebagai daftar terurut#

Index adalah struktur data terurut yang berisi salinan nilai sebuah kolom beserta rowid baris pemiliknya. Rowid adalah penunjuk internal yang diberikan SQLite kepada setiap baris tabel biasa, dan pada tabel dengan kolom INTEGER PRIMARY KEY nilai tersebut sama dengan nilai kolomnya. Tabel tersimpan dalam satu B-tree, yaitu struktur pohon berhalaman yang isinya terurut menurut rowid, sedangkan setiap index memiliki B-tree sendiri yang terurut menurut nilai kolom yang diindeks. Karena kedua struktur itu terpisah, index tidak mengubah susunan baris tabel, tetapi menyediakan jalur masuk tambahan yang tertata.

Bentuk daftar terurut inilah sumber kegunaannya. Mesin pencarian tidak perlu memeriksa baris satu per satu, tetapi melompat dari halaman akar B-tree ke halaman daun yang menyimpan nilai yang dicari, dengan jumlah langkah yang tumbuh sangat lambat terhadap jumlah baris. Satuan penyimpanannya adalah halaman (page) berukuran tetap, dan setiap halaman memuat sejumlah isian index yang tertata urut. Diagram berikut membandingkan susunan baris tabel dengan salinan terurut milik indexnya.

Pencarian kesamaan dan rentang#

Pencarian kesamaan seperti WHERE tahun = 2000 menjadi cepat karena index mampu melompat langsung ke kelompok nilai yang dicari. Query planner menurunkan pencarian dari akar B-tree index sampai halaman daun yang memuat 2000, lalu mengambil rowid yang menunjuk baris terkait. Rencana eksekusinya dapat dilihat dengan EXPLAIN QUERY PLAN, yaitu pernyataan SQL yang menampilkan pilihan planner tanpa menjalankan query-nya.

CREATE TABLE buku (
  id      INTEGER PRIMARY KEY,
  judul   TEXT NOT NULL,
  penulis TEXT NOT NULL,
  tahun   INTEGER NOT NULL
);
INSERT INTO buku (judul, penulis, tahun)
WITH RECURSIVE deret(i) AS (
  SELECT 1
  UNION ALL
  SELECT i + 1 FROM deret WHERE i < 20000
)
SELECT 'Buku ' || i, 'Penulis ' || (1 + (i % 200)), 1950 + (i % 75) FROM deret;
CREATE INDEX idx_buku_tahun ON buku(tahun);
EXPLAIN QUERY PLAN SELECT judul FROM buku WHERE tahun = 2000;

QUERY PLAN
`--SEARCH buku USING INDEX idx_buku_tahun (tahun=?)

Baris SEARCH berarti planner menggunakan index idx_buku_tahun untuk melompat ke baris yang cocok, sedangkan tanda (tahun=?) menyatakan syarat yang dilayani index. Pencarian rentang dilayani dengan cara yang serupa. Index dicari pada batas awal rentang, kemudian isian dibaca berurutan dari kiri ke kanan sampai batas akhir tercapai, karena seluruh nilai sudah berdampingan menurut urutan index. Pola yang sama membuat ORDER BY yang searah dengan index dapat dilayani tanpa pengurutan tambahan, karena hasil pembacaan index sudah terurut.

CREATE TABLE buku (
  id      INTEGER PRIMARY KEY,
  judul   TEXT NOT NULL,
  penulis TEXT NOT NULL,
  tahun   INTEGER NOT NULL
);
INSERT INTO buku (judul, penulis, tahun)
WITH RECURSIVE deret(i) AS (
  SELECT 1
  UNION ALL
  SELECT i + 1 FROM deret WHERE i < 20000
)
SELECT 'Buku ' || i, 'Penulis ' || (1 + (i % 200)), 1950 + (i % 75) FROM deret;

SELECT count(*) FROM buku WHERE tahun BETWEEN 2000 AND 2009;

2661

Ketika batas rentang mencakup sebagian besar baris, keunggulan urutan itu menyusut, dan keputusan planner bergantung pada estimasi jumlah baris yang cocok. Oleh karena itu, index memberi manfaat paling jelas pada syarat yang menyaring sebagian kecil baris. Kriteria inilah yang membedakan index yang dipakai sungguhan dari index yang hanya menumpuk.

Yang tidak dilayani index#

Index tidak memberi keuntungan pada setiap bentuk syarat. Syarat yang menerapkan fungsi pada kolom, misalnya upper(judul) = ‘BUKU 7’, tidak dapat dilayani oleh index yang dibuat atas kolom judul, karena isian index menyimpan judul apa adanya dan bukan hasil fungsinya. Planner tidak dapat menemukan baris tersebut melalui urutan index, sehingga seluruh tabel harus diperiksa dari awal sampai akhir.

Hal yang setara terjadi pada LIKE dengan awal wildcard. Pola LIKE ‘%7’ tidak menyatakan posisi awal, sehingga tidak ada titik masuk pada urutan index yang dapat digunakan dan pemindaian penuh (full scan) tidak terhindarkan. Kedua bentuk berikut diperiksa pada tabel yang sama dan sama-sama menghasilkan rencana SCAN.

CREATE TABLE buku (
  id      INTEGER PRIMARY KEY,
  judul   TEXT NOT NULL,
  penulis TEXT NOT NULL,
  tahun   INTEGER NOT NULL
);
INSERT INTO buku (judul, penulis, tahun)
WITH RECURSIVE deret(i) AS (
  SELECT 1
  UNION ALL
  SELECT i + 1 FROM deret WHERE i < 20000
)
SELECT 'Buku ' || i, 'Penulis ' || (1 + (i % 200)), 1950 + (i % 75) FROM deret;

EXPLAIN QUERY PLAN SELECT judul FROM buku WHERE upper(judul) = 'BUKU 7';
EXPLAIN QUERY PLAN SELECT judul FROM buku WHERE judul LIKE '%7';

QUERY PLAN
`--SCAN buku
QUERY PLAN
`--SCAN buku

Rencana SCAN, yaitu pemindaian seluruh baris tabel dari awal sampai akhir, adalah rencana yang menjadi tolok ukur. Index yang tidak pernah menghilangkan SCAN pada query yang sering dijalankan tidak memberi manfaat apa pun, meskipun sudah dibuat. Padahal SQLite menyediakan index ekspresi, yaitu index yang dibuat atas ekspresi seperti upper(judul), sebagai jalan keluar untuk syarat semacam ini.

Biaya index: ruang dan tulis#

Setiap index dibayar dengan ruang dan beban tulis. Ukuran ruangnya dapat diamati melalui PRAGMA page_count, yaitu jumlah halaman yang dipakai berkas basis data. Blok berikut membangun tabel 20000 baris, mencatat jumlah halamannya, membuat satu index, lalu mencatatnya lagi.

CREATE TABLE buku (
  id      INTEGER PRIMARY KEY,
  judul   TEXT NOT NULL,
  penulis TEXT NOT NULL,
  tahun   INTEGER NOT NULL
);
INSERT INTO buku (judul, penulis, tahun)
WITH RECURSIVE deret(i) AS (
  SELECT 1
  UNION ALL
  SELECT i + 1 FROM deret WHERE i < 20000
)
SELECT 'Buku ' || i, 'Penulis ' || (1 + (i % 200)), 1950 + (i % 75) FROM deret;
PRAGMA page_count;
CREATE INDEX idx_buku_tahun ON buku(tahun);
PRAGMA page_count;

160
210

Satu index menambah 50 halaman, atau hampir sepertiga ukuran tabelnya. Beban tulisnya bekerja dengan cara yang sama pada setiap perubahan data. Setiap INSERT dan DELETE harus memperbarui B-tree setiap index yang ada, dan UPDATE yang menyentuh kolom terindeks memperbarui index yang memuat kolom itu. Semakin banyak index pada sebuah tabel, semakin banyak pekerjaan tulis yang menyertai setiap pernyataan penulisan.

Konsekuensinya, index dibuat untuk memenuhi kebutuhan query yang nyata, bukan untuk setiap kolom yang terlihat. Kolom yang hanya dibaca untuk menampilkan isi baris tidak memerlukan index, sedangkan kolom yang sering menjadi syarat WHERE, kunci join, atau dasar pengurutan adalah kandidat yang tepat. Pertimbangan biaya dan manfaat inilah yang memisahkan pengindeksan yang sehat dari pengindeksan berlebihan.

Ringkasan#

• Index adalah B-tree terurut yang berisi nilai kolom beserta rowid barisnya, terpisah dari B-tree tabel, sehingga baris tabel tidak perlu diurutkan ulang.
• Kesamaan dilayani dengan melompat ke satu posisi daun, dan rentang dilayani dengan berjalan berurutan dari batas awal sampai batas akhir.
• Fungsi pada kolom dan LIKE dengan awal wildcard tidak dilayani index kolom biasa dan tetap menghasilkan SCAN.
• Setiap index menambah ruang halaman basis data dan memperberat setiap INSERT, UPDATE, dan DELETE yang menyentuh kolomnya.

Referensi#

• Overview Of The Query Planner — SQLite — Dokumentasi resmi cara query planner memilih rencana eksekusi dan peran index di dalamnya.
• CREATE INDEX — SQLite — Sintaks pembuatan index beserta perilaku pencarian pada index.
• PRAGMA Statements — SQLite — Daftar pragma, termasuk page_count yang dipakai untuk mengamati ukuran basis data.