Đang phát triển sqlite-vec, phần mở rộng tìm kiếm vector mới cho SQLite

 (alexgarcia.xyz)
3 điểm bởi GN⁺ 2024-05-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Để giảm bớt các hạn chế của sqlite-vss hiện có, sqlite-vec đang được phát triển như một phần mở rộng tìm kiếm vector nhúng dựa trên C thuần, nhắm tới toàn bộ các môi trường nơi SQLite có thể chạy
  • Luồng sử dụng SQL được đơn giản hóa xoay quanh CREATE VIRTUAL TABLE, INSERT INTO, SELECT, đồng thời hỗ trợ tìm kiếm kiểu KNN và đầu vào vector dạng JSON/binary compact
  • Loại bỏ phụ thuộc vào Faiss, nhắm tới không chỉ Linux, macOS mà cả Windows, WebAssembly, di động và Raspberry Pi; kích thước binary cũng được kỳ vọng ở mức vài trăm KB, nhỏ hơn mức 3MB~5MB hiện tại
  • Lưu vector theo đơn vị chunk trong shadow table để giảm nhu cầu đưa toàn bộ lên RAM, và có thể dùng PRAGMA mmap_size để tăng tốc tìm kiếm dựa trên bộ nhớ
  • Phiên bản ban đầu chỉ cung cấp exhaustive full-scan, chưa có ANN; bản phát hành v0.1.0 dự kiến sẽ có sau khi hoàn tất 246 TODO trong sqlite-vec.c

Tìm kiếm vector SQLite mà sqlite-vec muốn thay đổi

  • sqlite-vec là một phần mở rộng SQLite mới được viết bằng C thuần, là dự án nhằm thay thế sqlite-vss đã được công bố vào tháng 2/2023
  • Phạm vi mục tiêu bao gồm các hàm SQL do người dùng định nghĩa để tìm kiếm vector nhanh, bảng ảo (virtual table), cũng như công cụ và tiện ích cho thao tác vector
    • Lượng tử hóa
    • Chuyển đổi JSON/BLOB/numpy
    • Số học vector
  • Người dùng có thể tạo và tìm kiếm kho vector chỉ bằng SQL thuần
    • Tạo bảng ảo cho vector bằng CREATE VIRTUAL TABLE
    • Chèn vector bằng INSERT INTO
    • Tìm kiếm kiểu KNN theo dạng SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ...
  • Đầu vào vector có thể dùng chuỗi JSON hoặc định dạng binary compact

C thuần và không phụ thuộc mở ra các môi trường chạy

  • sqlite-vec hướng tới một phần mở rộng C thuần không phụ thuộc, và lựa chọn này là điều kiện cốt lõi để mở rộng nền tảng được hỗ trợ
  • sqlite-vss hiện có, do phụ thuộc C++, chỉ hoạt động ổn định trên Linux và macOS, còn kích thước binary nằm trong khoảng 3MB~5MB
  • Phần mở rộng mới đặt mục tiêu chạy trong các môi trường sau
    • Linux
    • macOS
    • Windows
    • WebAssembly trong trình duyệt
    • Thiết bị di động
    • Thiết bị nhỏ như Raspberry Pi
  • Kích thước binary dự kiến nằm trong khoảng vài trăm KB

Điều chỉnh mức dùng bộ nhớ và tốc độ tìm kiếm

  • sqlite-vec kiểm soát mức dùng bộ nhớ bằng cách chia vector để lưu vào các chunk bên trong shadow table
    • Khi tìm kiếm KNN, không đưa tất cả vector lên RAM cùng lúc mà đọc theo từng chunk
    • Không cần giữ toàn bộ vector thường trú trong bộ nhớ
  • Nếu cần tốc độ dựa trên bộ nhớ, có thể dùng PRAGMA mmap_size của SQLite để làm tìm kiếm KNN nhanh hơn

Tính năng vector mới và giới hạn ban đầu

  • sqlite-vec muốn hỗ trợ tốt hơn các tính năng sau, phản ánh dòng chảy của công cụ và nghiên cứu tìm kiếm vector gần đây
  • Những tính năng này là nền tảng để điều chỉnh tinh tế hơn tốc độ, độ chính xác và dung lượng đĩa của vector
  • sqlite-vec ban đầu chỉ hỗ trợ tìm kiếm vector exhaustive full-scan
    • Ban đầu không có tùy chọn “approximate nearest neighbors”
    • IVF và HNSW là các tính năng hy vọng sẽ bổ sung trong tương lai

Cấu hình demo trên trình duyệt

  • Demo sử dụng sqlite-vec chạy trong trình duyệt
  • Cấu hình có thể kiểm tra trong công cụ dành cho nhà phát triển như sau
  • Trong movies.bit.db, bảng articles chứa overview của 4.800 bộ phim dựa trên metadata phim TMDB
  • Bảng ảo riêng vec_movies là chỉ mục vector của các embedding overview đó

Dữ liệu demo và luồng tìm kiếm KNN

  • Bảng articles có các cột như title, release_date, overview
  • Cột overview chứa cốt truyện phim dưới dạng câu ngắn, và là đối tượng được embedding trong demo
  • Bảng ảo vec_movies lưu embedding của articles.overview trong cột overview_embeddings
    • Vector là binary vector 768 chiều
    • Kích thước lưu trữ là 768 / 8 = 96, tức 96 byte
  • Khi người dùng chọn phim bằng nút radio, ID phim được chọn sẽ được điền vào tham số :selected_movie của truy vấn SQL KNN
  • Kết quả tìm kiếm là 10 bộ phim gần nhất với phim đã chọn
    • Vì là binary vector, phép tính khoảng cách dùng hamming distance
    • Kết quả gần nhất luôn là chính bộ phim đó và khoảng cách là 0
  • Kết quả embedding các cốt truyện một câu ngắn và tập dữ liệu phim nhỏ không có chất lượng cao nhất; binary quantization cũng hy sinh thêm chất lượng, nhưng trọng tâm là cho thấy tìm kiếm vector nhanh và “đủ tốt” ngay trong trình duyệt
  • Để kiểm tra hoạt động bên trong, chỉ cần thêm EXPLAIN QUERY PLAN trước SELECT; có thể thấy “index” 0:knn mà vec_movies sử dụng

Hạn chế của sqlite-vss và phụ thuộc Faiss

  • Việc phát triển và áp dụng sqlite-vss gặp nhiều trở ngại
    • Chỉ hoạt động trên Linux và macOS, không hỗ trợ Windows, WASM, thiết bị di động, v.v.
    • Lưu toàn bộ vector trong bộ nhớ
    • Có lỗi và vấn đề liên quan đến transaction
    • Biên dịch rất khó và mất nhiều thời gian
    • Thiếu các thao tác vector phổ biến như scalar/binary quantization
  • Gần như hầu hết các vấn đề này bắt nguồn từ phụ thuộc vào Faiss
  • Một số vấn đề có thể giải quyết nếu đầu tư nhiều thời gian và công sức, nhưng không ít vấn đề có thể bị chặn bởi Faiss
  • Một giải pháp cấp thấp không phụ thuộc trở thành lựa chọn hấp dẫn, và sqlite-vec được bắt đầu từ nhận định rằng bản thân tìm kiếm vector không quá phức tạp

Trạng thái phát hành và lời kêu gọi tài trợ

  • Các chức năng cốt lõi của sqlite-vec đã hoạt động, nhưng xử lý lỗi và kiểm thử vẫn còn rất thiếu
  • Trong tệp sqlite-vec.c còn 246 TODO
    • 191 todo_assert()
    • 41 chú thích // TODO
    • 14 todo panic
    • Tiến độ tổng thể được hiển thị là 0/246, 0% theo sqlite-vec v0
  • Khi hoàn tất 246 TODO, bản phát hành v0.1.0 đầu tiên dự kiến sẽ ra mắt
    • Tài liệu
    • Demo
    • Binding
    • Các thành phần khác sẽ được cung cấp cùng
  • Mục tiêu thời gian là khoảng một tháng, nhưng không phải lịch trình đã được xác định chắc chắn
  • Đang tìm kiếm tài trợ từ các công ty quan tâm đến thành công của sqlite-vec; có thể liên hệ qua email

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-04
Ý kiến trên Hacker News

  • Tôi là tác giả — nếu có câu hỏi thì tôi sẽ trả lời. Đây mang tính chất “đang làm một dự án mới” hơn là một bản phát hành chính thức, và bản thân extension cũng vẫn đang được phát triển. Link dự án là https://github.com/asg017/sqlite-vec
    Tôi đã có hình dung khá cụ thể về v0.1.0 của extension này sẽ trông như thế nào, nhưng có lẽ sẽ cần thêm vài tuần nữa để tới đó. Bài viết này chủ yếu nhằm báo cho người dùng sqlite-vss, extension tìm kiếm vector cho SQLite mà tôi từng làm trước đây, biết điều gì sẽ đến tiếp theo; khi sẵn sàng sẽ có một bản phát hành lớn hơn
    Nhìn chung tôi rất hào hứng vì sẽ có một phương án tìm kiếm vector dễ nhúng. Điều đặc biệt hay là nó chạy được trên mọi hệ điều hành, WASM, thiết bị di động, Raspberry Pi, v.v.; cá nhân tôi đang thử chạy một ứng dụng tìm kiếm ngữ nghĩa nhỏ trên Beepy nên thấy khá thú vị
    [0] https://beepy.sqfmi.com/

    • Tôi tò mò nó hỗ trợ những hàm khoảng cách nào. Có vẻ như đã hỗ trợ vector nhị phân, nên tôi muốn biết có hỗ trợ khoảng cách Hamming không
      Tôi cũng muốn biết hiệu năng so với sqlite-vss. Tôi tò mò các số liệu profiling cả về tốc độ truy vấn lẫn mức dùng bộ nhớ
      Nhìn chung trông thật sự tuyệt vời, và tôi thích hướng đi này
      Cách tiếp cận ban đầu là sqlite-vec chỉ hỗ trợ tìm kiếm vector bằng quét toàn bộ vét cạn, chưa có tùy chọn láng giềng gần đúng gần nhất (ANN), nhưng sau này muốn thêm IVF và HNSW — tôi thấy đúng 1000%. Tôi thích việc không làm nó phức tạp quá mức ngay từ đầu
      Tôi từng ra mắt tìm kiếm vector trên thiết bị, và với tổ hợp vector nhị phân 128-bit cùng khoảng cách Hamming, nó đủ nhanh để chạy tìm kiếm khoảng cách hoàn toàn brute-force trên hơn 200.000 mục trong cơ sở dữ liệu cho từng khung hình camera. Trên điện thoại giá rẻ vẫn đạt hơn 10fps, còn trên điện thoại tốt thì rất mượt. Có rất nhiều trường hợp đáng ngạc nhiên là brute-force đã đủ
      Tuy vậy, khi triển khai các thuật toán ANN như HNSW, sẽ rất hay nếu có thể xử lý theo mô hình chỉ mục bảng. Khi đó việc chuyển từ tìm kiếm brute-force sang ANN sẽ đơn giản như tạo một chỉ mục trên bảng, và việc thử nghiệm nhiều thuật toán ANN cùng tham số cũng có thể thực hiện bằng cách điều chỉnh tham số tạo chỉ mục. Có thể bạn đã đi theo hướng đó rồi, nhưng tôi vẫn nhắc tới phòng khi hữu ích
    • Tôi tò mò liệu có kế hoạch triển khai các chiến lược lập chỉ mục như HNSW không. Quét tuyến tính rõ ràng là một điểm khởi đầu tốt, và nếu dữ liệu được sắp xếp theo thứ tự hợp lý, chẳng hạn dưới 10MB, thì có thể đủ nhanh, nên tôi không thấy đó là lý do để chặn bản beta
      Tôi cũng tò mò liệu nó có được build cùng sqlite-httpvfs không. Có vẻ rất hợp với dự án này: https://github.com/phiresky/sql.js-httpvfs
    • Tôi thật sự thích việc có Wasm. Thông thường trong trình duyệt rất khó dùng tìm kiếm vector bên trong SQLite
      Tôi cũng tò mò liệu bạn đã cân nhắc làm cho nó tương thích cú pháp với pgvector để có một DSL vector SQL chung chưa. Tôi đoán nhược điểm có lẽ không nhỏ hơn ưu điểm nhiều lắm, nhưng vẫn muốn biết có khả thi không
    • Có thể triển khai cái này bằng Rust không? Tôi cũng tò mò dự án sqlite-loadable-rs có hỗ trợ WASM không
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • Trước đây tôi đã thêm sqlite-vss vào Langchain như một vector store. Bạn có cho rằng dự án mới này đã đủ trưởng thành để thêm vào Langchain chưa, hay nên chờ thêm một chút?
      sqlite-vss hiện đã được dùng tốt trong một số dự án

  • Tôi thấy khó hiểu đoạn “vector nhị phân 768 chiều nên chiếm 96 byte (768 / 8 = 96)”. Vấn đề mà hầu hết vector store gặp phải là lời nguyền chiều không gian, và tôi nghĩ đây là vấn đề trước cả lập chỉ mục
    Ban đầu tôi tưởng có lẽ ý là 768 chiều * 8 byte (f64), tức 6144 byte. Thông thường người ta chấp nhận một chút mất mát để giảm xuống f32 hoặc f16, hoặc biểu diễn nhỏ hơn nữa
    Nếu có cách đưa 768 chiều vào 96 byte bằng nén hay kiểu phân bổ khấu hao giống trie, tôi muốn nghe thêm trong một bài riêng. Nếu coi mỗi chiều là 1 bit thì tôi hiểu, nhưng khi đó tôi vẫn còn thắc mắc về chất lượng tìm kiếm

    • Tôi là tác giả — ở đây vector nhị phân nghĩa là lượng tử hóa mỗi chiều thành 1 bit. Thông thường cần 4 * số chiều byte cho mỗi vector. Ở đây 4 là sizeof(float)
      Một số mô hình embedding như nomic v1.5[0] hay mô hình mới của mixedbread[1] được huấn luyện đặc biệt để vẫn giữ chất lượng sau lượng tử hóa nhị phân. Không phải mô hình nào cũng như vậy, nên kết quả có thể khác nhau. Nói chung với các vector rất lớn, như mô hình embedding lớn 3072 chiều của OpenAI, dường như nó vẫn hoạt động ở mức nào đó dù không được huấn luyện riêng cho việc này
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • Nhị phân ở đây nghĩa là lượng tử hóa mỗi chiều thành +1 hoặc -1
      Nếu dùng chỉ mục FAISS cho dữ liệu và áp dụng Product Quantization, với đặc trưng nhị phân bạn có thể thử vector nhị phân theo kiểu PQ768x1, và cũng có thể so sánh các cách như lượng tử hóa mỗi cặp vector thành một trong bốn giá trị: https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • Nhân tiện, nói chính xác thì lời nguyền chiều không gian có nghĩa là không gian nhiều chiều trở nên tương đối thưa thớt, và để lấp đầy không gian đó thì dữ liệu phải tăng theo cấp số nhân. Nó không liên quan đến dung lượng lưu trữ
      Thông thường trong cơ sở dữ liệu vector, dữ liệu được nén hoặc chiếu xuống không gian có số chiều thấp hơn trước khi lưu, nên tình huống này thực ra được cải thiện

  • Nhờ sqlite-vss, tôi đã học được cách RAG hoạt động và có thể triển khai nó trong một dự án đồ chơi. Việc debug hơi khó, nhưng khi cấu hình đúng thì nó chạy hoàn hảo trên Ubuntu, và tôi vẫn đang dùng đến giờ
    Thật vui khi có người làm một phiên bản mới tốt hơn mà không có các phụ thuộc hạn chế

  • Tôi tò mò liệu dự định chỉ dùng SQLite API công khai, hay hình dung theo kiểu gắn vào SQLite amalgamation
    Tôi chắc chắn quan tâm đến tính năng kiểu này, nhưng cần suy nghĩ xem sẽ phân phối nó riêng với SQLite như thế nào trong binding Go dựa trên Wasm. Cho đến nay, cách làm của tôi là đóng gói toàn bộ mã C để phân phối, vì đơn giản hơn nhiều so với “liên kết động” trong Wasm
    Ngoài ra, bạn có nhắc đến I/O BLOB tăng dần; chắc bạn đã biết, nhưng cần lưu ý rằng vì BLOB lớn được lưu dưới dạng danh sách liên kết các trang, I/O BLOB tuyệt đối không phải là truy cập ngẫu nhiên

    • Tôi dự định chỉ dùng API SQLite công khai. Vì vậy không cần gắn vào amalgamation
      Tôi rất thích binding SQLite của wazero. Thực tế tôi dự định cung cấp 1) binding CGO cho sqlite-vec và 2) một bản build sqlite-vec WASI tùy chỉnh có thể dùng trực tiếp trong go-sqlite3. Ban đầu tôi định dùng script build của repo đó để tạo file sqlite3.wasm. Nếu muốn hỗ trợ trực tiếp trong dự án, có lẽ chỉ cần đưa các file sqlite-vec.c/h vào go-sqlite3/sqlite3 là được
      I/O BLOB tăng dần là thứ tôi đã học được theo cách khá vất vả. Nó rõ ràng là yếu tố giới hạn tốc độ truy vấn của sqlite-vec. Giữ kích thước chunk tương đối nhỏ, ở mức vài MB thấp, và tăng page_size thì đạt được cân bằng khá ổn, nhưng đặc biệt page_size có các tác dụng phụ. PRAGMA mmap_size cũng giúp rất nhiều, vì dường như giữ các trang trong bộ nhớ và làm cho việc tra cứu overflow nhanh hơn, nhưng dĩ nhiên mức dùng bộ nhớ tăng lên nhiều. Đây là một sự cân bằng khó
    • Nếu tính năng này được đưa vào binding Wasm Go thì tôi thật sự quan tâm

  • Hôm nay DuckDB đã công bố extension “Vector Similarity Search in DuckDB”
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • Cái này đáng mong đợi. Có vẻ nó có thể đơn giản hóa đáng kể dự án HNSW nhỏ dựa trên CDN mà tôi từng làm: https://github.com/jasonjmcghee/portable-hnsw
      Với DuckDB VSS, có vẻ có thể embedding rồi lưu ở định dạng DuckDB, sau đó chạy SQL ngay trong CDN

  • Tôi thích những dự án kiểu này. Thích vì đây là một dự án mã nguồn mở nhắm vào một vấn đề rất cụ thể
    Tôi vẫn tiếp tục nghĩ xem liệu trong hệ sinh thái TypeScript/Next.js/React có thể tạo ra thứ gì đó rất hữu ích cho một ngách kỹ thuật hay không, nhưng vẫn chưa nảy ra cảm hứng

  • Trong ứng dụng AI RAG https://github.com/rnadigital/agentcloud, chúng tôi đã dùng Qdrant vector DB cho tự động hóa end-to-end, nên tôi rất mong chờ phần tiếp theo. Tôi muốn biết khi nào nó sẵn sàng để dùng và có hướng dẫn quick start hay không
    Tôi cũng có thể giúp viết blog

    • v0.1.0 đang được nhắm tới trong khoảng một tháng nữa. Tôi dự định đưa vào nhiều tài liệu và hướng dẫn quick start
      Có một package pip sqlite-vec chưa được ghi tài liệu, nên nếu muốn gọi trực tiếp từ “Agent Backend” trong Python thì có lẽ hiện giờ bạn cũng có thể thử

  • Cái này khá giống với những gì tôi tưởng tượng về “phát triển dựa trên README”. Tôi tò mò liệu tác giả có bắt đầu từ tài liệu hay không

    • Tôi bắt đầu từ code trước. Bản thân extension phần lớn đã được viết xong rồi[0]
      Tuy nhiên hiện đang ở trạng thái “tạo ra 80% bằng 20% công sức”, nên 20% còn lại gồm xử lý lỗi, fuzz testing, kiểm thử độ chính xác có lẽ sẽ chiếm 80% thời gian. Dù vậy, mọi người đã hỏi về tình trạng hiện tại của sqlite-vss, nên tôi nghĩ bài blog “đang làm” này có thể trả lời một vài câu hỏi
      Tôi cũng thích ý tưởng bắt đầu từ tài liệu. Đặc biệt với extension SQLite, SQL API trông như thế nào, tức là scalar function và virtual table, v.v., thật sự rất quan trọng. Trước khi viết phần lớn code, tôi đã phác thảo khá nhiều về phần SQL của sqlite-vec nên trông như thế nào
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • Có vẻ đây gần như là câu trả lời cho một GitHub issue tôi đã mở trên SQLite-vss vài tháng trước. Nói chính xác thì không phải là phản hồi cho issue đó, nhưng
    https://github.com/asg017/sqlite-vss/issues/124

    • Đúng vậy. Xin lỗi vì tôi đã không phản hồi tiếp ở đó
      Thực ra khi đọc ticket đó lần đầu, tôi đã rơi vào một hố thỏ kiểu “làm sao để cải thiện sqlite-vss”, và cuối cùng dẫn đến “mình nên tạo sqlite-vec”. Cảm ơn vì đã giúp tôi đi theo hướng này
      Với lượng tử hóa nhị phân tích hợp của sqlite-vec, bạn có thể làm đại khái như sau:
      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*/)))

  • Tôi thắc mắc liệu khi chạy trong trình duyệt, sqlite-vec có thể lưu bền vững dữ liệu vào IndexedDB native của trình duyệt hay không. Hay tôi muốn biết phần này người dùng phải tự xử lý
    Dù câu trả lời là chưa nghĩ đến, nếu có thể chia sẻ suy nghĩ theo hướng đó thì tôi rất cảm ơn

    • Có thể là được. Vì dựa trên bản build SQLite WASM chính thức, nên có thể dùng cùng các tùy chọn lưu bền vững[0] mà nó cung cấp
      Tôi không chắc IndexedDB có được hỗ trợ cụ thể hay không, nhưng có thể dùng localStorage/OPFS VFS
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs