Hi @Ryanhya, response to your question：

• VectorChord using Postgres native storage, not the same as pgvecto.rs
• VectorChord natively supports WAL of Postgres
• Perhaps @usamoi can give the most accurate answer to this question.

• Is the search executed from the top layer to the bottom layer in the hierarchical clustering structure? For example, if list=[64, 4096] and probes=[16, 1024], does the search first gets the top 16 clusters in the 64 clusters of the top layer and then get the top 1024 clusters within the region of the retrieved 16 clusters?

Yes.

@xieydd @usamoi :)Thanks! A few more questions:

• I learn about parameter vchordrq.epsilon to control the lower bounds of distances, which helps to refine the search results. But I am still a little confused about this concept. Intuitively the lower the distance is, the more similarity the vectors share. Why the vectors with distances less than the parameter need rerank?
• Does VectorChord support incremental in-place update for vector field? And what's the impact on the established IVF index (e.g., do the centroids shift due to updated vectors) ?

• I learn about parameter vchordrq.epsilon to control the lower bounds of distances, which helps to refine the search results. But I am still a little confused about this concept. Intuitively the lower the distance is, the more similarity the vectors share. Why the vectors with distances less than the parameter need rerank?

The algorithm works like:

1. let the set of all vectors be S, an empty set be T.
2. choose the vector which lowerbound is smallest in S, compute the distance of this vector, remove this vector from S, and add this vector to T.
3. repeat step 2 until smallest lowerbound in S is greater that smallest distance in T, remove the vector which distance is smallest in T, and return this vector to PostgreSQL.
4. every time PostgreSQL wants a row, repeat step 3.

Therefore, the smaller the estimated lowerbounds, the more distances the algorithm needs to compute to be confident that a certain vector is the closest to the query vector, and thus the slower the algorithm becomes.

In the document, we refer to this algorithm as "rerank" which may have caused some confusion.

• Does VectorChord support incremental in-place update for vector field? And what's the impact on the established IVF index (e.g., do the centroids shift due to updated vectors) ?

Centroids do shift due to updated vectors. So if you do a full table update, you'd better execute REINDEX INDEX CONCURRENTLY.

The algorithm works like:

1. let the set of all vectors be S, an empty set be T.
2. choose the vector which lowerbound is smallest in S, compute the distance of this vector, remove this vector from S, and add this vector to T.
3. repeat step 2 until smallest lowerbound in S is greater that smallest distance in T, remove the vector which distance is smallest in T, and return this vector to PostgreSQL.
4. every time PostgreSQL wants a row, repeat step 3.

Therefore, the smaller the estimated lowerbounds, the more distances the algorithm needs to compute to be confident that a certain vector is the closest to the query vector, and thus the slower the algorithm becomes.

In the document, we refer to this algorithm as "rerank" which may have caused some confusion.

So the lower bound is estimated by RaBitQ algorithm using quantized vectors and the distance is calculated using the full-precision raw vectors?
The parameter still seems to be unclear in these 4 steps. Is there another termination condition in step 3, e.g., repeat step 2 until smallest lowerbound in S is greater than smallest distance in T or is greater than the parameter? In that case, the smaller the parameter of lower bound is, the narrower the search space is, which improves the search speed but results in bad recall. The analysis is consistent with that in the documents.

Centroids do shift due to updated vectors. So if you do a full table update, you'd better execute REINDEX INDEX CONCURRENTLY.

What if an incremental update that only influences limited several rows?

So the lower bound is estimated by RaBitQ algorithm using quantized vectors and the distance is calculated using the full-precision raw vectors?

Yes.

The parameter still seems to be unclear in these 4 steps. Is there another termination condition in step 3, e.g., repeat step 2 until smallest lowerbound in S is greater than smallest distance in T or is greater than the parameter?

No. vchordrq.epsilon is part of the formula for lowerbound estimation, and its adjustment will affect all the lowerbounds. It does not participate in any other part of the algorithm.

What if an incremental update that only influences limited several rows?

It doesn't matter. Centroids only shift after a significant portion of the entire table has been updated, and the statistical properties of the new data differ from those of the old data.

So the lower bound is estimated by RaBitQ algorithm using quantized vectors and the distance is calculated using the full-precision raw vectors?

Yes.

The parameter still seems to be unclear in these 4 steps. Is there another termination condition in step 3, e.g., repeat step 2 until smallest lowerbound in S is greater than smallest distance in T or is greater than the parameter?

No. vchordrq.epsilon is part of the formula for lowerbound estimation, and its adjustment will affect all the lowerbounds. It does not participate in any other part of the algorithm.

What if an incremental update that only influences limited several rows?

It doesn't matter. Centroids only shift after a significant portion of the entire table has been updated, and the statistical properties of the new data differ from those of the old data.

I see. Thanks for your patient reply! My problem is solved :).

Hi! I conducted a simple experiment compared to pgvector recently, using SIFT10M dataset. All the indices are built with the default configurations or the recommended settings in the documents. For example, as for HNSW index, m is set to 16 and ef_construction is set to 64. As for VectorChord, lists is recommended to be set to 12639 according to 10 million vectors.

Although I change different values for epsilon and probes, it still fails to reach a higher QPS with an acceptable recall.

The overall results is: (the line of VectorChord is obtained by varying epsilon from 0.6 to default value 1.9 with fixed probes=40)

It seems that the results is not consistent with the claims in the document. So I wonder the parameter settings in your blog.

I will appreciate it if you can give me more insightful advices on improving the performances :).

SIFT's dimension is 128, which is too small for typical workloads. And for in memory benchmark, don't modify epsilon, keep it as 1.9 and just increase the nprobes

And can you post the full create index config?

The used sql is:

CREATE INDEX ON items USING vchordrq (embedding vector_l2_ops) WITH (options = $$
build.pin = true
[build.internal]
lists = [12639]
kmeans_iterations = 25
build_threads = 16
$$);

Thanks for your advices :). I will attempt to use another high-dimensional dataset and test the performances. I will report the latest results here.

The best approach is to use your real-world case data instead of any existing dataset, and create your own query set and labels. The results will vary depending on whether you use top 10 or top 100, the data distribution, query distribution (whether it matches the data or is out-of-distribution), target recall, filter conditions, and other factors.

We have indeed observed that vectorchord is much faster than hnsw on certain datasets, while on others the performance is completely opposite, so existing public datasets can't be a direct reference for your dataset.

Thanks :)! I will give a try.

@VoVAllen Hi!

Considering convenience and privacy, I still used two public datasets to evaluate the performance:

The overall result is:

At first I only used GIST1M with the following SQL to create index (the default configurations were still utilized for other indices):

CREATE INDEX ON gist1m USING vchordrq (embedding vector_l2_ops) WITH (options = $$
[build.internal]
lists = [2000]
sampling_factor = 256
kmeans_iterations = 10
build_threads = 16
$$);

I followed your advice that increasing probes with fixed epsilon=1.9. The performance is still not ideal as SIFT10M. I double-checked your blog and guessed the distance metric might be the key factor. So I roughly read the original RaBitQ paper. It seemed that the authors mainly focused on inner product and cosine similarity in high-dimensional vector space. Based on this discovery, I accessed GloVe1M with available ground truth sets calculated by cosine distance.

The used SQL is:

CREATE INDEX ON glove1m USING vchordrq (embedding vector_cosine_ops) WITH (options = $$
[build.internal]
spherical_centroids = true
lists = [2000]
sampling_factor = 256
kmeans_iterations = 10
build_threads = 16
$$);

Although the dimension is relatively small, VectorChord begins to show its advantages when the recall target is at least 0.8.

What makes me feel curious and interesting is that the line of VectorChord on GIST1M is almost smooth. Firstly I thought it was caused by the imbalanced clusters distribution. But I abandoned the assumption because the recall was increased quickly with only a slight decrease in QPS, which is not aligned with my empirical knowledge. Do you have any ideas about this?

By the way, which KMeans algorithm is utilized in VectorChord? Is it the classic Lloyd's version?

@Ryanhya It's normal lloyd and the performance here must be something wrong because we've tested against GIST dataset in https://blog.vectorchord.ai/vectorchord-store-400k-vectors-for-1-in-postgresql. The performance is like

and it's consistent with your experiment for pgvector. Can you try make kmeans_iterations larger to 25? And also do EXPLAIN (BUFFERS) SELECT xxx to check whether there're buffers read from the disk

Can you try make kmeans_iterations larger to 25?

I did and built another new index, but the trend seemed to be the same.

And also do EXPLAIN (BUFFERS) SELECT xxx to check whether there're buffers read from the disk

The log of the first query (omit the raw query vector data) is shown as:

Limit  (cost=0.00..500003.01 rows=1 width=16)
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16)
        Order By: (embedding <-> '[...]'::vector)
Planning:
  Buffers: shared hit=72

The other 999 queries' logs are almost the same as above except the raw query data.

Meanwhile, I recorded the latency distribution of the 1000 queries when probes=10:

@Ryanhya Can you show the full explain result? with EXPLAIN (ANALYZE, BUFFERS) SELECT xxx?

The full logs of EXPLAIN (ANALYZE, BUFFERS) SELECT of the first 5 queries are:

query_id: 0
log_info:
 Limit  (cost=0.00..500003.01 rows=1 width=16) (actual time=283.750..299.324 rows=100 loops=1)
  Buffers: shared hit=1448
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16) (actual time=283.749..299.300 rows=100 loops=1)
        Order By: (embedding <-> '[...]'::vector)
        Buffers: shared hit=1448
Planning:
  Buffers: shared hit=72
Planning Time: 0.595 ms
Execution Time: 299.628 ms
--------------------------
query_id: 1
log_info:
 Limit  (cost=0.00..500003.01 rows=1 width=16) (actual time=318.303..345.069 rows=100 loops=1)
  Buffers: shared hit=4335
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16) (actual time=318.301..345.044 rows=100 loops=1)
        Order By: (embedding <-> '[...]'::vector)
        Buffers: shared hit=4335
Planning:
  Buffers: shared hit=72
Planning Time: 0.736 ms
Execution Time: 346.151 ms
--------------------------
query_id: 2
log_info:
 Limit  (cost=0.00..500003.01 rows=1 width=16) (actual time=296.644..314.936 rows=100 loops=1)
  Buffers: shared hit=1631
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16) (actual time=296.641..314.911 rows=100 loops=1)
        Order By: (embedding <-> '[...]'::vector)
        Buffers: shared hit=1631
Planning:
  Buffers: shared hit=72
Planning Time: 0.778 ms
Execution Time: 315.402 ms
--------------------------
query_id: 3
log_info:
 Limit  (cost=0.00..500003.01 rows=1 width=16) (actual time=311.276..340.032 rows=100 loops=1)
  Buffers: shared hit=4646
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16) (actual time=311.273..340.012 rows=100 loops=1)
        Order By: (embedding <-> '[...]'::vector)
        Buffers: shared hit=4646
Planning:
  Buffers: shared hit=72
Planning Time: 0.818 ms
Execution Time: 341.230 ms
--------------------------
query_id: 4
log_info:
 Limit  (cost=0.00..500003.01 rows=1 width=16) (actual time=329.151..355.769 rows=100 loops=1)
  Buffers: shared hit=4683
  ->  Index Scan using gist1m_vchord_ivf_2000_25 on gist1m_vchord_ivf  (cost=0.00..500003.01 rows=1 width=16) (actual time=329.148..355.748 rows=100 loops=1)
        Order By: (embedding <-> '[...]'::vector)
        Buffers: shared hit=4683
Planning:
  Buffers: shared hit=72
Planning Time: 0.746 ms
Execution Time: 356.818 ms