Bitset

Topik ini memperkenalkan mekanisme bitset yang membantu mengaktifkan fungsi-fungsi utama seperti pemfilteran atribut dan operasi hapus di Milvus.

Gambaran Umum

Bitset adalah sekumpulan bit. Bit adalah elemen dengan hanya dua nilai yang mungkin, biasanya 0 dan 1, atau nilai boolean true dan false. Dalam Milvus, bitset adalah array dari angka bit 0 dan 1 yang dapat digunakan untuk merepresentasikan data tertentu secara ringkas dan efisien dibandingkan dengan ints, float, atau char. Nomor bit adalah 0 secara default dan hanya diatur ke 1 jika memenuhi persyaratan tertentu.

Operasi pada bit-bit dilakukan dengan logika boolean, di mana nilai keluarannya valid atau tidak valid, yang juga dilambangkan dengan 1 dan 0. Sebagai contoh, operator logika AND dapat digunakan untuk membandingkan dua bitset berdasarkan item pada posisi indeks yang sama dan menghasilkan bitset baru dengan hasilnya. Jika dua item dalam sebuah posisi adalah sama, maka dalam bitset baru 1 akan dituliskan pada posisi tersebut; 0 jika berbeda.

Implementasi

Bitset adalah mekanisme yang sederhana namun kuat yang membantu Milvus melakukan pemfilteran atribut, penghapusan data, dan kueri dengan Time Travel.

Pemfilteran atribut

Karena bitset hanya berisi dua nilai yang mungkin, maka bitset sangat cocok untuk menyimpan hasil penyaringan atribut. Data yang memenuhi persyaratan filter atribut yang diberikan ditandai dengan 1.

Penghapusan data

Bitset berfungsi sebagai cara yang ringkas untuk menyimpan informasi tentang apakah sebuah baris dalam segmen telah dihapus. Entitas yang dihapus ditandai dengan 1 dalam bitset yang sesuai, yang tidak akan dikomputasi selama pencarian atau kueri.

Contoh

Di sini kami menyajikan tiga contoh yang mengilustrasikan bagaimana bitset digunakan di Milvus, dengan referensi ke ketiga implementasi utama bitset yang telah dibahas di atas. Pada ketiga kasus tersebut, terdapat sebuah segmen dengan 8 entitas dan kemudian serangkaian peristiwa bahasa manipulasi data (DML) terjadi dengan urutan seperti yang ditunjukkan di bawah ini.

• Empat dari entitas, yang primary_keynya masing-masing adalah [1, 2, 3, 4], disisipkan ketika cap waktu ts sama dengan 100.
• Empat entitas lainnya, yang primary_keynya adalah [5, 6, 7, 8], disisipkan ketika timestamp ts sama dengan 200.
• Entitas yang primary_key-nya [7, 8] dihapus ketika timestamp ts sama dengan 300.
• Hanya entitas yang primary_keynya [1, 3, 5, 7] yang memenuhi syarat pemfilteran atribut.

Urutan peristiwa DML

Kasus pertama

Dalam kasus ini, seorang pengguna menetapkan time_travel sebagai 150, yang berarti bahwa pengguna melakukan kueri pada data yang memenuhi ts = 150. Proses pembangkitan bitset diilustrasikan oleh Gambar 1.

Pada tahap penyaringan awal, filter_bitset seharusnya adalah [1, 0, 1, 0, 1, 0, 1, 0], di mana entitas [1, 3, 5, 7] ditandai sebagai 1 karena merupakan hasil penyaringan yang valid.

Namun, entitas [4, 5, 6, 7] tidak dimasukkan ke dalam basis data vektor ketika ts sama dengan 150. Oleh karena itu, keempat entitas ini harus ditandai sebagai 0 terlepas dari kondisi pemfilteran. Sekarang hasil bitset seharusnya menjadi [1, 0, 1, 0, 0, 0, 0, 0].

Seperti yang telah dibahas di Penghapusan data, entitas yang ditandai dengan 1 akan diabaikan selama pencarian atau kueri. Hasil bitset sekarang perlu dibalik agar dapat digabungkan dengan bitmap penghapusan, yang memberi kita [0, 1, 0, 1, 1, 1, 1, 1].

Sedangkan untuk bitmap penghapusan del_bitset, nilai awal seharusnya adalah [0, 0, 0, 0, 0, 0, 1, 1]. Namun, entitas 7 dan 8 tidak akan dihapus sampai ts bernilai 300. Oleh karena itu, ketika ts bernilai 150, entitas 7 dan 8 masih valid. Hasilnya, nilai del_bitset setelah Perjalanan Waktu adalah [0, 0, 0, 0, 0, 0, 0, 0].

Sekarang kita memiliki dua bitset setelah Perjalanan Waktu dan pemfilteran atribut: filter_bitset [0, 1, 0, 1, 1, 1, 1, 1] dan del_bitset [0, 0, 0, 0, 0, 0, 0, 0] . Gabungkan kedua bitset ini dengan operator logika biner OR. Nilai akhir dari result_bitset adalah [0, 1, 0, 1, 1, 1, 1, 1], yang berarti hanya entitas 1 dan 3 yang akan dikomputasi pada tahap pencarian atau kueri berikutnya.

Gambar 1. Pencarian dengan Time Travel = 150.

Kasus kedua

Pada kasus ini, pengguna menetapkan time_travel sebagai 250. Proses pembangkitan bitset diilustrasikan oleh Gambar 2.

Seperti pada kasus pertama, filter_bitset awal adalah [1, 0, 1, 0, 1, 0, 1, 0].

Semua entitas ada di dalam basis data vektor ketika ts = 250. Oleh karena itu, filter_bitset tetap sama ketika kita memperhitungkan cap waktu. Sekali lagi, kita perlu membalik hasilnya dan mendapatkan [0, 1, 0, 1, 0, 1, 0, 1].

Sedangkan untuk penghapusan bitset del_bitset, nilai awalnya adalah [0, 0, 0, 0, 0, 0, 1, 1]. Namun, entitas 7 dan 8 tidak dihapus sampai ts bernilai 300. Oleh karena itu, ketika ts bernilai 250, entitas 7 dan 8 masih valid. Hasilnya, del_bitset setelah Perjalanan Waktu adalah [0, 0, 0, 0, 0, 0, 0, 0].

Sekarang kita memiliki dua bitset setelah Perjalanan Waktu dan pemfilteran atribut: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] dan del_bitset [0, 0, 0, 0, 0, 0, 0, 0] . Gabungkan kedua bitset ini dengan operator logika biner OR. Hasil_bitset adalah [0, 1, 0, 1, 0, 1, 0, 1]. Dengan kata lain, hanya entit [1, 3, 5, 7] yang akan dikomputasi pada tahap pencarian atau kueri berikutnya.

Gambar 2. Pencarian dengan Time Travel = 250.

Kasus tiga

Pada kasus ini, pengguna menetapkan time_travel sebagai 350. Proses pembangkitan bitset diilustrasikan oleh Gambar 3.

Seperti kasus-kasus sebelumnya, filter_bitset awal adalah [0, 1, 0, 1, 0, 1, 0, 1].

Semua entitas ada di dalam basis data vektor ketika ts= 350. Oleh karena itu, filter_bitset akhir yang telah dibalik adalah [0, 1, 0, 1, 0, 1, 0, 1], sama seperti pada kasus kedua.

Sedangkan untuk bitset penghapusan del_bitset, karena entitas 7 dan 8 telah dihapus ketika ts = 350, oleh karena itu, hasil dari del_bitset adalah [0, 0, 0, 0, 0, 0, 1, 1].

Sekarang kita memiliki dua bitset setelah Perjalanan Waktu dan pemfilteran atribut: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] dan del_bitset [0, 0, 0, 0, 0, 0, 1, 1] . Gabungkan kedua bitset ini dengan operator logika biner OR. result_bitset yang terakhir adalah [0, 1, 0, 1, 0, 1, 1, 1]. Dengan kata lain, hanya entitas [1, 3, 5] yang akan dikomputasi pada tahap pencarian atau kueri berikut ini.

Gambar 3. Pencarian dengan Perjalanan Waktu = 350.

Apa yang selanjutnya

Sekarang Anda sudah mengetahui bagaimana cara kerja bitset di Milvus, Anda mungkin juga ingin melakukannya:

• Mempelajari cara menggunakan string untuk memfilter hasil pencarian Anda, atau lihat Pencarian Hibrida di dokumen kami.
• Memahami bagaimana data diproses di Milvus.