ApsaraDB RDS:Use PASE for efficient vector search

IVFFlat

O IVFFlat é uma versão simplificada do algoritmo IVFADC.

1. O IVFFlat usa k-means para dividir os vetores em clusters. Cada cluster tem um centroide.

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

3. Pesquisa todos os vetores nesses n clusters e retorna os k resultados mais próximos.

Ignorar clusters distantes acelera a consulta, mas pode reduzir o recall — vetores similares à consulta podem ficar fora dos clusters selecionados. Um valor maior para n melhora o recall, porém aumenta o custo computacional.

O IVFFlat difere do IVFADC na segunda fase. O IVFADC usa quantização de produto para evitar a varredura por força bruta, sendo mais rápido, porém menos preciso. O IVFFlat faz busca por força bruta dentro dos clusters selecionados, oferecendo controle direto sobre o equilíbrio entre precisão e velocidade.

HNSW

O HNSW é um algoritmo ANN baseado em grafos.

1. O HNSW constrói uma estrutura hierárquica de camadas (grafos). Cada camada representa uma visão mais grosseira da camada abaixo.

2. A busca começa em um elemento aleatório na camada superior.

3. O HNSW encontra os vizinhos do elemento atual, adiciona-os a uma lista de candidatos de tamanho fixo ordenada por distância e continua a expandir os vizinhos. Quando a lista se estabiliza, o elemento principal torna-se o ponto de entrada para a próxima camada inferior.

4. Esse processo se repete até percorrer a camada inferior.

O HNSW usa o algoritmo Navigable Small World (NSW) — originalmente projetado para grafos de camada única — para construir cada camada, permitindo travessia mais rápida que os métodos baseados em clustering.

Este tópico pressupõe conhecimento prévio sobre aprendizado de máquina e algoritmos de busca ANN.

Etapa 1: Ative a extensão

CREATE EXTENSION pase;

Etapa 2: Calcule a similaridade vetorial (teste rápido opcional)

Use o operador <?> para calcular a similaridade entre dois vetores antes de criar um índice.

Construção do tipo PASE:

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:

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;

O operador <?> recebe um float4[] à esquerda e um valor PASE à direita. Ambos os vetores devem ter o mesmo número de dimensões; caso contrário, o PASE retornará um erro de cálculo de similaridade.

No construtor do PASE (float4[], second_param, similarity_method):

• Segundo parâmetro: reservado; defina como 0

• Método de similaridade: 0 = distância euclidiana, 1 = produto escalar (também chamado de produto interno)

Ao usar o método de produto escalar ou similaridade de cosseno, normalize primeiro os vetores de entrada. Um vetor normalizado satisfaz a condição de modo que . Para um vetor normalizado, o produto escalar equivale ao valor do cosseno. O ApsaraDB RDS for PostgreSQL suporta o método de distância euclidiana diretamente; use o método de produto escalar somente após normalizar os vetores.

Etapa 3: Crie um índice

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

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

Etapa 4: Consulte vetores

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

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

-- Step 1: Enable the extension
CREATE EXTENSION pase;

-- Step 2: Create the table
CREATE TABLE vectors_table (
  id     SERIAL PRIMARY KEY,
  vector float4[] NOT NULL
);

-- Step 3: Insert sample data
INSERT INTO vectors_table (vector) VALUES
  ('{1.0, 0.0, 0.0}'),
  ('{0.0, 1.0, 0.0}'),
  ('{0.0, 0.0, 1.0}'),
  ('{0.0, 0.5, 0.0}'),
  ('{0.0, 0.5, 0.0}'),
  ('{0.0, 0.6, 0.0}'),
  ('{0.0, 0.7, 0.0}'),
  ('{0.0, 0.8, 0.0}'),
  ('{0.0, 0.0, 0.0}');

-- Step 4: Build the IVFFlat index
CREATE INDEX ivfflat_idx ON vectors_table
USING
  pase_ivfflat(vector)
WITH
  (clustering_type = 1, distance_type = 0, dimension = 3, base64_encoded = 0, clustering_params = "10,100");

-- Step 5: Query the 10 nearest neighbors to [1, 1, 1]
SELECT id, vector <#> '1,1,1'::pase AS distance
FROM vectors_table
ORDER BY
  vector <#> '1,1,1:10:0'::pase
ASC LIMIT 10;

Cálculo de produto escalar ou similaridade de cosseno

O produto escalar de um vetor normalizado equivale ao seu valor de cosseno. Esta função usa um índice HNSW para recuperar os top-k resultados por produto escalar:

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;

Uso de arquivo de centroides externo para IVFFlat

Esta é uma opção avançada. Carregue um arquivo de centroides externo no diretório do servidor e referencie-o em clustering_params quando clustering_type = 0. O formato do arquivo é:

Number of dimensions|Number of centroids|Centroid vector dataset

Exemplo:

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