KAL
Menu

Pencarian

Intuisi inverted index dan posisi Elasticsearch atau OpenSearch dalam arsitektur.

Daftar isi

Pencarian teks pada skala besar ditopang oleh inverted index, yaitu struktur data yang memetakan setiap istilah ke daftar dokumen yang memuatnya, sehingga kueri dilayani dengan melihat daftar itu alih-alih memindai seluruh isi dokumen. Topik ini membangun intuisi tersebut dengan indeks sederhana yang dapat dijalankan ulang, lalu menempatkan posisi Elasticsearch dan OpenSearch dalam arsitektur sistem secara keseluruhan.

Dari pemindaian ke inverted index#

Cara paling sederhana mencari teks di basis data adalah kueri seperti LIKE '%istilah%', dan persis di situlah masalahnya. Pola pencarian dengan tanda bintang di kedua sisi tidak dapat memakai indeks biasa, sehingga setiap kueri memindai seluruh tabel. Pada tabel jutaan baris, biayanya tumbuh linear terhadap ukuran data dan beban ini bertumpuk pada basis data yang sedang sibuk melayani transaksi.

Inverted index membalik arah pandangannya. Basis data biasa memetakan dokumen ke isinya, sedangkan indeks terbalik memetakan istilah ke daftar dokumen, yang disebut posting list. Pencarian berjalan dalam dua fase, yaitu fase pengindeksan yang memecah teks menjadi token dan mengisi posting list, kemudian fase kueri yang mengambil serta menggabungkan posting list dari istilah yang dicari. Karena daftarnya sudah siap, biaya kueri sebanding dengan panjang posting list, bukan dengan jumlah seluruh dokumen.

Struktur yang sama juga menjadi tempat penyimpanan informasi relevansi, misalnya berapa kali sebuah istilah muncul di setiap dokumen, sehingga hasil kueri dapat diberi skor dan diurutkan. Mesin pencarian modern memiliki mekanisme yang sama, hanya dengan tingkat penyempurnaan yang jauh lebih tinggi.

Skor relevansi yang paling dikenal dibangun dari dua sinyal, yaitu term frequency yang mengukur seberapa sering istilah muncul di satu dokumen, dan inverse document frequency yang menurunkan bobot istilah yang terdapat pada hampir semua dokumen. Istilah yang jarang, seperti “cache” pada korpus contoh, membedakan dokumen dengan kuat, sedangkan istilah umum hampir tidak memberi informasi. Mesin pencarian modern memakai turunan gagasan tersebut, misalnya BM25, tetapi intuisi kedua komponennya tetap sama dan cukup untuk membaca perilaku pemeringkatan hasil kueri.

Membangun inverted index sederhana#

Intuisi struktur ini cukup dibangun dari puluhan baris Python. Program berikut mengindeks enam dokumen kecil dengan tokenisasi sederhana berupa pemisahan spasi, tanpa stemming dan tanpa stopword, lalu menjalankan beberapa kueri di atasnya.

python inverted-index.py 
"""Membangun inverted index sederhana dari enam dokumen, lalu menjalankan kueri.

Stemming dan stopword sengaja tidak dipakai agar mekanismenya terlihat polos.
"""

DOKUMEN = {
    1: "cache menyimpan salinan data agar latensi turun",
    2: "cdn menyimpan salinan konten di server edge terdekat",
    3: "basis data relasional menyimpan data terstruktur",
    4: "redis adalah cache dalam memori yang juga dipakai sebagai antrean",
    5: "object storage menyimpan berkas berukuran besar secara durabel",
    6: "cache miss memaksa sistem mengambil data dari basis data",
}


def tokenisasi(teks):
    return teks.split()


indeks = {}
for id_dok, teks in DOKUMEN.items():
    for token in tokenisasi(teks):
        indeks.setdefault(token, []).append(id_dok)

print("Isi inverted index untuk beberapa istilah:")
for istilah in ["cache", "menyimpan", "data", "redis"]:
    print(f"  {istilah:<10}: {indeks[istilah]}")


def kueri_dan(istilah_a, istilah_b):
    hasil = sorted(set(indeks.get(istilah_a, [])) & set(indeks.get(istilah_b, [])))
    return hasil


print()
print("Kueri 'cache AND data'  :", kueri_dan("cache", "data"))
print("Kueri 'cache AND redis' :", kueri_dan("cache", "redis"))
print("Kueri 'storage AND edge':", kueri_dan("storage", "edge"))

gabung = sorted(set(indeks.get("menyimpan", [])) | set(indeks.get("mengambil", [])))
print()
print("Kueri 'menyimpan OR mengambil':")
print(" ", gabung)
text Keluaran 
Isi inverted index untuk beberapa istilah:
  cache     : [1, 4, 6]
  menyimpan : [1, 2, 3, 5]
  data      : [1, 3, 3, 6, 6]
  redis     : [4]

Kueri 'cache AND data'  : [1, 6]
Kueri 'cache AND redis' : [4]
Kueri 'storage AND edge': []

Kueri 'menyimpan OR mengambil':
  [1, 2, 3, 5, 6]

Posting list istilah data memuat duplikat, yaitu 3 dan 6 masing-masing muncul dua kali, karena program mencatat setiap kemunculan istilah dan jumlah itulah bahan mentah untuk skor relevansi. Kueri AND menajamkan hasil dengan mengiris posting list, sedangkan kueri OR memperluasnya dengan menggabungkan. Kueri storage AND edge menghasilkan daftar kosong, dan itu keluaran yang sah, yaitu tidak ada dokumen yang memuat kedua istilah tersebut. Pada indeks nyata, langkah yang sama dilakukan oleh mesin pencarian, hanya ditambah normalisasi huruf kecil, stemming, dan penghapusan stopword.

Posisi Elasticsearch dan OpenSearch dalam arsitektur#

Elasticsearch dan OpenSearch adalah mesin pencarian terdistribusi yang membangun dan mengelola inverted index dalam skala besar. Keduanya menyimpan indeks dalam segment yang tidak berubah, membagi indeks ke beberapa shard, lalu menggandakan setiap shard menjadi replica untuk ketersediaan. Dokumen yang baru diindeks dapat dicari setelah operasi refresh yang berlangsung hampir seketika, dan sifat inilah yang membuat modelnya disebut near real time.

Dalam arsitektur, mesin pencarian menempati posisi khusus dan tidak menggantikan basis data. Basis data tetap menjadi sumber kebenaran (source of truth) untuk penulisan, dan mesin pencarian menampung salinan bidang-bidang yang perlu dicari, yang disinkronkan melalui pembaruan aplikasi atau perantara seperti antrean. Pembacaan yang berupa pencarian teks, agregasi, dan autocomplete dialihkan ke mesin pencarian, sedangkan pembacaan berdasarkan kunci utama tetap dilayani basis data.

Mesin pencarian juga bukan kebutuhan mutlak setiap proyek. Data berukuran kecil, pencarian berdasarkan kunci yang persis, atau filter sederhana cukup dilayani indeks bawaan basis data. Mesin pencarian dibutuhkan ketika kueri tidak ketat, relevansi perlu diurutkan, dan jumlah dokumen membuat pemindaian tidak lagi masuk akal.

Kesalahan umum#

  • Menjadikan mesin pencarian sumber kebenaran utama. Indeks pencarian dirancang agar dapat dibangun ulang, sehingga data yang hanya ada di dalamnya akan sulit direkonstruksi. Perbaikannya adalah menjaga basis data sebagai sumber kebenaran dan mensinkronkan salinan bidang pencarian ke mesin indeks.
  • Mengindeks semua bidang tanpa perencanaan analisisnya. Bidang yang diperlakukan sebagai teks penuh akan dipecah menjadi token, padahal bidang seperti status atau kategori lebih tepat sebagai kata kunci yang utuh.
  • Mengabaikan bentuk kata pada bahasa Indonesia. Tanpa stemming, pencarian “dibuat” tidak menemukan dokumen yang hanya memuat “membuat”, karena keduanya menjadi token yang berbeda.

Ringkasan#

  • Inverted index memetakan istilah ke posting list dokumen, sehingga biaya kueri sebanding dengan panjang daftar alih-alih jumlah seluruh dokumen.
  • Posting list menyimpan setiap kemunculan istilah, dan bahan itulah yang dipakai untuk kueri AND, OR, serta pemberian skor relevansi.
  • Elasticsearch dan OpenSearch menjalankan mekanisme yang sama dalam skala terdistribusi dengan shard dan replica, sedangkan basis data tetap menjadi sumber kebenaran yang disinkronkan ke mesin pencarian.

Referensi#