Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-24 Thread Bruce Momjian
On Wed, May 16, 2012 at 09:25:13AM -0400, Tom Lane wrote:
 Volker Grabsch v...@notjusthosting.com writes:
  I propose the following general optimization: If all window
  functions are partitioned by the same first field (here: id),
  then any filter on that field should be executed before
  WindowAgg.
 
 I'm not sure if that rule is correct in detail, but in any case the
 short answer is that window aggregates are a new feature in Postgres
 and we basically haven't done any optimization work on them yet.
 Feel free to work in that area if it interests you...

Is this a TODO?

-- 
  Bruce Momjian  br...@momjian.ushttp://momjian.us
  EnterpriseDB http://enterprisedb.com

  + It's impossible for everything to be true. +

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-22 Thread Hitoshi Harada
On Thu, May 17, 2012 at 7:26 AM, Volker Grabsch v...@notjusthosting.com wrote:
 Hitoshi Harada schrieb:
 On Wed, May 16, 2012 at 12:50 AM, Volker Grabsch v...@notjusthosting.com 
 wrote:
  I propose the following general optimization: If all window
  functions are partitioned by the same first field (here: id),
  then any filter on that field should be executed before
  WindowAgg. So a query like this:

 I think that's possible.  Currently the planner doesn't think any
 qualification from the upper query can be pushed down to a query that
 has a window function.  It would be possible to let it push down if
 the expression matches PARTITION BY expression.

 Sounds great!

 However, the
 challenge is that a query may have a number of window functions that
 have different PARTITION BY expressions.  At the time of pushing down
 in the planning, it is not obvious which window function comes first.

 I'm don't really unterstand what you mean with which window function
 comes first, because to my understanding, all window functions of
 a query belong to the same level in the query hierarchy. But then,
 my knowledge of PostgreSQL internals isn't very deep, either.

No, you can specify as many window specification as you like.  Say,

SELECT count(*) over (w1), count(*) over (w2)
FROM tbl
WINDOW w1 AS (PARTITION BY x ORDER BY y),
  w2 AS (PARTITION BY y ORDER BYx);

and in the same query level there are different type of window
specifications.  The code as stands today doesn't have any semantics
about which of w1 or w2 to run first (probably w1 will be run first,
but the query semantics doesn't enforce anything).

 One idea is to restrict such optimization in only case of single
 window function, and the other is to make it generalize and cover a
 lot of cases.

 From a practical point of view, the restriction to a single window
 function wouldn't be that bad, although I'd prefer to think about
 the number of different windows rather than number of window functions.

 In other words, every optimization that is correct for a single window
 function is also correct for multiple window functions if those use
 all the same window.

Yeah, I mean, multiple windows, not window functions.

 That said, our planner on window functions has a lot of improvement to
 be done.  Every kind of optimization I see is what I raised above;
 they can be done easily by hacking in a small case, or they can be
 done by generalizing for the most of cases.  My understanding is our
 project tends to like the latter and it takes a little time but covers
 more use cases.

 I'd also prefer to see a general solution, as this provides less
 room for unpleasant surprises (e.g. This query is only slightly
 different from the previous one. Why does it take so much longer?).

 On the other hand, any small improvement is a big step forward
 regarding window functions.

 Unfortunately, I can't voluteer on that, as it is currently
 impossible for me to allocate enough time for this.

 However, any pointer to where to look at the source (or in the
 manual) would be of great. Maybe I'll find at least enough time
 to provide a rough proposal, or to improve existing attempts
 to solve this issue.

Look at subquery_is_pushdown_safe in allpath.c.  Here we stop looking
deeper if the upper qualification can be pushed down to the inner
sub-query if the sub-query has any window function expressions.


Thanks,
-- 
Hitoshi Harada

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-17 Thread Volker Grabsch
Hitoshi Harada schrieb:
 On Wed, May 16, 2012 at 12:50 AM, Volker Grabsch v...@notjusthosting.com 
 wrote:
  I propose the following general optimization: If all window
  functions are partitioned by the same first field (here: id),
  then any filter on that field should be executed before
  WindowAgg. So a query like this:
 
 I think that's possible.  Currently the planner doesn't think any
 qualification from the upper query can be pushed down to a query that
 has a window function.  It would be possible to let it push down if
 the expression matches PARTITION BY expression.

Sounds great!

 However, the
 challenge is that a query may have a number of window functions that
 have different PARTITION BY expressions.  At the time of pushing down
 in the planning, it is not obvious which window function comes first.

I'm don't really unterstand what you mean with which window function
comes first, because to my understanding, all window functions of
a query belong to the same level in the query hierarchy. But then,
my knowledge of PostgreSQL internals isn't very deep, either.

 One idea is to restrict such optimization in only case of single
 window function, and the other is to make it generalize and cover a
 lot of cases.

From a practical point of view, the restriction to a single window
function wouldn't be that bad, although I'd prefer to think about
the number of different windows rather than number of window functions.

In other words, every optimization that is correct for a single window
function is also correct for multiple window functions if those use
all the same window.

 That said, our planner on window functions has a lot of improvement to
 be done.  Every kind of optimization I see is what I raised above;
 they can be done easily by hacking in a small case, or they can be
 done by generalizing for the most of cases.  My understanding is our
 project tends to like the latter and it takes a little time but covers
 more use cases.

I'd also prefer to see a general solution, as this provides less
room for unpleasant surprises (e.g. This query is only slightly
different from the previous one. Why does it take so much longer?).

On the other hand, any small improvement is a big step forward
regarding window functions.

Unfortunately, I can't voluteer on that, as it is currently
impossible for me to allocate enough time for this.

However, any pointer to where to look at the source (or in the
manual) would be of great. Maybe I'll find at least enough time
to provide a rough proposal, or to improve existing attempts
to solve this issue.

Also, is there any chance to include a (simple) attempt of
such an optimiztation into PostgreSQL-9.2 beta, or is this
only a possible topic for 9.3 and later?


Regards,
Volker

-- 
Volker Grabsch
---(())---

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-17 Thread Nicolas Barbier
2012/5/17 Volker Grabsch v...@notjusthosting.com:

 Also, is there any chance to include a (simple) attempt of
 such an optimiztation into PostgreSQL-9.2 beta, or is this
 only a possible topic for 9.3 and later?

For 9.2, you’re about 4 months late :-). The last commitfest was in Januari:

URL:https://commitfest.postgresql.org/action/commitfest_view?id=13

Nicolas

-- 
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


[HACKERS] Missing optimization when filters are applied after window functions

2012-05-16 Thread Volker Grabsch
Dear PostgreSQL hackers,

[ please CC to me as I'm not subscribed to the list ]

I think there is a missing optimization when a filter is
applied after a window function, where the filtered field
is also used for partitioning.

Here a simplified example: Suppose we have a table
that stores 100.000 ids, and 10 random values per id:

create table test (
id integer,
value double precision,
primary key (id, value)
);

insert into test (id, value)
select
generate_series(1, 10) id,
random()
from
generate_series(1, 10);

We are now asking for the rank of each value per id
(it doesn't matter if it's rank() or any other window
function):

select
id,
value,
rank() over (partition by id order by value)
from
test;

Now suppose we're interested only in the result for
id 23000. If the query above was defined in a view,
this would lead to the following query:

select
*
from
(
select
id,
value,
rank() over (partition by id order by value)
from
test
) subquery
where
id = 23000;

This is very slow! The explain command shows the reason:

Subquery Scan on subquery  (cost=0.00..86556.80 rows=5000 width=20)
   Filter: (subquery.id = 23000)
-  WindowAgg  (cost=0.00..74056.80 rows=100 width=12)
 -  Index Scan using test_pkey on test  (cost=0.00..56556.80 
rows=100 width=12)

The Filter (id = 23000) is applied after WindowAgg,
although it could certainly be applied before!

Of course we could rewrite the above query like this:

select
id,
value,
rank() over (partition by id order by value)
from
test
where
id = 23000;

This would lead to a more sane plan where the filter is
applied before WindowAgg, making use of the primary key:

WindowAgg  (cost=43.53..43.70 rows=10 width=12)
  -  Sort  (cost=43.53..43.55 rows=10 width=12)
Sort Key: value
-  Bitmap Heap Scan on test  (cost=4.53..43.36 rows=10 width=12)
  Recheck Cond: (id = 23000)
  -  Bitmap Index Scan on test_pkey  (cost=0.00..4.53 rows=10 
width=0)
Index Cond: (id = 23000)

However, the second query cannot be cleanly split into
a generic view and a specialized part anymore.

In other words, it is currently impossible to use Window
functions in a View without risking serious, unexpected
performance issues, even in simple cases!

I propose the following general optimization: If all window
functions are partitioned by the same first field (here: id),
then any filter on that field should be executed before
WindowAgg. So a query like this:

select
...
from
(select
... over (partition by FIELD, other2, ...)
... over (partition by FIELD, other3, ...)
... over (partition by FIELD, ...)
...
)
where
SOME_FILTER(FIELD)

Shoule be transformed into that:

select
...
from
(select
... over (partition by FIELD, other2, ...)
... over (partition by FIELD, other3, ...)
... over (partition by FIELD, ...)
...
 where
SOME_FILTER(FIELD)
)

I verfied that this issue exists with PostgreSQL 9.2 beta 1
as well as the PostgreSQL 9.1 release.

Is there any work on this issue? Or am I wrong and this
optimization should not be implemented for some reason?


Regards,
Volker

-- 
Volker Grabsch
---(())---

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-16 Thread Tom Lane
Volker Grabsch v...@notjusthosting.com writes:
 I propose the following general optimization: If all window
 functions are partitioned by the same first field (here: id),
 then any filter on that field should be executed before
 WindowAgg.

I'm not sure if that rule is correct in detail, but in any case the
short answer is that window aggregates are a new feature in Postgres
and we basically haven't done any optimization work on them yet.
Feel free to work in that area if it interests you...

regards, tom lane

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Missing optimization when filters are applied after window functions

2012-05-16 Thread Hitoshi Harada
On Wed, May 16, 2012 at 12:50 AM, Volker Grabsch v...@notjusthosting.com 
wrote:
 I propose the following general optimization: If all window
 functions are partitioned by the same first field (here: id),
 then any filter on that field should be executed before
 WindowAgg. So a query like this:

I think that's possible.  Currently the planner doesn't think any
qualification from the upper query can be pushed down to a query that
has a window function.  It would be possible to let it push down if
the expression matches PARTITION BY expression.  However, the
challenge is that a query may have a number of window functions that
have different PARTITION BY expressions.  At the time of pushing down
in the planning, it is not obvious which window function comes first.
One idea is to restrict such optimization in only case of single
window function, and the other is to make it generalize and cover a
lot of cases.

That said, our planner on window functions has a lot of improvement to
be done.  Every kind of optimization I see is what I raised above;
they can be done easily by hacking in a small case, or they can be
done by generalizing for the most of cases.  My understanding is our
project tends to like the latter and it takes a little time but covers
more use cases.

Thanks,
-- 
Hitoshi Harada

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers