Horton

Re: [PATCH] Incremental sort

Heikki Linnakangas <hlinnaka@iki.fi>

View thread View on postgr.es
From: Heikki Linnakangas <hlinnaka@iki.fi>
To: Alexander Korotkov <a.korotkov@postgrespro.ru>, Mithun Cy <mithun.cy@enterprisedb.com>
Cc: Robert Haas <robertmhaas@gmail.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2017-03-20T14:19:42Z
Lists: pgsql-hackers 
On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
> Please, find rebased patch in the attachment.

I had a quick look at this.

* I'd love to have an explanation of what an Incremental Sort is, in the 
file header comment for nodeIncrementalSort.c.

* I didn't understand the maxMem stuff in tuplesort.c. The comments 
there use the phrase "on-disk memory", which seems like an oxymoron. 
Also, "maximum status" seems weird, as it assumes that there's a natural 
order to the states.

* In the below example, the incremental sort is significantly slower 
than the Seq Scan + Sort you get otherwise:

create table foo (a int4, b int4, c int4);
insert into sorttest select g, g, g from generate_series(1, 1000000) g;
vacuum foo;
create index i_sorttest on sorttest (a, b, c);
set work_mem='100MB';


postgres=# explain select count(*) from (select * from sorttest order by 
a, c) as t;
                                               QUERY PLAN 

-------------------------------------------------------------------------------------------------------
  Aggregate  (cost=138655.68..138655.69 rows=1 width=8)
    ->  Incremental Sort  (cost=610.99..124870.38 rows=1102824 width=12)
          Sort Key: sorttest.a, sorttest.c
          Presorted Key: sorttest.a
          ->  Index Only Scan using i_sorttest on sorttest 
(cost=0.43..53578.79 rows=1102824 width=12)
(5 rows)

Time: 0.409 ms
postgres=# select count(*) from (select * from sorttest order by a, c) as t;
   count
---------
  1000000
(1 row)

Time: 387.091 ms


postgres=# explain select count(*) from (select * from sorttest order by 
a, c) 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, sorttest.c
          ->  Seq Scan on sorttest  (cost=0.00..15406.00 rows=1000000 
width=12)
(4 rows)

Time: 0.345 ms
postgres=# select count(*) from (select * from sorttest order by a, c) as t;
   count
---------
  1000000
(1 row)

Time: 231.668 ms

According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To 
alleviate that, it might be worthwhile to add a special case for when 
the group contains exactly one group, and not put the tuple to the 
tuplesort in that case. Or if we cannot ensure that the Incremental Sort 
is actually faster, the cost model should probably be smarter, to avoid 
picking an incremental sort when it's not a win.

- Heikki

Commits

  1. Further adjustments to Hashagg EXPLAIN ANALYZE output

  2. Rework EXPLAIN format for incremental sort

  3. Fix typos and improve incremental sort comments

  4. Stabilize incremental_sort tests

  5. Minor improvements in Incremental Sort explain

  6. Consider Incremental Sort paths at additional places

  7. Fix representation of SORT_TYPE_STILL_IN_PROGRESS.

  8. Fix failures in incremental_sort due to number of workers

  9. Fix show_incremental_sort_info with force_parallel_mode

  10. Implement Incremental Sort

  11. Fix handling of "Subplans Removed" field in EXPLAIN output.

  12. Fix EXPLAIN (SETTINGS) to follow policy about when to print empty fields.

  13. Ensure plpgsql result tuples have the right composite type marking.

  14. Propagate sort instrumentation from workers back to leader.

  15. Make new regression test case parallel-safe, and improve its output.

  16. Push limit through subqueries to underlying sort, where possible.

  17. Fix inappropriate printing of never-measured times in EXPLAIN.

  18. Fix some infelicities in EXPLAIN output for parallel query plans.