public inbox for [email protected]
help / color / mirror / Atom feedFrom: Alexander Korotkov <[email protected]>
To: Mark Dilger <[email protected]>
Cc: Pavel Borisov <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: Noah Misch <[email protected]>
Cc: Peter Eisentraut <[email protected]>
Cc: Aleksander Alekseev <[email protected]>
Cc: Postgres hackers <[email protected]>
Cc: Maxim Orlov <[email protected]>
Cc: Andres Freund <[email protected]>
Cc: Greg Stark <[email protected]>
Cc: Julien Rouhaud <[email protected]>
Cc: David Steele <[email protected]>
Cc: Peter Geoghegan <[email protected]>
Cc: Maxim Orlov <[email protected]>
Cc: [email protected]
Subject: Re: [PATCH] Improve amcheck to also check UNIQUE constraint in btree index.
Date: Mon, 13 May 2024 04:42:20 +0300
Message-ID: <CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com> (raw)
In-Reply-To: <CAPpHfdu4jF3TrML0rcNczYcf__xXRycKzn2Vi+kKgiYNNC0w-A@mail.gmail.com>
References: <CALT9ZEG9Zk5TxuDTnZPGe9H+b7DL40gXfeouWCaZ3A70yvyWLw@mail.gmail.com>
<CALT9ZEG1YAfPBH-ZMnK-cxu0SDdrV_w0QEBs9BLHfWvddpOHFA@mail.gmail.com>
<[email protected]>
<CACG=ezbRVZrdTguWphiFP-L2cCi_jy+spZA0wPJWA806B0=2dQ@mail.gmail.com>
<CACG=ezYk7up-BUL30SrGozURYWt97BK2f=XhUL6S+qU3F9qVzQ@mail.gmail.com>
<CAJ7c6TOe-ifS9JAqhk-5rPrAbnfGkxNYQiWnR6CUaAqLP31T6A@mail.gmail.com>
<CAPpHfduqJ9QCOrXDjkPxPRxJRws1FgFELwB2Yz3L6-n7FQMsrA@mail.gmail.com>
<[email protected]>
<CAPpHfdvY7UitNMgUKVx73+W_6STCRoiRBmoE2t7WP1-KBodT+g@mail.gmail.com>
<CALT9ZEFY-vsL4-cxta49wP=H7RjDaZk+Wg-ft4m-kVS_=WMsAQ@mail.gmail.com>
<[email protected]>
<CAPpHfdsLcQ2w24r9CCNVwaDwKMXabQzG15KwSaaqMAczF1DdVg@mail.gmail.com>
<CAPpHfdvxK+KSDqopaVdmCHgbO92AN4ibrbiCJ6i6-+g4oma-6Q@mail.gmail.com>
<[email protected]>
<CAPpHfdstoBC7TLsLZ5eKUW7LNHcVo2d5X4msmgsigb7nxiD-5A@mail.gmail.com>
<CALT9ZEFS8z2KoZ9omyfVyz-h54DSPP_jLp5Zc3Fzt6g1Fnw9MA@mail.gmail.com>
<[email protected]>
<CAPpHfduspEtrBN_BrAg90iW1VdoJcdTH7Hnx68GeiEqpAfocpg@mail.gmail.com>
<[email protected]>
<CAPpHfdu4jF3TrML0rcNczYcf__xXRycKzn2Vi+kKgiYNNC0w-A@mail.gmail.com>
On Mon, May 13, 2024 at 12:23 AM Alexander Korotkov
<[email protected]> wrote:
> On Sat, May 11, 2024 at 4:13 AM Mark Dilger
> <[email protected]> wrote:
> > > On May 10, 2024, at 12:05 PM, Alexander Korotkov <[email protected]> wrote:
> > > The only bt_target_page_check() caller is
> > > bt_check_level_from_leftmost(), which overrides state->target in the
> > > next iteration anyway. I think the patch is just refactoring to
> > > eliminate the confusion pointer by Peter Geoghegan upthread.
> >
> > I find your argument unconvincing.
> >
> > After bt_target_page_check() returns at line 919, and before bt_check_level_from_leftmost() overrides state->target in the next iteration, bt_check_level_from_leftmost() conditionally fetches an item from the page referenced by state->target. See line 963.
> >
> > I'm left with four possibilities:
> >
> >
> > 1) bt_target_page_check() never gets to the code that uses "rightpage" rather than "state->target" in the same iteration where bt_check_level_from_leftmost() conditionally fetches an item from state->target, so the change you're making doesn't matter.
> >
> > 2) The code prior to v2-0003 was wrong, having changed state->target in an inappropriate way, causing the wrong thing to happen at what is now line 963. The patch fixes the bug, because state->target no longer gets overwritten where you are now using "rightpage" for the value.
> >
> > 3) The code used to work, having set up state->target correctly in the place where you are now using "rightpage", but v2-0003 has broken that.
> >
> > 4) It's been broken all along and your patch just changes from wrong to wrong.
> >
> >
> > If you believe (1) is true, then I'm complaining that you are relying far to much on action at a distance, and that you are not documenting it. Even with documentation of this interrelationship, I'd be unhappy with how brittle the code is. I cannot easily discern that the two don't ever happen in the same iteration, and I'm not at all convinced one way or the other. I tried to set up some Asserts about that, but none of the test cases actually reach the new code, so adding Asserts doesn't help to investigate the question.
> >
> > If (2) is true, then I'm complaining that the commit message doesn't mention the fact that this is a bug fix. Bug fixes should be clearly documented as such, otherwise future work might assume the commit can be reverted with only stylistic consequences.
> >
> > If (3) is true, then I'm complaining that the patch is flat busted.
> >
> > If (4) is true, then maybe we should revert the entire feature, or have a discussion of mitigation efforts that are needed.
> >
> > Regardless of which of 1..4 you pick, I think it could all do with more regression test coverage.
> >
> >
> > For reference, I said something similar earlier today in another email to this thread:
> >
> > This patch introduces a change that stores a new page into variable "rightpage" rather than overwriting "state->target", which the old implementation most certainly did. That means that after returning from bt_target_page_check() into the calling function bt_check_level_from_leftmost() the value in state->target is not what it would have been prior to this patch. Now, that'd be irrelevant if nobody goes on to consult that value, but just 44 lines further down in bt_check_level_from_leftmost() state->target is clearly used. So the behavior at that point is changing between the old and new versions of the code, and I think I'm within reason to ask if it was wrong before the patch, wrong after the patch, or something else? Is this a bug being introduced, being fixed, or ... ?
>
> Thank you for your analysis. I'm inclined to believe in 2, but not
> yet completely sure. It's really pity that our tests don't cover
> this. I'm investigating this area.
It seems that I got to the bottom of this. Changing
BtreeCheckState.target for a cross-page unique constraint check is
wrong, but that happens only for leaf pages. After that
BtreeCheckState.target is only used for setting the low key. The low
key is only used for non-leaf pages. So, that didn't lead to any
visible bug. I've revised the commit message to reflect this.
So, the picture for the patches is the following now.
0001 – optimization, but rather simple and giving huge effect
0002 – refactoring
0003 – fix for the bug
0004 – better error reporting
------
Regards,
Alexander Korotkov
Attachments:
[application/octet-stream] v3-0002-amcheck-Refactoring-the-storage-of-the-last-visib.patch (11.0K, ../CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com/2-v3-0002-amcheck-Refactoring-the-storage-of-the-last-visib.patch)
download | inline diff:
From 7014fa433ba5c3c6ea645b13d433a11f4b5a0b15 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Fri, 10 May 2024 03:08:07 +0300
Subject: [PATCH v3 2/4] amcheck: Refactoring the storage of the last visible
entry
This commit introduces a new data structure BtreeLastVisibleEntry comprising
information about the last visible heap entry with the current value of key.
Usage of this data structure allows us to avoid passing all this information
as individual function arguments.
Reported-by: Alexander Korotkov
Discussion: https://www.postgresql.org/message-id/CAPpHfdsVbB9ToriaB1UHuOKwjKxiZmTFQcEF%3DjuzzC_nby31uA%40mail.gmail.com
Author: Pavel Borisov, Alexander Korotkov
---
contrib/amcheck/verify_nbtree.c | 125 +++++++++++++++----------------
src/tools/pgindent/typedefs.list | 1 +
2 files changed, 61 insertions(+), 65 deletions(-)
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index c7be785f88b..b433cb33254 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -145,6 +145,19 @@ typedef struct BtreeLevel
bool istruerootlevel;
} BtreeLevel;
+/*
+ * Information about the last visible entry with current B-tree key. Used
+ * for validation of the unique constraint.
+ */
+typedef struct BtreeLastVisibleEntry
+{
+ BlockNumber blkno; /* Index block */
+ OffsetNumber offset; /* Offset on index block */
+ int postingIndex; /* Number in the posting list (-1 for
+ * non-deduplicated tuples) */
+ ItemPointer tid; /* Heap tid */
+} BtreeLastVisibleEntry;
+
PG_FUNCTION_INFO_V1(bt_index_check);
PG_FUNCTION_INFO_V1(bt_index_parent_check);
@@ -165,17 +178,13 @@ static void bt_recheck_sibling_links(BtreeCheckState *state,
BlockNumber btpo_prev_from_target,
BlockNumber leftcurrent);
static bool heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid);
-static void bt_report_duplicate(BtreeCheckState *state, ItemPointer tid,
- BlockNumber block, OffsetNumber offset,
- int posting, ItemPointer nexttid,
+static void bt_report_duplicate(BtreeCheckState *state, BtreeLastVisibleEntry *lVis,
+ ItemPointer nexttid,
BlockNumber nblock, OffsetNumber noffset,
int nposting);
static void bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
BlockNumber targetblock,
- OffsetNumber offset, int *lVis_i,
- ItemPointer *lVis_tid,
- OffsetNumber *lVis_offset,
- BlockNumber *lVis_block);
+ OffsetNumber offset, BtreeLastVisibleEntry *lVis);
static void bt_target_page_check(BtreeCheckState *state);
static BTScanInsert bt_right_page_check_scankey(BtreeCheckState *state,
OffsetNumber *rightfirstoffset);
@@ -997,8 +1006,7 @@ heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid)
*/
static void
bt_report_duplicate(BtreeCheckState *state,
- ItemPointer tid, BlockNumber block, OffsetNumber offset,
- int posting,
+ BtreeLastVisibleEntry *lVis,
ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset,
int nposting)
{
@@ -1010,18 +1018,18 @@ bt_report_duplicate(BtreeCheckState *state,
*pnposting = "";
htid = psprintf("tid=(%u,%u)",
- ItemPointerGetBlockNumberNoCheck(tid),
- ItemPointerGetOffsetNumberNoCheck(tid));
+ ItemPointerGetBlockNumberNoCheck(lVis->tid),
+ ItemPointerGetOffsetNumberNoCheck(lVis->tid));
nhtid = psprintf("tid=(%u,%u)",
ItemPointerGetBlockNumberNoCheck(nexttid),
ItemPointerGetOffsetNumberNoCheck(nexttid));
- itid = psprintf("tid=(%u,%u)", block, offset);
+ itid = psprintf("tid=(%u,%u)", lVis->blkno, lVis->offset);
- if (nblock != block || noffset != offset)
+ if (nblock != lVis->blkno || noffset != lVis->offset)
nitid = psprintf(" tid=(%u,%u)", nblock, noffset);
- if (posting >= 0)
- pposting = psprintf(" posting %u", posting);
+ if (lVis->postingIndex >= 0)
+ pposting = psprintf(" posting %u", lVis->postingIndex);
if (nposting >= 0)
pnposting = psprintf(" posting %u", nposting);
@@ -1038,9 +1046,7 @@ bt_report_duplicate(BtreeCheckState *state,
/* Check if current nbtree leaf entry complies with UNIQUE constraint */
static void
bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
- BlockNumber targetblock, OffsetNumber offset, int *lVis_i,
- ItemPointer *lVis_tid, OffsetNumber *lVis_offset,
- BlockNumber *lVis_block)
+ BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)
{
ItemPointer tid;
bool has_visible_entry = false;
@@ -1049,7 +1055,7 @@ bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
/*
* Current tuple has posting list. Report duplicate if TID of any posting
- * list entry is visible and lVis_tid is valid.
+ * list entry is visible and lVis->tid is valid.
*/
if (BTreeTupleIsPosting(itup))
{
@@ -1059,11 +1065,10 @@ bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
if (heap_entry_is_visible(state, tid))
{
has_visible_entry = true;
- if (ItemPointerIsValid(*lVis_tid))
+ if (ItemPointerIsValid(lVis->tid))
{
bt_report_duplicate(state,
- *lVis_tid, *lVis_block,
- *lVis_offset, *lVis_i,
+ lVis,
tid, targetblock,
offset, i);
}
@@ -1073,13 +1078,13 @@ bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
* between the posting list entries of the first tuple on the
* page after cross-page check.
*/
- if (*lVis_block != targetblock && ItemPointerIsValid(*lVis_tid))
+ if (lVis->blkno != targetblock && ItemPointerIsValid(lVis->tid))
return;
- *lVis_i = i;
- *lVis_tid = tid;
- *lVis_offset = offset;
- *lVis_block = targetblock;
+ lVis->blkno = targetblock;
+ lVis->offset = offset;
+ lVis->postingIndex = i;
+ lVis->tid = tid;
}
}
}
@@ -1087,7 +1092,7 @@ bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
/*
* Current tuple has no posting list. If TID is visible save info about it
* for the next comparisons in the loop in bt_target_page_check(). Report
- * duplicate if lVis_tid is already valid.
+ * duplicate if lVis->tid is already valid.
*/
else
{
@@ -1095,37 +1100,38 @@ bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup,
if (heap_entry_is_visible(state, tid))
{
has_visible_entry = true;
- if (ItemPointerIsValid(*lVis_tid))
+ if (ItemPointerIsValid(lVis->tid))
{
bt_report_duplicate(state,
- *lVis_tid, *lVis_block,
- *lVis_offset, *lVis_i,
+ lVis,
tid, targetblock,
offset, -1);
}
- *lVis_i = -1;
- *lVis_tid = tid;
- *lVis_offset = offset;
- *lVis_block = targetblock;
+
+ lVis->blkno = targetblock;
+ lVis->offset = offset;
+ lVis->tid = tid;
+ lVis->postingIndex = -1;
}
}
- if (!has_visible_entry && *lVis_block != InvalidBlockNumber &&
- *lVis_block != targetblock)
+ if (!has_visible_entry &&
+ lVis->blkno != InvalidBlockNumber &&
+ lVis->blkno != targetblock)
{
char *posting = "";
- if (*lVis_i >= 0)
- posting = psprintf(" posting %u", *lVis_i);
+ if (lVis->postingIndex >= 0)
+ posting = psprintf(" posting %u", lVis->postingIndex);
ereport(DEBUG1,
(errcode(ERRCODE_NO_DATA),
errmsg("index uniqueness can not be checked for index tid=(%u,%u) in index \"%s\"",
targetblock, offset,
RelationGetRelationName(state->rel)),
errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
- *lVis_block, *lVis_offset, posting,
- ItemPointerGetBlockNumberNoCheck(*lVis_tid),
- ItemPointerGetOffsetNumberNoCheck(*lVis_tid)),
+ lVis->blkno, lVis->offset, posting,
+ ItemPointerGetBlockNumberNoCheck(lVis->tid),
+ ItemPointerGetOffsetNumberNoCheck(lVis->tid)),
errhint("VACUUM the table and repeat the check.")));
}
}
@@ -1372,12 +1378,8 @@ bt_target_page_check(BtreeCheckState *state)
OffsetNumber max;
BTPageOpaque topaque;
- /* last visible entry info for checking indexes with unique constraint */
- int lVis_i = -1; /* the position of last visible item for
- * posting tuple. for non-posting tuple (-1) */
- ItemPointer lVis_tid = NULL;
- BlockNumber lVis_block = InvalidBlockNumber;
- OffsetNumber lVis_offset = InvalidOffsetNumber;
+ /* Last visible entry info for checking indexes with unique constraint */
+ BtreeLastVisibleEntry lVis = {InvalidBlockNumber, InvalidOffsetNumber, -1, NULL};
topaque = BTPageGetOpaque(state->target);
max = PageGetMaxOffsetNumber(state->target);
@@ -1784,11 +1786,9 @@ bt_target_page_check(BtreeCheckState *state)
*/
if (state->checkunique && state->indexinfo->ii_Unique &&
P_ISLEAF(topaque) && !skey->anynullkeys &&
- (BTreeTupleIsPosting(itup) || ItemPointerIsValid(lVis_tid)))
+ (BTreeTupleIsPosting(itup) || ItemPointerIsValid(lVis.tid)))
{
- bt_entry_unique_check(state, itup, state->targetblock, offset,
- &lVis_i, &lVis_tid, &lVis_offset,
- &lVis_block);
+ bt_entry_unique_check(state, itup, state->targetblock, offset, &lVis);
unique_checked = true;
}
@@ -1816,17 +1816,16 @@ bt_target_page_check(BtreeCheckState *state)
if (_bt_compare(state->rel, skey, state->target,
OffsetNumberNext(offset)) != 0 || skey->anynullkeys)
{
- lVis_i = -1;
- lVis_tid = NULL;
- lVis_block = InvalidBlockNumber;
- lVis_offset = InvalidOffsetNumber;
+ lVis.blkno = InvalidBlockNumber;
+ lVis.offset = InvalidOffsetNumber;
+ lVis.postingIndex = -1;
+ lVis.tid = NULL;
}
else if (!unique_checked)
{
- bt_entry_unique_check(state, itup, state->targetblock, offset,
- &lVis_i, &lVis_tid, &lVis_offset,
- &lVis_block);
+ bt_entry_unique_check(state, itup, state->targetblock, offset, &lVis);
}
+
skey->scantid = scantid; /* Restore saved scan key state */
}
@@ -1916,9 +1915,7 @@ bt_target_page_check(BtreeCheckState *state)
* postponed.
*/
if (!unique_checked)
- bt_entry_unique_check(state, itup, state->targetblock, offset,
- &lVis_i, &lVis_tid, &lVis_offset,
- &lVis_block);
+ bt_entry_unique_check(state, itup, state->targetblock, offset, &lVis);
elog(DEBUG2, "cross page equal keys");
state->target = palloc_btree_page(state,
@@ -1933,9 +1930,7 @@ bt_target_page_check(BtreeCheckState *state)
rightfirstoffset);
itup = (IndexTuple) PageGetItem(state->target, itemid);
- bt_entry_unique_check(state, itup, rightblock_number, rightfirstoffset,
- &lVis_i, &lVis_tid, &lVis_offset,
- &lVis_block);
+ bt_entry_unique_check(state, itup, rightblock_number, rightfirstoffset, &lVis);
}
}
}
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 34ec87a85eb..8d24418fe3c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -315,6 +315,7 @@ BrinStatsData
BrinTuple
BrinValues
BtreeCheckState
+BtreeLastVisibleEntry
BtreeLevel
Bucket
BufFile
--
2.39.3 (Apple Git-145)
[application/octet-stream] v3-0004-amcheck-Report-an-error-when-the-next-page-to-a-l.patch (2.5K, ../CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com/3-v3-0004-amcheck-Report-an-error-when-the-next-page-to-a-l.patch)
download | inline diff:
From b4645780074cdb0a3abdb7c84435d6abad4e3bec Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Fri, 10 May 2024 03:07:22 +0300
Subject: [PATCH v3 4/4] amcheck: Report an error when the next page to a leaf
is not a leaf
This is a very unlikely condition during checking a B-tree unique constraint,
meaning that the index structure is violated badly, and we shouldn't continue
checking to avoid endless loops, etc. So it's worth immediately throwing an
error.
Reported-by: Peter Geoghegan
Discussion: https://postgr.es/m/CAH2-Wzk%2B2116uOXdOViA27SHcr31WKPgmjsxXLBs_aTxAeThzg%40mail.gmail.com
Author: Pavel Borisov
---
contrib/amcheck/verify_nbtree.c | 22 ++++++++++++++++------
1 file changed, 16 insertions(+), 6 deletions(-)
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index 977f8b6799d..e9bbc18c4a5 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -1849,7 +1849,6 @@ bt_target_page_check(BtreeCheckState *state)
if (offset == max)
{
BTScanInsert rightkey;
- BlockNumber rightblock_number;
/* first offset on a right index page (log only) */
OffsetNumber rightfirstoffset = InvalidOffsetNumber;
@@ -1894,10 +1893,11 @@ bt_target_page_check(BtreeCheckState *state)
* If index has unique constraint make sure that no more than one
* found equal items is visible.
*/
- rightblock_number = topaque->btpo_next;
if (state->checkunique && state->indexinfo->ii_Unique &&
- rightkey && P_ISLEAF(topaque) && rightblock_number != P_NONE)
+ rightkey && P_ISLEAF(topaque) && !P_RIGHTMOST(topaque))
{
+ BlockNumber rightblock_number = topaque->btpo_next;
+
elog(DEBUG2, "check cross page unique condition");
/*
@@ -1924,9 +1924,19 @@ bt_target_page_check(BtreeCheckState *state)
rightblock_number);
topaque = BTPageGetOpaque(rightpage);
- if (P_IGNORE(topaque) || !P_ISLEAF(topaque))
- break;
-
+ if (P_IGNORE(topaque))
+ {
+ if (unlikely(!P_ISLEAF(topaque)))
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("right block of leaf block is non-leaf for index \"%s\"",
+ RelationGetRelationName(state->rel)),
+ errdetail_internal("Block=%u page lsn=%X/%X.",
+ state->targetblock,
+ LSN_FORMAT_ARGS(state->targetlsn))));
+ else
+ break;
+ }
itemid = PageGetItemIdCareful(state, rightblock_number,
rightpage,
rightfirstoffset);
--
2.39.3 (Apple Git-145)
[application/octet-stream] v3-0003-amcheck-Don-t-load-the-right-sibling-page-into-Bt.patch (2.8K, ../CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com/4-v3-0003-amcheck-Don-t-load-the-right-sibling-page-into-Bt.patch)
download | inline diff:
From e9041f10384250472a54bd75a1cf28f89ec15e32 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Mon, 13 May 2024 04:18:56 +0300
Subject: [PATCH v3 3/4] amcheck: Don't load the right sibling page into
BtreeCheckState
5ae2087202 implemented a cross-page unique constraint check by loading
the right sibling to the BtreeCheckState.target variable. This is wrong,
because bt_target_page_check() shouldn't change the target page. Also,
BtreeCheckState.target shouldn't be changed alone without
BtreeCheckState.targetblock.
However, the above didn't cause any visible bugs for the following reasons.
1. We do a cross-page unique constraint check only for leaf index pages.
2. The only way target page get accessed after a cross-page unique constraint
check is loading of the lowkey.
3. The only place lowkey is used is bt_child_highkey_check(), and that applies
only to non-leafs.
The reasons above don't diminish the fact that changing BtreeCheckState.target
for a cross-page unique constraint check is wrong. This commit changes this
check to temporarily store the right sibling to the local variable.
Reported-by: Peter Geoghegan
Discussion: https://postgr.es/m/CAH2-Wzk%2B2116uOXdOViA27SHcr31WKPgmjsxXLBs_aTxAeThzg%40mail.gmail.com
Author: Pavel Borisov
---
contrib/amcheck/verify_nbtree.c | 14 +++++++++-----
1 file changed, 9 insertions(+), 5 deletions(-)
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index b433cb33254..977f8b6799d 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -1910,6 +1910,8 @@ bt_target_page_check(BtreeCheckState *state)
/* The first key on the next page is the same */
if (_bt_compare(state->rel, rightkey, state->target, max) == 0 && !rightkey->anynullkeys)
{
+ Page rightpage;
+
/*
* Do the bt_entry_unique_check() call if it was
* postponed.
@@ -1918,19 +1920,21 @@ bt_target_page_check(BtreeCheckState *state)
bt_entry_unique_check(state, itup, state->targetblock, offset, &lVis);
elog(DEBUG2, "cross page equal keys");
- state->target = palloc_btree_page(state,
- rightblock_number);
- topaque = BTPageGetOpaque(state->target);
+ rightpage = palloc_btree_page(state,
+ rightblock_number);
+ topaque = BTPageGetOpaque(rightpage);
if (P_IGNORE(topaque) || !P_ISLEAF(topaque))
break;
itemid = PageGetItemIdCareful(state, rightblock_number,
- state->target,
+ rightpage,
rightfirstoffset);
- itup = (IndexTuple) PageGetItem(state->target, itemid);
+ itup = (IndexTuple) PageGetItem(rightpage, itemid);
bt_entry_unique_check(state, itup, rightblock_number, rightfirstoffset, &lVis);
+
+ pfree(rightpage);
}
}
}
--
2.39.3 (Apple Git-145)
[application/octet-stream] v3-0001-amcheck-Optimize-speed-of-checking-for-unique-con.patch (3.8K, ../CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com/5-v3-0001-amcheck-Optimize-speed-of-checking-for-unique-con.patch)
download | inline diff:
From f801783ade88e524b73acfa19f1b06e5b54608df Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Fri, 10 May 2024 03:07:53 +0300
Subject: [PATCH v3 1/4] amcheck: Optimize speed of checking for unique
constraint violation
Currently, when amcheck validates a unique constraint, it visits the heap for
each index tuple. This commit implements skipping keys, which have only one
non-dedeuplicated index tuple (quite common case for unique indexes). That
gives substantial economy on index checking time.
Reported-by: Noah Misch
Discussion: https://postgr.es/m/20240325020323.fd.nmisch%40google.com
Author: Alexander Korotkov, Pavel Borisov
---
contrib/amcheck/verify_nbtree.c | 35 +++++++++++++++++++++++++++++++--
1 file changed, 33 insertions(+), 2 deletions(-)
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index 70f65b645a6..c7be785f88b 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -1429,6 +1429,13 @@ bt_target_page_check(BtreeCheckState *state)
bool lowersizelimit;
ItemPointer scantid;
+ /*
+ * True if we already called bt_entry_unique_check() for the current
+ * item. This helps to avoid visiting the heap for keys, which are
+ * anyway presented only once and can't comprise a unique violation.
+ */
+ bool unique_checked = false;
+
CHECK_FOR_INTERRUPTS();
itemid = PageGetItemIdCareful(state, state->targetblock,
@@ -1771,13 +1778,19 @@ bt_target_page_check(BtreeCheckState *state)
/*
* If the index is unique verify entries uniqueness by checking the
- * heap tuples visibility.
+ * heap tuples visibility. Immediately check posting tuples and
+ * tuples with repeated keys. Postpone check for keys, which have the
+ * first appearance.
*/
if (state->checkunique && state->indexinfo->ii_Unique &&
- P_ISLEAF(topaque) && !skey->anynullkeys)
+ P_ISLEAF(topaque) && !skey->anynullkeys &&
+ (BTreeTupleIsPosting(itup) || ItemPointerIsValid(lVis_tid)))
+ {
bt_entry_unique_check(state, itup, state->targetblock, offset,
&lVis_i, &lVis_tid, &lVis_offset,
&lVis_block);
+ unique_checked = true;
+ }
if (state->checkunique && state->indexinfo->ii_Unique &&
P_ISLEAF(topaque) && OffsetNumberNext(offset) <= max)
@@ -1796,6 +1809,9 @@ bt_target_page_check(BtreeCheckState *state)
* data (whole index tuple or last posting in index tuple). Key
* containing null value does not violate unique constraint and
* treated as different to any other key.
+ *
+ * If the next key is the same as the previous one, do the
+ * bt_entry_unique_check() call if it was postponed.
*/
if (_bt_compare(state->rel, skey, state->target,
OffsetNumberNext(offset)) != 0 || skey->anynullkeys)
@@ -1805,6 +1821,12 @@ bt_target_page_check(BtreeCheckState *state)
lVis_block = InvalidBlockNumber;
lVis_offset = InvalidOffsetNumber;
}
+ else if (!unique_checked)
+ {
+ bt_entry_unique_check(state, itup, state->targetblock, offset,
+ &lVis_i, &lVis_tid, &lVis_offset,
+ &lVis_block);
+ }
skey->scantid = scantid; /* Restore saved scan key state */
}
@@ -1889,6 +1911,15 @@ bt_target_page_check(BtreeCheckState *state)
/* The first key on the next page is the same */
if (_bt_compare(state->rel, rightkey, state->target, max) == 0 && !rightkey->anynullkeys)
{
+ /*
+ * Do the bt_entry_unique_check() call if it was
+ * postponed.
+ */
+ if (!unique_checked)
+ bt_entry_unique_check(state, itup, state->targetblock, offset,
+ &lVis_i, &lVis_tid, &lVis_offset,
+ &lVis_block);
+
elog(DEBUG2, "cross page equal keys");
state->target = palloc_btree_page(state,
rightblock_number);
--
2.39.3 (Apple Git-145)
view thread (24+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: [PATCH] Improve amcheck to also check UNIQUE constraint in btree index.
In-Reply-To: <CAPpHfdu6bGLxe-+9jfDwoji_T2iD6mjdiAGBr0JT-iX+TWNWOw@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox