Hi Michail, Thanks for the review and the test case. The attached patches fix the insert issue, and the value 381 now is inserted correctly. I also added your suggested fix for _bt_readfirstpage in addition to other fixes.
Anyone testing this can apply these patches alongside the injection points patch from Michail's email to verify the insert case. We are still working on WAL. Any further reviews or feedback are always appreciated. Best regards, Salma El-Sayed On Mon, Aug 10, 2026 at 12:57 PM Михаил Сироткин <[email protected]> wrote: > > Hello Hackers, > > I was looking at the latest version of the btree merge patch and found > that inserting into an index might not work correctly. > > To reproduce it, you will need to apply the patches from Salma and > then apply the attached patch. Configure PostgreSQL with injection points > enabled, > and install the pageinspect and injection_points extensions. > > Session 1: > CREATE EXTENSION pageinspect; > CREATE EXTENSION injection_points; > CREATE TABLE merge_test (id int); > ALTER TABLE merge_test SET (autovacuum_enabled = false); > INSERT INTO merge_test SELECT i FROM generate_series(1, 10000) i; > CREATE INDEX merge_test_idx ON merge_test(id); > DELETE FROM merge_test WHERE id % 20 != 0; > VACUUM merge_test; > > Session 2: > SELECT injection_points_attach('before_leaf_level', 'wait'); > > Session 3: > INSERT INTO merge_test VALUES (381); > > Session 1: > SELECT * FROM bt_merge('merge_test_idx', 10.0, 90.0, 10); > > Session 2: > SELECT injection_points_wakeup('before_leaf_level'); > SELECT injection_points_detach('before_leaf_level'); > > Session 1: > SET enable_seqscan = false; > SELECT * FROM merge_test WHERE id = 381; > > After this, you will see that you cannot find the row with id = 381 in the > merge_test > table (session 1). I think that the index tuple has landed on a page with the > BTP_MERGED_AWAY flag. > > I also think that you need to set mergedAwayBlkno inside _bt_readfirstpage to > really skip merge > recovery, because inside _bt_readnextpage, in a forward scan, you check > mergedAwayBlkno, > not skipMergeRecovery. > > Best regards, > Michail Sirotkin > > ср, 5 авг. 2026 г. в 01:01, Salma El-Sayed <[email protected]>: >> >> Hello Hackers, >> >> We want to share a v1 proof-of-concept patch series for B-tree leaf page >> merging (3 patches attached). As we mentioned in our previous email >> regarding the new design [1], we have completely gotten rid of the ghost >> records in the left page. >> >> I also attached a pdf (B-tree Page Merge PoC design.pdf) that puts all the >> design details from this email and our previous one [1] into one place. >> >> 1.) The design is based on the following foundational principles: >> >> a. We only merge two adjacent pages that share the same parent. >> >> b. We need to keep the MA blkno saved in every M page to overcome the >> race condition concern Matthias raised in his email [2]. We used >> pd_prune_xid in the page header to store the MA blkno, as the comments state >> it is "currently unused in index pages." This MA blkno serves as the group >> identity. >> >> c. When an M page splits, it inherits both the M flag and the MA blkno. >> Therefore, in any merge group with multiple M pages, all M pages (except the >> first one) result from M page splits. >> >> d. The merged group must be contiguous (MA <--> M <--> M), meaning no >> normal page (neither an MA nor an M page) can exist between an MA and an M >> page from the same group. M pages can be deleted at any time; deleted or HD >> (Half-Dead) pages in between do not break the group. >> >> e. currPos.items in BTScanOpaqueData still retains the data of the last >> read page. >> >> f. We save a safemergexid in the MA page, ensuring VACUUM only clears >> the flags after the XID horizon has passed. >> >> 2.) Besides the design details in [1], we have added a VACUUM cleanup >> process for the merge group. To keep point 1.d always valid, VACUUM must >> clean the group starting from the rightmost M page (the tail of the group) >> and move backward. >> >> When VACUUM encounters an MA page, it will: >> >> a. Unlock the page and only keep a pin on it, allowing it to walk >> forward and backward without causing deadlocks or violating lock ordering. >> No index scan will change this MA page, only one VACUUM can run at a time, >> and the MA block cannot split. Because of this, the MA page remains >> unchanged after we drop the lock. >> >> b. Walk forward to reach the end of the group (the tail M page). During >> this walk, VACUUM doesn't clean anything; it only locates the tail to begin >> cleaning from there. >> >> c. Walk backward, starting from the tail, to clear both the M flag and >> the saved MA blkno in each page until it reaches the MA page. Because these >> pages will either be reached again by VACUUM or have already been cleaned >> prior to this visit, we do not need to clean these pages entirely, they will >> be cleaned eventually anyway. >> >> d. On the MA page, clear the MA flag and transition the page to HD. We >> then let the standard VACUUM handle the rest of the deletion process from >> there. >> >> 3.) Open Question Regarding High Keys on MA Pages: When marking a page as >> MA, completely emptying the page and saving the safemergexid may cause >> crashes for concurrent searches that expect to find a high key. >> One solution is to add MA pages to the P_IGNORE flag so searches skip them. >> However, we want to avoid this because an MA page ("keyspace moved") has >> different semantics than a Half-Dead page ("page empty"). Adding it to >> P_IGNORE would require a massive and invasive audit of every P_IGNORE check >> in the codebase. >> >> Instead, we are considering keeping the old high key on the MA tombstone >> page and only deleting the data tuples. This cleanly fixes the concurrent >> search issue and also simplifies our VACUUM cleanup phase. >> >> However, we have a concern regarding the lifespan of this high key: is it >> safe to leave this "old" high key residing on the tombstone page during >> concurrent scans until VACUUM eventually marks it as Half-Dead? >> >> --- >> * A test script covering the basic merge, split on a merged page, and scan >> recovery with injection points is available at [3]. The injection points are >> included in the patch and fire only for the "merge_test_idx" index by name. >> >> * Note: WAL, parallel scan handling, and handling scans that change >> direction have not been implemented yet, but they are next on our list. >> >> Additionally, my mentors Kirk and Nikolay created a visualizer that >> illustrates the merge process very clearly [4]. >> >> [1] >> https://www.postgresql.org/message-id/CANBEAPFnx4eTOjNWnmtzoEYkZimSYC-7A2ouk76VcpzcfTrtNA%40mail.gmail.com >> [2] >> https://www.postgresql.org/message-id/CAEze2Wi9pfMG7n-CsPT0XuC5n6Qi%3D6b1PvQA_vSLpPTWE3kQcg%40mail.gmail.com >> [3] >> https://github.com/salmaaliia/postgres-btree-merge-tests/blob/main/first-patch-test-script.md >> [4] https://kirkw.github.io/explainers/btree-merge-explainer.html >> >> Best regards, >> Salma El-Sayed >>
From ba31c063d8036bac4ee431579842f8ca61c27f40 Mon Sep 17 00:00:00 2001 From: Salma <[email protected]> Date: Wed, 29 Jul 2026 00:09:51 +0300 Subject: [PATCH v2 2/3] pageinspect: Add support for B-tree page merges Extend pageinspect to display information about BTP_MERGED and BTP_MERGED_AWAY leaf pages in bt_page_stats() and bt_page_items(). Add new inspection functions: bt_find_merge_candidates() to locate mergeable leaf page pairs, bt_merge_detail() to inspect parent and sibling page states, and bt_merge() to trigger leaf page merges from SQL. --- contrib/pageinspect/btreefuncs.c | 800 +++++++++++++++++- .../pageinspect/pageinspect--1.12--1.13.sql | 63 ++ 2 files changed, 857 insertions(+), 6 deletions(-) diff --git a/contrib/pageinspect/btreefuncs.c b/contrib/pageinspect/btreefuncs.c index 3381e7cc2a7..b096bf44f78 100644 --- a/contrib/pageinspect/btreefuncs.c +++ b/contrib/pageinspect/btreefuncs.c @@ -36,6 +36,9 @@ #include "funcapi.h" #include "miscadmin.h" #include "pageinspect.h" +#include "storage/block.h" +#include "storage/buf.h" +#include "storage/bufmgr.h" #include "utils/array.h" #include "utils/builtins.h" #include "utils/rel.h" @@ -48,10 +51,18 @@ PG_FUNCTION_INFO_V1(bt_page_items_bytea); PG_FUNCTION_INFO_V1(bt_page_stats_1_9); PG_FUNCTION_INFO_V1(bt_page_stats); PG_FUNCTION_INFO_V1(bt_multi_page_stats); +PG_FUNCTION_INFO_V1(bt_find_merge_candidates); +PG_FUNCTION_INFO_V1(bt_merge_detail); +PG_FUNCTION_INFO_V1(bt_merge); #define IS_INDEX(r) ((r)->rd_rel->relkind == RELKIND_INDEX) #define IS_BTREE(r) ((r)->rd_rel->relam == BTREE_AM_OID) +#define BTREE_MERGE_THRESHOLD 0.20 /* page must be ≤20% full to be a + * candidate */ +#define BTREE_TARGET_FILLFACTOR 0.90 /* merged result must stay ≤90% full */ + + /* ------------------------------------------------ * structure for single btree page statistics * ------------------------------------------------ @@ -98,6 +109,35 @@ typedef struct ua_page_items TupleDesc tupd; } ua_page_items; +/** + * cross-call data structure for SRF for merge candidates + */ +typedef struct ua_merge_candidates +{ + Oid relid; + BlockNumber current_blkno; + TupleDesc tupd; + float8 merge_candidate_max_pct; + float8 merge_destination_max_pct; + int num_pages; + int returned; + +} ua_merge_candidates; + +/* + * State for bt_merge_detail(): holds the three block numbers of the + * Parent / Left / Right page trio across SRF calls. + */ +typedef struct ua_merge_detail +{ + Oid relid; + BlockNumber parent_blkno; + BlockNumber left_blkno; + BlockNumber right_blkno; + int call_cntr; /* 0=parent, 1=left, 2=right */ + bool show_tids; + TupleDesc tupd; +} ua_merge_detail; /* ------------------------------------------------- * GetBTPageStatistics() @@ -156,6 +196,12 @@ GetBTPageStatistics(BlockNumber blkno, Buffer buffer, BTPageStat *stat) } else if (P_IGNORE(opaque)) stat->type = 'e'; + else if (P_ISMERGEDAWAY(opaque)) + { + stat->type = 'm'; + /* Don't interpret BTMergedAwayPageData as index tuples */ + maxoff = InvalidOffsetNumber; + } else if (P_ISLEAF(opaque)) stat->type = 'l'; else if (P_ISROOT(opaque)) @@ -672,12 +718,18 @@ bt_page_items_internal(PG_FUNCTION_ARGS, enum pageinspect_version ext_version) opaque = BTPageGetOpaque(uargs->page); - if (!P_ISDELETED(opaque)) + if (!P_ISDELETED(opaque) && !P_ISMERGEDAWAY(opaque)) fctx->max_calls = PageGetMaxOffsetNumber(uargs->page); else { - /* Don't interpret BTDeletedPageData as index tuples */ - elog(NOTICE, "page from block " INT64_FORMAT " is deleted", blkno); + /* + * Don't interpret BTDeletedPageData or BTMergedAwayPageData as + * index tuples + */ + if (P_ISDELETED(opaque)) + elog(NOTICE, "page from block " INT64_FORMAT " is deleted", blkno); + else + elog(NOTICE, "page from block " INT64_FORMAT " is merged away", blkno); fctx->max_calls = 0; } uargs->leafpage = P_ISLEAF(opaque); @@ -787,13 +839,21 @@ bt_page_items_bytea(PG_FUNCTION_ARGS) if (P_ISDELETED(opaque)) elog(NOTICE, "page is deleted"); + else if (P_ISMERGEDAWAY(opaque)) + elog(NOTICE, "page is merged away"); - if (!P_ISDELETED(opaque)) + if (!P_ISDELETED(opaque) && !P_ISMERGEDAWAY(opaque)) fctx->max_calls = PageGetMaxOffsetNumber(uargs->page); else { - /* Don't interpret BTDeletedPageData as index tuples */ - elog(NOTICE, "page from block is deleted"); + /* + * Don't interpret BTDeletedPageData or BTMergedAwayPageData as + * index tuples + */ + if (P_ISDELETED(opaque)) + elog(NOTICE, "page from block is deleted"); + else + elog(NOTICE, "page from block is merged away"); fctx->max_calls = 0; } uargs->leafpage = P_ISLEAF(opaque); @@ -935,3 +995,731 @@ bt_metap(PG_FUNCTION_ARGS) PG_RETURN_DATUM(result); } + + +/*------------------------------------------------------- + * bt_find_merge_candidates() + * + * Scan the B-tree leaf chain left-to-right and return up to num_pages + * LEFT block numbers of adjacent leaf pairs where both pages are at most + * min_pct_threshold percent full and their combined content fits within + * the target fillfactor. Only merge candidates are returned. + * + * Usage: SELECT * FROM bt_find_merge_candidates('t1_pkey', 50.0, 5); + *------------------------------------------------------- + */ +Datum +bt_find_merge_candidates(PG_FUNCTION_ARGS) +{ + text *relname = PG_GETARG_TEXT_PP(0); + float8 merge_candidate_max_pct = PG_GETARG_FLOAT8(1); + float8 merge_destination_max_pct = PG_GETARG_FLOAT8(2); + int32 num_pages = PG_GETARG_INT32(3); + Datum result; + FuncCallContext *fctx; + MemoryContext mctx; + ua_merge_candidates *uargs; + Buffer left_buf, + right_buf; + Page left_page, + right_page; + BTPageOpaque left_opaque, + right_opaque; + BlockNumber left_blkno, + right_blkno; + Size left_free, + right_free; + Size left_used, + right_used; + BTScanInsert scankey; + int j; + Datum values[5]; + bool nulls[5]; + HeapTuple tuple; + + if (!superuser()) + ereport(ERROR, + (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), + errmsg("must be superuser to use pageinspect functions"))); + + if (SRF_IS_FIRSTCALL()) + { + RangeVar *relrv; + Relation rel; + TupleDesc tupleDesc; + + fctx = SRF_FIRSTCALL_INIT(); + + relrv = makeRangeVarFromNameList(textToQualifiedNameList(relname)); + rel = relation_openrv(relrv, AccessShareLock); + + if (!IS_INDEX(rel) || !IS_BTREE(rel)) + ereport(ERROR, (errcode(ERRCODE_WRONG_OBJECT_TYPE), + errmsg("\"%s\" is not a %s index", + RelationGetRelationName(rel), "btree"))); + + mctx = MemoryContextSwitchTo(fctx->multi_call_memory_ctx); + uargs = palloc_object(ua_merge_candidates); + + /* + * Start at the second leftmost leaf page. + */ + { + Buffer endpoint_buf = _bt_get_endpoint(rel, 0, false); + Page temp_page = BufferGetPage(endpoint_buf); + BTPageOpaque temp_opaque = BTPageGetOpaque(temp_page); + + uargs->current_blkno = temp_opaque->btpo_next; + /* elog(WARNING, "Hello from bt_find_merge_candidates"); */ + UnlockReleaseBuffer(endpoint_buf); + } + + uargs->relid = RelationGetRelid(rel); + relation_close(rel, AccessShareLock); + + uargs->merge_candidate_max_pct = merge_candidate_max_pct / 100.0; + uargs->merge_destination_max_pct = merge_destination_max_pct / 100.0; + uargs->num_pages = num_pages; + uargs->returned = 0; + + /* Build a tuple descriptor for our result type */ + if (get_call_result_type(fcinfo, NULL, &tupleDesc) != TYPEFUNC_COMPOSITE) + elog(ERROR, "return type must be a row type"); + tupleDesc = BlessTupleDesc(tupleDesc); + + uargs->tupd = tupleDesc; + fctx->user_fctx = uargs; + + MemoryContextSwitchTo(mctx); + } + + fctx = SRF_PERCALL_SETUP(); + uargs = fctx->user_fctx; + + if (uargs->returned >= uargs->num_pages) + SRF_RETURN_DONE(fctx); + + /* + * Reopen the relation for this call. We open and close it every call so + * that a LIMIT early exit cannot leak a relcache reference. + */ + { + Relation rel = relation_open(uargs->relid, AccessShareLock); + + /* + * Walk the leaf chain looking for the next merge candidate. We skip + * non-candidates and stop at the rightmost leaf or end of chain. + */ + for (;;) + { + CHECK_FOR_INTERRUPTS(); + + if (uargs->current_blkno == P_NONE) + { + relation_close(rel, AccessShareLock); + SRF_RETURN_DONE(fctx); + } + + left_blkno = uargs->current_blkno; + left_buf = ReadBuffer(rel, left_blkno); + LockBuffer(left_buf, BUFFER_LOCK_SHARE); + left_page = BufferGetPage(left_buf); + left_opaque = BTPageGetOpaque(left_page); + + if (P_RIGHTMOST(left_opaque)) + { + UnlockReleaseBuffer(left_buf); + relation_close(rel, AccessShareLock); + SRF_RETURN_DONE(fctx); + } + + /* Skip deleted, half-dead, and already-merged pages. */ + if (P_ISDELETED(left_opaque) || P_ISHALFDEAD(left_opaque) + || P_ISMERGED(left_opaque) || P_ISMERGEDAWAY(left_opaque)) + { + uargs->current_blkno = left_opaque->btpo_next; + UnlockReleaseBuffer(left_buf); + continue; + } + + Assert(P_ISLEAF(left_opaque)); + + /* Lock couple: acquire right BEFORE releasing left */ + right_blkno = left_opaque->btpo_next; + left_free = PageGetFreeSpace(left_page); + right_buf = ReadBuffer(rel, right_blkno); + LockBuffer(right_buf, BUFFER_LOCK_SHARE); + right_page = BufferGetPage(right_buf); + right_opaque = BTPageGetOpaque(right_page); + right_free = PageGetFreeSpace(right_page); + + /* R is unusable; skip directly past it using its btpo_next. */ + if (P_ISDELETED(right_opaque) || P_ISHALFDEAD(right_opaque) + || P_ISMERGED(right_opaque) || P_ISMERGEDAWAY(right_opaque)) + { + uargs->current_blkno = right_opaque->btpo_next; + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + continue; + } + + Assert(P_ISLEAF(right_opaque)); + + scankey = NULL; + { + OffsetNumber first_data_off = P_FIRSTDATAKEY(left_opaque); + + if (first_data_off <= PageGetMaxOffsetNumber(left_page)) + { + IndexTuple first_itup = (IndexTuple) PageGetItem(left_page, + PageGetItemId(left_page, first_data_off)); + + scankey = _bt_mkscankey(rel, first_itup); + } + } + + /* L is examined; slide the window to R as the default next-left. */ + uargs->current_blkno = right_blkno; + + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + + left_used = BLCKSZ - left_free; + right_used = BLCKSZ - right_free; + + /* + * Size check: both pages must individually be below the threshold + * AND their combined content must fit within the target + * fillfactor. + */ + if ((float) left_used / BLCKSZ <= uargs->merge_candidate_max_pct && + (float) right_used / BLCKSZ <= uargs->merge_candidate_max_pct && + (float) (left_used + right_used) / BLCKSZ <= uargs->merge_destination_max_pct) + { + /* + * Parent check: left and right must share the same immediate + * parent with adjacent downlinks. + */ + if (scankey != NULL && + + _bt_pages_share_parent(rel, left_blkno, right_blkno, scankey, NULL)) + { + pfree(scankey); + relation_close(rel, AccessShareLock); + break; /* found a valid candidate */ + } + } + + if (scankey) + pfree(scankey); + } + } + + + /* Build and return the output row */ + uargs->returned++; + memset(nulls, false, sizeof(nulls)); + j = 0; + values[j++] = Int64GetDatum((int64) left_blkno); + values[j++] = Int64GetDatum((int64) right_blkno); + values[j++] = Float8GetDatum(100.0 * left_free / BLCKSZ); + values[j++] = Float8GetDatum(100.0 * right_free / BLCKSZ); + /* free space the merged page would have */ + values[j++] = Float8GetDatum( + 100.0 * ((int64) left_free + (int64) right_free - (int64) BLCKSZ) / BLCKSZ); + + tuple = heap_form_tuple(uargs->tupd, values, nulls); + result = HeapTupleGetDatum(tuple); + SRF_RETURN_NEXT(fctx, result); +} + +static char * +index_tuple_data(IndexTuple itup) +{ + char *ptr; + int dlen; + char *dump; + char *datacstring; + + ptr = (char *) itup + IndexInfoFindDataOffset(itup->t_info); + dlen = IndexTupleSize(itup) - IndexInfoFindDataOffset(itup->t_info); + + if (BTreeTupleIsPosting(itup)) + dlen -= IndexTupleSize(itup) - BTreeTupleGetPostingOffset(itup); + else if (BTreeTupleIsPivot(itup) && BTreeTupleGetHeapTID(itup) != NULL) + dlen -= MAXALIGN(sizeof(ItemPointerData)); + + if (dlen < 0 || dlen > INDEX_SIZE_MASK) + elog(ERROR, "invalid tuple length %d", dlen); + + dump = palloc0(dlen * 3 + 1); + datacstring = dump; + for (int off = 0; off < dlen; off++) + { + if (off > 0) + *dump++ = ' '; + sprintf(dump, "%02x", *(ptr + off) & 0xff); + dump += 2; + } + + return datacstring; +} + +/*------------------------------------------------------- + * bt_merge_detail() + * + * Given a LEFT leaf block number, find its Right sibling and Parent page + * using a proper O(log N) B-tree descent, then return one row of structural + * details for each of the three pages in this order: Parent, Left, Right. + * + * Each row contains the page header fields and a tid[] array. For leaf + * pages the array holds heap TIDs (posting-list entries are expanded). + * For the parent page the array holds the child downlinks encoded as TIDs. + * + * merge_id is reserved for future use and is always NULL. + * + * Usage: SELECT * FROM bt_merge_detail('t1_pkey', 5, false); + *------------------------------------------------------- + */ +Datum +bt_merge_detail(PG_FUNCTION_ARGS) +{ + FuncCallContext *fctx; + ua_merge_detail *uargs; + + if (SRF_IS_FIRSTCALL()) + { + text *relname = PG_GETARG_TEXT_PP(0); + int64 left_blkno_arg = PG_GETARG_INT64(1); + MemoryContext mctx; + TupleDesc tupleDesc; + Relation rel; + List *relname_list; + RangeVar *relrv; + Buffer left_buf; + Page left_page; + BTPageOpaque left_opaque; + OffsetNumber first_data_off; + IndexTuple first_itup; + BTScanInsert scankey; + Buffer found_buf = InvalidBuffer; + BTStack stack; + BlockNumber parent_blkno = InvalidBlockNumber; + BlockNumber left_blkno; + BlockNumber right_blkno; + + fctx = SRF_FIRSTCALL_INIT(); + mctx = MemoryContextSwitchTo(fctx->multi_call_memory_ctx); + + uargs = palloc_object(ua_merge_detail); + + if (!superuser()) + ereport(ERROR, + (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), + errmsg("must be superuser to use pageinspect functions"))); + + /* Open and validate the relation */ + relname_list = textToQualifiedNameList(relname); + relrv = makeRangeVarFromNameList(relname_list); + rel = relation_openrv(relrv, AccessShareLock); + + /* Validate that it is a B-Tree and the block number is within bounds */ + bt_index_block_validate(rel, left_blkno_arg); + + left_blkno = (BlockNumber) left_blkno_arg; + + /* + * Step 1: Read the left leaf page to get right_blkno and the first + * data tuple, which we will use to build the scan key for the + * descent. + */ + left_buf = ReadBuffer(rel, left_blkno); + LockBuffer(left_buf, BUFFER_LOCK_SHARE); + left_page = BufferGetPage(left_buf); + left_opaque = BTPageGetOpaque(left_page); + + if (!P_ISLEAF(left_opaque)) + ereport(ERROR, (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("block %u is not a leaf page", left_blkno))); + + if (P_ISDELETED(left_opaque) || P_ISHALFDEAD(left_opaque)) + ereport(ERROR, (errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE), + errmsg("block %u is a deleted or half-dead page and cannot be inspected for merge", left_blkno))); + + if (P_ISMERGEDAWAY(left_opaque)) + ereport(ERROR, (errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE), + errmsg("block %u is a merged-away tombstone and cannot be inspected for merge", left_blkno))); + + right_blkno = left_opaque->btpo_next; + + if (P_RIGHTMOST(left_opaque)) + ereport( + ERROR, + (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("block %u is the rightmost leaf it has no right sibling", + left_blkno))); + + /* + * P_FIRSTDATAKEY returns the offset of the first real data tuple, + * skipping the high-key slot on non-leftmost pages. + */ + first_data_off = P_FIRSTDATAKEY(left_opaque); + if (first_data_off > PageGetMaxOffsetNumber(left_page)) + ereport(ERROR, (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("leaf page %u is empty cannot determine parent", + left_blkno))); + + first_itup = (IndexTuple) PageGetItem( + left_page, PageGetItemId(left_page, first_data_off)); + + /* + * Build a typed scan key from the tuple using the relation schema. + * _bt_mkscankey reads the TupleDesc and operator classes from rel, so + * our extension does not need to know the column data types. + */ + scankey = _bt_mkscankey(rel, first_itup); + + UnlockReleaseBuffer(left_buf); /* release left before the descent */ + + /* + * Step 2: Descend from the root in O(log N) reads. _bt_search + * returns: - found_buf: the leaf buffer (locked); we release it + * immediately. - stack: linked list from root to parent; + * stack->bts_blkno is the block number of the immediate parent + * (level-1 page). + */ + stack = _bt_search(rel, NULL, scankey, &found_buf, BT_READ, true); + if (stack != NULL) + parent_blkno = stack->bts_blkno; + + if (BufferIsValid(found_buf)) + UnlockReleaseBuffer(found_buf); + if (stack != NULL) + _bt_freestack(stack); + pfree(scankey); + + if (parent_blkno == InvalidBlockNumber) + ereport(ERROR, (errcode(ERRCODE_INTERNAL_ERROR), + errmsg("could not find parent page for leaf block %u", + left_blkno))); + + /* + * Step 3: Verify that Right is also a child of the same parent. + * + * Adjacent leaf siblings do NOT always share the same parent — they + * can straddle a parent-page boundary after a split. Instead of a + * second O(log N) descent, we simply scan the parent page we already + * have: if right_blkno does not appear as a downlink there, the two + * leaves have different parents and cannot be merged with a single + * parent update. + */ + { + Buffer parent_buf; + Page parent_page; + OffsetNumber off, + maxoff; + bool found_right = false; + + parent_buf = ReadBuffer(rel, parent_blkno); + LockBuffer(parent_buf, BUFFER_LOCK_SHARE); + parent_page = BufferGetPage(parent_buf); + maxoff = PageGetMaxOffsetNumber(parent_page); + + /* + * For non-rightmost pages, offset 1 is the HIGH KEY — its t_tid + * holds the separator key's downlink to the adjacent page, NOT a + * child of this page. Start from offset 2 to scan only real + * downlinks. + */ + { + BTPageOpaque pOpaque = BTPageGetOpaque(parent_page); + OffsetNumber scan_start = P_RIGHTMOST(pOpaque) + ? FirstOffsetNumber + : OffsetNumberNext(P_HIKEY); + + for (off = scan_start; off <= maxoff; off++) + { + IndexTuple itup = (IndexTuple) PageGetItem( + parent_page, PageGetItemId(parent_page, off)); + + if (ItemPointerGetBlockNumberNoCheck(&itup->t_tid) == right_blkno) + { + found_right = true; + break; + } + } + } + + UnlockReleaseBuffer(parent_buf); + + if (!found_right) + { + ereport(ERROR, + (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("pages cannot be merged: left block %u and right block " + "%u span a parent boundary", + left_blkno, right_blkno), + errhint("Parent block %u does not contain the right block.", + parent_blkno))); + } + } + + /* + * Store only the relation Oid so we can safely reopen it on every + * per-call invocation without leaking a relcache reference on LIMIT. + */ + uargs->relid = RelationGetRelid(rel); + relation_close(rel, AccessShareLock); + + uargs->parent_blkno = parent_blkno; + uargs->left_blkno = left_blkno; + uargs->right_blkno = right_blkno; + uargs->call_cntr = 0; + uargs->show_tids = PG_GETARG_BOOL(2); + + if (get_call_result_type(fcinfo, NULL, &tupleDesc) != TYPEFUNC_COMPOSITE) + elog(ERROR, "return type must be a row type"); + tupleDesc = BlessTupleDesc(tupleDesc); + + uargs->tupd = tupleDesc; + fctx->user_fctx = uargs; + + MemoryContextSwitchTo(mctx); + } + + fctx = SRF_PERCALL_SETUP(); + uargs = fctx->user_fctx; + + /* We return exactly 3 rows: 0=parent, 1=left, 2=right */ + if (uargs->call_cntr >= 3) + SRF_RETURN_DONE(fctx); + + { + Relation rel = relation_open(uargs->relid, AccessShareLock); + BlockNumber blkno; + BlockNumber btpo_prev_val; + BlockNumber btpo_next_val; + uint32 btpo_flags_val; + uint32 btpo_level_val; + Size free_size_val; + const char *role; + Buffer buf; + Page page; + BTPageOpaque opaque; + OffsetNumber off, + maxoff, + first_off; + char *high_key_hex = NULL; + char *first_val_hex = NULL; + char *last_val_hex = NULL; + int max_tids; + ItemPointerData *tids_buf; + int ntids = 0; + Datum *tids_datum; + Datum values[14]; + bool nulls[14]; + int j; + HeapTuple tuple; + Datum result; + + switch (uargs->call_cntr) + { + case 0: + blkno = uargs->parent_blkno; + role = "parent"; + break; + case 1: + blkno = uargs->left_blkno; + role = "left"; + break; + default: + blkno = uargs->right_blkno; + role = "right"; + break; + } + + buf = ReadBuffer(rel, blkno); + LockBuffer(buf, BUFFER_LOCK_SHARE); + page = BufferGetPage(buf); + opaque = BTPageGetOpaque(page); + maxoff = PageGetMaxOffsetNumber(page); + + btpo_prev_val = opaque->btpo_prev; + btpo_next_val = opaque->btpo_next; + btpo_flags_val = opaque->btpo_flags; + btpo_level_val = opaque->btpo_level; + free_size_val = PageGetFreeSpace(page); + + /* + * Collect TIDs / downlinks from the page. + * + * Leaf pages: iterate data tuples (skip high key via P_FIRSTDATAKEY). + * - Posting-list tuples: expand with BTreeTupleGetPosting(). - Normal + * tuples: take t_tid directly. + * + * Parent page: all items are pivot tuples; the block-number part of + * t_tid is the child downlink. Skip minus-infinity entries that have + * no real downlink (InvalidBlockNumber). + * + * Upper bound: 2*BLCKSZ/sizeof(ItemPointerData) covers any real page. + */ + max_tids = 2 * BLCKSZ / sizeof(ItemPointerData); + tids_buf = (ItemPointerData *) palloc(max_tids * sizeof(ItemPointerData)); + + if (P_ISLEAF(opaque) && !P_ISMERGEDAWAY(opaque) && !P_ISDELETED(opaque)) + { + first_off = P_FIRSTDATAKEY(opaque); + for (off = first_off; off <= maxoff; off++) + { + IndexTuple itup = + (IndexTuple) PageGetItem(page, PageGetItemId(page, off)); + + if (BTreeTupleIsPosting(itup)) + { + int nposting = BTreeTupleGetNPosting(itup); + ItemPointer posting = BTreeTupleGetPosting(itup); + + for (int i = 0; i < nposting && ntids < max_tids; i++) + tids_buf[ntids++] = posting[i]; + } + else + { + if (ntids < max_tids) + tids_buf[ntids++] = itup->t_tid; + } + } + + /* + * High key + */ + if (!P_RIGHTMOST(opaque)) + { + IndexTuple hikey = + (IndexTuple) PageGetItem(page, PageGetItemId(page, P_HIKEY)); + + high_key_hex = index_tuple_data(hikey); + } + + /* + * First and last data tuples + */ + if (first_off <= maxoff) + { + IndexTuple first_itup = + (IndexTuple) PageGetItem(page, PageGetItemId(page, first_off)); + IndexTuple last_itup = + (IndexTuple) PageGetItem(page, PageGetItemId(page, maxoff)); + + first_val_hex = index_tuple_data(first_itup); + last_val_hex = index_tuple_data(last_itup); + } + } + else if (!P_ISMERGEDAWAY(opaque) && !P_ISDELETED(opaque)) + { + for (off = FirstOffsetNumber; off <= maxoff; off++) + { + IndexTuple itup = + (IndexTuple) PageGetItem(page, PageGetItemId(page, off)); + + if (BTreeTupleIsPivot(itup) && + ItemPointerGetBlockNumberNoCheck(&itup->t_tid) != + InvalidBlockNumber) + { + if (ntids < max_tids) + tids_buf[ntids++] = itup->t_tid; + } + } + } + + UnlockReleaseBuffer(buf); + relation_close(rel, AccessShareLock); + + /* Convert tids_buf into a Datum array for construct_array_builtin */ + tids_datum = (Datum *) palloc(ntids * sizeof(Datum)); + for (int i = 0; i < ntids; i++) + tids_datum[i] = ItemPointerGetDatum(&tids_buf[i]); + + /* Build output tuple */ + memset(nulls, false, sizeof(nulls)); + j = 0; + values[j++] = CStringGetTextDatum(role); + values[j++] = Int64GetDatum((int64) blkno); + values[j++] = Int64GetDatum((int64) btpo_prev_val); + values[j++] = Int64GetDatum((int64) btpo_next_val); + values[j++] = Int64GetDatum((int64) btpo_level_val); + values[j++] = Int32GetDatum((int32) btpo_flags_val); + values[j++] = Int32GetDatum((int32) free_size_val); + values[j++] = Float8GetDatum(100.0 * free_size_val / BLCKSZ); + values[j++] = Int32GetDatum((int32) ntids); + if (high_key_hex) + values[j++] = CStringGetTextDatum(high_key_hex); + else + nulls[j++] = true; + if (first_val_hex) + values[j++] = CStringGetTextDatum(first_val_hex); + else + nulls[j++] = true; + if (last_val_hex) + values[j++] = CStringGetTextDatum(last_val_hex); + else + nulls[j++] = true; + nulls[j++] = true; /* merge_id: RFU, always NULL */ + + if (uargs->show_tids) + values[j++] = PointerGetDatum(construct_array_builtin(tids_datum, ntids, TIDOID)); + else + nulls[j++] = true; + + tuple = heap_form_tuple(uargs->tupd, values, nulls); + result = HeapTupleGetDatum(tuple); + + uargs->call_cntr++; + SRF_RETURN_NEXT(fctx, result); + } +} + +Datum +bt_merge(PG_FUNCTION_ARGS) +{ + text *relname = PG_GETARG_TEXT_PP(0); + float8 merge_candidate_max_pct = PG_GETARG_FLOAT8(1); + float8 merge_destination_max_pct = PG_GETARG_FLOAT8(2); + int32 num_pages = PG_GETARG_INT32(3); + Relation rel; + RangeVar *relrv; + int32 merges_performed; + + + if (!superuser()) + ereport(ERROR, + (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), + errmsg("must be superuser to use pageinspect functions"))); + + relrv = makeRangeVarFromNameList(textToQualifiedNameList(relname)); + rel = relation_openrv(relrv, AccessShareLock); + + if (!IS_INDEX(rel) || !IS_BTREE(rel)) + ereport(ERROR, + (errcode(ERRCODE_WRONG_OBJECT_TYPE), + errmsg("\"%s\" is not a %s index", + RelationGetRelationName(rel), "btree"))); + + /* + * Reject attempts to read non-local temporary relations; we would be + * likely to get wrong data since we have no visibility into the owning + * session's local buffers. + */ + if (RELATION_IS_OTHER_TEMP(rel)) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot access temporary tables of other sessions"))); + + + merges_performed = _bt_merge_index(rel, merge_candidate_max_pct, merge_destination_max_pct, num_pages); + + relation_close(rel, AccessShareLock); + + + PG_RETURN_INT32(merges_performed); + +} diff --git a/contrib/pageinspect/pageinspect--1.12--1.13.sql b/contrib/pageinspect/pageinspect--1.12--1.13.sql index 07ec70a5de3..4ca54567d59 100644 --- a/contrib/pageinspect/pageinspect--1.12--1.13.sql +++ b/contrib/pageinspect/pageinspect--1.12--1.13.sql @@ -72,3 +72,66 @@ LANGUAGE SQL PARALLEL RESTRICTED BEGIN ATOMIC SELECT * FROM heap_page_item_attrs(page, rel_oid, false); END; + + +-- +-- bt_find_merge_candidates(relname, min_pct_threshold, num_pages) +-- +-- Scan the B-tree leaf chain and return up to num_pages LEFT block numbers +-- of adjacent pairs that are merge candidates (both pages <= min_pct_threshold +-- percent full, and combined content fits within the target fillfactor). +-- +CREATE FUNCTION bt_find_merge_candidates( + IN relname text, + IN merge_candidate_max_pct float8 DEFAULT 10.0, + IN merge_destination_max_pct float8 DEFAULT 90.0, + IN num_pages int4 DEFAULT 1, + OUT left_blkno int8, + OUT right_blkno int8, + OUT free_space_left float8, + OUT free_space_right float8, + OUT result_free_space float8) +RETURNS SETOF record +AS 'MODULE_PATHNAME', 'bt_find_merge_candidates' +LANGUAGE C PARALLEL SAFE; + +-- +-- bt_merge_detail(relname, left_blkno) +-- +-- Given the LEFT leaf block number, find its Right sibling and Parent via +-- a proper B-tree descent (O(log N)), then return one detail row for each +-- of the three pages: Parent, Left, Right. +-- +CREATE FUNCTION bt_merge_detail( + IN relname text, + IN left_blkno int8, + IN show_tids boolean, + OUT page_role text, + OUT blkno int8, + OUT btpo_prev int8, + OUT btpo_next int8, + OUT btpo_level int8, + OUT btpo_flags int4, + OUT free_size int4, + OUT pct_free float8, + OUT num_tids int4, + OUT high_key text, + OUT first_val text, + OUT last_val text, + OUT merge_id int4, + OUT tids tid[] +) +RETURNS SETOF record +AS 'MODULE_PATHNAME', 'bt_merge_detail' +LANGUAGE C PARALLEL SAFE; + +CREATE FUNCTION bt_merge( + IN relname text, + IN merge_candidate_max_pct float8 DEFAULT 10.0, + IN merge_destination_max_pct float8 DEFAULT 90.0, + IN num_pages int4 DEFAULT 1, + OUT merges_performed int4 +) +RETURNS int4 +AS 'MODULE_PATHNAME', 'bt_merge' +LANGUAGE C PARALLEL SAFE; \ No newline at end of file -- 2.43.0
From 22b23711038c84ded7195633f9571d0060c2e175 Mon Sep 17 00:00:00 2001 From: Salma <[email protected]> Date: Wed, 29 Jul 2026 00:08:34 +0300 Subject: [PATCH v2 1/3] nbtree: Add leaf page merge support Add support for merging 2 adjacent leaf pages in B-tree indexes to reduce index bloat. Tuples from the left leaf page (L) are copied to the right leaf page (R), and downlinks in the parent are updated accordingly. Index scan logic is updated to handle concurrent merges by detecting merged-away tombstone pages and recovering scan positions forward and backward across merged page groups. L is marked as BTP_MERGED_AWAY (tombstone) and R as BTP_MERGED. VACUUM clears BTP_MERGED flags from merged pages once safe, and converts tombstone pages to half-dead (BTP_HALF_DEAD) for final page deletion. --- src/backend/access/nbtree/Makefile | 1 + src/backend/access/nbtree/meson.build | 1 + src/backend/access/nbtree/nbtdedup.c | 2 + src/backend/access/nbtree/nbtinsert.c | 36 +- src/backend/access/nbtree/nbtmerge.c | 493 ++++++++++++++++++++++++++ src/backend/access/nbtree/nbtpage.c | 84 ++++- src/backend/access/nbtree/nbtree.c | 217 ++++++++++++ src/backend/access/nbtree/nbtsearch.c | 443 ++++++++++++++++++++++- src/backend/access/nbtree/nbtutils.c | 2 +- src/include/access/nbtree.h | 119 +++++++ 10 files changed, 1386 insertions(+), 12 deletions(-) create mode 100644 src/backend/access/nbtree/nbtmerge.c diff --git a/src/backend/access/nbtree/Makefile b/src/backend/access/nbtree/Makefile index 0daf640af96..5593bb9c05f 100644 --- a/src/backend/access/nbtree/Makefile +++ b/src/backend/access/nbtree/Makefile @@ -16,6 +16,7 @@ OBJS = \ nbtcompare.o \ nbtdedup.o \ nbtinsert.o \ + nbtmerge.o \ nbtpage.o \ nbtpreprocesskeys.o \ nbtreadpage.o \ diff --git a/src/backend/access/nbtree/meson.build b/src/backend/access/nbtree/meson.build index 812f067e710..79d225814d0 100644 --- a/src/backend/access/nbtree/meson.build +++ b/src/backend/access/nbtree/meson.build @@ -4,6 +4,7 @@ backend_sources += files( 'nbtcompare.c', 'nbtdedup.c', 'nbtinsert.c', + 'nbtmerge.c', 'nbtpage.c', 'nbtpreprocesskeys.c', 'nbtreadpage.c', diff --git a/src/backend/access/nbtree/nbtdedup.c b/src/backend/access/nbtree/nbtdedup.c index af7affdf409..5fa40bfd624 100644 --- a/src/backend/access/nbtree/nbtdedup.c +++ b/src/backend/access/nbtree/nbtdedup.c @@ -119,6 +119,8 @@ _bt_dedup_pass(Relation rel, Buffer buf, IndexTuple newitem, Size newitemsz, */ newpage = PageGetTempPageCopySpecial(page); PageSetLSN(newpage, PageGetLSN(page)); + if (P_ISMERGED(opaque)) + BTMergedPageSetMABlkno(newpage, BTMergedPageGetMABlkno(page)); /* Copy high key, if any */ if (!P_RIGHTMOST(opaque)) diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c index c8af97dd23d..90072175ef3 100644 --- a/src/backend/access/nbtree/nbtinsert.c +++ b/src/backend/access/nbtree/nbtinsert.c @@ -61,7 +61,6 @@ static Buffer _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, IndexTuple nposting, uint16 postingoff); static void _bt_insert_parent(Relation rel, Relation heaprel, Buffer buf, Buffer rbuf, BTStack stack, bool isroot, bool isonly); -static void _bt_freestack(BTStack stack); static Buffer _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf); static inline bool _bt_pgaddtup(Page page, Size itemsize, const IndexTupleData *itup, OffsetNumber itup_off, bool newfirstdataitem); @@ -750,7 +749,7 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel, nbuf = _bt_relandgetbuf(rel, nbuf, nblkno, BT_READ); page = BufferGetPage(nbuf); opaque = BTPageGetOpaque(page); - if (!P_IGNORE(opaque)) + if (!P_IGNORE(opaque) && !P_ISMERGEDAWAY(opaque)) break; if (P_RIGHTMOST(opaque)) elog(ERROR, "fell off the end of index \"%s\"", @@ -1071,7 +1070,7 @@ _bt_stepright(Relation rel, Relation heaprel, BTInsertState insertstate, continue; } - if (!P_IGNORE(opaque)) + if (!P_IGNORE(opaque) && !P_ISMERGEDAWAY(opaque)) break; if (P_RIGHTMOST(opaque)) elog(ERROR, "fell off the end of index \"%s\"", @@ -1585,6 +1584,21 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf, lopaque->btpo_level = oopaque->btpo_level; /* handle btpo_cycleid after rightpage buffer acquired */ + /* + * If the original page was BTP_MERGED, the left-half temp page inherits + * BTP_MERGED via the btpo_flags copy above. However, the MA block number + * stored in pd_prune_xid (see BTMergedPageSetMABlkno) lives in + * PageHeaderData, not BTPageOpaqueData, so it is NOT carried over by the + * btpo_flags assignment. leftpage was freshly initialized by + * _bt_pageinit above, leaving pd_prune_xid as InvalidTransactionId (0). + * When leftpage is later copied back into origpage (memcpy at + * START_CRIT_SECTION time), the original MA block number would be + * silently lost, causing amcheck to report "merged page N has invalid MA + * block number 0". Propagate it now. + */ + if (P_ISMERGED(oopaque)) + BTMergedPageSetMABlkno(leftpage, BTMergedPageGetMABlkno(origpage)); + /* * Copy the original page's LSN into leftpage, which will become the * updated version of the page. We need this because XLogInsert will @@ -1773,6 +1787,20 @@ _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf, ropaque->btpo_level = oopaque->btpo_level; ropaque->btpo_cycleid = lopaque->btpo_cycleid; + /* + * If the original page was BTP_MERGED, the new right-half page inherits + * BTP_MERGED via the btpo_flags copy above. However, the MA_blkno we + * stored in pd_prune_xid (see BTMergedPageSetMABlkno) lives in + * PageHeaderData, not BTPageOpaqueData, so it is NOT copied by the + * btpo_flags assignment. The right page was freshly allocated by + * _bt_allocbuf, which calls _bt_pageinit -> PageInit, leaving + * pd_prune_xid as InvalidTransactionId (0). Propagate the MA_blkno now + * so that backward scans can verify the correct tombstone for both halves + * of the split merge group. + */ + if (P_ISMERGED(oopaque)) + BTMergedPageSetMABlkno(rightpage, BTMergedPageGetMABlkno(origpage)); + /* * Add new high key to rightpage where necessary. * @@ -2457,7 +2485,7 @@ _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child /* * _bt_freestack() -- free a retracement stack made by _bt_search_insert. */ -static void +void _bt_freestack(BTStack stack) { BTStack ostack; diff --git a/src/backend/access/nbtree/nbtmerge.c b/src/backend/access/nbtree/nbtmerge.c new file mode 100644 index 00000000000..b9ea0696fd8 --- /dev/null +++ b/src/backend/access/nbtree/nbtmerge.c @@ -0,0 +1,493 @@ +/*------------------------------------------------------------------------- + * + * nbtmerge.c + * Merge two adjacent underutilized leaf pages into one to reduce bloat. + * + * The merge scans leaf pages left-to-right and, when a consecutive pair both + * fall below a minimum fill threshold and their combined data fits within the + * target fill factor, copies all tuples from the left page (L) into the right + * page (R), redirects L's parent downlink to R, removes R's now-redundant + * downlink from the parent, marks L as BTP_MERGED_AWAY (tombstone), and marks + * R as BTP_MERGED. VACUUM is responsible for later reclaiming tombstone pages. + * + * IDENTIFICATION + * src/backend/access/nbtree/nbtmerge.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "access/nbtree.h" +#include "access/tableam.h" +#include "common/int.h" +#include "storage/bufmgr.h" +#include "storage/lmgr.h" +#include "utils/injection_point.h" +#include "storage/predicate.h" +#include "miscadmin.h" + +typedef struct BTMergeState +{ + + Relation rel; + float8 min_threshold; /* minimum fill fraction to qualify for merge */ + float8 fillfactor; /* maximum combined fill fraction after merge */ + BlockNumber left_blkno; + BlockNumber right_blkno; + BTStack stack; +} BTMergeState; + + +static int32 _bt_mergescan(Relation rel, float8 min_threshold, float8 fillfactor, int pages_limit); +static bool _bt_mergepage(BTMergeState mstate); +static BTScanInsert _bt_merge_mkscankey(Relation rel, Page page, BTPageOpaque opaque); +static bool _bt_pages_mergeable(Page left_page, Page right_page, float8 min_threshold, float8 fillfactor); + + +/* + * _bt_merge_index() -- Entry point: merge underutilized leaf pages. + * + * min_pct is the per-page threshold (0..100); pages below this are candidates. + * dest_pct is the target combined fill (0..100); the merged page must fit. + * num_pages caps how many leaf pairs are examined in one call. + * + * Returns the number of merges actually performed. + */ +int32 +_bt_merge_index(Relation rel, float8 min_pct, float8 dest_pct, int32 num_pages) +{ + return _bt_mergescan(rel, min_pct, dest_pct, num_pages); +} + + +/* + * _bt_merge_mkscankey() -- Build a BTScanInsert key from the first data tuple + * on a leaf page. Returns NULL if the page carries no data tuples. Caller + * must pfree the returned key. + */ +static BTScanInsert +_bt_merge_mkscankey(Relation rel, Page page, BTPageOpaque opaque) +{ + OffsetNumber first_off = P_FIRSTDATAKEY(opaque); + + if (first_off > PageGetMaxOffsetNumber(page)) + return NULL; + + return _bt_mkscankey(rel, + (IndexTuple) PageGetItem(page, + PageGetItemId(page, first_off))); +} + +/* + * _bt_pages_mergeable() -- Return true when the pair qualifies for merging. + * + * Both pages must individually be below min_threshold and their combined used + * space must fit within fillfactor. Thresholds are fractions (0.0 - 1.0). + */ +static bool +_bt_pages_mergeable(Page left_page, Page right_page, + float8 min_threshold, float8 fillfactor) +{ + BTPageOpaque left_opaque = BTPageGetOpaque(left_page); + Size left_used = BLCKSZ - PageGetFreeSpace(left_page); + Size right_used = BLCKSZ - PageGetFreeSpace(right_page); + Size bytes_needed = 0; + OffsetNumber maxoff_left = PageGetMaxOffsetNumber(left_page); + OffsetNumber first_left = P_FIRSTDATAKEY(left_opaque); + + /* Check individual threshold qualifications first */ + if ((float8) left_used / BLCKSZ > min_threshold || + (float8) right_used / BLCKSZ > min_threshold) + return false; + + /* Compute exact bytes needed for all data tuples transferred from L */ + for (OffsetNumber off = first_left; off <= maxoff_left; off++) + { + ItemId itemid = PageGetItemId(left_page, off); + IndexTuple itup = (IndexTuple) PageGetItem(left_page, itemid); + + bytes_needed += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData); + } + + /* Ensure R has enough physical free space to hold all transferred tuples */ + if (PageGetFreeSpace(right_page) < bytes_needed) + return false; + + /* Ensure total resulting size fits within the specified fillfactor */ + if ((float8) (right_used + bytes_needed) / BLCKSZ > fillfactor) + return false; + + return true; +} + + +/* + * _bt_mergescan() -- Walk leaf pages left-to-right looking for merge + * candidates. + * + * Scans leaf pages starting from the second leftmost. For each + * candidate pair (L, R), verifies they share a parent, then calls + * _bt_mergepage() to perform the actual merge under exclusive locks. + * + * Stops after pages_limit leaf pages have been examined or the rightmost leaf + * is reached. Returns the number of merges performed. + */ +static int32 +_bt_mergescan(Relation rel, float8 min_threshold, float8 fillfactor, int pages_limit) +{ + Buffer left_buf, + right_buf; + Page left_page, + right_page, + temp_page; + BTPageOpaque left_opaque, + right_opaque, + temp_opaque; + BlockNumber left_blkno, + right_blkno, + current_blkno, + r_right_blkno; + int32 merges_performed = 0; + int num_pages = 0; + BTScanInsert scankey; + BTMergeState mstate; + BTStack stack; + + mstate.rel = rel; + mstate.min_threshold = min_threshold / 100.0; + mstate.fillfactor = fillfactor / 100.0; + + /* Start from the second leftmost leaf page. */ + { + Buffer endpoint_buf = _bt_get_endpoint(rel, 0, false); + + current_blkno = BufferGetBlockNumber(endpoint_buf); + temp_page = BufferGetPage(endpoint_buf); + temp_opaque = BTPageGetOpaque(temp_page); + current_blkno = temp_opaque->btpo_next; + UnlockReleaseBuffer(endpoint_buf); + } + + for (;;) + { + CHECK_FOR_INTERRUPTS(); + + if (num_pages >= pages_limit || current_blkno == P_NONE) + return merges_performed; + + /* Pin and share-lock the left candidate. */ + left_blkno = current_blkno; + left_buf = ReadBuffer(rel, left_blkno); + LockBuffer(left_buf, BUFFER_LOCK_SHARE); + left_page = BufferGetPage(left_buf); + left_opaque = BTPageGetOpaque(left_page); + + if (P_RIGHTMOST(left_opaque)) + { + UnlockReleaseBuffer(left_buf); + return merges_performed; + } + + if (P_ISDELETED(left_opaque) || P_ISHALFDEAD(left_opaque) + || P_ISMERGED(left_opaque) || P_ISMERGEDAWAY(left_opaque)) + { + current_blkno = left_opaque->btpo_next; + UnlockReleaseBuffer(left_buf); + continue; + } + + Assert(P_ISLEAF(left_opaque)); + + /* Pin and share-lock the right candidate. */ + right_blkno = left_opaque->btpo_next; + right_buf = ReadBuffer(rel, right_blkno); + LockBuffer(right_buf, BUFFER_LOCK_SHARE); + right_page = BufferGetPage(right_buf); + right_opaque = BTPageGetOpaque(right_page); + + if (P_ISDELETED(right_opaque) || P_ISHALFDEAD(right_opaque) + || P_ISMERGED(right_opaque) || P_ISMERGEDAWAY(right_opaque)) + { + current_blkno = right_opaque->btpo_next; + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + continue; + } + + Assert(P_ISLEAF(right_opaque)); + + /* Save R's right sibling while we still hold the share lock on R. */ + r_right_blkno = right_opaque->btpo_next; + + /* L is examined; slide the window to R as the default next-left. */ + num_pages++; + current_blkno = right_blkno; + + scankey = _bt_merge_mkscankey(rel, left_page, left_opaque); + + if (_bt_pages_mergeable(left_page, right_page, + mstate.min_threshold, mstate.fillfactor) && + scankey != NULL) + { + /* + * R is also consumed; advance past it. + * + * Drop share locks before calling _bt_pages_share_parent. + * _bt_search descends to the left leaf and will try to lock it, + * which would fail an assertion if we already hold a lock on it. + * The scankey is a palloc'd copy so releasing here is safe. + */ + num_pages++; + current_blkno = r_right_blkno; + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + + if (_bt_pages_share_parent(rel, left_blkno, right_blkno, + scankey, &stack)) + { + mstate.left_blkno = left_blkno; + mstate.right_blkno = right_blkno; + mstate.stack = stack; + + if (_bt_mergepage(mstate)) + merges_performed++; + + _bt_freestack(stack); + } + + pfree(scankey); + continue; + } + + /* Pages don't qualify; current_blkno already points at R. */ + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + if (scankey) + pfree(scankey); + } +} + + +/* + * _bt_mergepage() -- Perform one leaf-page merge. + * + * Re-acquires exclusive locks on L, R, and their parent, re-verifies all + * preconditions under those exclusive locks, then: + * + * 1. Saves R's high key and all data tuples to palloc'd memory. + * 2. Re-initializes R's page, restoring its opaque header and high key. + * 3. Copies all data tuples from L into R, followed by R's original tuples. + * 4. Redirects L's downlink in the parent to point to R, then deletes R's + * now-redundant downlink entry from the parent. + * 5. Marks R as BTP_MERGED, recording L's block number in R's pd_prune_xid + * field so backward scans can identify the merge group tombstone. + * 6. Marks L as BTP_MERGED_AWAY, recording a safemergexid so VACUUM can + * determine when the tombstone page is safe to reclaim. + * + * Returns true if the merge completed, false if any precondition failed. + */ +static bool +_bt_mergepage(BTMergeState mstate) +{ + Relation rel = mstate.rel; + BlockNumber parent_blkno; + Buffer left_buf, + right_buf, + parent_buf = InvalidBuffer; + Page left_page, + right_page, + parent_page; + BTPageOpaque left_opaque, + right_opaque, + parent_opaque; + BTStack stack = mstate.stack; + ItemId itemid; + IndexTuple itup, + left_itup, + r_hikey = NULL; + Size r_hikey_size = 0, + sz; + OffsetNumber next_off; + int n_right; + IndexTuple *r_tuples = NULL; + Size *r_sizes = NULL; + BTPageOpaqueData saved_opaque; + FullTransactionId safemergexid; + bool merged = false; + + parent_blkno = stack->bts_blkno; + + left_buf = ReadBuffer(rel, mstate.left_blkno); + LockBuffer(left_buf, BT_WRITE); + left_page = BufferGetPage(left_buf); + left_opaque = BTPageGetOpaque(left_page); + Assert(P_ISLEAF(left_opaque)); + + INJECTION_POINT("after_left_lock", NULL); + + right_buf = ReadBuffer(rel, mstate.right_blkno); + LockBuffer(right_buf, BT_WRITE); + right_page = BufferGetPage(right_buf); + right_opaque = BTPageGetOpaque(right_page); + Assert(P_ISLEAF(right_opaque)); + + /* Re-verify left & right leaf pages under exclusive lock. */ + if (P_ISDELETED(left_opaque) || P_ISHALFDEAD(left_opaque) || + P_ISMERGED(left_opaque) || P_ISMERGEDAWAY(left_opaque) || + P_INCOMPLETE_SPLIT(left_opaque) || + left_opaque->btpo_next != mstate.right_blkno) + goto unlock_leaf_bufs; + + if (P_ISDELETED(right_opaque) || P_ISHALFDEAD(right_opaque) || + P_ISMERGED(right_opaque) || P_ISMERGEDAWAY(right_opaque) || + P_INCOMPLETE_SPLIT(right_opaque)) + goto unlock_leaf_bufs; + + if (!_bt_pages_mergeable(left_page, right_page, + mstate.min_threshold, mstate.fillfactor)) + goto unlock_leaf_bufs; + + /* + * Lock the parent and confirm that downlinks at bts_offset and + * bts_offset+1 still point to L and R respectively. + */ + parent_buf = ReadBuffer(rel, parent_blkno); + LockBuffer(parent_buf, BT_WRITE); + parent_page = BufferGetPage(parent_buf); + parent_opaque = BTPageGetOpaque(parent_page); + + if (P_ISDELETED(parent_opaque) || P_ISHALFDEAD(parent_opaque) || + parent_opaque->btpo_level != left_opaque->btpo_level + 1) + goto unlock_all_bufs; + + next_off = OffsetNumberNext(stack->bts_offset); + if (stack->bts_offset < P_FIRSTDATAKEY(parent_opaque) || + next_off > PageGetMaxOffsetNumber(parent_page)) + goto unlock_all_bufs; + + /* Verify L's downlink */ + itemid = PageGetItemId(parent_page, stack->bts_offset); + if (!ItemIdIsNormal(itemid)) + goto unlock_all_bufs; + left_itup = (IndexTuple) PageGetItem(parent_page, itemid); + if (BTreeTupleGetDownLink(left_itup) != mstate.left_blkno) + goto unlock_all_bufs; + + /* Verify R's downlink */ + itemid = PageGetItemId(parent_page, next_off); + if (!ItemIdIsNormal(itemid)) + goto unlock_all_bufs; + itup = (IndexTuple) PageGetItem(parent_page, itemid); + if (BTreeTupleGetDownLink(itup) != mstate.right_blkno) + goto unlock_all_bufs; + + /* Save R's high key (if not rightmost). */ + if (!P_RIGHTMOST(right_opaque)) + { + ItemId hikey_id = PageGetItemId(right_page, P_HIKEY); + + r_hikey_size = ItemIdGetLength(hikey_id); + r_hikey = (IndexTuple) palloc(r_hikey_size); + memcpy(r_hikey, PageGetItem(right_page, hikey_id), r_hikey_size); + } + + /* Save all of R's data tuples into temporary memory. */ + { + OffsetNumber r_start = P_FIRSTDATAKEY(right_opaque); + OffsetNumber r_maxoff = PageGetMaxOffsetNumber(right_page); + + n_right = (r_maxoff >= r_start) ? (r_maxoff - r_start + 1) : 0; + r_tuples = palloc_array(IndexTuple, n_right); + r_sizes = palloc_array(Size, n_right); + + for (int i = 0; i < n_right; i++) + { + itemid = PageGetItemId(right_page, r_start + i); + sz = ItemIdGetLength(itemid); + itup = (IndexTuple) PageGetItem(right_page, itemid); + r_tuples[i] = (IndexTuple) palloc(sz); + memcpy(r_tuples[i], itup, sz); + r_sizes[i] = sz; + } + } + + safemergexid = ReadNextFullTransactionId(); + + /* + * Any failure across the three-buffer update (L becomes a tombstone, R + * absorbs all tuples, parent loses R's downlink) would leave the index in + * an inconsistent state. Perform all three modifications as an atomic + * unit inside a critical section so that any error panics the server + * rather than aborting with a partially updated index. WAL logging will + * be added here once the redo infrastructure is in place. + */ + START_CRIT_SECTION(); + + /* Reinitialize R, preserving its opaque header. */ + saved_opaque = *right_opaque; + PageInit(right_page, BufferGetPageSize(right_buf), sizeof(BTPageOpaqueData)); + *BTPageGetOpaque(right_page) = saved_opaque; + + if (r_hikey != NULL) + { + if (PageAddItem(right_page, r_hikey, r_hikey_size, + P_HIKEY, false, false) == InvalidOffsetNumber) + elog(PANIC, "failed to restore high key to merged page"); + } + + /* Copy L's data tuples into R. */ + for (OffsetNumber off = P_FIRSTDATAKEY(left_opaque); + off <= PageGetMaxOffsetNumber(left_page); + off++) + { + itemid = PageGetItemId(left_page, off); + sz = ItemIdGetLength(itemid); + itup = (IndexTuple) PageGetItem(left_page, itemid); + + if (PageAddItem(right_page, itup, sz, + InvalidOffsetNumber, false, false) == InvalidOffsetNumber) + elog(PANIC, "failed to copy left tuple to merged page"); + } + + /* Append R's original data tuples after L's. */ + for (int i = 0; i < n_right; i++) + { + if (PageAddItem(right_page, r_tuples[i], r_sizes[i], + InvalidOffsetNumber, false, false) == InvalidOffsetNumber) + elog(PANIC, "failed to copy right tuple to merged page"); + } + + /* Redirect L's downlink to R and delete R's downlink entry. */ + BTreeTupleSetDownLink(left_itup, mstate.right_blkno); + PageIndexTupleDelete(parent_page, next_off); + + BTPageSetMerged(right_page); + BTMergedPageSetMABlkno(right_page, mstate.left_blkno); + BTPageSetMergedAway(left_page, safemergexid); + + MarkBufferDirty(left_buf); + MarkBufferDirty(right_buf); + MarkBufferDirty(parent_buf); + + END_CRIT_SECTION(); + + /* Free temporary memory. */ + if (r_hikey != NULL) + pfree(r_hikey); + for (int i = 0; i < n_right; i++) + pfree(r_tuples[i]); + pfree(r_tuples); + pfree(r_sizes); + + PredicateLockPageCombine(rel, mstate.left_blkno, mstate.right_blkno); + merged = true; + +unlock_all_bufs: + UnlockReleaseBuffer(parent_buf); + +unlock_leaf_bufs: + UnlockReleaseBuffer(right_buf); + UnlockReleaseBuffer(left_buf); + + return merged; +} diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c index 109017d6b52..6e73004e218 100644 --- a/src/backend/access/nbtree/nbtpage.c +++ b/src/backend/access/nbtree/nbtpage.c @@ -1773,7 +1773,7 @@ _bt_rightsib_halfdeadflag(Relation rel, BlockNumber leafrightsib) opaque = BTPageGetOpaque(page); Assert(P_ISLEAF(opaque) && !P_ISDELETED(opaque)); - result = P_ISHALFDEAD(opaque); + result = P_ISHALFDEAD(opaque) || P_ISMERGEDAWAY(opaque); _bt_relbuf(rel, buf); return result; @@ -2569,7 +2569,7 @@ _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf, BlockNumber scanblkno, } rightsib_is_rightmost = P_RIGHTMOST(opaque); - *rightsib_empty = (P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page)); + *rightsib_empty = !P_ISMERGEDAWAY(opaque) && (P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page)); /* * If we are deleting the next-to-last page on the target's level, then @@ -3130,3 +3130,83 @@ _bt_pendingfsm_add(BTVacState *vstate, vstate->pendingpages[vstate->npendingpages].safexid = safexid; vstate->npendingpages++; } + +bool +_bt_pages_share_parent(Relation rel, BlockNumber left_blkno, + BlockNumber right_blkno, BTScanInsert scankey, BTStack *stack_out) +{ + BTStack stack; + Buffer found_buf = InvalidBuffer; + BlockNumber parent_blkno = InvalidBlockNumber; + Buffer parent_buf; + Page parent_page; + OffsetNumber maxoff, + left_off; + bool found_left = false; + IndexTuple itup; + BlockNumber child; + + + /* Descend the tree to find left's parent. Caller built scankey. */ + stack = _bt_search(rel, NULL, scankey, &found_buf, BT_READ, true); + + if (BufferIsValid(found_buf)) + UnlockReleaseBuffer(found_buf); + + if (stack == NULL) + return false; + + parent_blkno = stack->bts_blkno; + + if (parent_blkno == InvalidBlockNumber) + { + _bt_freestack(stack); + return false; + } + + parent_buf = ReadBuffer(rel, parent_blkno); + LockBuffer(parent_buf, BUFFER_LOCK_SHARE); + parent_page = BufferGetPage(parent_buf); + + left_off = stack->bts_offset; + + maxoff = PageGetMaxOffsetNumber(parent_page); + + itup = (IndexTuple) PageGetItem(parent_page, PageGetItemId(parent_page, left_off)); + + child = ItemPointerGetBlockNumberNoCheck(&itup->t_tid); + + if (child == left_blkno) + { + found_left = true; + } + /** + * check if off + 1 in the parent is the right sibling + */ + if (found_left) + { + OffsetNumber next_off = OffsetNumberNext(left_off); + + if (next_off <= maxoff) + { + itup = (IndexTuple) PageGetItem(parent_page, PageGetItemId(parent_page, next_off)); + + child = ItemPointerGetBlockNumberNoCheck(&itup->t_tid); + + if (child == right_blkno) + { + UnlockReleaseBuffer(parent_buf); + if (stack_out != NULL) + *stack_out = stack; + else + _bt_freestack(stack); + return true; + } + } + } + + UnlockReleaseBuffer(parent_buf); + _bt_freestack(stack); + return false; + +} diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c index 3df2c752ead..268c4c11052 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -37,6 +37,8 @@ #include "utils/index_selfuncs.h" #include "utils/memutils.h" #include "utils/wait_event.h" +#include "utils/injection_point.h" + /* @@ -374,6 +376,12 @@ btbeginscan(Relation rel, int nkeys, int norderbys) */ so->currTuples = so->markTuples = NULL; + /* Initialize merge fields */ + so->skipMergeRecovery = false; + so->needMergeRecovery = false; + so->nSavedMergeTids = 0; + so->mergedAwayBlkno = InvalidBlockNumber; + scan->xs_itupdesc = RelationGetDescr(rel); scan->opaque = so; @@ -427,6 +435,11 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, BTScanPosUnpinIfPinned(so->markPos); BTScanPosInvalidate(so->markPos); + so->skipMergeRecovery = false; + so->needMergeRecovery = false; + so->nSavedMergeTids = 0; + so->mergedAwayBlkno = InvalidBlockNumber; + /* * Allocate tuple workspace arrays, if needed for an index-only scan and * not already done in a previous rescan call. To save on palloc @@ -1518,6 +1531,208 @@ backtrack: * pages_deleted stats in all cases (barring corruption) */ } + else if (P_ISMERGEDAWAY(opaque)) + { + FullTransactionId safemergexid = BTMergedAwayGetSafeXid(page); + + if (GlobalVisCheckRemovableFullXid(heaprel, safemergexid)) + { + BlockNumber tail_blkno; + BlockNumber curr_blkno = opaque->btpo_next; + Buffer curr_buf; + BTPageOpaque curr_opaque; + Buffer next_buf; + BTPageOpaque next_opaque; + BlockNumber next_blkno; + + BlockNumber bwd_blkno; + BlockNumber right_anchor; + Buffer bwd_buf; + Page bwd_page, + curr_page; + BTPageOpaque bwd_opaque; + BlockNumber nextblk; + BTPageOpaqueData saved_opaque; + IndexTupleData trunctuple; + + /* + * We release the MA page lock here because the forward and + * backward walks acquire write locks on M pages. Holding the MA + * read lock across multiple buffer lock acquisitions would + * violate PostgreSQL's lock ordering rules and risk deadlock. The + * pin on buf is retained throughout, preventing the MA page from + * being recycled. + */ + LockBuffer(buf, BUFFER_LOCK_UNLOCK); + + /* Walk Forward to find the tail using lock coupling. */ + curr_buf = _bt_getbuf(rel, curr_blkno, BT_READ); + curr_page = BufferGetPage(curr_buf); + curr_opaque = BTPageGetOpaque(curr_page); + + /* + * If the last VACUUM run cleared all M page flags but stopped + * before clearing the MA page flag, skip straight to finalizing + * the tombstone. + */ + if (!BTPageIsMergedMember(curr_opaque, curr_page, blkno)) + { + _bt_relbuf(rel, curr_buf); + goto finalize_ma; + } + + while (true) + { + next_blkno = curr_opaque->btpo_next; + + if (next_blkno == P_NONE) + { + tail_blkno = curr_blkno; + right_anchor = P_NONE; + _bt_relbuf(rel, curr_buf); + break; + } + + next_buf = _bt_getbuf(rel, next_blkno, BT_READ); + next_opaque = BTPageGetOpaque(BufferGetPage(next_buf)); + + /* End of the merge group reached; stop the forward walk. */ + if (!BTPageIsMergedMember(next_opaque, BufferGetPage(next_buf), blkno)) + { + tail_blkno = curr_blkno; + right_anchor = next_blkno; + _bt_relbuf(rel, curr_buf); + _bt_relbuf(rel, next_buf); + break; + } + + _bt_relbuf(rel, curr_buf); + curr_blkno = next_blkno; + curr_buf = next_buf; + curr_opaque = next_opaque; + } + + /* + * Walk Backward to clear M flags (Stop before hitting the MA + * tombstone!) + */ + bwd_blkno = tail_blkno; + + while (bwd_blkno != blkno) + { + CHECK_FOR_INTERRUPTS(); + + bwd_buf = _bt_getbuf(rel, bwd_blkno, BT_WRITE); + bwd_page = BufferGetPage(bwd_buf); + bwd_opaque = BTPageGetOpaque(bwd_page); + + while (bwd_opaque->btpo_next != right_anchor) + { + nextblk = bwd_opaque->btpo_next; + _bt_relbuf(rel, bwd_buf); + + CHECK_FOR_INTERRUPTS(); + + bwd_buf = _bt_getbuf(rel, nextblk, BT_WRITE); + bwd_page = BufferGetPage(bwd_buf); + bwd_opaque = BTPageGetOpaque(bwd_page); + + if (!BTPageIsMergedMember(bwd_opaque, bwd_page, blkno)) + { + _bt_relbuf(rel, bwd_buf); + /* Lock MA page again before skiping cleanup */ + LockBuffer(buf, BUFFER_LOCK_SHARE); + ereport(WARNING, + (errmsg("merged-away page %u: unexpected page state near block %u, deferring remaining cleanup to a future VACUUM", + blkno, bwd_blkno))); + + goto skip_merge_cleanup; + } + } + + /* + * If we encounter a page from a different merge group, + * something is wrong; skip the remaining cleanup and defer to + * a future VACUUM. This case is very unlikely because: - + * When a page splits, the new page also inherits the M flag. + * - No other VACUUM process runs concurrently on the same + * index, so no other process can reset any page in between. + */ + if (!BTPageIsMergedMember(bwd_opaque, bwd_page, blkno)) + { + _bt_relbuf(rel, bwd_buf); + + /* Lock MA page again before skiping cleanup */ + LockBuffer(buf, BUFFER_LOCK_SHARE); + ereport(WARNING, + (errmsg("merged-away page %u: unexpected page state near block %u, deferring remaining cleanup to a future VACUUM", + blkno, bwd_blkno))); + + goto skip_merge_cleanup; + } + + bwd_opaque->btpo_flags &= ~(BTP_MERGED); + BTMergedPageClearMABlkno(bwd_page); + MarkBufferDirty(bwd_buf); + + /* TODO: (WAL) needs a critical section + XLOG record */ + + right_anchor = BufferGetBlockNumber(bwd_buf); + bwd_blkno = bwd_opaque->btpo_prev; + _bt_relbuf(rel, bwd_buf); + } + + finalize_ma: + + /* We are back at the tombstone(MA) to make it HD */ + + /* Upgrade our read lock to a write lock while keeping the pin! */ + LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE); + + if (!P_ISMERGEDAWAY(opaque) || + !FullTransactionIdEquals(BTMergedAwayGetSafeXid(page), safemergexid)) + { + /* + * Downgrade from exclusive back to share lock before jumping + * to skip_merge_cleanup. The pin is still held, so the brief + * unlock window is safe. btvacuumpage and its caller expect + * buf to exit with a lock held. + */ + LockBuffer(buf, BUFFER_LOCK_UNLOCK); + LockBuffer(buf, BUFFER_LOCK_SHARE); + ereport(WARNING, + (errmsg("merged-away page %u changed concurrently, skipping cleanup", + blkno))); + goto skip_merge_cleanup; + } + + /* _bt_pagedel() stage 2 requires a high key to exist on the page. */ + + saved_opaque = *opaque; + + MemSet(&trunctuple, 0, sizeof(IndexTupleData)); + trunctuple.t_info = sizeof(IndexTupleData); + BTreeTupleSetTopParent(&trunctuple, InvalidBlockNumber); + + START_CRIT_SECTION(); + + PageInit(page, BufferGetPageSize(buf), sizeof(BTPageOpaqueData)); + + if (PageAddItem(page, (IndexTuple) &trunctuple, IndexTupleSize(&trunctuple), + P_HIKEY, false, false) == InvalidOffsetNumber) + elog(PANIC, "could not add dummy high key to half-dead page"); + + opaque = BTPageGetOpaque(page); + *opaque = saved_opaque; + opaque->btpo_flags &= ~(BTP_MERGED_AWAY | BTP_HAS_FULLXID); + opaque->btpo_flags |= BTP_HALF_DEAD; + MarkBufferDirty(buf); + + END_CRIT_SECTION(); + + attempt_pagedel = true; + } + } else if (P_ISLEAF(opaque)) { OffsetNumber deletable[MaxIndexTuplesPerPage]; @@ -1695,6 +1910,8 @@ backtrack: Assert(!attempt_pagedel || nhtidslive == 0); } +skip_merge_cleanup: + if (attempt_pagedel) { MemoryContext oldcontext; diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 5964bc9195e..45990e36fd3 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -26,6 +26,7 @@ #include "utils/injection_point.h" #include "utils/lsyscache.h" #include "utils/rel.h" +#include "utils/injection_point.h" static inline void _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so); @@ -45,7 +46,11 @@ static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, static Buffer _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno, BlockNumber lastcurrblkno); static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir); - +static void _bt_removeduplicates(IndexScanDesc scan); +static void _bt_find_merge_tail(IndexScanDesc scan, BlockNumber m_blkno, BlockNumber *blkno, + BlockNumber *lastcurrblkno); +static void _bt_copylastreadpagedata(IndexScanDesc scan); +static int compare(const void *a, const void *b); /* * _bt_drop_lock_and_maybe_pin() @@ -306,7 +311,7 @@ _bt_moveright(Relation rel, continue; } - if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval) + if (P_IGNORE(opaque) || P_ISMERGEDAWAY(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval) { /* step right one page */ buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access); @@ -1755,6 +1760,26 @@ _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, ScanDirection dir) { BTScanOpaque so = (BTScanOpaque) scan->opaque; + /* + * If the starting page has BTP_MERGED, we descended directly into a merge + * group (rather than stepping from a MERGED_AWAY tombstone). Set + * skipMergeRecovery so the scan loop knows no deduplication is needed for + * the subsequent MERGED pages in this group. + * + * so->currPos.buf is already pinned and locked on entry, so we can safely + * read the page opaque here without any extra locking. + */ + { + Page page = BufferGetPage(so->currPos.buf); + BTPageOpaque opaque = BTPageGetOpaque(page); + + if (P_ISMERGED(opaque)) + { + so->skipMergeRecovery = true; + so->mergedAwayBlkno = BTMergedPageGetMABlkno(page); + } + } + so->numKilled = 0; /* just paranoia */ so->markItemIndex = -1; /* ditto */ @@ -1849,11 +1874,23 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, { Relation rel = scan->indexRelation; BTScanOpaque so = (BTScanOpaque) scan->opaque; + bool needMergeRecoverWalk = false; + BlockNumber m_blkno = InvalidBlockNumber; Assert(so->currPos.currPage == lastcurrblkno || seized); Assert(!(blkno == P_NONE && seized)); Assert(!BTScanPosIsPinned(so->currPos)); + if (strcmp(RelationGetRelationName(rel), "merge_test_idx") == 0 && ScanDirectionIsForward(dir) && blkno == 4) + { + INJECTION_POINT("before_read_next_page", NULL); + } + + if (strcmp(RelationGetRelationName(rel), "merge_test_idx") == 0 && ScanDirectionIsBackward(dir) && blkno == 2) + { + INJECTION_POINT("before_read_prev_page", NULL); + } + /* * Remember that the scan already read lastcurrblkno, a page to the left * of blkno (or remember reading a page to the right, for backwards scans) @@ -1868,6 +1905,8 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, Page page; BTPageOpaque opaque; + needMergeRecoverWalk = false; + if (blkno == P_NONE || (ScanDirectionIsForward(dir) ? !so->currPos.moreRight : !so->currPos.moreLeft)) @@ -1913,8 +1952,21 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, page = BufferGetPage(so->currPos.buf); opaque = BTPageGetOpaque(page); lastcurrblkno = blkno; - if (likely(!P_IGNORE(opaque))) + + + if (likely(!P_IGNORE(opaque) && !P_ISMERGEDAWAY(opaque) && !P_ISMERGED(opaque))) { + /* + * We landed on a normal page. If we were in a merge group, we + * have now exited it. Clear the merge recovery flags so we are + * ready for the next merge group. + */ + if (so->needMergeRecovery || so->skipMergeRecovery) + { + so->needMergeRecovery = false; + so->skipMergeRecovery = false; + } + /* see if there are any matches on this page */ if (ScanDirectionIsForward(dir)) { @@ -1931,7 +1983,7 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, blkno = so->currPos.prevPage; } } - else + else if (unlikely(P_IGNORE(opaque))) { /* _bt_readpage not called, so do all this for ourselves */ if (ScanDirectionIsForward(dir)) @@ -1941,10 +1993,181 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, if (scan->parallel_scan != NULL) _bt_parallel_release(scan, blkno, lastcurrblkno); } + else if (P_ISMERGEDAWAY(opaque)) + { + if (ScanDirectionIsForward(dir)) + { + /* + * Save state indicating we passed a merged away page and + * proceed to the next page + */ + so->skipMergeRecovery = true; + so->mergedAwayBlkno = blkno; + blkno = opaque->btpo_next; + } + else + { + if (so->mergedAwayBlkno != blkno) + { + so->skipMergeRecovery = false; + so->needMergeRecovery = false; + } + + /* + * BACKWARD SCAN: Tombstone (BTP_MERGED_AWAY) + */ + if (so->skipMergeRecovery || so->needMergeRecovery) + { + /* + * We either already saw the merged page + * (skipMergeRecovery), or we just finished walking + * backward through the recovery group + * (needMergeRecovery). In either case, we safely skip + * this tombstone and step left. + */ + blkno = opaque->btpo_prev; + + /* Clear the states since we are exiting the merge group */ + so->skipMergeRecovery = false; + so->needMergeRecovery = false; + } + else + { + /* + * We hit the tombstone but haven't seen the merged page + * yet! This means the merge happened right after we read + * the left page. We must enter recovery mode to find the + * merged tuples. + */ + so->needMergeRecovery = true; + + /* + * 1- Save the TIDs we already read to filter them out + * later + */ + _bt_copylastreadpagedata(scan); + + /* + * 2- Trigger the rightward walk at the end of the loop to + * find the tail page + */ + needMergeRecoverWalk = true; + m_blkno = opaque->btpo_next; /* The start of the merged + * group */ + } + } + } + else if (P_ISMERGED(opaque)) + { + if (ScanDirectionIsForward(dir)) + { + if (BTMergedPageGetMABlkno(page) != so->mergedAwayBlkno) + { + so->skipMergeRecovery = false; + so->mergedAwayBlkno = BTMergedPageGetMABlkno(page); + } + + /* + * Case 1: We passed the BTP_MERGED_AWAY page already and that + * merged away page we have its blkno saved (will do this part + * later). We read this page as a normal page. + */ + if (so->skipMergeRecovery) + { + if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque), seized)) + break; + blkno = so->currPos.nextPage; + } + else + { + /* + * FWD SCAN: Recovery Mode We read the left page before it + * was merged. + */ + if (!so->needMergeRecovery) + { + /* + * First time hitting the merged group! Save L's items + * to filter them out of R and any split descendants. + */ + _bt_copylastreadpagedata(scan); + so->needMergeRecovery = true; + } + + if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque), seized)) + { + _bt_removeduplicates(scan); + + /* + * Only break to return if we still have unfiltered + * tuples + */ + if (so->currPos.lastItem >= so->currPos.firstItem) + break; + } + blkno = so->currPos.nextPage; + } + } + else + { + so->mergedAwayBlkno = BTMergedPageGetMABlkno(page); + + /* + * BACKWARD SCAN: Merged Page (BTP_MERGED) + */ + if (so->needMergeRecovery) + { + /* + * We are currently walking backward through the recovery + * group. Read the page, but filter out tuples we already + * saw. + */ + if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page), seized)) + { + _bt_removeduplicates(scan); + + /* + * Only break to return if we still have unfiltered + * tuples + */ + if (so->currPos.lastItem >= so->currPos.firstItem) + break; + } + + blkno = so->currPos.prevPage; /* Step left to the next + * page in the group */ + } + else + { + /* + * Normal backward scan. We hit a merged page directly. + * Set the skip flag so when we step left onto the + * tombstone, we skip it. + */ + so->skipMergeRecovery = true; + + if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page), seized)) + break; + + blkno = so->currPos.prevPage; + } + } + } /* no matching tuples on this page */ _bt_relbuf(rel, so->currPos.buf); seized = false; /* released by _bt_readpage (or by us) */ + + if (needMergeRecoverWalk) + { + _bt_find_merge_tail(scan, m_blkno, &blkno, &lastcurrblkno); + + /* + * After this call the loop will continue to read blkno page * so + * we now have to how these MERGED pages are going to be read + */ + needMergeRecoverWalk = false; + } } /* @@ -1955,9 +2178,219 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, Assert(BTScanPosIsPinned(so->currPos)); _bt_drop_lock_and_maybe_pin(rel, so); + return true; } + +/* + * _bt_find_merge_tail() -- Find the tail of a MERGED page group for backward scan recovery. + * + * During a backward scan, when the scan discovers it needs merge recovery + * (needMergeRecovery), it must walk forward from the first MERGED page (R) + * to locate the rightmost page in the merge group (the "tail"). This is + * needed so the backward scan can restart from the tail and walk backward + * through the full merge group, deduplicating against savedMergeTids. + * + * m_blkno is the block number of the first MERGED page (the immediate right + * sibling of the MERGED_AWAY tombstone). On return, *blkno is set to the + * tail of the merge group (the last consecutive MERGED page), and + * *lastcurrblkno is set to its right neighbor (the first non-MERGED page), + * which is used as the right anchor for split validation during the + * subsequent backward scan. + * + * Uses lock-coupling (acquire right, release left) to traverse the chain + * safely under concurrent activity. + */ +static void +_bt_find_merge_tail(IndexScanDesc scan, BlockNumber m_blkno, BlockNumber *blkno, + BlockNumber *lastcurrblkno) +{ + Relation rel = scan->indexRelation; + BlockNumber r_blkno, + l_blkno; + Buffer r_buf, + l_buf; + Page r_page, + l_page; + BTPageOpaque r_opaque, + l_opaque; + + /* L <--> R(r_blkno) <--> X <--> Y(tail) <--> Z (first non MERGED page) */ + + /* + * Step 1: Initialize the left page. m_blkno is the first merged page (R) + * we got from the tombstone's btpo_next. + */ + l_blkno = m_blkno; + l_buf = _bt_getbuf(rel, l_blkno, BT_READ); + l_page = BufferGetPage(l_buf); + l_opaque = BTPageGetOpaque(l_page); + + Assert(P_ISMERGED(l_opaque)); + + /* + * Step 2: Lock-couple rightward to find the boundary. Loop till we find a + * non-MERGED page or the rightmost edge. + */ + for (;;) + { + r_blkno = l_opaque->btpo_next; + + /* + * Check if the merged group extends to the rightmost edge of the + * index + */ + if (r_blkno == P_NONE) + { + *blkno = l_blkno; + *lastcurrblkno = P_NONE; /* No page to the right, so no right + * anchor */ + _bt_relbuf(rel, l_buf); + break; + } + + /* Lock the right page */ + r_buf = _bt_getbuf(rel, r_blkno, BT_READ); + r_page = BufferGetPage(r_buf); + r_opaque = BTPageGetOpaque(r_page); + + /* Check if we found the boundary (the first non-merged page) */ + if (!P_ISMERGED(r_opaque)) + { + *blkno = l_blkno; /* The tail of the merged group */ + *lastcurrblkno = r_blkno; /* The right anchor for validation */ + + /* We have our boundary. Unlock both pages before returning. */ + _bt_relbuf(rel, l_buf); + _bt_relbuf(rel, r_buf); + + break; + } + + /* The right page is also merged, so shift right (lock-coupling) */ + + /* Unlock the old left page */ + _bt_relbuf(rel, l_buf); + + /* Make the right page the new left page for the next iteration */ + l_blkno = r_blkno; + l_buf = r_buf; + l_page = r_page; + l_opaque = r_opaque; + } +} + + +/* + * _bt_copylastreadpagedata() -- Snapshot heap TIDs from the last-read page + * into savedMergeTids before they are overwritten. + * + * currPos.items is overwritten by every call to _bt_readpage. When merge + * recovery is triggered (either forward or backward), we must preserve the + * TIDs that were already returned (or about to be returned) from the + * MERGED_AWAY page so that _bt_removeduplicates can filter them out of the + * MERGED pages' contents later. + * + * Copies every heapTid from currPos.items[firstItem..lastItem] into + * so->savedMergeTids and sets so->nSavedMergeTids accordingly. The array + * is sorted in place (using ItemPointerCompare) so that _bt_removeduplicates + * can use bsearch() for O(log n) lookups. + * + * Must be called while currPos still reflects the page whose TIDs we want + * to save, i.e. before the next _bt_readpage call. + */ +static void +_bt_copylastreadpagedata(IndexScanDesc scan) +{ + BTScanOpaque so = (BTScanOpaque) scan->opaque; + int firstItem = so->currPos.firstItem; + int lastItem = so->currPos.lastItem; + ItemPointerData item; + + so->nSavedMergeTids = 0; + + for (int i = firstItem; i <= lastItem; i++) + { + item = so->currPos.items[i].heapTid; + so->savedMergeTids[so->nSavedMergeTids++] = item; + } + + if (so->nSavedMergeTids > 1) + qsort(so->savedMergeTids, so->nSavedMergeTids, sizeof(ItemPointerData), compare); +} + + +/* + * compare() -- ItemPointerData comparator for qsort() and bsearch(). + * + * Used by _bt_copylastreadpagedata to sort savedMergeTids and by + * _bt_removeduplicates to binary-search within that sorted array. + */ +static int +compare(const void *a, const void *b) +{ + return ItemPointerCompare((ItemPointer) a, (ItemPointer) b); +} + +/* + * _bt_removeduplicates() -- Filter out already-seen TIDs from the current page + * during merge-group recovery. + * + * After a concurrent page merge is detected, the MERGED page(s) contain a + * superset of the tuples from both the original left (MERGED_AWAY) and right + * pages. Any TID that was already returned to the caller from the + * MERGED_AWAY page exists in so->savedMergeTids and must be removed from + * currPos.items to prevent duplicates being returned. + * + * Iterates over currPos.items[firstItem..lastItem] and compacts the array + * in-place, retaining only items whose heapTid is NOT found in + * savedMergeTids (which must already be sorted by _bt_copylastreadpagedata). + * Updates currPos.lastItem and resets currPos.itemIndex to the correct + * boundary for the current scan direction. + * + * Must be called immediately after _bt_readpage on each MERGED page during + * recovery, before any items are returned to the caller. + */ +static void +_bt_removeduplicates(IndexScanDesc scan) +{ + BTScanOpaque so = (BTScanOpaque) scan->opaque; + int firstItem = so->currPos.firstItem; + int lastItem = so->currPos.lastItem; + int dest = firstItem; + ItemPointerData *item, + *found; + + /* Filter out items whose heap TIDs are in mergedAwayTids list */ + for (int i = firstItem; i <= lastItem; i++) + { + item = &so->currPos.items[i].heapTid; + + found = (ItemPointerData *) bsearch(item, so->savedMergeTids, so->nSavedMergeTids, sizeof(ItemPointerData), compare); + + if (found) + { + /* Skip duplicate item */ + continue; + } + + /* Retain non duplicate item */ + so->currPos.items[dest] = so->currPos.items[i]; + dest++; + } + so->currPos.lastItem = dest - 1; + + /* + * Update itemIndex to point to the correct boundary for the scan + * direction + */ + if (ScanDirectionIsForward(so->currPos.dir)) + so->currPos.itemIndex = so->currPos.firstItem; + else + so->currPos.itemIndex = so->currPos.lastItem; +} + /* * _bt_lock_and_validate_left() -- lock caller's left sibling blkno, * recovering from concurrent page splits/page deletions when necessary @@ -2150,7 +2583,7 @@ _bt_get_endpoint(Relation rel, uint32 level, bool rightmost) * right if needed to get to it (this could happen if the page split * since we obtained a pointer to it). */ - while (P_IGNORE(opaque) || + while (P_IGNORE(opaque) || P_ISMERGEDAWAY(opaque) || (rightmost && !P_RIGHTMOST(opaque))) { blkno = opaque->btpo_next; diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 014faa1622f..23950f949e0 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -967,7 +967,7 @@ _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum) * We cannot reliably test a deleted or half-dead page, since they have * dummy high keys */ - if (P_IGNORE(opaque)) + if (P_IGNORE(opaque) || P_ISMERGEDAWAY(opaque)) return true; Assert(offnum >= FirstOffsetNumber && diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h index 3097e9bb1af..a5c18319d56 100644 --- a/src/include/access/nbtree.h +++ b/src/include/access/nbtree.h @@ -83,6 +83,9 @@ typedef BTPageOpaqueData *BTPageOpaque; #define BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples (deprecated) */ #define BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling's downlink is missing */ #define BTP_HAS_FULLXID (1 << 8) /* contains BTDeletedPageData */ +#define BTP_MERGED (1 << 9) /* This node contain its lift sibling data */ +#define BTP_MERGED_AWAY (1 << 10) /* This node was merged into its right + * sibling */ /* * The max allowed value of a cycle ID is a bit less than 64K. This is @@ -227,6 +230,103 @@ typedef struct BTMetaPageData #define P_HAS_GARBAGE(opaque) (((opaque)->btpo_flags & BTP_HAS_GARBAGE) != 0) #define P_INCOMPLETE_SPLIT(opaque) (((opaque)->btpo_flags & BTP_INCOMPLETE_SPLIT) != 0) #define P_HAS_FULLXID(opaque) (((opaque)->btpo_flags & BTP_HAS_FULLXID) != 0) +#define P_ISMERGED(opaque) (((opaque)->btpo_flags & BTP_MERGED) != 0) +#define P_ISMERGEDAWAY(opaque) (((opaque)->btpo_flags & BTP_MERGED_AWAY) != 0) + +/* + * Accessors for the MERGED_AWAY block number stored on BTP_MERGED pages. + * + * We store the block number of the corresponding BTP_MERGED_AWAY (tombstone) + * page in pd_prune_xid, which is a 4-byte field in PageHeaderData that is + * explicitly documented as "currently unused in index pages" (see bufpage.h). + * This is the only available 4-byte slot on a MERGED page that may be + * completely full of index tuples -- we cannot extend the special area on + * a full page, and the item content area is occupied by live tuples. + * + * Only valid when P_MERGED(opaque) is true. All other B-tree pages keep + * pd_prune_xid at its default value of InvalidTransactionId (0). + */ +#define BTMergedPageGetMABlkno(page) \ + ((BlockNumber) ((PageHeader)(page))->pd_prune_xid) + +#define BTMergedPageSetMABlkno(page, blkno) \ + (((PageHeader)(page))->pd_prune_xid = (TransactionId)(blkno)) + +/* + * Clear the MA block number from a MERGED page when the BTP_MERGED flag is + * being cleared (e.g., during vacuum cleanup of the merge group). + * Restores pd_prune_xid to its standard value of InvalidTransactionId (0), + * since index pages normally never use that field. + */ +#define BTMergedPageClearMABlkno(page) \ + (((PageHeader)(page))->pd_prune_xid = InvalidTransactionId) + + +typedef struct BTMergedAwayPageData +{ + FullTransactionId safemergexid; +} BTMergedAwayPageData; + +static inline void +BTPageSetMerged(Page page) +{ + BTPageOpaque opaque; + + opaque = BTPageGetOpaque(page); + opaque->btpo_flags |= BTP_MERGED; + +} + +static inline void +BTPageSetMergedAway(Page page, FullTransactionId safemergexid) +{ + BTPageOpaque opaque; + PageHeader header; + BTMergedAwayPageData *contents; + + opaque = BTPageGetOpaque(page); + header = ((PageHeader) page); + + opaque->btpo_flags |= BTP_MERGED_AWAY | BTP_HAS_FULLXID; + header->pd_lower = MAXALIGN(SizeOfPageHeaderData) + + sizeof(BTMergedAwayPageData); + header->pd_upper = header->pd_special; + + contents = (BTMergedAwayPageData *) PageGetContents(page); + contents->safemergexid = safemergexid; +} + +static inline FullTransactionId +BTMergedAwayGetSafeXid(Page page) +{ + BTPageOpaque opaque; + BTMergedAwayPageData *contents; + + opaque = BTPageGetOpaque(page); + Assert(P_ISMERGEDAWAY(opaque)); + + if (!P_HAS_FULLXID(opaque)) + return FirstNormalFullTransactionId; + + contents = (BTMergedAwayPageData *) PageGetContents(page); + return contents->safemergexid; +} + +/* + * BTPageIsMergedMember -- true when a page is a valid member of the merge + * group whose tombstone (MA page) is at ma_blkno. + * + * Used during VACUUM cleanup to validate each M page before clearing its + * flags, preventing accidental absorption of pages from an adjacent group. + */ +static inline bool +BTPageIsMergedMember(BTPageOpaque opq, Page pg, BlockNumber ma_blkno) +{ + return P_ISMERGED(opq) && + P_ISLEAF(opq) && + !P_ISMERGEDAWAY(opq) && + BTMergedPageGetMABlkno(pg) == ma_blkno; +} /* * BTDeletedPageData is the page contents of a deleted page @@ -1092,6 +1192,15 @@ typedef struct BTScanOpaqueData /* keep these last in struct for efficiency */ BTScanPosData currPos; /* current position data */ BTScanPosData markPos; /* marked position, if any */ + + /* Merge information */ + bool skipMergeRecovery; + bool needMergeRecovery; + + ItemPointerData savedMergeTids[MaxTIDsPerBTreePage]; + int nSavedMergeTids; /* number of TIDs in the array */ + BlockNumber mergedAwayBlkno; /* blkno of L (BTP_MERGED_AWAY page) */ + } BTScanOpaqueData; typedef BTScanOpaqueData *BTScanOpaque; @@ -1219,6 +1328,7 @@ extern void _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf, BTStack stack); extern Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child); +extern void _bt_freestack(BTStack stack); /* * prototypes for functions in nbtsplitloc.c @@ -1262,6 +1372,8 @@ extern void _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate); extern void _bt_pendingfsm_init(Relation rel, BTVacState *vstate, bool cleanuponly); extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate); +extern bool _bt_pages_share_parent(Relation rel, BlockNumber left_blkno, + BlockNumber right_blkno, BTScanInsert scankey, BTStack *stack_out); /* * prototypes for functions in nbtpreprocesskeys.c @@ -1331,4 +1443,11 @@ extern IndexBuildResult *btbuild(Relation heap, Relation index, struct IndexInfo *indexInfo); extern void _bt_parallel_build_main(dsm_segment *seg, shm_toc *toc); +/** + * prototypes for functions in nbmerge.c + */ + +extern int32 _bt_merge_index(Relation rel, float8 min_pct, float8 dest_pct, int32 num_pages); + + #endif /* NBTREE_H */ -- 2.43.0
From 0fd478bb14e60207601bc058c19511f3f07e7c36 Mon Sep 17 00:00:00 2001 From: Salma <[email protected]> Date: Wed, 29 Jul 2026 00:09:59 +0300 Subject: [PATCH v2 3/3] amcheck: Add verification for B-tree page merges Extend verify_nbtree to validate structural invariants for merged and tombstone leaf pages. --- contrib/amcheck/verify_nbtree.c | 162 ++++++++++++++++++++++++++++++-- 1 file changed, 155 insertions(+), 7 deletions(-) diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c index 3ef2d66f826..2553ee2b327 100644 --- a/contrib/amcheck/verify_nbtree.c +++ b/contrib/amcheck/verify_nbtree.c @@ -238,6 +238,8 @@ static ItemId PageGetItemIdCareful(BtreeCheckState *state, BlockNumber block, static inline ItemPointer BTreeTupleGetHeapTIDCareful(BtreeCheckState *state, IndexTuple itup, bool nonpivot); static inline ItemPointer BTreeTupleGetPointsToTID(IndexTuple itup); +static void bt_check_ma_page(BtreeCheckState *state); +static void bt_check_m_page(BtreeCheckState *state); /* * bt_index_check(index regclass, heapallindexed boolean, checkunique boolean) @@ -661,7 +663,7 @@ bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level) opaque = BTPageGetOpaque(state->target); - if (P_IGNORE(opaque)) + if (P_IGNORE(opaque) || P_ISMERGEDAWAY(opaque)) { /* * Since there cannot be a concurrent VACUUM operation in readonly @@ -682,6 +684,9 @@ bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level) errdetail_internal("Block=%u left block=%u left link from block=%u.", current, leftcurrent, opaque->btpo_prev))); + if (P_ISMERGEDAWAY(opaque)) + bt_check_ma_page(state); + if (P_RIGHTMOST(opaque)) ereport(ERROR, (errcode(ERRCODE_INDEX_CORRUPTED), @@ -818,7 +823,7 @@ nextpage: * splits wasn't investigated yet. Thankfully we only need low key * for readonly verification and concurrent splits won't happen. */ - if (state->readonly && !P_RIGHTMOST(opaque)) + if (state->readonly && !P_RIGHTMOST(opaque) && !P_ISMERGEDAWAY(opaque)) { IndexTuple itup; ItemId itemid; @@ -1281,6 +1286,9 @@ bt_target_page_check(BtreeCheckState *state) } } + if (P_ISMERGED(topaque)) + bt_check_m_page(state); + /* * Loop over page items, starting from first non-highkey item, not high * key (if any). Most tests are not performed for the "negative infinity" @@ -1740,7 +1748,7 @@ bt_target_page_check(BtreeCheckState *state) /* * All !readonly checks now performed; just return */ - if (P_IGNORE(topaque)) + if (P_IGNORE(topaque) || P_ISMERGEDAWAY(topaque)) return; } @@ -1790,7 +1798,7 @@ bt_target_page_check(BtreeCheckState *state) rightblock_number); topaque = BTPageGetOpaque(rightpage); - if (P_IGNORE(topaque)) + if (P_IGNORE(topaque) || P_ISMERGEDAWAY(topaque)) { pfree(rightpage); break; @@ -1912,7 +1920,7 @@ bt_right_page_check_scankey(BtreeCheckState *state, OffsetNumber *rightfirstoffs rightpage = palloc_btree_page(state, targetnext); opaque = BTPageGetOpaque(rightpage); - if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque)) + if ((!P_IGNORE(opaque) && !P_ISMERGEDAWAY(opaque)) || P_RIGHTMOST(opaque)) break; /* @@ -2258,7 +2266,8 @@ bt_child_highkey_check(BtreeCheckState *state, * If we visit page with high key, check that it is equal to the * target key next to corresponding downlink. */ - if (!rightsplit && !P_RIGHTMOST(opaque) && !P_ISHALFDEAD(opaque)) + if (!rightsplit && !P_RIGHTMOST(opaque) && !P_ISHALFDEAD(opaque) && + !P_ISMERGEDAWAY(opaque)) { BTPageOpaque topaque; IndexTuple highkey; @@ -2497,6 +2506,22 @@ bt_child_check(BtreeCheckState *state, BTScanInsert targetkey, state->targetblock, childblock, LSN_FORMAT_ARGS(state->targetlsn)))); + /* + * A merged-away (MA) page is a tombstone that should have had its parent + * downlink redirected to the merged destination page (R) during the merge + * operation. In readonly mode, no concurrent merge can be in progress, so + * finding a downlink to an MA page indicates corruption. + */ + if (P_ISMERGEDAWAY(copaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("downlink to merged-away page found in index \"%s\"", + RelationGetRelationName(state->rel)), + errdetail_internal("Parent block=%u child block=%u parent page lsn=%X/%08X.", + state->targetblock, childblock, + LSN_FORMAT_ARGS(state->targetlsn)))); + + for (offset = P_FIRSTDATAKEY(copaque); offset <= maxoffset; offset = OffsetNumberNext(offset)) @@ -2611,6 +2636,13 @@ bt_downlink_missing_check(BtreeCheckState *state, bool rightsplit, return; } + /* + * A merged-away leaf page intentionally lacks a parent downlink, as it + * was unlinked during the custom bt_merge operation. + */ + if (P_ISMERGEDAWAY(opaque)) + return; + /* * Page under check is probably the "top parent" of a multi-level page * deletion. We'll need to descend the subtree to make sure that @@ -3435,7 +3467,7 @@ palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum) errmsg_internal("internal page block %u in index \"%s\" has garbage items", blocknum, RelationGetRelationName(state->rel)))); - if (P_HAS_FULLXID(opaque) && !P_ISDELETED(opaque)) + if (P_HAS_FULLXID(opaque) && (!P_ISDELETED(opaque) && !P_ISMERGEDAWAY(opaque))) ereport(ERROR, (errcode(ERRCODE_INDEX_CORRUPTED), errmsg_internal("full transaction id page flag appears in non-deleted block %u in index \"%s\"", @@ -3591,3 +3623,119 @@ BTreeTupleGetPointsToTID(IndexTuple itup) /* Pivot tuple returns TID with downlink block (heapkeyspace variant) */ return &itup->t_tid; } + + +static void +bt_check_ma_page(BtreeCheckState *state) +{ + Page page = state->target; + BlockNumber block = state->targetblock; + BTPageOpaque opaque = BTPageGetOpaque(page); + + + if (!P_ISLEAF(opaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged-away block %u is not a leaf page in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + if (P_ISROOT(opaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged-away block %u cannot be root page in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + + if (P_ISMERGED(opaque) || P_ISHALFDEAD(opaque) || P_ISDELETED(opaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged-away block %u has conflicting page flags in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + if (opaque->btpo_next == P_NONE) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged-away block %u lacks right sibling in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + if (!P_HAS_FULLXID(opaque) || + !FullTransactionIdIsValid(BTMergedAwayGetSafeXid(page))) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged-away block %u has invalid safemergexid in index \"%s\"", + block, RelationGetRelationName(state->rel)))); +} + +static void +bt_check_m_page(BtreeCheckState *state) +{ + Page page = state->target; + BlockNumber block = state->targetblock; + BTPageOpaque opaque = BTPageGetOpaque(page); + + BlockNumber ma_blkno; + Page ma_page; + BTPageOpaque ma_opaque; + + if (!P_ISLEAF(opaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged page %u is not a leaf page in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + if (P_ISMERGEDAWAY(opaque)) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged page %u cannot also be a merged-away tombstone in index \"%s\"", + block, RelationGetRelationName(state->rel)))); + + ma_blkno = BTMergedPageGetMABlkno(page); + + if (!BlockNumberIsValid(ma_blkno) || + ma_blkno == BTREE_METAPAGE || + ma_blkno == block) + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged page %u has invalid MA block number %u in index \"%s\"", + block, ma_blkno, RelationGetRelationName(state->rel)))); + + ma_page = palloc_btree_page(state, ma_blkno); + ma_opaque = BTPageGetOpaque(ma_page); + + if (state->readonly && !P_ISMERGEDAWAY(ma_opaque)) + { + pfree(ma_page); + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("merged page %u points to MA block %u which is not a merged-away tombstone in index \"%s\"", + block, ma_blkno, RelationGetRelationName(state->rel)))); + } + + pfree(ma_page); + + /* + * Verify adjacent merge group consistency: In readonly mode (where no + * concurrent VACUUM/merge can occur), if the right sibling is also an M + * page, it must belong to the same merge group (i.e. name the exact same + * MA block number). + */ + if (state->readonly && opaque->btpo_next != P_NONE) + { + Page next_page = palloc_btree_page(state, opaque->btpo_next); + BTPageOpaque next_opaque = BTPageGetOpaque(next_page); + + if (P_ISMERGED(next_opaque) && + BTMergedPageGetMABlkno(next_page) != ma_blkno) + { + BlockNumber next_ma = BTMergedPageGetMABlkno(next_page); + + pfree(next_page); + ereport(ERROR, + (errcode(ERRCODE_INDEX_CORRUPTED), + errmsg("adjacent merged pages %u and %u have inconsistent MA block numbers (%u vs %u) in index \"%s\"", + block, opaque->btpo_next, ma_blkno, next_ma, + RelationGetRelationName(state->rel)))); + } + pfree(next_page); + } +} -- 2.43.0
