PolarDB:High-dimensional vector search (PASE)

IVFFlat

IVFFlat is a simplified version of the IVFADC algorithm. It divides vectors into clusters using k-means, then at query time narrows the search to the clusters nearest to the query vector.

1. IVFFlat clusters all vectors using k-means. Each cluster has a centroid.

2. At query time, IVFFlat finds the *n* centroids nearest to the query vector.

3. IVFFlat searches all vectors in those *n* clusters and returns the *k* nearest.

Searching only *n* clusters speeds up queries but may miss similar vectors in skipped clusters, reducing recall. Increase *n* to improve recall at the cost of more computation. Unlike IVFADC — which uses product quantization to avoid full traversal — IVFFlat uses brute-force search within each cluster to preserve precision.

HNSW

HNSW builds a multi-layer graph using the NSW (Navigable Small World) algorithm. Each layer is a coarser view of the layer below it.

1. HNSW builds a hierarchical graph with multiple layers.

2. Search starts at a random entry point in the top layer.

3. HNSW identifies the neighbors of the current element and adds them to a fixed-length dynamic list, ranked by distance. It then expands to the neighbors of those neighbors, continuously re-sorting the list and keeping only the top *k* candidates. This continues until the list stabilizes, then the top element becomes the entry point for the next layer down.

4. The bottom layer returns the final nearest neighbors.

HNSW's neighbor-selection approach gives it better query performance than clustering-based algorithms at large scale, but it requires storing the proximity graph, which consumes additional memory.

Choose a distance method

If you use the dot product or cosine method, normalize your vectors first. For a vector , it must satisfy . After normalization, the dot product equals the cosine value.

PolarDB natively supports only Euclidean distance. To use dot product, normalize your vectors and follow the approach in the Appendix.

Create the index

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"
);

To use internal clustering (clustering_type = 1), insert data into the table before creating the index.

IVFFlat index parameters

Configuring `clustering_params` for internal clustering:

• clustering_sample_ratio: sampling fraction with 1000 as the denominator. Valid range: (0, 1000]. For example, 1 means a 1/1000 sampling ratio. Keep the total sampled records under 100,000.

• k: number of centroids. Valid range: [100, 1000]. A larger value improves recall but slows index creation.

Query with an IVFFlat index

The <#> operator activates the IVFFlat index. An ORDER BY clause is required.

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

The query string 'vector:probe_count:distance_type' accepts three colon-separated parameters:

Create the index

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
);

HNSW index parameters

Query with an HNSW index

The <?> operator activates the HNSW index. An ORDER BY clause is required.

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

The query string 'vector:ef_search:distance_type' accepts three colon-separated parameters:

PASE-type construction

The <?> operator takes a float4[] on the left and a PASE type on the right.

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;

The PASE constructor accepts up to three arguments: pase(vector, unused_param, distance_method). The second argument has no special purpose — set it to 0. The third argument sets the distance method: 0 for Euclidean, 1 for dot product.

Both vectors must have the same number of dimensions. A mismatch causes an error.

String-based construction

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;

The string format is 'vector:unused_param:distance_method', using colons as separators. Parameters have the same meaning as in PASE-type construction.

Calculate dot product with HNSW

Because PolarDB does not natively support dot product distance, use this function to search by dot product after normalizing your vectors.

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;

The dot product of a normalized vector equals its cosine value, so this function also works for cosine similarity search.

Create an IVFFlat index from an external centroid file

External clustering is an advanced option. Upload a centroid file to the server and set clustering_type = 0 in the index definition.

The centroid file format is:

Number_of_dimensions|Number_of_centroids|Centroid_vector_dataset

Example:

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