cockroachdb / cockroachdb/cockroach

sql/vecindex: reassign split vectors to better partitions

Open
#157,134 0 comments 0 reactions 0 assignees View on GitHub
A-vector-index C-enhancement T-specialized-indexing
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

When splitting a partition, the `reassignToSiblings` method checks if its vectors need to be reassigned to a partition other than the left and right sub-partitions. It currently checks whether any sibling partitions are closer. However, the larger the index, the more likely it is that there could be a better partition that is not a sibling, but instead a "cousin" partition at the same level of the tree (whether it be first, second, third, etc. cousin).

We should investigate ways to find non-sibling partitions that are closer. However, in doing this, we need to be careful that widening the search has a negligible impact on overall performance. For example, we could do a full tree search for every vector that may need to be reassigned. But that's likely to have unacceptable performance impact. There needs to be a balance between increased accuracy and performance.

One possible idea would be to find the N closest partitions to the splitting partition and then check all of those for each vector that may need to be reassigned. There may be other ideas as well - this will take some experimentation.

Jira issue: CRDB-56384

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.