cockroachdb / cockroachdb/cockroach
sql/vecindex: reassign split vectors to better partitions
- 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
Assessment
This issue has not been assessed yet.