Re: MDAM techniques and Index Skip Scan patch

On Tue, Mar 22, 2022 at 1:55 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Peter asked me off-list to spend some time thinking about the overall
> direction we ought to be pursuing here.

Thanks for taking a look!

"5.5 Exploiting Key Prefixes" and "5.6 Ordered Retrieval" from "Modern
B-Tree Techniques" are also good, BTW.

The terminology in this area is a mess. MySQL calls
SELECT-DISTINCT-that-matches-an-index "loose index scans". I think
that you're talking about skip scan when you say "loose index scan".
Skip scan is where there is an omitted prefix of columns in the SQL
query -- omitted columns after the first column that lack an equality
qual. Pretty sure that MySQL/InnoDB can't do that -- it can only
"skip" to the extent required to make
SELECT-DISTINCT-that-matches-an-index perform well, but that's about
it.

It might be useful for somebody to go write a "taxonomy of MDAM
techniques", or a glossary. The existing "Loose indexscan" Postgres
wiki page doesn't seem like enough. Something very high level and
explicit, with examples, just so we don't end up talking at cross
purposes too much.

> 1. Usually I'm in favor of doing this sort of thing in an index AM
> agnostic way, but here I don't see much point. All of the ideas at
> stake rely fundamentally on having a lexicographically-ordered multi
> column index; but we don't have any of those except btree, nor do
> I think we're likely to get any soon. This motivates the general
> tenor of my remarks below, which is "do it in access/nbtree/ not in
> the planner".

That was my intuition all along, but I didn't quite have the courage
to say so -- sounds too much like something that an optimizer
dilettante like me would be expected to say. :-)

Seems like one of those things where lots of high level details
intrinsically need to be figured out on-the-fly, at execution time,
rather than during planning. Perhaps it'll be easier to correctly
determine that a skip scan plan is the cheapest in practice than to
accurately cost skip scan plans. If the only alternative is a
sequential scan, then perhaps a very approximate cost model will work
well enough. It's probably way too early to tell right now, though.

> I've worried in the past that we'd
> need planner/statistical support to figure out whether a loose scan
> is likely to be useful compared to just plowing ahead in the index.

I don't expect to be able to come up with a structure that leaves no
unanswered questions about future MDAM work -- it's not realistic to
expect everything to just fall into place. But that's okay. Just
having everybody agree on roughly the right conceptual model is the
really important thing. That now seems quite close, which I count as
real progress.

> 4. I find each of the above ideas to be far more attractive than
> optimizing SELECT-DISTINCT-that-matches-an-index, so I don't really
> understand why the current patchsets seem to be driven largely
> by that single use-case. I wouldn't even bother with that for the
> initial patch.

I absolutely agree. I wondered about that myself in the past. My best
guess is that a certain segment of users are familiar with
SELECT-DISTINCT-that-matches-an-index from MySQL. And so to some
extent application frameworks evolved in a world where that capability
existed. IIRC Jesper once said that Hibernate relied on this
capability.

It's probably a lot easier to implement
SELECT-DISTINCT-that-matches-an-index if you have the MySQL storage
engine model, with concurrency control that's typically based on
two-phase locking. I think that MySQL does some amount of
deduplication in its executor here -- and *not* in what they call the storage
engine. This is exactly what I'd like to avoid in Postgres; as I said
"Maintenance of Index Order" (as the paper calls it) seems important,
and not something to be added later on. Optimizer and executor layers
that each barely know the difference between a skip scan and a full
index scan seems like something we might actually want to aim for,
rather than avoid. Teaching nbtree to transform quals into ranges
sounds odd at first, but it seems like the right approach now, on
balance -- that's the only *good* way to maintain index order.
(Maintaining index order is needed to avoid needing or relying on
deduplication in the executor proper, which is even inappropriate in
an implementation of SELECT-DISTINCT-that-matches-an-index IMO.)

--
Peter Geoghegan