Subject: Re: Bug in nbtree optimization to skip > operator comparisons (or < comparisons in backwards scans)

From: Peter Geoghegan <[email-masked]>
Date: Tue, 5 Dec 2023 17:45:41 -0800

On Tue, Dec 5, 2023 at 4:41 PM Peter Geoghegan <[email-masked]> wrote:
> "In general, when inequality keys are present, the initial-positioning
> code only promises to position before the first possible match, not
> exactly at the first match, for a forward scan; or after the last
> match for a backward scan."
>
> My test case mostly just demonstrates how to reproduce the scenario
> described by this sentence.

I just realized that my test case wasn't quite minimized correctly. It
depended on a custom function that was no longer created.

Attached is a revised version that uses btint84cmp instead.

-- 
Peter Geoghegan

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 6 Dec 2023 06:05:52 +0200

Hi, Peter!

> Attached is a revised version that uses btint84cmp instead.

Thank you for raising this issue.  Preprocessing of btree scan keys is
normally removing the redundant scan keys.  However, redundant scan
keys aren't removed when they have arguments of different types.
Please give me a bit of time to figure out how to workaround this.

------
Regards,
Alexander Korotkov

---

From: Peter Geoghegan <[email-masked]>
Date: Tue, 5 Dec 2023 20:20:01 -0800

> Please give me a bit of time to figure out how to workaround this.

Couldn't you condition the use of the optimization on
_bt_preprocess_keys being able to use cross-type operators when it
checked for redundant or contradictory scan keys? The vast majority of
index scans will be able to do that.

As I said already, what you're doing here isn't all that different to
the way that we rely on required equality strategy scan keys being
used to build our initial insertion scan key, that determines where
the scan is initially positioned to within _bt_first. Inequalities
aren't all that different to equalities.

-- 
Peter Geoghegan

---

From: Peter Geoghegan <[email-masked]>
Date: Wed, 6 Dec 2023 09:31:56 -0800

> index scans will be able to do that.

Some quick experimentation shows that my test case works as expected
once _bt_preprocess_keys is taught to remember that it has seen a
maybe-unsafe case, which it stashes in a special new field from the
scan's state for later. As I said, this field can be treated as a
condition of applying the required-in-opposite-direction-only
optimization in _bt_readpage().

This new field would be analogous to the existing
requiredMatchedByPrecheck state used by _bt_readpage() to determine
whether it can apply the required-in-same-direction optimization. The
new field works for the whole scan instead of just for one page, and
it works based on information from "behind the scan" instead of
information "just ahead of the scan". But the basic idea is the same.

_bt_preprocess_keys is rather complicated. It is perhaps tempting to
do this in a targeted way, that specifically limits itself to the exact
cases that we know to be unsafe. But it might be okay to just disable
the optimization in most or all cases where _bt_compare_scankey_args()
returns false. That's likely to be very rare in practice, anyway (who
really uses opfamilies like these?). Not really sure where to come
down on that.

--
Peter Geoghegan

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 8 Dec 2023 20:30:18 +0200

> Please give me a bit of time to figure out how to workaround this.

I dig into the problem.  I think this assumption is wrong in my commit.

"When the key is required for opposite direction scan, it must be
already satisfied by_bt_first() ..."

In your example "foo = 90" is satisfied by_bt_first(), but "foo >
99::int8" is not.  I think this could be resolved by introducing a
separate flag exactly distinguishing scan keys used for _bt_first().
I'm going to post the patch doing this.

------
Regards,
Alexander Korotkov

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 8 Dec 2023 20:46:01 +0200

> I'm going to post the patch doing this.

The draft patch is attached.  It requires polishing and proper
commenting.  But I hope the basic idea is clear.  Do you think this is
the way forward?

------
Regards,
Alexander Korotkov

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 8 Dec 2023 18:29:17 -0800

> commenting.  But I hope the basic idea is clear.  Do you think this is

Does this really need to work at the scan key level, rather than at
the whole-scan level? Wouldn't it make more sense to just totally
disable it for the whole scan, since we'll barely ever need to do that
anyway?

My ScalarArrayOpExpr patch will need to disable this optimization,
since with that patch in place we don't necessarily go through
_bt_first each time the search-type scan keys must change. We might
need to check a few tuples from before the _bt_first-wise position of
the next set of array values, which is a problem with
opposite-direction-only inequalities (it's a little bit like the
situation from my test case, actually). That's partly why I'd prefer
this to work at the whole-scan level (though I also just don't think
that inventing SK_BT_BT_FIRST makes much sense).

I think that you should make it clearer that this whole optimization
only applies to required *inequalities*, which can be required in the
opposite direction *only*. It should be more obvious from looking at
the code that the optimization doesn't apply to required equality
strategy scan keys (those are always required in *both* scan
directions or in neither direction, so unlike the closely related
prefix optimization added by the same commit, they just can't use the
optimization that we need to fix here).

BTW, do we really need to keep around the BTScanOpaqueData.firstPage
field? Why can't the call to _bt_readpage from _bt_first (and from
_bt_endpoint) just pass "firstPage=true" as a simple argument? Note
that the first call to _bt_readpage must take place from _bt_first (or
from _bt_endpoint). The first _bt_first call is already kind of
special, in a way that is directly related to this issue. I added some
comments about that to today's commit c9c0589fda, in fact -- I think
it's an important issue in general.

-- 
Peter Geoghegan

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 11 Dec 2023 17:56:13 +0200

Hi, Peter!

> it's an important issue in general.

Please, check the attached patchset.

The first patch removes the BTScanOpaqueData.firstPage field as you
proposed.  I think this is a good idea, thank you for the proposal.

Regarding the requiredOppositeDir bug.  I don't want to lose the
generality of the optimization.  I could work for different cases, for
example.
WHERE col1 > val1 AND col1 < val2
WHERE col1 = val1 AND col2 > val2 AND col2 < val3
WHERE col1 = val1 AND col2 = val2 AND col3 > val3 AND col3 < val4
And there could be additional scan keys, which shouldn't be skipped.
But that shouldn't mean we shouldn't skip others.

See the second patch for my next proposal to fix the problem.  Instead
of relying on _bt_first(), let's rely on the first matched item on the
page. Once it's found, we may skip scan keys required for the opposite
direction.  What do you think?

------
Regards,
Alexander Korotkov

---

From: Peter Geoghegan <[email-masked]>
Date: Mon, 11 Dec 2023 08:16:07 -0800

Will you be in Prague this week? If not this might have to wait.

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 11 Dec 2023 20:59:32 +0200

> Please, check the attached patchset.

Sorry, I forgot the attachment.  Here it is.

------
Regards,
Alexander Korotkov

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 12 Dec 2023 15:22:16 +0200

> Will you be in Prague this week? If not this might have to wait.

Sorry, I wouldn't be in Prague this week.  Due to my current
immigration status, I can't travel.
I wish you to have a lovely time in Prague.  I'm OK to wait, review
once you can.  I will probably provide a more polished version
meanwhile.

------
Regards,
Alexander Korotkov

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 25 Dec 2023 00:50:52 +0200

> once you can.  I will probably provide a more polished version

Please find the revised patchset attached.  It comes with revised
comments and commit messages.  Besides bug fixing the second patch
makes optimization easier to understand.  Now the flag used for
skipping checks of same direction required keys is named
continuescanPrechecked and means exactly that *continuescan flag is
known to be true for the last item on the page.

Any objections to pushing these two patches?

------
Regards,
Alexander Korotkov

---

From: Pavel Borisov <[email-masked]>
Date: Mon, 25 Dec 2023 22:32:37 +0400

Hi, Alexander!

> Any objections to pushing these two patches?

I've reviewed both patches:
0001 - is a pure refactoring replacing argument transfer from via struct
member to transfer explicitly as a function argument. It's justified by
the fact firstPage is localized only to several places. The patch looks
simple and good enough.

0002:
continuescanPrechecked is semantically much better than
previous requiredMatchedByPrecheck which confused me earlier. Thanks!

>From the new comments, it looks a little bit hard to understand who does
what. Semantics "if caller told" in comments looks more clear to me. Could
you especially give attention to the comments:

"If they wouldn't be matched, then the *continuescan flag would be set for
the current item and the last item on the page accordingly."
"If the key is required for the opposite direction scan, we need to know
there was already at least one matching item on the page.  For those keys."

> Prechecking the value of the continuescan flag for the last item on the
>+ * page (according to the scan direction).
Maybe, in this case, it would be more clear like: "...(for backwards scan
it will be the first item on a page)"

Otherwise the patch 0002 looks like a good fix for the bug to be pushed.

Kind regards,
Pavel Borisov

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 26 Dec 2023 21:35:37 +0200

Pavel,

On Mon, Dec 25, 2023 at 8:32 PM Pavel Borisov <[email-masked]> wrote:
> 0001 - is a pure refactoring replacing argument transfer from via struct member to transfer explicitly as a function argument. It's justified by the fact firstPage is localized only to several places. The patch looks simple and good enough.
>
> 0002:
> continuescanPrechecked is semantically much better than previous requiredMatchedByPrecheck which confused me earlier. Thanks!
>
> From the new comments, it looks a little bit hard to understand who does what. Semantics "if caller told" in comments looks more clear to me. Could you especially give attention to the comments:
>
> "If they wouldn't be matched, then the *continuescan flag would be set for the current item and the last item on the page accordingly."
> "If the key is required for the opposite direction scan, we need to know there was already at least one matching item on the page.  For those keys."
>
> Maybe, in this case, it would be more clear like: "...(for backwards scan it will be the first item on a page)"
>

Thank you for your review.  I've revised comments to meet your suggestions.

------
Regards,
Alexander Korotkov

---

From: Pavel Borisov <[email-masked]>
Date: Wed, 27 Dec 2023 15:18:35 +0400

Alexander,

On Tue, 26 Dec 2023 at 23:35, Alexander Korotkov <[email-masked]>
wrote:

> member to transfer explicitly as a function argument. It's justified by the
> fact firstPage is localized only to several places. The patch looks simple
> and good enough.
> >
> > 0002:
> > continuescanPrechecked is semantically much better than previous
> requiredMatchedByPrecheck which confused me earlier. Thanks!
> >
> > "If they wouldn't be matched, then the *continuescan flag would be set
> for the current item and the last item on the page accordingly."
> > Maybe, in this case, it would be more clear like: "...(for backwards
> scan it will be the first item on a page)"
> >
Thank you for revised comments! I think they are good enough.

Regards,
Pavel

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 27 Dec 2023 14:36:18 +0200

> Thank you for revised comments! I think they are good enough.

Pushed, thank you!

------
Regards,
Alexander Korotkov

---

From: "Anton A. Melnikov" <[email-masked]>
Date: Fri, 22 Mar 2024 10:29:38 +0300

Hi!

Maybe _bt_readpage(scan, dir, start, true) needed at this line:

https://github.com/postgres/postgres/blob/b4080fa3dcf6c6359e542169e0e81a0662c53ba8/src/backend/access/nbtree/nbtsearch.c#L2501

?

Do we really need to try prechecking the continuescan flag here?

And the current "false" in the last arg does not match the previous code before 06b10f80ba
and the current comment above.

Would be very grateful for clarification.

With the best regards!

-- 
Anton A. Melnikov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

---

From: Pavel Borisov <[email-masked]>
Date: Fri, 22 Mar 2024 12:02:49 +0400

Hi, Anton!
Looks like an oversight when refactoring BTScanOpaqueData.firstPage into
using function argument in 06b10f80ba4.

@@ -2487,14 +2486,13 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
104
105     /* remember which buffer we have pinned */
106     so->currPos.buf = buf;
107 -   so->firstPage = true;
108
109     _bt_initialize_more_data(so, dir);
110
111     /*
112      * Now load data from the first page of the scan.
113      */
114 -   if (!_bt_readpage(scan, dir, start))
115 +   if (!_bt_readpage(scan, dir, start, false))

Attached is a fix.
Thank you!

Regards,
Pavel

---

From: "Anton A. Melnikov" <[email-masked]>
Date: Fri, 22 Mar 2024 11:14:48 +0300

> Attached is a fix.

Thanks!