Re: Efficiently merging and sorting collections of sorted rows

Clint Miller <clint(dot)miller1(at)gmail(dot)com> writes:
> That's a good plan because it's not doing a quick sort. Instead, it's just
> reading the sort order off of the index, which is exactly what I want. (I
> had to disable enable_sort because I didn't have enough rows of test data
> in the table to get Postgres to use the index. But if I had enough rows,
> the enable_sort stuff wouldn't be necessary. My real table has lots of rows
> and doesn't need enable_sort turned off to do the sort with the index.)

TBH, I think this whole argument is proceeding from false premises.
Using an indexscan as a substitute for an explicit sort of lots of
rows isn't all that attractive, because it implies a whole lot of
random access to the table (unless the table is nearly in index
order, which isn't a condition you can count on without expending
a lot of maintenance effort to keep it that way). seqscan-and-sort
is often a superior alternative, especially if you're willing to give
the sort a reasonable amount of work_mem.

> 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.

If there's no duplicates to remove, I think this will work:

explain
(select * from foo a where s = 'a' order by i)
union all
(select * from foo b where s = 'b' order by i)
order by i;

Merge Append (cost=0.32..48.73 rows=12 width=36)
Sort Key: a.i
-> Index Only Scan using foo_idx on foo a (cost=0.15..24.26 rows=6 width=36)
Index Cond: (s = 'a'::text)
-> Index Only Scan using foo_idx on foo b (cost=0.15..24.26 rows=6 width=36)
Index Cond: (s = 'b'::text)

In this case it's pretty obvious that the two union arms can never
return the same row, but optimizing OR into UNION in general is
difficult because of the possibility of duplicates. I wouldn't
recommend holding your breath waiting for the planner to do this
for you.

regards, tom lane