Horton

Thread

Commits

  1. Account for startup rows when costing WindowAggs

  1. BUG #17862: Overall query cost ignores window function

    The Post Office <noreply@postgresql.org> — 2023-03-22T17:42:03Z

    The following bug has been logged on the website:

Bug reference:      17862
Logged by:          Tim Palmer
Email address:      tim3sp@gmail.com
PostgreSQL version: 15.2
Operating system:   Debian
Description:        

This query needs to read all of large_table to count the number of rows,
despite the LIMIT clause:

    SELECT large_table.*, count(*) OVER ()
    FROM generate_series(1, 1000000000000) large_table
    LIMIT 10

I would have expected a query plan something like this, with a large overall
cost:

 Limit  (cost=0.00..22500000000.00 rows=10 width=16)
   ->  WindowAgg  (cost=0.00..22500000000.00 rows=1000000000000 width=16)
         ->  Function Scan on generate_series large_table 
(cost=0.00..10000000000.00 rows=1000000000000 width=8)

But I actually get this query plan, with a cost of 0.23:

 Limit  (cost=0.00..0.23 rows=10 width=16)
   ->  WindowAgg  (cost=0.00..22500000000.00 rows=1000000000000 width=16)
         ->  Function Scan on generate_series large_table 
(cost=0.00..10000000000.00 rows=1000000000000 width=8)

I believe this (on a more complicated query) is affecting the plan chosen by
the optimizer.

  2. Re: BUG #17862: Overall query cost ignores window function

    David Rowley <dgrowleyml@gmail.com> — 2023-03-22T21:03:11Z

    On Thu, 23 Mar 2023 at 07:04, PG Bug reporting form
<noreply@postgresql.org> wrote:
>     SELECT large_table.*, count(*) OVER ()
>     FROM generate_series(1, 1000000000000) large_table
>     LIMIT 10
>
> I would have expected a query plan something like this, with a large overall
> cost:
>
>  Limit  (cost=0.00..22500000000.00 rows=10 width=16)
>    ->  WindowAgg  (cost=0.00..22500000000.00 rows=1000000000000 width=16)
>          ->  Function Scan on generate_series large_table
> (cost=0.00..10000000000.00 rows=1000000000000 width=8)
>
> But I actually get this query plan, with a cost of 0.23:
>
>  Limit  (cost=0.00..0.23 rows=10 width=16)
>    ->  WindowAgg  (cost=0.00..22500000000.00 rows=1000000000000 width=16)
>          ->  Function Scan on generate_series large_table
> (cost=0.00..10000000000.00 rows=1000000000000 width=8)

It likely would be possible to adjust cost_windowagg() to figure out a
startup_cost for getting the first row from a WindowFunc. Doing so
would require looking at the frame options and trying to figure out
how many rows need to be looked at. If you'd written count(*) OVER
(rows between current row and 10 following) then we'd only need to
look forward 10 rows from the current row. I'm really just not sure
this is worth the trouble unless you or someone else can demonstrate
that it's causing actual problems.

> I believe this (on a more complicated query) is affecting the plan chosen by
> the optimizer.

I immediately see what alternative plans could be considered and not
chosen as a result of this.  Can you give an example?

David

  3. Re: BUG #17862: Overall query cost ignores window function

    Tim Palmer <tim3sp@gmail.com> — 2023-03-23T14:40:55Z

    On Wed, 22 Mar 2023 at 21:03, David Rowley <dgrowleyml@gmail.com> wrote:
> It likely would be possible to adjust cost_windowagg() to figure out a
> startup_cost for getting the first row from a WindowFunc. Doing so
> would require looking at the frame options and trying to figure out
> how many rows need to be looked at. If you'd written count(*) OVER
> (rows between current row and 10 following) then we'd only need to
> look forward 10 rows from the current row.

The original query is attempting to retrieve one page of data and
(simultaneously) the total number of rows available to be paged through,
like the suggestion here https://stackoverflow.com/a/28888696.
A frame_end of '10 following' wouldn't be useful for that, but there's
probably no point in counting the exact row count beyond some limit
so potentially it could use something like '500 following'.

In the specific case of an empty OVER () clause, could the startup cost
be set to the total cost of the child plan node?

> > I believe this (on a more complicated query) is affecting the plan
chosen by
> > the optimizer.

> I immediately see what alternative plans could be considered and not
> chosen as a result of this.  Can you give an example?

As an example, given this table:

      CREATE TABLE t AS
      SELECT trunc(random() * 100) num1, trunc(random() * 100) num2
      FROM generate_series(1, 10000000);

      CREATE INDEX i ON t (num1);

      ANALYZE t;

And this query:

      SELECT t1.num1, count(*) OVER ()
      FROM t t1
      WHERE EXISTS (SELECT FROM t t2 WHERE t1.num1 = t2.num2)
      ORDER BY t1.num1
      LIMIT 10;

Here's the query plan with default settings:

      Limit  (cost=0.43..38.89 rows=10 width=16) (actual
time=124082.486..124082.494 rows=10 loops=1)
      ->  WindowAgg  (cost=0.43..38452467.86 rows=10000000 width=16)
(actual time=124082.485..124082.492 rows=10 loops=1)
            ->  Nested Loop Semi Join  (cost=0.43..38327467.86
rows=10000000 width=8) (actual time=0.137..121315.724 rows=10000000 loops=1)
                  Join Filter: (t1.num1 = t2.num2)
                  Rows Removed by Join Filter: 1003470239
                  ->  Index Only Scan using i on t t1
 (cost=0.43..259840.43 rows=10000000 width=8) (actual time=0.120..1343.223
rows=10000000 loops=1)
                        Heap Fetches: 0
                  ->  Materialize  (cost=0.00..243118.00 rows=10000000
width=8) (actual time=0.000..0.004 rows=101 loops=10000000)
                        ->  Seq Scan on t t2  (cost=0.00..154055.00
rows=10000000 width=8) (actual time=0.006..0.069 rows=569 loops=1)
      Planning Time: 0.193 ms
      Execution Time: 124105.899 ms

But there is a cheaper plan available (enable_indexscan=off,
enable_gathermerge=off):

      Limit  (cost=811708.65..811708.68 rows=10 width=16) (actual
time=8414.851..8414.855 rows=10 loops=1)
      ->  Sort  (cost=811708.65..836708.65 rows=10000000 width=16) (actual
time=8338.783..8338.787 rows=10 loops=1)
            Sort Key: t1.num1
            Sort Method: top-N heapsort  Memory: 25kB
            ->  WindowAgg  (cost=179057.25..595612.25 rows=10000000
width=16) (actual time=6114.888..7336.230 rows=10000000 loops=1)
                  ->  Hash Join  (cost=179057.25..470612.25 rows=10000000
width=8) (actual time=2067.306..4130.853 rows=10000000 loops=1)
                        Hash Cond: (t1.num1 = t2.num2)
                        ->  Seq Scan on t t1  (cost=0.00..154055.00
rows=10000000 width=8) (actual time=0.014..725.807 rows=10000000 loops=1)
                        ->  Hash  (cost=179056.00..179056.00 rows=100
width=8) (actual time=2067.281..2067.282 rows=100 loops=1)
                              Buckets: 1024  Batches: 1  Memory Usage: 12kB
                              ->  HashAggregate  (cost=179055.00..179056.00
rows=100 width=8) (actual time=2067.253..2067.264 rows=100 loops=1)
                                    Group Key: t2.num2
                                    Batches: 1  Memory Usage: 24kB
                                    ->  Seq Scan on t t2
 (cost=0.00..154055.00 rows=10000000 width=8) (actual time=0.005..853.380
rows=10000000 loops=1)
      Planning Time: 0.235 ms
      JIT:
      Functions: 18
      Options: Inlining true, Optimization true, Expressions true,
Deforming true
      Timing: Generation 1.088 ms, Inlining 2.531 ms, Optimization 51.099
ms, Emission 22.251 ms, Total 76.970 ms
      Execution Time: 8416.041 ms

Changing the window to only look at 500 rows doesn't impact the
chosen plan, but (as you suggested) makes the original plan much faster.
(This is with default settings again i.e. enable_indexscan=on,
enable_gathermerge=on):

      SELECT t1.num1, count(*) OVER (ROWS BETWEEN CURRENT ROW AND 500
FOLLOWING)
      FROM t t1
      WHERE EXISTS (SELECT FROM t t2 WHERE t1.num1 = t2.num2)
      ORDER BY t1.num1
      LIMIT 10;

      Limit  (cost=0.43..38.89 rows=10 width=16) (actual time=4.489..4.587
rows=10 loops=1)
      ->  WindowAgg  (cost=0.43..38452467.86 rows=10000000 width=16)
(actual time=4.487..4.581 rows=10 loops=1)
            ->  Nested Loop Semi Join  (cost=0.43..38327467.86
rows=10000000 width=8) (actual time=0.129..4.274 rows=511 loops=1)
                  Join Filter: (t1.num1 = t2.num2)
                  Rows Removed by Join Filter: 13286
                  ->  Index Only Scan using i on t t1
 (cost=0.43..259840.43 rows=10000000 width=8) (actual time=0.030..0.226
rows=511 loops=1)
                        Heap Fetches: 0
                  ->  Materialize  (cost=0.00..243118.00 rows=10000000
width=8) (actual time=0.000..0.003 rows=27 loops=511)
                        ->  Seq Scan on t t2  (cost=0.00..154055.00
rows=10000000 width=8) (actual time=0.009..0.018 rows=27 loops=1)
      Planning Time: 0.427 ms
      Execution Time: 4.657 ms


Tim

  4. Re: BUG #17862: Overall query cost ignores window function

    David Rowley <dgrowleyml@gmail.com> — 2023-03-25T01:40:00Z

    On Fri, 24 Mar 2023 at 03:41, Tim Palmer <tim3sp@gmail.com> wrote:
>
> On Wed, 22 Mar 2023 at 21:03, David Rowley <dgrowleyml@gmail.com> wrote:
> > It likely would be possible to adjust cost_windowagg() to figure out a
> > startup_cost for getting the first row from a WindowFunc. Doing so
> > would require looking at the frame options and trying to figure out
> > how many rows need to be looked at. If you'd written count(*) OVER
> > (rows between current row and 10 following) then we'd only need to
> > look forward 10 rows from the current row.
>
> The original query is attempting to retrieve one page of data and
> (simultaneously) the total number of rows available to be paged through,
> like the suggestion here https://stackoverflow.com/a/28888696.
> A frame_end of '10 following' wouldn't be useful for that, but there's
> probably no point in counting the exact row count beyond some limit
> so potentially it could use something like '500 following'.

I was just using the 10 following as an example of the fact that
WindowAgg does not always look at the entire partition to get the
first row.

> In the specific case of an empty OVER () clause, could the startup cost
> be set to the total cost of the child plan node?

It would likely improve your case and may be better in general, but
that would pretty much forego the planning making use of an cheap
startup plan when the WindowAgg just needed to look at a small number
of rows to fetch the first row. I highly doubt doing that would be
acceptable alone.

I think what it would take would be to look at each WindowFunc and
then estimate how many rows we need to look at for each WindowClause
and then take the Max of that number of rows and calculate the
proportion of the subpath's total cost we need to use based on the
number of estimated rows from the subpath.  I think the total subpath
rows would need to be divided by the ndistinct estimate for the
PARTITION BY clause too.

David

  5. Re: BUG #17862: Overall query cost ignores window function

    David Rowley <dgrowleyml@gmail.com> — 2023-04-12T09:05:55Z

    On Sat, 25 Mar 2023 at 14:40, David Rowley <dgrowleyml@gmail.com> wrote:
> I think what it would take would be to look at each WindowFunc and
> then estimate how many rows we need to look at for each WindowClause
> and then take the Max of that number of rows and calculate the
> proportion of the subpath's total cost we need to use based on the
> number of estimated rows from the subpath.  I think the total subpath
> rows would need to be divided by the ndistinct estimate for the
> PARTITION BY clause too.

I've written patch to fix this and started a thread on -hackers [1] to
discuss it.

David

[1] https://postgr.es/m/CAApHDvrB0S5BMv+0-wTTqWFE-BJ0noWqTnDu9QQfjZ2VSpLv_g@mail.gmail.com