Quelle  gistvacuum.c

/*-------------------------------------------------------------------------
 *
 * gistvacuum.c
 *   vacuuming routines for the postgres GiST index access method.
 *
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *   src/backend/access/gist/gistvacuum.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/genam.h"
#include "access/gist_private.h"
#include "access/transam.h"
#include "commands/vacuum.h"
#include "lib/integerset.h"
#include "miscadmin.h"
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
#include "storage/read_stream.h"
#include "utils/memutils.h"

/* Working state needed by gistbulkdelete */
typedef struct
{
 IndexVacuumInfo *info;
 IndexBulkDeleteResult *stats;
 IndexBulkDeleteCallback callback;
 void    *callback_state;
 GistNSN  startNSN;

 /*
  * These are used to memorize all internal and empty leaf pages.  They are
  * used for deleting all the empty pages.
 */
 IntegerSet *internal_page_set;
 IntegerSet *empty_leaf_set;
 MemoryContext page_set_context;
} GistVacState;

static void gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
         IndexBulkDeleteCallback callback, void *callback_state);
static void gistvacuumpage(GistVacState *vstate, Buffer buffer);
static void gistvacuum_delete_empty_pages(IndexVacuumInfo *info,
            GistVacState *vstate);
static bool gistdeletepage(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
         Buffer parentBuffer, OffsetNumber downlink,
         Buffer leafBuffer);

/*
 * VACUUM bulkdelete stage: remove index entries.
 */
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 stage: delete empty pages, and update index statistics.
 */
IndexBulkDeleteResult *
gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
{
 /* No-op in ANALYZE ONLY mode */
 if (info->analyze_only)
  return stats;

 /*
  * 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);
 }

 /*
  * 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.
 */
 if (!info->estimated_count)
 {
  if (stats->num_index_tuples > info->num_heap_tuples)
   stats->num_index_tuples = info->num_heap_tuples;
 }

 return stats;
}

/*
 * gistvacuumscan --- scan the index for VACUUMing purposes
 *
 * This scans the index for leaf tuples that are deletable according to the
 * vacuum callback, and updates the stats.  Both btbulkdelete and
 * btvacuumcleanup invoke this (the latter only if no btbulkdelete call
 * occurred).
 *
 * This also makes note of any empty leaf pages, as well as all internal
 * pages while looping over all index pages.  After scanning all the pages, we
 * remove the empty pages so that they can be reused.  Any deleted pages are
 * added directly to the free space map.  (They should've been added there
 * when they were originally deleted, already, but it's possible that the FSM
 * was lost at a crash, for example.)
 *
 * The caller is responsible for initially allocating/zeroing a stats struct.
 */
static void
gistvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
      IndexBulkDeleteCallback callback, void *callback_state)
{
 Relation rel = info->index;
 GistVacState vstate;
 BlockNumber num_pages;
 bool  needLock;
 MemoryContext oldctx;
 BlockRangeReadStreamPrivate p;
 ReadStream *stream = NULL;

 /*
  * Reset fields that track information about the entire index now.  This
  * avoids double-counting in the case where a single VACUUM command
  * requires multiple scans of the index.
  *
  * Avoid resetting the tuples_removed and pages_newly_deleted fields here,
  * since they track information about the VACUUM command, and so must last
  * across each call to gistvacuumscan().
  *
  * (Note that pages_free is treated as state about the whole index, not
  * the current VACUUM.  This is appropriate because RecordFreeIndexPage()
  * calls are idempotent, and get repeated for the same deleted pages in
  * some scenarios.  The point for us is to track the number of recyclable
  * pages in the index at the end of the VACUUM command.)
 */
 stats->num_pages = 0;
 stats->estimated_count = false;
 stats->num_index_tuples = 0;
 stats->pages_deleted = 0;
 stats->pages_free = 0;

 /*
  * Create the integer sets to remember all the internal and the empty leaf
  * pages in page_set_context.  Internally, the integer set will remember
  * this context so that the subsequent allocations for these integer sets
  * will be done from the same context.
  *
  * XXX the allocation sizes used below pre-date generation context's block
  * growing code.  These values should likely be benchmarked and set to
  * more suitable values.
 */
 vstate.page_set_context = GenerationContextCreate(CurrentMemoryContext,
               "GiST VACUUM page set context",
               16 * 1024,
               16 * 1024,
               16 * 1024);
 oldctx = MemoryContextSwitchTo(vstate.page_set_context);
 vstate.internal_page_set = intset_create();
 vstate.empty_leaf_set = intset_create();
 MemoryContextSwitchTo(oldctx);

 /* 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);

 /*
  * 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);

 p.current_blocknum = GIST_ROOT_BLKNO;

 /*
  * It is safe to use batchmode as block_range_read_stream_cb takes no
  * locks.
 */
 stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE |
          READ_STREAM_FULL |
          READ_STREAM_USE_BATCHING,
          info->strategy,
          rel,
          MAIN_FORKNUM,
          block_range_read_stream_cb,
          &p,
          0);
 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 (p.current_blocknum >= num_pages)
   break;

  p.last_exclusive = num_pages;

  /* Iterate over pages, then loop back to recheck relation length */
  while (true)
  {
   Buffer  buf;

   /* call vacuum_delay_point while not holding any buffer lock */
   vacuum_delay_point(false);

   buf = read_stream_next_buffer(stream, NULL);

   if (!BufferIsValid(buf))
    break;

   gistvacuumpage(&vstate, buf);
  }

  /*
   * We have to reset the read stream to use it again. After returning
   * InvalidBuffer, the read stream API won't invoke our callback again
   * until the stream has been reset.
 */
  read_stream_reset(stream);
 }

 read_stream_end(stream);

 /*
  * 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 (stats->pages_free > 0)
  IndexFreeSpaceMapVacuum(rel);

 /* update statistics */
 stats->num_pages = num_pages;

 /*
  * If we saw any empty pages, try to unlink them from the tree so that
  * they can be reused.
 */
 gistvacuum_delete_empty_pages(info, &vstate);

 /* we don't need the internal and empty page sets anymore */
 MemoryContextDelete(vstate.page_set_context);
 vstate.page_set_context = NULL;
 vstate.internal_page_set = NULL;
 vstate.empty_leaf_set = NULL;
}

/*
 * gistvacuumpage --- VACUUM one page
 *
 * This processes a single page for gistbulkdelete(). `buffer` contains the
 * page to process. In some cases we must go back and reexamine
 * previously-scanned pages; this routine recurses when necessary to handle
 * that case.
 */
static void
gistvacuumpage(GistVacState *vstate, Buffer buffer)
{
 IndexVacuumInfo *info = vstate->info;
 IndexBulkDeleteCallback callback = vstate->callback;
 void    *callback_state = vstate->callback_state;
 Relation rel = info->index;
 BlockNumber orig_blkno = BufferGetBlockNumber(buffer);
 Page  page;
 BlockNumber recurse_to;

 /*
  * orig_blkno is the highest block number reached by the outer
  * gistvacuumscan() loop. This will be the same as blkno unless we are
  * recursing to reexamine a previous page.
 */
 BlockNumber blkno = orig_blkno;

restart:
 recurse_to = InvalidBlockNumber;

 /*
  * We are not going to stay here for a long time, aggressively grab an
  * exclusive lock.
 */
 LockBuffer(buffer, GIST_EXCLUSIVE);
 page = (Page) BufferGetPage(buffer);

 if (gistPageRecyclable(page))
 {
  /* Okay to recycle this page */
  RecordFreeIndexPage(rel, blkno);
  vstate->stats->pages_deleted++;
  vstate->stats->pages_free++;
 }
 else if (GistPageIsDeleted(page))
 {
  /* Already deleted, but can't recycle yet */
  vstate->stats->pages_deleted++;
 }
 else if (GistPageIsLeaf(page))
 {
  OffsetNumber todelete[MaxOffsetNumber];
  int   ntodelete = 0;
  int   nremain;
  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.
   *
   * This is similar to the checks we do during searches, when following
   * a downlink, but we don't need to jump to higher-numbered pages,
   * because we will process them later, anyway.
 */
  if ((GistFollowRight(page) ||
    vstate->startNSN < GistPageGetNSN(page)) &&
   (opaque->rightlink != InvalidBlockNumber) &&
   (opaque->rightlink < orig_blkno))
  {
   recurse_to = opaque->rightlink;
  }

  /*
   * Scan over all items to see which ones need to be deleted according
   * to the callback function.
 */
  if (callback)
  {
   OffsetNumber off;

   for (off = FirstOffsetNumber;
     off <= maxoff;
     off = OffsetNumberNext(off))
   {
    ItemId  iid = PageGetItemId(page, off);
    IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);

    if (callback(&(idxtuple->t_tid), callback_state))
     todelete[ntodelete++] = off;
   }
  }

  /*
   * Apply any needed deletes.  We issue just one WAL record per page,
   * so as to minimize WAL traffic.
 */
  if (ntodelete > 0)
  {
   START_CRIT_SECTION();

   MarkBufferDirty(buffer);

   PageIndexMultiDelete(page, todelete, ntodelete);
   GistMarkTuplesDeleted(page);

   if (RelationNeedsWAL(rel))
   {
    XLogRecPtr recptr;

    recptr = gistXLogUpdate(buffer,
          todelete, ntodelete,
          NULL, 0, InvalidBuffer);
    PageSetLSN(page, recptr);
   }
   else
    PageSetLSN(page, gistGetFakeLSN(rel));

   END_CRIT_SECTION();

   vstate->stats->tuples_removed += ntodelete;
   /* must recompute maxoff */
   maxoff = PageGetMaxOffsetNumber(page);
  }

  nremain = maxoff - FirstOffsetNumber + 1;
  if (nremain == 0)
  {
   /*
    * The page is now completely empty.  Remember its block number,
    * so that we will try to delete the page in the second stage.
    *
    * Skip this when recursing, because IntegerSet requires that the
    * values are added in ascending order.  The next VACUUM will pick
    * it up.
 */
   if (blkno == orig_blkno)
    intset_add_member(vstate->empty_leaf_set, blkno);
  }
  else
   vstate->stats->num_index_tuples += nremain;
 }
 else
 {
  /*
   * On an internal page, check for "invalid tuples", left behind by an
   * incomplete page split on PostgreSQL 9.0 or below.  These are not
   * created by newer PostgreSQL versions, but unfortunately, there is
   * no version number anywhere in a GiST index, so we don't know
   * whether this index might still contain invalid tuples or not.
 */
  OffsetNumber maxoff = PageGetMaxOffsetNumber(page);
  OffsetNumber off;

  for (off = FirstOffsetNumber;
    off <= maxoff;
    off = OffsetNumberNext(off))
  {
   ItemId  iid = PageGetItemId(page, off);
   IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);

   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.")));
  }

  /*
   * Remember the block number of this page, so that we can revisit it
   * later in gistvacuum_delete_empty_pages(), when we search for
   * parents of empty leaf pages.
 */
  if (blkno == orig_blkno)
   intset_add_member(vstate->internal_page_set, blkno);
 }

 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;

  /* check for vacuum delay while not holding any buffer lock */
  vacuum_delay_point(false);

  buffer = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,
         info->strategy);
  goto restart;
 }
}

/*
 * Scan all internal pages, and try to delete their empty child pages.
 */
static void
gistvacuum_delete_empty_pages(IndexVacuumInfo *info, GistVacState *vstate)
{
 Relation rel = info->index;
 BlockNumber empty_pages_remaining;
 uint64  blkno;

 /*
  * Rescan all inner pages to find those that have empty child pages.
 */
 empty_pages_remaining = intset_num_entries(vstate->empty_leaf_set);
 intset_begin_iterate(vstate->internal_page_set);
 while (empty_pages_remaining > 0 &&
     intset_iterate_next(vstate->internal_page_set, &blkno))
 {
  Buffer  buffer;
  Page  page;
  OffsetNumber off,
     maxoff;
  OffsetNumber todelete[MaxOffsetNumber];
  BlockNumber leafs_to_delete[MaxOffsetNumber];
  int   ntodelete;
  int   deleted;

  buffer = ReadBufferExtended(rel, MAIN_FORKNUM, (BlockNumber) blkno,
         RBM_NORMAL, info->strategy);

  LockBuffer(buffer, GIST_SHARE);
  page = (Page) BufferGetPage(buffer);

  if (PageIsNew(page) || GistPageIsDeleted(page) || GistPageIsLeaf(page))
  {
   /*
    * This page was an internal page earlier, but now it's something
    * else. Shouldn't happen...
 */
   Assert(false);
   UnlockReleaseBuffer(buffer);
   continue;
  }

  /*
   * Scan all the downlinks, and see if any of them point to empty leaf
   * pages.
 */
  maxoff = PageGetMaxOffsetNumber(page);
  ntodelete = 0;
  for (off = FirstOffsetNumber;
    off <= maxoff && ntodelete < maxoff - 1;
    off = OffsetNumberNext(off))
  {
   ItemId  iid = PageGetItemId(page, off);
   IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
   BlockNumber leafblk;

   leafblk = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
   if (intset_is_member(vstate->empty_leaf_set, leafblk))
   {
    leafs_to_delete[ntodelete] = leafblk;
    todelete[ntodelete++] = off;
   }
  }

  /*
   * In order to avoid deadlock, child page must be locked before
   * parent, so we must release the lock on the parent, lock the child,
   * and then re-acquire the lock the parent.  (And we wouldn't want to
   * do I/O, while holding a lock, anyway.)
   *
   * At the instant that we're not holding a lock on the parent, the
   * downlink might get moved by a concurrent insert, so we must
   * re-check that it still points to the same child page after we have
   * acquired both locks.  Also, another backend might have inserted a
   * tuple to the page, so that it is no longer empty.  gistdeletepage()
   * re-checks all these conditions.
 */
  LockBuffer(buffer, GIST_UNLOCK);

  deleted = 0;
  for (int i = 0; i < ntodelete; i++)
  {
   Buffer  leafbuf;

   /*
    * Don't remove the last downlink from the parent.  That would
    * confuse the insertion code.
 */
   if (PageGetMaxOffsetNumber(page) == FirstOffsetNumber)
    break;

   leafbuf = ReadBufferExtended(rel, MAIN_FORKNUM, leafs_to_delete[i],
           RBM_NORMAL, info->strategy);
   LockBuffer(leafbuf, GIST_EXCLUSIVE);
   gistcheckpage(rel, leafbuf);

   LockBuffer(buffer, GIST_EXCLUSIVE);
   if (gistdeletepage(info, vstate->stats,
          buffer, todelete[i] - deleted,
          leafbuf))
    deleted++;
   LockBuffer(buffer, GIST_UNLOCK);

   UnlockReleaseBuffer(leafbuf);
  }

  ReleaseBuffer(buffer);

  /*
   * We can stop the scan as soon as we have seen the downlinks, even if
   * we were not able to remove them all.
 */
  empty_pages_remaining -= ntodelete;
 }
}

/*
 * gistdeletepage takes a leaf page, and its parent, and tries to delete the
 * leaf.  Both pages must be locked.
 *
 * Even if the page was empty when we first saw it, a concurrent inserter might
 * have added a tuple to it since.  Similarly, the downlink might have moved.
 * We re-check all the conditions, to make sure the page is still deletable,
 * before modifying anything.
 *
 * Returns true, if the page was deleted, and false if a concurrent update
 * prevented it.
 */
static bool
gistdeletepage(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
      Buffer parentBuffer, OffsetNumber downlink,
      Buffer leafBuffer)
{
 Page  parentPage = BufferGetPage(parentBuffer);
 Page  leafPage = BufferGetPage(leafBuffer);
 ItemId  iid;
 IndexTuple idxtuple;
 XLogRecPtr recptr;
 FullTransactionId txid;

 /*
  * Check that the leaf is still empty and deletable.
 */
 if (!GistPageIsLeaf(leafPage))
 {
  /* a leaf page should never become a non-leaf page */
  Assert(false);
  return false;
 }

 if (GistFollowRight(leafPage))
  return false;   /* don't mess with a concurrent page split */

 if (PageGetMaxOffsetNumber(leafPage) != InvalidOffsetNumber)
  return false;   /* not empty anymore */

 /*
  * Ok, the leaf is deletable.  Is the downlink in the parent page still
  * valid?  It might have been moved by a concurrent insert.  We could try
  * to re-find it by scanning the page again, possibly moving right if the
  * was split.  But for now, let's keep it simple and just give up.  The
  * next VACUUM will pick it up.
 */
 if (PageIsNew(parentPage) || GistPageIsDeleted(parentPage) ||
  GistPageIsLeaf(parentPage))
 {
  /* shouldn't happen, internal pages are never deleted */
  Assert(false);
  return false;
 }

 if (PageGetMaxOffsetNumber(parentPage) < downlink
  || PageGetMaxOffsetNumber(parentPage) <= FirstOffsetNumber)
  return false;

 iid = PageGetItemId(parentPage, downlink);
 idxtuple = (IndexTuple) PageGetItem(parentPage, iid);
 if (BufferGetBlockNumber(leafBuffer) !=
  ItemPointerGetBlockNumber(&(idxtuple->t_tid)))
  return false;

 /*
  * All good, proceed with the deletion.
  *
  * The page cannot be immediately recycled, because in-progress scans that
  * saw the downlink might still visit it.  Mark the page with the current
  * next-XID counter, so that we know when it can be recycled.  Once that
  * XID becomes older than GlobalXmin, we know that all scans that are
  * currently in progress must have ended.  (That's much more conservative
  * than needed, but let's keep it safe and simple.)
 */
 txid = ReadNextFullTransactionId();

 START_CRIT_SECTION();

 /* mark the page as deleted */
 MarkBufferDirty(leafBuffer);
 GistPageSetDeleted(leafPage, txid);
 stats->pages_newly_deleted++;
 stats->pages_deleted++;

 /* remove the downlink from the parent */
 MarkBufferDirty(parentBuffer);
 PageIndexTupleDelete(parentPage, downlink);

 if (RelationNeedsWAL(info->index))
  recptr = gistXLogPageDelete(leafBuffer, txid, parentBuffer, downlink);
 else
  recptr = gistGetFakeLSN(info->index);
 PageSetLSN(parentPage, recptr);
 PageSetLSN(leafPage, recptr);

 END_CRIT_SECTION();

 return true;
}