public inbox for [email protected]
help / color / mirror / Atom feedFrom: Peter Geoghegan <[email protected]>
To: Tomas Vondra <[email protected]>
Cc: Matthias van de Meent <[email protected]>
Cc: PostgreSQL Hackers <[email protected]>
Cc: Tom Lane <[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: Tue, 28 Nov 2023 16:57:52 -0800
Message-ID: <CAH2-WzmtV7XEWxf_rP1pw=vyDjGLi__zGOy6Me5MovR3e1kfdg@mail.gmail.com> (raw)
In-Reply-To: <CAH2-Wz=paSJk31VtMjYhHLAChCuD-Q=Qds-fTRjpC_L0dzOiXw@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>
<CAH2-WzmHWR=gqeuq4rHDTv4zHyXDXNTSNxYQKYru4vyaUk=FTQ@mail.gmail.com>
<CAEze2Wj-EBt8ECp7QScx5bBw4VNg=9T==o=Yh=gUR4__C3h=uA@mail.gmail.com>
<CAH2-Wz=Ct9fLcN-2SV0gx_iBk87RsAi+Sor3OwR2_5Rg_KO0+g@mail.gmail.com>
<CAEze2WiR5eJgVqDHCEaO0=mDiUyXY_o-8aK-PTKVPCKba_E4Vg@mail.gmail.com>
<CAH2-WzmTHoCsOmSgLg=yyft9LoERtuCKXyG2GZn+28PzonFA_g@mail.gmail.com>
<[email protected]>
<CAH2-WzkSZEOy_RaqSiBKnVH=8rv-6dhFWfbHaRPfOxjyMAcZXA@mail.gmail.com>
<CAH2-Wz=paSJk31VtMjYhHLAChCuD-Q=Qds-fTRjpC_L0dzOiXw@mail.gmail.com>
On Tue, Nov 28, 2023 at 3:52 PM Peter Geoghegan <[email protected]> wrote:
> While I still think that we need heuristics that apply speculative
> criteria to decide whether or not going to the next page directly
> (when we have a choice at all), that doesn't mean that the v7
> heuristics can't be improved on, with a little more thought. It's a
> bit tricky, since we're probably also benefiting from the same
> heuristics all the time -- probably even for this same test case.
Correction: this particular test case happens to be one where the
optimal strategy is to do *exactly* what the master branch does
currently. The master branch is unbeatable, so the only reasonable
goal for the patch is to not lose (or to lose by no more than a
completely negligible amount).
I'm now prepared to say that this behavior is not okay -- I definitely
need to fix this. It's a bug.
Because each distinct value never fits on one leaf page (it's more
like 1.5 - 2 pages, even though we're deduplicating heavily), and
because Postgres 12 optimizations are so effective with low
cardinality/posting-list-heavy indexes such as this, we're bound to
lose quite often. The only reason it doesn't happen _every single
time_ we descend the index is because the test script uses CREATE
INDEX, rather than using retail inserts (I tend to prefer the latter
for this sort of analysis). Since nbtsort.c isn't as clever/aggressive
about suffix truncation as the nbtsplitloc.c split strategies would
have been, had we used them (had there been retail inserts), many
individual leaf pages are left with high keys that aren't particularly
good targets for the high key precheck optimization (see Postgres 12
commit 29b64d1d).
If I wanted to produce a truly adversarial case for this issue (which
this is already close to), I'd go with the following:
1. Retail inserts that leave each leaf page full of one single value,
which will allow each high key to still make a "clean break" from the
right sibling page -- it'll have the right sibling's value. Maybe
insert 1200 - 1300 tuples per distinct index value for this.
In other words, bulk loading that results in an index that never has
to append a heap TID tiebreaker during suffix truncation, but comes
very close to needing to. Bulk loading where nbtsplitloc.c needs to
use SPLIT_MANY_DUPLICATES all the time, but never quite gets to the
point of needing a SPLIT_SINGLE_VALUE split.
2. A SAOP query with an array with every second value in the index as
an element. Something like "WHERE arr in (2, 4, 6, 8, ...)".
The patch will read every single leaf page, whereas master will
*reliably* only read every second leaf page. I didn't need to "trick"
the patch in a contrived sort of way to get this bad outcome -- this
scenario is fairly realistic. So this behavior is definitely not
something that I'm prepared to defend. As I said, it's a bug.
It'll be fixed in the next revision.
--
Peter Geoghegan
view thread (4+ 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-WzmtV7XEWxf_rP1pw=vyDjGLi__zGOy6Me5MovR3e1kfdg@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