MIME-Version: 1.0
References: <CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com>
 <CAEze2Wgdh5WZzOcUQxTUO45g4qL4oxfVOA8re0MqvKjsamrdFQ@mail.gmail.com>
 <CAH2-WzkExhbc5a7tuVy_pZFFiWZ4RiZTRfwVVM2+bcHUqor9ow@mail.gmail.com> <CAEze2WhRRnqeCjTZ3peSSdYVH5vc=o1V_hwRFqbjjNggpgDx4Q@mail.gmail.com>
In-Reply-To: <CAEze2WhRRnqeCjTZ3peSSdYVH5vc=o1V_hwRFqbjjNggpgDx4Q@mail.gmail.com>
From: Peter Geoghegan <pg@bowt.ie>
Date: Thu, 27 Jul 2023 10:00:31 -0400
Message-ID: <CAH2-WznprRoyeK1FmxpV6wHZESrjimmvv1J1hTwKuvMbah8LMA@mail.gmail.com>
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column
 ordered scans, skip scan
To: Matthias van de Meent <boekewurm+postgres@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>, Tom Lane <tgl@sss.pgh.pa.us>, 
	Tomas Vondra <tomas.vondra@enterprisedb.com>, Jeff Davis <pgsql@j-davis.com>, 
	benoit <benoit@hopsandfork.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://www.postgresql.org/message-id/CAH2-WznprRoyeK1FmxpV6wHZESrjimmvv1J1hTwKuvMbah8LMA%40mail.gmail.com>
Precedence: bulk

On Thu, Jul 27, 2023 at 7:59=E2=80=AFAM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> > Basically, the patch that added that feature had to revise the index
> > AM API, in order to support a mode of operation where scans return
> > groupings rather than tuples. Whereas this patch requires none of
> > that. It makes affected index scans as similar as possible to
> > conventional index scans.
>
> Hmm, yes. I see now where my confusion started. You called it out in
> your first paragraph of the original mail, too, but that didn't help
> me then:
>
> The wiki does not distinguish "Index Skip Scans" and "Loose Index
> Scans", but these are not the same.

A lot of people (myself included) were confused on this point for
quite a while. To make matters even more confusing, one of the really
compelling cases for the MDAM design is scans that feed into
GroupAggregates -- preserving index sort order for naturally big index
scans will tend to enable it. One of my examples from the start of
this thread showed just that. (It just so happened that that example
was faster because of all the "skipping" that nbtree *wasn't* doing
with the patch.)

> Yes, that's why I asked: The MDAM paper's examples seem to materialize
> the full predicate up-front, which would require a product of all
> indexed columns' quals in size, so that materialization has a good
> chance to get really, really large. But if we're not doing that
> materialization upfront, then there is no issue with resource
> consumption (except CPU time, which can likely be improved with other
> methods)

I get why you asked. I might have asked the same question.

As I said, the MDAM paper has *surprisingly* little to say about
B-Tree executor stuff -- it's almost all just describing the
preprocessing/transformation process. It seems as if optimizations
like the one from my patch were considered too obvious to talk about
and/or out of scope by the authors. Thinking about the MDAM paper like
that was what made everything fall into place for me. Remember,
"missing key predicates" isn't all that special.

--=20
Peter Geoghegan