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

On Sun, 30 Dec 2018 at 13:00, James Coleman <jtc331(at)gmail(dot)com> wrote:
> Note that the index scan (or bitmap scan) nodes return all 1500 rows
> matching `bar_fk IN (1,2,3)`. After all rows are returned, that total
> set is ordered, and finally the LIMIT is applied. While only 50 rows
> were requested, 30x that were fetched from the heap.
>
> I believe it is possible to use the index
> `index_foos_on_bar_fk_and_created_at` to fulfill both the `bar_fk IN
> (1,2,3)` qualifier and (at least partially; more on that later) the
> ordering `ORDER BY created_at` while fetching fewer than all rows
> matching the qualifier.
>
> 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. Probably execution for
something like this could be handled by having 1 IndexScanDesc per
initial key. A scan would have to scan all of those for the first
tuple and return the lowest order key. Subsequent scans would fetch
the next tuple for the IndexScanDesc used previously then again,
return the lowest order tuple. There's some binary heap code and
examples in nodeMergeAppend.c about how that could be done fairly
efficiently.

The hard part about that would be knowing when to draw the line. If
there was 1000's of initial keys then some other method might be
better. Probably the planner would have to estimate which method was
best. There are also issues if there are multiple prefix keys as you'd
need to scan a cartesian product of the keys, which would likely get
out of hand quickly with 2 or more initial keys.

There were discussions and a patch for a planner-level implementation
of which could likely assist with this in [1]. I'm not sure if this
particular case was handled in the patch. I believe it was more
intended for queries such as: SELECT ... FROM t WHERE a = 1 OR b = 2
and could transform this into something more along the lines of:
SELECT .. FROM t WHERE a = 1 UNION SELECT ... FROM t WHERE b = 1, and
using the table's ctid to uniquify the rows. You could get away with
something similar but use UNION ALL instead. You don't need UNION
since your "OR" is on the same column, meaning there can be no
overlapping rows.

Something like:

(SELECT * FROM foos WHERE bar_fk = 1 LIMIT 50)
UNION ALL
(SELECT * FROM foos WHERE bar_fk = 2 LIMIT 50)
UNION ALL
(SELECT * FROM foos WHERE bar_fk = 3 LIMIT 50)
ORDER BY created_at LIMIT 50;

> 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

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services