Développement de `sqlite-vec`, une nouvelle extension de recherche vectorielle pour SQLite

 (alexgarcia.xyz)
3 points par GN⁺ 2024-05-04 | 1 commentaires | Partager sur WhatsApp
  • Pour réduire les limites de sqlite-vss, sqlite-vec est en cours de développement comme extension embarquée de recherche vectorielle en pur C, avec pour objectif tous les environnements où SQLite peut s’exécuter
  • Le flux d’utilisation SQL est simplifié autour de CREATE VIRTUAL TABLE, INSERT INTO et SELECT, avec prise en charge de la recherche de style KNN ainsi que des entrées vectorielles en JSON et en binaire compact
  • En supprimant la dépendance à Faiss, le projet vise non seulement Linux et macOS, mais aussi Windows, WebAssembly, le mobile et le Raspberry Pi, avec une taille binaire attendue de quelques centaines de Ko, contre 3 à 5 Mo auparavant
  • Les vecteurs sont stockés par chunks dans une shadow table, ce qui réduit le besoin de charger l’ensemble en RAM, et PRAGMA mmap_size peut accélérer les recherches en mémoire
  • La première version ne proposera qu’un full-scan exhaustif, sans ANN, et la sortie de v0.1.0 est prévue une fois les 246 TODO de sqlite-vec.c terminés

Ce que sqlite-vec veut changer dans la recherche vectorielle de SQLite

  • sqlite-vec est une nouvelle extension SQLite écrite en pur C, pensée comme un remplaçant de sqlite-vss, publié en février 2023
  • Le périmètre visé inclut des fonctions SQL personnalisées pour la recherche vectorielle rapide, des tables virtuelles, ainsi que des outils et utilitaires pour travailler avec les vecteurs
    • quantification
    • conversion JSON/BLOB/numpy
    • arithmétique vectorielle
  • Les utilisateurs peuvent créer et interroger un stockage vectoriel en pur SQL
    • création d’une table virtuelle pour les vecteurs avec CREATE VIRTUAL TABLE
    • insertion des vecteurs avec INSERT INTO
    • recherche de style KNN sous la forme SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ...
  • Les vecteurs en entrée peuvent être fournis sous forme de chaîne JSON ou au format binaire compact

Le pur C et l’absence de dépendances élargissent les environnements d’exécution

  • sqlite-vec vise une extension en pur C sans dépendance, un choix clé pour élargir les plateformes prises en charge
  • L’ancien sqlite-vss, à cause de sa dépendance au C++, ne fonctionnait de façon stable que sur Linux et macOS, avec une taille binaire comprise entre 3 et 5 Mo
  • La nouvelle extension vise une exécution dans les environnements suivants
    • Linux
    • macOS
    • Windows
    • WebAssembly dans le navigateur
    • appareils mobiles
    • petits appareils comme le Raspberry Pi
  • La taille binaire attendue se situe dans la plage de quelques centaines de Ko

Contrôle de l’usage mémoire et de la vitesse de recherche

  • sqlite-vec contrôle l’usage mémoire en stockant les vecteurs dans des chunks au sein d’une shadow table
    • lors d’une recherche KNN, tous les vecteurs ne sont pas chargés en RAM en une seule fois, mais lus chunk par chunk
    • il n’est donc pas nécessaire de garder tous les vecteurs résidents en mémoire
  • Si de meilleures performances en mémoire sont nécessaires, on peut utiliser PRAGMA mmap_size de SQLite pour accélérer la recherche KNN

Nouvelles fonctions vectorielles et limites initiales

  • sqlite-vec cherche à mieux prendre en charge les fonctions suivantes, dans la continuité des outils récents de recherche vectorielle et des avancées de la recherche
  • Ces fonctions servent de base pour ajuster plus finement la vitesse, la précision et l’usage disque des vecteurs
  • La première version de sqlite-vec ne prendra en charge que la recherche vectorielle exhaustive par full-scan
    • il n’y aura pas d’option “approximate nearest neighbors” au départ
    • IVF et HNSW sont envisagés pour plus tard

Configuration de la démo dans le navigateur

  • La démo utilise sqlite-vec exécuté dans le navigateur
  • La configuration visible dans les outils de développement est la suivante
    • un sqlite3.wasm non optimisé de 5,9 Mo
    • le build WASM officiel de SQLite compilé avec sqlite-vec
    • une base de données SQLite movies.bit.db de 2,6 Mo
  • movies.bit.db contient dans la table articles les synopsis de 4 800 films fondés sur les métadonnées de films TMDB
  • Une table virtuelle distincte vec_movies sert d’index vectoriel pour les embeddings de ces synopsis

Données de démo et déroulement de la recherche KNN

  • La table articles contient des colonnes comme title, release_date et overview
  • La colonne overview contient un bref résumé du film, utilisé dans la démo comme base pour les embeddings
  • La table virtuelle vec_movies stocke les embeddings de articles.overview dans la colonne overview_embeddings
    • les vecteurs sont des vecteurs binaires à 768 dimensions
    • la taille de stockage est de 768 / 8 = 96, soit 96 octets
  • Quand l’utilisateur sélectionne un film via un bouton radio, l’identifiant du film sélectionné est injecté dans le paramètre :selected_movie de la requête SQL KNN
  • Les résultats de recherche sont les 10 films les plus proches du film sélectionné
    • comme il s’agit d’un vecteur binaire, le calcul de distance utilise la distance de Hamming
    • le résultat le plus proche est toujours le même film, avec une distance de 0
  • Les embeddings produits à partir de très courts résumés et d’un petit jeu de données de films n’offrent pas la meilleure qualité possible, et la quantification binaire dégrade encore cette qualité, mais l’objectif est de montrer une recherche vectorielle rapide et « suffisamment bonne » dans le navigateur
  • Pour voir le fonctionnement interne, il suffit de préfixer SELECT avec EXPLAIN QUERY PLAN, ce qui permet de voir l’“index” 0:knn utilisé par vec_movies

Les limites de sqlite-vss et la dépendance à Faiss

  • Le développement et l’adoption de sqlite-vss se sont heurtés à plusieurs obstacles
    • il ne fonctionne que sur Linux et macOS, sans prise en charge de Windows, du WASM ou des appareils mobiles
    • tous les vecteurs sont stockés en mémoire
    • il existe des bugs et problèmes liés aux transactions
    • la compilation est très difficile et prend beaucoup de temps
    • des opérations vectorielles courantes comme la quantification scalaire ou binaire sont absentes
  • Presque tous ces problèmes proviennent de la dépendance à Faiss
  • Une partie pourrait être résolue avec beaucoup de temps et d’efforts, mais nombre d’entre eux risquent de rester bloqués à cause de Faiss
  • C’est ce qui a conduit au lancement de sqlite-vec, dans l’idée qu’une solution bas niveau sans dépendances était une option séduisante et que la recherche vectorielle elle-même n’était pas si complexe

État de la release et appel au sponsoring

  • Les fonctions essentielles de sqlite-vec fonctionnent, mais la gestion des erreurs et les tests restent très insuffisants
  • Le fichier sqlite-vec.c comporte encore 246 TODO
    • todo_assert() : 191
    • commentaires // TODO : 41
    • todo panic : 14
    • la progression globale affichée pour sqlite-vec v0 est de 0/246, soit 0 %
  • Une fois les 246 TODO terminés, la première release v0.1.0 est prévue
    • documentation
    • démo
    • bindings
    • autres composants
  • L’objectif est d’y parvenir d’ici environ un mois, mais aucun calendrier n’est confirmé
  • Le projet recherche le sponsoring d’entreprises intéressées par le succès de sqlite-vec, avec possibilité de contact par e-mail

À lire aussi

1 commentaires

 
GN⁺ 2024-05-04
Commentaires sur Hacker News

  • C’est l’auteur — je répondrai aux questions s’il y en a. Il s’agit moins d’une release officielle que d’un « je travaille sur un nouveau projet », et l’extension elle-même est encore en cours de développement. Lien du projet : https://github.com/asg017/sqlite-vec
    J’ai déjà une idée assez précise de ce à quoi ressemblera la v0.1.0 de cette extension, mais il faudra sans doute encore quelques semaines pour y arriver. Ce billet visait surtout à informer les utilisateurs de sqlite-vss, mon extension précédente de recherche vectorielle pour SQLite, de ce qui arrive ensuite, et une release plus importante est prévue quand ce sera prêt
    Globalement, je suis très enthousiaste à l’idée d’avoir une alternative de recherche vectorielle facile à embarquer. Le fait que cela fonctionne sur tous les systèmes d’exploitation, en WASM, sur mobile, sur Raspberry Pi, etc., est particulièrement appréciable, et personnellement je trouve amusant d’essayer de faire tourner une petite appli de recherche sémantique sur Beepy
    [0] https://beepy.sqfmi.com/

    • Je me demande quelles fonctions de distance sont prises en charge. On dirait que les vecteurs binaires sont déjà supportés, donc je me demande si la distance de Hamming l’est aussi
      J’aimerais aussi connaître les performances par rapport à sqlite-vss. Je suis curieux de voir des chiffres de profilage à la fois sur la vitesse des requêtes et sur l’utilisation mémoire
      Dans l’ensemble, ça a vraiment l’air excellent, et j’aime beaucoup cette direction
      Le fait que sqlite-vec ne prenne au départ en charge que la recherche vectorielle par scan exhaustif, sans option de plus proches voisins approximatifs (ANN), mais avec l’idée d’ajouter plus tard IVF et HNSW, me semble être le bon choix à 1000 %. C’est bien de ne pas rendre les choses trop complexes dès le début
      J’ai déjà lancé de la recherche vectorielle on-device, et avec une combinaison de vecteurs binaires 128 bits et de distance de Hamming, c’était assez rapide pour exécuter une recherche de distance totalement exhaustive à chaque frame caméra, même avec plus de 200 000 entrées dans la base de données. On dépassait les 10 fps même sur des téléphones bas de gamme, et c’était très fluide sur les bons téléphones. Il y a étonnamment beaucoup de cas où la force brute suffit
      Cela dit, au moment d’implémenter des algorithmes ANN comme HNSW, ce serait chouette de pouvoir les gérer selon le paradigme des index de table. Ainsi, passer d’une recherche par force brute à de l’ANN deviendrait aussi simple que créer un index sur une table, et expérimenter plusieurs algorithmes ANN et leurs paramètres reviendrait à ajuster les paramètres de création de l’index. C’est peut-être déjà la direction prise, mais je le mentionne au cas où
    • Je me demande si vous prévoyez aussi d’implémenter des stratégies d’indexation comme HNSW. Le scan linéaire est évidemment un bon point de départ, et si les données sont triées dans un ordre raisonnable et, par exemple, font moins de 10 Mo, cela peut être suffisamment rapide, donc ça ne semble pas être une raison de bloquer une bêta release
      Je me demande aussi si cela se compile avec sqlite-httpvfs. Cela semblerait bien correspondre à ce projet : https://github.com/phiresky/sql.js-httpvfs
    • Le fait qu’il y ait du Wasm est vraiment bien. D’ordinaire, il était difficile d’utiliser la recherche vectorielle dans SQLite depuis le navigateur
      Je me demande aussi si vous avez envisagé une compatibilité syntaxique avec pgvector pour un DSL SQL vectoriel commun. J’imagine que les inconvénients ne sont pas forcément bien plus importants que les avantages, mais je me demande si c’est possible
    • Est-ce qu’on pourrait implémenter ça en Rust ? Je me demande aussi si le projet sqlite-loadable-rs prend en charge WASM
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • J’avais ajouté sqlite-vss à Langchain comme vector store il y a quelque temps. Je me demande si vous considérez que ce nouveau projet est déjà assez mûr pour être ajouté lui aussi à Langchain, ou s’il vaudrait mieux attendre encore un peu
      sqlite-vss est déjà bien utilisé dans plusieurs projets

  • Le passage « un vecteur binaire de 768 dimensions occupe 96 octets (768 / 8 = 96) » me perturbe. C’est justement ce genre de problème que la plupart des vector stores rencontrent, à savoir la malédiction de la dimensionnalité, et à mon sens c’est un problème antérieur à l’indexation
    Je me suis dit qu’il s’agissait peut-être plutôt de 768 dimensions * 8 octets (f64), soit 6144 octets. En général, on réduit ça en f32, f16, ou dans une représentation encore plus compacte, au prix d’une légère perte
    S’il existe une méthode pour faire tenir 768 dimensions dans 96 octets, via de la compression ou un schéma d’encodage proche d’un trie, j’aimerais vraiment en lire davantage dans un billet séparé. Si chaque dimension est traitée comme 1 bit, je comprends, mais dans ce cas je me pose encore des questions sur la qualité de recherche

    • C’est l’auteur — ici, vecteur binaire signifie que chaque dimension est quantifiée sur 1 bit. En temps normal, il faut 4 * nombre de dimensions octets par vecteur. Ici, 4 correspond à sizeof(float)
      Certains modèles d’embedding, comme nomic v1.5[0] ou le nouveau modèle de mixedbread[1], sont entraînés spécifiquement pour conserver leur qualité même après quantification binaire. Ce n’est pas le cas de tous les modèles, donc les résultats peuvent varier. En général, avec de très grands vecteurs comme le grand modèle d’embedding 3072 dimensions d’OpenAI, cela semble fonctionner dans une certaine mesure même sans entraînement spécifique pour cet usage
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • Binaire signifie que chaque dimension est quantifiée en +1 ou -1
      Si on utilise un index FAISS sur les données et qu’on applique de la quantification par produit (Product Quantization), on peut aussi tester des vecteurs binaires avec un schéma comme PQ768x1 pour des caractéristiques binaires, ou comparer avec des approches où chaque paire de vecteurs est quantifiée vers l’une de quatre valeurs : https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • À noter que la malédiction de la dimensionnalité, au sens strict, signifie qu’un espace de grande dimension devient relativement clairsemé et qu’il faut une quantité de données qui croît exponentiellement pour le remplir. Cela n’a rien à voir avec le stockage
      En général, dans les bases de données vectorielles, on compresse ou on projette les données dans un espace de dimension plus faible avant le stockage, ce qui améliore plutôt la situation

  • Grâce à sqlite-vss, j’ai pu comprendre comment fonctionne le RAG et l’implémenter dans un projet jouet. Le débogage était un peu difficile, mais une fois bien configuré, ça tournait sans accroc sur Ubuntu, et je l’utilise encore aujourd’hui.
    Ravi d’apprendre qu’une nouvelle meilleure version est en préparation, sans dépendances contraignantes.

  • Je me demande si l’objectif est d’utiliser uniquement l’API SQLite publique, ou si vous envisagez quelque chose qui s’attache à l’amalgamation SQLite.
    Cette fonctionnalité m’intéresse clairement, mais avec des bindings Go basés sur Wasm, il faut réfléchir à la manière de la distribuer séparément de SQLite. Jusqu’à présent, j’ai toujours embarqué tout le code C, car c’est bien plus simple qu’un « lien dynamique » en Wasm.
    Vous avez aussi mentionné les E/S BLOB incrémentales ; vous le savez peut-être déjà, mais il faut garder à l’esprit que les gros BLOB sont stockés sous forme de liste chaînée de pages, donc les E/S BLOB ne sont absolument pas à accès aléatoire.

    • L’idée est d’utiliser uniquement l’API SQLite publique. Donc pas besoin de l’attacher à l’amalgamation.
      J’aime vraiment beaucoup les bindings SQLite pour wazero. Je prévois d’ailleurs de proposer 1) des bindings CGO pour sqlite-vec et 2) un build WASI personnalisé de sqlite-vec utilisable directement dans go-sqlite3. À l’origine, je pensais utiliser les scripts de build de ce dépôt pour générer le fichier sqlite3.wasm. Si vous voulez le prendre en charge directement dans le projet, il devrait suffire de placer les fichiers sqlite-vec.c/h dans go-sqlite3/sqlite3.
      J’ai appris à mes dépens que les E/S BLOB incrémentales sont compliquées. C’est clairement un facteur limitant pour la vitesse des requêtes de sqlite-vec. En gardant des tailles de chunk relativement petites, de l’ordre de quelques Mo, et en augmentant page_size, on obtenait un compromis correct, mais page_size a notamment des effets secondaires. PRAGMA mmap_size aide aussi beaucoup, car cela semble garder les pages en mémoire et accélérer les lectures de débordement, mais bien sûr cela augmente fortement l’usage mémoire. C’est un équilibre difficile.
    • Ce serait vraiment intéressant si cette fonctionnalité arrivait dans les bindings Go Wasm.

  • DuckDB a annoncé aujourd’hui son extension « Vector Similarity Search in DuckDB ».
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • C’est prometteur. Ça pourrait fortement simplifier un petit projet HNSW basé sur CDN que j’avais fait auparavant : https://github.com/jasonjmcghee/portable-hnsw
      Avec DuckDB VSS, on pourrait encoder les embeddings, les stocker au format DuckDB, puis exécuter du SQL à l’intérieur du CDN.

  • J’aime ce genre de projet. C’est un projet open source qui vise un problème très spécifique, et c’est ce qui me plaît.
    Je continue à me demander si on pourrait créer quelque chose de très utile pour une niche technique dans l’écosystème TypeScript/Next.js/React, mais l’inspiration ne m’est pas encore venue.

  • J’ai utilisé Qdrant vector DB pour l’automatisation de bout en bout dans l’appli AI RAG https://github.com/rnadigital/agentcloud, donc je suis impatient de voir la suite. Je me demande quand ce sera prêt à l’emploi et s’il y aura un guide de démarrage rapide.
    Je pourrais peut-être aussi aider pour la rédaction d’articles de blog.

    • La v0.1.0 est visée d’ici environ un mois. Je prévois d’inclure beaucoup de documentation et des guides de démarrage rapide.
      Il existe aussi un paquet pip sqlite-vec non documenté, donc si vous voulez l’appeler directement depuis un « Agent Backend » Python, vous pouvez probablement déjà l’essayer.

  • C’est assez proche de ce que j’imaginais pour du « README-driven development ». Je me demande si l’auteur a commencé par la documentation.

    • J’ai commencé par le code. L’extension elle-même est déjà en grande partie écrite[0].
      Mais on en est au stade du « 80 % réalisés avec 20 % d’effort », donc les 20 % restants — gestion des erreurs, fuzz testing, tests de correction — vont probablement prendre 80 % du temps. Cela dit, comme les gens posent déjà des questions sur l’état actuel de sqlite-vss, je me suis dit que ce billet de blog « work in progress » pourrait répondre à quelques-unes d’entre elles.
      J’aime aussi l’idée de commencer par la documentation. Surtout pour une extension SQLite, l’API SQL — à quoi ressemblent les fonctions scalaires, les tables virtuelles, etc. — est vraiment essentielle. Avant même d’écrire la majeure partie du code, j’ai beaucoup esquissé ce à quoi la partie SQL de sqlite-vec devait ressembler.
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • On dirait presque une réponse à une issue GitHub que j’avais ouverte sur SQLite-vss il y a quelques mois. Pas strictement une réponse à cette issue, mais presque.
    https://github.com/asg017/sqlite-vss/issues/124

    • Exact. Désolé de ne pas avoir pu y répondre ensuite.
      En réalité, c’est en lisant ce ticket pour la première fois que je suis tombé dans le terrier du lapin « comment rendre sqlite-vss meilleur », ce qui m’a finalement conduit à « il faut que je crée sqlite-vec ». Merci de m’avoir mis sur cette voie.
      Avec la quantification binaire intégrée de sqlite-vec, on peut faire à peu près ceci :
      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*/)))

  • Je me demande si, lorsqu’il s’exécute dans le navigateur, sqlite-vec peut persister les données dans IndexedDB natif du navigateur. Ou bien faut-il que l’utilisateur gère lui-même cette partie ?
    Même si la réponse est que vous n’y avez pas encore réfléchi, je vous serais reconnaissant de partager votre réflexion dans cette direction.

    • C’est peut-être possible. Comme il repose sur le build officiel SQLite WASM, il peut utiliser les mêmes options de persistance[0] fournies à cet endroit.
      Je ne suis pas certain qu’IndexedDB soit pris en charge spécifiquement, mais les VFS localStorage/OPFS peuvent être utilisés.
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs