Re: incremental sort vs. gather paths

On 12/16/21 17:48, Robert Haas wrote:
> This code introduced in ba3e76cc571eba3dea19c9465ff15ac3ac186576 looks
> wrong to me:
> 
>              total_groups = cheapest_partial_path->rows *
>                  cheapest_partial_path->parallel_workers;
>              path = (Path *)
>                  create_gather_merge_path(root, ordered_rel,
>                                           path,
>                                           path->pathtarget,
>                                           root->sort_pathkeys, NULL,
>                                           &total_groups);
> 
> This too:
> 
>                  total_groups = input_path->rows *
>                      input_path->parallel_workers;
> 
> This came to my attention because Dave Page sent me a query plan that
> looks like this:
> 
> Gather Merge  (cost=22617.94..22703.35 rows=732 width=97) (actual
> time=2561.476..2561.856 rows=879 loops=1)
>     Workers Planned: 2
>     Workers Launched: 2
>     ->  Sort  (cost=21617.92..21618.83 rows=366 width=97) (actual
> time=928.329..928.378 rows=293 loops=3)
>           Sort Key: aid
>           Sort Method: quicksort  Memory: 155kB
>           Worker 0:  Sort Method: quicksort  Memory: 25kB
>           Worker 1:  Sort Method: quicksort  Memory: 25kB
>           ->  Parallel Seq Scan on accounts_1m  (cost=0.00..21602.33
> rows=366 width=97) (actual time=74.391..74.518 rows=293 loops=3)
>                 Filter: (aid < 10000000)
>                 Rows Removed by Filter: 333040
> 
> If you look at the actual row count estimates, you see that the Gather
> Merge produces 3 times the number of rows that the Parallel Seq Scan
> produces, which is completely correct, because the raw number is 897
> in both cases, but EXPLAIN unhelpfully divides the displayed row count
> by the loop count, which in this case is 3. If you look at the
> estimated row count, you see that the Gather Merge is estimated to
> produce exactly 2 times the number of rows that the nodes under it
> would produce. That's not a very good estimate, unless
> parallel_leader_participation=off, which in this case it isn't.
> 
> What's happening here is that the actual number of rows produced by
> accounts_1m is actually 879 and is estimated as 879.
> get_parallel_divisor() decides to divide that number by 2.4, and gets
> 366, because it thinks the leader will do less work than the other
> workers. Then the code above fires and, instead of letting the
> original row count estimate for accounts_1m apply to the Gather Merge
> path, it overrides it with 2 * 366 = 732. This cannot be right.
> Really, I don't think it should be overriding the row count estimate
> at all. But if it is, multiplying by the number of workers can't be
> right, because the leader can also do stuff.
> 

Maybe, but other places (predating incremental sort) creating Gather 
Merge do the same thing, and commit ba3e76cc57 merely copied this. For 
example generate_gather_paths() does this:

     foreach(lc, rel->partial_pathlist)
     {
         Path       *subpath = (Path *) lfirst(lc);
         GatherMergePath *path;

         if (subpath->pathkeys == NIL)
             continue;

         rows = subpath->rows * subpath->parallel_workers;
         path = create_gather_merge_path(root, rel, subpath,
                                         rel->reltarget,
                                     subpath->pathkeys, NULL, rowsp);
         add_path(rel, &path->path);
     }

i.e. it's doing the same (rows * parallel_workers) calculation.

It may not not be the right way to estimate this, of course. But I'd say 
if ba3e76cc57 is doing it wrong, so are the older places.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company