Indeks komposit

Merancang indeks komposit dengan urutan field yang benar menurut aturan ESR.

Daftar isi

Indeks komposit menyimpan kunci dari beberapa field sekaligus dalam satu struktur B-tree, dan urutan fieldnya menentukan query mana yang dapat dilayani dengan baik. Topik ini membahas keterbatasan indeks satu field pada query yang menggabungkan penyaringan dengan pengurutan, penyusunan indeks komposit menurut aturan ESR (Equality, Sort, Range), serta pemanfaatan awalan indeks dan arah perjalanan kunci. Demonstrasi tetap memakai basis data kamus dengan koleksi entri berisi lima ratus dokumen. Setelah mengikuti topik ini, urutan field pada indeks komposit dapat ditentukan berdasarkan bentuk query, bukan berdasarkan kebiasaan.

Pengurutan yang tidak tertangani indeks#

Query yang menyaring pada satu field tetapi mengurutkan pada field lain memunculkan pekerjaan tambahan pada server. Indeks satu field hanya menyimpan satu dimensi nilai, sehingga hasil penyaringan harus diurutkan ulang oleh server sebelum dikirim. Biaya pengurutan di dalam memori ini dihitung ulang pada setiap eksekusi query, bukan sekali di awal. Kondisi ini terlihat pada rencana query sebagai tahap SORT yang berdiri di atas tahap pembacaan.

Tanamlah data contoh berikut, lalu bersihkan indeks lama agar demonstrasi dimulai dari kondisi bersih.

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

mongosh

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

text Keluaran

Indeks non-_id dibersihkan: true

Buat indeks satu field pada kategori, lalu amati rencana query yang menyaring kategori verba dan mengurutkan hasilnya menurut frekuensi menurun.

mongosh

db.entri.createIndex({ kategori: 1 })
db.entri.find({ kategori: "verba" }).sort({ frekuensi: -1 }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

kategori_1
{
  isCached: false,
  stage: 'SORT',
  sortPattern: { frekuensi: -1 },
  memLimit: 104857600,
  type: 'simple',
  inputStage: {
    stage: 'FETCH',
    inputStage: {
      stage: 'IXSCAN',
      keyPattern: { kategori: 1 },
      indexName: 'kategori_1',
      isMultiKey: false,
      multiKeyPaths: { kategori: [] },
      isUnique: false,
      isSparse: false,
      isPartial: false,
      indexVersion: 2,
      direction: 'forward',
      indexBounds: { kategori: [ '["verba", "verba"]' ] }
    }
  }
}

Rencana memuat tiga tahap bertingkat. Tahap SORT mengurutkan dokumen di dalam memori sebelum hasilnya dikirim, dengan angka 104857600 pada field memLimit sebagai batas memorinya dalam byte. Tahap IXSCAN di bawahnya hanya menangani penyaringan kategori, sedangkan urutan frekuensi dihitung ulang untuk setiap eksekusi. Indeks satu field memang menghilangkan pemindaian koleksi, tetapi pekerjaan pengurutannya tetap berat pada hasil yang banyak.

Indeks komposit dengan urutan equality dan sort#

Indeks komposit mendaftarkan lebih dari satu field dalam dokumen spesifikasinya, misalnya { kategori: 1, frekuensi: -1 }. Kuncinya tersusun leksikografis, yaitu entri dikelompokkan menurut kategori, lalu di dalam setiap kategori diurutkan menurut frekuensi menurun. Bentuk inilah yang membuat pengurutan pada query dapat diambil langsung dari urutan kunci indeks.

Ganti indeks satu field dengan indeks komposit yang menyandingkan kategori dan frekuensi.

mongosh

const hapus1 = db.entri.dropIndex("kategori_1")
print("kategori_1 dihapus: " + (hapus1.ok === 1))
db.entri.createIndex({ kategori: 1, frekuensi: -1 })

text Keluaran

kategori_1 dihapus: true

kategori_1_frekuensi_-1

Jalankan ulang explain untuk query yang sama dan periksa rencananya.

mongosh

db.entri.find({ kategori: "verba" }).sort({ frekuensi: -1 }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

{
  isCached: false,
  stage: 'FETCH',
  inputStage: {
    stage: 'IXSCAN',
    keyPattern: { kategori: 1, frekuensi: -1 },
    indexName: 'kategori_1_frekuensi_-1',
    isMultiKey: false,
    multiKeyPaths: { kategori: [], frekuensi: [] },
    isUnique: false,
    isSparse: false,
    isPartial: false,
    indexVersion: 2,
    direction: 'forward',
    indexBounds: {
      kategori: [ '["verba", "verba"]' ],
      frekuensi: [ '[MaxKey, MinKey]' ]
    }
  }
}

Tahap SORT menghilang dari rencana. Server menelusuri indeks dengan batas kategori bernilai verba, dan entri yang dilaluinya sudah tersusun menurut frekuensi menurun sebagaimana diminta query. Statistik eksekusinya memperlihatkan jumlah kunci dan dokumen yang disentuh.

mongosh

const st1 = db.entri.find({ kategori: "verba" }).sort({ frekuensi: -1 }).explain("executionStats").executionStats
print("nReturned: " + st1.nReturned)
print("totalKeysExamined: " + st1.totalKeysExamined)
print("totalDocsExamined: " + st1.totalDocsExamined)

text Keluaran

nReturned: 167

totalKeysExamined: 167

totalDocsExamined: 167

Seluruh 167 dokumen kategori verba diambil karena query tidak menyaring field lain, sehingga jumlah kunci yang diperiksa sama dengan jumlah dokumen yang diambil. Pada bentuk query inilah indeks komposit bekerja paling efisien, yaitu kesamaan diterapkan pada field pertama dan urutan hasil diambil dari field kedua. Setiap filter tambahan yang tidak termuat dalam indeks memunculkan pengambilan dokumen yang sebagian tidak lolos filter, sebagaimana ditunjukkan bagian berikutnya.

Aturan ESR dan rentang nilai#

Aturan ESR menuntun urutan field pada indeks komposit, yaitu kesamaan (equality) lebih dahulu, diikuti pengurutan (sort), lalu rentang (range) paling akhir. Kesamaan diletakkan di depan karena nilainya mempersempit kunci sejak awal perjalanan indeks. Field pengurutan diletakkan sebelum field rentang agar urutan hasil tetap dapat diambil dari kunci. Field rentang tetap dapat dievaluasi pada kunci indeks, sehingga penempatannya di posisi terakhir tidak merusak urutan hasil.

Perhatikan query yang menyaring kategori, mengurutkan frekuensi, sekaligus menyaring tahun. Dengan indeks yang hanya memuat kategori dan frekuensi, filter tahun dievaluasi setelah dokumen diambil.

mongosh

const st2 = db.entri.find({ kategori: "verba", tahun: { $gte: 2020 } }).sort({ frekuensi: -1 }).explain("executionStats").executionStats
print("nReturned: " + st2.nReturned)
print("totalKeysExamined: " + st2.totalKeysExamined)
print("totalDocsExamined: " + st2.totalDocsExamined)

text Keluaran

nReturned: 82

totalKeysExamined: 167

totalDocsExamined: 167

Server memeriksa 167 kunci dan mengambil seluruh 167 dokumen, meskipun hanya 82 dokumen yang memenuhi syarat tahun. Tambahkan tahun sebagai field ketiga indeks mengikuti urutan ESR.

mongosh

const hapus2 = db.entri.dropIndex("kategori_1_frekuensi_-1")
print("kategori_1_frekuensi_-1 dihapus: " + (hapus2.ok === 1))
db.entri.createIndex({ kategori: 1, frekuensi: -1, tahun: 1 })

text Keluaran

kategori_1_frekuensi_-1 dihapus: true

kategori_1_frekuensi_-1_tahun_1

Jalankan ulang rencana dan statistiknya untuk query yang sama.

mongosh

db.entri.find({ kategori: "verba", tahun: { $gte: 2020 } }).sort({ frekuensi: -1 }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

{
  isCached: false,
  stage: 'FETCH',
  inputStage: {
    stage: 'IXSCAN',
    keyPattern: { kategori: 1, frekuensi: -1, tahun: 1 },
    indexName: 'kategori_1_frekuensi_-1_tahun_1',
    isMultiKey: false,
    multiKeyPaths: { kategori: [], frekuensi: [], tahun: [] },
    isUnique: false,
    isSparse: false,
    isPartial: false,
    indexVersion: 2,
    direction: 'forward',
    indexBounds: {
      kategori: [ '["verba", "verba"]' ],
      frekuensi: [ '[MaxKey, MinKey]' ],
      tahun: [ '[2020, inf]' ]
    }
  }
}

mongosh

const st3 = db.entri.find({ kategori: "verba", tahun: { $gte: 2020 } }).sort({ frekuensi: -1 }).explain("executionStats").executionStats
print("nReturned: " + st3.nReturned)
print("totalKeysExamined: " + st3.totalKeysExamined)
print("totalDocsExamined: " + st3.totalDocsExamined)

text Keluaran

nReturned: 82

totalKeysExamined: 167

totalDocsExamined: 82

Tahap SORT tetap tidak muncul, sedangkan totalDocsExamined turun dari 167 menjadi 82 karena filter tahun dievaluasi pada kunci indeks sebelum dokumen diambil. Field rentang yang ditempatkan setelah field pengurutan memberi keuntungan tanpa mengorbankan urutan hasil. Inilah alasan urutan kesamaan, pengurutan, rentang pada indeks menjadi pola baku.

Awalan indeks dan arah perjalanan#

Indeks komposit { kategori: 1, frekuensi: -1, tahun: 1 } melayani query pada awalannya, yaitu kategori saja atau kategori dan frekuensi, tanpa perlu indeks terpisah. Sebaliknya, query yang menyaring field di tengah atau di akhir indeks tidak menemukan awalan kunci yang bisa dilalui, sehingga indeks tersebut tidak terpakai. Periksa kedua bentuk query berikut.

mongosh

db.entri.find({ kategori: "adjektiva" }).explain("queryPlanner").queryPlanner.winningPlan.inputStage.indexName
db.entri.find({ frekuensi: { $gt: 800 } }).explain("queryPlanner").queryPlanner.winningPlan.stage

text Keluaran

kategori_1_frekuensi_-1_tahun_1
COLLSCAN

Query dengan awalan kategori memakai indeks kategori_1_frekuensi_-1_tahun_1, sedangkan query yang menyaring frekuensi saja kembali ke COLLSCAN. Arah perjalanan indeks juga dapat dibalik untuk mendukung urutan sebaliknya, selama field kesamaan pada query membatasi indeks ke satu nilai.

mongosh

db.entri.find({ kategori: "verba" }).sort({ frekuensi: 1 }).explain("queryPlanner").queryPlanner.winningPlan.inputStage.direction

text Keluaran

backward

Field direction bernilai backward, yang berarti indeks dilalui dari ujung akhir ke awal sehingga frekuensi tersusun menaik. Indeks yang sama dengan demikian melayani pengurutan menurun maupun menaik pada frekuensi selama kategori dipatok satu nilai.

Kesalahan umum#

Kesalahan yang sering terjadi adalah meletakkan field rentang sebelum field pengurutan, misalnya { kategori: 1, tahun: 1, frekuensi: -1 }. Susunan ini terlihat logis karena mengikuti urutan penyebutan field pada query, tetapi urutan kuncinya berbeda dari yang dibutuhkan pengurutan.

mongosh

const hapus3 = db.entri.dropIndex("kategori_1_frekuensi_-1_tahun_1")
print("kategori_1_frekuensi_-1_tahun_1 dihapus: " + (hapus3.ok === 1))
db.entri.createIndex({ kategori: 1, tahun: 1, frekuensi: -1 })
db.entri.find({ kategori: "verba", tahun: { $gte: 2020 } }).sort({ frekuensi: -1 }).explain("queryPlanner").queryPlanner.winningPlan

text Keluaran

kategori_1_frekuensi_-1_tahun_1 dihapus: true

kategori_1_tahun_1_frekuensi_-1
{
  isCached: false,
  stage: 'FETCH',
  inputStage: {
    stage: 'SORT',
    sortPattern: { frekuensi: -1 },
    memLimit: 104857600,
    type: 'default',
    inputStage: {
      stage: 'IXSCAN',
      keyPattern: { kategori: 1, tahun: 1, frekuensi: -1 },
      indexName: 'kategori_1_tahun_1_frekuensi_-1',
      isMultiKey: false,
      multiKeyPaths: { kategori: [], tahun: [], frekuensi: [] },
      isUnique: false,
      isSparse: false,
      isPartial: false,
      indexVersion: 2,
      direction: 'forward',
      indexBounds: {
        kategori: [ '["verba", "verba"]' ],
        tahun: [ '[2020, inf]' ],
        frekuensi: [ '[MaxKey, MinKey]' ]
      }
    }
  }
}

Tahap SORT kembali muncul di dalam rencana. Indeks ini memang memeriksa lebih sedikit kunci karena batas tahun dipatuhi sejak awal, tetapi keuntungan itu dibayar dengan pengurutan di dalam memori untuk setiap eksekusi. Susunan field yang salah sering terasa logis karena mengikuti urutan penyebutan field pada query, bukan susunan kunci yang dibutuhkan pengurutan.

Perbaikannya adalah mengembalikan urutan field ke bentuk ESR, yaitu field kesamaan, field pengurutan, lalu field rentang. Hilangnya tahap SORT kemudian diverifikasi melalui explain. Indeks dengan susunan lama itu tetap berguna untuk query yang hanya menyaring tanpa mengurutkan. Karena itu, urutan field setiap indeks perlu ditinjau dari kombinasi penyaringan dan pengurutan yang benar-benar berjalan. Field memLimit pada tahap SORT juga menjadi peringatan bahwa hasil yang melebihi batas memori menimbulkan error pada eksekusi nyata.

Ringkasan#

Indeks satu field tidak menghilangkan tahap SORT pada query yang menyaring dan mengurutkan pada field berbeda.
Indeks komposit menyimpan kunci beberapa field sekaligus, dan susunan kesamaan lalu pengurutan mengambil urutan hasil langsung dari indeks.
Aturan ESR menempatkan field rentang setelah field pengurutan, sehingga filter rentang dievaluasi pada kunci tanpa memunculkan tahap SORT.
Hanya awalan indeks yang dapat dipakai query, sedangkan arah perjalanan indeks dapat dibalik untuk mendukung urutan sebaliknya.

Referensi#

Compound Indexes — MongoDB Manual — Dokumentasi indeks komposit beserta aturan awalannya.
Create Indexes to Support Your Queries — MongoDB Manual — Panduan perancangan indeks berisi aturan ESR (Equality, Sort, Range).
db.collection.createIndex() — MongoDB Manual — Spesifikasi pembuatan indeks dengan beberapa field sekaligus.
Query Plans — MongoDB Manual — Penjelasan tahap-tahap rencana query seperti IXSCAN dan SORT.