Neue Vektorsuch-Erweiterung sqlite-vec für SQLite in Entwicklung

 (alexgarcia.xyz)
3 Punkte von GN⁺ 2024-05-04 | 1 Kommentare | Auf WhatsApp teilen
  • Um die Einschränkungen des bestehenden sqlite-vss zu reduzieren, wird sqlite-vec als rein C-basierte eingebettete Vektorsuch-Erweiterung entwickelt und zielt auf praktisch alle Umgebungen ab, in denen SQLite läuft
  • Der SQL-Nutzungsfluss wird auf CREATE VIRTUAL TABLE, INSERT INTO und SELECT vereinfacht und unterstützt KNN-Suche im Stil von KNN sowie Vektoreingaben als JSON und kompaktes Binary-Format
  • Ohne Faiss-Abhängigkeit zielt es neben Linux und macOS auch auf Windows, WebAssembly, Mobile und Raspberry Pi ab; die Binärgröße wird statt der bisherigen 3 MB bis 5 MB im Bereich von einigen Hundert KB erwartet
  • Vektoren werden in Chunks in Shadow Tables gespeichert, wodurch weniger Bedarf besteht, alles in den RAM zu laden; mit PRAGMA mmap_size lässt sich die Geschwindigkeit speicherbasierter Suchen erhöhen
  • Die erste Version bietet nur exhaustive Full-Scan und noch kein ANN; ein Release von v0.1.0 ist geplant, nachdem die 246 TODOs in sqlite-vec.c erledigt sind

Was sqlite-vec an der Vektorsuche in SQLite ändern will

  • sqlite-vec ist eine neue, in reinem C geschriebene SQLite-Erweiterung und ein Projekt, das das im Februar 2023 veröffentlichte sqlite-vss ersetzen soll
  • Der Zielumfang umfasst benutzerdefinierte SQL-Funktionen für schnelle Vektorsuche, Virtual Tables sowie Tools und Utilities für Vektoroperationen
    • Quantisierung
    • Umwandlung zwischen JSON/BLOB/numpy
    • Vektorarithmetik
  • Nutzer können einen Vektorspeicher ausschließlich mit SQL erstellen und durchsuchen
    • Erstellen einer Virtual Table für Vektoren mit CREATE VIRTUAL TABLE
    • Einfügen von Vektoren mit INSERT INTO
    • KNN-Suche in der Form SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ...
  • Als Vektoreingabe kann ein JSON-String oder ein kompaktes Binary-Format verwendet werden

Reines C und keine Abhängigkeiten erweitern die Laufzeitumgebungen

  • sqlite-vec zielt auf eine abhängigkeitsfreie Erweiterung in reinem C ab; diese Entscheidung ist die zentrale Voraussetzung für eine breitere Plattformunterstützung
  • Das bestehende sqlite-vss lief wegen seiner C++-Abhängigkeit nur unter Linux und macOS zuverlässig, und die Binärgröße lag im Bereich von 3 MB bis 5 MB
  • Die neue Erweiterung soll in folgenden Umgebungen laufen
    • Linux
    • macOS
    • Windows
    • WebAssembly im Browser
    • Mobile Geräte
    • Kleine Geräte wie Raspberry Pi
  • Die erwartete Binärgröße liegt im Bereich von einigen Hundert KB

Speicherverbrauch und Suchgeschwindigkeit steuern

  • sqlite-vec steuert den Speicherverbrauch, indem Vektoren in Chunks innerhalb einer Shadow Table gespeichert werden
    • Bei einer KNN-Suche werden nicht alle Vektoren auf einmal in den RAM geladen, sondern chunkweise gelesen
    • Die gesamten Vektoren müssen nicht dauerhaft im Speicher liegen
  • Wenn speicherbasierte Geschwindigkeit benötigt wird, kann SQLite-PRAGMA mmap_size genutzt werden, um KNN-Suchen schneller zu machen

Neue Vektorfunktionen und anfängliche Einschränkungen

  • sqlite-vec will folgende Funktionen besser unterstützen und damit aktuelle Vektorsuch-Tools und Forschungstrends aufgreifen
  • Diese Funktionen bilden die Grundlage, um Geschwindigkeit, Genauigkeit und Speicherplatzbedarf auf der Festplatte von Vektoren feiner zu steuern
  • Die frühe Version von sqlite-vec unterstützt nur Vektorsuche per exhaustive Full-Scan
    • Eine Option für „approximate nearest neighbors“ gibt es anfangs nicht
    • IVF und HNSW sind Funktionen, die künftig ergänzt werden sollen

Aufbau der Browser-Demo

  • Die Demo nutzt sqlite-vec, das im Browser läuft
  • In den Developer Tools ist folgende Konfiguration zu sehen
    • ein nicht optimiertes 5,9 MB großes sqlite3.wasm
    • der offizielle SQLite-WASM-Build, in den sqlite-vec kompiliert wurde
    • eine 2,6 MB große SQLite-Datenbank movies.bit.db
  • movies.bit.db enthält in der Tabelle articles 4.800 Film-Overviews auf Basis der TMDB-Filmmetadaten
  • Eine separate Virtual Table vec_movies ist der Vektorindex für die Embeddings dieser Overviews

Demo-Daten und Ablauf der KNN-Suche

  • Die Tabelle articles enthält Spalten wie title, release_date und overview
  • Die Spalte overview enthält kurze Sätze zur Filmhandlung und dient in der Demo als Ziel für Embeddings
  • Die Virtual Table vec_movies speichert die Embeddings von articles.overview in der Spalte overview_embeddings
    • Die Vektoren sind 768-dimensionale Binary Vectors
    • Die Speichergröße beträgt 768 / 8 = 96, also 96 Byte
  • Wenn der Nutzer per Radio-Button einen Film auswählt, wird die ausgewählte Film-ID in den Parameter :selected_movie der KNN-SQL-Query eingesetzt
  • Die Suchergebnisse sind die 10 Filme, die dem ausgewählten Film am nächsten liegen
    • Da es sich um Binary Vectors handelt, wird zur Distanzberechnung die Hamming Distance verwendet
    • Das nächstgelegene Ergebnis ist immer derselbe Film, mit Distanz 0
  • Die Ergebnisse der Einbettung kurzer Ein-Satz-Handlungen und eines kleinen Filmdatensatzes sind nicht von höchster Qualität, und Binary Quantization opfert zusätzlich Qualität; der Fokus liegt aber darauf, eine schnelle und „gut genug“ Vektorsuche im Browser zu zeigen
  • Um das interne Verhalten zu prüfen, kann man EXPLAIN QUERY PLAN vor SELECT setzen; dann sieht man den von vec_movies verwendeten 0:knn-„Index“

Einschränkungen von sqlite-vss und die Faiss-Abhängigkeit

  • Bei Entwicklung und Nutzung von sqlite-vss gab es mehrere Hindernisse
    • Es läuft nur unter Linux und macOS und unterstützt weder Windows, WASM noch mobile Geräte
    • Es speichert alle Vektoren im Speicher
    • Es gibt Bugs und Issues im Zusammenhang mit Transaktionen
    • Die Kompilierung ist sehr schwierig und dauert lange
    • Gängige Vektoroperationen wie Scalar/Binary Quantization fehlen
  • Fast alle diese Probleme gehen auf die Abhängigkeit von Faiss zurück
  • Einige Probleme könnten sich mit viel Zeit und Aufwand lösen lassen, viele andere könnten jedoch durch Faiss blockiert sein
  • Eine abhängigkeitsfreie Low-Level-Lösung wurde zu einer attraktiven Option, und aus der Einschätzung heraus, dass Vektorsuche selbst nicht besonders komplex ist, entstand sqlite-vec

Release-Status und Sponsoring-Aufruf

  • Die Kernfunktionen von sqlite-vec funktionieren, aber Fehlerbehandlung und Tests sind noch sehr unzureichend
  • In der Datei sqlite-vec.c sind noch 246 TODOs offen
    • 191-mal todo_assert()
    • 41 // TODO-Kommentare
    • 14-mal todo panic
    • Der Gesamtfortschritt wird für sqlite-vec v0 mit 0/246, 0 % angezeigt
  • Wenn die 246 TODOs erledigt sind, soll das erste Release v0.1.0 erscheinen
    • Dokumentation
    • Demos
    • Bindings
    • weitere Komponenten sollen mitgeliefert werden
  • Der Zielzeitpunkt liegt bei ungefähr einem Monat, ist aber kein fester Termin
  • Gesucht werden Sponsoren aus Unternehmen, die am Erfolg von sqlite-vec interessiert sind; Anfragen sind per E-Mail möglich

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-04
Meinungen auf Hacker News

  • Ich bin der Autor — wenn es Fragen gibt, beantworte ich sie gern. Das ist eher ein „ich arbeite an einem neuen Projekt“ als ein offizielles Release, und die Erweiterung selbst ist noch in Arbeit. Der Projektlink ist https://github.com/asg017/sqlite-vec
    Ich habe schon eine ziemlich konkrete Vorstellung davon, wie v0.1.0 dieser Erweiterung aussehen wird, aber bis dahin dürfte es noch ein paar Wochen dauern. Dieser Beitrag sollte vor allem Nutzer meiner früheren SQLite-Erweiterung für Vektorsuche, sqlite-vss, darüber informieren, was als Nächstes kommt; sobald es bereit ist, wird es ein größeres Release geben.
    Insgesamt freue ich mich sehr darauf, eine leicht einzubettende Alternative für Vektorsuche zu haben. Besonders gut ist, dass sie auf allen Betriebssystemen, in WASM, auf Mobilgeräten, Raspberry Pi usw. läuft; persönlich versuche ich gerade, auf dem Beepy eine kleine semantische Such-App laufen zu lassen, was ziemlich spannend ist.
    [0] https://beepy.sqfmi.com/

    • Mich würde interessieren, welche Distanzfunktionen unterstützt werden. Es sieht so aus, als würden bereits binäre Vektoren unterstützt; ich frage mich, ob auch die Hamming-Distanz unterstützt wird.
      Außerdem würde ich gern die Performance im Vergleich zu sqlite-vss kennen. Mich interessieren Profiling-Zahlen sowohl zur Abfragegeschwindigkeit als auch zum Speicherverbrauch.
      Insgesamt sieht das wirklich hervorragend aus, und mir gefällt diese Richtung.
      Der Ansatz, dass sqlite-vec zunächst nur Vektorsuche per vollständigem Brute-Force-Scan unterstützt und keine ANN-Optionen (Approximate Nearest Neighbor) anbietet, später aber IVF und HNSW hinzufügen möchte, ist meiner Meinung nach zu 1000 % richtig. Mir gefällt, dass es nicht von Anfang an übermäßig komplex gemacht wird.
      Ich habe schon einmal On-Device-Vektorsuche ausgeliefert, und mit der Kombination aus 128-Bit-Binärvektoren und Hamming-Distanz war es schnell genug, um selbst bei Datenbanken mit mehr als 200.000 Einträgen bei jedem Kameraframe eine vollständige Brute-Force-Distanzsuche auszuführen. Selbst auf günstigen Smartphones kamen über 10 fps heraus, auf guten Smartphones lief es sehr flüssig. Es ist überraschend oft der Fall, dass Brute Force ausreicht.
      Wenn jedoch ANN-Algorithmen wie HNSW implementiert werden, wäre es großartig, wenn sich das im Tabellenindex-Paradigma abbilden ließe. Dann wäre der Wechsel von Brute-Force-Suche zu ANN so einfach wie das Anlegen eines Index auf einer Tabelle, und Experimente mit verschiedenen ANN-Algorithmen und Parametern wären über die Anpassung der Index-Erstellungsparameter möglich. Vielleicht geht es ohnehin schon in diese Richtung, aber ich wollte es vorsichtshalber erwähnen.
    • Mich würde interessieren, ob auch Indexierungsstrategien wie HNSW geplant sind. Ein linearer Scan ist als Ausgangspunkt natürlich sinnvoll, und wenn die Daten in einer vernünftigen Reihenfolge sortiert sind und etwa unter 10 MB liegen, kann das schnell genug sein; es scheint also kein Grund zu sein, ein Beta-Release aufzuhalten.
      Außerdem frage ich mich, ob es zusammen mit sqlite-httpvfs gebaut wird. Das würde gut zu diesem Projekt passen: https://github.com/phiresky/sql.js-httpvfs
    • Dass Wasm dabei ist, gefällt mir wirklich. Normalerweise war es im Browser schwierig, Vektorsuche innerhalb von SQLite zu nutzen.
      Mich würde interessieren, ob ihr erwogen habt, es für eine gemeinsame SQL-Vektor-DSL syntaxkompatibel mit pgvector zu machen. Ich vermute, die Nachteile wären deutlich kleiner als die Vorteile, aber ich frage mich, ob es machbar ist.
    • Könnte man das in Rust implementieren? Ich frage mich auch, ob das Projekt sqlite-loadable-rs WASM unterstützt.
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • Ich habe sqlite-vss früher als Vektorspeicher zu Langchain hinzugefügt. Hältst du dieses neue Projekt für reif genug, um es ebenfalls zu Langchain hinzuzufügen, oder sollte man besser noch etwas warten?
      sqlite-vss wird bereits in einigen Projekten gut genutzt.

  • Der Teil „ein binärer Vektor mit 768 Dimensionen belegt 96 Byte (768 / 8 = 96)“ verwirrt mich. Genau hier liegt meiner Ansicht nach der Fluch der Dimensionalität, mit dem die meisten Vektorspeicher zu kämpfen haben, und das ist ein Problem noch vor der Indexierung.
    Ich dachte zunächst, gemeint seien vielleicht 768 Dimensionen * 8 Byte (f64), also 6144 Byte. Üblicherweise reduziert man das unter Inkaufnahme eines gewissen Qualitätsverlusts auf f32 oder f16 oder eine noch kleinere Darstellung.
    Falls es eine Methode gibt, 768 Dimensionen per Kompression oder einer trie-ähnlichen amortisierten Technik in 96 Byte unterzubringen, würde ich gern in einem eigenen Beitrag mehr darüber hören. Wenn jede Dimension als 1 Bit behandelt wird, verstehe ich es, aber dann habe ich weiterhin Fragen zur Suchqualität.

    • Ich bin der Autor — mit binärem Vektor ist hier gemeint, dass jede Dimension auf 1 Bit quantisiert wird. Normalerweise braucht man pro Vektor 4 * Anzahl der Dimensionen Byte. Die 4 steht hier für sizeof(float).
      Einige Embedding-Modelle, etwa nomic v1.5[0] oder das neue Modell von mixedbread[1], werden speziell so trainiert, dass die Qualität auch nach binärer Quantisierung erhalten bleibt. Das gilt nicht für alle Modelle, daher können die Ergebnisse variieren. Im Allgemeinen scheint es bei sehr großen Vektoren, wie OpenAIs großem Embedding-Modell mit 3072 Dimensionen, bis zu einem gewissen Grad zu funktionieren, selbst wenn sie nicht speziell dafür trainiert wurden.
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • Binär bedeutet, dass jede Dimension auf +1 oder -1 quantisiert wird.
      Wenn man für die Daten einen FAISS-Index verwendet und Product Quantization anwendet, kann man bei binären Merkmalen binäre Vektoren etwa mit PQ768x1 ausprobieren und auch Varianten vergleichen, bei denen jedes Vektorpaar auf einen von vier Werten quantisiert wird: https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • Zur Einordnung: Der Fluch der Dimensionalität bedeutet genau genommen, dass hochdimensionale Räume relativ dünn besetzt werden und die Datenmenge exponentiell wachsen muss, um diesen Raum zu füllen. Mit Speicherkapazität hat das nichts zu tun.
      In Vektordatenbanken werden Daten vor dem Speichern üblicherweise in einen niedriger dimensionalen Raum komprimiert oder projiziert, wodurch sich diese Situation eher verbessert.

  • Dank sqlite-vss konnte ich lernen, wie RAG funktioniert, und es in einem Spielzeugprojekt implementieren. Das Debugging war etwas schwierig, aber wenn man es richtig hinbekommen hat, lief es unter Ubuntu einwandfrei, und ich nutze es immer noch
    Freut mich, dass eine bessere neue Version ohne eingeschränkte Abhängigkeiten gebaut wird

  • Mich würde interessieren, ob geplant ist, nur die öffentliche SQLite API zu verwenden, oder ob eher eine Anbindung an die SQLite-Amalgamation vorgesehen ist
    An so einer Funktion bin ich definitiv interessiert, muss mir aber überlegen, wie ich sie bei Wasm-basierten Go-Bindings getrennt von SQLite ausliefern kann. Bisher habe ich den gesamten C-Code gebündelt ausgeliefert, weil das deutlich einfacher war als Wasm-„Dynamic Linking“
    Außerdem wurde inkrementelle BLOB-Ein-/Ausgabe erwähnt; wie ihr wahrscheinlich schon wisst, sollte man im Hinterkopf behalten, dass große BLOBs als verkettete Liste von Pages gespeichert werden, weshalb BLOB-I/O keineswegs Random Access ist

    • Es ist geplant, nur die öffentliche SQLite API zu verwenden. Daher muss nichts an die Amalgamation angehängt werden
      Ich mag die wazero-SQLite-Bindings wirklich sehr. Tatsächlich plane ich, 1) CGO-Bindings für sqlite-vec und 2) einen eigenen WASI-Build von sqlite-vec bereitzustellen, der direkt mit go-sqlite3 verwendet werden kann. Ursprünglich wollte ich das Build-Skript dieses Repositories verwenden, um die Datei sqlite3.wasm zu erzeugen. Wenn ihr es direkt im Projekt unterstützen wollt, müsste es meiner Einschätzung nach reichen, die Dateien sqlite-vec.c/h in go-sqlite3/sqlite3 zu legen
      Inkrementelle BLOB-Ein-/Ausgabe habe ich auf die harte Tour gelernt. Sie ist bei der Query-Geschwindigkeit von sqlite-vec eindeutig ein limitierender Faktor. Wenn man die Chunk-Größe relativ klein hält, im niedrigen MB-Bereich, und page_size erhöht, war die Balance ganz okay, aber gerade page_size hat Nebenwirkungen. PRAGMA mmap_size hilft ebenfalls sehr, weil es die Pages offenbar im Speicher hält und Overflow-Lookups schneller macht, erhöht aber natürlich den Speicherverbrauch deutlich. Eine schwierige Balance
    • Wenn diese Funktion in die Wasm-Go-Bindings kommt, bin ich wirklich interessiert

  • DuckDB hat heute die Erweiterung „Vector Similarity Search in DuckDB“ angekündigt
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • Darauf freue ich mich. Das könnte ein kleines CDN-basiertes HNSW-Projekt, das ich früher gebaut habe, stark vereinfachen: https://github.com/jasonjmcghee/portable-hnsw
      Mit DuckDB VSS könnte man offenbar Embeddings erstellen, sie im DuckDB-Format speichern und dann innerhalb des CDNs SQL ausführen

  • Ich mag Projekte dieser Art. Mir gefällt, dass es ein Open-Source-Projekt ist, das auf ein sehr spezifisches Problem abzielt
    Ich überlege immer wieder, ob sich im TypeScript/Next.js/React-Ökosystem etwas sehr Nützliches für eine technische Nische bauen ließe, aber mir ist noch keine Inspiration gekommen

  • Wir haben in der AI-RAG-App https://github.com/rnadigital/agentcloud für Ende-zu-Ende-Automatisierung die Qdrant-Vektordatenbank verwendet, und ich freue mich, dass ein Nachfolger entsteht. Mich würde interessieren, wann sie einsatzbereit sein wird und ob es einen Quickstart-Guide gibt
    Ich könnte wohl auch beim Schreiben des Blogs helfen

    • v0.1.0 ist für etwa in einem Monat angepeilt. Geplant sind viele Dokumente und Quickstart-Guides
      Es gibt ein undokumentiertes sqlite-vec-pip-Paket; wenn ihr es direkt aus dem „Agent Backend“ in Python aufrufen wollt, könntet ihr es vermutlich schon jetzt ausprobieren

  • Das kommt ziemlich nah an das heran, was ich mir unter „README-driven Development“ vorgestellt habe. Ich frage mich, ob der Autor mit der Dokumentation angefangen hat

    • Ich habe zuerst mit dem Code angefangen. Die Erweiterung selbst ist schon größtenteils geschrieben[0]
      Allerdings ist sie in dem Zustand, in dem „80 % mit 20 % des Aufwands“ entstanden sind; die restlichen 20 %, also Fehlerbehandlung, Fuzz-Tests und Korrektheitstests, werden wohl 80 % der Zeit beanspruchen. Da Leute aber bereits Fragen zum aktuellen Zustand von sqlite-vss stellen, dachte ich, dieser Blogpost „in Arbeit“ könnte einige dieser Fragen beantworten
      Die Idee, mit der Dokumentation anzufangen, gefällt mir auch. Gerade bei SQLite-Erweiterungen ist es wirklich wichtig, wie die SQL API aussieht, also skalare Funktionen, virtuelle Tabellen und so weiter. Bevor ich den Großteil des Codes geschrieben habe, habe ich ziemlich viel skizziert, wie der SQL-Teil von sqlite-vec aussehen sollte
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • Das scheint ziemlich genau eine Antwort auf ein GitHub-Issue zu sein, das ich vor ein paar Monaten bei SQLite-vss erstellt habe. Genau genommen ist es keine Antwort auf dieses Issue, aber trotzdem
    https://github.com/asg017/sqlite-vss/issues/124

    • Stimmt. Tut mir leid, dass ich dort nicht nachgefasst habe
      Tatsächlich hat mich dieses Ticket beim ersten Lesen in das Rabbit Hole „Wie kann man sqlite-vss besser machen?“ geführt, und am Ende wurde daraus „Ich sollte sqlite-vec bauen“. Danke, dass du mich auf diesen Weg gebracht hast
      Mit der eingebauten binären Quantisierung von sqlite-vec könntest du so etwas ungefähr folgendermaßen machen:
      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*/)))

  • Ich frage mich, ob sqlite-vec bei der Ausführung im Browser Daten im browsernativen IndexedDB persistent speichern kann. Oder ob Nutzer diesen Teil selbst übernehmen müssen
    Auch wenn die Antwort lautet, dass ihr darüber noch nicht nachgedacht habt, wäre ich dankbar, wenn ihr eure Überlegungen in diese Richtung teilen könntet

    • Es könnte möglich sein. Da es auf dem offiziellen SQLite-WASM-Build basiert, kann man dieselben dort bereitgestellten Persistenzoptionen[0] nutzen
      Ich bin mir nicht sicher, ob IndexedDB konkret unterstützt wird, aber localStorage/OPFS VFS können verwendet werden
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs