Bagaimana Basis Data Memahami dan Menjalankan Kueri Anda?
Gambar sampul depan
Artikel ini diterjemahkan oleh Angela Ni.
Kueri vektor di Milvus adalah proses pengambilan vektor melalui pemfilteran skalar berdasarkan ekspresi boolean. Dengan pemfilteran skalar, pengguna dapat membatasi hasil kueri mereka dengan kondisi tertentu yang diterapkan pada atribut data. Sebagai contoh, jika pengguna mencari film yang dirilis pada tahun 1990-2010 dan memiliki skor lebih tinggi dari 8.5, maka hanya film yang memiliki atribut (tahun rilis dan skor) yang memenuhi syarat.
Tulisan ini bertujuan untuk melihat bagaimana sebuah kueri diselesaikan di Milvus mulai dari input ekspresi kueri hingga pembuatan rencana kueri dan eksekusi kueri.
Langsung ke:
Ekspresi kueri
Ekspresi kueri dengan pemfilteran atribut di Milvus mengadopsi sintaks EBNF (Extended Backus-Naur form). Gambar di bawah ini adalah aturan ekspresi di Milvus.
Sintaks Ekspresi
Ekspresi logika dapat dibuat dengan menggunakan kombinasi operator logika biner, operator logika unary, ekspresi logika, dan ekspresi tunggal. Karena sintaks EBNF itu sendiri bersifat rekursif, sebuah ekspresi logis dapat merupakan hasil kombinasi atau bagian dari ekspresi logis yang lebih besar. Ekspresi logika dapat berisi banyak ekspresi sub-logika. Aturan yang sama berlaku di Milvus. Jika pengguna perlu memfilter atribut dari hasil dengan banyak kondisi, pengguna dapat membuat set kondisi pemfilteran sendiri dengan mengkombinasikan operator dan ekspresi logika yang berbeda.
Ekspresi Boolean
Gambar di atas menunjukkan bagian dari aturan ekspresi Boolean di Milvus. Operator logika unary dapat ditambahkan ke sebuah ekspresi. Saat ini Milvus hanya mendukung operator logika unary "not", yang mengindikasikan bahwa sistem perlu mengambil vektor-vektor yang nilai medan skalarnya tidak memenuhi hasil perhitungan. Operator logika biner termasuk "dan" dan "atau". Ekspresi tunggal termasuk ekspresi istilah dan ekspresi perbandingan.
Perhitungan aritmatika dasar seperti penjumlahan, pengurangan, perkalian, dan pembagian juga didukung selama kueri di Milvus. Gambar berikut ini menunjukkan urutan operasi. Operator didaftar dari atas ke bawah dalam urutan prioritas.
Prioritas
Bagaimana ekspresi kueri pada film tertentu diproses di Milvus?
Misalkan ada banyak sekali data film yang tersimpan di Milvus dan pengguna ingin menanyakan film tertentu. Sebagai contoh, setiap data film yang disimpan di Milvus memiliki lima bidang berikut: ID film, tahun rilis, jenis film, skor, dan poster. Dalam contoh ini, tipe data dari ID film dan tahun rilis adalah int64, sedangkan skor film adalah data float point. Selain itu, poster film disimpan dalam format vektor float-point, dan tipe film dalam format data string. Khususnya, dukungan untuk tipe data string adalah fitur baru dalam Milvus 2.1.
Sebagai contoh, jika pengguna ingin meminta film dengan skor lebih tinggi dari 8,5. Film-film tersebut juga harus dirilis selama satu dekade sebelum tahun 2000 hingga satu dekade setelah tahun 2000 atau jenis filmnya adalah film komedi atau film aksi, pengguna harus memasukkan ekspresi predikat berikut ini: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action])
.
Setelah menerima ekspresi kueri, sistem akan menjalankannya dengan urutan sebagai berikut:
- Kueri untuk film dengan skor lebih tinggi dari 8,5. Hasil kueri disebut "hasil1".
- Hitung 2000 - 10 untuk mendapatkan "result2" (1990).
- Hitung 2000 + 10 untuk mendapatkan "result3" (2010).
- Kueri untuk film dengan nilai
release_year
lebih besar dari "result2" dan lebih kecil dari "result3". Dengan kata lain, sistem perlu melakukan kueri untuk film yang dirilis antara tahun 1990 dan 2010. Hasil kueri disebut "result4". - Kueri untuk film yang merupakan film komedi atau film aksi. Hasil kueri disebut "result5".
- Kombinasikan "result4" dan "result5" untuk mendapatkan film yang dirilis antara tahun 1990 dan 2010 atau termasuk dalam kategori film komedi atau aksi. Hasilnya disebut "result6".
- Ambil bagian yang sama dari "result1" dan "result6" untuk mendapatkan hasil akhir yang memenuhi semua persyaratan.
Contoh film
Rencanakan pembuatan AST
Milvus memanfaatkan alat sumber terbuka ANTLR (ANother Tool for Language Recognition) untuk membuat rencana AST (pohon sintaksis abstrak). ANTLR adalah generator pengurai yang kuat untuk membaca, memproses, mengeksekusi, atau menerjemahkan struktur teks atau file biner. Lebih khusus lagi, ANTLR dapat menghasilkan parser untuk membangun dan menjalankan pohon parsing berdasarkan sintaks atau aturan yang telah ditentukan sebelumnya. Gambar berikut ini adalah contoh di mana ekspresi masukannya adalah "SP=100;". LEXER, fungsionalitas pengenalan bahasa bawaan dalam ANTLR, menghasilkan empat token untuk ekspresi input - "SP", "=", "100", dan ";". Kemudian alat ini akan mem-parsing keempat token tersebut untuk menghasilkan pohon parsing yang sesuai.
pohon penguraian
Mekanisme walker adalah bagian yang sangat penting dalam alat ANTLR. Ini dirancang untuk berjalan melalui semua pohon parsing untuk memeriksa apakah setiap node mematuhi aturan sintaks, atau untuk mendeteksi kata-kata sensitif tertentu. Beberapa API yang relevan tercantum dalam gambar di bawah ini. Karena ANTLR dimulai dari simpul akar dan turun melalui setiap sub-simpul hingga ke bawah, maka tidak perlu membedakan urutan cara menelusuri pohon parsing.
pejalan pohon parsing
Milvus menghasilkan PlanAST untuk kueri dengan cara yang mirip dengan ANTLR. Namun, menggunakan ANTLR membutuhkan pendefinisian ulang aturan sintaks yang agak rumit. Oleh karena itu, Milvus mengadopsi salah satu aturan yang paling umum - aturan ekspresi Boolean, dan bergantung pada paket Expr yang bersumber terbuka di GitHub untuk melakukan kueri dan mengurai sintaks ekspresi kueri.
Selama kueri dengan pemfilteran atribut, Milvus akan menghasilkan pohon rencana primitif yang belum terpecahkan menggunakan pengurai semut, metode penguraian yang disediakan oleh Expr, setelah menerima ekspresi kueri. Pohon rencana primitif yang akan kita dapatkan adalah pohon biner sederhana. Kemudian pohon rencana tersebut akan di-tuning oleh Expr dan pengoptimal bawaan di Milvus. Pengoptimal di Milvus sangat mirip dengan mekanisme walker yang telah disebutkan sebelumnya. Karena fungsionalitas pengoptimalan pohon rencana yang disediakan oleh Expr cukup canggih, beban pengoptimal bawaan Milvus sangat diringankan. Pada akhirnya, penganalisis menganalisis pohon rencana yang dioptimalkan dengan cara rekursif untuk menghasilkan AST rencana dalam struktur penyangga protokol (protobuf).
merencanakan alur kerja AST
Eksekusi kueri
Eksekusi kueri pada dasarnya adalah eksekusi plan AST yang dihasilkan pada langkah sebelumnya.
Dalam Milvus, plan AST didefinisikan dalam sebuah struktur protobuf. Gambar di bawah ini adalah pesan dengan struktur protobuf. Ada enam jenis ekspresi, di antaranya ekspresi biner dan ekspresi unary yang selanjutnya dapat memiliki ekspresi logika biner dan ekspresi logika unary.
protobuf1
protobuf2
Gambar di bawah ini adalah gambar UML dari ekspresi kueri. Gambar ini menunjukkan kelas dasar dan kelas turunan dari setiap ekspresi. Setiap kelas dilengkapi dengan metode untuk menerima parameter pengunjung. Ini adalah pola desain pengunjung yang khas. Milvus menggunakan pola ini untuk mengeksekusi rancangan AST karena keuntungan terbesarnya adalah pengguna tidak perlu melakukan apa pun pada ekspresi primitif tetapi dapat secara langsung mengakses salah satu metode dalam pola untuk memodifikasi kelas ekspresi kueri tertentu dan elemen-elemen yang relevan.
UML
Ketika mengeksekusi sebuah plan AST, Milvus pertama-tama menerima sebuah node plan tipe proto. Kemudian node rencana tipe segcore diperoleh melalui proto parser C++ internal. Setelah mendapatkan dua jenis node rencana, Milvus menerima serangkaian akses kelas dan kemudian memodifikasi dan mengeksekusi dalam struktur internal node rencana. Terakhir, Milvus mencari semua node rencana eksekusi untuk mendapatkan hasil yang disaring. Hasil akhirnya adalah keluaran dalam format bitmask. Bitmask adalah sebuah larik angka bit ("0" dan "1"). Data yang memenuhi persyaratan filter ditandai sebagai "1" dalam bitmask, sedangkan yang tidak memenuhi persyaratan ditandai sebagai "0" dalam bitmask.
jalankan alur kerja
Tentang Seri Deep Dive
Dengan pengumuman resmi ketersediaan umum Milvus 2.0, kami menyusun seri blog Milvus Deep Dive ini untuk memberikan interpretasi mendalam tentang arsitektur dan kode sumber Milvus. Topik-topik yang dibahas dalam seri blog ini meliputi:
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word