🌐 AI搜索 & 代理 主页
Skip to content

Commit 7df159a

Browse files
hlinnakahlinnaka
committed
Delete empty pages during GiST VACUUM.
To do this, we scan GiST two times. In the first pass we make note of empty leaf pages and internal pages. At second pass we scan through internal pages, looking for downlinks to the empty pages. Deleting internal pages is still not supported, like in nbtree, the last child of an internal page is never deleted. That means that if you have a workload where new keys are always inserted to different area than where old keys are removed, the index will still grow without bound. But the rate of growth will be an order of magnitude slower than before. Author: Andrey Borodin Discussion: https://www.postgresql.org/message-id/B1E4DF12-6CD3-4706-BDBD-BF3283328F60@yandex-team.ru
1 parent df816f6 commit 7df159a

File tree

11 files changed

+626
-49
lines changed

11 files changed

+626
-49
lines changed

‎src/backend/access/gist/README‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -413,6 +413,54 @@ emptied yet; tuples never move upwards in the tree. The final emptying loops
413413
through buffers at a given level until all buffers at that level have been
414414
emptied, and then moves down to the next level.
415415

416+
Bulk delete algorithm (VACUUM)
417+
------------------------------
418+
419+
VACUUM works in two stages:
420+
421+
In the first stage, we scan the whole index in physical order. To make sure
422+
that we don't miss any dead tuples because a concurrent page split moved them,
423+
we check the F_FOLLOW_RIGHT flags and NSN on each page, to detect if the
424+
page has been concurrently split. If a concurrent page split is detected, and
425+
one half of the page was moved to a position that we already scanned, we
426+
"jump backwards" to scan the page again. This is the same mechanism that
427+
B-tree VACUUM uses, but because we already have NSNs on pages, to detect page
428+
splits during searches, we don't need a "vacuum cycle ID" concept for that
429+
like B-tree does.
430+
431+
While we scan all the pages, we also make note of any completely empty leaf
432+
pages. We will try to unlink them from the tree in the second stage. We also
433+
record the block numbers of all internal pages; they are needed in the second
434+
stage, to locate parents of the empty pages.
435+
436+
In the second stage, we try to unlink any empty leaf pages from the tree, so
437+
that their space can be reused. In order to delete an empty page, its
438+
downlink must be removed from the parent. We scan all the internal pages,
439+
whose block numbers we memorized in the first stage, and look for downlinks
440+
to pages that we have memorized as being empty. Whenever we find one, we
441+
acquire a lock on the parent and child page, re-check that the child page is
442+
still empty. Then, we remove the downlink and mark the child as deleted, and
443+
release the locks.
444+
445+
The insertion algorithm would get confused, if an internal page was completely
446+
empty. So we never delete the last child of an internal page, even if it's
447+
empty. Currently, we only support deleting leaf pages.
448+
449+
This page deletion algorithm works on a best-effort basis. It might fail to
450+
find a downlink, if a concurrent page split moved it after the first stage.
451+
In that case, we won't be able to remove all empty pages. That's OK, it's
452+
not expected to happen very often, and hopefully the next VACUUM will clean
453+
it up.
454+
455+
When we have deleted a page, it's possible that an in-progress search will
456+
still descend on the page, if it saw the downlink before we removed it. The
457+
search will see that it is deleted, and ignore it, but as long as that can
458+
happen, we cannot reuse the page. To "wait out" any in-progress searches, when
459+
a page is deleted, it's labeled with the current next-transaction counter
460+
value. The page is not recycled, until that XID is no longer visible to
461+
anyone. That's much more conservative than necessary, but let's keep it
462+
simple.
463+
416464

417465
Authors:
418466
Teodor Sigaev <teodor@sigaev.ru>

‎src/backend/access/gist/gist.c‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -704,6 +704,9 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
704704
GISTInsertStack *item;
705705
OffsetNumber downlinkoffnum;
706706

707+
/* currently, internal pages are never deleted */
708+
Assert(!GistPageIsDeleted(stack->page));
709+
707710
downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
708711
iid = PageGetItemId(stack->page, downlinkoffnum);
709712
idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
@@ -838,6 +841,18 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
838841
}
839842
}
840843

844+
/*
845+
* The page might have been deleted after we scanned the parent
846+
* and saw the downlink.
847+
*/
848+
if (GistPageIsDeleted(stack->page))
849+
{
850+
UnlockReleaseBuffer(stack->buffer);
851+
xlocked = false;
852+
state.stack = stack = stack->parent;
853+
continue;
854+
}
855+
841856
/* now state.stack->(page, buffer and blkno) points to leaf page */
842857

843858
gistinserttuple(&state, stack, giststate, itup,

‎src/backend/access/gist/gistutil.c‎

Lines changed: 31 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
#include "storage/lmgr.h"
2424
#include "utils/float.h"
2525
#include "utils/syscache.h"
26+
#include "utils/snapmgr.h"
2627
#include "utils/lsyscache.h"
2728

2829

@@ -829,13 +830,31 @@ gistNewBuffer(Relation r)
829830
{
830831
Page page = BufferGetPage(buffer);
831832

833+
/*
834+
* If the page was never initialized, it's OK to use.
835+
*/
832836
if (PageIsNew(page))
833-
return buffer; /* OK to use, if never initialized */
837+
return buffer;
834838

835839
gistcheckpage(r, buffer);
836840

837-
if (GistPageIsDeleted(page))
838-
return buffer; /* OK to use */
841+
/*
842+
* Otherwise, recycle it if deleted, and too old to have any processes
843+
* interested in it.
844+
*/
845+
if (gistPageRecyclable(page))
846+
{
847+
/*
848+
* If we are generating WAL for Hot Standby then create a
849+
* WAL record that will allow us to conflict with queries
850+
* running on standby, in case they have snapshots older
851+
* than the page's deleteXid.
852+
*/
853+
if (XLogStandbyInfoActive() && RelationNeedsWAL(r))
854+
gistXLogPageReuse(r, blkno, GistPageGetDeleteXid(page));
855+
856+
return buffer;
857+
}
839858

840859
LockBuffer(buffer, GIST_UNLOCK);
841860
}
@@ -859,6 +878,15 @@ gistNewBuffer(Relation r)
859878
return buffer;
860879
}
861880

881+
/* Can this page be recycled yet? */
882+
bool
883+
gistPageRecyclable(Page page)
884+
{
885+
return PageIsNew(page) ||
886+
(GistPageIsDeleted(page) &&
887+
TransactionIdPrecedes(GistPageGetDeleteXid(page), RecentGlobalXmin));
888+
}
889+
862890
bytea *
863891
gistoptions(Datum reloptions, bool validate)
864892
{

0 commit comments

Comments
 (0)