optimizing constant quals within outer joins

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/

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.67 rows=151221 width=187)
Merge Cond: ("outer".objectid = "inner".objectid)
-> Sort (cost=441.55..454.06 rows=5004 width=45)
Sort Key: oip.objectid
-> Subquery Scan oip (cost=0.00..134.08 rows=5004 width=45)
-> Limit (cost=0.00..84.04 rows=5004 width=23)
-> Result (cost=0.00..84.04 rows=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 Scan on 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.13 rows=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.13 rows=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 sql stable 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 Scan on 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.74 rows=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.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)

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=19721 width=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.62 rows=1986 width=244)
Sort Key: b.unique1
-> Result (cost=0.00..162.86 rows=1986 width=244)
One-Time Filter: expensive(1)
-> Seq Scan on onek b (cost=0.00..162.86 rows=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