Question about the index storage and search process

[Ryanhya]

After reading the documents, I have the following questions:

• Is it the same as pgvecto.rs that the separate index storage is utilized in VectorChord?
• WAL for index is also not supported in VectorChord?
• 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?

[xieydd]

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.

[usamoi]

• 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.

[Ryanhya]

@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) ?

[usamoi]

• 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.

[Ryanhya]

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?

[usamoi]

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.

[Ryanhya]

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 :).

[Ryanhya]

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 :).

[VoVAllen]

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

[VoVAllen]

And can you post the full create index config?

[Ryanhya]

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.

[VoVAllen]

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.

[Ryanhya]

Thanks :)! I will give a try.

[Ryanhya]

@VoVAllen Hi!

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

Datasets	Type	Dimension	Base vectors	Query vectors	Distance
GIST1M	float32	960	1,000,000	1,000	L2
GloVe1M	float32	200	1,183,514	10,000	cosine

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?