O SonnetDB integra um índice de grafo HNSW (Hierarchical Navigable Small World) para campos do tipo VECTOR, otimiznado a latência de buscas em vetores de grande escala de segundos para milissegundos. Este artigo explora a arquitetura subjacente, detalhando a influência dos parâmetros m e ef no desempenho e a organização do formato de arquivo auixliar .SDBVIDX.

Blocos de Índice HNSW

No SonnetDB, o índice HNSW é construído de forma independente para cada bloco de dados dentro de um segmento de armazenamento. Cada bloco VECTOR corresponde a uma instância de HnswVectorBlockIndex, que encapsula o grafo de adjacências multinível completo. Após a construção, o índice é serializado e gravado em um arquivo lateral .SDBVIDX, mantendo uma correspondência um-para-um com o arquivo de dados principal .SDBSEG. Durante uma consulta, o sistema executa buscas ANN (Approximate Nearest Neighbor) bloco por bloco, consolidando os resultados Top-K de cada bloco para fornecer a resposta final.

public static HnswVectorBlockIndex ConstruirIndiceDeBloco(
    int idDoBloco,
    ReadOnlySpan<PontoDeDados> vetoresParaIndexar,
    ConfiguracoesIndiceHNSW opcoesDeIndice)

A fase de construção do índice inicia-se atribuindo um nível aleatório a cada vetor, seguido pela inserção sequencial de cada nó no grafo. Este prcoesso envolve uma descida gulosa a partir do ponto de entrada da camada superior, realizando uma busca de largura ef em cada camada para identificar vizinhos candidatos. No máximo M vizinhos mais próximos são então selecionados para estabelecer conexões bidirecionais.

Compreendendo o Parâmetro M

O parâmetro M estabelece o número máximo de vizinhos que cada nó pode manter em qualquer camada do grafo. A estrutura ConfiguracoesIndiceHNSW do SonnetDB é definida da seguinte forma:

public sealed record ConfiguracoesIndiceHNSW(int MaxVizinhosM, int LarguraBuscaEf);

Quando um novo nó é inserido e o número de vizinhos candidatos excede o valor de MaxVizinhosM, o algoritmo trunca a lista, priorizando os vizinhos mais próximos pela distância:

int quantidadeATer = Math.Min(opcoes.MaxVizinhosM, candidatosAVizinhos.Count);

Recomendações de Otimização para M:

• M=8: Produz índices mais compactos, ideais para ambientes com restrição de memória, com uma revocação esperada entre 85-90%.
• M=16: O valor padrão, oferecendo um equilíbrio sólido para a maioria dos cenários, resultando em aproximadamente 95% de revocação.
• M=24 a 32: Configuração para alta precisão, capaz de atingir mais de 98% de revocação, embora com um aumento correspondente no volume do índice e no tempo de construção.

Explorando o Parâmetro Ef

O parâmetro ef influencia tanto as etapas de construção quanto as de consulta do índice. Durante a construção, ele define a largura da busca interna. Em contraste, no momento da busca, um valor ef dinâmico é calculado como max(k, LarguraBuscaEf), onde k é o número de resultados desejados.

int efParaBusca = Math.Min(TotalDeElementos, Math.Max(limiteDeResultados, configuracoes.LarguraBuscaEf));
var resultados = RealizarBuscaNaCamada(cargaUtilDoValor, vetorDeConsulta, pontoDePartida, 0, efParaBusca, funcaoMetrica);

A experiência demonstra que definir ef como 2 a 5 vezes o valor de k (o número de vizinhos mais próximos a serem retornados) geralmente oferece o melhor custo-benefício em termos de revocação em torno de 95%. Com ef=200, a revocação pode consistentemente superar 98%.

Estrutura do Arquivo .SDBVIDX

A disposição binária do arquivo .SDBVIDX é organizada da seguinte forma:

Deslocamento | Conteúdo
-------------|------------------------------------
0            | Assinatura: "SDBVIDX1" (8 bytes)
8            | VersãoDoFormato: int32 LE = 1
12           | TamanhoDoCabecalho: int32 LE = 32
16           | ContagemDeBlocos: int32 LE
20           | Preenchimento até 32 bytes

[Serialização do Bloco 1]
  IdDoBloco: int32
  ContagemDeElementos: int32
  Dimensao: int32
  M_Configurado: int32
  Ef_Configurado: int32
  NivelMaximo: int32
  PontoDeEntrada: int32
  [Dados de Nível para o Nó 0...]
  [Dados de Nível para o Nó 1...]
  ... (para todos os nós do bloco)

Os arquivos são gravados usando o método SegmentVectorIndexFile.Write() e carregados de forma preguiçosa via TryLoad(). Caso um arquivo esteja ausente ou corrompido, o sistema retorna silenciosamente a uma busca exata, garantindo a continuidade das operações de consulta. Ao ajustar cuidadosamente os parâmetros M e ef, os usuários podem equilibrar efetivamente o tamanho do índice, a precisão da busca e a latência da consulta.