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

On Mon, Jul 8, 2019 at 9:37 PM Tomas Vondra
<tomas.vondra@2ndquadrant.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