public inbox for [email protected]
help / color / mirror / Atom feedFrom: Peter Geoghegan <[email protected]>
To: Matthias van de Meent <[email protected]>
Cc: PostgreSQL Hackers <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: Jeff Davis <[email protected]>
Cc: benoit <[email protected]>
Cc: Alexander Korotkov <[email protected]>
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
Date: Mon, 6 Nov 2023 15:02:57 -0800
Message-ID: <CAH2-WzmHWR=gqeuq4rHDTv4zHyXDXNTSNxYQKYru4vyaUk=FTQ@mail.gmail.com> (raw)
In-Reply-To: <CAEze2Whps99tdDfDC4hrL92W1oiZBnFXqv1OB55OMdPXtx6yuA@mail.gmail.com>
References: <CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com>
<CAEze2Wgdh5WZzOcUQxTUO45g4qL4oxfVOA8re0MqvKjsamrdFQ@mail.gmail.com>
<CAH2-WzkExhbc5a7tuVy_pZFFiWZ4RiZTRfwVVM2+bcHUqor9ow@mail.gmail.com>
<CAH2-WzkEyBU9UQM-5GWPcB=WEShAUKcJdvgFuqVHuPuO-iYW0Q@mail.gmail.com>
<CAH2-Wz=X4wCT-x4HeM95CTqT147K_bL8mC_5d6TUzLPaHdE1nw@mail.gmail.com>
<CAH2-Wz=_FQ0AVgoF+UT7EzafVyd7kanQ0-82BesrpjUHPtjLvg@mail.gmail.com>
<CAH2-WzmjKdovfd-T+o0VaboZCdKnccXSvN4cub3qZw=baC_hyA@mail.gmail.com>
<CAEze2Whps99tdDfDC4hrL92W1oiZBnFXqv1OB55OMdPXtx6yuA@mail.gmail.com>
On Mon, Nov 6, 2023 at 1:28 PM Matthias van de Meent
<[email protected]> wrote:
> I'm planning on reviewing this patch tomorrow, but in an initial scan
> through the patch I noticed there's little information about how the
> array keys state machine works in this new design. Do you have a more
> toplevel description of the full state machine used in the new design?
This is an excellent question. You're entirely right: there isn't
enough information about the design of the state machine.
In v1 of the patch, from all the way back in July, the "state machine"
advanced in the hackiest way possible: via repeated "incremental"
advancement (using logic from the function that we call
_bt_advance_array_keys() on HEAD) in a loop -- we just kept doing that
until the function I'm now calling _bt_tuple_before_array_skeys()
eventually reported that the array keys were now sufficiently
advanced. v2 greatly improved matters by totally overhauling
_bt_advance_array_keys(): it was taught to use binary searches to
advance the array keys, with limited remaining use of "incremental"
array key advancement.
However, version 2 (and all later versions to date) have somewhat
wonky state machine transitions, in one important respect: calls to
the new _bt_advance_array_keys() won't always advance the array keys
to the maximum extent possible (possible while still getting correct
behavior, that is). There were still various complicated scenarios
involving multiple "required" array keys (SK_BT_REQFWD + SK_BT_REQBKWD
scan keys that use BTEqualStrategyNumber), where one single call to
_bt_advance_array_keys() would advance the array keys to a point that
was still < caller's tuple. AFAICT this didn't cause wrong answers to
queries (that would require failing to find a set of exactly matching
array keys where a matching set exists), but it was kludgey. It was
sloppy in roughly the same way as the approach in my v1 prototype was
sloppy (just to a lesser degree).
I should be able to post v6 later this week. My current plan is to
commit the other nbtree patch first (the backwards scan "boundary
cases" one from the ongoing CF) -- since I saw your review earlier
today. I think that you should probably wait for this v6 before
starting your review. The upcoming version will have simple
preconditions and postconditions for the function that advances the
array key state machine (the new _bt_advance_array_keys). These are
enforced by assertions at the start and end of the function. So the
rules for the state machine become crystal clear and fairly easy to
keep in your head (e.g., tuple must be >= required array keys on entry
and <= required array keys on exit, the array keys must always either
advance by one increment or be completely exhausted for the top-level
scan in the current scan direction).
Unsurprisingly, I found that adding and enforcing these invariants led
to a simpler and more general design within _bt_advance_array_keys.
That code is still the most complicated part of the patch, but it's
much less of a bag of tricks. Another reason for you to hold off for a
few more days.
--
Peter Geoghegan
view thread (8+ 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]
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
In-Reply-To: <CAH2-WzmHWR=gqeuq4rHDTv4zHyXDXNTSNxYQKYru4vyaUk=FTQ@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