Thread: optimizing constant quals within outer joins
I have an optimization I'd like to see which I think should be pretty
easy for someone familiar with the planner code to implement. My
situation is this: I have an application using veil[1]. Essentially, I
have a schema "private" and another "public". Private contains regular
tables, where private contains views on those tables, like "create view
public.foo as select * from foo where i_have_global_priv('select_foo')",
and i_have_global_priv is a stable function.
My problem is that in several situations, postgresql is planning a
sequential scan with i_have_global_priv(n) as a filter, where N is some
constant literal specified in the view definition. This leads to the
function being called hundreds of thousands of times, which makes my
query orders of magnitude slower.
In some cases, the planner already optimizes this by moving the "where
i_have_global_priv(n)" qualification out of the seq scan filter and into
the one-time filter of a result node. The relevant function in the code
seems to be pull_constant_clauses, called from query_planner in
planmain.c around line 118.
By experimentation, it seems that this optimization will not be made on
either side of an outer join. For example:
dew=# explain select * from (select * from private.orderitem where i_have_global_priv(28)) as oi join (
select* from private.orderitemproduct where i_have_global_priv(32) ) as oip using (objectid);
QUERY PLAN
---------------------------------------------------------------------------------------Result (cost=96.56..402.70
rows=5004width=325) One-Time Filter: (i_have_global_priv(28) AND i_have_global_priv(32)) -> Hash Join
(cost=96.55..402.69rows=5004 width=325) Hash Cond: ("outer".objectid = "inner".objectid) -> Seq Scan on
orderitem (cost=0.00..165.44 rows=6044 width=306) -> Hash (cost=84.04..84.04 rows=5004 width=23)
-> Seq Scan on orderitemproduct (cost=0.00..84.04 rows=5004 width=23)
dew=# explain select * from (select * from private.orderitem where i_have_global_priv(28)) as oi left join (
select* from private.orderitemproduct where i_have_global_priv(32) ) as oip using (objectid);
QUERY PLAN
---------------------------------------------------------------------------------Hash Left Join (cost=100.72..301.94
rows=2015width=325) Hash Cond: ("outer".objectid = "inner".objectid) -> Seq Scan on orderitem (cost=0.00..180.55
rows=2015width=306) Filter: i_have_global_priv(28) -> Hash (cost=96.55..96.55 rows=1668 width=23) ->
SeqScan on orderitemproduct (cost=0.00..96.55 rows=1668 width=23) Filter: i_have_global_priv(32)
Notice that the cross join plan results in i_have_global_priv being
called just twice -- once for each privilege being checked, while the
left join plan will result in it being called once for each row.
So, is this something I can coerce someone into doing? It would be very
much appreciated here.
[1] <http://veil.projects.postgresql.org/>
On Wed, Jun 28, 2006 at 10:35:37AM -0400, Phil Frost wrote:
> I have an optimization I'd like to see which I think should be pretty
> easy for someone familiar with the planner code to implement. My
> situation is this: I have an application using veil[1]. Essentially, I
> have a schema "private" and another "public". Private contains regular
> tables, where private contains views on those tables, like "create view
> public.foo as select * from foo where i_have_global_priv('select_foo')",
> and i_have_global_priv is a stable function.
>
> My problem is that in several situations, postgresql is planning a
> sequential scan with i_have_global_priv(n) as a filter, where N is some
> constant literal specified in the view definition. This leads to the
> function being called hundreds of thousands of times, which makes my
> query orders of magnitude slower.
Is the function marked stable or immutable?
In the examples you give the planner can't move the function around the
tree because that would change the output of the query. For inner joins
it's ok, for outer joins it's much more tricky.
I thought the planner would evaluate constant conditions early on which
I why I'm asking about the function.
Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.
On Wed, Jun 28, 2006 at 05:11:59PM +0200, Martijn van Oosterhout wrote:
> On Wed, Jun 28, 2006 at 10:35:37AM -0400, Phil Frost wrote:
> > I have an optimization I'd like to see which I think should be pretty
> > easy for someone familiar with the planner code to implement. My
> > situation is this: I have an application using veil[1]. Essentially, I
> > have a schema "private" and another "public". Private contains regular
> > tables, where private contains views on those tables, like "create view
> > public.foo as select * from foo where i_have_global_priv('select_foo')",
> > and i_have_global_priv is a stable function.
> >
> > My problem is that in several situations, postgresql is planning a
> > sequential scan with i_have_global_priv(n) as a filter, where N is some
> > constant literal specified in the view definition. This leads to the
> > function being called hundreds of thousands of times, which makes my
> > query orders of magnitude slower.
>
> Is the function marked stable or immutable?
>
> In the examples you give the planner can't move the function around the
> tree because that would change the output of the query. For inner joins
> it's ok, for outer joins it's much more tricky.
>
> I thought the planner would evaluate constant conditions early on which
> I why I'm asking about the function.
i_have_global_priv is a stable function.
The planner in fact can move the function around without changing the
output. I can make it do so by putting "offset 0" in the subqueries:
dew=# explain select * from (select * from private.orderitem where i_have_global_priv(28) offset 0) as oi left join
( select * from private.orderitemproduct where i_have_global_priv(32) offset 0 ) as oip using (objectid);
QUERY PLAN
---------------------------------------------------------------------------------------------------Merge Right Join
(cost=1310.33..3603.67rows=151221 width=187) Merge Cond: ("outer".objectid = "inner".objectid) -> Sort
(cost=441.55..454.06rows=5004 width=45) Sort Key: oip.objectid -> Subquery Scan oip (cost=0.00..134.08
rows=5004width=45) -> Limit (cost=0.00..84.04 rows=5004 width=23) -> Result
(cost=0.00..84.04rows=5004 width=23) One-Time Filter: i_have_global_priv(32)
-> Seq Scan on orderitemproduct (cost=0.00..84.04 rows=5004 width=23) -> Sort (cost=868.78..883.89 rows=6044
width=146) Sort Key: oi.objectid -> Limit (cost=0.00..165.44 rows=6044 width=306) ->
Result (cost=0.00..165.44 rows=6044 width=306) One-Time Filter: i_have_global_priv(28)
-> Seq Scan on orderitem (cost=0.00..165.44 rows=6044 width=306)
The transformation is from this:
-> Seq Scan on orderitem (cost=0.00..180.55 rows=2015 width=306) Filter: i_have_global_priv(28)
to this:
-> Result (cost=0.00..165.44 rows=6044 width=306) One-Time Filter: i_have_global_priv(28) -> Seq
Scanon orderitem (cost=0.00..165.44 rows=6044 width=306)
which produce the same result. However, I'm not about to put "offset 0"
in all my view definitions, as that would prevent a number of other
extremely desirable optimizations.
Can a Result node not be an input to an outer join node? That would make
me sad :(
Phil Frost <indigo@bitglue.com> writes:
> The planner in fact can move the function around without changing the
> output.
Not when it's within the nullable side of an outer join --- moving a
WHERE clause up out of that would make the difference between no row
out, and a null-extended row out, which are certainly not the same.
I'm not sure why it's not pulling up from the left side of the left join
though. That might be a bug. What PG version is this exactly?
Of course the real question is why is your app generating such poorly
phrased queries ;-)
regards, tom lane
On Wed, Jun 28, 2006 at 11:40:52AM -0400, Tom Lane wrote:
> Phil Frost <indigo@bitglue.com> writes:
> > The planner in fact can move the function around without changing the
> > output.
>
> Not when it's within the nullable side of an outer join --- moving a
> WHERE clause up out of that would make the difference between no row
> out, and a null-extended row out, which are certainly not the same.
>
> I'm not sure why it's not pulling up from the left side of the left join
> though. That might be a bug. What PG version is this exactly?
>
> Of course the real question is why is your app generating such poorly
> phrased queries ;-)
Sure it can't pull the condition to the root result node, but it can
make an intermediate result node that is a child of the join and wraps
the sequential scan. "offset 0" makes it do this. I'd like this:
create table a(i int);
create table b(i int);
create function stable_function() returns bool language plpgsql stable as $$ begin return true; end $$;
create view c as select * from b where stable_function();
explain select * from a left join c using (i); QUERY PLAN
-----------------------------------------------------------------Merge Right Join (cost=220.32..338.32 rows=7629
width=4) Merge Cond: ("outer".i = "inner".i) -> Sort (cost=70.54..72.32 rows=713 width=4) Sort Key: b.i
-> Seq Scan on b (cost=0.00..36.75 rows=713 width=4) Filter: stable_function() -> Sort
(cost=149.78..155.13rows=2140 width=4) Sort Key: a.i -> Seq Scan on a (cost=0.00..31.40 rows=2140
width=4)
to become this:
QUERY PLAN
-----------------------------------------------------------------Merge Right Join (cost=220.32..338.32 rows=7629
width=4) Merge Cond: ("outer".i = "inner".i) -> Sort (cost=70.54..72.32 rows=713 width=4) Sort Key: b.i
-> Result One-Time Filter: stable_function() -> Seq Scan on b (cost=0.00..36.75 rows=713
width=4) Filter: stable_function() -> Sort (cost=149.78..155.13 rows=2140 width=4) Sort
Key:a.i -> Seq Scan on a (cost=0.00..31.40 rows=2140 width=4)
That will make the same results. Maybe there is something about the
implementation that I don't understand that makes it hard, but the
concept is simple: before you do a seq scan on b, you call
stable_function(), and if it returns true, you just do the sequential
scan without calling stable_function() for each row. If it returns
false, you can not do the sequental scan at all, and return the empty
set immediately.
I wasn't aware my queries are "badly phrased". The application generates
quite nice queries like "select * from saleorder_summary", which is a view
along the lines of 'select * from "order" left join saleorder using
(objectid)'. "order" and "saleorder" are views like "select * from
private.order where i_have_global_priv(20)". The subqueries are in the
examples I gave just to make it simpler to demonstrate.
The only other way I can think of phrasing a query like that is perhaps
select *
from private.order
left join purchaseorder on ( order.objectid = purchaseorder.objectid and i_have_global_priv(31)
)
This of course would not only be hugely inconvinent, but would require
that regular users have unrestricted access to the base tables, which
totally defeats the purpose of using veil. Also, that too is not
optimized as well as it could be:
test=# explain select * from a left join b on (a.i = b.i and stable_function()); QUERY PLAN
-----------------------------------------------------------------Merge Left Join (cost=299.56..710.97 rows=7633
width=8) Merge Cond: ("outer".i = "inner".i) Join Filter: stable_function() -> Sort (cost=149.78..155.13 rows=2140
width=4) Sort Key: a.i -> Seq Scan on a (cost=0.00..31.40 rows=2140 width=4) -> Sort
(cost=149.78..155.13rows=2140 width=4) Sort Key: b.i -> Seq Scan on b (cost=0.00..31.40 rows=2140
width=4)
stable_function() will still be called multiple times needlessly.
Tom Lane <tgl@sss.pgh.pa.us> writes:
> Phil Frost <indigo@bitglue.com> writes:
> > The planner in fact can move the function around without changing the
> > output.
>
> Not when it's within the nullable side of an outer join --- moving a
> WHERE clause up out of that would make the difference between no row
> out, and a null-extended row out, which are certainly not the same.
>
> I'm not sure why it's not pulling up from the left side of the left join
> though. That might be a bug. What PG version is this exactly?
In fact it doesn't even pull it up out of a regular join. I looked into this
when it was first brought up on IRC and as near as I can tell it is trying to
do so and somehow just failing.
postgres=# create function foo(text) returns bool as 'select case when $1 = ''foo'' then true else false end' language
sqlstable strict ;
postgres=# explain select 1 from a,a as b where foo('foo') ; QUERY PLAN
-------------------------------------------------------------------------Result (cost=31.34..75332.74 rows=3763600
width=0) One-Time Filter: foo('foo'::text) -> Nested Loop (cost=31.34..75332.74 rows=3763600 width=0) -> Seq
Scanon a (cost=0.00..29.40 rows=1940 width=0) -> Materialize (cost=31.34..50.74 rows=1940 width=0)
-> Seq Scan on a b (cost=0.00..29.40 rows=1940 width=0)
(6 rows)
postgres=# explain select 1 from (select * from a where foo('foo')) as x, a; QUERY PLAN
-----------------------------------------------------------------Nested Loop (cost=31.34..25169.19 rows=1255180
width=0) -> Seq Scan on a (cost=0.00..34.25 rows=647 width=0) Filter: foo('foo'::text) -> Materialize
(cost=31.34..50.74rows=1940 width=0) -> Seq Scan on a (cost=0.00..29.40 rows=1940 width=0)
(5 rows)
--
greg
Greg Stark <gsstark@mit.edu> writes:
>> I'm not sure why it's not pulling up from the left side of the left join
>> though. That might be a bug. What PG version is this exactly?
> In fact it doesn't even pull it up out of a regular join. I looked into this
> when it was first brought up on IRC and as near as I can tell it is trying to
> do so and somehow just failing.
Hm, some of this actually did work as recently as 8.1:
regression=# explain select 1 from (select * from int8_tbl where foo('foo')) as x; QUERY PLAN
--------------------------------------------------------------Result (cost=0.00..1.05 rows=5 width=0) One-Time
Filter:foo('foo'::text) -> Seq Scan on int8_tbl (cost=0.00..1.05 rows=5 width=0)
(3 rows)
while HEAD produces
regression=# explain select 1 from (select * from int8_tbl where foo('foo')) as x; QUERY PLAN
--------------------------------------------------------Seq Scan on int8_tbl (cost=0.00..1.06 rows=2 width=0) Filter:
foo('foo'::text)
(2 rows)
I think I broke that case by removing simplify_jointree from the "prep"
phase and moving its processing into deconstruct_jointree, which happens
after query_planner tries to pull out non-variable WHERE clauses.
The raw result of pull_up_subqueries will be a jointree that looks like
{FromExpr ({FromExpr ({RangeTblRef}) (foo function call)}) (empty top-level qual)}
and unfortunately query_planner is only looking in the topmost
FromExpr's qual list. Before, simplify_jointree would fold the two
FromExprs together before query_planner saw them, but now that doesn't
happen. Obviously Veil users are gonna be real unhappy about this :-(
The most direct fix for this would be to get rid of the
always-rather-ad-hoc pull_constant_clauses step in query_planner,
and make deconstruct_jointree responsible for recognizing potential
gating clauses and stashing them somewhere appropriate (probably in
a new field of PlannerInfo). However this only gets us back to stuff
that works in existing releases, it doesn't fix Phil's complaint.
Phil's problem is that the whole notion of moving constant quals into
a gating Result node is only applied at the top level of query_planner.
Seems like this would need to be pushed into the guts of the planner
to handle the cases he wants. Not quite sure where a clean place for
it would be ... [ thinks ... ] Maybe we should just let such quals be
processed normally all through the planner, and have createplan.c pull
them out at the last moment and stick a Result atop the plan node they
would otherwise have gone into. See also the note about variable-free
clauses in distribute_qual_to_rels. I think that code would still work
but we'd want to change the comment.
regards, tom lane
Phil Frost <indigo@bitglue.com> writes:
> I have an optimization I'd like to see which I think should be pretty
> easy for someone familiar with the planner code to implement.
I've done something about this for 8.2. It could possibly be improved
on, in that it's not terribly smart about where to place the gating
Result nodes, but at least it uses them correctly ...
regression=# explain select * from (select * from onek a where expensive(0)) ss1 join (select * from onek b where
expensive(1))ss2 using(unique1); QUERY PLAN
-------------------------------------------------------------------------------Result (cost=543.30..849.05 rows=19721
width=484) One-Time Filter: (expensive(0) AND expensive(1)) -> Merge Join (cost=543.30..849.05 rows=19721 width=484)
Merge Cond: (a.unique1 = b.unique1) -> Sort (cost=271.65..276.61 rows=1986 width=244) Sort
Key:a.unique1 -> Seq Scan on onek a (cost=0.00..162.86 rows=1986 width=244) -> Sort
(cost=271.65..276.61rows=1986 width=244) Sort Key: b.unique1 -> Seq Scan on onek b
(cost=0.00..162.86rows=1986 width=244)
(10 rows)
regression=# explain select * from (select * from onek a where expensive(0)) ss1 left join (select * from onek b where
expensive(1))ss2 using(unique1); QUERY PLAN
-------------------------------------------------------------------------------------Result (cost=543.30..849.05
rows=19721width=484) One-Time Filter: expensive(0) -> Merge Left Join (cost=543.30..849.05 rows=19721 width=484)
Merge Cond: (a.unique1 = b.unique1) -> Sort (cost=271.65..276.61 rows=1986 width=244) Sort
Key:a.unique1 -> Seq Scan on onek a (cost=0.00..162.86 rows=1986 width=244) -> Sort
(cost=271.65..276.62rows=1986 width=244) Sort Key: b.unique1 -> Result (cost=0.00..162.86
rows=1986width=244) One-Time Filter: expensive(1) -> Seq Scan on onek b
(cost=0.00..162.86rows=1986 width=244)
(12 rows)
regards, tom lane
Tom Lane wrote: > regression=# explain select * from (select * from onek a where expensive(0)) ss1 join (select * from onek b where expensive(1))ss2 using(unique1); > QUERY PLAN > ------------------------------------------------------------------------------- > Result (cost=543.30..849.05 rows=19721 width=484) > One-Time Filter: (expensive(0) AND expensive(1)) > -> Merge Join (cost=543.30..849.05 rows=19721 width=484) > Merge Cond: (a.unique1 = b.unique1) I note that the rowcount is not altered by the one-time filter. Is this an issue? I imagine the problem is not being able to estimate the number of rows that pass the filter. > -> Sort (cost=271.65..276.61 rows=1986 width=244) > Sort Key: a.unique1 > -> Seq Scan on onek a (cost=0.00..162.86 rows=1986 width=244) > -> Sort (cost=271.65..276.61 rows=1986 width=244) > Sort Key: b.unique1 > -> Seq Scan on onek b (cost=0.00..162.86 rows=1986 width=244) > (10 rows) I also wonder whether it wouldn't be better in this case to apply each filter to each arm of the merge join. -- Alvaro Herrera http://www.CommandPrompt.com/ The PostgreSQL Company - Command Prompt, Inc.
Alvaro Herrera <alvherre@commandprompt.com> writes:
> I note that the rowcount is not altered by the one-time filter. Is this
> an issue? I imagine the problem is not being able to estimate the
> number of rows that pass the filter.
That's intentional. The filter is either going to pass all or none of
the rows, not some fraction of them. It clearly isn't very reasonable
to guess that it will pass none of them (except if the qual is actually
constant FALSE).
> I also wonder whether it wouldn't be better in this case to apply each
> filter to each arm of the merge join.
Uh, why? For the most part, I'd think the higher you can put the filter
in the plan tree, the better.
regards, tom lane
Tom Lane wrote: > Alvaro Herrera <alvherre@commandprompt.com> writes: > > I note that the rowcount is not altered by the one-time filter. Is this > > an issue? I imagine the problem is not being able to estimate the > > number of rows that pass the filter. > > That's intentional. The filter is either going to pass all or none of > the rows, not some fraction of them. It clearly isn't very reasonable > to guess that it will pass none of them (except if the qual is actually > constant FALSE). > > > I also wonder whether it wouldn't be better in this case to apply each > > filter to each arm of the merge join. > > Uh, why? For the most part, I'd think the higher you can put the filter > in the plan tree, the better. Huh, sorry, I had misunderstood the meaning of a _one_-time filter :-) -- Alvaro Herrera http://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support