From: Heikki Linnakangas <hlinnaka@iki.fi>
To: Andrey Borodin <x4mmm@yandex-team.ru>
To: Michael Paquier <michael@paquier.xyz>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Robert Haas <robertmhaas@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Костя Кузнецов <chapaev28@ya.ru>
Subject: Re: GiST VACUUM
Date: Wed, 2 Jan 2019 17:36:33 +0200
Message-ID: <9f11fd6c-aa0f-42e9-4ae2-b5cc8c148658@iki.fi> (raw)
In-Reply-To: <d7e89e1b-efd4-1464-f03d-4ba4ea9e1835@iki.fi>
References: <479336FE-B713-4DFB-9661-9BFCCA70F4EF@yandex-team.ru>
<51675201-3F1C-4796-ADB4-28D0B35E9CF0@yandex-team.ru>
<651572F0-65C3-4285-85FC-50E81B1199F1@yandex-team.ru>
<CAEepm=1vznVTZf01f4KNVJEa4m4tCgtBuumgmY8q=g+S=Gdt5A@mail.gmail.com>
<2AF4B7F1-ABCF-4602-8AF8-06EA45191BFC@yandex-team.ru>
<844f3373-486e-a34d-d5a1-6a048e19355c@iki.fi>
<4A1FF988-A69D-4607-8A6E-B3EC0FD6C2CF@yandex-team.ru>
<43f15ab5-dd95-97d4-658b-e9954ca986a6@iki.fi>
<DABC2BB9-154A-47E2-B1D9-B58A4023E6D7@yandex-team.ru>
<E8FDC7F0-0516-4A84-B754-4CC92801E5F5@yandex-team.ru>
<20181002011404.GU11712@paquier.xyz>
<C1D00194-9A4D-4DE1-AAFE-6DA478A15207@yandex-team.ru>
<d7e89e1b-efd4-1464-f03d-4ba4ea9e1835@iki.fi>
On 02/01/2019 17:35, Heikki Linnakangas wrote:
> On 28/10/2018 19:32, Andrey Borodin wrote:
>> Hi everyone!
>>
>>> 2 окт. 2018 г., в 6:14, Michael Paquier <michael@paquier.xyz> написал(а):
>>> Andrey, your latest patch does not apply. I am moving this to the next
>>> CF, waiting for your input.
>>
>> I'm doing preps for CF.
>> Here's rebased version.
>
> Thanks, I had another look at these.
Here are new patch versions, with the fixes I mentioned. Forgot to
attach these earlier.
- Heikki
Attachments:download all (2 files, .tar.gz)0001-Physical-GiST-scan-in-VACUUM-v18-heikki.patch (text/x-patch, 17.0K) download
From 46456dbf1d07aaf3e6963035a02aaa060decace3 Mon Sep 17 00:00:00 2001
From: Andrey Borodin <amborodin@acm.org>
Date: Sun, 28 Oct 2018 22:20:58 +0500
Subject: [PATCH 1/2] Physical GiST scan in VACUUM v18-heikki
---
src/backend/access/gist/gist.c | 8 +-
src/backend/access/gist/gistvacuum.c | 430 +++++++++++++++------------
2 files changed, 247 insertions(+), 191 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.cindex a2cb84800e8..d42e810c6b3 100644--- a/src/backend/access/gist/gist.c+++ b/src/backend/access/gist/gist.c@@ -38,7 +38,7 @@ static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool releasebuf);
-static void gistvacuumpage(Relation rel, Page page, Buffer buffer,+static void gistprunepage(Relation rel, Page page, Buffer buffer,
Relation heapRel);
@@ -261,7 +261,7 @@ gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
*/
if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
{
- gistvacuumpage(rel, page, buffer, heapRel);+ gistprunepage(rel, page, buffer, heapRel);
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
}
@@ -1544,11 +1544,11 @@ freeGISTstate(GISTSTATE *giststate)
}
/*
- * gistvacuumpage() -- try to remove LP_DEAD items from the given page.+ * gistprunepage() -- try to remove LP_DEAD items from the given page.
* Function assumes that buffer is exclusively locked.
*/
static void
-gistvacuumpage(Relation rel, Page page, Buffer buffer, Relation heapRel)+gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
{
OffsetNumber deletable[MaxIndexTuplesPerPage];
int ndeletable = 0;
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.cindex 5948218c779..4fb32bf76bf 100644--- a/src/backend/access/gist/gistvacuum.c+++ b/src/backend/access/gist/gistvacuum.c@@ -21,6 +21,34 @@
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
+/* Working state needed by gistbulkdelete */+typedef struct+{+ IndexVacuumInfo *info;+ IndexBulkDeleteResult *stats;+ IndexBulkDeleteCallback callback;+ void *callback_state;+ GistNSN startNSN;+ BlockNumber totFreePages; /* true total # of free pages */+} GistVacState;++static void gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,+ IndexBulkDeleteCallback callback, void *callback_state);+static void gistvacuumpage(GistVacState *vstate, BlockNumber blkno,+ BlockNumber orig_blkno);++IndexBulkDeleteResult *+gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,+ IndexBulkDeleteCallback callback, void *callback_state)+{+ /* allocate stats if first time through, else re-use existing struct */+ if (stats == NULL)+ stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));++ gistvacuumscan(info, stats, callback, callback_state);++ return stats;+}
/*
* VACUUM cleanup: update FSM
@@ -28,104 +56,36 @@
IndexBulkDeleteResult *
gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
{
- Relation rel = info->index;- BlockNumber npages,- blkno;- BlockNumber totFreePages;- double tuplesCount;- bool needLock;-
/* No-op in ANALYZE ONLY mode */
if (info->analyze_only)
return stats;
- /* Set up all-zero stats if gistbulkdelete wasn't called */+ /*+ * If gistbulkdelete was called, we need not do anything, just return the+ * stats from the latest gistbulkdelete call. If it wasn't called, we+ * still need to do a pass over the index, to obtain index statistics.+ */
if (stats == NULL)
+ {
stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
+ gistvacuumscan(info, stats, NULL, NULL);+ }
/*
- * Need lock unless it's local to this backend.+ * It's quite possible for us to be fooled by concurrent page splits into+ * double-counting some index tuples, so disbelieve any total that exceeds+ * the underlying heap's count ... if we know that accurately. Otherwise+ * this might just make matters worse.
*/
- needLock = !RELATION_IS_LOCAL(rel);-- /* try to find deleted pages */- if (needLock)- LockRelationForExtension(rel, ExclusiveLock);- npages = RelationGetNumberOfBlocks(rel);- if (needLock)- UnlockRelationForExtension(rel, ExclusiveLock);-- totFreePages = 0;- tuplesCount = 0;- for (blkno = GIST_ROOT_BLKNO + 1; blkno < npages; blkno++)+ if (!info->estimated_count)
{
- Buffer buffer;- Page page;-- vacuum_delay_point();-- buffer = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,- info->strategy);- LockBuffer(buffer, GIST_SHARE);- page = (Page) BufferGetPage(buffer);-- if (PageIsNew(page) || GistPageIsDeleted(page))- {- totFreePages++;- RecordFreeIndexPage(rel, blkno);- }- else if (GistPageIsLeaf(page))- {- /* count tuples in index (considering only leaf tuples) */- tuplesCount += PageGetMaxOffsetNumber(page);- }- UnlockReleaseBuffer(buffer);+ if (stats->num_index_tuples > info->num_heap_tuples)+ stats->num_index_tuples = info->num_heap_tuples;
}
- /* Finally, vacuum the FSM */- IndexFreeSpaceMapVacuum(info->index);-- /* return statistics */- stats->pages_free = totFreePages;- if (needLock)- LockRelationForExtension(rel, ExclusiveLock);- stats->num_pages = RelationGetNumberOfBlocks(rel);- if (needLock)- UnlockRelationForExtension(rel, ExclusiveLock);- stats->num_index_tuples = tuplesCount;- stats->estimated_count = false;-
return stats;
}
-typedef struct GistBDItem-{- GistNSN parentlsn;- BlockNumber blkno;- struct GistBDItem *next;-} GistBDItem;--static void-pushStackIfSplited(Page page, GistBDItem *stack)-{- GISTPageOpaque opaque = GistPageGetOpaque(page);-- if (stack->blkno != GIST_ROOT_BLKNO && !XLogRecPtrIsInvalid(stack->parentlsn) &&- (GistFollowRight(page) || stack->parentlsn < GistPageGetNSN(page)) &&- opaque->rightlink != InvalidBlockNumber /* sanity check */ )- {- /* split page detected, install right link to the stack */-- GistBDItem *ptr = (GistBDItem *) palloc(sizeof(GistBDItem));-- ptr->blkno = opaque->rightlink;- ptr->parentlsn = stack->parentlsn;- ptr->next = stack->next;- stack->next = ptr;- }-}--
/*
* Bulk deletion of all index entries pointing to a set of heap tuples and
* check invalid tuples left after upgrade.
@@ -134,141 +94,237 @@ pushStackIfSplited(Page page, GistBDItem *stack)
*
* Result: a palloc'd struct containing statistical info for VACUUM displays.
*/
-IndexBulkDeleteResult *-gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,+static void+gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
IndexBulkDeleteCallback callback, void *callback_state)
{
Relation rel = info->index;
- GistBDItem *stack,- *ptr;+ GistVacState vstate;+ BlockNumber num_pages;+ bool needLock;+ BlockNumber blkno;- /* first time through? */- if (stats == NULL)- stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));- /* we'll re-count the tuples each time */+ /*+ * Reset counts that will be incremented during the scan; needed in case+ * of multiple scans during a single VACUUM command.+ */
stats->estimated_count = false;
stats->num_index_tuples = 0;
+ stats->pages_deleted = 0;++ /* Set up info to pass down to gistvacuumpage */+ vstate.info = info;+ vstate.stats = stats;+ vstate.callback = callback;+ vstate.callback_state = callback_state;+ if (RelationNeedsWAL(rel))+ vstate.startNSN = GetInsertRecPtr();+ else+ vstate.startNSN = gistGetFakeLSN(rel);+ vstate.totFreePages = 0;- stack = (GistBDItem *) palloc0(sizeof(GistBDItem));- stack->blkno = GIST_ROOT_BLKNO;-- while (stack)- {- Buffer buffer;- Page page;- OffsetNumber i,- maxoff;- IndexTuple idxtuple;- ItemId iid;-- buffer = ReadBufferExtended(rel, MAIN_FORKNUM, stack->blkno,- RBM_NORMAL, info->strategy);- LockBuffer(buffer, GIST_SHARE);- gistcheckpage(rel, buffer);- page = (Page) BufferGetPage(buffer);-- if (GistPageIsLeaf(page))- {- OffsetNumber todelete[MaxOffsetNumber];- int ntodelete = 0;+ /*+ * Need lock unless it's local to this backend.+ */+ needLock = !RELATION_IS_LOCAL(rel);- LockBuffer(buffer, GIST_UNLOCK);- LockBuffer(buffer, GIST_EXCLUSIVE);+ /*+ * The outer loop iterates over all index pages, in physical order (we+ * hope the kernel will cooperate in providing read-ahead for speed). It+ * is critical that we visit all leaf pages, including ones added after we+ * start the scan, else we might fail to delete some deletable tuples.+ * Hence, we must repeatedly check the relation length. We must acquire+ * the relation-extension lock while doing so to avoid a race condition:+ * if someone else is extending the relation, there is a window where+ * bufmgr/smgr have created a new all-zero page but it hasn't yet been+ * write-locked by gistNewBuffer(). If we manage to scan such a page+ * here, we'll improperly assume it can be recycled. Taking the lock+ * synchronizes things enough to prevent a problem: either num_pages won't+ * include the new page, or gistNewBuffer already has write lock on the+ * buffer and it will be fully initialized before we can examine it. (See+ * also vacuumlazy.c, which has the same issue.) Also, we need not worry+ * if a page is added immediately after we look; the page splitting code+ * already has write-lock on the left page before it adds a right page, so+ * we must already have processed any tuples due to be moved into such a+ * page.+ *+ * We can skip locking for new or temp relations, however, since no one+ * else could be accessing them.+ */+ needLock = !RELATION_IS_LOCAL(rel);- page = (Page) BufferGetPage(buffer);- if (stack->blkno == GIST_ROOT_BLKNO && !GistPageIsLeaf(page))- {- /* only the root can become non-leaf during relock */- UnlockReleaseBuffer(buffer);- /* one more check */- continue;- }+ blkno = GIST_ROOT_BLKNO;+ for (;;)+ {+ /* Get the current relation length */+ if (needLock)+ LockRelationForExtension(rel, ExclusiveLock);+ num_pages = RelationGetNumberOfBlocks(rel);+ if (needLock)+ UnlockRelationForExtension(rel, ExclusiveLock);++ /* Quit if we've scanned the whole relation */+ if (blkno >= num_pages)+ break;+ /* Iterate over pages, then loop back to recheck length */+ for (; blkno < num_pages; blkno++)+ gistvacuumpage(&vstate, blkno, blkno);+ }- /*- * check for split proceeded after look at parent, we should check- * it after relock- */- pushStackIfSplited(page, stack);+ /*+ * If we found any recyclable pages (and recorded them in the FSM), then+ * forcibly update the upper-level FSM pages to ensure that searchers can+ * find them. It's possible that the pages were also found during+ * previous scans and so this is a waste of time, but it's cheap enough+ * relative to scanning the index that it shouldn't matter much, and+ * making sure that free pages are available sooner not later seems+ * worthwhile.+ *+ * Note that if no recyclable pages exist, we don't bother vacuuming the+ * FSM at all.+ */+ if (vstate.totFreePages > 0)+ IndexFreeSpaceMapVacuum(rel);- /*- * Remove deletable tuples from page- */+ /* update statistics */+ stats->num_pages = num_pages;+ stats->pages_free = vstate.totFreePages;+}- maxoff = PageGetMaxOffsetNumber(page);+/*+ * gistvacuumpage --- VACUUM one page+ *+ * This processes a single page for gistbulkdelete(). In some cases we+ * must go back and re-examine previously-scanned pages; this routine+ * recurses when necessary to handle that case.+ *+ * blkno is the page to process. orig_blkno is the highest block number+ * reached by the outer gistvacuumscan loop (the same as blkno, unless we+ * are recursing to re-examine a previous page).+ */+static void+gistvacuumpage(GistVacState *vstate, BlockNumber blkno, BlockNumber orig_blkno)+{+ IndexVacuumInfo *info = vstate->info;+ IndexBulkDeleteResult *stats = vstate->stats;+ IndexBulkDeleteCallback callback = vstate->callback;+ void *callback_state = vstate->callback_state;+ Relation rel = info->index;+ Buffer buffer;+ Page page;+ BlockNumber recurse_to;- for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))- {- iid = PageGetItemId(page, i);- idxtuple = (IndexTuple) PageGetItem(page, iid);+restart:+ recurse_to = InvalidBlockNumber;- if (callback(&(idxtuple->t_tid), callback_state))- todelete[ntodelete++] = i;- else- stats->num_index_tuples += 1;- }+ /* call vacuum_delay_point while not holding any buffer lock */+ vacuum_delay_point();- stats->tuples_removed += ntodelete;+ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,+ info->strategy);- if (ntodelete)- {- START_CRIT_SECTION();+ /*+ * We are not going to stay here for a long time, agressively grab an+ * exclusive lock.+ */+ LockBuffer(buffer, GIST_EXCLUSIVE);+ page = (Page) BufferGetPage(buffer);- MarkBufferDirty(buffer);+ if (PageIsNew(page) || GistPageIsDeleted(page))+ {+ UnlockReleaseBuffer(buffer);+ vstate->totFreePages++;+ RecordFreeIndexPage(rel, blkno);+ return;+ }- PageIndexMultiDelete(page, todelete, ntodelete);- GistMarkTuplesDeleted(page);+ if (GistPageIsLeaf(page))+ {+ OffsetNumber todelete[MaxOffsetNumber];+ int ntodelete = 0;+ GISTPageOpaque opaque = GistPageGetOpaque(page);+ OffsetNumber maxoff = PageGetMaxOffsetNumber(page);++ /*+ * Check whether we need to recurse back to earlier pages. What we+ * are concerned about is a page split that happened since we started+ * the vacuum scan. If the split moved some tuples to a lower page+ * then we might have missed 'em. If so, set up for tail recursion.+ */+ if ((GistFollowRight(page) ||+ vstate->startNSN < GistPageGetNSN(page)) &&+ (opaque->rightlink != InvalidBlockNumber) &&+ (opaque->rightlink < orig_blkno))+ {+ recurse_to = opaque->rightlink;+ }- if (RelationNeedsWAL(rel))- {- XLogRecPtr recptr;+ /*+ * Scan over all items to see which ones need deleted according to the+ * callback function.+ */+ if (callback)+ {+ OffsetNumber off;- recptr = gistXLogUpdate(buffer,- todelete, ntodelete,- NULL, 0, InvalidBuffer);- PageSetLSN(page, recptr);- }- else- PageSetLSN(page, gistGetFakeLSN(rel));+ for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))+ {+ ItemId iid = PageGetItemId(page, off);+ IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);- END_CRIT_SECTION();+ if (callback(&(idxtuple->t_tid), callback_state))+ todelete[ntodelete++] = off;
}
-
}
- else++ /*+ * Apply any needed deletes. We issue just one WAL record per page,+ * so as to minimize WAL traffic.+ */+ if (ntodelete)
{
- /* check for split proceeded after look at parent */- pushStackIfSplited(page, stack);+ START_CRIT_SECTION();- maxoff = PageGetMaxOffsetNumber(page);+ MarkBufferDirty(buffer);- for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))+ PageIndexMultiDelete(page, todelete, ntodelete);+ GistMarkTuplesDeleted(page);++ if (RelationNeedsWAL(rel))
{
- iid = PageGetItemId(page, i);- idxtuple = (IndexTuple) PageGetItem(page, iid);-- ptr = (GistBDItem *) palloc(sizeof(GistBDItem));- ptr->blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));- ptr->parentlsn = BufferGetLSNAtomic(buffer);- ptr->next = stack->next;- stack->next = ptr;-- if (GistTupleIsInvalid(idxtuple))- ereport(LOG,- (errmsg("index \"%s\" contains an inner tuple marked as invalid",- RelationGetRelationName(rel)),- errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),- errhint("Please REINDEX it.")));+ XLogRecPtr recptr;++ recptr = gistXLogUpdate(buffer,+ todelete, ntodelete,+ NULL, 0, InvalidBuffer);+ PageSetLSN(page, recptr);
}
- }+ else+ PageSetLSN(page, gistGetFakeLSN(rel));- UnlockReleaseBuffer(buffer);+ END_CRIT_SECTION();++ stats->tuples_removed += ntodelete;+ /* must recompute maxoff */+ maxoff = PageGetMaxOffsetNumber(page);+ }- ptr = stack->next;- pfree(stack);- stack = ptr;+ stats->num_index_tuples += maxoff - FirstOffsetNumber + 1;- vacuum_delay_point();
}
- return stats;+ UnlockReleaseBuffer(buffer);++ /*+ * This is really tail recursion, but if the compiler is too stupid to+ * optimize it as such, we'd eat an uncomfortably large amount of stack+ * space per recursion level (due to the deletable[] array). A failure is+ * improbable since the number of levels isn't likely to be large ... but+ * just in case, let's hand-optimize into a loop.+ */+ if (recurse_to != InvalidBlockNumber)+ {+ blkno = recurse_to;+ goto restart;+ }
}
--
2.19.2
0002-Delete-pages-during-GiST-VACUUM-v18-heikki.patch (text/x-patch, 18.9K) download
From 62fbe0ce5506e006b92dbfb07aee7414040d982f Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Wed, 2 Jan 2019 16:00:16 +0200
Subject: [PATCH 2/2] Delete pages during GiST VACUUM v18-heikki
---
src/backend/access/gist/README | 14 +++
src/backend/access/gist/gist.c | 18 +++
src/backend/access/gist/gistutil.c | 3 +-
src/backend/access/gist/gistvacuum.c | 152 ++++++++++++++++++++++++-
src/backend/access/gist/gistxlog.c | 60 ++++++++++
src/backend/access/rmgrdesc/gistdesc.c | 3 +
src/backend/nodes/bitmapset.c | 16 +++
src/include/access/gist.h | 3 +
src/include/access/gist_private.h | 7 +-
src/include/access/gistxlog.h | 10 +-
src/include/nodes/bitmapset.h | 1 +
src/test/regress/expected/gist.out | 4 +-
src/test/regress/sql/gist.sql | 4 +-
13 files changed, 282 insertions(+), 13 deletions(-)
diff --git a/src/backend/access/gist/README b/src/backend/access/gist/READMEindex 02228662b81..c84359de310 100644--- a/src/backend/access/gist/README+++ b/src/backend/access/gist/README@@ -413,6 +413,20 @@ emptied yet; tuples never move upwards in the tree. The final emptying loops
through buffers at a given level until all buffers at that level have been
emptied, and then moves down to the next level.
+Bulk delete algorithm (VACUUM)+------------------------------++Function gistbulkdelete() is responsible for marking empty leaf pages as free+so that they can be used it allocate newly split pages. To find this pages+function scans index in physical order.++Physical scan reads the entire index from the first page to last. This scan+maintains information necessary to collect block numbers of internal pages+that need cleansing and block number of empty leafs.++After the scan, for each internal pages under exclusive lock, each potentially+free leaf page is examined. gistbulkdelete() never delete last one reference+from internal page to preserve balanced tree properties.
Authors:
Teodor Sigaev <teodor@sigaev.ru>
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.cindex d42e810c6b3..bbfd5a92b88 100644--- a/src/backend/access/gist/gist.c+++ b/src/backend/access/gist/gist.c@@ -704,6 +704,11 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
GISTInsertStack *item;
OffsetNumber downlinkoffnum;
+ /*+ * Currently internal pages are not deleted during vacuum,+ * so we do not need to check if page is deleted+ */+
downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
iid = PageGetItemId(stack->page, downlinkoffnum);
idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
@@ -838,6 +843,19 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
}
}
+ /*+ * Leaf pages can be left deleted but still referenced+ * until it's space is reused. Downlink to this page may be already+ * removed from the internal page, but this scan can posess it.+ */+ if(GistPageIsDeleted(stack->page))+ {+ UnlockReleaseBuffer(stack->buffer);+ xlocked = false;+ state.stack = stack = stack->parent;+ continue;+ }+
/* now state.stack->(page, buffer and blkno) points to leaf page */
gistinserttuple(&state, stack, giststate, itup,
diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.cindex 70627e5df66..adb316c6afa 100644--- a/src/backend/access/gist/gistutil.c+++ b/src/backend/access/gist/gistutil.c@@ -23,6 +23,7 @@
#include "storage/lmgr.h"
#include "utils/float.h"
#include "utils/syscache.h"
+#include "utils/snapmgr.h"
#include "utils/lsyscache.h"
@@ -807,7 +808,7 @@ gistNewBuffer(Relation r)
gistcheckpage(r, buffer);
- if (GistPageIsDeleted(page))+ if (GistPageIsDeleted(page) && TransactionIdPrecedes(GistPageGetDeleteXid(page), RecentGlobalDataXmin))
return buffer; /* OK to use */
LockBuffer(buffer, GIST_UNLOCK);
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.cindex 4fb32bf76bf..bac6b8c77af 100644--- a/src/backend/access/gist/gistvacuum.c+++ b/src/backend/access/gist/gistvacuum.c@@ -16,8 +16,10 @@
#include "access/genam.h"
#include "access/gist_private.h"
+#include "access/transam.h"
#include "commands/vacuum.h"
#include "miscadmin.h"
+#include "nodes/bitmapset.h"
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
@@ -30,6 +32,10 @@ typedef struct
void *callback_state;
GistNSN startNSN;
BlockNumber totFreePages; /* true total # of free pages */
+ BlockNumber emptyPages;++ Bitmapset *internalPagesMap;+ Bitmapset *emptyLeafPagesMap;
} GistVacState;
static void gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
@@ -91,8 +97,6 @@ gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
* check invalid tuples left after upgrade.
* The set of target tuples is specified via a callback routine that tells
* whether any given heap tuple (identified by ItemPointer) is being deleted.
- *- * Result: a palloc'd struct containing statistical info for VACUUM displays.
*/
static void
gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
@@ -122,6 +126,9 @@ gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
else
vstate.startNSN = gistGetFakeLSN(rel);
vstate.totFreePages = 0;
+ vstate.emptyPages = 0;+ vstate.internalPagesMap = NULL;+ vstate.emptyLeafPagesMap = NULL;
/*
* Need lock unless it's local to this backend.
@@ -166,6 +173,12 @@ gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
/* Quit if we've scanned the whole relation */
if (blkno >= num_pages)
break;
++ if (!vstate.internalPagesMap)+ vstate.internalPagesMap = bms_make_empty(num_pages);+ if (!vstate.emptyLeafPagesMap)+ vstate.emptyLeafPagesMap = bms_make_empty(num_pages);+
/* Iterate over pages, then loop back to recheck length */
for (; blkno < num_pages; blkno++)
gistvacuumpage(&vstate, blkno, blkno);
@@ -189,6 +202,126 @@ gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
/* update statistics */
stats->num_pages = num_pages;
stats->pages_free = vstate.totFreePages;
++ /* rescan inner pages that had empty child pages */+ if (vstate.emptyPages > 0)+ {+ int x;++ x = -1;+ while (vstate.emptyPages > 0 &&+ (x = bms_next_member(vstate.internalPagesMap, x)) >= 0)+ {+ Buffer buffer;+ Page page;+ OffsetNumber off,+ maxoff;+ IndexTuple idxtuple;+ ItemId iid;+ OffsetNumber todelete[MaxOffsetNumber];+ Buffer buftodelete[MaxOffsetNumber];+ int ntodelete = 0;++ /* FIXME: 'x' is signed, so this will not work with indexes larger than 2^31 blocks */+ blkno = (BlockNumber) x;++ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,+ info->strategy);++ LockBuffer(buffer, GIST_EXCLUSIVE);+ page = (Page) BufferGetPage(buffer);+ if (PageIsNew(page) || GistPageIsDeleted(page) || GistPageIsLeaf(page))+ {+ UnlockReleaseBuffer(buffer);+ continue;+ }++ maxoff = PageGetMaxOffsetNumber(page);+ /* Check that leafs are still empty and decide what to delete */+ for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))+ {+ Buffer leafBuffer;+ Page leafPage;+ BlockNumber leafBlockNo;++ iid = PageGetItemId(page, off);+ idxtuple = (IndexTuple) PageGetItem(page, iid);+ /* if this page was not empty in previous scan - we do not consider it */+ leafBlockNo = ItemPointerGetBlockNumber(&(idxtuple->t_tid));+ if (!bms_is_member(leafBlockNo, vstate.emptyLeafPagesMap))+ continue;++ leafBuffer = ReadBufferExtended(rel, MAIN_FORKNUM, leafBlockNo,+ RBM_NORMAL, info->strategy);+ LockBuffer(leafBuffer, GIST_EXCLUSIVE);+ gistcheckpage(rel, leafBuffer);+ leafPage = (Page) BufferGetPage(leafBuffer);+ if (!GistPageIsLeaf(leafPage))+ {+ UnlockReleaseBuffer(leafBuffer);+ continue;+ }++ if (PageGetMaxOffsetNumber(leafPage) == InvalidOffsetNumber /* Nothing left to split */+ && !(GistFollowRight(leafPage) || GistPageGetNSN(page) < GistPageGetNSN(leafPage)) /* No follow-right */+ && ntodelete < maxoff-1) /* We must keep at least one leaf page per each */+ {+ buftodelete[ntodelete] = leafBuffer;+ todelete[ntodelete++] = off;+ }+ else+ UnlockReleaseBuffer(leafBuffer);+ }++ if (ntodelete)+ {+ /*+ * Like in _bt_unlink_halfdead_page we need a upper bound on xid+ * that could hold downlinks to this page. We use+ * ReadNewTransactionId() to instead of GetCurrentTransactionId+ * since we are in a VACUUM.+ */+ TransactionId txid = ReadNewTransactionId();+ int i;++ START_CRIT_SECTION();++ /* Mark pages as deleted dropping references from internal pages */+ for (i = 0; i < ntodelete; i++)+ {+ Page leafPage = (Page) BufferGetPage(buftodelete[i]);+ XLogRecPtr recptr;++ GistPageSetDeleteXid(leafPage,txid);++ GistPageSetDeleted(leafPage);+ MarkBufferDirty(buftodelete[i]);+ stats->pages_deleted++;+ vstate.emptyPages--;++ MarkBufferDirty(buffer);+ /* Offsets are changed as long as we delete tuples from internal page */+ PageIndexTupleDelete(page, todelete[i] - i);++ if (RelationNeedsWAL(rel))+ recptr = gistXLogSetDeleted(rel->rd_node, buftodelete[i],+ txid, buffer, todelete[i] - i);+ else+ recptr = gistGetFakeLSN(rel);+ PageSetLSN(page, recptr);+ PageSetLSN(leafPage, recptr);++ UnlockReleaseBuffer(buftodelete[i]);+ }+ END_CRIT_SECTION();+ }++ UnlockReleaseBuffer(buffer);+ }+ }++ bms_free(vstate.emptyLeafPagesMap);+ bms_free(vstate.internalPagesMap);
}
/*
@@ -242,6 +375,7 @@ restart:
{
OffsetNumber todelete[MaxOffsetNumber];
int ntodelete = 0;
+ int nremain;
GISTPageOpaque opaque = GistPageGetOpaque(page);
OffsetNumber maxoff = PageGetMaxOffsetNumber(page);
@@ -309,8 +443,18 @@ restart:
maxoff = PageGetMaxOffsetNumber(page);
}
- stats->num_index_tuples += maxoff - FirstOffsetNumber + 1;-+ nremain = maxoff - FirstOffsetNumber + 1;+ if (nremain == 0)+ {+ vstate->emptyLeafPagesMap = bms_add_member(vstate->emptyLeafPagesMap, blkno);+ vstate->emptyPages++;+ }+ else+ stats->num_index_tuples += nremain;+ }+ else+ {+ vstate->internalPagesMap = bms_add_member(vstate->internalPagesMap, blkno);
}
UnlockReleaseBuffer(buffer);
diff --git a/src/backend/access/gist/gistxlog.c b/src/backend/access/gist/gistxlog.cindex 01e025d5fdb..bb0fa473f5e 100644--- a/src/backend/access/gist/gistxlog.c+++ b/src/backend/access/gist/gistxlog.c@@ -64,6 +64,39 @@ gistRedoClearFollowRight(XLogReaderState *record, uint8 block_id)
UnlockReleaseBuffer(buffer);
}
+static void+gistRedoPageSetDeleted(XLogReaderState *record)+{+ XLogRecPtr lsn = record->EndRecPtr;+ gistxlogPageDelete *xldata = (gistxlogPageDelete *) XLogRecGetData(record);+ Buffer buffer;+ Page page;++ if (XLogReadBufferForRedo(record, 0, &buffer) == BLK_NEEDS_REDO)+ {+ page = (Page) BufferGetPage(buffer);++ GistPageSetDeleteXid(page, xldata->deleteXid);+ GistPageSetDeleted(page);++ PageSetLSN(page, lsn);+ MarkBufferDirty(buffer);+ }+ if (BufferIsValid(buffer))+ UnlockReleaseBuffer(buffer);++ if (XLogReadBufferForRedo(record, 1, &buffer) == BLK_NEEDS_REDO)+ {+ page = (Page) BufferGetPage(buffer);++ PageIndexTupleDelete(page, xldata->downlinkOffset);++ PageSetLSN(page, lsn);+ MarkBufferDirty(buffer);+ }+ if (BufferIsValid(buffer))+ UnlockReleaseBuffer(buffer);+}
/*
* redo any page update (except page split)
*/
@@ -116,6 +149,7 @@ gistRedoPageUpdateRecord(XLogReaderState *record)
data += sizeof(OffsetNumber) * xldata->ntodelete;
PageIndexMultiDelete(page, todelete, xldata->ntodelete);
+
if (GistPageIsLeaf(page))
GistMarkTuplesDeleted(page);
}
@@ -535,6 +569,9 @@ gist_redo(XLogReaderState *record)
case XLOG_GIST_CREATE_INDEX:
gistRedoCreateIndex(record);
break;
+ case XLOG_GIST_PAGE_DELETE:+ gistRedoPageSetDeleted(record);+ break;
default:
elog(PANIC, "gist_redo: unknown op code %u", info);
}
@@ -653,6 +690,29 @@ gistXLogSplit(bool page_is_leaf,
return recptr;
}
+/*+ * Write XLOG record describing a page delete. This also includes removal of+ * downlink from internal page.+ */+XLogRecPtr+gistXLogSetDeleted(RelFileNode node, Buffer buffer, TransactionId xid,+ Buffer internalPageBuffer, OffsetNumber internalPageOffset) {+ gistxlogPageDelete xlrec;+ XLogRecPtr recptr;++ xlrec.deleteXid = xid;+ xlrec.downlinkOffset = internalPageOffset;++ XLogBeginInsert();+ XLogRegisterData((char *) &xlrec, sizeof(gistxlogPageDelete));++ XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);+ XLogRegisterBuffer(1, internalPageBuffer, REGBUF_STANDARD);+ /* new tuples */+ recptr = XLogInsert(RM_GIST_ID, XLOG_GIST_PAGE_DELETE);+ return recptr;+}+
/*
* Write XLOG record describing a page update. The update can include any
* number of deletions and/or insertions of tuples on a single index page.
diff --git a/src/backend/access/rmgrdesc/gistdesc.c b/src/backend/access/rmgrdesc/gistdesc.cindex b79ed1dfdc8..f65335ba23a 100644--- a/src/backend/access/rmgrdesc/gistdesc.c+++ b/src/backend/access/rmgrdesc/gistdesc.c@@ -76,6 +76,9 @@ gist_identify(uint8 info)
case XLOG_GIST_CREATE_INDEX:
id = "CREATE_INDEX";
break;
+ case XLOG_GIST_PAGE_DELETE:+ id = "PAGE_DELETE";+ break;
}
return id;
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.cindex 8ce253c88df..29cfcd78984 100644--- a/src/backend/nodes/bitmapset.c+++ b/src/backend/nodes/bitmapset.c@@ -258,6 +258,22 @@ bms_make_singleton(int x)
return result;
}
+/*+ * bms_make_singleton - preallocate an empty bitmapset+ */+Bitmapset *+bms_make_empty(int size)+{+ Bitmapset *result;+ int wordnum;++ if (size < 0)+ elog(ERROR, "negative bitmapset member not allowed");+ wordnum = WORDNUM(size - 1);+ result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));+ return result;+}+
/*
* bms_free - free a bitmapset
*
diff --git a/src/include/access/gist.h b/src/include/access/gist.hindex 827566dc6e7..0dd2bf47c8c 100644--- a/src/include/access/gist.h+++ b/src/include/access/gist.h@@ -151,6 +151,9 @@ typedef struct GISTENTRY
#define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
+#define GistPageGetDeleteXid(page) ( ((PageHeader) (page))->pd_prune_xid )+#define GistPageSetDeleteXid(page, val) ( ((PageHeader) (page))->pd_prune_xid = val)+
/*
* Vector of GISTENTRY structs; user-defined methods union and picksplit
* take it as one of their arguments
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.hindex a73716d6eaa..5d02800dac6 100644--- a/src/include/access/gist_private.h+++ b/src/include/access/gist_private.h@@ -412,12 +412,17 @@ extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
int len, GISTSTATE *giststate);
+/* gistxlog.c */+extern XLogRecPtr gistXLogSetDeleted(RelFileNode node, Buffer buffer,+ TransactionId xid, Buffer internalPageBuffer,+ OffsetNumber internalPageOffset);+
extern XLogRecPtr gistXLogUpdate(Buffer buffer,
OffsetNumber *todelete, int ntodelete,
IndexTuple *itup, int ntup,
Buffer leftchild);
-XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete,+extern XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete,
int ntodelete, RelFileNode hnode);
extern XLogRecPtr gistXLogSplit(bool page_is_leaf,
diff --git a/src/include/access/gistxlog.h b/src/include/access/gistxlog.hindex b67c7100500..3c71d0261a1 100644--- a/src/include/access/gistxlog.h+++ b/src/include/access/gistxlog.h@@ -17,13 +17,15 @@
#include "access/xlogreader.h"
#include "lib/stringinfo.h"
+/* XLog stuff */+
#define XLOG_GIST_PAGE_UPDATE 0x00
#define XLOG_GIST_DELETE 0x10 /* delete leaf index tuples for a page */
/* #define XLOG_GIST_NEW_ROOT 0x20 */ /* not used anymore */
#define XLOG_GIST_PAGE_SPLIT 0x30
/* #define XLOG_GIST_INSERT_COMPLETE 0x40 */ /* not used anymore */
#define XLOG_GIST_CREATE_INDEX 0x50
- /* #define XLOG_GIST_PAGE_DELETE 0x60 */ /* not used anymore */+#define XLOG_GIST_PAGE_DELETE 0x60
/*
* Backup Blk 0: updated page.
@@ -76,6 +78,12 @@ typedef struct gistxlogPageSplit
*/
} gistxlogPageSplit;
+typedef struct gistxlogPageDelete+{+ TransactionId deleteXid; /* last Xid which could see page in scan */+ OffsetNumber downlinkOffset; /* Offset of the downlink referencing this page */+} gistxlogPageDelete;+
extern void gist_redo(XLogReaderState *record);
extern void gist_desc(StringInfo buf, XLogReaderState *record);
extern const char *gist_identify(uint8 info);
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.hindex 433df8a46d0..55435f9ae64 100644--- a/src/include/nodes/bitmapset.h+++ b/src/include/nodes/bitmapset.h@@ -79,6 +79,7 @@ extern Bitmapset *bms_copy(const Bitmapset *a);
extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
extern int bms_compare(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_make_singleton(int x);
+extern Bitmapset *bms_make_empty(int size);
extern void bms_free(Bitmapset *a);
extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.outindex f5a2993aaf2..5b92f08c747 100644--- a/src/test/regress/expected/gist.out+++ b/src/test/regress/expected/gist.out@@ -27,9 +27,7 @@ insert into gist_point_tbl (id, p)
select g+100000, point(g*10+1, g*10+1) from generate_series(1, 10000) g;
-- To test vacuum, delete some entries from all over the index.
delete from gist_point_tbl where id % 2 = 1;
--- And also delete some concentration of values. (GiST doesn't currently--- attempt to delete pages even when they become empty, but if it did, this--- would exercise it)+-- And also delete some concentration of values.
delete from gist_point_tbl where id < 10000;
vacuum analyze gist_point_tbl;
-- rebuild the index with a different fillfactor
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sqlindex bae722fe13c..e66396e851b 100644--- a/src/test/regress/sql/gist.sql+++ b/src/test/regress/sql/gist.sql@@ -28,9 +28,7 @@ select g+100000, point(g*10+1, g*10+1) from generate_series(1, 10000) g;
-- To test vacuum, delete some entries from all over the index.
delete from gist_point_tbl where id % 2 = 1;
--- And also delete some concentration of values. (GiST doesn't currently--- attempt to delete pages even when they become empty, but if it did, this--- would exercise it)+-- And also delete some concentration of values.
delete from gist_point_tbl where id < 10000;
vacuum analyze gist_point_tbl;
--
2.19.2
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: hlinnaka@iki.fi, x4mmm@yandex-team.ru, michael@paquier.xyz, thomas.munro@enterprisedb.com, robertmhaas@gmail.com, chapaev28@ya.ru
Subject: Re: GiST VACUUM
In-Reply-To: <9f11fd6c-aa0f-42e9-4ae2-b5cc8c148658@iki.fi>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox