Re: [HACKERS] [PATCH] Incremental sort - Mailing list pgsql-hackers
| From | Alexander Korotkov |
|---|---|
| Subject | Re: [HACKERS] [PATCH] Incremental sort |
| Date | |
| Msg-id | CAPpHfdu1UQmqioJt-UKt_o_MuXdAGovDgqRiUB8Sa092fVRvXg@mail.gmail.com Whole thread Raw |
| In response to | [HACKERS] [PATCH] Incremental sort (was: PoC: Partial sort) (Alexander Korotkov <a.korotkov@postgrespro.ru>) |
| Responses |
Re: [HACKERS] [PATCH] Incremental sort
(Peter Geoghegan <pg@bowt.ie>)
Re: [HACKERS] [PATCH] Incremental sort (Robert Haas <robertmhaas@gmail.com>) |
| List | pgsql-hackers |
On Wed, Mar 29, 2017 at 5:14 PM, Alexander Korotkov <a.korotkov@postgrespro.ru> wrote:
I added to cost_sort() extra costing for incremental sort: cost of extra tuple copying and comparing as well as cost of tuplesort reset.The only problem is that I made following estimate for tuplesort reset:run_cost += 10.0 * cpu_tuple_cost * num_groups;It makes ordinal sort to be selected in your example, but it contains constant 10 which is quite arbitrary. It would be nice to evade such hard coded constants, but I don't know how could we calculate such cost realistically.
That appears to be wrong. I intended to make cost_sort prefer plain sort over incremental sort for this dataset size. But, that appears to be not always right solution. Quick sort is so fast only on presorted data.
On my laptop I have following numbers for test case provided by Heikki.
Presorted data – very fast.
# explain select count(*) from (select * from sorttest order by a, c) as t;
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate (cost=147154.34..147154.35 rows=1 width=8)
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: sorttest.a, sorttest.c
-> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000 width=12)
(4 rows)
# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)
Time: 260,752 ms
Not presorted data – not so fast. It's actually slower than incremental sort was.
# explain select count(*) from (select * from sorttest order by a desc, c desc) as t;
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate (cost=130063.84..130063.85 rows=1 width=8)
-> Sort (cost=115063.84..117563.84 rows=1000000 width=12)
Sort Key: sorttest.a DESC, sorttest.c DESC
-> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000 width=12)
(4 rows)
# select count(*) from (select * from sorttest order by a desc, c desc) as t;
count
---------
1000000
(1 row)
Time: 416,207 ms
Thus, it would be nice to reflect the fact that our quicksort implementation is very fast on presorted data. Fortunately, we have corresponding statistics: STATISTIC_KIND_CORRELATION. However, it probably should be a subject of a separate patch.
But I'd like to make incremental sort not slower than quicksort in case of presorted data. New idea about it comes to my mind. Since cause of incremental sort slowness in this case is too frequent reset of tuplesort, then what if we would artificially put data in larger groups. Attached revision of patch implements this: it doesn't stop to accumulate tuples to tuplesort until we have MIN_GROUP_SIZE tuples.
# explain select count(*) from (select * from sorttest order by a, c) as t;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Aggregate (cost=85412.43..85412.43 rows=1 width=8)
-> Incremental Sort (cost=0.46..72912.43 rows=1000000 width=12)
Sort Key: sorttest.a, sorttest.c
Presorted Key: sorttest.a
-> Index Only Scan using i_sorttest on sorttest (cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)
# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)
Time: 251,227 ms
# explain select count(*) from (select * from sorttest order by a desc, c desc) as t;
QUERY PLAN
────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Aggregate (cost=85412.43..85412.43 rows=1 width=8)
-> Incremental Sort (cost=0.46..72912.43 rows=1000000 width=12)
Sort Key: sorttest.a DESC, sorttest.c DESC
Presorted Key: sorttest.a
-> Index Only Scan Backward using i_sorttest on sorttest (cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)
# select count(*) from (select * from sorttest order by a desc, c desc) as t;
count
---------
1000000
(1 row)
Time: 253,270 ms
Now, incremental sort is not slower than quicksort. And this seems to be cool.
However, in the LIMIT case we will pay the price of fetching some extra tuples from outer node. But, that doesn't seem to hurt us too much.
# explain select * from sorttest order by a, c limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Limit (cost=0.46..0.84 rows=10 width=12)
-> Incremental Sort (cost=0.46..37500.78 rows=1000000 width=12)
Sort Key: a, c
Presorted Key: a
-> Index Only Scan using i_sorttest on sorttest (cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)
# select * from sorttest order by a, c limit 10;
a | b | c
----+----+----
1 | 1 | 1
2 | 2 | 2
3 | 3 | 3
4 | 4 | 4
5 | 5 | 5
6 | 6 | 6
7 | 7 | 7
8 | 8 | 8
9 | 9 | 9
10 | 10 | 10
(10 rows)
Time: 0,903 ms
Any thoughts?
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
The Russian Postgres Company
Attachment
pgsql-hackers by date: