PolarDB:Busca vetorial de alta dimensão (PASE)

IVFFlat

O IVFFlat é uma versão simplificada do algoritmo IVFADC. Ele agrupa vetores usando k-means e pesquisa apenas nos clusters mais próximos do vetor de consulta, ignorando clusters distantes para acelerar a busca. A precisão aumenta conforme o número de clusters pesquisados, o que permite ajuste direto.

Funcionamento do IVFFlat:

1. O IVFFlat aplica clusterização k-means para agrupar vetores em clusters, cada um com um centroide.

2. Identifica os n centroides mais próximos do vetor de consulta.

3. Percorre e classifica todos os vetores nesses n clusters e retorna os k vetores mais próximos.

Um valor maior para n aumenta a precisão, mas também eleva o custo computacional. Diferentemente do IVFADC, que usa quantização de produto na fase 2 para reduzir o custo de travessia (às custas da precisão), o IVFFlat utiliza busca por força bruta. Isso oferece controle direto sobre o equilíbrio entre precisão e desempenho.

HNSW

O HNSW constrói um grafo hierárquico multicamadas usando o algoritmo Navigable Small World (NSW). Cada camada atua como uma skip list panorâmica sobre a camada inferior, o que permite travessia rápida em grandes conjuntos de dados.

Funcionamento do HNSW:

1. O HNSW cria uma estrutura com múltiplas camadas (grafos). Cada camada funciona como um panorama e uma skip list da camada abaixo dela.

2. A partir de um elemento aleatório na camada superior, o HNSW identifica vizinhos e os adiciona a uma lista dinâmica de comprimento fixo, ordenada por distância.

3. Continua expandindo os vizinhos, reordena a lista após cada adição e mantém apenas os k melhores. Quando a lista estabiliza, o HNSW desce para a próxima camada usando o elemento principal como ponto de partida.

4. O processo se repete até concluir a busca na camada inferior.

Depois que a precisão atinge determinado nível, não é possível aumentá-la apenas reconfigurando parâmetros. O HNSW também exige armazenamento adicional para persistir os vizinhos do grafo de proximidade.

CREATE EXTENSION pase;

Construção com tipo PASE

O operador <?> calcula a similaridade entre vetores. O tipo de dado PASE aceita até três parâmetros:

• Parâmetro 1: O vetor do lado direito (float4[])

• Parâmetro 2: Reservado; defina como 0

• Parâmetro 3: Método de similaridade — 0 para distância euclidiana, 1 para produto escalar (produto interno)

SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[]) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0, 1) AS distance;

Construção baseada em string

A construção baseada em string usa dois pontos (:) para separar parâmetros em vez de argumentos de função:

SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0:1'::pase AS distance;

Em '3,1,1:0:1', o primeiro segmento é o vetor, o segundo é o parâmetro reservado (0) e o terceiro é o método de similaridade (0 = Euclidiana, 1 = produto escalar).

Requisito de normalização

• Distância euclidiana: Nenhuma normalização necessária.

• Produto escalar ou cosseno: Normalize primeiro o vetor original. Para um vetor normalizado, o produto escalar equivale ao valor do cosseno. Por exemplo, se o vetor original for , ele deve satisfazer: .

Índice IVFFlat

CREATE INDEX ivfflat_idx ON vectors_table
USING
  pase_ivfflat(vector)
WITH
  (clustering_type = 1, distance_type = 0, dimension = 256, base64_encoded = 0, clustering_params = "10,100");

Parâmetros

clustering_params para clusterização interna (clustering_type = 1)

Formato: clustering_sample_ratio,k

• clustering_sample_ratio: Fração de amostragem com denominador 1.000. Intervalo: (0, 1000]. Por exemplo, 1 significa uma taxa de amostragem de 1/1000. Um valor maior aumenta a precisão, mas torna a criação do índice mais lenta. Mantenha o total de registros amostrados abaixo de 100.000.

• k: Número de centroides. Um valor maior aumenta a precisão, mas torna a criação do índice mais lenta. O intervalo recomendado é [100, 1000].

Índice HNSW

CREATE INDEX hnsw_idx ON vectors_table
USING
  pase_hnsw(vector)
WITH
  (dim = 256, base_nb_num = 16, ef_build = 40, ef_search = 200, base64_encoded = 0);

Parâmetros

Consulta com índice IVFFlat

Use o operador <#> para consultas com índice IVFFlat. Uma cláusula ORDER BY é obrigatória para que o índice tenha efeito. Os resultados são classificados em ordem crescente de distância.

SELECT id, vector <#> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <#> '1,1,1:10:0'::pase
ASC LIMIT 10;

A string de consulta '1,1,1:10:0' contém três parâmetros separados por dois pontos:

Consulta com índice HNSW

Utilize o operador <?> para consultas com índice HNSW. Uma cláusula ORDER BY é obrigatória para que o índice tenha efeito. Os resultados são classificados em ordem crescente de distância.

SELECT id, vector <?> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <?> '1,1,1:100:0'::pase
ASC LIMIT 10;

A string de consulta '1,1,1:100:0' contém três parâmetros separados por dois pontos:

Calcule o produto escalar (produto interno)

Como o produto escalar de um vetor normalizado equivale ao seu valor de cosseno, a função a seguir serve tanto para buscas por produto escalar quanto por similaridade de cosseno. Ela utiliza um índice HNSW.

CREATE OR REPLACE FUNCTION inner_product_search(query_vector text, ef integer, k integer, table_name text) RETURNS TABLE (id integer, uid text, distance float4) AS $$
BEGIN
    RETURN QUERY EXECUTE format('
    select a.id, a.vector <?> pase(ARRAY[%s], %s, 1) AS distance from
    (SELECT id, vector FROM %s ORDER BY vector <?> pase(ARRAY[%s], %s, 0) ASC LIMIT %s) a
    ORDER BY distance DESC;', query_vector, ef,  table_name,  query_vector, ef, k);
END
$$
LANGUAGE plpgsql;

Crie um índice IVFFlat a partir de um arquivo externo de centroides

Este é um recurso avançado. Carregue um arquivo externo de centroides no diretório especificado do servidor e referencie-o em clustering_params. O formato do arquivo é:

Number of dimensions|Number of centroids|Centroid vector dataset

Exemplo:

3|2|1,1,1,2,2,2