1/*-------------------------------------------------------------------------
4 * BTree-specific page management code for the Postgres btree access
7 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
12 * src/backend/access/nbtree/nbtpage.c
15 * Postgres btree pages look like ordinary relation pages. The opaque
16 * data at high addresses includes pointers to left and right siblings
17 * and flag data describing page state. The first page in a btree, page
18 * zero, is special -- it stores meta-information describing the tree.
19 * Pages one and higher store the actual tree data.
21 *-------------------------------------------------------------------------
48 Size *updatedbuflen,
bool needswal);
64 * _bt_initmetapage() -- Fill a page buffer with a correct metapage image
90 * Set pd_lower just past the end of the metadata. This is essential,
91 * because without doing so, metadata will be lost if xlog.c compresses
99 * _bt_upgrademetapage() -- Upgrade a meta-page from an old format to version
100 * 3, the last version that can be updated without broadly affecting
101 * on-disk compatibility. (A REINDEX is required to upgrade to v4.)
103 * This routine does purely in-memory image upgrade. Caller is
104 * responsible for locking, WAL-logging etc.
115 /* It must be really a meta page of upgradable version */
120 /* Set version number and fill extra fields added into version 3 */
124 /* Only a REINDEX can set this field */
128 /* Adjust pd_lower (see _bt_initmetapage() for details) */
134 * Get metadata from share-locked buffer containing metapage, while performing
135 * standard sanity checks.
137 * Callers that cache data returned here in local cache should note that an
138 * on-the-fly upgrade using _bt_upgrademetapage() can change the version field
139 * and BTREE_NOVAC_VERSION specific fields without invalidating local cache.
152 /* sanity-check the metapage */
156 (
errcode(ERRCODE_INDEX_CORRUPTED),
157 errmsg(
"index \"%s\" is not a btree",
163 (
errcode(ERRCODE_INDEX_CORRUPTED),
164 errmsg(
"version mismatch in index \"%s\": file version %d, "
165 "current version %d, minimal supported version %d",
173 * _bt_vacuum_needs_cleanup() -- Checks if index needs cleanup
175 * Called by btvacuumcleanup when btbulkdelete was never called because no
176 * index tuples needed to be deleted.
188 * Copy details from metapage to local variables quickly.
190 * Note that we deliberately avoid using cached version of metapage here.
200 * Metapage needs to be dynamically upgraded to store fields that are
201 * only present when btm_version >= BTREE_NOVAC_VERSION
211 * Trigger cleanup in rare cases where prev_num_delpages exceeds 5% of the
212 * total size of the index. We can reasonably expect (though are not
213 * guaranteed) to be able to recycle this many pages if we decide to do a
214 * btvacuumscan call during the ongoing btvacuumcleanup. For further
215 * details see the nbtree/README section on placing deleted pages in the
218 if (prev_num_delpages > 0 &&
226 * _bt_set_cleanup_info() -- Update metapage for btvacuumcleanup.
228 * Called at the end of btvacuumcleanup, when num_delpages value has been
239 * On-disk compatibility note: The btm_last_cleanup_num_delpages metapage
240 * field started out as a TransactionId field called btm_oldest_btpo_xact.
241 * Both "versions" are just uint32 fields. It was convenient to repurpose
242 * the field when we began to use 64-bit XIDs in deleted pages.
244 * It's possible that a pg_upgrade'd database will contain an XID value in
245 * what is now recognized as the metapage's btm_last_cleanup_num_delpages
246 * field. _bt_vacuum_needs_cleanup() may even believe that this value
247 * indicates that there are lots of pages that it needs to recycle, when
248 * in reality there are only one or two. The worst that can happen is
249 * that there will be a call to btvacuumscan a little earlier, which will
250 * set btm_last_cleanup_num_delpages to a sane value when we're called.
252 * Note also that the metapage's btm_last_cleanup_num_heap_tuples field is
253 * no longer used as of PostgreSQL 14. We set it to -1.0 on rewrite, just
260 /* Don't miss chance to upgrade index/metapage when BTREE_MIN_VERSION */
264 /* Usually means index continues to have num_delpages of 0 */
269 /* trade in our read lock for a write lock */
275 /* upgrade meta-page if needed */
279 /* update cleanup-related information */
284 /* write wal record if needed */
315 * _bt_getroot() -- Get the root page of the btree.
317 * Since the root page can move around the btree file, we have to read
318 * its location from the metadata page, and then read the root page
319 * itself. If no root page exists yet, we have to create one.
321 * The access type parameter (BT_READ or BT_WRITE) controls whether
322 * a new root page will be created or not. If access = BT_READ,
323 * and no root page exists, we just return InvalidBuffer. For
324 * BT_WRITE, we try to create the root page if it doesn't exist.
325 * NOTE that the returned root page will have only a read lock set
326 * on it even if access = BT_WRITE!
328 * If access = BT_WRITE, heaprel must be set; otherwise caller can just
329 * pass NULL. See _bt_allocbuf for an explanation.
331 * The returned page is not necessarily the true root --- it could be
332 * a "fast root" (a page that is alone in its level due to deletions).
333 * Also, if the root page is split while we are "in flight" to it,
334 * what we will return is the old root, which is now just the leftmost
335 * page on a probably-not-very-wide level. For most purposes this is
336 * as good as or better than the true root, so we do not bother to
337 * insist on finding the true root. We do, however, guarantee to
338 * return a live (not deleted or half-dead) page.
340 * On successful return, the root page is pinned and read-locked.
341 * The metadata page is not locked or pinned on exit.
357 * Try to use previously-cached metapage data to find the root. This
358 * normally saves one buffer access per index search, which is a very
359 * helpful savings in bufmgr traffic and hence contention.
364 /* We shouldn't have cached it if any of these fail */
381 * Since the cache might be stale, we check the page more carefully
382 * here than normal. We *must* check that it's not deleted. If it's
383 * not alone on its level, then we reject too --- this may be overly
384 * paranoid but better safe than sorry. Note we don't check P_ISROOT,
385 * because that's not set in a "fast root".
392 /* OK, accept cached page as the root */
396 /* Cache is stale, throw it away */
405 /* if no root page initialized yet, do it */
410 /* If access = BT_READ, caller doesn't want us to create root yet */
417 /* trade in our read lock for a write lock */
422 * Race condition: if someone else initialized the metadata between
423 * the time we released the read lock and acquired the write lock, we
424 * must avoid doing it again.
429 * Metadata initialized by someone else. In order to guarantee no
430 * deadlocks, we have to release the metadata page and start all
431 * over again. (Is that really true? But it's hardly worth trying
432 * to optimize this case.)
439 * Get, initialize, write, and leave a lock of the appropriate type on
440 * the new root page. Since this is the first page in the tree, it's
441 * a leaf as well as the root.
451 /* Get raw page pointer for metapage */
454 /* NO ELOG(ERROR) till meta is updated */
457 /* upgrade metapage if needed */
507 * swap root write lock for read lock. There is no danger of anyone
508 * else accessing the new root page while it's unlocked, since no one
509 * else knows where it is yet.
514 /* okay, metadata is correct, release lock on it without caching */
524 * Cache the metapage data for next time
531 * We are done with the metapage; arrange to release it via first
532 * _bt_relandgetbuf call
545 /* it's dead, Jim. step right one page */
547 elog(
ERROR,
"no live root page found in index \"%s\"",
553 elog(
ERROR,
"root page %u of index \"%s\" has level %u, expected %u",
559 * By here, we have a pin and read lock on the root page, and no lock set
560 * on the metadata page. Return the root page's buffer.
566 * _bt_gettrueroot() -- Get the true root page of the btree.
568 * This is the same as the BT_READ case of _bt_getroot(), except
569 * we follow the true-root link not the fast-root link.
571 * By the time we acquire lock on the root page, it might have been split and
572 * not be the true root anymore. This is okay for the present uses of this
573 * routine; we only really need to be able to move up at least one tree level
574 * from whatever non-root page we were at. If we ever do need to lock the
575 * one true root page, we could loop here, re-reading the metapage on each
576 * failure. (Note that it wouldn't do to hold the lock on the metapage while
577 * moving to the root --- that'd deadlock against any concurrent root split.)
593 * We don't try to use cached metapage data here, since (a) this path is
594 * not performance-critical, and (b) if we are here it suggests our cache
595 * is out-of-date anyway. In light of point (b), it's probably safest to
596 * actively flush any cached metapage info.
610 (
errcode(ERRCODE_INDEX_CORRUPTED),
611 errmsg(
"index \"%s\" is not a btree",
617 (
errcode(ERRCODE_INDEX_CORRUPTED),
618 errmsg(
"version mismatch in index \"%s\": file version %d, "
619 "current version %d, minimal supported version %d",
623 /* if no root page initialized yet, fail */
634 * We are done with the metapage; arrange to release it via first
635 * _bt_relandgetbuf call
648 /* it's dead, Jim. step right one page */
650 elog(
ERROR,
"no live root page found in index \"%s\"",
656 elog(
ERROR,
"root page %u of index \"%s\" has level %u, expected %u",
664 * _bt_getrootheight() -- Get the height of the btree search tree.
666 * We return the level (counting from zero) of the current fast root.
667 * This represents the number of tree levels we'd have to descend through
668 * to start any btree index search.
670 * This is used by the planner for cost-estimation purposes. Since it's
671 * only an estimate, slightly-stale data is fine, hence we don't worry
672 * about updating previously cached data.
687 * If there's no root page yet, _bt_getroot() doesn't expect a cache
688 * to be made, so just stop here and report the index height is zero.
689 * (XXX perhaps _bt_getroot() should be changed to allow this case.)
698 * Cache the metapage data for next time
706 /* Get cached page */
708 /* We shouldn't have cached it if any of these fail */
720 * _bt_metaversion() -- Get version/status info from metapage.
722 * Sets caller's *heapkeyspace and *allequalimage arguments using data
723 * from the B-Tree metapage (could be locally-cached version). This
724 * information needs to be stashed in insertion scankey, so we provide a
725 * single function that fetches both at once.
727 * This is used to determine the rules that must be used to descend a
728 * btree. Version 4 indexes treat heap TID as a tiebreaker attribute.
729 * pg_upgrade'd version 3 indexes need extra steps to preserve reasonable
730 * performance when inserting a new BTScanInsert-wise duplicate tuple
731 * among many leaf pages already full of such duplicates.
733 * Also sets allequalimage field, which indicates whether or not it is
734 * safe to apply deduplication. We rely on the assumption that
735 * btm_allequalimage will be zero'ed on heapkeyspace indexes that were
736 * pg_upgrade'd from Postgres 12.
751 * If there's no root page yet, _bt_getroot() doesn't expect a cache
752 * to be made, so just stop here. (XXX perhaps _bt_getroot() should
753 * be changed to allow this case.)
765 * Cache the metapage data for next time
767 * An on-the-fly version upgrade performed by _bt_upgrademetapage()
768 * can change the nbtree version for an index without invalidating any
769 * local cache. This is okay because it can only happen when moving
770 * from version 2 to version 3, both of which are !heapkeyspace
779 /* Get cached page */
781 /* We shouldn't have cached it if any of these fail */
794 * _bt_checkpage() -- Verify that a freshly-read page looks sane.
802 * ReadBuffer verifies that every newly-read page passes
803 * PageHeaderIsValid, which means it either contains a reasonably sane
804 * page header or is all-zero. We have to defend against the all-zero
809 (
errcode(ERRCODE_INDEX_CORRUPTED),
810 errmsg(
"index \"%s\" contains unexpected zero page at block %u",
813 errhint(
"Please REINDEX it.")));
816 * Additionally check that the special area looks sane.
820 (
errcode(ERRCODE_INDEX_CORRUPTED),
821 errmsg(
"index \"%s\" contains corrupted page at block %u",
824 errhint(
"Please REINDEX it.")));
828 * _bt_getbuf() -- Get an existing block in a buffer, for read or write.
830 * The general rule in nbtree is that it's never okay to access a
831 * page without holding both a buffer pin and a buffer lock on
834 * When this routine returns, the appropriate lock is set on the
835 * requested buffer and its reference count has been incremented
836 * (ie, the buffer is "locked and pinned"). Also, we apply
837 * _bt_checkpage to sanity-check the page, and perform Valgrind
838 * client requests that help Valgrind detect unsafe page accesses.
840 * Note: raw LockBuffer() calls are disallowed in nbtree; all
841 * buffer lock requests need to go through wrapper functions such
851 /* Read an existing block of the relation */
860 * _bt_allocbuf() -- Allocate a new block/page.
862 * Returns a write-locked buffer containing an unallocated nbtree page.
864 * Callers are required to pass a valid heaprel. We need heaprel so that we
865 * can handle generating a snapshotConflictHorizon that makes reusing a page
866 * from the FSM safe for queries that may be running on standbys.
878 * First see if the FSM knows of any free pages.
880 * We can't trust the FSM's report unreservedly; we have to check that the
881 * page is still free. (For example, an already-free page could have been
882 * re-used between the time the last VACUUM scanned it and the time the
883 * VACUUM made its FSM updates.)
885 * In fact, it's worse than that: we can't even assume that it's safe to
886 * take a lock on the reported page. If somebody else has a lock on it,
887 * or even worse our own caller does, we could deadlock. (The own-caller
888 * scenario is actually not improbable. Consider an index on a serial or
889 * timestamp column. Nearly all splits will be at the rightmost page, so
890 * it's entirely likely that _bt_split will call us while holding a lock
891 * on the page most recently acquired from FSM. A VACUUM running
892 * concurrently with the previous split could well have placed that page
895 * To get around that, we ask for only a conditional lock on the reported
896 * page. If we fail, then someone else is using the page, and we may
897 * reasonably assume it's not free. (If we happen to be wrong, the worst
898 * consequence is the page will be lost to use till the next VACUUM, which
899 * is no big problem.)
912 * It's possible to find an all-zeroes page in an index. For
913 * example, a backend might successfully extend the relation one
914 * page and then crash before it is able to make a WAL entry for
915 * adding the page. If we find a zeroed page then reclaim it
920 /* Okay to use page. Initialize and return it. */
928 * If we are generating WAL for Hot Standby then create a WAL
929 * record that will allow us to conflict with queries running
930 * on standby, in case they have snapshots older than safexid
938 * Note that we don't register the buffer with the record,
939 * because this operation doesn't modify the page (that
940 * already happened, back when VACUUM deleted the page).
941 * This record only exists to provide a conflict point for
942 * Hot Standby. See record REDO routine comments.
945 xlrec_reuse.
block = blkno;
956 /* Okay to use page. Re-initialize and return it. */
960 elog(
DEBUG2,
"FSM returned nonrecyclable page");
965 elog(
DEBUG2,
"FSM returned nonlockable page");
966 /* couldn't get lock, so just drop pin */
972 * Extend the relation by one page. Need to use RBM_ZERO_AND_LOCK or we
973 * risk a race condition against btvacuumscan --- see comments therein.
974 * This forces us to repeat the valgrind request that _bt_lockbuf()
975 * otherwise would make, as we can't use _bt_lockbuf() without introducing
982 /* Initialize the new page before returning it */
991 * _bt_relandgetbuf() -- release a locked buffer and get another one.
993 * This is equivalent to _bt_relbuf followed by _bt_getbuf. Also, if obuf is
994 * InvalidBuffer then it reduces to just _bt_getbuf; allowing this case
995 * simplifies some callers.
997 * The original motivation for using this was to avoid two entries to the
998 * bufmgr when one would do. However, now it's mainly just a notational
999 * convenience. The only case where it saves work over _bt_relbuf/_bt_getbuf
1000 * is when the target page is the same one already in the buffer.
1018 * _bt_relbuf() -- release a locked buffer.
1020 * Lock and pin (refcount) are both dropped.
1030 * _bt_lockbuf() -- lock a pinned buffer.
1032 * Lock is acquired without acquiring another pin. This is like a raw
1033 * LockBuffer() call, but performs extra steps needed by Valgrind.
1035 * Note: Caller may need to call _bt_checkpage() with buf when pin on buf
1036 * wasn't originally acquired in _bt_getbuf() or _bt_relandgetbuf().
1041 /* LockBuffer() asserts that pin is held by this backend */
1045 * It doesn't matter that _bt_unlockbuf() won't get called in the event of
1046 * an nbtree error (e.g. a unique violation error). That won't cause
1047 * Valgrind false positives.
1049 * The nbtree client requests are superimposed on top of the bufmgr.c
1050 * buffer pin client requests. In the event of an nbtree error the buffer
1051 * will certainly get marked as defined when the backend once again
1052 * acquires its first pin on the buffer. (Of course, if the backend never
1053 * touches the buffer again then it doesn't matter that it remains
1054 * non-accessible to Valgrind.)
1056 * Note: When an IndexTuple C pointer gets computed using an ItemId read
1057 * from a page while a lock was held, the C pointer becomes unsafe to
1058 * dereference forever as soon as the lock is released. Valgrind can only
1059 * detect cases where the pointer gets dereferenced with no _current_
1060 * lock/pin held, though.
1067 * _bt_unlockbuf() -- unlock a pinned buffer.
1073 * Buffer is pinned and locked, which means that it is expected to be
1074 * defined and addressable. Check that proactively.
1078 /* LockBuffer() asserts that pin is held by this backend */
1086 * _bt_conditionallockbuf() -- conditionally BT_WRITE lock pinned
1089 * Note: Caller may need to call _bt_checkpage() with buf when pin on buf
1090 * wasn't originally acquired in _bt_getbuf() or _bt_relandgetbuf().
1095 /* ConditionalLockBuffer() asserts that pin is held by this backend */
1106 * _bt_upgradelockbufcleanup() -- upgrade lock to a full cleanup lock.
1112 * Buffer is pinned and locked, which means that it is expected to be
1113 * defined and addressable. Check that proactively.
1117 /* LockBuffer() asserts that pin is held by this backend */
1123 * _bt_pageinit() -- Initialize a new page.
1125 * On return, the page header is initialized; data space is empty;
1126 * special space is zeroed out.
1135 * Delete item(s) from a btree leaf page during VACUUM.
1137 * This routine assumes that the caller already has a full cleanup lock on
1138 * the buffer. Also, the given deletable and updatable arrays *must* be
1139 * sorted in ascending order.
1141 * Routine deals with deleting TIDs when some (but not all) of the heap TIDs
1142 * in an existing posting list item are to be removed. This works by
1143 * updating/overwriting an existing item with caller's new version of the item
1144 * (a version that lacks the TIDs that are to be deleted).
1146 * We record VACUUMs and b-tree deletes differently in WAL. Deletes must
1147 * generate their own snapshotConflictHorizon directly from the tableam,
1148 * whereas VACUUMs rely on the initial VACUUM table scan performing
1149 * WAL-logging that takes care of the issue for the table's indexes
1150 * indirectly. Also, we remove the VACUUM cycle ID from pages, which b-tree
1161 char *updatedbuf = NULL;
1162 Size updatedbuflen = 0;
1165 /* Shouldn't be called unless there's something to do */
1166 Assert(ndeletable > 0 || nupdatable > 0);
1168 /* Generate new version of posting lists without deleted TIDs */
1171 updatedoffsets, &updatedbuflen,
1174 /* No ereport(ERROR) until changes are logged */
1178 * Handle posting tuple updates.
1180 * Deliberately do this before handling simple deletes. If we did it the
1181 * other way around (i.e. WAL record order -- simple deletes before
1182 * updates) then we'd have to make compensating changes to the 'updatable'
1183 * array of offset numbers.
1185 * PageIndexTupleOverwrite() won't unset each item's LP_DEAD bit when it
1186 * happens to already be set. It's important that we not interfere with
1187 * any future simple index tuple deletion operations.
1189 for (
int i = 0;
i < nupdatable;
i++)
1195 itup = updatable[
i]->
itup;
1199 elog(
PANIC,
"failed to update partially dead item in block %u of index \"%s\"",
1203 /* Now handle simple deletes of entire tuples */
1208 * We can clear the vacuum cycle ID since this page has certainly been
1209 * processed by the current vacuum scan.
1215 * Clear the BTP_HAS_GARBAGE page flag.
1217 * This flag indicates the presence of LP_DEAD items on the page (though
1218 * not reliably). Note that we only rely on it with pg_upgrade'd
1219 * !heapkeyspace indexes. That's why clearing it here won't usually
1220 * interfere with simple index tuple deletion.
1232 xlrec_vacuum.
ndeleted = ndeletable;
1233 xlrec_vacuum.
nupdated = nupdatable;
1257 /* can't leak memory here */
1258 if (updatedbuf != NULL)
1260 /* free tuples allocated within _bt_delitems_update() */
1261 for (
int i = 0;
i < nupdatable;
i++)
1262 pfree(updatable[
i]->itup);
1266 * Delete item(s) from a btree leaf page during single-page cleanup.
1268 * This routine assumes that the caller has pinned and write locked the
1269 * buffer. Also, the given deletable and updatable arrays *must* be sorted in
1272 * Routine deals with deleting TIDs when some (but not all) of the heap TIDs
1273 * in an existing posting list item are to be removed. This works by
1274 * updating/overwriting an existing item with caller's new version of the item
1275 * (a version that lacks the TIDs that are to be deleted).
1277 * This is nearly the same as _bt_delitems_vacuum as far as what it does to
1278 * the page, but it needs its own snapshotConflictHorizon and isCatalogRel
1279 * (from the tableam). This is used by the REDO routine to generate recovery
1280 * conflicts. The other difference is that only _bt_delitems_vacuum will
1281 * clear page's VACUUM cycle ID.
1292 char *updatedbuf = NULL;
1293 Size updatedbuflen = 0;
1296 /* Shouldn't be called unless there's something to do */
1297 Assert(ndeletable > 0 || nupdatable > 0);
1299 /* Generate new versions of posting lists without deleted TIDs */
1302 updatedoffsets, &updatedbuflen,
1305 /* No ereport(ERROR) until changes are logged */
1308 /* Handle updates and deletes just like _bt_delitems_vacuum */
1309 for (
int i = 0;
i < nupdatable;
i++)
1315 itup = updatable[
i]->
itup;
1319 elog(
PANIC,
"failed to update partially dead item in block %u of index \"%s\"",
1327 * Unlike _bt_delitems_vacuum, we *must not* clear the vacuum cycle ID at
1328 * this point. The VACUUM command alone controls vacuum cycle IDs.
1333 * Clear the BTP_HAS_GARBAGE page flag.
1335 * This flag indicates the presence of LP_DEAD items on the page (though
1336 * not reliably). Note that we only rely on it with pg_upgrade'd
1337 * !heapkeyspace indexes.
1350 xlrec_delete.
ndeleted = ndeletable;
1351 xlrec_delete.
nupdated = nupdatable;
1376 /* can't leak memory here */
1377 if (updatedbuf != NULL)
1379 /* free tuples allocated within _bt_delitems_update() */
1380 for (
int i = 0;
i < nupdatable;
i++)
1381 pfree(updatable[
i]->itup);
1385 * Set up state needed to delete TIDs from posting list tuples via "updating"
1386 * the tuple. Performs steps common to both _bt_delitems_vacuum and
1387 * _bt_delitems_delete. These steps must take place before each function's
1388 * critical section begins.
1390 * updatable and nupdatable are inputs, though note that we will use
1391 * _bt_update_posting() to replace the original itup with a pointer to a final
1392 * version in palloc()'d memory. Caller should free the tuples when its done.
1394 * The first nupdatable entries from updatedoffsets are set to the page offset
1395 * number for posting list tuples that caller updates. This is mostly useful
1396 * because caller may need to WAL-log the page offsets (though we always do
1397 * this for caller out of convenience).
1399 * Returns buffer consisting of an array of xl_btree_update structs that
1400 * describe the steps we perform here for caller (though only when needswal is
1401 * true). Also sets *updatedbuflen to the final size of the buffer. This
1402 * buffer is used by caller when WAL logging is required.
1409 char *updatedbuf = NULL;
1412 /* Shouldn't be called unless there's something to do */
1415 for (
int i = 0;
i < nupdatable;
i++)
1420 /* Replace work area IndexTuple with updated version */
1423 /* Keep track of size of xl_btree_update for updatedbuf in passing */
1427 /* Build updatedoffsets buffer in passing */
1436 /* Allocate, set final size for caller */
1437 updatedbuf =
palloc(buflen);
1438 *updatedbuflen = buflen;
1439 for (
int i = 0;
i < nupdatable;
i++)
1451 memcpy(updatedbuf + offset, vacposting->
deletetids, itemsz);
1460 * Comparator used by _bt_delitems_delete_check() to restore deltids array
1461 * back to its original leaf-page-wise sort order
1469 Assert(indexdelete1->
id != indexdelete2->
id);
1475 * Try to delete item(s) from a btree leaf page during single-page cleanup.
1477 * nbtree interface to table_index_delete_tuples(). Deletes a subset of index
1478 * tuples from caller's deltids array: those whose TIDs are found safe to
1479 * delete by the tableam (or already marked LP_DEAD in index, and so already
1480 * known to be deletable by our simple index deletion caller). We physically
1481 * delete index tuples from buf leaf page last of all (for index tuples where
1482 * that is known to be safe following our table_index_delete_tuples() call).
1484 * Simple index deletion caller only includes TIDs from index tuples marked
1485 * LP_DEAD, as well as extra TIDs it found on the same leaf page that can be
1486 * included without increasing the total number of distinct table blocks for
1487 * the deletion operation as a whole. This approach often allows us to delete
1488 * some extra index tuples that were practically free for tableam to check in
1489 * passing (when they actually turn out to be safe to delete). It probably
1490 * only makes sense for the tableam to go ahead with these extra checks when
1491 * it is block-oriented (otherwise the checks probably won't be practically
1492 * free, which we rely on). The tableam interface requires the tableam side
1493 * to handle the problem, though, so this is okay (we as an index AM are free
1494 * to make the simplifying assumption that all tableams must be block-based).
1496 * Bottom-up index deletion caller provides all the TIDs from the leaf page,
1497 * without expecting that tableam will check most of them. The tableam has
1498 * considerable discretion around which entries/blocks it checks. Our role in
1499 * costing the bottom-up deletion operation is strictly advisory.
1501 * Note: Caller must have added deltids entries (i.e. entries that go in
1502 * delstate's main array) in leaf-page-wise order: page offset number order,
1503 * TID order among entries taken from the same posting list tuple (tiebreak on
1504 * TID). This order is convenient to work with here.
1506 * Note: We also rely on the id field of each deltids element "capturing" this
1507 * original leaf-page-wise order. That is, we expect to be able to get back
1508 * to the original leaf-page-wise order just by sorting deltids on the id
1509 * field (tableam will sort deltids for its own reasons, so we'll need to put
1510 * it back in leaf-page-wise order afterwards).
1525 /* Use tableam interface to determine which tuples to delete first */
1529 /* Should not WAL-log snapshotConflictHorizon unless it's required */
1534 * Construct a leaf-page-wise description of what _bt_delitems_delete()
1535 * needs to do to physically delete index tuples from the page.
1537 * Must sort deltids array to restore leaf-page-wise order (original order
1538 * before call to tableam). This is the order that the loop expects.
1540 * Note that deltids array might be a lot smaller now. It might even have
1541 * no entries at all (with bottom-up deletion caller), in which case there
1542 * is nothing left to do.
1552 /* We definitely have to delete at least one index tuple (or one TID) */
1565 if (idxoffnum == postingidxoffnum)
1568 * This deltid entry is a TID from a posting list tuple that has
1569 * already been completely processed
1581 /* Plain non-pivot tuple */
1584 deletable[ndeletable++] = idxoffnum;
1589 * itup is a posting list tuple whose lowest deltids entry (which may
1590 * or may not be for the first TID from itup) is considered here now.
1591 * We should process all of the deltids entries for the posting list
1592 * together now, though (not just the lowest). Remember to skip over
1593 * later itup-related entries during later iterations of outermost
1596 postingidxoffnum = idxoffnum;
/* Remember work in outermost loop */
1597 nestedi =
i;
/* Initialize for first itup deltids entry */
1598 vacposting = NULL;
/* Describes final action for itup */
1600 for (
int p = 0; p < nitem; p++)
1606 * This nested loop reuses work across ptid TIDs taken from itup.
1607 * We take advantage of the fact that both itup's TIDs and deltids
1608 * entries (within a single itup/posting list grouping) must both
1609 * be in ascending TID order.
1611 for (; nestedi < delstate->
ndeltids; nestedi++)
1616 /* Stop once we get past all itup related deltids entries */
1621 /* Skip past non-deletable itup related entries up front */
1625 /* Entry is first partial ptid match (or an exact match)? */
1629 /* Greater than or equal (partial or exact) match... */
1634 /* ...exact ptid match to a deletable deltids entry? */
1638 /* Exact match for deletable deltids entry -- ptid gets deleted */
1639 if (vacposting == NULL)
1643 vacposting->
itup = itup;
1650 /* Final decision on itup, a posting list tuple */
1652 if (vacposting == NULL)
1654 /* No TIDs to delete from itup -- do nothing */
1658 /* Straight delete of itup (to delete all TIDs) */
1659 deletable[ndeletable++] = idxoffnum;
1660 /* Turns out we won't need granular information */
1665 /* Delete some (but not all) TIDs from itup */
1668 updatable[nupdatable++] = vacposting;
1672 /* Physically delete tuples (or TIDs) using deletable (or updatable) */
1674 deletable, ndeletable, updatable, nupdatable);
1677 for (
int i = 0;
i < nupdatable;
i++)
1682 * Check that leftsib page (the btpo_prev of target page) is not marked with
1683 * INCOMPLETE_SPLIT flag. Used during page deletion.
1685 * Returning true indicates that page flag is set in leftsib (which is
1686 * definitely still the left sibling of target). When that happens, the
1687 * target doesn't have a downlink in parent, and the page deletion algorithm
1688 * isn't prepared to handle that. Deletion of the target page (or the whole
1689 * subtree that contains the target page) cannot take place.
1691 * Caller should not have a lock on the target page itself, since pages on the
1692 * same level must always be locked left to right to avoid deadlocks.
1702 /* Easy case: No left sibling */
1711 * If the left sibling was concurrently split, so that its next-pointer
1712 * doesn't point to the current page anymore, the split that created
1713 * target must be completed. Caller can reasonably expect that there will
1714 * be a downlink to the target page that it can relocate using its stack.
1715 * (We don't allow splitting an incompletely split page again until the
1716 * previous split has been completed.)
1725 * Check that leafrightsib page (the btpo_next of target leaf page) is not
1726 * marked with ISHALFDEAD flag. Used during page deletion.
1728 * Returning true indicates that page flag is set in leafrightsib, so page
1729 * deletion cannot go ahead. Our caller is not prepared to deal with the case
1730 * where the parent page does not have a pivot tuples whose downlink points to
1731 * leafrightsib (due to an earlier interrupted VACUUM operation). It doesn't
1732 * seem worth going to the trouble of teaching our caller to deal with it.
1733 * The situation will be resolved after VACUUM finishes the deletion of the
1734 * half-dead page (when a future VACUUM operation reaches the target page
1737 * _bt_leftsib_splitflag() is called for both leaf pages and internal pages.
1738 * _bt_rightsib_halfdeadflag() is only called for leaf pages, though. This is
1739 * okay because of the restriction on deleting pages that are the rightmost
1740 * page of their parent (i.e. that such deletions can only take place when the
1741 * entire subtree must be deleted). The leaf level check made here will apply
1742 * to a right "cousin" leaf page rather than a simple right sibling leaf page
1743 * in cases where caller actually goes on to attempt deleting pages that are
1744 * above the leaf page. The right cousin leaf page is representative of the
1745 * left edge of the subtree to the right of the to-be-deleted subtree as a
1746 * whole, which is exactly the condition that our caller cares about.
1747 * (Besides, internal pages are never marked half-dead, so it isn't even
1748 * possible to _directly_ assess if an internal page is part of some other
1749 * to-be-deleted subtree.)
1773 * _bt_pagedel() -- Delete a leaf page from the b-tree, if legal to do so.
1775 * This action unlinks the leaf page from the b-tree structure, removing all
1776 * pointers leading to it --- but not touching its own left and right links.
1777 * The page cannot be physically reclaimed right away, since other processes
1778 * may currently be trying to follow links leading to the page; they have to
1779 * be allowed to use its right-link to recover. See nbtree/README.
1781 * On entry, the target buffer must be pinned and locked (either read or write
1782 * lock is OK). The page must be an empty leaf page, which may be half-dead
1783 * already (a half-dead page should only be passed to us when an earlier
1784 * VACUUM operation was interrupted, though). Note in particular that caller
1785 * should never pass a buffer containing an existing deleted page here. The
1786 * lock and pin on caller's buffer will be dropped before we return.
1788 * Maintains bulk delete stats for caller, which are taken from vstate. We
1789 * need to cooperate closely with caller here so that whole VACUUM operation
1790 * reliably avoids any double counting of subsidiary-to-leafbuf pages that we
1791 * delete in passing. If such pages happen to be from a block number that is
1792 * ahead of the current scanblkno position, then caller is expected to count
1793 * them directly later on. It's simpler for us to understand caller's
1794 * requirements than it would be for caller to understand when or how a
1795 * deleted page became deleted after the fact.
1797 * NOTE: this leaks memory. Rather than trying to clean up everything
1798 * carefully, it's better to run it in a temp context that can be reset
1805 bool rightsib_empty;
1810 * Save original leafbuf block number from caller. Only deleted blocks
1811 * that are <= scanblkno are added to bulk delete stat's pages_deleted
1817 * "stack" is a search stack leading (approximately) to the target page.
1818 * It is initially NULL, but when iterating, we keep it to avoid
1819 * duplicated search effort.
1821 * Also, when "stack" is not NULL, we have already checked that the
1822 * current page is not the right half of an incomplete split, i.e. the
1823 * left sibling does not have its INCOMPLETE_SPLIT flag set, including
1824 * when the current target page is to the right of caller's initial page
1825 * (the scanblkno page).
1835 * Internal pages are never deleted directly, only as part of deleting
1836 * the whole subtree all the way down to leaf level.
1838 * Also check for deleted pages here. Caller never passes us a fully
1839 * deleted page. Only VACUUM can delete pages, so there can't have
1840 * been a concurrent deletion. Assume that we reached any deleted
1841 * page encountered here by following a sibling link, and that the
1848 * Pre-9.4 page deletion only marked internal pages as half-dead,
1849 * but now we only use that flag on leaf pages. The old algorithm
1850 * was never supposed to leave half-dead pages in the tree, it was
1851 * just a transient state, but it was nevertheless possible in
1852 * error scenarios. We don't know how to deal with them here. They
1853 * are harmless as far as searches are considered, but inserts
1854 * into the deleted keyspace could add out-of-order downlinks in
1855 * the upper levels. Log a notice, hopefully the admin will notice
1860 (
errcode(ERRCODE_INDEX_CORRUPTED),
1861 errmsg(
"index \"%s\" contains a half-dead internal page",
1863 errhint(
"This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
1867 (
errcode(ERRCODE_INDEX_CORRUPTED),
1868 errmsg_internal(
"found deleted block %u while following right link from block %u in index \"%s\"",
1878 * We can never delete rightmost pages nor root pages. While at it,
1879 * check that page is empty, since it's possible that the leafbuf page
1880 * was empty a moment ago, but has since had some inserts.
1882 * To keep the algorithm simple, we also never delete an incompletely
1883 * split page (they should be rare enough that this doesn't make any
1884 * meaningful difference to disk usage):
1886 * The INCOMPLETE_SPLIT flag on the page tells us if the page is the
1887 * left half of an incomplete split, but ensuring that it's not the
1888 * right half is more complicated. For that, we have to check that
1889 * the left sibling doesn't have its INCOMPLETE_SPLIT flag set using
1890 * _bt_leftsib_splitflag(). On the first iteration, we temporarily
1891 * release the lock on scanblkno/leafbuf, check the left sibling, and
1892 * construct a search stack to scanblkno. On subsequent iterations,
1893 * we know we stepped right from a page that passed these tests, so
1900 /* Should never fail to delete a half-dead page */
1908 * First, remove downlink pointing to the page (or a parent of the
1909 * page, if we are going to delete a taller subtree), and mark the
1910 * leafbuf page half-dead
1915 * We need an approximate pointer to the page's parent page. We
1916 * use a variant of the standard search mechanism to search for
1917 * the page's high key; this will give us a link to either the
1918 * current parent or someplace to its left (if there are multiple
1919 * equal high keys, which is possible with !heapkeyspace indexes).
1921 * Also check if this is the right-half of an incomplete split
1922 * (see comment above).
1940 * To avoid deadlocks, we'd better drop the leaf page lock
1941 * before going further.
1946 * Check that the left sibling of leafbuf (if any) is not
1947 * marked with INCOMPLETE_SPLIT flag before proceeding
1949 Assert(leafblkno == scanblkno);
1957 * We need an insertion scan key, so build one.
1959 * _bt_search searches for the leaf page that contains any
1960 * matching non-pivot tuples, but we need it to "search" for
1961 * the high key pivot from the page that we're set to delete.
1962 * Compensate for the mismatch by having _bt_search locate the
1963 * last position < equal-to-untruncated-prefix non-pivots.
1967 /* Set up a BTLessStrategyNumber-like insertion scan key */
1971 /* won't need a second lock or pin on leafbuf */
1975 * Re-lock the leaf page, and start over to use our stack
1976 * within _bt_mark_page_halfdead. We must do it that way
1977 * because it's possible that leafbuf can no longer be
1978 * deleted. We need to recheck.
1980 * Note: We can't simply hold on to the sleafbuf lock instead,
1981 * because it's barely possible that sleafbuf is not the same
1982 * page as leafbuf. This happens when leafbuf split after our
1983 * original lock was dropped, but before _bt_search finished
1984 * its descent. We rely on the assumption that we'll find
1985 * leafbuf isn't safe to delete anymore in this scenario.
1986 * (Page deletion can cope with the stack being to the left of
1987 * leafbuf, but not to the right of leafbuf.)
1994 * See if it's safe to delete the leaf page, and determine how
1995 * many parent/internal pages above the leaf level will be
1996 * deleted. If it's safe then _bt_mark_page_halfdead will also
1997 * perform the first phase of deletion, which includes marking the
1998 * leafbuf page half-dead.
2010 * Then unlink it from its siblings. Each call to
2011 * _bt_unlink_halfdead_page unlinks the topmost page from the subtree,
2012 * making it shallower. Iterate until the leafbuf page is deleted.
2014 rightsib_empty =
false;
2018 /* Check for interrupts in _bt_unlink_halfdead_page */
2020 &rightsib_empty, vstate))
2023 * _bt_unlink_halfdead_page should never fail, since we
2024 * established that deletion is generally safe in
2025 * _bt_mark_page_halfdead -- index must be corrupt.
2027 * Note that _bt_unlink_halfdead_page already released the
2028 * lock and pin on leafbuf for us.
2042 * Check here, as calling loops will have locks held, preventing
2043 * interrupts from being processed.
2048 * The page has now been deleted. If its right sibling is completely
2049 * empty, it's possible that the reason we haven't deleted it earlier
2050 * is that it was the rightmost child of the parent. Now that we
2051 * removed the downlink for this page, the right sibling might now be
2052 * the only child of the parent, and could be removed. It would be
2053 * picked up by the next vacuum anyway, but might as well try to
2054 * remove it now, so loop back to process the right sibling.
2056 * Note: This relies on the assumption that _bt_getstackbuf() will be
2057 * able to reuse our original descent stack with a different child
2058 * block (provided that the child block is to the right of the
2059 * original leaf page reached by _bt_search()). It will even update
2060 * the descent stack each time we loop around, avoiding repeated work.
2062 if (!rightsib_empty)
2070 * First stage of page deletion.
2072 * Establish the height of the to-be-deleted subtree with leafbuf at its
2073 * lowest level, remove the downlink to the subtree, and mark leafbuf
2074 * half-dead. The final to-be-deleted subtree is usually just leafbuf itself,
2075 * but may include additional internal pages (at most one per level of the
2076 * tree below the root).
2078 * Caller must pass a valid heaprel, since it's just about possible that our
2079 * call to _bt_lock_subtree_parent will need to allocate a new index page to
2080 * complete a page split. Every call to _bt_allocbuf needs to pass a heaprel.
2082 * Returns 'false' if leafbuf is unsafe to delete, usually because leafbuf is
2083 * the rightmost child of its parent (and parent has more than one downlink).
2084 * Returns 'true' when the first stage of page deletion completed
2113 * Save info about the leaf page.
2119 * Before attempting to lock the parent page, check that the right sibling
2120 * is not in half-dead state. A half-dead right sibling would have no
2121 * downlink in the parent, which would be highly confusing later when we
2122 * delete the downlink. It would fail the "right sibling of target page
2123 * is also the next child in parent page" cross-check below.
2127 elog(
DEBUG1,
"could not delete page %u because its right sibling %u is half-dead",
2128 leafblkno, leafrightsib);
2133 * We cannot delete a page that is the rightmost child of its immediate
2134 * parent, unless it is the only child --- in which case the parent has to
2135 * be deleted too, and the same condition applies recursively to it. We
2136 * have to check this condition all the way up before trying to delete,
2137 * and lock the parent of the root of the to-be-deleted subtree (the
2138 * "subtree parent"). _bt_lock_subtree_parent() locks the subtree parent
2139 * for us. We remove the downlink to the "top parent" page (subtree root
2140 * page) from the subtree parent page below.
2142 * Initialize topparent to be leafbuf page now. The final to-be-deleted
2143 * subtree is often a degenerate one page subtree consisting only of the
2144 * leafbuf page. When that happens, the leafbuf page is the final subtree
2145 * root page/top parent page.
2147 topparent = leafblkno;
2148 topparentrightsib = leafrightsib;
2150 &subtreeparent, &poffset,
2151 &topparent, &topparentrightsib))
2157#ifdef USE_ASSERT_CHECKING
2160 * This is just an assertion because _bt_lock_subtree_parent should have
2161 * guaranteed tuple has the expected contents
2173 * Check that the parent-page index items we're about to delete/overwrite
2174 * in subtree parent page contain what we expect. This can fail if the
2175 * index has become corrupt for some reason. When that happens we back
2176 * out of deletion of the leafbuf subtree. (This is just like the case
2177 * where _bt_lock_subtree_parent() cannot "re-find" leafbuf's downlink.)
2182 (
errcode(ERRCODE_INDEX_CORRUPTED),
2183 errmsg_internal(
"right sibling %u of block %u is not next child %u of block %u in index \"%s\"",
2184 topparentrightsib, topparent,
2195 * Any insert which would have gone on the leaf block will now go to its
2196 * right sibling. In other words, the key space moves right.
2200 /* No ereport(ERROR) until changes are logged */
2204 * Update parent of subtree. We want to delete the downlink to the top
2205 * parent page/root of the subtree, and the *following* key. Easiest way
2206 * is to copy the right sibling's downlink over the downlink that points
2207 * to top parent page, and then delete the right sibling's original pivot
2210 * Lanin and Shasha make the key space move left when deleting a page,
2211 * whereas the key space moves right here. That's why we cannot simply
2212 * delete the pivot tuple with the downlink to the top parent page. See
2226 * Mark the leaf page as half-dead, and stamp it with a link to the top
2227 * parent page. When the leaf page is also the top parent page, the link
2228 * is set to InvalidBlockNumber.
2237 if (topparent != leafblkno)
2244 elog(
ERROR,
"could not overwrite high key in half-dead page");
2246 /* Must mark buffers dirty before XLogInsert */
2258 if (topparent != leafblkno)
2289 * Second stage of page deletion.
2291 * Unlinks a single page (in the subtree undergoing deletion) from its
2292 * siblings. Also marks the page deleted.
2294 * To get rid of the whole subtree, including the leaf page itself, call here
2295 * until the leaf page is deleted. The original "top parent" established in
2296 * the first stage of deletion is deleted in the first call here, while the
2297 * leaf page is deleted in the last call here. Note that the leaf page itself
2298 * is often the initial top parent page.
2300 * Returns 'false' if the page could not be unlinked (shouldn't happen). If
2301 * the right sibling of the current target page is empty, *rightsib_empty is
2302 * set to true, allowing caller to delete the target's right sibling page in
2303 * passing. Note that *rightsib_empty is only actually used by caller when
2304 * target page is leafbuf, following last call here for leafbuf/the subtree
2305 * containing leafbuf. (We always set *rightsib_empty for caller, just to be
2308 * Must hold pin and lock on leafbuf at entry (read or write doesn't matter).
2309 * On success exit, we'll be holding pin and write lock. On failure exit,
2310 * we'll release both pin and lock before returning (we define it that way
2311 * to avoid having to reacquire a lock we already released).
2334 bool rightsib_is_rightmost;
2345 * Remember some information about the leaf page.
2356 * Check here, as calling loops will have locks held, preventing
2357 * interrupts from being processed.
2361 /* Unlink the current top parent of the subtree */
2364 /* Target is leaf page (or leaf page is top parent, if you prefer) */
2368 leftsib = leafleftsib;
2373 /* Target is the internal page taken from leaf's top parent link */
2374 Assert(target != leafblkno);
2376 /* Fetch the block number of the target's left sibling */
2385 * To avoid deadlocks, we'd better drop the target page lock before
2392 * We have to lock the pages we need to modify in the standard order:
2393 * moving right, then up. Else we will deadlock against other writers.
2395 * So, first lock the leaf page, if it's not the target. Then find and
2396 * write-lock the current left sibling of the target page. The sibling
2397 * that was current a moment ago could have split, so we may have to move
2400 if (target != leafblkno)
2409 bool leftsibvalid =
true;
2412 * Before we follow the link from the page that was the left
2413 * sibling mere moments ago, validate its right link. This
2414 * reduces the opportunities for loop to fail to ever make any
2415 * progress in the presence of index corruption.
2417 * Note: we rely on the assumption that there can only be one
2418 * vacuum process running at a time (against the same index).
2422 leftsibvalid =
false;
2430 * This is known to fail in the field; sibling link corruption
2431 * is relatively common. Press on with vacuuming rather than
2432 * just throwing an ERROR.
2435 (
errcode(ERRCODE_INDEX_CORRUPTED),
2436 errmsg_internal(
"valid left sibling for deletion target could not be located: "
2437 "left sibling %u of target %u with leafblkno %u and scanblkno %u on level %u of index \"%s\"",
2438 leftsib, target, leafblkno, scanblkno,
2441 /* Must release all pins and locks on failure exit */
2443 if (target != leafblkno)
2451 /* step right one page */
2460 /* Next write-lock the target page itself */
2466 * Check page is still empty etc, else abandon deletion. This is just for
2467 * paranoia's sake; a half-dead page cannot resurrect because there can be
2468 * only one vacuum process running at a time.
2471 elog(
ERROR,
"target page changed status unexpectedly in block %u of index \"%s\"",
2476 (
errcode(ERRCODE_INDEX_CORRUPTED),
2477 errmsg_internal(
"target page left link unexpectedly changed from %u to %u in block %u of index \"%s\"",
2481 if (target == leafblkno)
2485 elog(
ERROR,
"target leaf page changed status unexpectedly in block %u of index \"%s\"",
2488 /* Leaf page is also target page: don't set leaftopparent */
2497 elog(
ERROR,
"target internal page on level %u changed status unexpectedly in block %u of index \"%s\"",
2500 /* Target is internal: set leaftopparent for next call here... */
2504 /* ...except when it would be a redundant pointer-to-self */
2505 if (leaftopparent == leafblkno)
2509 /* No leaftopparent for level 0 (leaf page) or level 1 target */
2513 * And next write-lock the (current) right sibling.
2521 * Validate target's right sibling page. Its left link must point back to
2527 * This is known to fail in the field; sibling link corruption is
2528 * relatively common. Press on with vacuuming rather than just
2529 * throwing an ERROR (same approach used for left-sibling's-right-link
2530 * validation check a moment ago).
2533 (
errcode(ERRCODE_INDEX_CORRUPTED),
2535 "right sibling %u of target %u with leafblkno %u "
2536 "and scanblkno %u spuriously links to non-target %u "
2537 "on level %u of index \"%s\"",
2538 rightsib, target, leafblkno,
2542 /* Must release all pins and locks on failure exit */
2547 if (target != leafblkno)
2557 * If we are deleting the next-to-last page on the target's level, then
2558 * the rightsib is a candidate to become the new fast root. (In theory, it
2559 * might be possible to push the fast root even further down, but the odds
2560 * of doing so are slim, and the locking considerations daunting.)
2562 * We can safely acquire a lock on the metapage here --- see comments for
2565 if (leftsib ==
P_NONE && rightsib_is_rightmost)
2571 /* rightsib will be the only one left on the level */
2577 * The expected case here is btm_fastlevel == targetlevel+1; if
2578 * the fastlevel is <= targetlevel, something is wrong, and we
2579 * choose to overwrite it to fix it.
2583 /* no update wanted */
2591 * Here we begin doing the deletion.
2594 /* No ereport(ERROR) until changes are logged */
2598 * Update siblings' side-links. Note the target page's side-links will
2599 * continue to point to the siblings. Asserts here are just rechecking
2600 * things we already verified above.
2615 * If we deleted a parent of the targeted leaf page, instead of the leaf
2616 * itself, update the leaf to point to the next remaining child in the
2619 * Note: We rely on the fact that a buffer pin on the leaf page has been
2620 * held since leafhikey was initialized. This is safe, though only
2621 * because the page was already half-dead at that point. The leaf page
2622 * cannot have been modified by any other backend during the period when
2625 if (target != leafblkno)
2629 * Mark the page itself deleted. It can be recycled when all current
2630 * transactions are gone. Storing GetTopTransactionId() would work, but
2631 * we're in VACUUM and would not otherwise have an XID. Having already
2632 * updated links to the target, ReadNextFullTransactionId() suffices as an
2633 * upper bound. Any scan having retained a now-stale link is advertising
2634 * in its PGPROC an xmin less than or equal to the value we read here. It
2635 * will continue to do so, holding back the xmin horizon, for the duration
2643 * Store upper bound XID that's used to determine when deleted page is no
2644 * longer needed as a tombstone
2650 /* And update the metapage, if needed */
2653 /* upgrade metapage if needed */
2661 /* Must mark buffers dirty before XLogInsert */
2666 if (target != leafblkno)
2683 if (target != leafblkno)
2686 /* information stored on the target/to-be-unlinked block */
2689 xlrec.
level = targetlevel;
2692 /* information needed to recreate the leaf block (if not the target) */
2733 if (target != leafblkno)
2742 /* release metapage */
2746 /* release siblings */
2751 /* If the target is not leafbuf, we're done with it now -- release it */
2752 if (target != leafblkno)
2756 * Maintain pages_newly_deleted, which is simply the number of pages
2757 * deleted by the ongoing VACUUM operation.
2759 * Maintain pages_deleted in a way that takes into account how
2760 * btvacuumpage() will count deleted pages that have yet to become
2761 * scanblkno -- only count page when it's not going to get that treatment
2765 if (target <= scanblkno)
2769 * Remember information about the target page (now a newly deleted page)
2770 * in dedicated vstate space for later. The page will be considered as a
2771 * candidate to place in the FSM at the end of the current btvacuumscan()
2776 /* Success - hold on to lock on leafbuf (might also have been target) */
2781 * Establish how tall the to-be-deleted subtree will be during the first stage
2784 * Caller's child argument is the block number of the page caller wants to
2785 * delete (this is leafbuf's block number, except when we're called
2786 * recursively). stack is a search stack leading to it. Note that we will
2787 * update the stack entry(s) to reflect current downlink positions --- this is
2788 * similar to the corresponding point in page split handling.
2790 * If "first stage" caller cannot go ahead with deleting _any_ pages, returns
2791 * false. Returns true on success, in which case caller can use certain
2792 * details established here to perform the first stage of deletion. This
2793 * function is the last point at which page deletion may be deemed unsafe
2794 * (barring index corruption, or unexpected concurrent page deletions).
2796 * We write lock the parent of the root of the to-be-deleted subtree for
2797 * caller on success (i.e. we leave our lock on the *subtreeparent buffer for
2798 * caller). Caller will have to remove a downlink from *subtreeparent. We
2799 * also set a *subtreeparent offset number in *poffset, to indicate the
2800 * location of the pivot tuple that contains the relevant downlink.
2802 * The root of the to-be-deleted subtree is called the "top parent". Note
2803 * that the leafbuf page is often the final "top parent" page (you can think
2804 * of the leafbuf page as a degenerate single page subtree when that happens).
2805 * Caller should initialize *topparent to the target leafbuf page block number
2806 * (while *topparentrightsib should be set to leafbuf's right sibling block
2807 * number). We will update *topparent (and *topparentrightsib) for caller
2808 * here, though only when it turns out that caller will delete at least one
2809 * internal page (i.e. only when caller needs to store a valid link to the top
2810 * parent block in the leafbuf page using BTreeTupleSetTopParent()).
2827 * Locate the pivot tuple whose downlink points to "child". Write lock
2828 * the parent page itself.
2834 * Failed to "re-find" a pivot tuple whose downlink matched our child
2835 * block number on the parent level -- the index must be corrupt.
2836 * Don't even try to delete the leafbuf subtree. Just report the
2837 * issue and press on with vacuuming the index.
2839 * Note: _bt_getstackbuf() recovers from concurrent page splits that
2840 * take place on the parent level. Its approach is a near-exhaustive
2841 * linear search. This also gives it a surprisingly good chance of
2842 * recovering in the event of a buggy or inconsistent opclass. But we
2843 * don't rely on that here.
2846 (
errcode(ERRCODE_INDEX_CORRUPTED),
2847 errmsg_internal(
"failed to re-find parent key in index \"%s\" for deletion target page %u",
2862 * _bt_getstackbuf() completes page splits on returned parent buffer when
2865 * In general it's a bad idea for VACUUM to use up more disk space, which
2866 * is why page deletion does not finish incomplete page splits most of the
2867 * time. We allow this limited exception because the risk is much lower,
2868 * and the potential downside of not proceeding is much higher: A single
2869 * internal page with the INCOMPLETE_SPLIT flag set might otherwise
2870 * prevent us from deleting hundreds of empty leaf pages from one level
2875 if (parentoffset < maxoff)
2878 * Child is not the rightmost child in parent, so it's safe to delete
2879 * the subtree whose root/topparent is child page
2881 *subtreeparent = pbuf;
2882 *poffset = parentoffset;
2887 * Child is the rightmost child of parent.
2889 * Since it's the rightmost child of parent, deleting the child (or
2890 * deleting the subtree whose root/topparent is the child page) is only
2891 * safe when it's also possible to delete the parent.
2893 Assert(parentoffset == maxoff);
2897 * Child isn't parent's only child, or parent is rightmost on its
2898 * entire level. Definitely cannot delete any pages.
2905 * Now make sure that the parent deletion is itself safe by examining the
2906 * child's grandparent page. Recurse, passing the parent page as the
2907 * child page (child's grandparent is the parent on the next level up). If
2908 * parent deletion is unsafe, then child deletion must also be unsafe (in
2909 * which case caller cannot delete any pages at all).
2911 *topparent = parent;
2915 * Release lock on parent before recursing.
2917 * It's OK to release page locks on parent before recursive call locks
2918 * grandparent. An internal page can only acquire an entry if the child
2919 * is split, but that cannot happen as long as we still hold a lock on the
2925 * Before recursing, check that the left sibling of parent (if any) is not
2926 * marked with INCOMPLETE_SPLIT flag first (must do so after we drop the
2929 * Note: We deliberately avoid completing incomplete splits here.
2934 /* Recurse to examine child page's grandparent page */
2936 subtreeparent, poffset,
2937 topparent, topparentrightsib);
2941 * Initialize local memory state used by VACUUM for _bt_pendingfsm_finalize
2944 * Called at the start of a btvacuumscan(). Caller's cleanuponly argument
2945 * indicates if ongoing VACUUM has not (and will not) call btbulkdelete().
2947 * We expect to allocate memory inside VACUUM's top-level memory context here.
2948 * The working buffer is subject to a limit based on work_mem. Our strategy
2949 * when the array can no longer grow within the bounds of that limit is to
2950 * stop saving additional newly deleted pages, while proceeding as usual with
2951 * the pages that we can fit.
2959 * Don't bother with optimization in cleanup-only case -- we don't expect
2960 * any newly deleted pages. Besides, cleanup-only calls to btvacuumscan()
2961 * can only take place because this optimization didn't work out during
2968 * Cap maximum size of array so that we always respect work_mem. Avoid
2969 * int overflow here.
2974 /* BTVacState.maxbufsize has type int */
2975 maxbufsize =
Min(maxbufsize, INT_MAX);
2976 /* Stay sane with small work_mem */
2977 maxbufsize =
Max(maxbufsize, vstate->
bufsize);
2980 /* Allocate buffer, indicate that there are currently 0 pending pages */
2986 * Place any newly deleted pages (i.e. pages that _bt_pagedel() deleted during
2987 * the ongoing VACUUM operation) into the free space map -- though only when
2988 * it is actually safe to do so by now.
2990 * Called at the end of a btvacuumscan(), just before free space map vacuuming
2993 * Frees memory allocated by _bt_pendingfsm_init(), if any.
3006 /* Just free memory when nothing to do */
3013#ifdef DEBUG_BTREE_PENDING_FSM
3016 * Debugging aid: Sleep for 5 seconds to greatly increase the chances of
3017 * placing pending pages in the FSM. Note that the optimization will
3018 * never be effective without some other backend concurrently consuming an
3025 * Recompute VACUUM XID boundaries.
3027 * We don't actually care about the oldest non-removable XID. Computing
3028 * the oldest such XID has a useful side-effect that we rely on: it
3029 * forcibly updates the XID horizon state for this backend. This step is
3030 * essential; GlobalVisCheckRemovableFullXid() will not reliably recognize
3031 * that it is now safe to recycle newly deleted pages without this step.
3041 * Do the equivalent of checking BTPageIsRecyclable(), but without
3042 * accessing the page again a second time.
3044 * Give up on finding the first non-recyclable page -- all later pages
3045 * must be non-recyclable too, since _bt_pendingfsm_add() adds pages
3046 * to the array in safexid order.
3059 * Maintain array of pages that were deleted during current btvacuumscan()
3060 * call, for use in _bt_pendingfsm_finalize()
3070#ifdef USE_ASSERT_CHECKING
3073 * Verify an assumption made by _bt_pendingfsm_finalize(): pages from the
3074 * array will always be in safexid order (since that is the order that we
3075 * save them in here)
3087 * If temp buffer reaches maxbufsize/work_mem capacity then we discard
3088 * information about this page.
3090 * Note that this also covers the case where we opted to not use the
3091 * optimization in _bt_pendingfsm_init().
3096 /* Consider enlarging buffer */
3099 int newbufsize = vstate->
bufsize * 2;
3101 /* Respect work_mem */
3111 /* Save metadata for newly deleted page */
#define InvalidBlockNumber
static bool BlockNumberIsValid(BlockNumber blockNumber)
BlockNumber BufferGetBlockNumber(Buffer buffer)
Buffer ReleaseAndReadBuffer(Buffer buffer, Relation relation, BlockNumber blockNum)
Buffer ExtendBufferedRel(BufferManagerRelation bmr, ForkNumber forkNum, BufferAccessStrategy strategy, uint32 flags)
bool ConditionalLockBuffer(Buffer buffer)
void ReleaseBuffer(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void LockBufferForCleanup(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
#define BUFFER_LOCK_UNLOCK
#define RelationGetNumberOfBlocks(reln)
static Page BufferGetPage(Buffer buffer)
static Size BufferGetPageSize(Buffer buffer)
static bool BufferIsValid(Buffer bufnum)
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, Item newtup, Size newsize)
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
void PageInit(Page page, Size pageSize, Size specialSize)
PageHeaderData * PageHeader
static uint16 PageGetSpecialSize(const PageData *page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
static bool PageIsNew(const PageData *page)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
#define PG_USED_FOR_ASSERTS_ONLY
#define MemSet(start, val, len)
int errmsg_internal(const char *fmt,...)
int errhint(const char *fmt,...)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
Assert(PointerIsAligned(start, uint64))
BlockNumber GetFreeIndexPage(Relation rel)
void RecordFreeIndexPage(Relation rel, BlockNumber freeBlock)
IndexTuple CopyIndexTuple(IndexTuple source)
static int pg_cmp_s16(int16 a, int16 b)
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
IndexTupleData * IndexTuple
struct IndexTupleData IndexTupleData
static Size IndexTupleSize(const IndexTupleData *itup)
#define MaxIndexTuplesPerPage
void * MemoryContextAlloc(MemoryContext context, Size size)
void * repalloc(void *pointer, Size size)
void pfree(void *pointer)
#define VALGRIND_MAKE_MEM_DEFINED(addr, size)
#define VALGRIND_CHECK_MEM_IS_DEFINED(addr, size)
#define VALGRIND_MAKE_MEM_NOACCESS(addr, size)
#define START_CRIT_SECTION()
#define CHECK_FOR_INTERRUPTS()
#define END_CRIT_SECTION()
void _bt_update_posting(BTVacuumPosting vacposting)
Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child)
Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
static bool _bt_lock_subtree_parent(Relation rel, Relation heaprel, BlockNumber child, BTStack stack, Buffer *subtreeparent, OffsetNumber *poffset, BlockNumber *topparent, BlockNumber *topparentrightsib)
void _bt_upgrademetapage(Page page)
void _bt_relbuf(Relation rel, Buffer buf)
Buffer _bt_gettrueroot(Relation rel)
int _bt_getrootheight(Relation rel)
void _bt_pageinit(Page page, Size size)
static bool _bt_rightsib_halfdeadflag(Relation rel, BlockNumber leafrightsib)
void _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate)
Buffer _bt_allocbuf(Relation rel, Relation heaprel)
void _bt_delitems_vacuum(Relation rel, Buffer buf, OffsetNumber *deletable, int ndeletable, BTVacuumPosting *updatable, int nupdatable)
static bool _bt_leftsib_splitflag(Relation rel, BlockNumber leftsib, BlockNumber target)
void _bt_checkpage(Relation rel, Buffer buf)
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
static BTMetaPageData * _bt_getmeta(Relation rel, Buffer metabuf)
static void _bt_delitems_delete(Relation rel, Buffer buf, TransactionId snapshotConflictHorizon, bool isCatalogRel, OffsetNumber *deletable, int ndeletable, BTVacuumPosting *updatable, int nupdatable)
void _bt_set_cleanup_info(Relation rel, BlockNumber num_delpages)
static bool _bt_mark_page_halfdead(Relation rel, Relation heaprel, Buffer leafbuf, BTStack stack)
bool _bt_conditionallockbuf(Relation rel, Buffer buf)
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
void _bt_unlockbuf(Relation rel, Buffer buf)
void _bt_upgradelockbufcleanup(Relation rel, Buffer buf)
void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level, bool allequalimage)
void _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel, TM_IndexDeleteOp *delstate)
bool _bt_vacuum_needs_cleanup(Relation rel)
static char * _bt_delitems_update(BTVacuumPosting *updatable, int nupdatable, OffsetNumber *updatedoffsets, Size *updatedbuflen, bool needswal)
static int _bt_delitems_cmp(const void *a, const void *b)
void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate)
void _bt_lockbuf(Relation rel, Buffer buf, int access)
Buffer _bt_getroot(Relation rel, Relation heaprel, int access)
void _bt_pendingfsm_init(Relation rel, BTVacState *vstate, bool cleanuponly)
static void _bt_pendingfsm_add(BTVacState *vstate, BlockNumber target, FullTransactionId safexid)
static bool _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf, BlockNumber scanblkno, bool *rightsib_empty, BTVacState *vstate)
#define P_ISHALFDEAD(opaque)
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
static FullTransactionId BTPageGetDeleteXid(Page page)
#define BTREE_MIN_VERSION
static void BTreeTupleSetTopParent(IndexTuple leafhikey, BlockNumber blkno)
#define P_LEFTMOST(opaque)
#define BTPageGetOpaque(page)
#define P_ISDELETED(opaque)
static BlockNumber BTreeTupleGetTopParent(IndexTuple leafhikey)
struct BTPendingFSM BTPendingFSM
static void BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
#define P_FIRSTDATAKEY(opaque)
#define P_RIGHTMOST(opaque)
#define P_INCOMPLETE_SPLIT(opaque)
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
static bool BTPageIsRecyclable(Page page, Relation heaprel)
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
static bool BTreeTupleIsPosting(IndexTuple itup)
static void BTPageSetDeleted(Page page, FullTransactionId safexid)
#define BTREE_NOVAC_VERSION
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
#define SizeOfBtreeVacuum
#define XLOG_BTREE_META_CLEANUP
#define SizeOfBtreeUpdate
#define XLOG_BTREE_VACUUM
#define SizeOfBtreeDelete
#define SizeOfBtreeMarkPageHalfDead
#define XLOG_BTREE_UNLINK_PAGE
#define XLOG_BTREE_UNLINK_PAGE_META
#define SizeOfBtreeNewroot
#define XLOG_BTREE_MARK_PAGE_HALFDEAD
#define XLOG_BTREE_REUSE_PAGE
#define SizeOfBtreeUnlinkPage
#define SizeOfBtreeReusePage
#define XLOG_BTREE_NEWROOT
#define XLOG_BTREE_DELETE
#define InvalidOffsetNumber
#define OffsetNumberIsValid(offsetNumber)
#define OffsetNumberNext(offsetNumber)
#define qsort(a, b, c, d)
void PredicateLockPageCombine(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
TransactionId GetOldestNonRemovableTransactionId(Relation rel)
bool GlobalVisCheckRemovableFullXid(Relation rel, FullTransactionId fxid)
#define RelationGetRelationName(relation)
#define RelationIsAccessibleInLogicalDecoding(relation)
#define RelationNeedsWAL(relation)
#define RelationUsesLocalBuffers(relation)
void pg_usleep(long microsec)
uint32 btm_last_cleanup_num_delpages
float8 btm_last_cleanup_num_heap_tuples
FullTransactionId safexid
struct BTStackData * bts_parent
IndexBulkDeleteResult * stats
BTPendingFSM * pendingpages
uint16 deletetids[FLEXIBLE_ARRAY_MEMBER]
OffsetNumber updatedoffset
BlockNumber pages_deleted
BlockNumber pages_newly_deleted
MemoryContext rd_indexcxt
RelFileLocator rd_locator
TransactionId snapshotConflictHorizon
FullTransactionId snapshotConflictHorizon
FullTransactionId safexid
BlockNumber leaftopparent
static TransactionId table_index_delete_tuples(Relation rel, TM_IndexDeleteOp *delstate)
#define InvalidTransactionId
#define FullTransactionIdFollowsOrEquals(a, b)
FullTransactionId ReadNextFullTransactionId(void)
#define XLogStandbyInfoActive()
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
void XLogRegisterBufData(uint8 block_id, const void *data, uint32 len)
void XLogRegisterData(const void *data, uint32 len)
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
void XLogBeginInsert(void)