Re: Using Btree to Provide Sorting on Suffix Keys with LIMIT

On Sat, Dec 29, 2018 at 6:50 PM David Rowley
<david(dot)rowley(at)2ndquadrant(dot)com> wrote:
> > Areas of extension: (given index `(a, b, c)`) include `a = 1 and b in
> > (...) order by c` and `a in (...) and b = 1 order by c` (and further
> > similar derivations with increasing numbers of equality quals).
>
> I don't quite understand this the above paragraph, but I assume this
> would be possible to do with some new index am routine which allowed
> multiple different values for the initial key.

I'm confused about James' use of the term "new index am". I guess he
just meant new support function or something?

> > Note: Another (loosely) related problem is that sorting can't
> > currently take advantage of cases where an index provides a partial
> > (prefix of requested pathkeys) ordering.
>
> There has been a patch [2] around for about 4 years now that does
> this. I'm unsure of the current status, other than not yet committed.
>
> [1] https://www.postgresql.org/message-id/flat/7f70bd5a-5d16-e05c-f0b4-2fdfc8873489%40BlueTreble.com
> [2] https://www.postgresql.org/message-id/flat/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ(at)mail(dot)gmail(dot)com

I can see why you'd mention these two, but I also expected you to
mention the skip scan project, since that involves pushing down
knowledge about how the index is to be accessed to the index am (at
least, I assume that it does), and skipping leading attributes to use
the sort order from a suffix attribute. Actually, the partial sort
idea that you linked to is more or less a dual of skip scan, at least
to my mind (the former *extends* the sort order by adding a suffix
tie-breaker, while the latter *skips* a leading attribute to get to an
interesting suffix attribute).

The way James constructed his example suggested that there'd be some
kind of natural locality, that we'd expect to be able to take
advantage of at execution time when the new strategy is favorable. I'm
not sure if that was intended -- James? I think it might help James to
construct a more obviously realistic/practical motivating example. I'm
perfectly willing to believe that this idea would help his real world
queries, and having an example that can easily be played with is
helpful in other ways. But I'd like to know why this idea is important
is in detail, since I think that it would help me to place it in the
wider landscape of ideas that are like this. Placing it in that wider
landscape, and figuring out next steps at a high level seem to be the
problem right now.

--
Peter Geoghegan