Fundamental indeks

Memahami struktur B-tree indeks, trade-off baca dan tulis, serta kapan indeks diperlukan.

Daftar isi

Indeks menyimpan nilai dari satu atau beberapa field dalam struktur terurut yang terpisah dari dokumen, sehingga server menemukan dokumen tanpa membaca seluruh koleksi. Topik ini membahas struktur B-tree yang mendasari indeks MongoDB, perbandingan pemindaian koleksi dengan pemindaian indeks, serta trade-off antara kecepatan pembacaan dan biaya penulisan. Demonstrasi memakai basis data kamus dengan koleksi entri berisi lima ratus dokumen kata. Setelah mengikuti topik ini, indeks dapat dibuat, diverifikasi, dan dihapus dengan pertimbangan yang jelas.

Koleksi tanpa indeks#

Tanpa indeks yang cocok, server MongoDB menjalankan pemindaian koleksi (collection scan), yaitu pemeriksaan setiap dokumen satu per satu untuk menguji syarat query. Tahap COLLSCAN pada rencana eksekusi menandai perilaku ini. Biaya pemindaian koleksi tumbuh linear terhadap jumlah dokumen, sehingga query yang sama pada koleksi berisi jutaan dokumen memeriksa jutaan dokumen pula. Pemindaian indeks (index scan) menyelesaikan pencarian yang sama dengan membaca sebagian kecil kunci yang terurut.

Tanamlah data contoh berikut pada basis data kamus. Perulangan menghasilkan lima ratus dokumen entri kamus, dengan setiap kata muncul pada lima dokumen homonim yang berbeda.

mongosh

use kamus
const sukuAwal = ["ba", "ta", "ka", "me", "pa", "sa", "ni", "go", "lu", "wi"]
const sukuAkhir = ["tah", "rin", "sup", "kan", "del", "mus", "pel", "rong", "wis", "dak"]
const daftarKategori = ["nomina", "verba", "adjektiva"]
const docs = []
const tambah = function (i, j, k) {
  docs.push({
    kata: sukuAwal[i] + sukuAkhir[j],
    homonim: k + 1,
    kategori: daftarKategori[(i + j + k) % 3],
    frekuensi: ((i * 53 + j * 29 + k * 7) % 900) + 100,
    tahun: 2015 + ((i + j * 2 + k) % 10)
  })
}
for (let i = 0; i < 10; i++) {
  for (let j = 0; j < 10; j++) {
    for (let k = 0; k < 5; k++) {
      tambah(i, j, k)
    }
  }
}
const hasil = db.entri.insertMany(docs)
print("Dokumen tersimpan: " + db.entri.countDocuments())

text Keluaran

switched to db kamus

Dokumen tersimpan: 500

Bila koleksi entri pernah dipakai pada latihan lain, bersihkan indeks lamanya agar demonstrasi dimulai dari kondisi yang hanya memuat indeks bawaan _id_.

mongosh

const bersih = db.entri.dropIndexes()
print("Indeks non-_id dibersihkan: " + (bersih.ok === 1))

text Keluaran

Indeks non-_id dibersihkan: true

Query berikut mencari seluruh entri dengan kata batah, kemudian rencana eksekusinya dibaca melalui explain("queryPlanner") tanpa mengembalikan dokumen apa pun.

mongosh

db.entri.find({ kata: "batah" }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

{
  isCached: false,
  stage: 'COLLSCAN',
  filter: { kata: { '$eq': 'batah' } },
  direction: 'forward'
}

Field stage bernilai COLLSCAN, yang berarti server membaca seluruh koleksi untuk query ini. Jumlah dokumen yang benar-benar diperiksa terbaca pada mode executionStats melalui tiga field yang nilainya stabil antareksekusi, yaitu nReturned, totalKeysExamined, dan totalDocsExamined.

mongosh

const statistik = db.entri.find({ kata: "batah" }).explain("executionStats").executionStats
print("nReturned: " + statistik.nReturned)
print("totalKeysExamined: " + statistik.totalKeysExamined)
print("totalDocsExamined: " + statistik.totalDocsExamined)

text Keluaran

nReturned: 5

totalKeysExamined: 0

totalDocsExamined: 500

Server memeriksa lima ratus dokumen untuk mengembalikan lima dokumen, sedangkan totalKeysExamined bernilai nol karena belum ada indeks yang dipakai. Pada koleksi yang jauh lebih besar, selisih tersebut menjadi biaya utama setiap query.

Membuat indeks pada field yang diquery#

Metode createIndex menerima dokumen spesifikasi berupa pasangan field dan arah, yaitu 1 untuk urutan menaik dan -1 untuk urutan menurun. Buat indeks pada field kata, lalu daftar indeks koleksi diperiksa dengan getIndexes.

mongosh

db.entri.createIndex({ kata: 1 })
db.entri.getIndexes()

text Keluaran

kata_1
[
  { v: 2, key: { _id: 1 }, name: '_id_' },
  { v: 2, key: { kata: 1 }, name: 'kata_1' }
]

Server memberi nama kata_1 secara otomatis dari nama field dan arahnya. Nama tersebut dipakai setiap kali indeks tertentu perlu dirujuk, misalnya saat penghapusan.

Jalankan ulang explain untuk query yang sama dan amati perubahan rencananya.

mongosh

db.entri.find({ kata: "batah" }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

{
  isCached: false,
  stage: 'FETCH',
  inputStage: {
    stage: 'IXSCAN',
    keyPattern: { kata: 1 },
    indexName: 'kata_1',
    isMultiKey: false,
    multiKeyPaths: { kata: [] },
    isUnique: false,
    isSparse: false,
    isPartial: false,
    indexVersion: 2,
    direction: 'forward',
    indexBounds: { kata: [ '["batah", "batah"]' ] }
  }
}

Rencana kini terdiri atas dua tahap bertingkat. Tahap IXSCAN menelusuri indeks kata_1 dengan batas kunci ["batah", "batah"], sedangkan tahap FETCH mengambil dokumen lengkap yang ditunjuk oleh setiap kunci tersebut. Ukur ulang statistik eksekusinya.

mongosh

const statistik2 = db.entri.find({ kata: "batah" }).explain("executionStats").executionStats
print("nReturned: " + statistik2.nReturned)
print("totalKeysExamined: " + statistik2.totalKeysExamined)
print("totalDocsExamined: " + statistik2.totalDocsExamined)

text Keluaran

nReturned: 5

totalKeysExamined: 5

totalDocsExamined: 5

Jumlah dokumen yang diperiksa turun dari lima ratus menjadi lima, yaitu persis jumlah dokumen yang dikembalikan. Nilai totalKeysExamined juga lima. Artinya, setiap kunci yang dibaca dari indeks langsung menghasilkan dokumen, sehingga tidak ada pekerjaan yang terbuang.

Struktur B-tree dan rentang nilai#

MongoDB menyimpan indeks sebagai pohon B-tree, yaitu pohon seimbang yang setiap simpulnya memuat kunci terurut beserta penunjuk ke simpul anak. Kedalaman pohon tumbuh secara logaritmik terhadap jumlah kunci, sehingga menemukan satu kunci hanya memerlukan sedikit langkah tanpa mempedulikan ukuran koleksi. Sifat terurut pada kunci daun, yaitu kunci pada simpul paling bawah pohon, memberi manfaat tambahan berupa rentang nilai yang dapat dilalui berurutan tanpa memeriksa keseluruhan kunci. Rentang dengan arah sebaliknya dilayani oleh perjalanan mundur pada pohon yang sama, sehingga arah query tidak menuntut indeks kedua. Query kesamaan dan query rentang sama-sama diuntungkan oleh struktur ini.

Buat indeks pada field frekuensi, lalu jalankan query rentang untuk entri dengan frekuensi minimal 800. Batas kunci pada rencana menunjukkan rentang yang dilalui indeks.

mongosh

db.entri.createIndex({ frekuensi: 1 })
const rencana = db.entri.find({ frekuensi: { $gte: 800 } }).explain("executionStats")
print("Batas kunci: " + JSON.stringify(rencana.queryPlanner.winningPlan.inputStage.indexBounds))
print("nReturned: " + rencana.executionStats.nReturned)
print("totalKeysExamined: " + rencana.executionStats.totalKeysExamined)
print("totalDocsExamined: " + rencana.executionStats.totalDocsExamined)

text Keluaran

frekuensi_1

Batas kunci: {"frekuensi":["[800, inf]"]}

nReturned: 14

totalKeysExamined: 14

totalDocsExamined: 14

Batas kunci [800, inf] berarti server memulai perjalanan pada kunci pertama yang nilainya 800, lalu berjalan menaik hingga ujung daun. Empat belas kunci dibaca dan empat belas dokumen diambil, sehingga sisa empat ratus delapan puluh enam dokumen tidak pernah disentuh. Tanpa indeks, query rentang yang sama tetap memeriksa seluruh koleksi melalui COLLSCAN.

Biaya indeks dan kapan dibutuhkan#

Setiap penyisipan, pembaruan, dan penghapusan dokumen harus memperbarui semua indeks koleksi tersebut. Koleksi dengan banyak indeks membayar biaya ini pada setiap penulisan, dan struktur B-tree-nya juga mengonsumsi penyimpanan serta memori server. Pembangunan indeks baru pada koleksi yang sudah besar juga memerlukan waktu, sehingga penambahannya sebaiknya disengaja, bukan refleks. Pembaruan yang mengubah nilai field terindeks menggerakkan kunci pada pohon, sedangkan pembaruan pada field lain tidak. Karena itu jumlah indeks perlu selaras dengan query yang benar-benar berjalan.

Indeks layak dibuat bila fieldnya sering muncul pada syarat query atau pengurutan. Syarat itu juga perlu memiliki selektivitas yang cukup, yaitu mengembalikan dokumen yang jauh lebih sedikit daripada isi koleksi. Sebaliknya, indeks tidak dibutuhkan pada koleksi kecil yang seluruhnya sering dibaca, field yang jarang diquery, dan field dengan nilai yang hampir sama. Hapus indeks yang tidak terpakai dengan dropIndex berdasarkan namanya.

mongosh

const hapus = db.entri.dropIndex("frekuensi_1")
print("frekuensi_1 dihapus: " + (hapus.ok === 1))
db.entri.getIndexes()

text Keluaran

frekuensi_1 dihapus: true

[
  { v: 2, key: { _id: 1 }, name: '_id_' },
  { v: 2, key: { kata: 1 }, name: 'kata_1' }
]

Kesalahan umum#

Kesalahan yang lazim adalah menganggap satu indeks melayani field lain. Indeks kata_1 yang baru dibuat hanya menyimpan nilai kata, sehingga query pada field kategori tetap memeriksa seluruh koleksi.

mongosh

db.entri.find({ kategori: "verba" }).explain("queryPlanner").queryPlanner.winningPlan.stage

text Keluaran

COLLSCAN

Rencana kembali menunjukkan COLLSCAN meskipun koleksi sudah memiliki indeks, karena server tidak menemukan kunci indeks yang menyimpan nilai kategori. Perbaikannya adalah membuat indeks pada field yang muncul dalam syarat query, yaitu db.entri.createIndex({ kategori: 1 }) untuk contoh ini. Query yang menyaring beberapa field sekaligus menuntut indeks komposit, yaitu satu indeks yang mencakup beberapa field dengan urutan yang tepat, karena indeks per field yang terpisah tidak menggabungkan penyaringan query. Kesalahan sejenis juga terjadi sebaliknya, yaitu menghapus indeks yang ternyata masih dipakai query rutin, sehingga query yang tadinya cepat kembali memindai seluruh koleksi. Pemeriksaan rencana query melalui explain setelah setiap perubahan daftar indeks menjadi kebiasaan yang mencegah kedua jenis kesalahan ini.

Ringkasan#

Indeks menyimpan kunci terurut dalam struktur B-tree, sehingga query kesamaan maupun rentang dapat dilayani dengan membaca sedikit kunci.
Tahap COLLSCAN menandai pemindaian seluruh koleksi, sedangkan IXSCAN menandai pemindaian indeks, dan keduanya terbaca melalui explain.
totalDocsExamined pada executionStats mengukur pekerjaan query secara langsung, yaitu jumlah dokumen yang benar-benar dibaca server.
Setiap indeks menambah biaya penulisan dan penyimpanan, sehingga daftar indeks perlu selaras dengan query aplikasi dan indeks yang terlantar dihapus.

Referensi#

Indexes — MongoDB Manual — Ringkasan konsep indeks, perilaku pembuatan, dan jenis-jenisnya.
db.collection.createIndex() — MongoDB Manual — Spesifikasi pembuatan indeks beserta opsi dan penamaannya.
db.collection.getIndexes() — MongoDB Manual — Metode untuk membaca daftar indeks sebuah koleksi.
db.collection.dropIndex() — MongoDB Manual — Metode penghapusan indeks tertentu berdasarkan nama.