Novo extensão de busca vetorial para SQLite, `sqlite-vec`, está em desenvolvimento

 (alexgarcia.xyz)
3 pontos por GN⁺ 2024-05-04 | 1 comentários | Compartilhar no WhatsApp
  • Para reduzir as limitações do sqlite-vss, o sqlite-vec está sendo desenvolvido como uma extensão embarcada de busca vetorial em C puro, visando praticamente todos os ambientes onde o SQLite roda
  • O fluxo de uso em SQL é simplificado em torno de CREATE VIRTUAL TABLE, INSERT INTO e SELECT, com suporte a busca no estilo KNN e entrada de vetores em JSON e formato binário compacto
  • Ao remover a dependência de Faiss, o projeto mira não só Linux e macOS, mas também Windows, WebAssembly, dispositivos móveis e Raspberry Pi, com expectativa de um binário de algumas centenas de KB, menor que os 3MB~5MB anteriores
  • Os vetores são armazenados em chunks dentro de uma shadow table, reduzindo a necessidade de carregar tudo na RAM, e PRAGMA mmap_size pode acelerar buscas baseadas em memória
  • A versão inicial terá apenas full-scan exaustivo, sem ANN, e o lançamento do v0.1.0 está previsto para depois que os 246 TODOs em sqlite-vec.c forem concluídos

O que o sqlite-vec quer mudar na busca vetorial do SQLite

  • sqlite-vec é uma nova extensão do SQLite escrita em C puro e um projeto que busca substituir o sqlite-vss, lançado em fevereiro de 2023
  • O escopo inclui funções SQL definidas pelo usuário para busca vetorial rápida, tabelas virtuais (virtual tables), ferramentas e utilitários para operações com vetores
    • quantização
    • conversão entre JSON/BLOB/numpy
    • aritmética vetorial
  • O usuário pode criar e consultar um armazenamento vetorial usando apenas SQL
    • criar uma tabela virtual para vetores com CREATE VIRTUAL TABLE
    • inserir vetores com INSERT INTO
    • fazer busca no estilo KNN com SELECT ... WHERE sample_embedding MATCH ... ORDER BY distance LIMIT ...
  • A entrada de vetores pode usar strings JSON ou formato binário compacto

Ambientes de execução viabilizados por C puro e ausência de dependências

  • O sqlite-vec tem como meta ser uma extensão em C puro sem dependências, e essa escolha é a condição central para ampliar as plataformas suportadas
  • O sqlite-vss anterior, por causa da dependência de C++, só funcionava de forma estável em Linux e macOS, com binários na faixa de 3MB~5MB
  • A nova extensão pretende rodar nos seguintes ambientes
    • Linux
    • macOS
    • Windows
    • WebAssembly no navegador
    • dispositivos móveis
    • dispositivos pequenos como Raspberry Pi
  • O tamanho esperado do binário é de algumas centenas de KB

Controle de uso de memória e velocidade de busca

  • O sqlite-vec controla o uso de memória armazenando os vetores divididos em chunks dentro de uma shadow table
    • em buscas KNN, os vetores são lidos por chunk, sem carregar todos de uma vez na RAM
    • não é necessário manter o conjunto inteiro de vetores residente em memória
  • Se for necessário desempenho baseado em memória, é possível usar PRAGMA mmap_size do SQLite para acelerar a busca KNN

Novos recursos vetoriais e limitações iniciais

  • O sqlite-vec busca oferecer suporte melhor aos recursos abaixo, refletindo ferramentas e pesquisas recentes de busca vetorial
  • Esses recursos formam a base para ajustar com mais precisão a velocidade, a precisão e o uso de disco dos vetores
  • O sqlite-vec inicial suporta apenas busca vetorial por full-scan exaustivo
    • a opção de “approximate nearest neighbors” não estará presente no começo
    • IVF e HNSW são recursos desejados para adição futura

Estrutura da demo no navegador

  • A demo usa sqlite-vec rodando no navegador
  • A configuração que pode ser vista nas ferramentas de desenvolvedor inclui
    • sqlite3.wasm não otimizado de 5.9MB
    • a build oficial SQLite WASM compilada com sqlite-vec
    • um banco de dados SQLite movies.bit.db de 2.6MB
  • O movies.bit.db contém 4.800 overviews de filmes na tabela articles, com base em metadados de filmes da TMDB
  • A tabela virtual separada vec_movies é o índice vetorial dos embeddings desses overviews

Dados da demo e fluxo de busca KNN

  • A tabela articles tem colunas como title, release_date e overview
  • A coluna overview contém o resumo do enredo dos filmes em frases curtas e é o alvo dos embeddings na demo
  • A tabela virtual vec_movies armazena os embeddings de articles.overview na coluna overview_embeddings
    • os vetores são binary vectors de 768 dimensões
    • o tamanho armazenado é 768 / 8 = 96, ou seja, 96 bytes
  • Quando o usuário seleciona um filme com o botão de opção, o ID do filme escolhido preenche o parâmetro :selected_movie da consulta SQL KNN
  • O resultado da busca são os 10 filmes mais próximos do filme selecionado
    • como se trata de binary vector, o cálculo de distância usa hamming distance
    • o resultado mais próximo é sempre o próprio filme, com distância 0
  • Os embeddings de resumos curtos em frase única e de um dataset pequeno de filmes não têm a melhor qualidade possível, e a quantização binária sacrifica ainda mais a qualidade, mas o foco é mostrar uma busca vetorial rápida e “boa o suficiente” dentro do navegador
  • Para verificar o funcionamento interno, basta colocar EXPLAIN QUERY PLAN antes de SELECT, e será possível ver o “index” 0:knn usado por vec_movies

Limitações do sqlite-vss e dependência de Faiss

  • Houve vários obstáculos no desenvolvimento e na adoção do sqlite-vss
    • só funcionava em Linux e macOS, sem suporte a Windows, WASM, dispositivos móveis etc.
    • armazenava todos os vetores na memória
    • havia bugs e problemas relacionados a transações
    • era muito difícil e demorado de compilar
    • faltavam operações vetoriais comuns, como quantização escalar/binária
  • Quase todos esses problemas vinham da dependência de Faiss
  • Alguns deles talvez pudessem ser resolvidos com muito tempo e esforço, mas vários continuariam bloqueados por causa do Faiss
  • A partir da avaliação de que uma solução de baixo nível sem dependências era uma opção atraente e de que a busca vetorial em si não é tão complexa, surgiu o sqlite-vec

Estado do lançamento e pedido de patrocínio

  • Os recursos centrais do sqlite-vec já funcionam, mas o tratamento de erros e os testes ainda são muito insuficientes
  • Ainda restam 246 TODOs no arquivo sqlite-vec.c
    • 191 todo_assert()
    • 41 comentários // TODO
    • 14 todo panic
    • o progresso total aparece como 0/246, 0%, com base no sqlite-vec v0
  • Quando os 246 TODOs forem concluídos, sairá o primeiro lançamento v0.1.0
    • documentação
    • demo
    • bindings
    • outros componentes devem ser fornecidos junto
  • A meta é algo como cerca de um mês, mas sem cronograma confirmado
  • O projeto está buscando patrocínio de empresas interessadas no sucesso do sqlite-vec, com contato por e-mail

Leituras relacionadas

1 comentários

 
GN⁺ 2024-05-04
Comentários do Hacker News

  • Sou o autor — respondo perguntas, se houver. Isto tem mais o caráter de “estou trabalhando em um projeto novo” do que de um lançamento oficial, e a extensão em si ainda está em desenvolvimento. Link do projeto: https://github.com/asg017/sqlite-vec
    Já tenho uma ideia bem concreta de como será a v0.1.0 desta extensão, mas provavelmente ainda vai levar mais algumas semanas até chegar lá. Este post teve muito o objetivo de avisar aos usuários do sqlite-vss, a extensão anterior de busca vetorial para SQLite que criei, o que vem a seguir, e deve haver um lançamento maior quando estiver pronto
    No geral, estou muito animado por ter uma alternativa de busca vetorial fácil de embutir. É especialmente ótimo que rode em todos os sistemas operacionais, WASM, dispositivos móveis, Raspberry Pi etc., e pessoalmente estou me divertindo tentando rodar um pequeno app de busca semântica no Beepy
    [0] https://beepy.sqfmi.com/

    • Tenho curiosidade sobre quais funções de distância ele suporta. Já parece suportar vetores binários, então queria saber se distância de Hamming também é suportada
      Também queria saber como fica o desempenho em comparação com o sqlite-vss. Tenho curiosidade sobre números de profiling tanto de velocidade de consulta quanto de uso de memória
      No geral, isso parece realmente excelente, e gosto dessa direção
      Acho 1000% certa a abordagem de o sqlite-vec inicialmente suportar apenas busca vetorial por varredura completa e não ter opção de vizinho mais próximo aproximado (ANN), mas depois querer adicionar IVF e HNSW. Gosto do fato de não tornar tudo excessivamente complexo logo de início
      Já lancei busca vetorial on-device antes, e a combinação de vetores binários de 128 bits com distância de Hamming era rápida o suficiente para rodar uma busca exaustiva completa de distância a cada frame da câmera, mesmo com mais de 200 mil itens no banco de dados. Em celulares baratos passava de 10fps, e em aparelhos bons ficava bem fluido. É surpreendente quantas vezes força bruta é suficiente
      Dito isso, ao implementar algoritmos ANN como HNSW, seria legal se desse para tratar isso dentro do paradigma de índice de tabela. Assim, mudar de busca por força bruta para ANN ficaria tão simples quanto criar um índice na tabela, e também daria para experimentar vários algoritmos ANN e parâmetros ajustando os parâmetros de criação do índice. Talvez isso já esteja indo nessa direção, mas achei melhor mencionar
    • Fico curioso se há planos de implementar também estratégias de indexação como HNSW. Varredura linear obviamente é um ótimo ponto de partida, e se os dados estiverem ordenados de forma razoável e tiverem, por exemplo, menos de 10MB, isso pode ser rápido o bastante, então não parece haver motivo para impedir um lançamento beta
      Também queria saber se isso compila junto com sqlite-httpvfs. Parece combinar bem com este projeto: https://github.com/phiresky/sql.js-httpvfs
    • A parte de Wasm é realmente ótima. Normalmente era difícil usar busca vetorial dentro do SQLite no navegador
      Também queria saber se você pensou em torná-lo compatível em sintaxe com pgvector para uma SQL vector DSL comum. Imagino que as desvantagens não sejam tão maiores que as vantagens, mas queria saber se isso é possível
    • Dá para implementar isso em Rust? Também queria saber se o projeto sqlite-loadable-rs suporta WASM
      https://observablehq.com/@asg017/introducing-sqlite-loadable...
    • Eu tinha adicionado o sqlite-vss ao Langchain como vector store no passado. Você acha que este novo projeto já está maduro o suficiente para também ser adicionado ao Langchain, ou seria melhor esperar mais um pouco?
      O sqlite-vss já está sendo usado bem em alguns projetos

  • A parte que diz “um vetor binário de 768 dimensões ocupa 96 bytes (768 / 8 = 96)” me confundiu. Justamente esse tipo de coisa é o problema da maldição da dimensionalidade que a maioria dos vector stores enfrenta, e eu vejo isso como um problema anterior à indexação
    Achei que talvez quisesse dizer 768 dimensões * 8 bytes (f64), ou seja, 6144 bytes. Normalmente se reduz isso para f32, f16 ou representações ainda menores aceitando alguma perda
    Se existir alguma forma de colocar 768 dimensões em 96 bytes usando compressão ou alguma técnica de colapso parecida com trie, eu gostaria muito de ler um post separado sobre isso. Se cada dimensão estiver sendo tratada como 1 bit, eu entendo, mas mesmo assim continuo com dúvidas sobre a qualidade da busca

    • Sou o autor — aqui, vetor binário significa que cada dimensão é quantizada em 1 bit. Normalmente, são necessários 4 * número de dimensões bytes por vetor. Aqui, 4 é sizeof(float)
      Alguns modelos de embedding, como o nomic v1.5[0] e o novo modelo da mixedbread[1], são treinados especificamente para manter a qualidade mesmo após quantização binária. Nem todos os modelos são assim, então os resultados podem variar. Em geral, com vetores muito grandes, como o grande modelo de embeddings de 3072 dimensões da OpenAI, isso parece funcionar até certo ponto mesmo sem treinamento específico para isso
      [0] https://twitter.com/nomic_ai/status/1769837800793243687
      [1] https://www.mixedbread.ai/blog/binary-mrl
    • Binário significa quantizar cada dimensão em +1 ou -1
      Se você usar um índice FAISS nos dados e aplicar Product Quantization, no caso de características binárias dá para testar vetores binários de um jeito como PQ768x1, e também comparar abordagens que quantizam cada par de vetores em um de quatro valores possíveis: https://github.com/facebookresearch/faiss/wiki/The-index-fac...
    • Só como referência, a maldição da dimensionalidade significa, em termos estritos, que espaços de alta dimensão se tornam relativamente esparsos e que a quantidade de dados necessária para preencher esse espaço cresce exponencialmente. Isso não tem relação com capacidade de armazenamento
      Normalmente, em bancos de dados vetoriais, os dados são comprimidos ou projetados para um espaço de dimensão menor antes do armazenamento, então, na verdade, essa situação tende a melhorar

  • Graças ao sqlite-vss, consegui aprender como o RAG funciona e implementar isso em projetos de brinquedo. Depurar foi um pouco difícil, mas, quando tudo foi ajustado corretamente, funcionou sem problemas no Ubuntu, e ainda uso até hoje
    Fico feliz em ver que estão criando uma nova versão melhor, sem dependências limitantes

  • Tenho curiosidade se o plano é usar apenas a API pública do SQLite ou se vocês imaginam algo acoplado ao amalgamation do SQLite
    Com certeza tenho interesse nesse tipo de funcionalidade, mas, no caso de bindings de Go baseados em Wasm, preciso pensar em como distribuir isso separadamente do SQLite. Até agora, tenho empacotado todo o código C junto, porque isso é muito mais simples do que “linkagem dinâmica” em Wasm
    Você também mencionou E/S incremental de BLOB, mas, como talvez já saiba, BLOBs grandes são armazenados como uma lista encadeada de páginas, então a E/S de BLOB nunca é realmente de acesso aleatório

    • O plano é usar apenas a API pública do SQLite. Então não deve ser necessário acoplar ao amalgamation
      Gosto muito do binding de SQLite para wazero. Na verdade, o plano é oferecer 1) bindings CGO para o sqlite-vec e 2) um build WASI customizado do sqlite-vec que possa ser usado diretamente no go-sqlite3. Originalmente, eu pensava em usar os scripts de build daquele repositório para gerar o arquivo sqlite3.wasm. Se você quiser dar suporte direto a isso no projeto, talvez baste colocar os arquivos sqlite-vec.c/h em go-sqlite3/sqlite3
      Aprendi da maneira difícil sobre E/S incremental de BLOB. Isso é claramente um fator limitante na velocidade de consulta do sqlite-vec. Manter o tamanho dos chunks relativamente pequeno, na faixa de poucos MB, e aumentar o page_size deu um equilíbrio razoável, mas há efeitos colaterais, especialmente com o page_size. PRAGMA mmap_size também ajuda bastante, aparentemente mantendo páginas na memória e acelerando buscas por overflow, mas, claro, isso aumenta muito o uso de memória. É um equilíbrio difícil
    • Eu realmente teria interesse se isso entrasse no binding Wasm de Go

  • O DuckDB anunciou hoje a extensão “Vector Similarity Search in DuckDB”
    https://duckdb.org/2024/05/03/vector-similarity-search-vss.h...

    • Isso parece promissor. Acho que pode simplificar bastante um pequeno projeto de HNSW baseado em CDN que fiz antes: https://github.com/jasonjmcghee/portable-hnsw
      Com o DuckDB VSS, parece que daria para gerar embeddings, armazená-los no formato do DuckDB e depois processar tudo executando SQL dentro da CDN

  • Gosto desse tipo de projeto. É um projeto open source voltado para um problema bem específico, e isso é ótimo
    Continuo pensando se também seria possível criar algo muito útil para um nicho técnico no ecossistema TypeScript/Next.js/React, mas ainda não tive inspiração

  • Usei o banco vetorial Qdrant para automação de ponta a ponta no app de AI RAG https://github.com/rnadigital/agentcloud, então estou animado em ver uma continuação. Tenho curiosidade sobre quando isso estará pronto para uso e se haverá um guia de início rápido
    Talvez eu também possa ajudar a escrever posts no blog

    • A meta para a v0.1.0 é daqui a cerca de um mês. Pretendo incluir bastante documentação e guias de início rápido
      Existe um pacote pip sqlite-vec não documentado, então, se você quiser chamá-lo diretamente a partir de um “Agent Backend” em Python, talvez já dê para experimentar agora

  • Isso é bem parecido com o que eu imaginava que seria “desenvolvimento guiado por README”. Fiquei curioso se o autor começou pela documentação

    • Comecei pelo código. A extensão em si já está praticamente toda escrita[0]
      Só que estou naquele ponto clássico de “80% feito com 20% do esforço”, e os 20% restantes — tratamento de erros, fuzz testing e testes de correção — provavelmente vão consumir 80% do tempo. Ainda assim, como as pessoas já estão fazendo perguntas sobre o estado atual do sqlite-vss, achei que este post de blog de “trabalho em andamento” poderia responder algumas delas
      Também gosto da ideia de começar pela documentação. Especialmente em extensões para SQLite, é muito importante como a API SQL vai se parecer, ou seja, funções escalares, tabelas virtuais etc. Antes de escrever a maior parte do código, rabisquei bastante como a parte SQL do sqlite-vec deveria ser
      [0] https://github.com/asg017/sqlite-vec/blob/main/sqlite-vec.c

  • Isso parece próximo de uma resposta para uma issue que abri no GitHub do SQLite-vss alguns meses atrás. Tecnicamente não é uma resposta direta àquela issue, mas chega perto
    https://github.com/asg017/sqlite-vss/issues/124

    • Sim. Desculpe por não ter conseguido responder lá depois
      Na verdade, quando li aquele ticket pela primeira vez, acabei entrando numa verdadeira toca de coelho sobre “como tornar o sqlite-vss melhor”, e isso acabou levando à conclusão de que eu deveria criar o sqlite-vec. Obrigado por me ajudar a seguir por esse caminho
      Com a quantização binária embutida do sqlite-vec, dá para fazer algo mais ou menos assim:
      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*/)))

  • Tenho curiosidade se, ao rodar no navegador, o sqlite-vec consegue persistir dados no IndexedDB nativo do navegador. Ou se essa parte precisa ser tratada pelo próprio usuário
    Mesmo que a resposta seja que isso ainda não foi pensado, eu agradeceria se você pudesse compartilhar como está pensando nessa direção

    • Pode ser possível. Como ele é baseado no build oficial do SQLite WASM, dá para usar as mesmas opções de persistência[0] oferecidas ali
      Não tenho certeza se o IndexedDB é suportado especificamente, mas localStorage/OPFS VFS pode ser usado
      [0] https://sqlite.org/wasm/doc/trunk/persistence.md#kvvfs