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 1s6Uga-00CKUT-07 for pgsql-hackers@arkaria.postgresql.org; Mon, 13 May 2024 12:21:44 +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 1s6Ufa-000Rlp-A3 for pgsql-hackers@arkaria.postgresql.org; Mon, 13 May 2024 12:20:42 +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 1s6UfZ-000Rk9-PJ for pgsql-hackers@lists.postgresql.org; Mon, 13 May 2024 12:20:42 +0000 Received: from mail-ej1-x630.google.com ([2a00:1450:4864:20::630]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s6UfW-000o3o-TH for pgsql-hackers@lists.postgresql.org; Mon, 13 May 2024 12:20:40 +0000 Received: by mail-ej1-x630.google.com with SMTP id a640c23a62f3a-a5a552c8cbaso438816166b.2 for ; Mon, 13 May 2024 05:20:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715602837; x=1716207637; 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=Lkp6zHJJPVtKKVtMmRKytepnQXCOxwZJVhZqnNkg69s=; b=HnLxRTYGbGcsn+PXPi0okTIv0vRB23FV+YH//BoJPViSHZcvltzgYVpxFOdC2HLJWl GXoGacbRfjDNhkAmd7gKd28sjsv0UCvxmT117ckNPWzUwrsJ51hJe6vLEh9UZWsaksqu LOnfeqUvmqQuvXpaCpKcQwVY90ztFvvFjyBscJ/8RnNuYQUxava043J+RseDR37HEx7f jVT+fh6MsEZWP3Q5Eh9+osafl0WxPZ/iywj0dKyntsF7qXuN4VGI3pUr7t6lkZHYjuxk 9edvfXQtd+Muql2JqUpSWdpCBJ0hB7rjNJTNzqjZJFE30LDPlnDN+J0W9rCNxKlw0009 PR9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715602837; x=1716207637; 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=Lkp6zHJJPVtKKVtMmRKytepnQXCOxwZJVhZqnNkg69s=; b=cJOce//cDxQ55N+wf2YXzGXO0241MhGYCzpuPXh5NXz+mqt019GSi0j38L6/jptcHJ WPQ4hy+rDl3xUm2KtzHjozvOL4r+w9dSBxlA6vGzGQ8eP6gt4EWrRLUXVhO2Vrbu76DD M8v3Rlp5Sobhy/8xCRQRyw7rCha0pGJc/swFr5SsSogy4oe5UvfwhYkjq/aDPxTDdvSN pXLY+pr7GkRTY9Rilsv3HidAlcLIdLlUjd03LsRUsmoDy9xXEyQvIGi5upt6NgDRChbU mxqD7uIcJjcE8z7ZT1waXI9P0eCjyWiDMQ5p6ajdEOHb+tMoJIdkN9PQT3bYuwb8D1T1 ZtuQ== X-Forwarded-Encrypted: i=1; AJvYcCWAAYiec0vBfcdfN4Tck6EhHz4jZhHKKVSCIwL4WpkhPaQ2PcWgKmGzjelq7RrvzKDwwYI+N6YHN1D/tdaQKLHLiOi/AXNMxzUI3W3ifCLPloGu X-Gm-Message-State: AOJu0YytIySy+gEGjLP9tyr+06SmrS3ggP9fqiooQ4/WL74XRoZgvKRR U0mRksKfiNF5ftGduFmI350Dp8n5p6h+EqULoUQZS+QXmcscahvhTiBhC9x/cYurGKc9jLYLxMX ZEGBR3WuUU5TIzSuIga4EXNM5Hzo= X-Google-Smtp-Source: AGHT+IE8K2pYmTcVNCPTMAx07pGR9gHWqC2YeeEmejWSO3Rn/Tte2BTmA4+879nUgQ40toOYXsgUyr4QdW3mz0/eU/o= X-Received: by 2002:a17:906:f6da:b0:a59:a97b:5aff with SMTP id a640c23a62f3a-a5a2d680c8fmr638524666b.73.1715602837485; Mon, 13 May 2024 05:20:37 -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:20:25 +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="000000000000b43d48061854e98f" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000b43d48061854e98f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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)) On Mon, 13 May 2024 at 16:19, Pavel Borisov wrote: > > > 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 >>> 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 happe= n at >>> what is now line 963. The patch fixes the bug, because state->target n= o >>> longer gets overwritten where you are now using "rightpage" for the val= ue. >>> > > >>> > > 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 t= hat. >>> > > >>> > > 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 o= ne >>> 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 h= elp >>> 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 b= e >>> 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 fro= m >>> bt_target_page_check() into the calling function >>> bt_check_level_from_leftmost() the value in state->target is not what i= t >>> would have been prior to this patch. Now, that'd be irrelevant if nobo= dy >>> 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. >>> >> >> 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 n= ext >> 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 gettin= g >> rightpage into state->target in bt_target_page_check() that ensures us t= hat >> 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 >> 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 opinio= n >> the patch 0003 is a pure code refactoring. >> >> As for the cross-page check regression/TAP testing, this test had >> problems 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 >> all as it's unused. PFA is a simple patch for this. (I don't add it to t= he >> current patch set as I believe it has nothing to do with UNIQUE constrai= nt >> 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)) > --000000000000b43d48061854e98f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
A correction of a typo in = previous message:
non-leaf pages itera= tion cycles (under P_ISLEAF(topaque))=C2=A0->=C2=A0non-leaf pages iterat= ion cycles (under !P_ISLEAF(topaque))

On Mon, 13 May 2024 at 16:19, Pa= vel Borisov <pashkin.elfe@gmai= l.com> wrote:


On Mon, 13 May 2024 at 15:55, Pa= vel Borisov <pashkin.elfe@gmail.com> wrote:
Hi, Alexander!
On M= on, 13 May 2024 at 05:42, Alexander Korotkov <aekorotkov@gmail.com> wrote:
On Mon, May 13, 2024 at= 12:23=E2=80=AFAM Alexander 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
--000000000000b43d48061854e98f--