Conversation
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
360efe8 to
cd5a316
Compare
|
Pushed two follow-up commits:
Verified on |
|
Hi @jitokim, thanks for the PR. The proposed approach has its own drawback - if a sparsevec with a large nnz is inserted after a vacuum, the insert page will be moved to the end of the index and none of the space will be reused. One idea to partially mitigate this is to only move the insert page a certain number of free slots. --- a/src/hnswinsert.c
+++ b/src/hnswinsert.c
@@ -42,10 +42,11 @@ GetInsertPage(Relation index)
* Check for a free offset
*/
static bool
-HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size etupSize, Size ntupSize, Buffer *nbuf, Page *npage, OffsetNumber *freeOffno, OffsetNumber *freeNeighborOffno, BlockNumber *newInsertPage, uint8 *tupleVersion)
+HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size etupSize, Size ntupSize, Buffer *nbuf, Page *npage, OffsetNumber *freeOffno, OffsetNumber *freeNeighborOffno, BlockNumber *newInsertPage, int *newInsertPageTries, uint8 *tupleVersion)
{
OffsetNumber offno;
OffsetNumber maxoffno = PageGetMaxOffsetNumber(page);
+ int startingTries = *newInsertPageTries;
for (offno = FirstOffsetNumber; offno <= maxoffno; offno = OffsetNumberNext(offno))
{
@@ -65,9 +66,6 @@ HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size
Size pageFree;
Size npageFree;
- if (!BlockNumberIsValid(*newInsertPage))
- *newInsertPage = elementPage;
-
if (neighborPage == elementPage)
{
*nbuf = buf;
@@ -99,6 +97,20 @@ HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size
else if (pageFree >= etupSize)
npageFree += pageFree - etupSize;
+ /*
+ * Keep track of first page where element at level 0 can fit. For
+ * variable-length items (sparsevec), skip up to 3 pages to
+ * prevent large scans.
+ */
+ if (!BlockNumberIsValid(*newInsertPage))
+ {
+ if (pageFree >= etupSize || *newInsertPageTries >= 3)
+ *newInsertPage = elementPage;
+ /* Only increment once per page */
+ else if (*newInsertPageTries == startingTries)
+ (*newInsertPageTries)++;
+ }
+
/* Check for space */
if (pageFree >= etupSize && npageFree >= ntupSize)
{
@@ -160,6 +172,7 @@ AddElementOnDisk(Relation index, HnswElement e, int m, BlockNumber insertPage, B
OffsetNumber freeOffno = InvalidOffsetNumber;
OffsetNumber freeNeighborOffno = InvalidOffsetNumber;
BlockNumber newInsertPage = InvalidBlockNumber;
+ int newInsertPageTries = 0;
uint8 tupleVersion;
char *base = NULL;
@@ -210,7 +223,7 @@ AddElementOnDisk(Relation index, HnswElement e, int m, BlockNumber insertPage, B
}
/* Next, try space from a deleted element */
- if (HnswFreeOffset(index, buf, page, e, etupSize, ntupSize, &nbuf, &npage, &freeOffno, &freeNeighborOffno, &newInsertPage, &tupleVersion))
+ if (HnswFreeOffset(index, buf, page, e, etupSize, ntupSize, &nbuf, &npage, &freeOffno, &freeNeighborOffno, &newInsertPage, &newInsertPageTries, &tupleVersion))
{
if (nbuf != buf)
{This would prevent it from getting stuck on sparsevec with a small nnz. Another approach would be to use the free space map. Will spend some time trying this. |
…element With the previous change, a larger element that does not fit the slots freed by VACUUM scans past them to the end of the index and moves insertPage there, so smaller elements stop reusing the freed slots until the next VACUUM. Count the pages whose deleted slots are all too small for the element. After a few of them, jump to the last page instead of scanning the rest of the index, and keep insertPage where it is so the freed slots are still reused by elements that fit them. The last page is only followed if it is initialized. A page that was added by a crashed or failed insert is not linked from the previous page.
|
Thanks for the feedback, @ankane. Reproduced: after VACUUM, a few large inserts move insertPage to the tail and small inserts stop reusing the freed slots (+1,259 pages vs +10 on master, 50k rows). The tries-bounded latch keeps reuse, but repeat large inserts still scan to the end of the index ( Pushed a version that bounds the scan instead: after 3 pages whose deleted slots are all too small, jump to the last page and leave insertPage unchanged. Reuse matches master, large inserts stay near baseline, and That said, FSM sounds like the better fix. Happy to close this if you go that way. |
2 participants
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).