Re: PoC: Partial sort

First, thanks a lot for working on this feature. This PostgreSQL shortcoming crops up in all the time in web applications that implement paging by multiple sorted columns.

I've been trying it out in a few situations. I implemented a new enable_partialsort GUC to make it easier to turn on/off, this way it's a lot easier to test. The attached patch applies on top of partial-sort-5.patch

I will spend more time reviewing the patch, but some of this planner code is over my head. If there's any way I can help to make sure this lands in the next version, let me know.

----

The patch performs just as well as I would expect it to:

marti=# select ac.name, r.name from artist_credit ac join release r on (ac.id=r.artist_credit) order by ac.name, r.name limit 1000;
Time: 9.830 ms
marti=# set enable_partialsort = off;
marti=# select ac.name, r.name from artist_credit ac join release r on (ac.id=r.artist_credit) order by ac.name, r.name limit 1000;
Time: 1442.815 ms

A difference of almost 150x!

There's a missed opportunity in that the code doesn't consider pushing new Sort steps into subplans. For example, if there's no index on language(name) then this query cannot take advantage partial sorts:

marti=# explain select l.name, r.name from language l join release r on (l.id=r.language) order by l.name, r.name limit 1000;
 Limit  (cost=123203.20..123205.70 rows=1000 width=32)
   ->  Sort  (cost=123203.20..126154.27 rows=1180430 width=32)
         Sort Key: l.name, r.name
         ->  Hash Join  (cost=229.47..58481.49 rows=1180430 width=32)
               Hash Cond: (r.language = l.id)
               ->  Seq Scan on release r  (cost=0.00..31040.10 rows=1232610 width=26)
               ->  Hash  (cost=131.43..131.43 rows=7843 width=14)
                     ->  Seq Scan on language l  (cost=0.00..131.43 rows=7843 width=14)

But because there are only so few languages, it would be a lot faster to sort languages in advance and then do partial sort:

 Limit  (rows=1000 width=31)
   ->  Partial sort  (rows=1180881 width=31)
         Sort Key: l.name, r.name
         Presorted Key: l.name
         ->  Nested Loop  (rows=1180881 width=31)
               ->  Sort  (rows=7843 width=10)
                     Sort Key: name
                     ->  Seq Scan on language  (rows=7843 width=14)
               ->  Index Scan using release_language_idx on release r  (rows=11246 width=25)
                     Index Cond: (language = l.id)

Even an explicit sorted CTE cannot take advantage of partial sorts:
marti=# explain with sorted_lang as (select id, name from language order by name)
marti-# select l.name, r.name from sorted_lang l join release r on (l.id=r.language) order by l.name, r.name limit 1000;
 Limit  (cost=3324368.83..3324371.33 rows=1000 width=240)
   CTE sorted_lang
     ->  Sort  (cost=638.76..658.37 rows=7843 width=14)
           Sort Key: language.name
           ->  Seq Scan on language  (cost=0.00..131.43 rows=7843 width=14)
   ->  Sort  (cost=3323710.46..3439436.82 rows=46290543 width=240)
         Sort Key: l.name, r.name
         ->  Merge Join  (cost=664.62..785649.92 rows=46290543 width=240)
               Merge Cond: (r.language = l.id)
               ->  Index Scan using release_language_idx on release r  (cost=0.43..87546.06 rows=1232610 width=26)
               ->  Sort  (cost=664.19..683.80 rows=7843 width=222)
                     Sort Key: l.id
                     ->  CTE Scan on sorted_lang l  (cost=0.00..156.86 rows=7843 width=222)

But even with these limitations, this will easily be the killer feature of the next release, for me at least.