mirror of
https://github.com/qdrant/qdrant.git
synced 2026-09-21 13:37:46 -05:00
901fa8e865
`PostingList::upsert` ends in `propagate_max_next_weight_to_the_left`, whose doc
comment states "If an entry has a weight larger than `max_next_weight`, the
propagation stops". It never stopped — the loop always walked the entire prefix.
Record ids ascend during an upload, so every insert lands at the end, walks the
whole list, and growing a posting list to length L costs O(L²). On the NeurIPS
2023 sparse base set (MS MARCO / SPLADE) the hottest dimension appears in ~66% of
documents, so at 1M points its posting list holds 660k elements and every new
point rewrites all of them.
Two changes to `PostingList`:
* restore the early exit — every entry satisfies the same recurrence the loop
walks, `max_next_weight[i] = max(max_next_weight[i + 1], weight[i + 1])`, so
once an entry already holds the value being written, every entry to its left is
correct too;
* add an append fast path — when the incoming record id is past the last stored
id, push directly instead of binary searching a list that can hold millions of
elements.
Neither changes what is stored. An index grown by `upsert` stays identical to one
built by `InvertedIndexBuilder`, `max_next_weight` included, which is what a
segment reload depends on; searches return identical results.
Building an `InvertedIndexRam` one point at a time, SPLADE vectors:
points before after
100k 2,216/s 124,016/s
1M 250/s 114,422/s
Uploading 1M of those points to a single node: 72.2s -> 23.7s with default
collection settings, and 839.8s -> 29.5s with `indexing_threshold: 0`, which
stops segments converting and is the documented way to speed up a bulk load.
Claude-Session: https://claude.ai/code/session_01HXjykBsMZaRNrP17o2fuEJ
Co-authored-by: Andrey Vasnetsov <andrey@qdrant.com>
Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>