Memperkenalkan Milvus Ngram Index: Pencocokan Kata Kunci dan Kueri Suka yang Lebih Cepat untuk Beban Kerja Agen

Dalam sistem agen, pengambilan konteks adalah blok bangunan dasar di seluruh pipeline, yang menyediakan dasar untuk penalaran, perencanaan, dan tindakan hilir. Pencarian vektor membantu agen mengambil konteks yang relevan secara semantik yang menangkap maksud dan makna di seluruh kumpulan data yang besar dan tidak terstruktur. Namun, relevansi semantik saja sering kali tidak cukup. Pipeline agen juga mengandalkan pencarian teks lengkap untuk menerapkan batasan kata kunci yang tepat-seperti nama produk, panggilan fungsi, kode kesalahan, atau istilah yang signifikan secara hukum. Lapisan pendukung ini memastikan bahwa konteks yang diambil tidak hanya relevan, tetapi juga secara eksplisit memenuhi persyaratan tekstual yang sulit.

Beban kerja nyata secara konsisten mencerminkan kebutuhan ini:

• Asisten dukungan pelanggan harus menemukan percakapan yang menyebutkan produk atau bahan tertentu.

• Kopilot pengkodean mencari cuplikan yang berisi nama fungsi, panggilan API, atau string kesalahan yang tepat.

• Agen hukum, medis, dan akademis menyaring dokumen untuk mencari klausa atau kutipan yang harus muncul kata demi kata.

Secara tradisional, sistem telah menangani hal ini dengan operator SQL LIKE. Kueri seperti name LIKE '%rod%' sederhana dan didukung secara luas, tetapi di bawah konkurensi yang tinggi dan volume data yang besar, kesederhanaan ini membawa biaya kinerja yang besar.

• Tanpa indeks, kueri LIKE memindai seluruh penyimpanan konteks dan menerapkan pencocokan pola baris demi baris. Dengan jutaan record, bahkan satu kueri saja bisa memakan waktu beberapa detik - terlalu lambat untuk interaksi agen secara real-time.

• Bahkan dengan indeks terbalik konvensional, pola wildcard seperti %rod% tetap sulit untuk dioptimalkan karena mesin masih harus menelusuri seluruh kamus dan menjalankan pencocokan pola pada setiap entri. Operasi ini menghindari pemindaian baris tetapi tetap linear secara fundamental, sehingga hanya menghasilkan peningkatan yang marginal.

Hal ini menciptakan kesenjangan yang jelas dalam sistem pencarian hibrida: pencarian vektor menangani relevansi semantik secara efisien, tetapi pemfilteran kata kunci yang tepat seringkali menjadi langkah paling lambat dalam proses.

Milvus secara native mendukung pencarian vektor hibrida dan pencarian teks lengkap dengan pemfilteran metadata. Untuk mengatasi keterbatasan pencocokan kata kunci, Milvus memperkenalkan Indeks Ngram, yang meningkatkan kinerja LIKE dengan memecah teks menjadi beberapa substring kecil dan mengindeksnya untuk pencarian yang efisien. Hal ini secara dramatis mengurangi jumlah data yang diperiksa selama eksekusi kueri, memberikan puluhan hingga ratusan kali lebih cepat LIKE kueri dalam beban kerja agen yang nyata.

Bagian selanjutnya dari artikel ini akan menjelaskan cara kerja Ngram Index di Milvus dan mengevaluasi kinerjanya dalam skenario dunia nyata.

Apa itu Indeks Ngram?

Dalam database, pemfilteran teks biasanya diekspresikan menggunakan SQL, bahasa kueri standar yang digunakan untuk mengambil dan mengelola data. Salah satu operator teks yang paling banyak digunakan adalah LIKE, yang mendukung pencocokan string berbasis pola.

Ekspresi LIKE dapat dikelompokkan secara luas ke dalam empat jenis pola umum, tergantung pada bagaimana karakter pengganti (wildcard) digunakan:

• Pencocokan infiks (name LIKE '%rod%'): Mencocokkan catatan di mana batang substring muncul di mana saja dalam teks.

• Pencocokan awalan (name LIKE 'rod%'): Mencocokkan catatan yang teksnya dimulai dengan batang.

• Pencocokan akhiran (name LIKE '%rod'): Mencocokkan catatan yang teksnya diakhiri dengan batang.

• Pencocokan karakter pengganti (name LIKE '%rod%aab%bc_de'): Menggabungkan beberapa kondisi substring (%) dengan wildcard karakter tunggal (_) dalam satu pola.

Meskipun pola-pola ini berbeda dalam penampilan dan ekspresifitasnya, Indeks Ngram di Milvus mempercepat semuanya dengan menggunakan pendekatan yang sama.

Sebelum membangun indeks, Milvus membagi setiap nilai teks menjadi substring-substring pendek yang saling tumpang tindih dengan panjang yang tetap, yang dikenal sebagai n-gram. Sebagai contoh, ketika n = 3, kata "Milvus" diuraikan menjadi 3-gram berikut: "Mil", "ilv", "lvu", dan "vus". Setiap n-gram kemudian disimpan dalam indeks terbalik yang memetakan substring ke kumpulan ID dokumen tempat substring tersebut muncul. Pada waktu kueri, kondisi LIKE diterjemahkan ke dalam kombinasi pencarian n-gram, yang memungkinkan Milvus untuk dengan cepat menyaring sebagian besar catatan yang tidak cocok dan mengevaluasi pola terhadap kumpulan kandidat yang jauh lebih kecil. Inilah yang mengubah pemindaian string yang mahal menjadi kueri berbasis indeks yang efisien.

Dua parameter mengontrol bagaimana Indeks Ngram dibangun: min_gram dan max_gram. Bersama-sama, keduanya mendefinisikan rentang panjang substring yang dihasilkan dan diindeks oleh Milvus.

• min_gram: Panjang substring terpendek untuk diindeks. Dalam praktiknya, ini juga menentukan panjang substring kueri minimum yang dapat memanfaatkan Indeks Ngram

• max_gram: Panjang substring terpanjang untuk diindeks. Pada waktu kueri, ini juga menentukan ukuran jendela maksimum yang digunakan ketika membagi string kueri yang lebih panjang menjadi n-gram.

Dengan mengindeks semua substring yang bersebelahan yang panjangnya berada di antara min_gram dan max_gram, Milvus membangun fondasi yang konsisten dan efisien untuk mempercepat semua jenis pola LIKE yang didukung.

Bagaimana Cara Kerja Indeks Ngram?

Milvus mengimplementasikan Indeks Ngram dalam proses dua tahap:

• Membangun indeks: Menghasilkan n-gram untuk setiap dokumen dan membangun indeks terbalik selama proses pemasukan data.

• Mempercepat kueri: Gunakan indeks untuk mempersempit pencarian ke sekumpulan kandidat kecil, lalu verifikasi kecocokan LIKE yang tepat pada kandidat tersebut.

Contoh konkret membuat proses ini lebih mudah dipahami.

Tahap 1: Membangun indeks

Menguraikan teks menjadi n-gram:

Asumsikan kita mengindeks teks "Apple" dengan pengaturan berikut:

• min_gram = 2

• max_gram = 3

Di bawah pengaturan ini, Milvus menghasilkan semua substring yang bersebelahan dengan panjang 2 dan 3:

• 2-gram: Ap, pp, pl, le

• 3-gram: App, ppl, ple

Membangun indeks terbalik:

Sekarang perhatikan sebuah set data kecil yang terdiri dari lima catatan:

• Dokumen 0: Apple

• Dokumen 1 Pineapple

• Dokumen 2 Maple

• Dokumen 3 Apply

• Dokumen 4: Snapple

Selama proses ingestion, Milvus menghasilkan n-gram untuk setiap catatan dan memasukkannya ke dalam indeks terbalik. Dalam indeks ini:

• Kunci adalah n-gram (substring)

• Nilai adalah daftar ID dokumen di mana n-gram muncul

"Ap"  -> [0, 3]
"App" -> [0, 3]
"Ma"  -> [2]
"Map" -> [2]
"Pi"  -> [1]
"Pin" -> [1]
"Sn"  -> [4]
"Sna" -> [4]
"ap"  -> [1, 2, 4]
"apl" -> [2]
"app" -> [1, 4]
"ea"  -> [1]
"eap" -> [1]
"in"  -> [1]
"ine" -> [1]
"le"  -> [0, 1, 2, 4]
"ly"  -> [3]
"na"  -> [4]
"nap" -> [4]
"ne"  -> [1]
"nea" -> [1]
"pl"  -> [0, 1, 2, 3, 4]
"ple" -> [0, 1, 2, 4]
"ply" -> [3]
"pp"  -> [0, 1, 3, 4]
"ppl" -> [0, 1, 3, 4]

Sekarang indeks sudah selesai dibangun.

Tahap 2: Mempercepat kueri

Ketika filter LIKE dijalankan, Milvus menggunakan Indeks Ngram untuk mempercepat evaluasi kueri melalui langkah-langkah berikut:

1. Ekstrak istilah kueri: Substring yang bersebelahan tanpa karakter pengganti diekstrak dari ekspresi LIKE (misalnya, '%apple%' menjadi apple).

2. Menguraikan istilah kueri: Istilah kueri diuraikan menjadi n-gram berdasarkan panjangnya (L) dan min_gram dan max_gram yang telah dikonfigurasi.

3. Cari setiap gram & potong: Milvus mencari n-gram kueri dalam indeks terbalik dan memotong daftar ID dokumen mereka untuk menghasilkan set kandidat kecil.

4. Verifikasi dan kembalikan hasilnya: Kondisi asli LIKE diterapkan hanya pada kumpulan kandidat ini untuk menentukan hasil akhir.

Dalam praktiknya, cara kueri dipecah menjadi n-gram tergantung pada bentuk pola itu sendiri. Untuk melihat cara kerjanya, kita akan fokus pada dua kasus umum: pencocokan infiks dan pencocokan wildcard. Pencocokan awalan dan akhiran berperilaku sama dengan pencocokan infiks, jadi kita tidak akan membahasnya secara terpisah.

Pencocokan infiks

Untuk pencocokan infix, eksekusi bergantung pada panjang substring literal (L) relatif terhadap min_gram dan max_gram.

1. min_gram ≤ L ≤ max_gram (misalnya, strField LIKE '%ppl%')

Substring literal ppl sepenuhnya berada dalam rentang n-gram yang dikonfigurasi. Milvus secara langsung mencari n-gram "ppl" dalam indeks terbalik, menghasilkan ID dokumen kandidat [0, 1, 3, 4].

Karena literal itu sendiri adalah n-gram yang diindeks, semua kandidat sudah memenuhi kondisi infiks. Langkah verifikasi terakhir tidak menghilangkan catatan apa pun, dan hasilnya tetap [0, 1, 3, 4].

2. L > max_gram (misalnya, strField LIKE '%pple%')

Substring literal pple lebih panjang daripada max_gram, sehingga diuraikan menjadi n-gram yang tumpang tindih dengan menggunakan ukuran jendela max_gram. Dengan max_gram = 3, hal ini menghasilkan n-gram "ppl" dan "ple".

Milvus mencari setiap n-gram dalam indeks terbalik:

• "ppl" → [0, 1, 3, 4]

• "ple" → [0, 1, 2, 4]

Perpotongan daftar-daftar ini menghasilkan himpunan kandidat [0, 1, 4]. Filter LIKE '%pple%' yang asli kemudian diterapkan pada kandidat-kandidat ini. Ketiganya memenuhi syarat, sehingga hasil akhirnya tetap [0, 1, 4].

3. L < min_gram (misalnya, strField LIKE '%pp%')

Substring literal lebih pendek daripada min_gram dan oleh karena itu tidak dapat diuraikan menjadi n-gram yang diindeks. Dalam kasus ini, Indeks Ngram tidak dapat digunakan, dan Milvus kembali ke jalur eksekusi default, mengevaluasi kondisi LIKE melalui pemindaian penuh dengan pencocokan pola.

Pencocokan wildcard (misalnya, strField LIKE '%Ap%pple%')

Pola ini mengandung beberapa karakter pengganti, sehingga Milvus pertama-tama memecahnya menjadi beberapa literal yang bersebelahan: "Ap" dan "pple".

Milvus kemudian memproses setiap literal secara terpisah:

• "Ap" memiliki panjang 2 dan berada dalam rentang n-gram.

• "pple" lebih panjang dari max_gram dan diuraikan menjadi "ppl" dan "ple".

Hal ini mengurangi kueri menjadi n-gram berikut ini:

• "Ap" → [0, 3]

• "ppl" → [0, 1, 3, 4]

• "ple" → [0, 1, 2, 4]

Perpotongan daftar ini menghasilkan satu kandidat: [0].

Akhirnya, filter LIKE '%Ap%pple%' asli diterapkan pada dokumen 0 ("Apple"). Karena tidak memenuhi pola penuh, kumpulan hasil akhirnya kosong.

Keterbatasan dan Trade-off dari Indeks Ngram

Meskipun Indeks Ngram dapat secara signifikan meningkatkan kinerja kueri LIKE, indeks ini memperkenalkan trade-off yang harus dipertimbangkan dalam penerapan di dunia nyata.

• Peningkatan ukuran indeks

Biaya utama dari Indeks Ngram adalah biaya penyimpanan yang lebih tinggi. Karena indeks menyimpan semua substring yang bersebelahan yang panjangnya berada di antara min_gram dan max_gram, jumlah n-gram yang dihasilkan tumbuh dengan cepat seiring dengan meluasnya rentang ini. Setiap penambahan panjang n-gram secara efektif menambahkan satu set lengkap substring yang tumpang tindih untuk setiap nilai teks, sehingga meningkatkan jumlah kunci indeks dan daftar postingnya. Dalam praktiknya, memperluas jangkauan hanya dengan satu karakter dapat menggandakan ukuran indeks secara kasar dibandingkan dengan indeks terbalik standar.

• Tidak efektif untuk semua beban kerja

Indeks Ngram tidak mempercepat setiap beban kerja. Jika pola kueri sangat tidak teratur, mengandung literal yang sangat pendek, atau gagal mengurangi dataset menjadi kumpulan kandidat yang kecil pada fase pemfilteran, manfaat kinerjanya mungkin terbatas. Dalam kasus seperti itu, eksekusi kueri masih dapat mendekati biaya pemindaian penuh, meskipun indeksnya ada.

Mengevaluasi Kinerja Indeks Ngram pada Kueri LIKE

Tujuan dari tolok ukur ini adalah untuk mengevaluasi seberapa efektif Indeks Ngram mempercepat kueri LIKE dalam praktiknya.

Metodologi Pengujian

Untuk menempatkan kinerjanya dalam konteks, kami membandingkannya dengan dua mode eksekusi dasar:

• Master: Eksekusi secara brute-force tanpa indeks apa pun.

• Master-terbalik: Eksekusi menggunakan indeks terbalik konvensional.

Kami merancang dua skenario pengujian untuk mencakup karakteristik data yang berbeda:

• Kumpulan data teks wiki: 100.000 baris, dengan setiap bidang teks dipotong menjadi 1 KB.

• Dataset kata tunggal: 1.000.000 baris, di mana setiap baris berisi satu kata.

Di kedua skenario, pengaturan berikut diterapkan secara konsisten:

• Kueri menggunakan pola pencocokan infiks (%xxx%)

• Indeks Ngram dikonfigurasikan dengan min_gram = 2 dan max_gram = 4

• Untuk mengisolasi biaya eksekusi kueri dan menghindari overhead perwujudan hasil, semua kueri mengembalikan count(*), bukan set hasil lengkap.

Hasil

Tes untuk wiki, setiap baris adalah teks wiki dengan panjang konten terpotong 1000, 100K baris

	Literal	Waktu (ms)	Kecepatan	Hitung
Master	stadion	207.8		335
Master-terbalik		2095		335
Ngram		1.09	190 / 1922	335
Guru	sekolah menengah	204.8		340
Master-terbalik		2000		340
Ngram		1.26	162.5 / 1587	340
Guru	adalah sponsor sekolah menengah yang bersifat koedukasi	223.9		1
Guru terbalik		2100		1
Ngram		1.69	132.5 / 1242.6	1

Tes untuk kata tunggal, 1 juta baris

	Literal	Waktu (ms)	Percepatan	Hitung
Menguasai	na	128.6		40430
Master-terbalik		66.5		40430
Ngram		1.38	93.2 / 48.2	40430
Guru	nat	122		5200
Master-terbalik		65.1		5200
Ngram		1.27	96 / 51.3	5200
Guru	nati	118.8		1630
Master-terbalik		66.9		1630
Ngram		1.21	98.2 / 55.3	1630
Master	natio	118.4		1100
Master terbalik		65.1		1100
Ngram		1.33	89 / 48.9	1100
Guru	bangsa	118		1100
Master-terbalik		63.3		1100
Ngram		1.4	84.3 / 45.2	1100

Catatan: Hasil ini didasarkan pada tolok ukur yang dilakukan pada bulan Mei. Sejak saat itu, cabang Master telah mengalami pengoptimalan kinerja tambahan, sehingga kesenjangan kinerja yang diamati di sini diharapkan lebih kecil pada versi saat ini.

Hasil tolok ukur menyoroti sebuah pola yang jelas: Indeks Ngram secara signifikan mempercepat kueri LIKE di semua kasus, dan seberapa cepat kueri berjalan sangat bergantung pada struktur dan panjang data teks yang mendasarinya.

• Untuk bidang teks yang panjang, seperti dokumen gaya Wikipedia yang terpotong hingga 1.000 byte, peningkatan kinerja sangat terasa. Dibandingkan dengan eksekusi brute-force tanpa indeks, Indeks Ngram mencapai kecepatan sekitar 100-200×. Jika dibandingkan dengan inverted index konvensional, peningkatannya bahkan lebih dramatis, mencapai 1.200-1.900×. Hal ini dikarenakan kueri LIKE pada teks yang panjang sangat mahal untuk pendekatan pengindeksan tradisional, sementara pencarian n-gram dapat dengan cepat mempersempit ruang pencarian ke sekumpulan kandidat yang sangat kecil.

• Pada kumpulan data yang terdiri dari entri kata tunggal, keuntungannya lebih kecil tetapi masih substansial. Dalam skenario ini, Indeks Ngram berjalan sekitar 80-100× lebih cepat daripada eksekusi brute-force dan 45-55× lebih cepat daripada indeks terbalik konvensional. Meskipun teks yang lebih pendek pada dasarnya lebih murah untuk dipindai, pendekatan berbasis n-gram masih menghindari perbandingan yang tidak perlu dan secara konsisten mengurangi biaya kueri.

Kesimpulan

Indeks Ngram mempercepat kueri LIKE dengan memecah teks menjadi n-gram dengan panjang tetap dan mengindeksnya menggunakan struktur terbalik. Desain ini mengubah pencocokan substring yang mahal menjadi pencarian n-gram yang efisien diikuti dengan verifikasi minimal. Hasilnya, pemindaian teks lengkap dapat dihindari sementara semantik yang tepat dari LIKE tetap terjaga.

Dalam praktiknya, pendekatan ini efektif untuk berbagai macam beban kerja, dengan hasil yang sangat baik untuk pencocokan fuzzy pada bidang teks yang panjang. Oleh karena itu, Ngram Index sangat cocok untuk skenario real-time seperti pencarian kode, agen dukungan pelanggan, pengambilan dokumen hukum dan medis, basis pengetahuan perusahaan, dan pencarian akademis, di mana pencocokan kata kunci yang tepat tetap penting.

Pada saat yang sama, Indeks Ngram mendapatkan manfaat dari konfigurasi yang cermat. Memilih nilai min_gram dan max_gram yang tepat sangat penting untuk menyeimbangkan ukuran indeks dan kinerja kueri. Ketika disetel untuk mencerminkan pola kueri yang sebenarnya, Indeks Ngram memberikan solusi praktis dan terukur untuk kueri LIKE berkinerja tinggi dalam sistem produksi.

Untuk informasi lebih lanjut tentang Indeks Ngram, lihat dokumentasi di bawah ini:

• Indeks Ngram | Dokumentasi Milvus

Ada pertanyaan atau ingin mendalami fitur Milvus terbaru? Bergabunglah dengan saluran Discord kami atau ajukan pertanyaan di GitHub. Anda juga dapat memesan sesi tatap muka selama 20 menit untuk mendapatkan wawasan, panduan, dan jawaban atas pertanyaan Anda melalui Jam Kerja Milvus.

Pelajari Lebih Lanjut tentang Fitur Milvus 2.6

• Memperkenalkan Milvus 2.6: Pencarian Vektor yang Terjangkau dalam Skala Miliaran

• Memperkenalkan Fungsi Penyematan: Bagaimana Milvus 2.6 Menyederhanakan Vektorisasi dan Pencarian Semantik

• Penghancuran JSON di Milvus: Pemfilteran JSON 88,9x Lebih Cepat dengan Fleksibilitas

• Membuka Pengambilan Tingkat Entitas yang Sebenarnya: Kemampuan Array-of-Structs dan MAX_SIM Baru di Milvus

• Menyatukan Pemfilteran Geospasial dan Pencarian Vektor dengan Bidang Geometri dan RTREE di Milvus 2.6

• Memperkenalkan AISAQ di Milvus: Pencarian Vektor Berskala Miliaran Baru Saja Menjadi 3.200× Lebih Murah dalam Memori

• Mengoptimalkan NVIDIA CAGRA di Milvus: Pendekatan Hibrida GPU-CPU untuk Pengindeksan yang Lebih Cepat dan Kueri yang Lebih Murah

• MinHash LSH di Milvus: Senjata Rahasia untuk Memerangi Duplikasi dalam Data Pelatihan LLM

• Membawa Kompresi Vektor ke Tingkat Ekstrim: Bagaimana Milvus Melayani Kueri 3× Lebih Banyak dengan RaBitQ

• Benchmark Bohong - DB Vektor Layak Mendapat Ujian Nyata

• Kami Mengganti Kafka/Pulsar dengan Burung Pelatuk untuk Milvus