Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1s6Ug5-00CKQo-E7 for pgsql-hackers@arkaria.postgresql.org; Mon, 13 May 2024 12:21:13 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1s6Uf5-000PaT-H1 for pgsql-hackers@arkaria.postgresql.org; Mon, 13 May 2024 12:20:11 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1s6Uf4-000PX8-Uy for pgsql-hackers@lists.postgresql.org; Mon, 13 May 2024 12:20:11 +0000 Received: from mail-ej1-x62a.google.com ([2a00:1450:4864:20::62a]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s6Uf2-000o3C-3Y for pgsql-hackers@lists.postgresql.org; Mon, 13 May 2024 12:20:10 +0000 Received: by mail-ej1-x62a.google.com with SMTP id a640c23a62f3a-a59a0168c75so1107689866b.1 for ; Mon, 13 May 2024 05:20:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715602806; x=1716207606; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=PQtT/txgIq/2gyaf0w0K1HdqtRtXsG7hFq0sWR1inwY=; b=ff8wa7zxH3vejw9ADTMLqhkPOIMmzNaw1IC/TxXsKQwQWFreUEBsCHF6YCcaEiURcQ qxwO15WY0+CxhQJGBUMTJFaSRJnLzwhhzwxGL67442p8rIvQ1KH4HhFs4ERtDQTHbNX+ AfRPFrTAT94S9O6UMS75h6rtwPdY7EQVkcPgUZukfnk05lZ12lRjPLyJXDiS9So4nZRj cYz0YSd5l4i+5XNkXKMjYXIHTMYG4vJwn1Nibe9GISZGJG3AvYo5BDm4QZDjUUanQxUd IfI1DpUbVgTG1ZkNqdBtWWpZUVsmSiZtA+jFADvYQPS4qfPV6/iVvL1gCEqs/tIf1EtU DSNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715602806; x=1716207606; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=PQtT/txgIq/2gyaf0w0K1HdqtRtXsG7hFq0sWR1inwY=; b=n1IFssY/aU8aB6Hg3cGHImKv4qoxOueAo566EsK+ef2sjTQel/qzq9WZNtDan8Re27 ebtMwoam0xg67JDEifQPMjL0ibrUATE75Rw/E+rzPIvtQHJ8By/4VBoAn94tMggFvk/Q j4OOp3dcHdmECLuHlaxlCaK58bQFwSDEFP6vHEg2ez+f6vZr6wR/VrSwXmhUBgwRyWok pfRw2ffCZ5YTnSHw37edoi1VWjtPlLhkRxmifWbg//rw8ZK61O+Y5//hvEAg70HMQvVa 0M+mcjQA9ezSkJLZJ003ZreEn6fMXUeBnUyTtYVhSLlKB3gUp/9NjRj0tOCSIkpxu5NL mXJg== X-Forwarded-Encrypted: i=1; AJvYcCUn9izkQ2yQwSrJA8wbRjgEHphtSlu744JFnzQC2vuvH0fwTlxHdyA+1xD9mm20JY5cFvh1kF94L7eIcWMBY+LbYlwSYfetZQxhj9Wyt5nCfIPI X-Gm-Message-State: AOJu0YyM3FC1+uUZufxETDZz094JKU/7fv8cNA2fJ1DH2IUgMeSuHPga kjOG8KSbTGep+OazqJ7FXrlfuov6ZRVHYa+avsFg7uNht+o6y9mxJXQ32In6fHmU+CuzaqX/GPM ka5q4SUM9jqrYDL0BFySO8QK00jE= X-Google-Smtp-Source: AGHT+IEfLtzh/OceRqWyiLt4y8fJg8W3efxbmDWs7fAmJGwOeEVjsqRh4J4FsGpOExOtMkE1kmtbsM/t3SG1J7SDfMs= X-Received: by 2002:a17:906:3a8d:b0:a59:be8a:bd6f with SMTP id a640c23a62f3a-a5a2d65f272mr605982666b.61.1715602805571; Mon, 13 May 2024 05:20:05 -0700 (PDT) MIME-Version: 1.0 References: <20220922151328.lakwdytvwnyyif3b@awork3.anarazel.de> <8c74cc5e-4b97-4cd7-9aaf-67886822a78c@eisentraut.org> <20240501022412.85@rfd.leadboat.com> <1375614.1715301775@sss.pgh.pa.us> <8635D8B1-45B7-4D67-86C7-D6ECB4F10B11@enterprisedb.com> In-Reply-To: From: Pavel Borisov Date: Mon, 13 May 2024 16:19:54 +0400 Message-ID: Subject: Re: [PATCH] Improve amcheck to also check UNIQUE constraint in btree index. To: Alexander Korotkov Cc: Mark Dilger , Tom Lane , Noah Misch , Peter Eisentraut , Aleksander Alekseev , Postgres hackers , Maxim Orlov , Andres Freund , Greg Stark , Julien Rouhaud , David Steele , Peter Geoghegan , Maxim Orlov , lubennikovaav@gmail.com Content-Type: multipart/alternative; boundary="000000000000cd485a061854e70f" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000cd485a061854e70f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, 13 May 2024 at 15:55, Pavel Borisov wrote: > Hi, Alexander! > > On Mon, 13 May 2024 at 05:42, Alexander Korotkov > wrote: > >> On Mon, May 13, 2024 at 12:23=E2=80=AFAM Alexander Korotkov >> wrote: >> > On Sat, May 11, 2024 at 4:13=E2=80=AFAM Mark Dilger >> > wrote: >> > > > On May 10, 2024, at 12:05 PM, Alexander Korotkov < >> aekorotkov@gmail.com> wrote: >> > > > The only bt_target_page_check() caller is >> > > > bt_check_level_from_leftmost(), which overrides state->target in t= he >> > > > 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->targe= t >> in an inappropriate way, causing the wrong thing to happen at what is no= w >> 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 th= at. >> > > >> > > 4) It's been broken all along and your patch just changes from wron= g >> to wrong. >> > > >> > > >> > > If you believe (1) is true, then I'm complaining that you are relyin= g >> 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 h= ow >> 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 th= e >> 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 nobod= y >> 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 t= he >> 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. >> > > I agree with your analysis regarding state->target: > - when the unique check is on, state->target was reassigned only for the > leaf pages (under P_ISLEAF(topaque) in bt_target_page_check). > - in this level (leaf) in bt_check_level_from_leftmost() this value of > state->target was used to get state->lowkey. Then it was reset (in the ne= xt > iteration of do loop in in bt_check_level_from_leftmost() > - state->lowkey lives until the end of pages level (leaf) iteration cycle= . > Then, low-key is reset (state->lowkey =3D NULL in the end of > bt_check_level_from_leftmost()) > - state->lowkey is used only in bt_child_check/bt_child_highkey_check. > Both are called only from non-leaf pages iteration cycles (under > P_ISLEAF(topaque)) > - Also there is a check (rightblock_number !=3D P_NONE) in before getting > rightpage into state->target in bt_target_page_check() that ensures us th= at > rightpage indeed exists and getting this (unused) lowkey in > bt_check_level_from_leftmost will not invoke any page reading errors. > > I'm pretty sure that there was no bug in this, not just the bug was hidde= n. > > Indeed re-assigning state->target in leaf page iteration for cross-page > unique check was not beautiful, and Peter pointed out this. In my opinion > the patch 0003 is a pure code refactoring. > > As for the cross-page check regression/TAP testing, this test had problem= s > since the btree page layout is not fixed (especially it's different on > 32-bit arch). I had a variant for testing cross-page check when the test > was yet regression one upthread for both 32/64 bit architectures. I > remember it was decided not to include it due to complications and low > impact for testing the corner case of very rare cross-page duplicates. > (There were also suggestions to drop cross-page duplicates check at all, > which I didn't agree 2 years ago, but still it can make sense) > > Separately, I propose to avoid getting state->lowkey for leaf pages at al= l > as it's unused. PFA is a simple patch for this. (I don't add it to the > current patch set as I believe it has nothing to do with UNIQUE constrain= t > check, rather it improves the previous btree amcheck code) > A correction of a typo in previous message: non-leaf pages iteration cycles (under !P_ISLEAF(topaque)) -> non-leaf pages iteration cycles (under !P_ISLEAF(topaque)) --000000000000cd485a061854e70f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
On Mon, 13 May 2024 at 15:55, Pavel B= orisov <pashkin.elfe@gmail.com= > wrote:
=
Hi, Alexander!

On Mon, 13 May 2024 at 05:4= 2, Alexander Korotkov <aekorotkov@gmail.com> wrote:
On Mon, May 13, 2024 at 12:23=E2=80=AFAM Alexa= nder Korotkov
<aekorotkov@gm= ail.com> wrote:
> On Sat, May 11, 2024 at 4:13=E2=80=AFAM Mark Dilger
> <= mark.dilger@enterprisedb.com> wrote:
> > > On May 10, 2024, at 12:05 PM, Alexander Korotkov <aekorotkov@gmail.com= > wrote:
> > > The only bt_target_page_check() caller is
> > > bt_check_level_from_leftmost(), which overrides state->ta= rget in the
> > > next iteration anyway.=C2=A0 I think the patch is just refac= toring 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_c= heck_level_from_leftmost() overrides state->target in the next iteration= , bt_check_level_from_leftmost() conditionally fetches an item from the pag= e referenced by state->target.=C2=A0 See line 963.
> >
> > I'm left with four possibilities:
> >
> >
> > 1)=C2=A0 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 ite= m from state->target, so the change you're making doesn't matter= .
> >
> > 2)=C2=A0 The code prior to v2-0003 was wrong, having changed stat= e->target in an inappropriate way, causing the wrong thing to happen at = what is now line 963.=C2=A0 The patch fixes the bug, because state->targ= et no longer gets overwritten where you are now using "rightpage"= for the value.
> >
> > 3)=C2=A0 The code used to work, having set up state->target co= rrectly in the place where you are now using "rightpage", but v2-= 0003 has broken that.
> >
> > 4)=C2=A0 It's been broken all along and your patch just chang= es 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 document= ing it.=C2=A0 Even with documentation of this interrelationship, I'd be= unhappy with how brittle the code is.=C2=A0 I cannot easily discern that t= he two don't ever happen in the same iteration, and I'm not at all = convinced one way or the other.=C2=A0 I tried to set up some Asserts about = that, but none of the test cases actually reach the new code, so adding Ass= erts 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.=C2=A0 Bug fixes should= be clearly documented as such, otherwise future work might assume the comm= it can be reverted with only stylistic consequences.
> >
> > If (3) is true, then I'm complaining that the patch is flat b= usted.
> >
> > If (4) is true, then maybe we should revert the entire feature, o= r have a discussion of mitigation efforts that are needed.
> >
> > Regardless of which of 1..4 you pick, I think it could all do wit= h 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 variab= le "rightpage" rather than overwriting "state->target&quo= t;, which the old implementation most certainly did.=C2=A0 That means that = after returning from bt_target_page_check() into the calling function bt_ch= eck_level_from_leftmost() the value in state->target is not what it woul= d have been prior to this patch.=C2=A0 Now, that'd be irrelevant if nob= ody goes on to consult that value, but just 44 lines further down in bt_che= ck_level_from_leftmost() state->target is clearly used.=C2=A0 So the beh= avior at that point is changing between the old and new versions of the cod= e, and I think I'm within reason to ask if it was wrong before the patc= h, wrong after the patch, or something else?=C2=A0 Is this a bug being intr= oduced, being fixed, or ... ?
>
> Thank you for your analysis.=C2=A0 I'm inclined to believe in 2, b= ut not
> yet completely sure.=C2=A0 It's really pity that our tests don'= ;t cover
> this.=C2=A0 I'm investigating this area.

It seems that I got to the bottom of this.=C2=A0 Changing
BtreeCheckState.target for a cross-page unique constraint check is
wrong, but that happens only for leaf pages.=C2=A0 After that
BtreeCheckState.target is only used for setting the low key.=C2=A0 The low<= br> key is only used for non-leaf pages.=C2=A0 So, that didn't lead to any<= br> visible bug.=C2=A0 I've revised the commit message to reflect this.
=
=C2=A0
I agree with your analysis regarding state-&g= t;target:
- when the unique check is on, state->target was reassigned= only for the leaf pages (under P_ISLEAF(topaque) in bt_target_page_check).=
- in this level (leaf) in bt_check_level_from_leftmost() this value of = state->target was used to get state->lowkey. Then it was reset (in th= e next iteration of do loop in in bt_check_level_from_leftmost()
- stat= e->lowkey lives until the end of pages level (leaf) iteration cycle. The= n, low-key is reset (state->lowkey =3D NULL in the end of =C2=A0bt_check= _level_from_leftmost())
- state->lowkey is used only in bt_child_chec= k/bt_child_highkey_check. Both are called only from non-leaf pages iteratio= n cycles (under P_ISLEAF(topaque))
- Also there is a check (rightblock_n= umber !=3D P_NONE) in before getting rightpage into state->target in bt_= target_page_check() that ensures us that rightpage indeed exists and gettin= g this (unused) lowkey in bt_check_level_from_leftmost will not invoke any = page reading errors.

I'm pretty sure that there was = no bug in this, not just the=C2=A0bug was hidden.

= Indeed re-assigning state->target in leaf page iteration for cross-page = unique check was not beautiful, and Peter pointed out this. In my opinion t= he patch 0003 is a pure code refactoring.=C2=A0

As= for the cross-page check regression/TAP testing, this test had problems si= nce the btree page layout is not fixed (especially it's different on 32= -bit arch). I had a variant for testing cross-page check when the test was = yet regression one upthread for both 32/64 bit architectures. I remember it= was decided not to include it due to complications and low impact for test= ing the corner case=C2=A0of very=C2=A0rare cross-page duplicates. (There we= re also suggestions to drop cross-page duplicates check at all, which I did= n't agree 2 years ago, but still it can make sense)

Separately, I propose to avoid getting state->lowkey for leaf page= s at all as it's unused. PFA is a simple patch for this. (I don't a= dd it to the current patch set as I believe it has nothing to do with UNIQU= E constraint check, rather it improves the previous btree amcheck code)

A correction of a typo in pr= evious message:
non-leaf pages i= teration cycles (under !P_ISLEAF(topaque))=C2=A0->=C2=A0non-leaf pages iteration cycles (under !P_ISLEAF(to= paque))=C2=A0
--000000000000cd485a061854e70f--