Conversation
jitokim
force-pushed
the
fix/hnsw-insertpage-unfittable-slot
branch
from
September 10, 2026 10:12
bf88fcb to
360efe8
Compare
HnswFreeOffset() claimed *newInsertPage on the first deleted element it encountered, before checking whether that slot could hold the incoming element. For fixed-size types every slot fits so this was harmless, but for variable-size types (sparsevec) a slot freed by a small element cannot hold a larger one. The metapage insertPage was then rewound to that page on every insert, and each subsequent larger insert walked the index from there to the end. Latch newInsertPage only when the element tuple fits (pageFree >= etupSize). The freed neighbor tuple is always at least a level-0 neighbor tuple, so this matches the "first page where element at level 0 can fit" criterion that AddElementOnDisk() already uses for minCombinedSize, and keeps the two updates of the same variable consistent. Fixes pgvector#1025
jitokim
force-pushed
the
fix/hnsw-insertpage-unfittable-slot
branch
from
September 10, 2026 10:14
360efe8 to
cd5a316
Compare
Author
|
Pushed two follow-up commits:
Verified on |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
HnswFreeOffset()latches*newInsertPageon the first deleted element it finds, before checking whether that slot can hold the element being inserted. With fixed-size types every slot fits, so this is harmless. Withsparseveca slot freed by a small element cannot hold a larger one, so after aVACUUMthe metapageinsertPageis rewound to a page that never fits, and every subsequent larger insert walks the index from there to the end — a full index scan per insert, permanently.Fixes #1025
Change
Latch
newInsertPageonly when the element tuple fits (pageFree >= etupSize). The freed neighbor tuple is always at least a level-0 neighbor tuple, so checkingetupSizealone is sufficient. This matches the "first page where element at level 0 can fit" criterionAddElementOnDisk()already uses forminCombinedSize, so both updates ofnewInsertPagefollow the same rule.An earlier revision of this PR checked the full fit for the current element (
pageFree >= etupSize && npageFree >= ntupSize). That over-constrains for fixed-size types: a level-N element needs a larger neighbor tuple than a level-0 slot provides, so it would skip level-0 slots without latching and the next insert would start past them. Measured onvector(64)m=16 (200k rows, 5% scattered delete, VACUUM, 50k inserts, 5 runs): ~4% of freed slots left unreused, +0.2% index size, recovered on the next VACUUM. The current revision leaves zero such slots in 12/12 runs (counted viapageinspectasdeleted=1element tuples).Verification
sparsevec(10000), 100k rows at nnz=50, scattered 5% delete +VACUUM, then nnz=500 inserts — buffers per insert:VACUUMmake installcheck14/14 on this branch (PostgreSQL 16).