Penjelasan Indeks

Indeks adalah struktur tambahan yang dibangun di atas data. Struktur internalnya bergantung pada perkiraan algoritme pencarian tetangga terdekat yang digunakan. Indeks mempercepat pencarian, tetapi menimbulkan waktu, ruang, dan RAM tambahan selama pencarian. Selain itu, penggunaan indeks biasanya menurunkan tingkat pemanggilan (meskipun efeknya dapat diabaikan, namun tetap penting). Oleh karena itu, artikel ini menjelaskan cara meminimalkan biaya penggunaan indeks sekaligus memaksimalkan manfaatnya.

Gambaran Umum

Di Milvus, indeks bersifat spesifik untuk bidang, dan jenis indeks yang berlaku bervariasi sesuai dengan jenis data dari bidang target. Sebagai basis data vektor profesional, Milvus berfokus pada peningkatan kinerja pencarian vektor dan pemfilteran skalar, dan itulah sebabnya Milvus menawarkan berbagai jenis indeks.

Tabel berikut mencantumkan hubungan pemetaan antara tipe data bidang dan tipe indeks yang berlaku.

Tipe Data Bidang	Jenis Indeks yang Berlaku
FLOAT_VECTOR FLOAT16_VECTOR BFLOAT16_VECTOR INT8_VECTOR	DATAR IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ GPU_BRUTE_FORCE
BINARY_VECTOR	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
SPARSE_FLOAT_VECTOR	SPARSE_INVERTED_INDEX
VARCHAR	TERBALIK (Direkomendasikan) BITMAP Trie
BOOL	BITMAP (Direkomendasikan) TERBALIK
INT8 INT16 INT32 INT64	TERBALIK STL_SORT
FLOAT GANDA	TERBALIK
ARRAY (elemen tipe BOOL, INT8/16/32/64, dan VARCHAR)	BITMAP (Direkomendasikan)
ARRAY (elemen dari tipe BOOL, INT8/16/32/64, FLOAT, DOUBLE, dan VARCHAR)	TERBALIK
JSON	TERBALIK

Artikel ini berfokus pada cara memilih indeks vektor yang sesuai. Untuk bidang skalar, Anda selalu dapat menggunakan jenis indeks yang disarankan.

Memilih jenis indeks yang sesuai untuk pencarian vektor dapat memengaruhi kinerja dan penggunaan sumber daya secara signifikan. Saat memilih jenis indeks untuk bidang vektor, penting untuk mempertimbangkan berbagai faktor, termasuk struktur data yang mendasari, penggunaan memori, dan persyaratan kinerja.

Anatomi Indeks Vektor

Seperti yang ditunjukkan pada diagram di bawah ini, sebuah tipe indeks di Milvus terdiri dari tiga komponen inti, yaitu struktur data, kuantisasi, dan refiner. Kuantisasi dan refiner bersifat opsional, tetapi banyak digunakan karena keuntungan yang diperoleh lebih besar daripada biaya.

Anatomi Indeks Vektor

Selama pembuatan indeks, Milvus menggabungkan struktur data dan metode kuantisasi yang dipilih untuk menentukan tingkat ekspansi yang optimal. Pada waktu kueri, sistem mengambil vektor kandidat topK × expansion rate, menerapkan pemurni untuk menghitung ulang jarak dengan presisi yang lebih tinggi, dan akhirnya mengembalikan hasil topK yang paling akurat. Pendekatan hibrida ini menyeimbangkan kecepatan dan akurasi dengan membatasi pemurnian intensif sumber daya pada subset kandidat yang telah disaring.

Struktur data

Struktur data membentuk lapisan dasar indeks. Jenis yang umum termasuk:

• File Terbalik (Inverted File) (IVF)

  Jenis indeks seri IVF memungkinkan Milvus untuk mengelompokkan vektor ke dalam ember melalui partisi berbasis centroid. Secara umum dapat diasumsikan bahwa semua vektor dalam sebuah bucket cenderung dekat dengan vektor kueri jika centroid bucket dekat dengan vektor kueri. Berdasarkan premis ini, Milvus hanya memindai penyematan vektor dalam bucket yang centroidnya dekat dengan vektor kueri, daripada memeriksa seluruh dataset. Strategi ini mengurangi biaya komputasi sambil mempertahankan akurasi yang dapat diterima.

  Jenis struktur data indeks ini ideal untuk set data berskala besar yang membutuhkan throughput yang cepat.

• Struktur berbasis grafik

  Struktur data berbasis grafik untuk pencarian vektor, seperti Hierarchical Navigable Small World(HNSW), membuat grafik berlapis di mana setiap vektor terhubung ke tetangga terdekatnya. Kueri menavigasi hirarki ini, mulai dari lapisan atas yang kasar dan beralih melalui lapisan yang lebih rendah, sehingga memungkinkan kompleksitas pencarian logaritmik-waktu yang efisien.

  Jenis struktur data indeks ini unggul dalam ruang dimensi tinggi dan skenario yang menuntut kueri latensi rendah.

Kuantisasi

Kuantisasi mengurangi jejak memori dan biaya komputasi melalui representasi yang lebih kasar:

• Kuantisasi Skalar (misalnya SQ8) memungkinkan Milvus untuk memampatkan setiap dimensi vektor menjadi satu byte (8-bit), mengurangi penggunaan memori hingga 75% dibandingkan dengan float 32-bit sambil mempertahankan akurasi yang wajar.

• Product Quantization(PQ) memungkinkan Milvus untuk membagi vektor menjadi subvektor dan mengkodekannya menggunakan pengelompokan berbasis codebook. Hal ini menghasilkan rasio kompresi yang lebih tinggi (misalnya, 4-32x) dengan biaya pemanggilan yang sedikit berkurang, sehingga cocok untuk lingkungan dengan memori terbatas.

Pemurni

Kuantisasi pada dasarnya bersifat lossy. Untuk mempertahankan tingkat penarikan, kuantisasi secara konsisten menghasilkan lebih banyak kandidat top-K daripada yang diperlukan, memungkinkan refiner menggunakan presisi yang lebih tinggi untuk lebih memilih hasil top-K dari kandidat-kandidat ini, sehingga meningkatkan tingkat penarikan.

Sebagai contoh, refiner FP32 beroperasi pada kandidat hasil pencarian yang dikembalikan oleh kuantisasi dengan menghitung ulang jarak menggunakan presisi FP32 daripada nilai yang dikuantisasi.

Hal ini sangat penting untuk aplikasi yang membutuhkan pertukaran antara efisiensi pencarian dan presisi, seperti pencarian semantik atau sistem rekomendasi, di mana variasi jarak yang kecil secara signifikan berdampak pada kualitas hasil.

Ringkasan

Arsitektur berjenjang ini - pemfilteran kasar melalui struktur data, komputasi yang efisien melalui kuantisasi, dan penyetelan presisi melalui penyempurnaan - memungkinkan Milvus untuk mengoptimalkan pertukaran akurasi-kinerja secara adaptif.

Pengorbanan kinerja

Ketika mengevaluasi performa, sangat penting untuk menyeimbangkan waktu pembuatan, kueri per detik (QPS), dan tingkat penarikan. Aturan umumnya adalah sebagai berikut:

• Jenis indeks berbasis grafik biasanya mengungguli varian IVF dalam hal QPS.

• Varian IVF sangat cocok untuk skenario dengan topK yang besar (misalnya, lebih dari 2.000).

• PQ biasanya menawarkan tingkat recall yang lebih baik pada tingkat kompresi yang sama jika dibandingkan dengan SQ, meskipun SQ memberikan kinerja yang lebih cepat.

• Menggunakan hard drive untuk sebagian indeks (seperti pada DiskANN) membantu mengelola kumpulan data yang besar, tetapi juga menimbulkan potensi kemacetan IOPS.

Kapasitas

Kapasitas biasanya melibatkan hubungan antara ukuran data dan RAM yang tersedia. Ketika berurusan dengan kapasitas, pertimbangkan hal berikut:

• Jika seperempat dari data mentah Anda muat dalam memori, pertimbangkan DiskANN untuk latensi yang stabil.

• Jika semua data mentah Anda muat ke dalam memori, pertimbangkan jenis indeks berbasis memori dan mmap.

• Anda dapat menggunakan jenis indeks yang menerapkan kuantisasi dan mmap untuk menukar akurasi dengan kapasitas maksimum.

Pemanggilan kembali

Pemanggilan kembali biasanya melibatkan rasio filter, yang mengacu pada data yang disaring sebelum pencarian. Ketika berurusan dengan pemanggilan, pertimbangkan hal berikut:

• Jika rasio filter kurang dari 85%, jenis indeks berbasis grafik mengungguli varian IVF.

• Jika rasio filter antara 85% dan 95%, gunakan varian IVF.

• Jika rasio filter lebih dari 98%, gunakan Brute-Force (FLAT) untuk hasil pencarian yang paling akurat.

Kinerja

Performa pencarian biasanya melibatkan K teratas, yang mengacu pada jumlah rekaman yang dikembalikan oleh pencarian. Ketika berurusan dengan kinerja, pertimbangkan hal berikut:

• Untuk pencarian dengan top-K kecil (misalnya, 2.000) yang membutuhkan tingkat penarikan yang tinggi, jenis indeks berbasis grafik mengungguli varian IVF.

• Untuk pencarian dengan top-K yang besar (dibandingkan dengan jumlah total sematan vektor), varian IVF adalah pilihan yang lebih baik daripada jenis indeks berbasis grafik.

• Untuk pencarian dengan top-K berukuran sedang dan rasio filter yang tinggi, varian IVF adalah pilihan yang lebih baik.

Matriks Keputusan: Memilih jenis indeks yang paling tepat

Tabel berikut ini adalah matriks keputusan yang dapat Anda jadikan acuan saat memilih jenis indeks yang sesuai.

Skenario	Indeks yang Direkomendasikan	Catatan
Data mentah muat dalam memori	HNSW, IVF + Penghalusan	Gunakan HNSW untuk penarikan rendah-k/tinggi.
Data mentah pada disk, SSD	DiskANN	Optimal untuk kueri yang peka terhadap latensi.
Data mentah pada disk, RAM terbatas	IVFPQ/SQ + mmap	Menyeimbangkan memori dan akses disk.
Rasio filter tinggi (>95%)	Brute-Force (FLAT)	Menghindari overhead indeks untuk set kandidat yang kecil.
Besar k (≥1% dari set data)	IVF	Pemangkasan klaster mengurangi komputasi.
Tingkat penarikan yang sangat tinggi (>99%)	Brute-Force (FLAT) + GPU	--

Estimasi penggunaan memori

Konsumsi memori indeks dipengaruhi oleh struktur data, tingkat kompresi melalui kuantisasi, dan refiner yang digunakan. Secara umum, indeks berbasis grafik biasanya memiliki jejak memori yang lebih tinggi karena struktur grafik (misalnya, HNSW), yang biasanya mengimplikasikan overhead ruang per vektor yang nyata. Sebaliknya, IVF dan variannya lebih hemat memori karena overhead ruang per vektor lebih sedikit. Namun, teknik canggih seperti DiskANN memungkinkan bagian dari indeks, seperti grafik atau refiner, berada di disk, sehingga mengurangi beban memori sambil mempertahankan kinerja.

Secara khusus, penggunaan memori indeks dapat dihitung sebagai berikut:

Penggunaan memori indeks IVF

Indeks IVF menyeimbangkan efisiensi memori dengan kinerja pencarian dengan mempartisi data ke dalam cluster. Di bawah ini adalah rincian memori yang digunakan oleh 1 juta vektor 128 dimensi yang diindeks menggunakan varian IVF.

1. Hitung memori yang digunakan oleh centroid.

   Jenis indeks seri IVF memungkinkan Milvus untuk mengelompokkan vektor ke dalam ember menggunakan partisi berbasis centroid. Setiap centroid disertakan dalam indeks dalam penyematan vektor mentah. Ketika Anda membagi vektor menjadi 2.000 cluster, penggunaan memori dapat dihitung sebagai berikut:

   2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB
   

2. Hitung memori yang digunakan oleh penugasan cluster.

   Setiap penyematan vektor ditugaskan ke sebuah klaster dan disimpan sebagai ID bilangan bulat. Untuk 2.000 cluster, bilangan bulat 2-byte sudah cukup. Penggunaan memori dapat dihitung sebagai berikut:

   1,000,000 vectors × 2 bytes = 2.0 MB
   

3. Hitung kompresi yang disebabkan oleh kuantisasi.

   Varian IVF biasanya menggunakan PQ dan SQ8, dan penggunaan memori dapat diperkirakan sebagai berikut:

   • Menggunakan PQ dengan 8 subkuantisasi

     1,000,000 vectors × 8 bytes = 8.0 MB
     

   • Menggunakan SQ8

     1,000,000 vectors × 128 dimensions × 1 byte = 128 MB 
     

   Tabel berikut mencantumkan perkiraan penggunaan memori dengan konfigurasi yang berbeda:

   Konfigurasi	Estimasi Memori	Total Memori
   IVF-PQ (tanpa perbaikan)	1,0 MB + 2,0 MB + 8,0 MB	11,0 MB
   IVF-PQ + 10% perbaikan mentah	1,0 MB + 2,0 MB + 8,0 MB + 51,2 MB	62,2 MB
   IVF-SQ8 (tanpa perbaikan)	1,0 MB + 2,0 MB + 128 MB	131,0 MB
   IVF-FLAT (vektor mentah penuh)	1,0 MB + 2,0 MB + 512 MB	515,0 MB

4. Hitung biaya tambahan perbaikan.

   Varian IVF sering kali dipasangkan dengan pemurni untuk memeringkat ulang kandidat. Untuk pencarian yang mengambil 10 hasil teratas dengan tingkat ekspansi 5, overhead perbaikan dapat diperkirakan sebagai berikut:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Penggunaan memori indeks berbasis grafik

Jenis indeks berbasis grafik seperti HNSW membutuhkan memori yang signifikan untuk menyimpan struktur grafik dan penyematan vektor mentah. Di bawah ini adalah rincian memori yang dikonsumsi oleh 1 juta vektor 128 dimensi yang diindeks menggunakan jenis indeks HNSW.

1. Hitung memori yang digunakan oleh struktur graf.

   Setiap vektor dalam HNSW mempertahankan koneksi ke tetangganya. Dengan derajat graf (sisi per simpul) sebesar 32, memori yang digunakan dapat dihitung sebagai berikut:

   1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB  
   

2. Hitung memori yang digunakan oleh penyematan vektor mentah.

   Memori yang digunakan untuk menyimpan vektor FP32 yang tidak dikompresi dapat dihitung sebagai berikut:

   1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB  
   

   Bila Anda menggunakan HNSW untuk mengindeks 1 juta embedding vektor 128 dimensi, total memori yang digunakan adalah 128 MB (grafik) + 512 MB (vektor) = 640 MB.

3. Hitung kompresi yang disebabkan oleh kuantisasi.

   Kuantisasi mengurangi ukuran vektor. Sebagai contoh, menggunakan PQ dengan 8 subkuantisasi (8 byte per vektor) menyebabkan kompresi yang drastis. Memori yang dikonsumsi oleh penyematan vektor yang dikompresi dapat dihitung sebagai berikut:

   1,000,000 vectors × 8 bytes = 8 MB
   

   Ini mencapai tingkat kompresi 64 kali lipat jika dibandingkan dengan embedding vektor mentah, dan total memori yang digunakan oleh jenis indeks HNSWPQ adalah 128 MB (grafik) + 8 MB (vektor terkompresi) = 136 MB.

4. Hitung biaya overhead penyempurnaan.

   Refinement, seperti pemeringkatan ulang dengan vektor mentah, untuk sementara memuat data presisi tinggi ke dalam memori. Untuk pencarian yang mengambil 10 hasil teratas dengan tingkat ekspansi 5, overhead refinement dapat diperkirakan sebagai berikut:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Pertimbangan lain

Sementara IVF dan indeks berbasis grafik mengoptimalkan penggunaan memori melalui kuantisasi, file yang dipetakan dengan memori (mmap), dan skenario alamat DiskANN di mana kumpulan data melebihi memori akses acak (RAM) yang tersedia.

DiskANN

DiskANN adalah indeks berbasis grafik Vamana yang menghubungkan titik-titik data untuk navigasi yang efisien selama pencarian sambil menerapkan PQ untuk mengurangi ukuran vektor dan memungkinkan penghitungan jarak perkiraan yang cepat antar vektor.

Grafik Vamana disimpan di disk, yang memungkinkan DiskANN untuk menangani kumpulan data besar yang jika tidak, akan terlalu besar untuk ditampung di memori. Hal ini sangat berguna untuk kumpulan data miliaran titik.

File yang dipetakan dengan memori (mmap)

Pemetaan memori (Mmap) memungkinkan akses memori langsung ke file besar pada disk, memungkinkan Milvus untuk menyimpan indeks dan data dalam memori dan hard drive. Pendekatan ini membantu mengoptimalkan operasi I/O dengan mengurangi overhead panggilan I/O berdasarkan frekuensi akses, sehingga memperluas kapasitas penyimpanan untuk koleksi tanpa memengaruhi kinerja pencarian secara signifikan.

Secara khusus, Anda dapat mengonfigurasi Milvus untuk memetakan memori data mentah dalam bidang tertentu alih-alih memuatnya secara penuh ke dalam memori. Dengan cara ini, Anda dapat memperoleh akses memori langsung ke bidang-bidang tersebut tanpa mengkhawatirkan masalah memori dan memperluas kapasitas koleksi.