SQLite向け新ベクター検索拡張 `sqlite-vec` を開発中

 (alexgarcia.xyz)
3 ポイント 投稿者 GN⁺ 2024-05-04 | 1件のコメント | WhatsAppで共有
  • 既存の sqlite-vss の限界を減らすため、sqlite-vec は純粋なCベースの組み込み型ベクター検索拡張として開発中で、SQLiteが動作する幅広い環境を対象としている
  • SQLの利用フローは CREATE VIRTUAL TABLE、INSERT INTO、SELECT を中心に単純化され、KNNスタイル検索とJSON・compact binaryのベクター入力をサポートする
  • Faiss依存をなくし、Linux、macOSだけでなくWindows、WebAssembly、モバイル、Raspberry Piまでを視野に入れ、バイナリサイズも従来の3MB〜5MBより小さい数百KB規模を見込む
  • ベクターをshadow tableの**チャンク(chunk)**単位で保存し、全体をRAMに載せる必要を減らし、PRAGMA mmap_size でメモリベース検索の速度を高められる
  • 初期バージョンはexhaustive full-scanのみを提供し、ANNは含まれず、sqlite-vec.c の246個のTODOが完了した後に v0.1.0 のリリースが予定されている

sqlite-vec が変えようとしているSQLiteベクター検索

  • sqlite-vec は純粋なCで書かれる新しいSQLite拡張であり、2023年2月に公開された sqlite-vss を置き換えることを目指すプロジェクトである
  • 目標範囲には、高速なベクター検索のためのユーザー定義SQL関数、仮想テーブル(virtual table)、ベクター操作用のツールやユーティリティまで含まれる
    • 量子化
    • JSON/BLOB/numpy変換
    • ベクター演算
  • ユーザーは純粋なSQLだけでベクターストアを作成し、検索できる
    • CREATE VIRTUAL TABLE でベクター用の仮想テーブルを作成
    • INSERT INTO でベクターを挿入
    • SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ... 形式でKNNスタイル検索
  • ベクター入力にはJSON文字列またはcompact binary形式を使用できる

純粋なCと無依存が広げる実行環境

  • sqlite-vec は無依存の純粋C拡張を目標としており、この選択が対応プラットフォームを広げるための重要な条件となっている
  • 既存の sqlite-vss はC++依存のためLinuxとmacOSでしか安定動作せず、バイナリサイズは3MB〜5MBの範囲だった
  • 新しい拡張は次の環境での動作を目標としている
    • Linux
    • macOS
    • Windows
    • ブラウザ上のWebAssembly
    • モバイル端末
    • Raspberry Piのような小型デバイス
  • 想定されるバイナリサイズは数百KBの範囲である

メモリ使用量と検索速度の調整

  • sqlite-vec はベクターをshadow table内のチャンクに分けて保存する方式でメモリ使用量を制御する
    • KNN検索時にすべてのベクターを一度にRAMへ載せず、チャンク単位で読み込む
    • 全ベクターをメモリ常駐させる必要がない
  • メモリベースの速度が必要なら、SQLiteの PRAGMA mmap_size を使ってKNN検索をさらに高速化できる

新しいベクター機能と初期の制限

  • sqlite-vec は最近のベクター検索ツールや研究動向を踏まえ、次の機能をよりよくサポートしようとしている
  • これらの機能は、ベクターの速度、精度、ディスク使用量をより細かく調整するための基盤になる
  • 初期の sqlite-vec は exhaustive full-scan ベクター検索のみをサポートする
    • “approximate nearest neighbors” オプションは当初はない
    • IVFとHNSWは今後追加したい機能である

ブラウザデモの構成

  • デモではブラウザで動作する sqlite-vec を使用している
  • 開発者ツールで確認できる構成は次のとおり
    • 最適化されていない 5.9MB の sqlite3.wasm
    • sqlite-vec がコンパイルされた 公式SQLite WASMビルド
    • 2.6MB サイズの movies.bit.db SQLiteデータベース
  • movies.bit.db には TMDB映画メタデータ に基づく4,800本の映画概要が articles テーブルに格納されている
  • 別の vec_movies 仮想テーブルは、その概要埋め込みのベクターインデックスである

デモデータとKNN検索の流れ

  • articles テーブルには title、release_date、overview のようなカラムがある
  • overview カラムには映画のあらすじを短い文章で収めており、デモでの埋め込み対象となっている
  • vec_movies 仮想テーブルは articles.overview の埋め込みを overview_embeddings カラムに保存する
    • ベクターは768次元のbinary vector
    • 保存サイズは 768 / 8 = 96 で96バイト
  • ユーザーがラジオボタンで映画を選ぶと、選択した映画IDがKNN SQLクエリの :selected_movie パラメータに入る
  • 検索結果は、選択した映画に最も近い10本の映画である
    • binary vectorなので、距離計算にはhamming distanceを使う
    • 最も近い結果は常に同じ映画で、距離は0である
  • 短い単文のあらすじと小さな映画データセットを埋め込んだ結果は最高品質ではなく、binary quantizationによって品質はさらに犠牲になるが、ブラウザ内で高速かつ「十分に良い」ベクター検索を示すことに重点が置かれている
  • 内部動作を確認するには SELECT の前に EXPLAIN QUERY PLAN を付ければよく、vec_movies が使う 0:knn “index” を見ることができる

sqlite-vss の限界とFaiss依存

  • sqlite-vss の開発と採用には複数の障害があった
    • LinuxとmacOSでしか動作せず、Windows、WASM、モバイル端末などはサポートできない
    • ベクターをすべてメモリ内に保存する
    • トランザクション関連のバグや問題がある
    • コンパイルが非常に難しく、時間もかかる
    • scalar/binary quantizationのような一般的なベクター操作が欠けている
  • これらの問題のほとんどは Faiss 依存に起因している
  • 一部の問題は多くの時間と労力をかければ解決できるかもしれないが、かなりの部分はFaissが原因で行き詰まる可能性がある
  • 無依存の低レベルソリューションが魅力的な選択肢となり、ベクター検索そのものもそれほど複雑ではないという判断から sqlite-vec は始まった

リリース状況とスポンサー募集

  • sqlite-vec の中核機能は動作しているが、エラー処理とテストはまだ非常に不足している
  • sqlite-vec.c ファイルには246個のTODOが残っている
    • todo_assert() 191個
    • // TODO コメント 41個
    • todo panic 14個
    • 全体進捗は 0/246、0%と表示されている
  • 246個のTODOが完了すれば、最初の v0.1.0 リリースが公開される予定である
    • ドキュメント
    • デモ
    • バインディング
    • その他の構成要素があわせて提供される予定
  • 目標時期は約1か月程度だが、確定したスケジュールではない
  • sqlite-vec の成功に関心を持つ企業からのスポンサーを募集しており、メールで問い合わせできる

関連記事

1件のコメント

 
GN⁺ 2024-05-04
Hacker News のコメント

  • 作者です — 質問があれば答えます。これは正式リリースというより「新しいプロジェクトに取り組んでいる」という性格のもので、拡張機能自体もまだ作業中です。プロジェクトのリンクはこちらです: https://github.com/asg017/sqlite-vec
    この拡張の v0.1.0 がどんな形になるかはかなり具体的に見えていますが、そこまではあと数週間かかりそうです。今回の記事は、以前作った SQLite ベクトル検索拡張である sqlite-vss のユーザーに、次に何が来るのかを知らせる目的が大きく、準備ができたらもっと大きなリリースを行う予定です。
    全体としては、簡単に埋め込めるベクトル検索の代替を持てることにとても期待しています。あらゆる OS、WASM、モバイル端末、Raspberry Pi などで動くのが特に良い点で、個人的には Beepy で小さなセマンティック検索アプリを動かしてみようとしているので楽しみです。
    [0] https://beepy.sqfmi.com/

    • どの距離関数をサポートするのか気になります。すでにバイナリベクトルをサポートしているように見えるので、ハミング距離もサポートされるのか知りたいです。
      sqlite-vss と比較した性能も知りたいです。クエリ速度とメモリ使用量の両方について、プロファイリングの数値が気になります。
      全体として本当に素晴らしく見えますし、この方向性は気に入っています。
      最初は sqlite-vec が全件スキャンによるベクトル検索だけをサポートし、近似最近傍探索（ANN）のオプションはないものの、後で IVF と HNSW を追加したい、というアプローチは 1000% 正しいと思います。最初から過度に複雑にしない点が良いです。
      オンデバイスのベクトル検索をリリースしたことがありますが、128ビットのバイナリベクトルとハミング距離の組み合わせでは、データベースが20万件以上あっても、カメラの各フレームごとに完全な総当たり距離検索を回せるほど十分に高速でした。低価格帯のスマートフォンでも 10fps 以上出ていて、良いスマートフォンでは非常に滑らかでした。総当たりで十分なケースは驚くほど多いです。
      ただし HNSW のような ANN アルゴリズムを実装する際には、テーブルインデックスのパラダイムとして扱えると素晴らしいと思います。そうすれば総当たり検索から ANN への切り替えが、テーブルにインデックスを作るのと同じくらい単純になり、複数の ANN アルゴリズムやパラメータの実験も、インデックス作成パラメータを調整する形で可能になります。すでにその方向かもしれませんが、念のため触れておきます。
    • HNSW のようなインデックス戦略も実装する予定があるのか気になります。線形スキャンは出発点として当然良いですし、データが妥当な順序で並んでいて、たとえば 10MB 未満なら十分速い可能性があるので、ベータリリースを妨げる理由には見えません。
      sqlite-httpvfs と一緒にビルドするのかも気になります。このプロジェクトと相性が良さそうです: https://github.com/phiresky/sql.js-httpvfs
    • Wasm が入っている点が本当に良いです。通常、ブラウザでは SQLite 内のベクトル検索を使うのが難しかったので。
      共通の SQL ベクトル DSL のために、pgvector と構文互換にすることも検討したのか気になります。メリットよりデメリットの方がずっと小さいのではないかと思いますが、可能なのか知りたいです。
    • これを Rust で実装できるでしょうか？ sqlite-loadable-rs プロジェクトが WASM をサポートしているのかも気になります。
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • 以前 sqlite-vss を Langchain にベクトルストアとして追加しました。この新しいプロジェクトも Langchain に追加するほど成熟していると見ていますか、それとももう少し待った方がよいでしょうか。
      sqlite-vss はすでにいくつかのプロジェクトでうまく使っています。

  • 「768次元のバイナリベクトルなので 96バイトを占める（768 / 8 = 96）」という部分が混乱します。ほとんどのベクトルストアが直面する問題である次元の呪いはまさにこういう部分で、インデックス化以前の問題だと思います。
    おそらく 768次元 * 8バイト（f64）で 6144バイトを意味しているのではないかと思いました。通常は多少の損失を受け入れて f32 や f16、あるいはもっと小さい表現に削ります。
    圧縮やトライ木に似た償却的な方法などで 768次元を 96バイトに収める方法があるなら、別の記事でもっと聞きたいです。各次元を 1ビットとして扱うということなら理解できますが、その場合でも検索品質についてはまだ気になる点があります。

    • 作者です — ここでいうバイナリベクトルは、各次元を 1ビットに量子化するという意味です。通常はベクトル1つあたり 4 * 次元数 バイトが必要です。ここでの 4 は sizeof(float) です。
      nomic v1.5[0] や mixedbread の新しいモデル[1]のように、一部の埋め込みモデルはバイナリ量子化後も品質が維持されるよう特別に学習されています。すべてのモデルがそうというわけではないので、結果は変わり得ます。一般的には OpenAI の 3072次元の大規模埋め込みモデルのような非常に大きなベクトルでは、そのために特別に学習していなくても、ある程度は機能するようです。
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • バイナリというのは、各次元を +1 または -1 に量子化するという意味です。
      データに FAISS インデックスを使い、積量子化（Product Quantization）を適用すると、バイナリ特徴量の場合は PQ768x1 のような方式でバイナリベクトルを試せますし、ベクトルのペアごとに4つの値のいずれかへ量子化する方式なども比較できます: https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • 参考までに、次元の呪いは厳密には、高次元空間が相対的に疎になり、その空間を埋めるにはデータが指数関数的に増える必要がある、という意味です。保存容量とは関係ありません。
      通常、ベクトルデータベースでは保存前にデータをより低次元の空間へ圧縮または射影するため、むしろこの状況は改善されます。

  • sqlite-vss のおかげで、RAG がどう動作するのかを学び、トイプロジェクトに実装できた。デバッグは少し難しかったが、きちんと合わせれば Ubuntu で問題なく動作し、今でも使っている
    制限の多い依存関係なしに、より良い新バージョンを作るというのはうれしい

  • 公開 SQLite API だけを使う予定なのか、それとも SQLite amalgamation に組み込む形を想定しているのか気になる
    こうした機能には確かに関心があるが、Wasm ベースの Go バインディングで SQLite とは別にどう配布するかを考える必要がある。これまでは Wasm の「動的リンク」よりずっと単純なので、C コードをすべてまとめて配布してきた
    またインクリメンタル BLOB 入出力に触れているが、すでに知っているとは思うものの、大きな BLOB はページの連結リストとして保存されるため、BLOB 入出力は決してランダムアクセスではない点に注意すべき

    • 公開 SQLite API だけを使う予定。なので amalgamation に組み込む必要はない
      wazero SQLite バインディングは本当に気に入っている。実際に 1) sqlite-vec 用の CGO バインディングと、2) go-sqlite3 から直接使えるカスタムの WASI ビルド sqlite-vec を提供する予定。もともとは、そのリポジトリのビルドスクリプトを使って sqlite3.wasm ファイルを作るつもりだった。プロジェクト側で直接サポートしたいなら、sqlite-vec.c/h ファイルを go-sqlite3/sqlite3 に入れるだけでよさそう
      インクリメンタル BLOB 入出力については苦労して学んだ。sqlite-vec のクエリ速度では明らかに制約要因になっている。チャンクサイズを比較的小さく、数 MB 程度に抑え、page_size を大きくするとバランスは悪くなかったが、特に page_size には副作用がある。PRAGMA mmap_size もページをメモリ上に保持してオーバーフロー参照を速くするようで大いに役立つが、当然ながらメモリ使用量はかなり増える。難しいバランスだ
    • この機能が Wasm Go バインディングに入るなら本当に興味がある

  • DuckDB が今日「Vector Similarity Search in DuckDB」拡張を発表した
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • これは楽しみ。以前作った小さな CDN ベースの HNSW プロジェクトを大きく単純化できそう: https://github.com/jasonjmcghee/portable-hnsw
      DuckDB VSS を使えば、埋め込みを作って DuckDB 形式で保存し、CDN 内で SQL を実行する形で処理できそう

  • こういうスタイルのプロジェクトは好き。とても特定の問題を狙ったオープンソースプロジェクトなのが良い
    TypeScript/Next.js/React エコシステムでも、技術的なニッチにすごく役立つ何かを作れないかと考え続けているが、まだひらめきはない

  • AI RAG アプリの https://github.com/rnadigital/agentcloud でエンドツーエンド自動化に Qdrant ベクトル DB を使ったので、後継作を作っていると聞いて期待している。いつ頃使える状態になるのか、クイックスタートガイドがあるのか気になる
    ブログ執筆も手伝えそう

    • v0.1.0 は 1か月後くらいを目標にしている。ドキュメントとクイックスタートガイドを多めに含める予定
      ドキュメント化されていない sqlite-vec pip パッケージがあるので、Python の「Agent Backend」から直接呼び出したいなら、今でも試せるとは思う

  • これは「README 駆動開発」がどんなものかと想像していたものにかなり近い。作者がドキュメントから始めたのか気になる

    • コードを先に始めた。拡張自体はすでに大部分を書き終えている[0]
      ただし「20% の労力で 80% を作った」状態なので、残り 20% であるエラー処理、ファズテスト、正確性テストが時間の 80% を占めそう。それでも、現在の sqlite-vss の状態についてすでに質問している人たちがいるので、この「作業中」のブログ記事でいくつかの疑問に答えられると思った
      ドキュメントから始めるというアイデアも気に入っている。特に SQLite 拡張では、SQL API がどう見えるか、つまりスカラー関数や仮想テーブルなどが本当に重要。ほとんどのコードを書く前に、sqlite-vec の SQL 部分がどうあるべきかはかなりスケッチしていた
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • 数か月前に SQLite-vss に上げた GitHub issue への答えに近いもののように思える。厳密にはその issue への回答ではないけれど
    https://github.com/asg017/sqlite-vss/issues/124

    • その通り。そこでフォローアップの返信ができていなくて申し訳ない
      実はそのチケットを最初に読んだとき、「sqlite-vss をどうすればもっと良くできるか」というラビットホールに入り込み、最終的に「sqlite-vec を作るべきだ」に行き着いた。この道に進む手助けをしてくれてありがとう
      sqlite-vec の組み込みバイナリ量子化を使えば、おおよそこんな感じでできる:
      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*/)))

  • ブラウザ内で実行する場合、sqlite-vec がブラウザネイティブの IndexedDB にデータを永続化できるのか気になります。あるいは、この部分はユーザーが自分で処理する必要があるのでしょうか。
    まだ考えていないという回答でも構いませんが、その方向性について考えを共有してもらえるとありがたいです。

    • 可能かもしれません。公式の SQLite WASM ビルドをベースにしているため、そこで提供されている同じ 永続化オプション[0] を利用できます。
      IndexedDB が具体的にサポートされているかは確かではありませんが、localStorage/OPFS VFS は利用できます。
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs