Quelle nbtpage.c
Sprache: C
/*------------------------------------------------------------------------- * * nbtpage . c * BTree - specific page management code for the Postgres btree 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 / nbtree / nbtpage . c * * NOTES * Postgres btree pages look like ordinary relation pages . The opaque * data at high addresses includes pointers to left and right siblings * and flag data describing page state . The first page in a btree , page * zero , is special - - it stores meta - information describing the tree . * Pages one and higher store the actual tree data . * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #include "postgres.h" #include "access/nbtree.h" #include "access/nbtxlog.h" #include "access/tableam.h" #include "access/transam.h" #include "access/xlog.h" #include "access/xloginsert.h" #include "common/int.h" #include "miscadmin.h" #include "storage/indexfsm.h" #include "storage/predicate.h" #include "storage/procarray.h" #include "utils/memdebug.h" #include "utils/memutils.h" #include "utils/snapmgr.h" static BTMetaPageData *_bt_getmeta(Relation rel, Buffer metabuf);static void _bt_delitems_delete(Relation rel, Buffer buf,bool isCatalogRel,int ndeletable,int nupdatable);static char *_bt_delitems_update(BTVacuumPosting *updatable, int nupdatable,bool needswal);static bool _bt_mark_page_halfdead(Relation rel, Relation heaprel,static bool _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf,bool *rightsib_empty,static bool _bt_lock_subtree_parent(Relation rel, Relation heaprel,static void _bt_pendingfsm_add(BTVacState *vstate, BlockNumber target,/* * _ bt_initmetapage ( ) - - Fill a page buffer with a correct metapage image void bool allequalimage)0 ;1 .0 ;/* * Set pd_lower just past the end of the metadata . This is essential , * because without doing so , metadata will be lost if xlog . c compresses * the page . char *) metad + sizeof (BTMetaPageData)) - (char *) page;/* * _ bt_upgrademetapage ( ) - - Upgrade a meta - page from an old format to version * 3 , the last version that can be updated without broadly affecting * on - disk compatibility . ( A REINDEX is required to upgrade to v4 . ) * * This routine does purely in - memory image upgrade . Caller is * responsible for locking , WAL - logging etc . void /* It must be really a meta page of upgradable version */ /* Set version number and fill extra fields added into version 3 */ 0 ;1 .0 ;/* Only a REINDEX can set this field */ false ;/* Adjust pd_lower (see _bt_initmetapage() for details) */ char *) metad + sizeof (BTMetaPageData)) - (char *) page;/* * Get metadata from share - locked buffer containing metapage , while performing * standard sanity checks . * * Callers that cache data returned here in local cache should note that an * on - the - fly upgrade using _ bt_upgrademetapage ( ) can change the version field * and BTREE_NOVAC_VERSION specific fields without invalidating local cache . static BTMetaPageData */* sanity-check the metapage */ if (!P_ISMETA(metaopaque) ||"index \" %s\" is not a btree" ,if (metad->btm_version < BTREE_MIN_VERSION ||"version mismatch in index \" %s\": file version %d, " "current version %d, minimal supported version %d" ,return metad;/* * _ bt_vacuum_needs_cleanup ( ) - - Checks if index needs cleanup * * Called by btvacuumcleanup when btbulkdelete was never called because no * index tuples needed to be deleted . bool /* * Copy details from metapage to local variables quickly . * * Note that we deliberately avoid using cached version of metapage here . if (btm_version < BTREE_NOVAC_VERSION)/* * Metapage needs to be dynamically upgraded to store fields that are * only present when btm_version > = BTREE_NOVAC_VERSION return true ;/* * Trigger cleanup in rare cases where prev_num_delpages exceeds 5 % of the * total size of the index . We can reasonably expect ( though are not * guaranteed ) to be able to recycle this many pages if we decide to do a * btvacuumscan call during the ongoing btvacuumcleanup . For further * details see the nbtree / README section on placing deleted pages in the * FSM . if (prev_num_delpages > 0 &&20 )return true ;return false ;/* * _ bt_set_cleanup_info ( ) - - Update metapage for btvacuumcleanup . * * Called at the end of btvacuumcleanup , when num_delpages value has been * finalized . void /* * On - disk compatibility note : The btm_last_cleanup_num_delpages metapage * field started out as a TransactionId field called btm_oldest_btpo_xact . * Both " versions " are just uint32 fields . It was convenient to repurpose * the field when we began to use 64 - bit XIDs in deleted pages . * * It ' s possible that a pg_upgrade ' d database will contain an XID value in * what is now recognized as the metapage ' s btm_last_cleanup_num_delpages * field . _ bt_vacuum_needs_cleanup ( ) may even believe that this value * indicates that there are lots of pages that it needs to recycle , when * in reality there are only one or two . The worst that can happen is * that there will be a call to btvacuumscan a little earlier , which will * set btm_last_cleanup_num_delpages to a sane value when we ' re called . * * Note also that the metapage ' s btm_last_cleanup_num_heap_tuples field is * no longer used as of PostgreSQL 14 . We set it to - 1 . 0 on rewrite , just * to be consistent . /* Don't miss chance to upgrade index/metapage when BTREE_MIN_VERSION */ if (metad->btm_version >= BTREE_NOVAC_VERSION &&/* Usually means index continues to have num_delpages of 0 */ return ;/* trade in our read lock for a write lock */ /* upgrade meta-page if needed */ if (metad->btm_version < BTREE_NOVAC_VERSION)/* update cleanup-related information */ 1 .0 ;/* write wal record if needed */ if (RelationNeedsWAL(rel))0 , metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);0 , &md, sizeof (xl_btree_metadata));/* * _ bt_getroot ( ) - - Get the root page of the btree . * * Since the root page can move around the btree file , we have to read * its location from the metadata page , and then read the root page * itself . If no root page exists yet , we have to create one . * * The access type parameter ( BT_READ or BT_WRITE ) controls whether * a new root page will be created or not . If access = BT_READ , * and no root page exists , we just return InvalidBuffer . For * BT_WRITE , we try to create the root page if it doesn ' t exist . * NOTE that the returned root page will have only a read lock set * on it even if access = BT_WRITE ! * * If access = BT_WRITE , heaprel must be set ; otherwise caller can just * pass NULL . See _ bt_allocbuf for an explanation . * * The returned page is not necessarily the true root - - - it could be * a " fast root " ( a page that is alone in its level due to deletions ) . * Also , if the root page is split while we are " in flight " to it , * what we will return is the old root , which is now just the leftmost * page on a probably - not - very - wide level . For most purposes this is * as good as or better than the true root , so we do not bother to * insist on finding the true root . We do , however , guarantee to * return a live ( not deleted or half - dead ) page . * * On successful return , the root page is pinned and read - locked . * The metadata page is not locked or pinned on exit . int access)/* * Try to use previously - cached metapage data to find the root . This * normally saves one buffer access per index search , which is a very * helpful savings in bufmgr traffic and hence contention . if (rel->rd_amcache != NULL)/* We shouldn't have cached it if any of these fail */ /* * Since the cache might be stale , we check the page more carefully * here than normal . We * must * check that it ' s not deleted . If it ' s * not alone on its level , then we reject too - - - this may be overly * paranoid but better safe than sorry . Note we don ' t check P_ISROOT , * because that ' s not set in a " fast root " . if (!P_IGNORE(rootopaque) &&/* OK, accept cached page as the root */ return rootbuf;/* Cache is stale, throw it away */ if (rel->rd_amcache)/* if no root page initialized yet, do it */ if (metad->btm_root == P_NONE)/* If access = BT_READ, caller doesn't want us to create root yet */ if (access == BT_READ)return InvalidBuffer;/* trade in our read lock for a write lock */ /* * Race condition : if someone else initialized the metadata between * the time we released the read lock and acquired the write lock , we * must avoid doing it again . if (metad->btm_root != P_NONE)/* * Metadata initialized by someone else . In order to guarantee no * deadlocks , we have to release the metadata page and start all * over again . ( Is that really true ? But it ' s hardly worth trying * to optimize this case . ) return _bt_getroot(rel, heaprel, access);/* * Get , initialize , write , and leave a lock of the appropriate type on * the new root page . Since this is the first page in the tree , it ' s * a leaf as well as the root . 0 ;0 ;/* Get raw page pointer for metapage */ /* NO ELOG(ERROR) till meta is updated */ /* upgrade metapage if needed */ if (metad->btm_version < BTREE_NOVAC_VERSION)0 ;0 ;0 ;1 .0 ;/* XLOG stuff */ if (RelationNeedsWAL(rel))0 , rootbuf, REGBUF_WILL_INIT);2 , metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);0 ;0 ;0 ;2 , &md, sizeof (xl_btree_metadata));0 ;/* * swap root write lock for read lock . There is no danger of anyone * else accessing the new root page while it ' s unlocked , since no one * else knows where it is yet . /* okay, metadata is correct, release lock on it without caching */ else /* * Cache the metapage data for next time sizeof (BTMetaPageData));sizeof (BTMetaPageData));/* * We are done with the metapage ; arrange to release it via first * _ bt_relandgetbuf call for (;;)if (!P_IGNORE(rootopaque))break ;/* it's dead, Jim. step right one page */ if (P_RIGHTMOST(rootopaque))"no live root page found in index \" %s\"" ,if (rootopaque->btpo_level != rootlevel)"root page %u of index \" %s\" has level %u, expected %u" ,/* * By here , we have a pin and read lock on the root page , and no lock set * on the metadata page . Return the root page ' s buffer . return rootbuf;/* * _ bt_gettrueroot ( ) - - Get the true root page of the btree . * * This is the same as the BT_READ case of _ bt_getroot ( ) , except * we follow the true - root link not the fast - root link . * * By the time we acquire lock on the root page , it might have been split and * not be the true root anymore . This is okay for the present uses of this * routine ; we only really need to be able to move up at least one tree level * from whatever non - root page we were at . If we ever do need to lock the * one true root page , we could loop here , re - reading the metapage on each * failure . ( Note that it wouldn ' t do to hold the lock on the metapage while * moving to the root - - - that ' d deadlock against any concurrent root split . ) /* * We don ' t try to use cached metapage data here , since ( a ) this path is * not performance - critical , and ( b ) if we are here it suggests our cache * is out - of - date anyway . In light of point ( b ) , it ' s probably safest to * actively flush any cached metapage info . if (rel->rd_amcache)if (!P_ISMETA(metaopaque) ||"index \" %s\" is not a btree" ,if (metad->btm_version < BTREE_MIN_VERSION ||"version mismatch in index \" %s\": file version %d, " "current version %d, minimal supported version %d" ,/* if no root page initialized yet, fail */ if (metad->btm_root == P_NONE)return InvalidBuffer;/* * We are done with the metapage ; arrange to release it via first * _ bt_relandgetbuf call for (;;)if (!P_IGNORE(rootopaque))break ;/* it's dead, Jim. step right one page */ if (P_RIGHTMOST(rootopaque))"no live root page found in index \" %s\"" ,if (rootopaque->btpo_level != rootlevel)"root page %u of index \" %s\" has level %u, expected %u" ,return rootbuf;/* * _ bt_getrootheight ( ) - - Get the height of the btree search tree . * * We return the level ( counting from zero ) of the current fast root . * This represents the number of tree levels we ' d have to descend through * to start any btree index search . * * This is used by the planner for cost - estimation purposes . Since it ' s * only an estimate , slightly - stale data is fine , hence we don ' t worry * about updating previously cached data . int if (rel->rd_amcache == NULL)/* * If there ' s no root page yet , _ bt_getroot ( ) doesn ' t expect a cache * to be made , so just stop here and report the index height is zero . * ( XXX perhaps _ bt_getroot ( ) should be changed to allow this case . ) if (metad->btm_root == P_NONE)return 0 ;/* * Cache the metapage data for next time sizeof (BTMetaPageData));sizeof (BTMetaPageData));/* Get cached page */ /* We shouldn't have cached it if any of these fail */ return metad->btm_fastlevel;/* * _ bt_metaversion ( ) - - Get version / status info from metapage . * * Sets caller ' s * heapkeyspace and * allequalimage arguments using data * from the B - Tree metapage ( could be locally - cached version ) . This * information needs to be stashed in insertion scankey , so we provide a * single function that fetches both at once . * * This is used to determine the rules that must be used to descend a * btree . Version 4 indexes treat heap TID as a tiebreaker attribute . * pg_upgrade ' d version 3 indexes need extra steps to preserve reasonable * performance when inserting a new BTScanInsert - wise duplicate tuple * among many leaf pages already full of such duplicates . * * Also sets allequalimage field , which indicates whether or not it is * safe to apply deduplication . We rely on the assumption that * btm_allequalimage will be zero ' ed on heapkeyspace indexes that were * pg_upgrade ' d from Postgres 12 . void bool *heapkeyspace, bool *allequalimage)if (rel->rd_amcache == NULL)/* * If there ' s no root page yet , _ bt_getroot ( ) doesn ' t expect a cache * to be made , so just stop here . ( XXX perhaps _ bt_getroot ( ) should * be changed to allow this case . ) if (metad->btm_root == P_NONE)return ;/* * Cache the metapage data for next time * * An on - the - fly version upgrade performed by _ bt_upgrademetapage ( ) * can change the nbtree version for an index without invalidating any * local cache . This is okay because it can only happen when moving * from version 2 to version 3 , both of which are ! heapkeyspace * versions . sizeof (BTMetaPageData));sizeof (BTMetaPageData));/* Get cached page */ /* We shouldn't have cached it if any of these fail */ /* * _ bt_checkpage ( ) - - Verify that a freshly - read page looks sane . void /* * ReadBuffer verifies that every newly - read page passes * PageHeaderIsValid , which means it either contains a reasonably sane * page header or is all - zero . We have to defend against the all - zero * case , however . if (PageIsNew(page))"index \" %s\" contains unexpected zero page at block %u" ,"Please REINDEX it." )));/* * Additionally check that the special area looks sane . if (PageGetSpecialSize(page) != MAXALIGN(sizeof (BTPageOpaqueData)))"index \" %s\" contains corrupted page at block %u" ,"Please REINDEX it." )));/* * _ bt_getbuf ( ) - - Get an existing block in a buffer , for read or write . * * The general rule in nbtree is that it ' s never okay to access a * page without holding both a buffer pin and a buffer lock on * the page ' s buffer . * * When this routine returns , the appropriate lock is set on the * requested buffer and its reference count has been incremented * ( ie , the buffer is " locked and pinned " ) . Also , we apply * _ bt_checkpage to sanity - check the page , and perform Valgrind * client requests that help Valgrind detect unsafe page accesses . * * Note : raw LockBuffer ( ) calls are disallowed in nbtree ; all * buffer lock requests need to go through wrapper functions such * as _ bt_lockbuf ( ) . int access)/* Read an existing block of the relation */ return buf;/* * _ bt_allocbuf ( ) - - Allocate a new block / page . * * Returns a write - locked buffer containing an unallocated nbtree page . * * Callers are required to pass a valid heaprel . We need heaprel so that we * can handle generating a snapshotConflictHorizon that makes reusing a page * from the FSM safe for queries that may be running on standbys . /* * First see if the FSM knows of any free pages . * * We can ' t trust the FSM ' s report unreservedly ; we have to check that the * page is still free . ( For example , an already - free page could have been * re - used between the time the last VACUUM scanned it and the time the * VACUUM made its FSM updates . ) * * In fact , it ' s worse than that : we can ' t even assume that it ' s safe to * take a lock on the reported page . If somebody else has a lock on it , * or even worse our own caller does , we could deadlock . ( The own - caller * scenario is actually not improbable . Consider an index on a serial or * timestamp column . Nearly all splits will be at the rightmost page , so * it ' s entirely likely that _ bt_split will call us while holding a lock * on the page most recently acquired from FSM . A VACUUM running * concurrently with the previous split could well have placed that page * back in FSM . ) * * To get around that , we ask for only a conditional lock on the reported * page . If we fail , then someone else is using the page , and we may * reasonably assume it ' s not free . ( If we happen to be wrong , the worst * consequence is the page will be lost to use till the next VACUUM , which * is no big problem . ) for (;;)if (blkno == InvalidBlockNumber)break ;if (_bt_conditionallockbuf(rel, buf))/* * It ' s possible to find an all - zeroes page in an index . For * example , a backend might successfully extend the relation one * page and then crash before it is able to make a WAL entry for * adding the page . If we find a zeroed page then reclaim it * immediately . if (PageIsNew(page))/* Okay to use page. Initialize and return it. */ return buf;if (BTPageIsRecyclable(page, heaprel))/* * If we are generating WAL for Hot Standby then create a WAL * record that will allow us to conflict with queries running * on standby , in case they have snapshots older than safexid * value if (RelationNeedsWAL(rel) && XLogStandbyInfoActive())/* * Note that we don ' t register the buffer with the record , * because this operation doesn ' t modify the page ( that * already happened , back when VACUUM deleted the page ) . * This record only exists to provide a conflict point for * Hot Standby . See record REDO routine comments . /* Okay to use page. Re-initialize and return it. */ return buf;"FSM returned nonrecyclable page" );else "FSM returned nonlockable page" );/* couldn't get lock, so just drop pin */ /* * Extend the relation by one page . Need to use RBM_ZERO_AND_LOCK or we * risk a race condition against btvacuumscan - - - see comments therein . * This forces us to repeat the valgrind request that _ bt_lockbuf ( ) * otherwise would make , as we can ' t use _ bt_lockbuf ( ) without introducing * a race . if (!RelationUsesLocalBuffers(rel))/* Initialize the new page before returning it */ return buf;/* * _ bt_relandgetbuf ( ) - - release a locked buffer and get another one . * * This is equivalent to _ bt_relbuf followed by _ bt_getbuf . Also , if obuf is * InvalidBuffer then it reduces to just _ bt_getbuf ; allowing this case * simplifies some callers . * * The original motivation for using this was to avoid two entries to the * bufmgr when one would do . However , now it ' s mainly just a notational * convenience . The only case where it saves work over _ bt_relbuf / _ bt_getbuf * is when the target page is the same one already in the buffer . int access)if (BufferIsValid(obuf))return buf;/* * _ bt_relbuf ( ) - - release a locked buffer . * * Lock and pin ( refcount ) are both dropped . void /* * _ bt_lockbuf ( ) - - lock a pinned buffer . * * Lock is acquired without acquiring another pin . This is like a raw * LockBuffer ( ) call , but performs extra steps needed by Valgrind . * * Note : Caller may need to call _ bt_checkpage ( ) with buf when pin on buf * wasn ' t originally acquired in _ bt_getbuf ( ) or _ bt_relandgetbuf ( ) . void int access)/* LockBuffer() asserts that pin is held by this backend */ /* * It doesn ' t matter that _ bt_unlockbuf ( ) won ' t get called in the event of * an nbtree error ( e . g . a unique violation error ) . That won ' t cause * Valgrind false positives . * * The nbtree client requests are superimposed on top of the bufmgr . c * buffer pin client requests . In the event of an nbtree error the buffer * will certainly get marked as defined when the backend once again * acquires its first pin on the buffer . ( Of course , if the backend never * touches the buffer again then it doesn ' t matter that it remains * non - accessible to Valgrind . ) * * Note : When an IndexTuple C pointer gets computed using an ItemId read * from a page while a lock was held , the C pointer becomes unsafe to * dereference forever as soon as the lock is released . Valgrind can only * detect cases where the pointer gets dereferenced with no _ current_ * lock / pin held , though . if (!RelationUsesLocalBuffers(rel))/* * _ bt_unlockbuf ( ) - - unlock a pinned buffer . void /* * Buffer is pinned and locked , which means that it is expected to be * defined and addressable . Check that proactively . /* LockBuffer() asserts that pin is held by this backend */ if (!RelationUsesLocalBuffers(rel))/* * _ bt_conditionallockbuf ( ) - - conditionally BT_WRITE lock pinned * buffer . * * Note : Caller may need to call _ bt_checkpage ( ) with buf when pin on buf * wasn ' t originally acquired in _ bt_getbuf ( ) or _ bt_relandgetbuf ( ) . bool /* ConditionalLockBuffer() asserts that pin is held by this backend */ if (!ConditionalLockBuffer(buf))return false ;if (!RelationUsesLocalBuffers(rel))return true ;/* * _ bt_upgradelockbufcleanup ( ) - - upgrade lock to a full cleanup lock . void /* * Buffer is pinned and locked , which means that it is expected to be * defined and addressable . Check that proactively . /* LockBuffer() asserts that pin is held by this backend */ /* * _ bt_pageinit ( ) - - Initialize a new page . * * On return , the page header is initialized ; data space is empty ; * special space is zeroed out . void sizeof (BTPageOpaqueData));/* * Delete item ( s ) from a btree leaf page during VACUUM . * * This routine assumes that the caller already has a full cleanup lock on * the buffer . Also , the given deletable and updatable arrays * must * be * sorted in ascending order . * * Routine deals with deleting TIDs when some ( but not all ) of the heap TIDs * in an existing posting list item are to be removed . This works by * updating / overwriting an existing item with caller ' s new version of the item * ( a version that lacks the TIDs that are to be deleted ) . * * We record VACUUMs and b - tree deletes differently in WAL . Deletes must * generate their own snapshotConflictHorizon directly from the tableam , * whereas VACUUMs rely on the initial VACUUM table scan performing * WAL - logging that takes care of the issue for the table ' s indexes * indirectly . Also , we remove the VACUUM cycle ID from pages , which b - tree * deletes don ' t do . void int ndeletable,int nupdatable)bool needswal = RelationNeedsWAL(rel);char *updatedbuf = NULL;0 ;/* Shouldn't be called unless there's something to do */ 0 || nupdatable > 0 );/* Generate new version of posting lists without deleted TIDs */ if (nupdatable > 0 )/* No ereport(ERROR) until changes are logged */ /* * Handle posting tuple updates . * * Deliberately do this before handling simple deletes . If we did it the * other way around ( i . e . WAL record order - - simple deletes before * updates ) then we ' d have to make compensating changes to the ' updatable ' * array of offset numbers . * * PageIndexTupleOverwrite ( ) won ' t unset each item ' s LP_DEAD bit when it * happens to already be set . It ' s important that we not interfere with * any future simple index tuple deletion operations . for (int i = 0 ; i < nupdatable; i++)if (!PageIndexTupleOverwrite(page, updatedoffset, (Item) itup,"failed to update partially dead item in block %u of index \" %s\"" ,/* Now handle simple deletes of entire tuples */ if (ndeletable > 0 )/* * We can clear the vacuum cycle ID since this page has certainly been * processed by the current vacuum scan . 0 ;/* * Clear the BTP_HAS_GARBAGE page flag . * * This flag indicates the presence of LP_DEAD items on the page ( though * not reliably ) . Note that we only rely on it with pg_upgrade ' d * ! heapkeyspace indexes . That ' s why clearing it here won ' t usually * interfere with simple index tuple deletion . /* XLOG stuff */ if (needswal)0 , buf, REGBUF_STANDARD);if (ndeletable > 0 )0 , deletable,sizeof (OffsetNumber));if (nupdatable > 0 )0 , updatedoffsets,sizeof (OffsetNumber));0 , updatedbuf, updatedbuflen);/* can't leak memory here */ if (updatedbuf != NULL)/* free tuples allocated within _bt_delitems_update() */ for (int i = 0 ; i < nupdatable; i++)/* * Delete item ( s ) from a btree leaf page during single - page cleanup . * * This routine assumes that the caller has pinned and write locked the * buffer . Also , the given deletable and updatable arrays * must * be sorted in * ascending order . * * Routine deals with deleting TIDs when some ( but not all ) of the heap TIDs * in an existing posting list item are to be removed . This works by * updating / overwriting an existing item with caller ' s new version of the item * ( a version that lacks the TIDs that are to be deleted ) . * * This is nearly the same as _ bt_delitems_vacuum as far as what it does to * the page , but it needs its own snapshotConflictHorizon and isCatalogRel * ( from the tableam ) . This is used by the REDO routine to generate recovery * conflicts . The other difference is that only _ bt_delitems_vacuum will * clear page ' s VACUUM cycle ID . static void bool isCatalogRel,int ndeletable,int nupdatable)bool needswal = RelationNeedsWAL(rel);char *updatedbuf = NULL;0 ;/* Shouldn't be called unless there's something to do */ 0 || nupdatable > 0 );/* Generate new versions of posting lists without deleted TIDs */ if (nupdatable > 0 )/* No ereport(ERROR) until changes are logged */ /* Handle updates and deletes just like _bt_delitems_vacuum */ for (int i = 0 ; i < nupdatable; i++)if (!PageIndexTupleOverwrite(page, updatedoffset, (Item) itup,"failed to update partially dead item in block %u of index \" %s\"" ,if (ndeletable > 0 )/* * Unlike _ bt_delitems_vacuum , we * must not * clear the vacuum cycle ID at * this point . The VACUUM command alone controls vacuum cycle IDs . /* * Clear the BTP_HAS_GARBAGE page flag . * * This flag indicates the presence of LP_DEAD items on the page ( though * not reliably ) . Note that we only rely on it with pg_upgrade ' d * ! heapkeyspace indexes . /* XLOG stuff */ if (needswal)0 , buf, REGBUF_STANDARD);if (ndeletable > 0 )0 , deletable,sizeof (OffsetNumber));if (nupdatable > 0 )0 , updatedoffsets,sizeof (OffsetNumber));0 , updatedbuf, updatedbuflen);/* can't leak memory here */ if (updatedbuf != NULL)/* free tuples allocated within _bt_delitems_update() */ for (int i = 0 ; i < nupdatable; i++)/* * Set up state needed to delete TIDs from posting list tuples via " updating " * the tuple . Performs steps common to both _ bt_delitems_vacuum and * _ bt_delitems_delete . These steps must take place before each function ' s * critical section begins . * * updatable and nupdatable are inputs , though note that we will use * _ bt_update_posting ( ) to replace the original itup with a pointer to a final * version in palloc ( ) ' d memory . Caller should free the tuples when its done . * * The first nupdatable entries from updatedoffsets are set to the page offset * number for posting list tuples that caller updates . This is mostly useful * because caller may need to WAL - log the page offsets ( though we always do * this for caller out of convenience ) . * * Returns buffer consisting of an array of xl_btree_update structs that * describe the steps we perform here for caller ( though only when needswal is * true ) . Also sets * updatedbuflen to the final size of the buffer . This * buffer is used by caller when WAL logging is required . static char *int nupdatable,bool needswal)char *updatedbuf = NULL;0 ;/* Shouldn't be called unless there's something to do */ 0 );for (int i = 0 ; i < nupdatable; i++)/* Replace work area IndexTuple with updated version */ /* Keep track of size of xl_btree_update for updatedbuf in passing */ sizeof (uint16);/* Build updatedoffsets buffer in passing */ /* XLOG stuff */ if (needswal)0 ;/* Allocate, set final size for caller */ for (int i = 0 ; i < nupdatable; i++)sizeof (uint16);return updatedbuf;/* * Comparator used by _ bt_delitems_delete_check ( ) to restore deltids array * back to its original leaf - page - wise sort order static int const void *a, const void *b)return pg_cmp_s16(indexdelete1->id, indexdelete2->id);/* * Try to delete item ( s ) from a btree leaf page during single - page cleanup . * * nbtree interface to table_index_delete_tuples ( ) . Deletes a subset of index * tuples from caller ' s deltids array : those whose TIDs are found safe to * delete by the tableam ( or already marked LP_DEAD in index , and so already * known to be deletable by our simple index deletion caller ) . We physically * delete index tuples from buf leaf page last of all ( for index tuples where * that is known to be safe following our table_index_delete_tuples ( ) call ) . * * Simple index deletion caller only includes TIDs from index tuples marked * LP_DEAD , as well as extra TIDs it found on the same leaf page that can be * included without increasing the total number of distinct table blocks for * the deletion operation as a whole . This approach often allows us to delete * some extra index tuples that were practically free for tableam to check in * passing ( when they actually turn out to be safe to delete ) . It probably * only makes sense for the tableam to go ahead with these extra checks when * it is block - oriented ( otherwise the checks probably won ' t be practically * free , which we rely on ) . The tableam interface requires the tableam side * to handle the problem , though , so this is okay ( we as an index AM are free * to make the simplifying assumption that all tableams must be block - based ) . * * Bottom - up index deletion caller provides all the TIDs from the leaf page , * without expecting that tableam will check most of them . The tableam has * considerable discretion around which entries / blocks it checks . Our role in * costing the bottom - up deletion operation is strictly advisory . * * Note : Caller must have added deltids entries ( i . e . entries that go in * delstate ' s main array ) in leaf - page - wise order : page offset number order , * TID order among entries taken from the same posting list tuple ( tiebreak on * TID ) . This order is convenient to work with here . * * Note : We also rely on the id field of each deltids element " capturing " this * original leaf - page - wise order . That is , we expect to be able to get back * to the original leaf - page - wise order just by sorting deltids on the id * field ( tableam will sort deltids for its own reasons , so we ' ll need to put * it back in leaf - page - wise order afterwards ) . void bool isCatalogRel;int ndeletable = 0 ,0 ;/* Use tableam interface to determine which tuples to delete first */ /* Should not WAL-log snapshotConflictHorizon unless it's required */ if (!XLogStandbyInfoActive())/* * Construct a leaf - page - wise description of what _ bt_delitems_delete ( ) * needs to do to physically delete index tuples from the page . * * Must sort deltids array to restore leaf - page - wise order ( original order * before call to tableam ) . This is the order that the loop expects . * * Note that deltids array might be a lot smaller now . It might even have * no entries at all ( with bottom - up deletion caller ) , in which case there * is nothing left to do . sizeof (TM_IndexDelete),if (delstate->ndeltids == 0 )return ;/* We definitely have to delete at least one index tuple (or one TID) */ for (int i = 0 ; i < delstate->ndeltids; i++)int nestedi,if (idxoffnum == postingidxoffnum)/* * This deltid entry is a TID from a posting list tuple that has * already been completely processed 0 );0 );continue ;if (!BTreeTupleIsPosting(itup))/* Plain non-pivot tuple */ if (dstatus->knowndeletable)continue ;/* * itup is a posting list tuple whose lowest deltids entry ( which may * or may not be for the first TID from itup ) is considered here now . * We should process all of the deltids entries for the posting list * together now , though ( not just the lowest ) . Remember to skip over * later itup - related entries during later iterations of outermost * loop . /* Remember work in outermost loop */ /* Initialize for first itup deltids entry */ /* Describes final action for itup */ for (int p = 0 ; p < nitem; p++)int ptidcmp = -1 ;/* * This nested loop reuses work across ptid TIDs taken from itup . * We take advantage of the fact that both itup ' s TIDs and deltids * entries ( within a single itup / posting list grouping ) must both * be in ascending TID order . for (; nestedi < delstate->ndeltids; nestedi++)/* Stop once we get past all itup related deltids entries */ if (tdstatus->idxoffnum != idxoffnum)break ;/* Skip past non-deletable itup related entries up front */ if (!tdstatus->knowndeletable)continue ;/* Entry is first partial ptid match (or an exact match)? */ if (ptidcmp >= 0 )/* Greater than or equal (partial or exact) match... */ break ;/* ...exact ptid match to a deletable deltids entry? */ if (ptidcmp != 0 )continue ;/* Exact match for deletable deltids entry -- ptid gets deleted */ if (vacposting == NULL)sizeof (uint16));0 ;/* Final decision on itup, a posting list tuple */ if (vacposting == NULL)/* No TIDs to delete from itup -- do nothing */ else if (vacposting->ndeletedtids == nitem)/* Straight delete of itup (to delete all TIDs) */ /* Turns out we won't need granular information */ else /* Delete some (but not all) TIDs from itup */ 0 &&/* Physically delete tuples (or TIDs) using deletable (or updatable) */ /* be tidy */ for (int i = 0 ; i < nupdatable; i++)/* * Check that leftsib page ( the btpo_prev of target page ) is not marked with * INCOMPLETE_SPLIT flag . Used during page deletion . * * Returning true indicates that page flag is set in leftsib ( which is * definitely still the left sibling of target ) . When that happens , the * target doesn ' t have a downlink in parent , and the page deletion algorithm * isn ' t prepared to handle that . Deletion of the target page ( or the whole * subtree that contains the target page ) cannot take place . * * Caller should not have a lock on the target page itself , since pages on the * same level must always be locked left to right to avoid deadlocks . static bool bool result;/* Easy case: No left sibling */ if (leftsib == P_NONE)return false ;/* * If the left sibling was concurrently split , so that its next - pointer * doesn ' t point to the current page anymore , the split that created * target must be completed . Caller can reasonably expect that there will * be a downlink to the target page that it can relocate using its stack . * ( We don ' t allow splitting an incompletely split page again until the * previous split has been completed . ) return result;/* * Check that leafrightsib page ( the btpo_next of target leaf page ) is not * marked with ISHALFDEAD flag . Used during page deletion . * * Returning true indicates that page flag is set in leafrightsib , so page * deletion cannot go ahead . Our caller is not prepared to deal with the case * where the parent page does not have a pivot tuples whose downlink points to * leafrightsib ( due to an earlier interrupted VACUUM operation ) . It doesn ' t * seem worth going to the trouble of teaching our caller to deal with it . * The situation will be resolved after VACUUM finishes the deletion of the * half - dead page ( when a future VACUUM operation reaches the target page * again ) . * * _ bt_leftsib_splitflag ( ) is called for both leaf pages and internal pages . * _ bt_rightsib_halfdeadflag ( ) is only called for leaf pages , though . This is * okay because of the restriction on deleting pages that are the rightmost * page of their parent ( i . e . that such deletions can only take place when the * entire subtree must be deleted ) . The leaf level check made here will apply * to a right " cousin " leaf page rather than a simple right sibling leaf page * in cases where caller actually goes on to attempt deleting pages that are * above the leaf page . The right cousin leaf page is representative of the * left edge of the subtree to the right of the to - be - deleted subtree as a * whole , which is exactly the condition that our caller cares about . * ( Besides , internal pages are never marked half - dead , so it isn ' t even * possible to _ directly_ assess if an internal page is part of some other * to - be - deleted subtree . ) static bool bool result;return result;/* * _ bt_pagedel ( ) - - Delete a leaf page from the b - tree , if legal to do so . * * This action unlinks the leaf page from the b - tree structure , removing all * pointers leading to it - - - but not touching its own left and right links . * The page cannot be physically reclaimed right away , since other processes * may currently be trying to follow links leading to the page ; they have to * be allowed to use its right - link to recover . See nbtree / README . * * On entry , the target buffer must be pinned and locked ( either read or write * lock is OK ) . The page must be an empty leaf page , which may be half - dead * already ( a half - dead page should only be passed to us when an earlier * VACUUM operation was interrupted , though ) . Note in particular that caller * should never pass a buffer containing an existing deleted page here . The * lock and pin on caller ' s buffer will be dropped before we return . * * Maintains bulk delete stats for caller , which are taken from vstate . We * need to cooperate closely with caller here so that whole VACUUM operation * reliably avoids any double counting of subsidiary - to - leafbuf pages that we * delete in passing . If such pages happen to be from a block number that is * ahead of the current scanblkno position , then caller is expected to count * them directly later on . It ' s simpler for us to understand caller ' s * requirements than it would be for caller to understand when or how a * deleted page became deleted after the fact . * * NOTE : this leaks memory . Rather than trying to clean up everything * carefully , it ' s better to run it in a temp context that can be reset * frequently . void bool rightsib_empty;/* * Save original leafbuf block number from caller . Only deleted blocks * that are < = scanblkno are added to bulk delete stat ' s pages_deleted * count . /* * " stack " is a search stack leading ( approximately ) to the target page . * It is initially NULL , but when iterating , we keep it to avoid * duplicated search effort . * * Also , when " stack " is not NULL , we have already checked that the * current page is not the right half of an incomplete split , i . e . the * left sibling does not have its INCOMPLETE_SPLIT flag set , including * when the current target page is to the right of caller ' s initial page * ( the scanblkno page ) . for (;;)/* * Internal pages are never deleted directly , only as part of deleting * the whole subtree all the way down to leaf level . * * Also check for deleted pages here . Caller never passes us a fully * deleted page . Only VACUUM can delete pages , so there can ' t have * been a concurrent deletion . Assume that we reached any deleted * page encountered here by following a sibling link , and that the * index is corrupt . if (!P_ISLEAF(opaque) || P_ISDELETED(opaque))/* * Pre - 9 . 4 page deletion only marked internal pages as half - dead , * but now we only use that flag on leaf pages . The old algorithm * was never supposed to leave half - dead pages in the tree , it was * just a transient state , but it was nevertheless possible in * error scenarios . We don ' t know how to deal with them here . They * are harmless as far as searches are considered , but inserts * into the deleted keyspace could add out - of - order downlinks in * the upper levels . Log a notice , hopefully the admin will notice * and reindex . if (P_ISHALFDEAD(opaque))"index \" %s\" contains a half-dead internal page" ,"This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it." )));if (P_ISDELETED(opaque))"found deleted block %u while following right link from block %u in index \" %s\"" ,return ;/* * We can never delete rightmost pages nor root pages . While at it , * check that page is empty , since it ' s possible that the leafbuf page * was empty a moment ago , but has since had some inserts . * * To keep the algorithm simple , we also never delete an incompletely * split page ( they should be rare enough that this doesn ' t make any * meaningful difference to disk usage ) : * * The INCOMPLETE_SPLIT flag on the page tells us if the page is the * left half of an incomplete split , but ensuring that it ' s not the * right half is more complicated . For that , we have to check that * the left sibling doesn ' t have its INCOMPLETE_SPLIT flag set using * _ bt_leftsib_splitflag ( ) . On the first iteration , we temporarily * release the lock on scanblkno / leafbuf , check the left sibling , and * construct a search stack to scanblkno . On subsequent iterations , * we know we stepped right from a page that passed these tests , so * it ' s OK . if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) ||/* Should never fail to delete a half-dead page */ return ;/* * First , remove downlink pointing to the page ( or a parent of the * page , if we are going to delete a taller subtree ) , and mark the * leafbuf page half - dead if (!P_ISHALFDEAD(opaque))/* * We need an approximate pointer to the page ' s parent page . We * use a variant of the standard search mechanism to search for * the page ' s high key ; this will give us a link to either the * current parent or someplace to its left ( if there are multiple * equal high keys , which is possible with ! heapkeyspace indexes ) . * * Also check if this is the right - half of an incomplete split * ( see comment above ) . if (!stack)/* * To avoid deadlocks , we ' d better drop the leaf page lock * before going further . /* * Check that the left sibling of leafbuf ( if any ) is not * marked with INCOMPLETE_SPLIT flag before proceeding if (_bt_leftsib_splitflag(rel, leftsib, leafblkno))return ;/* * We need an insertion scan key , so build one . * * _ bt_search searches for the leaf page that contains any * matching non - pivot tuples , but we need it to " search " for * the high key pivot from the page that we ' re set to delete . * Compensate for the mismatch by having _ bt_search locate the * last position < equal - to - untruncated - prefix non - pivots . /* Set up a BTLessStrategyNumber-like insertion scan key */ false ;true ;/* won't need a second lock or pin on leafbuf */ /* * Re - lock the leaf page , and start over to use our stack * within _ bt_mark_page_halfdead . We must do it that way * because it ' s possible that leafbuf can no longer be * deleted . We need to recheck . * * Note : We can ' t simply hold on to the sleafbuf lock instead , * because it ' s barely possible that sleafbuf is not the same * page as leafbuf . This happens when leafbuf split after our * original lock was dropped , but before _ bt_search finished * its descent . We rely on the assumption that we ' ll find * leafbuf isn ' t safe to delete anymore in this scenario . * ( Page deletion can cope with the stack being to the left of * leafbuf , but not to the right of leafbuf . ) continue ;/* * See if it ' s safe to delete the leaf page , and determine how * many parent / internal pages above the leaf level will be * deleted . If it ' s safe then _ bt_mark_page_halfdead will also * perform the first phase of deletion , which includes marking the * leafbuf page half - dead . if (!_bt_mark_page_halfdead(rel, vstate->info->heaprel, leafbuf,return ;/* * Then unlink it from its siblings . Each call to * _ bt_unlink_halfdead_page unlinks the topmost page from the subtree , * making it shallower . Iterate until the leafbuf page is deleted . false ;while (P_ISHALFDEAD(opaque))/* Check for interrupts in _bt_unlink_halfdead_page */ if (!_bt_unlink_halfdead_page(rel, leafbuf, scanblkno,/* * _ bt_unlink_halfdead_page should never fail , since we * established that deletion is generally safe in * _ bt_mark_page_halfdead - - index must be corrupt . * * Note that _ bt_unlink_halfdead_page already released the * lock and pin on leafbuf for us . false );return ;/* * Check here , as calling loops will have locks held , preventing * interrupts from being processed . /* * The page has now been deleted . If its right sibling is completely * empty , it ' s possible that the reason we haven ' t deleted it earlier * is that it was the rightmost child of the parent . Now that we * removed the downlink for this page , the right sibling might now be * the only child of the parent , and could be removed . It would be * picked up by the next vacuum anyway , but might as well try to * remove it now , so loop back to process the right sibling . * * Note : This relies on the assumption that _ bt_getstackbuf ( ) will be * able to reuse our original descent stack with a different child * block ( provided that the child block is to the right of the * original leaf page reached by _ bt_search ( ) ) . It will even update * the descent stack each time we loop around , avoiding repeated work . if (!rightsib_empty)break ;/* * First stage of page deletion . * * Establish the height of the to - be - deleted subtree with leafbuf at its * lowest level , remove the downlink to the subtree , and mark leafbuf * half - dead . The final to - be - deleted subtree is usually just leafbuf itself , * but may include additional internal pages ( at most one per level of the * tree below the root ) . * * Caller must pass a valid heaprel , since it ' s just about possible that our * call to _ bt_lock_subtree_parent will need to allocate a new index page to * complete a page split . Every call to _ bt_allocbuf needs to pass a heaprel . * * Returns ' false ' if leafbuf is unsafe to delete , usually because leafbuf is * the rightmost child of its parent ( and parent has more than one downlink ) . * Returns ' true ' when the first stage of page deletion completed * successfully . static bool /* * Save info about the leaf page . /* * Before attempting to lock the parent page , check that the right sibling * is not in half - dead state . A half - dead right sibling would have no * downlink in the parent , which would be highly confusing later when we * delete the downlink . It would fail the " right sibling of target page * is also the next child in parent page " cross - check below . if (_bt_rightsib_halfdeadflag(rel, leafrightsib))"could not delete page %u because its right sibling %u is half-dead" ,return false ;/* * We cannot delete a page that is the rightmost child of its immediate * parent , unless it is the only child - - - in which case the parent has to * be deleted too , and the same condition applies recursively to it . We * have to check this condition all the way up before trying to delete , * and lock the parent of the root of the to - be - deleted subtree ( the * " subtree parent " ) . _ bt_lock_subtree_parent ( ) locks the subtree parent * for us . We remove the downlink to the " top parent " page ( subtree root * page ) from the subtree parent page below . * * Initialize topparent to be leafbuf page now . The final to - be - deleted * subtree is often a degenerate one page subtree consisting only of the * leafbuf page . When that happens , the leafbuf page is the final subtree * root page / top parent page . if (!_bt_lock_subtree_parent(rel, heaprel, leafblkno, stack,return false ;#ifdef USE_ASSERT_CHECKING/* * This is just an assertion because _ bt_lock_subtree_parent should have * guaranteed tuple has the expected contents #endif /* * Check that the parent - page index items we ' re about to delete / overwrite * in subtree parent page contain what we expect . This can fail if the * index has become corrupt for some reason . When that happens we back * out of deletion of the leafbuf subtree . ( This is just like the case * where _ bt_lock_subtree_parent ( ) cannot " re - find " leafbuf ' s downlink . ) if (BTreeTupleGetDownLink(itup) != topparentrightsib)"right sibling %u of block %u is not next child %u of block %u in index \" %s\"" ,false );return false ;/* * Any insert which would have gone on the leaf block will now go to its * right sibling . In other words , the key space moves right . /* No ereport(ERROR) until changes are logged */ /* * Update parent of subtree . We want to delete the downlink to the top * parent page / root of the subtree , and the * following * key . Easiest way * is to copy the right sibling ' s downlink over the downlink that points * to top parent page , and then delete the right sibling ' s original pivot * tuple . * * Lanin and Shasha make the key space move left when deleting a page , * whereas the key space moves right here . That ' s why we cannot simply * delete the pivot tuple with the downlink to the top parent page . See * nbtree / README . /* * Mark the leaf page as half - dead , and stamp it with a link to the top * parent page . When the leaf page is also the top parent page , the link * is set to InvalidBlockNumber . 0 , sizeof (IndexTupleData));sizeof (IndexTupleData);if (topparent != leafblkno)else if (!PageIndexTupleOverwrite(page, P_HIKEY, (Item) &trunctuple,"could not overwrite high key in half-dead page" );/* Must mark buffers dirty before XLogInsert */ /* XLOG stuff */ if (RelationNeedsWAL(rel))if (topparent != leafblkno)else 0 , leafbuf, REGBUF_WILL_INIT);1 , subtreeparent, REGBUF_STANDARD);return true ;/* * Second stage of page deletion . * * Unlinks a single page ( in the subtree undergoing deletion ) from its * siblings . Also marks the page deleted . * * To get rid of the whole subtree , including the leaf page itself , call here * until the leaf page is deleted . The original " top parent " established in * the first stage of deletion is deleted in the first call here , while the * leaf page is deleted in the last call here . Note that the leaf page itself * is often the initial top parent page . * * Returns ' false ' if the page could not be unlinked ( shouldn ' t happen ) . If * the right sibling of the current target page is empty , * rightsib_empty is * set to true , allowing caller to delete the target ' s right sibling page in * passing . Note that * rightsib_empty is only actually used by caller when * target page is leafbuf , following last call here for leafbuf / the subtree * containing leafbuf . ( We always set * rightsib_empty for caller , just to be * consistent . ) * * Must hold pin and lock on leafbuf at entry ( read or write doesn ' t matter ) . * On success exit , we ' ll be holding pin and write lock . On failure exit , * we ' ll release both pin and lock before returning ( we define it that way * to avoid having to reacquire a lock we already released ) . static bool bool *rightsib_empty, BTVacState *vstate)bool rightsib_is_rightmost;/* * Remember some information about the leaf page . /* * Check here , as calling loops will have locks held , preventing * interrupts from being processed . /* Unlink the current top parent of the subtree */ if (!BlockNumberIsValid(target))/* Target is leaf page (or leaf page is top parent, if you prefer) */ 0 ;else /* Target is the internal page taken from leaf's top parent link */ /* Fetch the block number of the target's left sibling */ 0 );/* * To avoid deadlocks , we ' d better drop the target page lock before * going further . /* * We have to lock the pages we need to modify in the standard order : * moving right , then up . Else we will deadlock against other writers . * * So , first lock the leaf page , if it ' s not the target . Then find and * write - lock the current left sibling of the target page . The sibling * that was current a moment ago could have split , so we may have to move * right . if (target != leafblkno)if (leftsib != P_NONE)while (P_ISDELETED(opaque) || opaque->btpo_next != target)bool leftsibvalid = true ;/* * Before we follow the link from the page that was the left * sibling mere moments ago , validate its right link . This * reduces the opportunities for loop to fail to ever make any * progress in the presence of index corruption . * * Note : we rely on the assumption that there can only be one * vacuum process running at a time ( against the same index ) . if (P_RIGHTMOST(opaque) || P_ISDELETED(opaque) ||false ;if (!leftsibvalid)/* * This is known to fail in the field ; sibling link corruption * is relatively common . Press on with vacuuming rather than * just throwing an ERROR . "valid left sibling for deletion target could not be located: " "left sibling %u of target %u with leafblkno %u and scanblkno %u on level %u of index \" %s\"" ,/* Must release all pins and locks on failure exit */ if (target != leafblkno)return false ;/* step right one page */ else /* Next write-lock the target page itself */ /* * Check page is still empty etc , else abandon deletion . This is just for * paranoia ' s sake ; a half - dead page cannot resurrect because there can be * only one vacuum process running at a time . if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) || P_ISDELETED(opaque))"target page changed status unexpectedly in block %u of index \" %s\"" ,if (opaque->btpo_prev != leftsib)"target page left link unexpectedly changed from %u to %u in block %u of index \" %s\"" ,if (target == leafblkno)if (P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||"target leaf page changed status unexpectedly in block %u of index \" %s\"" ,/* Leaf page is also target page: don't set leaftopparent */ else if (P_FIRSTDATAKEY(opaque) != PageGetMaxOffsetNumber(page) ||"target internal page on level %u changed status unexpectedly in block %u of index \" %s\"" ,/* Target is internal: set leaftopparent for next call here... */ /* ...except when it would be a redundant pointer-to-self */ if (leaftopparent == leafblkno)/* No leaftopparent for level 0 (leaf page) or level 1 target */ 1 );/* * And next write - lock the ( current ) right sibling . /* * Validate target ' s right sibling page . Its left link must point back to * the target page . if (opaque->btpo_prev != target)/* * This is known to fail in the field ; sibling link corruption is * relatively common . Press on with vacuuming rather than just * throwing an ERROR ( same approach used for left - sibling ' s - right - link * validation check a moment ago ) . "right sibling's left-link doesn't match: " "right sibling %u of target %u with leafblkno %u " "and scanblkno %u spuriously links to non-target %u " "on level %u of index \" %s\"" ,/* Must release all pins and locks on failure exit */ if (BufferIsValid(lbuf))if (target != leafblkno)return false ;/* * If we are deleting the next - to - last page on the target ' s level , then * the rightsib is a candidate to become the new fast root . ( In theory , it * might be possible to push the fast root even further down , but the odds * of doing so are slim , and the locking considerations daunting . ) * * We can safely acquire a lock on the metapage here - - - see comments for * _ bt_newlevel ( ) . if (leftsib == P_NONE && rightsib_is_rightmost)if (P_RIGHTMOST(opaque))/* rightsib will be the only one left on the level */ /* * The expected case here is btm_fastlevel = = targetlevel + 1 ; if * the fastlevel is < = targetlevel , something is wrong , and we * choose to overwrite it to fix it . if (metad->btm_fastlevel > targetlevel + 1 )/* no update wanted */ /* * Here we begin doing the deletion . /* No ereport(ERROR) until changes are logged */ /* * Update siblings ' side - links . Note the target page ' s side - links will * continue to point to the siblings . Asserts here are just rechecking * things we already verified above . if (BufferIsValid(lbuf))/* * If we deleted a parent of the targeted leaf page , instead of the leaf * itself , update the leaf to point to the next remaining child in the * subtree . * * Note : We rely on the fact that a buffer pin on the leaf page has been * held since leafhikey was initialized . This is safe , though only * because the page was already half - dead at that point . The leaf page * cannot have been modified by any other backend during the period when * no lock was held . if (target != leafblkno)/* * Mark the page itself deleted . It can be recycled when all current * transactions are gone . Storing GetTopTransactionId ( ) would work , but * we ' re in VACUUM and would not otherwise have an XID . Having already * updated links to the target , ReadNextFullTransactionId ( ) suffices as an * upper bound . Any scan having retained a now - stale link is advertising * in its PGPROC an xmin less than or equal to the value we read here . It * will continue to do so , holding back the xmin horizon , for the duration * of that scan . /* * Store upper bound XID that ' s used to determine when deleted page is no * longer needed as a tombstone 0 ;/* And update the metapage, if needed */ if (BufferIsValid(metabuf))/* upgrade metapage if needed */ if (metad->btm_version < BTREE_NOVAC_VERSION)/* Must mark buffers dirty before XLogInsert */ if (BufferIsValid(lbuf))if (target != leafblkno)/* XLOG stuff */ if (RelationNeedsWAL(rel))0 , buf, REGBUF_WILL_INIT);if (BufferIsValid(lbuf))1 , lbuf, REGBUF_STANDARD);2 , rbuf, REGBUF_STANDARD);if (target != leafblkno)3 , leafbuf, REGBUF_WILL_INIT);/* information stored on the target/to-be-unlinked block */ /* information needed to recreate the leaf block (if not the target) */ if (BufferIsValid(metabuf))4 , metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);4 , &xlmeta, sizeof (xl_btree_metadata));else if (BufferIsValid(metabuf))if (BufferIsValid(lbuf))if (target != leafblkno)/* release metapage */ if (BufferIsValid(metabuf))/* release siblings */ if (BufferIsValid(lbuf))/* If the target is not leafbuf, we're done with it now -- release it */ if (target != leafblkno)/* * Maintain pages_newly_deleted , which is simply the number of pages * deleted by the ongoing VACUUM operation . * * Maintain pages_deleted in a way that takes into account how * btvacuumpage ( ) will count deleted pages that have yet to become * scanblkno - - only count page when it ' s not going to get that treatment * later on . if (target <= scanblkno)/* * Remember information about the target page ( now a newly deleted page ) * in dedicated vstate space for later . The page will be considered as a * candidate to place in the FSM at the end of the current btvacuumscan ( ) * call . /* Success - hold on to lock on leafbuf (might also have been target) */ return true ;/* * Establish how tall the to - be - deleted subtree will be during the first stage * of page deletion . * * Caller ' s child argument is the block number of the page caller wants to * delete ( this is leafbuf ' s block number , except when we ' re called * recursively ) . stack is a search stack leading to it . Note that we will * update the stack entry ( s ) to reflect current downlink positions - - - this is * similar to the corresponding point in page split handling . * * If " first stage " caller cannot go ahead with deleting _ any_ pages , returns * false . Returns true on success , in which case caller can use certain * details established here to perform the first stage of deletion . This * function is the last point at which page deletion may be deemed unsafe * ( barring index corruption , or unexpected concurrent page deletions ) . * * We write lock the parent of the root of the to - be - deleted subtree for * caller on success ( i . e . we leave our lock on the * subtreeparent buffer for * caller ) . Caller will have to remove a downlink from * subtreeparent . We * also set a * subtreeparent offset number in * poffset , to indicate the * location of the pivot tuple that contains the relevant downlink . * * The root of the to - be - deleted subtree is called the " top parent " . Note * that the leafbuf page is often the final " top parent " page ( you can think * of the leafbuf page as a degenerate single page subtree when that happens ) . * Caller should initialize * topparent to the target leafbuf page block number * ( while * topparentrightsib should be set to leafbuf ' s right sibling block * number ) . We will update * topparent ( and * topparentrightsib ) for caller * here , though only when it turns out that caller will delete at least one * internal page ( i . e . only when caller needs to store a valid link to the top * parent block in the leafbuf page using BTreeTupleSetTopParent ( ) ) . static bool /* * Locate the pivot tuple whose downlink points to " child " . Write lock * the parent page itself . if (pbuf == InvalidBuffer)/* * Failed to " re - find " a pivot tuple whose downlink matched our child * block number on the parent level - - the index must be corrupt . * Don ' t even try to delete the leafbuf subtree . Just report the * issue and press on with vacuuming the index . * * Note : _ bt_getstackbuf ( ) recovers from concurrent page splits that * take place on the parent level . Its approach is a near - exhaustive * linear search . This also gives it a surprisingly good chance of * recovering in the event of a buggy or inconsistent opclass . But we * don ' t rely on that here . "failed to re-find parent key in index \" %s\" for deletion target page %u" ,false );return false ;/* * _ bt_getstackbuf ( ) completes page splits on returned parent buffer when * required . * * In general it ' s a bad idea for VACUUM to use up more disk space , which * is why page deletion does not finish incomplete page splits most of the * time . We allow this limited exception because the risk is much lower , * and the potential downside of not proceeding is much higher : A single * internal page with the INCOMPLETE_SPLIT flag set might otherwise * prevent us from deleting hundreds of empty leaf pages from one level * down . if (parentoffset < maxoff)/* * Child is not the rightmost child in parent , so it ' s safe to delete * the subtree whose root / topparent is child page return true ;/* * Child is the rightmost child of parent . * * Since it ' s the rightmost child of parent , deleting the child ( or * deleting the subtree whose root / topparent is the child page ) is only * safe when it ' s also possible to delete the parent . if (parentoffset != P_FIRSTDATAKEY(opaque) || P_RIGHTMOST(opaque))/* * Child isn ' t parent ' s only child , or parent is rightmost on its * entire level . Definitely cannot delete any pages . return false ;/* * Now make sure that the parent deletion is itself safe by examining the * child ' s grandparent page . Recurse , passing the parent page as the * child page ( child ' s grandparent is the parent on the next level up ) . If * parent deletion is unsafe , then child deletion must also be unsafe ( in * which case caller cannot delete any pages at all ) . /* * Release lock on parent before recursing . * * It ' s OK to release page locks on parent before recursive call locks * grandparent . An internal page can only acquire an entry if the child * is split , but that cannot happen as long as we still hold a lock on the * leafbuf page . /* * Before recursing , check that the left sibling of parent ( if any ) is not * marked with INCOMPLETE_SPLIT flag first ( must do so after we drop the * parent lock ) . * * Note : We deliberately avoid completing incomplete splits here . if (_bt_leftsib_splitflag(rel, leftsibparent, parent))return false ;/* Recurse to examine child page's grandparent page */ return _bt_lock_subtree_parent(rel, heaprel, parent, stack->bts_parent,/* * Initialize local memory state used by VACUUM for _ bt_pendingfsm_finalize * optimization . * * Called at the start of a btvacuumscan ( ) . Caller ' s cleanuponly argument * indicates if ongoing VACUUM has not ( and will not ) call btbulkdelete ( ) . * * We expect to allocate memory inside VACUUM ' s top - level memory context here . * The working buffer is subject to a limit based on work_mem . Our strategy * when the array can no longer grow within the bounds of that limit is to * stop saving additional newly deleted pages , while proceeding as usual with * the pages that we can fit . void bool cleanuponly)/* * Don ' t bother with optimization in cleanup - only case - - we don ' t expect * any newly deleted pages . Besides , cleanup - only calls to btvacuumscan ( ) * can only take place because this optimization didn ' t work out during * the last VACUUM . if (cleanuponly)return ;/* * Cap maximum size of array so that we always respect work_mem . Avoid * int overflow here . 256 ;1024 ) / sizeof (BTPendingFSM);sizeof (BTPendingFSM));/* BTVacState.maxbufsize has type int */ /* Stay sane with small work_mem */ int ) maxbufsize;/* Allocate buffer, indicate that there are currently 0 pending pages */ sizeof (BTPendingFSM) * vstate->bufsize);0 ;/* * Place any newly deleted pages ( i . e . pages that _ bt_pagedel ( ) deleted during * the ongoing VACUUM operation ) into the free space map - - though only when * it is actually safe to do so by now . * * Called at the end of a btvacuumscan ( ) , just before free space map vacuuming * takes place . * * Frees memory allocated by _ bt_pendingfsm_init ( ) , if any . void if (vstate->npendingpages == 0 )/* Just free memory when nothing to do */ if (vstate->pendingpages)return ;#ifdef DEBUG_BTREE_PENDING_FSM/* * Debugging aid : Sleep for 5 seconds to greatly increase the chances of * placing pending pages in the FSM . Note that the optimization will * never be effective without some other backend concurrently consuming an * XID . 5000000 L);#endif /* * Recompute VACUUM XID boundaries . * * We don ' t actually care about the oldest non - removable XID . Computing * the oldest such XID has a useful side - effect that we rely on : it * forcibly updates the XID horizon state for this backend . This step is * essential ; GlobalVisCheckRemovableFullXid ( ) will not reliably recognize * that it is now safe to recycle newly deleted pages without this step . for (int i = 0 ; i < vstate->npendingpages; i++)/* * Do the equivalent of checking BTPageIsRecyclable ( ) , but without * accessing the page again a second time . * * Give up on finding the first non - recyclable page - - all later pages * must be non - recyclable too , since _ bt_pendingfsm_add ( ) adds pages * to the array in safexid order . if (!GlobalVisCheckRemovableFullXid(heaprel, safexid))break ;/* * Maintain array of pages that were deleted during current btvacuumscan ( ) * call , for use in _ bt_pendingfsm_finalize ( ) static void #ifdef USE_ASSERT_CHECKING/* * Verify an assumption made by _ bt_pendingfsm_finalize ( ) : pages from the * array will always be in safexid order ( since that is the order that we * save them in here ) if (vstate->npendingpages > 0 )1 ].safexid;#endif /* * If temp buffer reaches maxbufsize / work_mem capacity then we discard * information about this page . * * Note that this also covers the case where we opted to not use the * optimization in _ bt_pendingfsm_init ( ) . if (vstate->npendingpages == vstate->maxbufsize)return ;/* Consider enlarging buffer */ if (vstate->npendingpages == vstate->bufsize)int newbufsize = vstate->bufsize * 2 ;/* Respect work_mem */ if (newbufsize > vstate->maxbufsize)sizeof (BTPendingFSM) * vstate->bufsize);/* Save metadata for newly deleted page */
Messung V0.5 in Prozent C=90 H=95 G=92
¤ Dauer der Verarbeitung: 0.151 Sekunden
(vorverarbeitet am 2026-08-08)
¤ *© Formatika GbR, Deutschland
2026-08-25
Neuigkeiten Aktuelles Motto des Tages Open Source Software
Jenseits des Üblichen ....
Besucherstatistik
Statistik #Sources=141584 #Domains=752002
