Re: [PATCH] Incremental sort (was: PoC: Partial sort)

On Sat, Mar 28, 2020 at 6:59 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>
> Hi,
>
> Attached is my take on simplification of the useful pathkeyes thing. It
> keeps the function, but it truncates query_pathkeys to only members with
> EC members in the relation. I think that's essentially the optimization
> you've proposed.

Thanks. I've included that in the patch series in this email (as a
separate patch) with a few additional comments.

I've also noticed that the enabled_incrementalsort check in
generate_useful_gather_paths seemed broken, because it returned us out
of the function before creating either a plain gather merge (if
already sorted) or an explicit sort path. I've included a patch that
moves it to the if block that actually builds the incremental sort
path.

> I've also noticed an issue in explain output. EXPLAIN ANALYZE on a simple
> query gives me this:
>
> QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------------------------------------------
> Gather Merge (cost=66.30..816060.48 rows=8333226 width=24) (actual time=6.464..19091.006 rows=10000000 loops=1)
> Workers Planned: 2
> Workers Launched: 2
> -> Incremental Sort (cost=66.28..729188.13 rows=4166613 width=24) (actual time=1.836..13401.109 rows=3333333 loops=3)
> Sort Key: a, b, c
> Presorted Key: a, b
> Full-sort Groups: 4156 (Methods: quicksort) Memory: 30kB (avg), 30kB (max)
> Presorted Groups: 4137 (Methods: quicksort) Memory: 108kB (avg), 111kB (max)
> Full-sort Groups: 6888 (Methods: ) Memory: 30kB (avg), 30kB (max)
> Presorted Groups: 6849 (Methods: ) Memory: 121kB (avg), 131kB (max)
> Full-sort Groups: 6869 (Methods: ) Memory: 30kB (avg), 30kB (max)
> Presorted Groups: 6816 (Methods: ) Memory: 128kB (avg), 132kB (max)
> -> Parallel Index Scan using t_a_b_idx on t (cost=0.43..382353.69 rows=4166613 width=24) (actual time=0.033..9346.679 rows=3333333 loops=3)
> Planning Time: 0.133 ms
> Execution Time: 23998.669 ms
> (15 rows)
>
> while with incremental sort disabled it looks like this:
>
> QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------------------------
> Gather Merge (cost=734387.50..831676.35 rows=8333226 width=24) (actual time=5597.978..14967.246 rows=10000000 loops=1)
> Workers Planned: 2
> Workers Launched: 2
> -> Sort (cost=734387.47..744804.00 rows=4166613 width=24) (actual time=5584.616..7645.711 rows=3333333 loops=3)
> Sort Key: a, b, c
> Sort Method: external merge Disk: 111216kB
> Worker 0: Sort Method: external merge Disk: 109552kB
> Worker 1: Sort Method: external merge Disk: 112112kB
> -> Parallel Seq Scan on t (cost=0.00..105361.13 rows=4166613 width=24) (actual time=0.011..1753.128 rows=3333333 loops=3)
> Planning Time: 0.048 ms
> Execution Time: 19682.582 ms
> (11 rows)
>
> So I think there's a couple of issues:
>
> 1) Missing worker identification (Worker #).

Fixed.

> 2) Missing method for workers (we have it for the leader, though).

Fixed. Since we can't have pointers in the parallel shared memory
space, we can't store the sort methods used in a list. To accomplish
the same goal, I've assigned the TuplesortMethod enum entries uique
bit positions, and store the methods used in a bitmask.

> 3) I'm not sure why the lable is "Methods" instead of "Sort Method", and
> why it's in parenthesis.

I've removed the parentheses. It's labeled "Methods" since there can
be more than one (different batches could use different methods). I've
updated this to properly use singular/plural depending on the number
of methods used.

> 4) Not sure having two lines for each worker is a great idea.

I've left these in for now because the lines are already very long
(much, much longer than the worker lines in a standard sort node).
This is largely because we're trying to summarize many sort batches,
while standard sort nodes only have to give the exact stats from a
single batch.

See the example output later in the email.

> 5) I'd probably prefer having multiple labels for avg/max memory values,
> instead of (avg) and (max) notes. Also, I think we use "peak" in this
> context instead of "max".

Updated.

Here's the current output:

Limit (cost=1887419.20..1889547.68 rows=10000 width=8) (actual
time=13218.403..13222.519 rows=10000 loo
ps=1)
-> Gather Merge (cost=1887419.20..19624748.03 rows=83333360
width=8) (actual time=13218.401..13229.7
50 rows=10000 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Incremental Sort (cost=1886419.17..10005010.55
rows=41666680 width=8) (actual time=13208.00
4..13208.586 rows=4425 loops=3)
Sort Key: a, b
Presorted Key: a
Full-sort Groups: 1 Sort Method: quicksort Memory:
avg=28kB peak=28kB
Presorted Groups: 1 Sort Method: top-N heapsort Memory:
avg=1681kB peak=1681kB
Worker 0: Full-sort Groups: 1 Sort Method: quicksort
Memory: avg=28kB peak=28kB
Presorted Groups: 1 Sort Method: top-N heapsort
Memory: avg=1680kB peak=1680kB
Worker 1: Full-sort Groups: 1 Sort Method: quicksort
Memory: avg=28kB peak=28kB
Presorted Groups: 1 Sort Method: top-N heapsort
Memory: avg=1682kB peak=1682kB
-> Parallel Index Scan using index_s_a on s
(cost=0.57..4967182.06 rows=41666680 width=8
) (actual time=0.455..11730.878 rows=6666668 loops=3)

James