Ekstensi pencarian vektor baru untuk SQLite, sqlite-vec, sedang dikembangkan

 (alexgarcia.xyz)
3 poin oleh GN⁺ 2024-05-04 | 1 komentar | Bagikan ke WhatsApp
  • Untuk mengurangi keterbatasan sqlite-vss yang ada, sqlite-vec sedang dikembangkan sebagai ekstensi pencarian vektor tertanam berbasis C murni, dengan target seluruh lingkungan tempat SQLite berjalan
  • Alur penggunaan SQL disederhanakan dengan berpusat pada CREATE VIRTUAL TABLE, INSERT INTO, dan SELECT, serta mendukung pencarian gaya KNN dan input vektor JSON maupun compact binary
  • Dengan menghapus dependensi Faiss, proyek ini menargetkan bukan hanya Linux dan macOS, tetapi juga Windows, WebAssembly, perangkat mobile, hingga Raspberry Pi; ukuran biner juga diharapkan berada di kisaran ratusan KB, lebih kecil dari 3MB~5MB sebelumnya
  • Vektor disimpan dalam unit chunk pada shadow table sehingga mengurangi kebutuhan memuat semuanya ke RAM, dan PRAGMA mmap_size dapat digunakan untuk meningkatkan kecepatan pencarian berbasis memori
  • Versi awal hanya menyediakan exhaustive full-scan dan belum menyertakan ANN; rilis v0.1.0 direncanakan setelah 246 TODO di sqlite-vec.c selesai

Pencarian vektor SQLite yang ingin diubah oleh sqlite-vec

  • sqlite-vec adalah ekstensi SQLite baru yang ditulis dalam C murni, dan merupakan proyek yang bertujuan menggantikan sqlite-vss yang dirilis pada Februari 2023
  • Cakupan tujuannya mencakup fungsi SQL kustom untuk pencarian vektor cepat, virtual table, serta alat dan utilitas untuk operasi vektor
    • Kuantisasi
    • Konversi JSON/BLOB/numpy
    • Aritmetika vektor
  • Pengguna dapat membuat dan mencari penyimpanan vektor hanya dengan SQL murni
    • Membuat virtual table untuk vektor dengan CREATE VIRTUAL TABLE
    • Menyisipkan vektor dengan INSERT INTO
    • Pencarian gaya KNN dalam bentuk SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ...
  • Input vektor dapat menggunakan string JSON atau format compact binary

C murni dan tanpa dependensi membuka lingkungan eksekusi yang lebih luas

  • sqlite-vec menargetkan ekstensi C murni tanpa dependensi, dan pilihan ini menjadi syarat utama untuk memperluas platform yang didukung
  • sqlite-vss yang ada sebelumnya hanya berjalan stabil di Linux dan macOS karena dependensi C++, dan ukuran binernya berada di kisaran 3MB~5MB
  • Ekstensi baru ini menargetkan agar dapat berjalan di lingkungan berikut
    • Linux
    • macOS
    • Windows
    • WebAssembly di browser
    • Perangkat mobile
    • Perangkat kecil seperti Raspberry Pi
  • Perkiraan ukuran biner berada di kisaran ratusan KB

Mengatur penggunaan memori dan kecepatan pencarian

  • sqlite-vec mengendalikan penggunaan memori dengan menyimpan vektor dalam chunk yang dibagi di dalam shadow table
    • Saat pencarian KNN, semua vektor tidak dimuat sekaligus ke RAM, melainkan dibaca per chunk
    • Seluruh vektor tidak harus tetap berada di memori
  • Jika membutuhkan kecepatan berbasis memori, PRAGMA mmap_size milik SQLite dapat digunakan untuk membuat pencarian KNN lebih cepat

Fitur vektor baru dan batasan awal

  • sqlite-vec berupaya mendukung fitur berikut dengan lebih baik, mencerminkan alat pencarian vektor terbaru dan arah riset saat ini
  • Fitur-fitur ini menjadi dasar untuk mengatur kecepatan, akurasi, dan penggunaan disk vektor dengan lebih rinci
  • sqlite-vec versi awal hanya mendukung pencarian vektor exhaustive full-scan
    • Opsi “approximate nearest neighbors” belum ada pada awalnya
    • IVF dan HNSW adalah fitur yang diharapkan dapat ditambahkan di masa mendatang

Konfigurasi demo browser

  • Demo menggunakan sqlite-vec yang berjalan di browser
  • Konfigurasi yang dapat dilihat di developer tools adalah sebagai berikut
    • sqlite3.wasm 5.9MB yang belum dioptimalkan
    • Build SQLite WASM resmi yang mengompilasi sqlite-vec
    • Database SQLite movies.bit.db berukuran 2.6MB
  • movies.bit.db berisi overview 4.800 film berbasis metadata film TMDB dalam tabel articles
  • Virtual table terpisah vec_movies adalah indeks vektor untuk embedding overview tersebut

Data demo dan alur pencarian KNN

  • Tabel articles memiliki kolom seperti title, release_date, dan overview
  • Kolom overview berisi sinopsis film dalam kalimat pendek, dan menjadi target embedding dalam demo
  • Virtual table vec_movies menyimpan embedding dari articles.overview di kolom overview_embeddings
    • Vektornya adalah binary vector 768 dimensi
    • Ukuran penyimpanannya adalah 768 / 8 = 96, yaitu 96 byte
  • Ketika pengguna memilih film melalui tombol radio, ID film yang dipilih akan mengisi parameter :selected_movie pada kueri SQL KNN
  • Hasil pencarian adalah 10 film yang paling dekat dengan film yang dipilih
    • Karena berupa binary vector, perhitungan jarak menggunakan hamming distance
    • Hasil terdekat selalu film yang sama, dengan jarak 0
  • Hasil embedding dari sinopsis singkat dan dataset film kecil ini bukan kualitas terbaik, dan binary quantization juga mengorbankan kualitas lebih jauh, tetapi fokusnya adalah menunjukkan pencarian vektor yang cepat dan “cukup baik” di dalam browser
  • Untuk memeriksa cara kerja internalnya, tambahkan EXPLAIN QUERY PLAN di depan SELECT; Anda dapat melihat “index” 0:knn yang digunakan oleh vec_movies

Keterbatasan sqlite-vss dan dependensi Faiss

  • Ada beberapa hambatan dalam pengembangan dan adopsi sqlite-vss
    • Hanya berjalan di Linux dan macOS, serta tidak mendukung Windows, WASM, perangkat mobile, dan lainnya
    • Semua vektor disimpan di dalam memori
    • Memiliki bug dan isu terkait transaksi
    • Sangat sulit dan lama untuk dikompilasi
    • Tidak memiliki operasi vektor umum seperti scalar/binary quantization
  • Hampir semua masalah ini berasal dari dependensi pada Faiss
  • Sebagian masalah mungkin dapat diselesaikan dengan banyak waktu dan upaya, tetapi banyak di antaranya bisa terhambat oleh Faiss
  • Solusi low-level tanpa dependensi menjadi pilihan yang menarik, dan sqlite-vec dimulai dari penilaian bahwa pencarian vektor itu sendiri tidak terlalu rumit

Status rilis dan permintaan sponsor

  • Fitur inti sqlite-vec sudah berjalan, tetapi penanganan error dan pengujian masih sangat kurang
  • File sqlite-vec.c masih memiliki 246 TODO
    • 191 todo_assert()
    • 41 komentar // TODO
    • 14 todo panic
    • Progres keseluruhan ditampilkan sebagai 0/246, 0% untuk sqlite-vec v0
  • Setelah 246 TODO selesai, rilis pertama v0.1.0 direncanakan akan keluar
    • Dokumentasi
    • Demo
    • Binding
    • Komponen lainnya akan disediakan bersama
  • Target waktunya sekitar satu bulan, tetapi bukan jadwal yang sudah pasti
  • Mereka sedang mencari sponsor dari perusahaan yang tertarik pada keberhasilan sqlite-vec, dan dapat dihubungi melalui email

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-04
Pendapat di Hacker News

  • Saya penulisnya — kalau ada pertanyaan, akan saya jawab. Ini lebih bersifat “sedang mengerjakan proyek baru” daripada rilis resmi, dan ekstensinya sendiri juga masih dalam proses. Tautan proyeknya: https://github.com/asg017/sqlite-vec
    Saya punya gambaran yang cukup konkret tentang seperti apa v0.1.0 dari ekstensi ini nantinya, tetapi sepertinya masih butuh beberapa minggu lagi untuk sampai ke sana. Tulisan ini terutama bertujuan memberi tahu pengguna sqlite-vss, ekstensi pencarian vektor SQLite yang saya buat sebelumnya, tentang apa yang akan datang berikutnya, dan akan ada rilis yang lebih besar saat sudah siap
    Secara umum saya sangat antusias karena akan ada alternatif pencarian vektor yang mudah di-embed. Bagus terutama karena bisa berjalan di semua sistem operasi, WASM, perangkat mobile, Raspberry Pi, dan sebagainya; secara pribadi saya sedang mencoba menjalankan aplikasi kecil pencarian semantik di Beepy, jadi ini menyenangkan
    [0] https://beepy.sqfmi.com/

    • Saya penasaran fungsi jarak apa saja yang didukung. Sepertinya sudah mendukung vektor biner, jadi saya ingin tahu apakah jarak Hamming juga didukung
      Saya juga ingin tahu performanya dibanding sqlite-vss. Penasaran dengan angka profiling baik untuk kecepatan kueri maupun penggunaan memori
      Secara keseluruhan terlihat benar-benar bagus, dan saya suka arah ini
      Pendekatan bahwa sqlite-vec pada awalnya hanya mendukung pencarian vektor full scan menyeluruh tanpa opsi approximate nearest neighbor (ANN), tetapi nanti ingin menambahkan IVF dan HNSW, menurut saya 1000% tepat. Saya suka karena tidak dibuat terlalu rumit sejak awal
      Saya pernah merilis pencarian vektor on-device, dan dengan kombinasi vektor biner 128-bit serta jarak Hamming, bahkan untuk database berisi lebih dari 200 ribu item, pencarian jarak brute-force penuh masih cukup cepat untuk dijalankan di setiap frame kamera. Di ponsel murah pun bisa lebih dari 10fps, dan di ponsel bagus terasa sangat mulus. Mengejutkan betapa seringnya brute force sudah cukup
      Namun saat mengimplementasikan algoritma ANN seperti HNSW, akan keren kalau bisa ditangani dengan paradigma indeks tabel. Dengan begitu, beralih dari pencarian brute-force ke ANN menjadi sesederhana membuat indeks pada tabel, dan eksperimen dengan berbagai algoritma ANN serta parameternya juga bisa dilakukan dengan menyesuaikan parameter pembuatan indeks. Mungkin memang sudah mengarah ke sana, tetapi saya sebutkan untuk berjaga-jaga
    • Saya penasaran apakah ada rencana mengimplementasikan strategi pengindeksan seperti HNSW. Linear scan jelas bagus sebagai titik awal, dan jika datanya tersusun dalam urutan yang masuk akal dan misalnya kurang dari 10MB, itu bisa cukup cepat, jadi rasanya bukan alasan untuk menunda rilis beta
      Saya juga penasaran apakah ini dibangun bersama sqlite-httpvfs. Sepertinya cocok dengan proyek ini: https://github.com/phiresky/sql.js-httpvfs
    • Senang sekali melihat adanya Wasm. Biasanya sulit memakai pencarian vektor di dalam SQLite dari browser
      Saya penasaran apakah Anda mempertimbangkan membuatnya kompatibel secara sintaks dengan pgvector demi DSL vektor SQL yang umum. Saya menduga kekurangannya tidak jauh lebih kecil daripada kelebihannya, tetapi penasaran apakah memungkinkan
    • Bisakah ini diimplementasikan dengan Rust? Saya juga penasaran apakah proyek sqlite-loadable-rs mendukung WASM
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • Dulu saya menambahkan sqlite-vss ke Langchain sebagai penyimpanan vektor. Apakah proyek baru ini menurut Anda sudah cukup matang untuk ditambahkan ke Langchain juga, atau sebaiknya menunggu sedikit lagi?
      sqlite-vss sudah digunakan dengan baik di beberapa proyek

  • Bagian “vektor biner 768 dimensi sehingga memakan 96 byte (768 / 8 = 96)” membingungkan. Menurut saya, kutukan dimensionalitas, masalah yang dialami sebagian besar vector store, justru ada pada bagian seperti ini, dan itu masalah sebelum pengindeksan
    Saya sempat mengira maksudnya mungkin 768 dimensi * 8 byte (f64), jadi 6144 byte. Biasanya orang menerima sedikit loss lalu menurunkannya ke f32 atau f16, atau representasi yang lebih kecil
    Kalau ada cara memasukkan 768 dimensi ke dalam 96 byte lewat kompresi atau amortisasi semacam trie, saya ingin mendengarnya dalam tulisan terpisah. Kalau setiap dimensi diperlakukan sebagai 1 bit, saya mengerti, tetapi saya masih punya pertanyaan soal kualitas pencariannya

    • Saya penulisnya — di sini vektor biner berarti setiap dimensi dikuantisasi menjadi 1 bit. Biasanya dibutuhkan 4 * jumlah dimensi byte per vektor. Di sini 4 adalah sizeof(float)
      Sebagian model embedding, seperti nomic v1.5[0] atau model baru dari mixedbread[1], dilatih secara khusus agar kualitasnya tetap terjaga setelah kuantisasi biner. Tidak semua model seperti itu, jadi hasilnya bisa berbeda. Secara umum, pada vektor yang sangat besar seperti model embedding besar 3072 dimensi milik OpenAI, tampaknya ini cukup bekerja meskipun tidak dilatih khusus untuk tujuan tersebut
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • Biner berarti setiap dimensi dikuantisasi menjadi +1 atau -1
      Jika memakai indeks FAISS pada data dan menerapkan Product Quantization, untuk fitur biner Anda bisa mencoba vektor biner dengan cara seperti PQ768x1, dan juga membandingkan metode seperti menguantisasi setiap pasangan vektor menjadi salah satu dari empat nilai: https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • Sebagai catatan, kutukan dimensionalitas secara tepat berarti ruang berdimensi tinggi menjadi relatif jarang, dan untuk mengisi ruang tersebut data harus bertambah secara eksponensial. Ini tidak berkaitan dengan kapasitas penyimpanan
      Biasanya dalam database vektor, data dikompresi atau diproyeksikan ke ruang berdimensi lebih rendah sebelum disimpan, sehingga situasi ini justru membaik

  • Berkat sqlite-vss, saya bisa mempelajari bagaimana RAG bekerja dan mengimplementasikannya dalam proyek mainan. Debugging-nya agak sulit, tetapi kalau sudah pas, ia berjalan mulus di Ubuntu, dan saya masih menggunakannya
    Senang mendengar ada versi baru yang lebih baik tanpa dependensi yang terbatas

  • Penasaran apakah rencananya hanya akan menggunakan SQLite API publik, atau membayangkan bentuk yang ditempelkan ke SQLite amalgamation
    Saya jelas tertarik dengan fitur seperti ini, tetapi harus memikirkan bagaimana mendistribusikannya terpisah dari SQLite di binding Go berbasis Wasm. Sejauh ini kami membundel semua kode C karena jauh lebih sederhana daripada “dynamic linking” Wasm
    Selain itu, Anda menyebutkan I/O BLOB inkremental, dan mungkin sudah tahu, tetapi perlu diingat bahwa karena BLOB besar disimpan sebagai linked list halaman, I/O BLOB sama sekali bukan akses acak

    • Rencananya hanya akan menggunakan SQLite API publik. Jadi tidak perlu ditempelkan ke amalgamation
      Saya sangat menyukai binding SQLite wazero. Bahkan, saya berencana menyediakan 1) binding CGO untuk sqlite-vec dan 2) build sqlite-vec WASI kustom yang bisa dipakai langsung di go-sqlite3. Awalnya saya berniat membuat file sqlite3.wasm menggunakan skrip build dari repositori tersebut. Kalau ingin mendukungnya langsung di proyek, rasanya cukup memasukkan file sqlite-vec.c/h ke go-sqlite3/sqlite3
      Saya mempelajari I/O BLOB inkremental dengan susah payah. Itu jelas menjadi faktor pembatas dalam kecepatan query sqlite-vec. Menjaga ukuran chunk relatif kecil, di kisaran MB rendah, dan menaikkan page_size memberi keseimbangan yang cukup baik, tetapi ada efek samping terutama pada page_size. PRAGMA mmap_size juga sangat membantu karena tampaknya menjaga halaman di memori sehingga lookup overflow menjadi cepat, tetapi tentu saja penggunaan memori jauh lebih besar. Ini keseimbangan yang sulit
    • Kalau fitur ini masuk ke binding Wasm Go, saya benar-benar tertarik

  • DuckDB hari ini mengumumkan ekstensi “Vector Similarity Search in DuckDB”
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • Ini menarik. Sepertinya bisa sangat menyederhanakan proyek kecil berbasis CDN untuk HNSW yang pernah saya buat: https://github.com/jasonjmcghee/portable-hnsw
      Dengan DuckDB VSS, tampaknya kita bisa melakukan embedding, menyimpannya dalam format DuckDB, lalu menjalankan SQL di dalam CDN

  • Saya suka proyek dengan gaya seperti ini. Bagus karena ini proyek open source yang membidik masalah yang sangat spesifik
    Saya terus berpikir apakah di ekosistem TypeScript/Next.js/React juga bisa dibuat sesuatu yang sangat berguna untuk ceruk teknis, tetapi belum mendapat inspirasi

  • Di aplikasi AI RAG https://github.com/rnadigital/agentcloud, kami menggunakan Qdrant vector DB untuk otomatisasi end-to-end, jadi saya menantikan kelanjutannya. Penasaran kapan kira-kira siap dipakai dan apakah ada panduan quick start
    Saya rasa saya juga bisa membantu menulis blog

    • v0.1.0 ditargetkan sekitar satu bulan lagi. Rencananya akan menyertakan banyak dokumentasi dan panduan quick start
      Ada paket pip sqlite-vec yang belum terdokumentasi, jadi kalau ingin memanggilnya langsung dari “Agent Backend” Python, sepertinya sudah bisa dicoba sekarang

  • Ini cukup mirip dengan apa yang saya bayangkan sebagai “README-driven development”. Penasaran apakah penulisnya mulai dari dokumentasi

    • Saya mulai dari kode dulu. Ekstensinya sendiri sebagian besar sudah ditulis[0]
      Namun kondisinya masih seperti “membuat 80% dengan 20% usaha”, jadi 20% sisanya—penanganan error, fuzz testing, dan pengujian kebenaran—sepertinya akan memakan 80% waktunya. Meski begitu, orang-orang sudah bertanya tentang kondisi sqlite-vss saat ini, jadi saya pikir tulisan blog “sedang dikerjakan” ini bisa menjawab beberapa pertanyaan
      Saya juga suka ide memulai dari dokumentasi. Khususnya pada ekstensi SQLite, seperti apa SQL API-nya—fungsi skalar, virtual table, dan sebagainya—sangat penting. Sebelum menulis sebagian besar kode, saya cukup banyak membuat sketsa seperti apa bagian SQL dari sqlite-vec seharusnya
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • Sepertinya ini cukup mendekati jawaban untuk issue GitHub yang saya ajukan ke SQLite-vss beberapa bulan lalu. Secara teknis memang bukan jawaban untuk issue itu, tapi
    https://github.com/asg017/sqlite-vss/issues/124

    • Benar. Maaf saya tidak sempat memberi balasan lanjutan di sana
      Sebenarnya saat pertama kali membaca tiket itu, saya masuk ke lubang kelinci “bagaimana membuat sqlite-vss lebih baik”, dan akhirnya berujung pada “saya harus membuat sqlite-vec”. Terima kasih sudah membantu saya menuju arah ini
      Dengan quantization biner bawaan sqlite-vec, kira-kira bisa dilakukan seperti ini:
      CREATE VIRTUAL TABLE vec_files USING vec0 ( contents_embedding bit[1536] );
      INSERT INTO vec_files(rowid,contents_embedding) VALUES ((1, vec_quantize_binary( /* 1536-dimension float vector here*/)))

  • Saya penasaran apakah sqlite-vec, saat dijalankan di dalam browser, dapat mempersistenkan data ke IndexedDB native browser. Atau ingin tahu apakah bagian ini harus ditangani sendiri oleh pengguna
    Kalaupun jawabannya belum pernah dipikirkan, saya akan berterima kasih jika Anda bisa berbagi pemikiran ke arah itu

    • Kemungkinan bisa. Karena berbasis build SQLite WASM resmi, opsi persistensi yang sama[0] yang disediakan di sana dapat digunakan
      Belum pasti apakah IndexedDB didukung secara spesifik, tetapi localStorage/OPFS VFS dapat digunakan
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs