cockroachdb / cockroachdb/cockroach

sql/vecindex: replace EstimatePartitionCount split scheduling with a probabilistic fixup-add

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

Description

**Is your feature request related to a problem? Please describe.**

After every successful insert search, the index issues an inconsistent
(non-transactional) `EstimatePartitionCount` scan of the chosen leaf
partition and, if the count is at or above `MaxPartitionSize`, enqueues
a split fixup:

```go
// pkg/sql/vecindex/cspann/index.go
count, err := vi.store.EstimatePartitionCount(ctx, idxCtx.treeKey, partitionKey)
if err != nil {
return nil, errors.Wrapf(err, "counting vectors in partition %d", partitionKey)
}
if count >= vi.options.MaxPartitionSize {
vi.fixups.AddSplit(ctx, idxCtx.treeKey,
result.ParentPartitionKey, partitionKey, false /* singleStep */)
}
```

This adds a scan per insert on the hot path purely to decide whether to
enqueue a split. Empirically (see "Additional context") it is also a
source of pipeline pressure under high-concurrency / large-batch
inserts — replacing it removes a class of issues where the fixup
pipeline cannot keep up with the insert hot path.

**Describe the solution you'd like**

Skip the inconsistent count entirely. Instead, on each insert, enqueue
a split fixup with probability `1 / MaxPartitionSize` (or some
equivalent target rate).

Properties:
- Expected number of inserts between split enqueues for a given
partition equals `MaxPartitionSize`, matching the existing trigger
threshold in steady state.
- The split-fixup worker already re-reads the partition under the
appropriate scope and is a no-op if the partition is not actually
oversized, so a spurious enqueue is cheap and correct.
- The insert hot path drops one KV scan per insert and stops issuing
any read at all that exists solely for fixup scheduling.

**Additional context**

This idea was prototyped during a vector-index loader experiment
(`vecbench` loading 1M vectors). On its own, replacing the
`EstimatePartitionCount` + `AddSplit` call site with a probabilistic
fixup-add was the change that allowed high-concurrency / large-batch
configurations to run cleanly; prior configurations either deadlocked
the fixup pipeline or showed elevated transaction retry rates. Combined
with other independent changes, the full stack moved the 1M-vector load
from ~12m13s to ~7m44s; the probabilistic-fixup change was load-bearing
for that result.

Epic: none

Jira issue: CRDB-64257

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.