Re: PoC: Partial sort
| От | Marti Raudsepp |
|---|---|
| Тема | Re: PoC: Partial sort |
| Дата | |
| Msg-id | CABRT9RAgLuWbUbTVAoABsxYeSVf7-CqfQJaRAHGAMsFP97MifQ@mail.gmail.com обсуждение исходный текст |
| Ответ на | Re: PoC: Partial sort (Alexander Korotkov <aekorotkov@gmail.com>) |
| Ответы |
Re: PoC: Partial sort
(Alexander Korotkov <aekorotkov@gmail.com>)
|
| Список | pgsql-hackers |
Hi Alexander,
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
----
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: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)
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)
-> 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)
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.
Regards,
Marti
Marti
On Mon, Jan 13, 2014 at 8:01 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
On Tue, Dec 31, 2013 at 5:41 AM, Andreas Karlsson <andreas@proxel.se> wrote:On 12/29/2013 08:24 AM, David Rowley wrote:It should be possible. I have hacked a quick proof of concept for reusing the tuplesort state. Can you try it and see if the performance regression is fixed by this?If it was possible to devise some way to reuse any
previous tuplesortstate perhaps just inventing a reset method which
clears out tuples, then we could see performance exceed the standard
seqscan -> sort. The code the way it is seems to lookup the sort
functions from the syscache for each group then allocate some sort
space, so quite a bit of time is also spent in palloc0() and pfree()
If it was not possible to do this then maybe adding a cost to the number
of sort groups would be better so that the optimization is skipped if
there are too many sort groups.
One thing which have to be fixed with my patch is that we probably want to close the tuplesort once we have returned the last tuple from ExecSort().
I have attached my patch and the incremental patch on Alexander's patch.Thanks. It's included into attached version of patch. As wall as estimation improvements, more comments and regression tests fix.------
With best regards,
Alexander Korotkov.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Вложения
В списке pgsql-hackers по дате отправления: