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

On Mon, Jul 8, 2019 at 9:37 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> Now, consider this example:
>
> create table t (a int, b int, c int);
> insert into t select mod(i,100),mod(i,100),i from generate_series(1,10000000) s(i);
> create index on t (a);
> analyze t;
> explain select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1;
>
> With 0001+0002+0003 pathes, I get a plan like this:
>
> QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------
> Limit (cost=10375.39..10594.72 rows=1 width=16)
> -> Incremental Sort (cost=10375.39..2203675.71 rows=10000 width=16)
> Sort Key: a, b, (sum(c))
> Presorted Key: a, b
> -> GroupAggregate (cost=10156.07..2203225.71 rows=10000 width=16)
> Group Key: a, b
> -> Gather Merge (cost=10156.07..2128124.39 rows=10000175 width=12)
> Workers Planned: 2
> -> Incremental Sort (cost=9156.04..972856.05 rows=4166740 width=12)
> Sort Key: a, b
> Presorted Key: a
> -> Parallel Index Scan using t_a_idx on t (cost=0.43..417690.30 rows=4166740 width=12)
> (12 rows)
>
>
> and with 0004, I get this:
>
> QUERY PLAN
> ------------------------------------------------------------------------------------------------------
> Limit (cost=20443.84..20665.32 rows=1 width=16)
> -> Incremental Sort (cost=20443.84..2235250.05 rows=10000 width=16)
> Sort Key: a, b, (sum(c))
> Presorted Key: a, b
> -> GroupAggregate (cost=20222.37..2234800.05 rows=10000 width=16)
> Group Key: a, b
> -> Incremental Sort (cost=20222.37..2159698.74 rows=10000175 width=12)
> Sort Key: a, b
> Presorted Key: a
> -> Index Scan using t_a_idx on t (cost=0.43..476024.65 rows=10000175 width=12)
> (10 rows)
>
> Notice that cost of the second plan is almost double the first one. That
> means 0004 does not even generate the first plan, i.e. there are cases
> where we don't try to add the explicit sort before passing the path to
> generate_gather_paths().
>
> And I think I know why is that - while gather_grouping_paths() tries to
> add explicit sort below the gather merge, there are other places that
> call generate_gather_paths() that don't do that. In this case it's
> probably apply_scanjoin_target_to_paths() which simply builds
>
> parallel (seq|index) scan + gather merge
>
> and that's it. The problem is likely the same - the code does not know
> which pathkeys are "interesting" at that point. We probably need to
> teach planner to do this.

I've been working on figuring out sample queries for each of the
places we're looking at adding create_increment_sort() (starting with
the cases enabled by gather-merge nodes). The
generate_useful_gather_paths() call in
apply_scanjoin_target_to_paths() is required to generate the above
preferred plan.

But I found that if I set enable_sort=off (with our without the
_useful_ variant of generate_gather_paths()) I get a very similar plan
that's actually lower cost yet:

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Limit (cost=10255.98..10355.77 rows=1 width=16)
-> Incremental Sort (cost=10255.98..1008228.67 rows=10000 width=16)
Sort Key: a, b, (sum(c))
Presorted Key: a, b
-> Finalize GroupAggregate (cost=10156.20..1007778.67
rows=10000 width=16)
Group Key: a, b
-> Gather Merge (cost=10156.20..1007528.67 rows=20000 width=16)
Workers Planned: 2
-> Partial GroupAggregate
(cost=9156.18..1004220.15 rows=10000 width=16)
Group Key: a, b
-> Incremental Sort
(cost=9156.18..972869.60 rows=4166740 width=12)
Sort Key: a, b
Presorted Key: a
-> Parallel Index Scan using t_a_idx
on t (cost=0.43..417703.85 rows=4166740 width=12)

Is that something we should consider a bug at this stage? It's also
not clear to mean (costing aside) which plan is intuitively
preferable.

James