public inbox for [email protected]
help / color / mirror / Atom feedFrom: Matthias van de Meent <[email protected]>
To: Peter Geoghegan <[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]>
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
Date: Thu, 27 Jul 2023 15:59:51 +0200
Message-ID: <CAEze2WhRef3bnfRbRbeYAnemxrixM-g1p3tKzOHHb6hP2Z4=5A@mail.gmail.com> (raw)
In-Reply-To: <CAH2-Wz=6vQyS5YhkZJV1gXjEF=TFEh2gxB0kjxDuZLgbC98KOg@mail.gmail.com>
References: <CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com>
<CAEze2Wgdh5WZzOcUQxTUO45g4qL4oxfVOA8re0MqvKjsamrdFQ@mail.gmail.com>
<CAH2-WzkExhbc5a7tuVy_pZFFiWZ4RiZTRfwVVM2+bcHUqor9ow@mail.gmail.com>
<CAEze2WhjFd8+BvWG-Wx3AEaTjO=V5Yo_aee=wpPe65rFcKdQCg@mail.gmail.com>
<CAH2-Wz=6vQyS5YhkZJV1gXjEF=TFEh2gxB0kjxDuZLgbC98KOg@mail.gmail.com>
On Thu, 27 Jul 2023 at 06:14, Peter Geoghegan <[email protected]> wrote:
>
> On Wed, Jul 26, 2023 at 12:07 PM Matthias van de Meent
> <[email protected]> wrote:
> > We could cache the last accessed leaf page across amrescan operations
> > to reduce the number of index traversals needed when the join key of
> > the left side is highly (but not necessarily strictly) correllated.
>
> That sounds like block nested loop join. It's possible that that could
> reuse some infrastructure from this patch, but I'm not sure.
My idea is not quite block nested loop join. It's more 'restart the
index scan at the location the previous index scan ended, if
heuristics say there's a good chance that might save us time'. I'd say
it is comparable to the fast tree descent optimization that we have
for endpoint queries, and comparable to this patch's scankey
optimization, but across AM-level rescans instead of internal rescans.
See also the attached prototype and loosely coded patch. It passes
tests, but it might not be without bugs.
The basic design of that patch is this: We keep track of how many
times we've rescanned, and the end location of the index scan. If a
new index scan hits the same page after _bt_search as the previous
scan ended, we register that. Those two values - num_rescans and
num_samepage - are used as heuristics for the following:
If 50% or more of rescans hit the same page as the end location of the
previous scan, we start saving the scan's end location's buffer into
the BTScanOpaque, so that the next _bt_first can check whether that
page might be the right leaf page, and if so, immediately go to that
buffer instead of descending the tree - saving one tree descent in the
process.
Further optimizations of this mechanism could easily be implemented by
e.g. only copying the min/max index tuples instead of the full index
page, reducing the overhead at scan end.
Kind regards,
Matthias van de Meent
Neon (https://neon.tech)
Attachments:
[application/octet-stream] v1-0001-Cache-btree-scan-end-page-across-rescans-in-the-s.patch.cfbot-ignore (8.6K, ../CAEze2WhRef3bnfRbRbeYAnemxrixM-g1p3tKzOHHb6hP2Z4=5A@mail.gmail.com/2-v1-0001-Cache-btree-scan-end-page-across-rescans-in-the-s.patch.cfbot-ignore)
download
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]
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
In-Reply-To: <CAEze2WhRef3bnfRbRbeYAnemxrixM-g1p3tKzOHHb6hP2Z4=5A@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