Índice explicado

Um índice é uma estrutura adicional construída sobre os dados. A sua estrutura interna depende do algoritmo de pesquisa do vizinho mais próximo aproximado em utilização. Um índice acelera a pesquisa, mas incorre em tempo de pré-processamento, espaço e RAM adicionais durante a pesquisa. Além disso, a utilização de um índice reduz normalmente a taxa de recuperação (embora o efeito seja insignificante, não deixa de ser importante). Portanto, este artigo explica como minimizar os custos da utilização de um índice e, ao mesmo tempo, maximizar os benefícios.

Visão geral

No Milvus, os índices são específicos dos campos, e os tipos de índices aplicáveis variam de acordo com os tipos de dados dos campos alvo. Sendo uma base de dados vetorial profissional, o Milvus concentra-se em melhorar o desempenho das pesquisas vectoriais e da filtragem escalar, razão pela qual oferece vários tipos de índices.

A tabela seguinte lista a relação de mapeamento entre os tipos de dados de campo e os tipos de índices aplicáveis.

Tipo de dados de campo	Tipos de índice aplicáveis
FLOAT_VECTOR FLOAT16_VECTOR BFLOAT16_VECTOR INT8_VECTOR	FLAT IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ GPU_BRUTE_FORCE
VECTOR BINÁRIO	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
VECTOR_FLOAT_ESPARSO	ÍNDICE_INVERTIDO_ESPARSO
VARCHAR	INVERTED (Recomendado) BITMAP Trie
BOOL	BITMAP (Recomendado) INVERTIDO
INT8 INT16 INT32 INT64	INVERTIDO STL_SORT
FLOAT DOUBLE	INVERTED
ARRAY (elementos dos tipos BOOL, INT8/16/32/64 e VARCHAR)	BITMAP (recomendado)
ARRAY (elementos dos tipos BOOL, INT8/16/32/64, FLOAT, DOUBLE e VARCHAR)	INVERTIDO
JSON	INVERTIDO

Este artigo centra-se na forma de selecionar índices vectoriais adequados. Para campos escalares, pode sempre utilizar o tipo de índice recomendado.

A seleção de um tipo de índice adequado para uma pesquisa de vetor pode afetar significativamente o desempenho e a utilização de recursos. Ao escolher um tipo de índice para um campo de vetor, é essencial considerar vários factores, incluindo a estrutura de dados subjacente, a utilização de memória e os requisitos de desempenho.

Anatomia do índice de vetor

Como demonstrado no diagrama abaixo, um tipo de índice em Milvus consiste em três componentes principais, nomeadamente a estrutura de dados, a quantização e o refinador. A quantização e o refinador são opcionais, mas são amplamente utilizados devido a um equilíbrio significativo entre ganhos e custos.

Anatomia do Índice Vetorial

Durante a criação do índice, o Milvus combina a estrutura de dados escolhida e o método de quantização para determinar uma taxa de expansão óptima. No momento da consulta, o sistema recupera topK × expansion rate os vectores candidatos, aplica o refinador para recalcular as distâncias com maior precisão e, finalmente, devolve os resultados mais exactos topK. Esta abordagem híbrida equilibra a velocidade e a precisão, restringindo o refinamento, que consome muitos recursos, a um subconjunto filtrado de candidatos.

Estrutura de dados

A estrutura de dados constitui a camada fundamental do índice. Os tipos comuns incluem:

• Ficheiro invertido (IVF)

  Os tipos de índice da série IVF permitem que o Milvus agrupe vectores em grupos através de um particionamento baseado em centróides. Em geral, é seguro assumir que todos os vectores de um grupo estão provavelmente próximos do vetor de consulta se o centróide do grupo estiver próximo do vetor de consulta. Com base nesta premissa, o Milvus analisa apenas as incorporações de vectores nos baldes em que os centróides estão próximos do vetor de consulta, em vez de examinar todo o conjunto de dados. Esta estratégia reduz os custos computacionais, mantendo uma precisão aceitável.

  Este tipo de estrutura de dados de índice é ideal para conjuntos de dados de grande escala que requerem um rendimento rápido.

• Estrutura baseada em grafos

  Uma estrutura de dados baseada em gráficos para pesquisa vetorial, como o Hierarchical Navigable Small World(HNSW), constrói um gráfico em camadas em que cada vetor se liga aos seus vizinhos mais próximos. As consultas navegam nesta hierarquia, começando nas camadas superiores grosseiras e passando pelas camadas inferiores, o que permite uma complexidade de pesquisa eficiente em tempo logarítmico.

  Este tipo de estrutura de dados de índice é excelente em espaços de elevada dimensão e em cenários que exigem consultas de baixa latência.

Quantização

A quantização reduz o espaço de memória e os custos computacionais através de uma representação mais grosseira:

• A Quantização Escalar (por exemplo, SQ8) permite ao Milvus comprimir cada dimensão vetorial num único byte (8 bits), reduzindo a utilização de memória em 75% em comparação com os valores flutuantes de 32 bits, preservando uma precisão razoável.

• A Quantização de Produto(PQ) permite ao Milvus dividir os vectores em subvectores e codificá-los utilizando o agrupamento baseado no livro de códigos. Isto permite atingir rácios de compressão mais elevados (por exemplo, 4-32x) à custa de uma redução marginal da recuperação, tornando-o adequado para ambientes com restrições de memória.

Refinador

A quantização é inerentemente com perdas. Para manter a taxa de recuperação, a quantização produz consistentemente mais candidatos top-K do que o necessário, permitindo que os refinadores usem maior precisão para selecionar ainda mais os resultados top-K desses candidatos, aumentando a taxa de recuperação.

Por exemplo, o refinador FP32 opera nos candidatos de resultados de pesquisa retornados pela quantização recalculando as distâncias usando a precisão FP32 em vez dos valores quantizados.

Isto é fundamental para aplicações que exigem um compromisso entre a eficiência e a precisão da pesquisa, como a pesquisa semântica ou os sistemas de recomendação, em que pequenas variações de distância afectam significativamente a qualidade dos resultados.

Resumo

Esta arquitetura em camadas - filtragem grosseira através de estruturas de dados, computação eficiente através de quantização e afinação da precisão através de refinamento - permite ao Milvus otimizar a relação precisão-desempenho de forma adaptativa.

Compensações de desempenho

Ao avaliar o desempenho, é crucial equilibrar o tempo de construção, a consulta por segundo (QPS) e a taxa de recuperação. As regras gerais são as seguintes:

• Os tipos de índices baseados em grafos geralmente superam as variantes de IVF em termos de QPS.

• As variantes IVF adequam-se particularmente aos cenários com um topK grande (por exemplo, mais de 2.000).

• O PQ oferece normalmente uma melhor taxa de recuperação com taxas de compressão semelhantes quando comparado com o SQ, embora este último ofereça um desempenho mais rápido.

• A utilização de discos rígidos para parte do índice (como em DiskANN) ajuda a gerir grandes conjuntos de dados, mas também introduz potenciais estrangulamentos de IOPS.

Capacidade

A capacidade envolve normalmente a relação entre o tamanho dos dados e a RAM disponível. Ao lidar com a capacidade, considere o seguinte:

• Se um quarto dos seus dados brutos couber na memória, considere a DiskANN devido à sua latência estável.

• Se todos os seus dados brutos couberem na memória, considere os tipos de índice baseados na memória e o mmap.

• Pode utilizar os tipos de índice aplicados à quantização e o mmap para trocar a precisão pela capacidade máxima.

Recolha

A recuperação envolve normalmente o rácio de filtro, que se refere aos dados que são filtrados antes das pesquisas. Ao lidar com a recuperação, considere o seguinte:

• Se o rácio de filtragem for inferior a 85%, os tipos de índices baseados em grafos superam as variantes de FIV.

• Se o rácio de filtragem estiver entre 85% e 95%, utilize variantes de FIV.

• Se o rácio de filtragem for superior a 98%, utilize a Força bruta (FLAT) para obter os resultados de pesquisa mais exactos.

Desempenho

O desempenho de uma pesquisa envolve normalmente o top-K, que se refere ao número de registos que a pesquisa devolve. Ao lidar com o desempenho, considere o seguinte:

• Para uma pesquisa com um top-K pequeno (por exemplo, 2.000) que requer uma alta taxa de recuperação, os tipos de índice baseados em gráficos superam as variantes de FIV.

• Para uma pesquisa com um top-K grande (comparado com o número total de incorporações vectoriais), as variantes de FIV são uma melhor escolha do que os tipos de índices baseados em grafos.

• Para uma pesquisa com um top-K de dimensão média e um rácio de filtragem elevado, as variantes FIV são a melhor escolha.

Matriz de decisão: Escolher o tipo de índice mais adequado

A tabela a seguir é uma matriz de decisão que pode ser consultada ao escolher um tipo de índice apropriado.

Cenário	Índice recomendado	Notas
Os dados em bruto cabem na memória	HNSW, IVF + Refinamento	Utilizar HNSW para baixak/recuperação elevada.
Dados em bruto no disco, SSD	DiskANN	Ótimo para consultas sensíveis à latência.
Dados em bruto no disco, RAM limitada	IVFPQ/SQ + mmap	Equilibra o acesso à memória e ao disco.
Rácio de filtragem elevado (>95%)	Força bruta (FLAT)	Evita a sobrecarga de índices para conjuntos de candidatos pequenos.
Grande k (≥1% do conjunto de dados)	FIV	A poda de clusters reduz a computação.
Taxa de recuperação extremamente elevada (>99%)	Força bruta (FLAT) + GPUs	--

Estimativa de utilização de memória

O consumo de memória de um índice é influenciado pela sua estrutura de dados, taxa de compressão através da quantização e o refinador em uso. De um modo geral, os índices baseados em grafos têm tipicamente um maior consumo de memória devido à estrutura do grafo (por exemplo, HNSW), o que implica normalmente uma sobrecarga de espaço por vetor. Em contrapartida, o IVF e as suas variantes são mais eficientes em termos de memória, uma vez que se aplica menos sobrecarga de espaço por vetor. No entanto, técnicas avançadas como a DiskANN permitem que partes do índice, como o gráfico ou o refinador, residam no disco, reduzindo a carga de memória e mantendo o desempenho.

Especificamente, a utilização de memória de um índice pode ser calculada da seguinte forma:

Utilização de memória do índice IVF

Os índices IVF equilibram a eficiência da memória com o desempenho da pesquisa ao particionar os dados em clusters. Segue-se uma análise da memória utilizada por 1 milhão de vectores de 128 dimensões indexados com variantes de IVF.

1. Calcular a memória utilizada pelos centróides.

   Os tipos de índice da série IVF permitem que o Milvus agrupe vectores em grupos utilizando o particionamento baseado em centróides. Cada centróide é incluído no índice na incorporação de vectores em bruto. Quando divide os vectores em 2.000 clusters, a utilização de memória pode ser calculada da seguinte forma:

   2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB
   

2. Calcule a memória utilizada pelas atribuições de cluster.

   Cada incorporação de vetor é atribuída a um cluster e armazenada como IDs inteiros. Para 2000 clusters, é suficiente um número inteiro de 2 bytes. A utilização de memória pode ser calculada da seguinte forma:

   1,000,000 vectors × 2 bytes = 2.0 MB
   

3. Calcular a compressão causada pela quantização.

   As variantes de FIV utilizam normalmente PQ e SQ8, e a utilização de memória pode ser estimada da seguinte forma:

   • Usando PQ com 8 subquantizadores

     1,000,000 vectors × 8 bytes = 8.0 MB
     

   • Utilização de SQ8

     1,000,000 vectors × 128 dimensions × 1 byte = 128 MB 
     

   A tabela a seguir lista o uso estimado de memória com diferentes configurações:

   Configuração	Estimativa de memória	Memória total
   IVF-PQ (sem refinamento)	1,0 MB + 2,0 MB + 8,0 MB	11,0 MB
   IVF-PQ + 10% de refinamento em bruto	1,0 MB + 2,0 MB + 8,0 MB + 51,2 MB	62,2 MB
   IVF-SQ8 (sem refinamento)	1,0 MB + 2,0 MB + 128 MB	131,0 MB
   IVF-FLAT (vectores brutos completos)	1,0 MB + 2,0 MB + 512 MB	515,0 MB

4. Calcular a sobrecarga de refinamento.

   As variantes de FIV geralmente são combinadas com um refinador para reclassificar os candidatos. Para uma pesquisa que recupera os 10 principais resultados com uma taxa de expansão de 5, a sobrecarga de refinamento pode ser estimada da seguinte forma:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Utilização da memória do índice baseado em grafos

Os tipos de índice baseados em grafos, como o HNSW, requerem uma memória significativa para armazenar a estrutura do grafo e as incorporações de vetor em bruto. Abaixo está uma análise detalhada da memória consumida por 1 milhão de vectores de 128 dimensões indexados utilizando o tipo de índice HNSW.

1. Calcule a memória utilizada pela estrutura do grafo.

   Cada vetor em HNSW mantém ligações aos seus vizinhos. Com um grau de grafo (arestas por nó) de 32, a memória consumida pode ser calculada da seguinte forma:

   1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB  
   

2. Calcular a memória utilizada pelos embeddings vectoriais em bruto.

   A memória consumida pelo armazenamento de vectores FP32 não comprimidos pode ser calculada da seguinte forma:

   1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB  
   

   Quando se utiliza o HNSW para indexar o 1 milhão de embeddings vectoriais de 128 dimensões, a memória total utilizada seria de 128 MB (gráfico) + 512 MB (vectores) = 640 MB.

3. Calcule a compressão causada pela quantização.

   A quantização reduz o tamanho do vetor. Por exemplo, a utilização de PQ com 8 subquantizadores (8 bytes por vetor) conduz a uma compressão drástica. A memória consumida pelos embeddings vectoriais comprimidos pode ser calculada da seguinte forma:

   1,000,000 vectors × 8 bytes = 8 MB
   

   Isto alcança uma taxa de compressão de 64 vezes quando comparado com os embeddings de vetor em bruto, e a memória total utilizada pelo tipo de índice HNSWPQ seria 128 MB (gráfico) + 8 MB (vetor comprimido) = 136 MB.

4. Calcule a sobrecarga de refinamento.

   O refinamento, como a reclassificação com vetores brutos, carrega temporariamente dados de alta precisão na memória. Para uma pesquisa que recupera os 10 principais resultados com uma taxa de expansão de 5, a sobrecarga de refinamento pode ser estimada da seguinte forma:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Outras considerações

Enquanto o IVF e os índices baseados em grafos optimizam a utilização da memória através da quantização, os ficheiros mapeados na memória (mmap) e o DiskANN abordam cenários em que os conjuntos de dados excedem a memória de acesso aleatório (RAM) disponível.

DiskANN

O DiskANN é um índice baseado no grafo Vamana que liga pontos de dados para uma navegação eficiente durante a pesquisa, aplicando PQ para reduzir o tamanho dos vectores e permitir um cálculo rápido da distância aproximada entre vectores.

O grafo Vamana é armazenado no disco, o que permite ao DiskANN lidar com grandes conjuntos de dados que, de outra forma, seriam demasiado grandes para caber na memória. Isto é particularmente útil para conjuntos de dados de milhares de milhões de pontos.

Ficheiros mapeados na memória (mmap)

O mapeamento de memória (Mmap) permite o acesso direto à memória de ficheiros grandes no disco, permitindo ao Milvus armazenar índices e dados tanto na memória como nos discos rígidos. Esta abordagem ajuda a otimizar as operações de E/S, reduzindo a sobrecarga das chamadas de E/S com base na frequência de acesso, expandindo assim a capacidade de armazenamento das colecções sem afetar significativamente o desempenho da pesquisa.

Especificamente, é possível configurar o Milvus para mapear em memória os dados brutos em determinados campos, em vez de carregá-los totalmente na memória. Desta forma, pode obter acesso direto à memória dos campos sem se preocupar com problemas de memória e aumentar a capacidade da coleção.