Re: Todo: Teach planner to evaluate multiple windows in the optimal order

Hi,

On 03/01/23 08:21, David Rowley wrote:
>
> I do think you'll likely want to put any WindowClauses which have
> pathkeys which are a true subset or true superset of the ORDER BY /
> DISTINCT pathkeys last.  If they're a superset then we won't need to
> perform any additional ordering for the DISTINCT / ORDER BY clause.
> If they're a subset then we might be able to perform an Incremental
> Sort, which is likely much cheaper than a full sort.  The existing
> code should handle that part. You just need to make
> select_active_windows() more intelligent.

I think current implementation does exactly this.

#1. If order by clause in the window function is subset of order by in query

create table abcd(a int, b int, c int, d int);
insert into abcd select x,y,z,c from generate_series(1,5) x, generate_Series(1,5)y, generate_Series(1,5) z, generate_Series(1,5) c;
explain analyze select a,row_number() over (order by b),count(*) over (order by a,b) from abcd order by a,b,c;

                                                             QUERY PLAN
         
--------------------------------------------------------------------------------------------------------------------------
--------
  Incremental Sort  (cost=80.32..114.56 rows=625 width=28) (actual time=1.440..3.311 rows=625 loops=1)
    Sort Key: a, b, c
    Presorted Key: a, b
    Full-sort Groups: 13  Sort Method: quicksort  Average Memory: 28kB  Peak Memory: 28kB
    ->  WindowAgg  (cost=79.24..91.74 rows=625 width=28) (actual time=1.272..2.567 rows=625 loops=1)
          ->  Sort  (cost=79.24..80.80 rows=625 width=20) (actual time=1.233..1.296 rows=625 loops=1)
                Sort Key: a, b
                Sort Method: quicksort  Memory: 64kB
                ->  WindowAgg  (cost=39.27..50.21 rows=625 width=20) (actual time=0.304..0.786 rows=625 loops=1)
                      ->  Sort  (cost=39.27..40.84 rows=625 width=12) (actual time=0.300..0.354 rows=625 loops=1)
                            Sort Key: b
                            Sort Method: quicksort  Memory: 54kB
                            ->  Seq Scan on abcd  (cost=0.00..10.25 rows=625 width=12) (actual time=0.021..0.161 rows=625 l
oops=1)
  Planning Time: 0.068 ms
  Execution Time: 3.509 ms
(15 rows)

Here, as window function (row count) has two cols a, b for order by, 
incremental sort is performed for remaining col in query,

which makes sense.


#2. If order by clause in the Window function is superset of order by in 
query

explain analyze select a,row_number() over (order by a,b,c),count(*) over (order by a,b) from abcd order by a;

                                                       QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
  WindowAgg  (cost=39.27..64.27 rows=625 width=28) (actual time=1.089..3.020 rows=625 loops=1)
    ->  WindowAgg  (cost=39.27..53.34 rows=625 width=20) (actual time=1.024..1.635 rows=625 loops=1)
          ->  Sort  (cost=39.27..40.84 rows=625 width=12) (actual time=1.019..1.084 rows=625 loops=1)
                Sort Key: a, b, c
                Sort Method: quicksort  Memory: 54kB
                ->  Seq Scan on abcd  (cost=0.00..10.25 rows=625 width=12) (actual time=0.023..0.265 rows=625 loops=1)
  Planning Time: 0.071 ms
  Execution Time: 3.156 ms
(8 rows)

No, additional sort is needed to be performed in this case, as you referred.

On 03/01/23 08:21, David Rowley wrote:
> If they're a superset then we won't need to perform any additional 
> ordering for the DISTINCT / ORDER BY clause.
> If they're a subset then we might be able to perform an Incremental
> Sort, which is likely much cheaper than a full sort.

So question is, how current implementation is different from desired one?

-- 
Regards,
Ankit Kumar Pandey