Subject: Possible incorrect row estimation for Gather paths

From: Anthonin Bonnefoy <[email-masked]>
Date: Fri, 24 May 2024 11:35:10 +0200

Hi,

While experimenting on an explain option to display all plan candidates
(very rough prototype here [1]), I've noticed some discrepancies in some
generated plans.

EXPLAIN (ALL_CANDIDATES) SELECT * FROM pgbench_accounts order by aid;
 Plan 1
->  Gather Merge  (cost=11108.32..22505.38 rows=100000 width=97)
     Workers Planned: 1
     ->  Sort  (cost=10108.31..10255.37 rows=58824 width=97)
           Sort Key: aid
           ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..2228.24
rows=58824 width=97)
 Plan 2
->  Gather Merge  (cost=11108.32..17873.08 rows=58824 width=97)
     Workers Planned: 1
     ->  Sort  (cost=10108.31..10255.37 rows=58824 width=97)
           Sort Key: aid
           ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..2228.24
rows=58824 width=97)

The 2 plans are similar except one Gather Merge has a lower 58K estimated
rows.

The first plan is created with generate_useful_gather_paths with
override_rows=false then create_gather_merge_path and will use rel->rows as
the row count (so the 100K rows of pgbench_accounts).
#0: create_gather_merge_path(...) at pathnode.c:1885:30
#1: generate_useful_gather_paths(... override_rows=false) at
allpaths.c:3286:11
#2: apply_scanjoin_target_to_paths(...) at planner.c:7744:3
#3: grouping_planner(...) at planner.c:1638:3

The second plan is created through create_ordered_paths then
create_gather_merge_path and the number of rows is estimated to
(worker_rows * parallel_workers). Since we only have 1 parallel worker,
this yields 58K rows.
#0: create_gather_merge_path(...) at pathnode.c:1885:30
#1: create_ordered_paths(...) at planner.c:5287:5
#2: grouping_planner(...) at planner.c:1717:17

The 58K row estimate looks possibly incorrect. A worker row count is
estimated using total_rows/parallel_divisor. The parallel_divisor will
include the possible leader participation and will be 1.7 for 1 worker thus
the 58K rows (100K/1.7=58K)
However, the gather merge will only do 58K*1, dropping the leader
participation component.

I have a tentative patch split in two changes:
1: This is a related refactoring to remove an unnecessary and confusing
assignment of rows in create_gather_merge_path. This value is never used
and immediately overwritten in cost_gather_merge
2: This changes the row estimation of gather path to use
worker_rows*parallel_divisor to get a more accurate estimation.
Additionally, when creating a gather merge path in create_ordered_paths, we
try to use the source's rel rows when available.

The patch triggered a small change in the hash_join regression test. Pre
patch, we had the following candidates.
Plan 4
->  Aggregate  (cost=511.01..511.02 rows=1 width=8)
     ->  Gather  (cost=167.02..511.00 rows=2 width=0)
           Workers Planned: 1
           ->  Parallel Hash Join  (cost=167.02..510.80 rows=1 width=0)
                 Hash Cond: (r.id = s.id)
                 ->  Parallel Seq Scan on simple r  (cost=0.00..299.65
rows=11765 width=4)
                 ->  Parallel Hash  (cost=167.01..167.01 rows=1 width=4)
                       ->  Parallel Seq Scan on extremely_skewed s
 (cost=0.00..167.01 rows=1 width=4)
Plan 5
->  Finalize Aggregate  (cost=510.92..510.93 rows=1 width=8)
     ->  Gather  (cost=510.80..510.91 rows=1 width=8)
           Workers Planned: 1
           ->  Partial Aggregate  (cost=510.80..510.81 rows=1 width=8)
                 ->  Parallel Hash Join  (cost=167.02..510.80 rows=1
width=0)
                       Hash Cond: (r.id = s.id)
                       ->  Parallel Seq Scan on simple r
 (cost=0.00..299.65 rows=11765 width=4)
                       ->  Parallel Hash  (cost=167.01..167.01 rows=1
width=4)
                             ->  Parallel Seq Scan on extremely_skewed s
 (cost=0.00..167.01 rows=1 width=4)

Post patch, the plan candidates became:
Plan 4
->  Finalize Aggregate  (cost=511.02..511.03 rows=1 width=8)
     ->  Gather  (cost=510.80..511.01 rows=2 width=8)
           Workers Planned: 1
           ->  Partial Aggregate  (cost=510.80..510.81 rows=1 width=8)
                 ->  Parallel Hash Join  (cost=167.02..510.80 rows=1
width=0)
                       Hash Cond: (r.id = s.id)
                       ->  Parallel Seq Scan on simple r
 (cost=0.00..299.65 rows=11765 width=4)
                       ->  Parallel Hash  (cost=167.01..167.01 rows=1
width=4)
                             ->  Parallel Seq Scan on extremely_skewed s
 (cost=0.00..167.01 rows=1 width=4)
Plan 5
->  Aggregate  (cost=511.01..511.02 rows=1 width=8)
     ->  Gather  (cost=167.02..511.00 rows=2 width=0)
           Workers Planned: 1
           ->  Parallel Hash Join  (cost=167.02..510.80 rows=1 width=0)
                 Hash Cond: (r.id = s.id)
                 ->  Parallel Seq Scan on simple r  (cost=0.00..299.65
rows=11765 width=4)
                 ->  Parallel Hash  (cost=167.01..167.01 rows=1 width=4)
                       ->  Parallel Seq Scan on extremely_skewed s
 (cost=0.00..167.01 rows=1 width=4)

The FinalizeAggregate plan has an increased cost of 1 post patch due to the
number of rows in the Gather node that went from 1 to 2 (rint(1 * 1.7)=2).
This was enough to make the Agggregate plan cheaper. The test is to check
the parallel hash join so updating it with the new cheapest plan looked
fine.

Regards,
Anthonin

[1]: https://github.com/bonnefoa/postgres/tree/plan-candidates

---

From: Rafia Sabih <[email-masked]>
Date: Wed, 10 Jul 2024 16:54:22 +0200

Hello Anthonin,

I spent some time on this problem and your proposed solution.
As I understand it, this is the correction for the row count when the
number of parallel workers < 4.
Once the number of workers is 4 or more, the output from
parallel_divisor is the same as the number of parallel workers.
And then the number of rows for such cases would be the same with or
without the proposed patch.
So that way I think it is good to fix this case for a smaller number of workers.

But I don't quite understood the purpose of this,
+ total_groups = input_rel->rows;
+
+ /*
+ * If the number of rows is unknown, fallback to gather rows
+ * estimation
+ */
+ if (total_groups == 0)
+ total_groups = gather_rows_estimate(input_path);

why not just use total_groups = gather_rows_estimate(input_path), what
is the importance of having total_groups = input_rel->rows?

With respect to the change introduced by the patch in the regression
test, I wonder if we should test it on the tables of a larger scale
and check for performance issues.
Imagine the case when Parallel Seq Scan on extremely_skewed s
(cost=0.00..167.01 rows=1 width=4) returns 1000 rows instead of 1 ...
I wonder which plan would perform better then or will there be a
totally different plan.

However, my hunch is that there should not be serious problems,
because before this patch the number of estimated rows was incorrect
anyway.

I don't see a problem in merging the two patches.

On Fri, 24 May 2024 at 11:35, Anthonin Bonnefoy
<[email-masked]> wrote:
>
> Hi,
>
> While experimenting on an explain option to display all plan candidates (very rough prototype here [1]), I've noticed some discrepancies in some generated plans.
>
>            ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..2228.24 rows=58824 width=97)
>  Plan 2
>            ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..2228.24 rows=58824 width=97)
>
> The 2 plans are similar except one Gather Merge has a lower 58K estimated rows.
>
> The first plan is created with generate_useful_gather_paths with override_rows=false then create_gather_merge_path and will use rel->rows as the row count (so the 100K rows of pgbench_accounts).
> #1: generate_useful_gather_paths(... override_rows=false) at allpaths.c:3286:11
> The second plan is created through create_ordered_paths then create_gather_merge_path and the number of rows is estimated to (worker_rows * parallel_workers). Since we only have 1 parallel worker, this yields 58K rows.
> The 58K row estimate looks possibly incorrect. A worker row count is estimated using total_rows/parallel_divisor. The parallel_divisor will include the possible leader participation and will be 1.7 for 1 worker thus the 58K rows (100K/1.7=58K)
> However, the gather merge will only do 58K*1, dropping the leader participation component.
>
> 1: This is a related refactoring to remove an unnecessary and confusing assignment of rows in create_gather_merge_path. This value is never used and immediately overwritten in cost_gather_merge
> 2: This changes the row estimation of gather path to use worker_rows*parallel_divisor to get a more accurate estimation. Additionally, when creating a gather merge path in create_ordered_paths, we try to use the source's rel rows when available.
>
> The patch triggered a small change in the hash_join regression test. Pre patch, we had the following candidates.
> Plan 4
>                  ->  Parallel Seq Scan on simple r  (cost=0.00..299.65 rows=11765 width=4)
>                        ->  Parallel Seq Scan on extremely_skewed s  (cost=0.00..167.01 rows=1 width=4)
> Plan 5
>                        ->  Parallel Seq Scan on simple r  (cost=0.00..299.65 rows=11765 width=4)
>                              ->  Parallel Seq Scan on extremely_skewed s  (cost=0.00..167.01 rows=1 width=4)
>
>                        ->  Parallel Seq Scan on simple r  (cost=0.00..299.65 rows=11765 width=4)
>                              ->  Parallel Seq Scan on extremely_skewed s  (cost=0.00..167.01 rows=1 width=4)
> Plan 5
>                  ->  Parallel Seq Scan on simple r  (cost=0.00..299.65 rows=11765 width=4)
>                        ->  Parallel Seq Scan on extremely_skewed s  (cost=0.00..167.01 rows=1 width=4)
>
> The FinalizeAggregate plan has an increased cost of 1 post patch due to the number of rows in the Gather node that went from 1 to 2 (rint(1 * 1.7)=2). This was enough to make the Agggregate plan cheaper. The test is to check the parallel hash join so updating it with the new cheapest plan looked fine.
>
> Regards,
> Anthonin
>

-- 
Regards,
Rafia Sabih

---

From: Anthonin Bonnefoy <[email-masked]>
Date: Tue, 16 Jul 2024 09:56:31 +0200

Hi Rafia,

Thanks for reviewing.

> is the importance of having total_groups = input_rel->rows?

The initial goal was to use the source tuples if available and avoid
possible rounding errors. Though I realise that the difference would
be minimal. For example, 200K tuples and 3 workers would yield
int(int(200000 / 2.4) * 2.4)=199999. That is probably not worth the
additional complexity, I've updated the patch to just use
gather_rows_estimate.

> I wonder which plan would perform better then or will there be a
For the extremely_skewed test, having the parallel seq scan returning
more rows won't impact the Gather since The Hash Join will reduce the
number of rows to 1. I've found an example where we can see the plan
changes with the default settings:

CREATE TABLE simple (id SERIAL PRIMARY KEY, other bigint);
insert into simple select generate_series(1,500000), ceil(random()*100);
analyze simple;
EXPLAIN SELECT * FROM simple where other < 10 order by id;

Unpatched:
 Gather Merge  (cost=9377.85..12498.60 rows=27137 width=12)
   Workers Planned: 1
   ->  Sort  (cost=8377.84..8445.68 rows=27137 width=12)
         Sort Key: id
         ->  Parallel Seq Scan on simple  (cost=0.00..6379.47
rows=27137 width=12)
               Filter: (other < 10)

Patched:
 Sort  (cost=12381.73..12492.77 rows=44417 width=12)
   Sort Key: id
   ->  Seq Scan on simple  (cost=0.00..8953.00 rows=44417 width=12)
         Filter: (other < 10)

Looking at the candidates, the previous Gather Merge now has an
estimated number of rows of 44418. The 1 difference compared to the
other Gather Merge plan is due to rounding (26128 * 1.7 = 44417.6).

 Plan 3
   ->  Gather Merge  (cost=9296.40..14358.75 rows=44418 width=12)
         Workers Planned: 1
         ->  Sort  (cost=8296.39..8361.71 rows=26128 width=12)
               Sort Key: id
               ->  Parallel Seq Scan on simple  (cost=0.00..6379.47
rows=26128 width=12)
                     Filter: (other < 10)
 Plan 4
   ->  Gather Merge  (cost=9296.40..14358.63 rows=44417 width=12)
         Workers Planned: 1
         ->  Sort  (cost=8296.39..8361.71 rows=26128 width=12)
               Sort Key: id
               ->  Parallel Seq Scan on simple  (cost=0.00..6379.47
rows=26128 width=12)
                     Filter: (other < 10)
 Plan 5
   ->  Sort  (cost=12381.73..12492.77 rows=44417 width=12)
         Sort Key: id
         ->  Seq Scan on simple  (cost=0.00..8953.00 rows=44417 width=12)
               Filter: (other < 10)

The Sort plan is slightly slower than the Gather Merge plan: 100ms
average against 83ms but the Gather Merge comes at the additional cost
of creating and using a parallel worker. The unpatched row estimation
makes the parallel plan look cheaper and running a parallel query for
a 17ms improvement doesn't seem like a good trade.

I've also realised from the comments in optimizer.h that
nodes/pathnodes.h should not be included there and fixed it.

Regards,
Anthonin

---

From: Richard Guo <[email-masked]>
Date: Wed, 17 Jul 2024 09:59:05 +0800

I can reproduce this problem with the query below.

explain (costs on) select * from tenk1 order by twenty;
                                   QUERY PLAN
---------------------------------------------------------------------------------
 Gather Merge  (cost=772.11..830.93 rows=5882 width=244)
   Workers Planned: 1
   ->  Sort  (cost=772.10..786.80 rows=5882 width=244)
         Sort Key: twenty
         ->  Parallel Seq Scan on tenk1  (cost=0.00..403.82 rows=5882 width=244)
(5 rows)

> additional complexity, I've updated the patch to just use

I wonder if the changes in create_ordered_paths should also be reduced
to 'total_groups = gather_rows_estimate(path);'.

> nodes/pathnodes.h should not be included there and fixed it.

I think perhaps it's better to declare gather_rows_estimate() in
cost.h rather than optimizer.h.
(BTW, I wonder if compute_gather_rows() would be a better name?)

I noticed another issue in generate_useful_gather_paths() -- *rowsp
would have a random value if override_rows is true and we use
incremental sort for gather merge.  I think we should fix this too.

Thanks
Richard