Re: Efficiently merging and sorting collections of sorted rows

On Fri, Jun 23, 2017 at 3:58 PM, Clint Miller <clint(dot)miller1(at)gmail(dot)com> wrote:
> Here, it's loading the full result set into memory and doing a quick sort.
> (I think that's what it's doing, at least. If that's not the case, let me
> know.) That's not good.

It's not sorting stuff that doesn't need to be read into memory in the
first place. In the case of your plan with the sequential scan, some
rows are eliminated early, before being input to the sort node.

> What I'd really like Postgres to do is use the index to get a sorted list of
> rows where s = 'a'. Then, use the index again to get a sorted list of rows
> where s = 'b'. Then it seems like Postgres should be able to merge the
> sorted lists into a single sorted result set in O(n) time and O(1) memory
> using a single merge operation.
>
> Am I doing something wrong here? Is there a way to get Postgres to not do a
> quick sort here?

I would like that too. There is a patch that does what I think you're
describing, but it seems to be in limbo:

https://commitfest.postgresql.org/11/409/

--
Peter Geoghegan