Delaying the planning of unnamed statements until Bind

Hello pgsql-hackers,

Following a recent discussion on the JDBC list
(http://archives.postgresql.org/pgsql-jdbc/2004-05/msg00100.php) I'm
looking at modifying when unnamed statements received via a v3 protocol
Parse message are planned. The idea is to delay planning until the Bind
message arrives, so that the planner benefits from knowing the actual
parameter values in use. This means that clients such as JDBC can use an
unnamed Parse/Bind as a way to provide typed and/or binary parameter
values without running the risk of worsening the query plan.

As this is my first excursion into the backend code (and the first time
I've touched any C for about a year, for that matter) I'd like to get a
sanity check on what I'm doing..

So far my changes involve:

1. Add a ParamListInfo parameter to pg_plan_query(), pg_plan_queries(),
planner(); this provides actual parameter values or NULL if
unavailiable. All existing callers except execute_bind_message pass NULL.

2. In execute_parse_message, if parsing into the unnamed statement,
first parse the query. If there are any parameters present, don't plan
the query yet (set unnamed_stat_pstmt->plan_list = NULL). Otherwise,
parse and plan as normal.

3. In execute_bind_message, if the source statement is not planned
(plan_list == NULL), plan it, passing the concrete parameter values
received in the Bind message. The planning happens using the target
portal's memory context; the resulting plan_list is only used for this
portal and the source statement remains unplanned. Move the call to
PortalDefineQuery() so that it occurs after parameters have been
received and any planning has been done.

4. In planner(), if parameters are provided, replace Param nodes with
Const nodes in the query tree where appropriate.

For 4) I have a couple of options:

a) thread a ParamListInfo parameter through the planner code. Pass it
to eval_const_expressions(). Make eval_const_expressions() do the
Param->Const replacement where possible in the mutated tree it produces.

b) if parameters are provided, do the Param->Const replacement at the
start of planner() using a custom tree walker.

4a) appears more efficient as it doesn't need another intermediate tree
copy, but it requires threading the parameter values through many
planner functions. There are quite a few (20-30ish?) functions affected.

4b) appears simpler to implement but requires more tree copying at runtime.

...

Does this look like a reasonable approach to take? Any suggestions, or
gotchas I've missed?

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> Following a recent discussion on the JDBC list
> (http://archives.postgresql.org/pgsql-jdbc/2004-05/msg00100.php) I'm
> looking at modifying when unnamed statements received via a v3 protocol
> Parse message are planned. The idea is to delay planning until the Bind
> message arrives, so that the planner benefits from knowing the actual
> parameter values in use. This means that clients such as JDBC can use an
> unnamed Parse/Bind as a way to provide typed and/or binary parameter
> values without running the risk of worsening the query plan.

I'm a bit concerned about driving such a change in behavior off nothing
more than whether the statement is named or not. The protocol spec does
say this:

: In addition, an "unnamed" prepared statement and portal exist. Although
: these behave largely the same as named objects, operations on them are
: optimized for the case of executing a query only once and then
: discarding it, whereas operations on named objects are optimized on the
: expectation of multiple uses.

so you could argue that this change is just an optimization of that
kind. It had better be documented though.

> 3. In execute_bind_message, if the source statement is not planned
> (plan_list == NULL), plan it, passing the concrete parameter values
> received in the Bind message.

I am not sure you can rely on plan_list == NULL to be the driving test;
consider an empty query string for instance. It'd be better to add a
boolean planning_done field to the struct.

> The planning happens using the target
> portal's memory context; the resulting plan_list is only used for this
> portal and the source statement remains unplanned.

I don't like that at all. Do the planning using the given parameters,
but save the plan. Otherwise you have substantially pessimized the
behavior for the case where an unnamed statement is reused.

> 4. In planner(), if parameters are provided, replace Param nodes with
> Const nodes in the query tree where appropriate.

No, you can't replace Params with Consts. You can use the values of
Params in the places where selfuncs.c wants to extract constant values
for estimation purposes.

> ... it requires threading the parameter values through many
> planner functions. There are quite a few (20-30ish?) functions affected.

This would be a pretty thorough mess, especially after you got done
propagating the info to selectivity functions. Frankly I'd suggest
using a planner global variable instead; see PlannerParamList for a
model.

regards, tom lane

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>Following a recent discussion on the JDBC list
>>(http://archives.postgresql.org/pgsql-jdbc/2004-05/msg00100.php) I'm
>>looking at modifying when unnamed statements received via a v3 protocol
>>Parse message are planned. The idea is to delay planning until the Bind
>>message arrives, so that the planner benefits from knowing the actual
>>parameter values in use. This means that clients such as JDBC can use an
>>unnamed Parse/Bind as a way to provide typed and/or binary parameter
>>values without running the risk of worsening the query plan.
>
>
> I'm a bit concerned about driving such a change in behavior off nothing
> more than whether the statement is named or not. The protocol spec does
> say this:
>
> : In addition, an "unnamed" prepared statement and portal exist. Although
> : these behave largely the same as named objects, operations on them are
> : optimized for the case of executing a query only once and then
> : discarding it, whereas operations on named objects are optimized on the
> : expectation of multiple uses.
>
> so you could argue that this change is just an optimization of that
> kind. It had better be documented though.

Ideally the when-to-plan decision should be client-controllable per
statement. I couldn't see a way to do this without causing a protocol
version change; using the unnamed statement sounded like a reasonable
compromise.

It'd also make the extended query protocol closer to the simple query
protocol as the documentation claims. This is the underlying problem
that bit me: the extended query protocol is *not* just the simple query
protocol broken down into smaller steps. There are non-obvious changes
deep in the guts of the system if you use the extra functionality of the
extended protocol.

Would it be better to bite the bullet and bump the protocol version,
adding a new field to Parse to control this behaviour?

>>3. In execute_bind_message, if the source statement is not planned
>>(plan_list == NULL), plan it, passing the concrete parameter values
>>received in the Bind message.
>
>
> I am not sure you can rely on plan_list == NULL to be the driving test;
> consider an empty query string for instance. It'd be better to add a
> boolean planning_done field to the struct.

Oops -- I made the incorrect assumption that NIL != NULL (i.e. it was a
shared placeholder node for empty lists).

Looks like this would only bite in the empty-query case (where
querytree_list is NIL). Trying to plan that via pg_plan_queries looks
fairly harmless. Nevertheless, I can add a field to the struct.

>>The planning happens using the target
>>portal's memory context; the resulting plan_list is only used for this
>>portal and the source statement remains unplanned.
>
>
> I don't like that at all. Do the planning using the given parameters,
> but save the plan. Otherwise you have substantially pessimized the
> behavior for the case where an unnamed statement is reused.

How often is the unnamed statement reused? From my exhaustive sample of
one (the JDBC driver) it's never reused. (admittedly that means it
doesn't affect me either way, but..)

If the planning behaviour was controllable per-statement, would you be
ok with replanning on every Bind when the statement asks for delaying
planning?

The reason I don't like storing the plan is that I see nothing special
about the first set (or Nth set) of parameters if the statement is being
reused, and you could come up with a plan that's substantially worse
than if you'd just planned before parameters were available (e.g.
picking an indexscan over a seqscan because the first Bind had selective
parameters, then subsequently Binding nonselective parameters).

>>4. In planner(), if parameters are provided, replace Param nodes with
>>Const nodes in the query tree where appropriate.
>
>
> No, you can't replace Params with Consts. You can use the values of
> Params in the places where selfuncs.c wants to extract constant values
> for estimation purposes.

Transforming the tree seemed the most reliable way to get a result
that's consistent with Const being in the tree from the start (i.e. the
simple query case), and doing the replacement hasn't broken anything in
my (admittedly brief) testing yet. What should I be looking at to see
the breakage?

Note that the Const vs. Param difference appears to affect
eval_const_expressions too, so it's more than just the selectivity
functions that would need changing if we want to produce the same query
plans as from an equivalent simple query.

>>... it requires threading the parameter values through many
>>planner functions. There are quite a few (20-30ish?) functions affected.
>
>
> This would be a pretty thorough mess, especially after you got done
> propagating the info to selectivity functions. Frankly I'd suggest
> using a planner global variable instead; see PlannerParamList for a
> model.

If I'm replacing the Param nodes it doesn't need to go as deep as the
selectivity functions. It's not great but it's not a disaster either.
Certainly if I needed to propagate all the way to the selectivity
functions it'd get out of control.

Would it be safe to save-and-clear the global parameter state only at
the topmost planner() level as is done for PlannerParamList and friends?
I'm concerned about the global parameter state interfering with the
parameter values of things like functions evaluated during planning.
Tracing the opportunities for recursion in the planner is, well,
interesting..

Thanks for your comments!

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> Tom Lane wrote:
>> I'm a bit concerned about driving such a change in behavior off nothing
>> more than whether the statement is named or not.

> Would it be better to bite the bullet and bump the protocol version,
> adding a new field to Parse to control this behaviour?

No, I don't think so. Protocol version changes are expensive. Maybe in
a few years we'll want to do another one, when we've accumulated a list
of things we want to fix. But not today and not for just one item.
I concur that making unnamed statements act this way is a reasonable
compromise for now. However it seems we still have a bit of a
disagreement as to what the details of "this way" are.

>> I don't like that at all. Do the planning using the given parameters,
>> but save the plan. Otherwise you have substantially pessimized the
>> behavior for the case where an unnamed statement is reused.

> How often is the unnamed statement reused?

Who's to say? If it's not reused then this argument is moot, so let's
assume there are people out there who want to reuse it. What behavior
will they wish for? The "plan with first set of actual parameters, then
keep using plan" behavior was discussed long ago, and it seems useful to
me to provide it. People who think they are going to have statistically
different parameter values from time to time will of course not want to
use this, but people who expect the same plan to continue to be useful
won't want to pay the overhead of replanning.

The reason this is important is exactly the one you have already seen,
namely that when faced with unknown Params the planner will sometimes
fall back to very conservative assumptions. An example that comes up
pretty often is
select * from mytable where entry_time >= $1;
The planner will take a seqscan when it sees this because it is worried
about the downside if a large fraction of the table is being selected.
However the people who do this generally know that they are always going
to provide cutoff times in the fairly recent past, which would make an
indexscan reasonable. So planning on the basis of the first supplied
parameter value would cause the right decisions to be made, and redoing
that on every call would just make for useless overhead.

In my experience planning is significantly more expensive than parse
analysis, and so people who do not want this behavior could avoid it
at relatively little cost by just re-sending Parse each time. But if
we don't provide the behavior then there is simply no way for people
who do want it to get it.

>> No, you can't replace Params with Consts.

> Transforming the tree seemed the most reliable way to get a result
> that's consistent with Const being in the tree from the start (i.e. the
> simple query case), and doing the replacement hasn't broken anything in
> my (admittedly brief) testing yet.

This depends on the outcome of the above discussion. If you're not
saving the plan then replacing params with constants is reasonable,
but if you are saving the plan then you can't do that.

> Would it be safe to save-and-clear the global parameter state only at
> the topmost planner() level as is done for PlannerParamList and friends?

Can't see why not. Note that I do not see this state as "global" in the
sense of affecting anything outside the planner.

regards, tom lane

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> select * from mytable where entry_time >= $1;
>
> The planner will take a seqscan when it sees this because it is worried
> about the downside if a large fraction of the table is being selected.

I wonder if it would make sense for the planner to be smarter about this. In a
sense the cost is a probability distribution, and representing it with a
single number, the expected value, is a just not enough information.

If the planner had the expected value as well as the variance of the cost
distribution then it might realize that in this case for instance that the
penalty for guessing wrong with an index scan is only going to be a small
slowdown factor, perhaps 2-4x slower. Whereas the penalty for guessing wrong
with a sequential scan could be a factor in the thousands or more.

In this particular case I think the guessing that a sequential scan is faster
is just plain wrong. There's a bit of hidden information here than the planner
isn't using which is that the DBA chose to put an index on this column. That
would mean some substantial number of queries are expected by a human to be
selective enough to warrant using an index.

--
greg

Greg Stark <gsstark(at)mit(dot)edu> writes:
> If the planner had the expected value as well as the variance of the cost
> distribution then it might realize that in this case for instance that the
> penalty for guessing wrong with an index scan is only going to be a small
> slowdown factor, perhaps 2-4x slower. Whereas the penalty for guessing wrong
> with a sequential scan could be a factor in the thousands or more.

Au contraire --- a full-table index scan can be vastly slower than a
full-table seqscan. I think it's wishful thinking to assume that
picking an indexscan is the right thing when we don't know any better.

regards, tom lane

Tom Lane wrote:

>Au contraire --- a full-table index scan can be vastly slower than a
>full-table seqscan. I think it's wishful thinking to assume that
>picking an indexscan is the right thing when we don't know any better.
>
>
>

I wish we could get this basic truth across to users somehow - I have
lost count of the number of times I have had to explain that the
crossover in cost between a sequential scan and an index scan occurs at
a surprisingly low proportion of a table in most cases.

cheers

andrew

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>Tom Lane wrote:

>>>I don't like that at all. Do the planning using the given parameters,
>>>but save the plan. Otherwise you have substantially pessimized the
>>>behavior for the case where an unnamed statement is reused.
>
>>How often is the unnamed statement reused?
>
> Who's to say? If it's not reused then this argument is moot, so let's
> assume there are people out there who want to reuse it.

The approach you suggest appears to affect the performance of the query
even in the case where the unnamed statement is not reused (see below),
so I don't think this is moot.

> What behavior
> will they wish for? The "plan with first set of actual parameters, then
> keep using plan" behavior was discussed long ago, and it seems useful to
> me to provide it. People who think they are going to have statistically
> different parameter values from time to time will of course not want to
> use this, but people who expect the same plan to continue to be useful
> won't want to pay the overhead of replanning.
>
> The reason this is important is exactly the one you have already seen,
> namely that when faced with unknown Params the planner will sometimes
> fall back to very conservative assumptions. An example that comes up
> pretty often is
> select * from mytable where entry_time >= $1;

Ok, I think I understand the argument now. As I understand it we have
three cases here:

1) Parameterized query where planning is expensive, and the general
parameterized plan with unknown Params provides a "good enough" plan.
This is already supported via PREPARE/EXECUTE or Parse/Bind with named
statements and would continue to be supported in the same way regardless
of what we do. No problems there.

2) Parameterized query where planning is expensive, specific parameter
values are needed to produce a good plan, and that plan remains "good
enough" for other parameter values because of the particular values used
by the client. This is the case you described above. I can see that this
behavior could be useful for specific queries. Currently, there's no way
to get equivalent behaviour -- this is a new feature. It might be
awkward for clients to actually *use*, as they can't interleave
different (unnamed) queries without replanning.

3) Parameterized query where specific parameter values are needed to
produce a good plan, and the benefit of a good plan outweighs the cost
of replanning each time. This can currently be done by substituting
parameters on the client side, but this forces the client to forego the
benefits of Bind (binary, typed, parameter transfer). So I see it as
letting clients make use of an existing feature, not a new feature :)

If (3) is not supported via Parse/Bind, a general client interface such
as JDBC has trouble using parameterized Parse/Bind by default: you don't
know how the query's performance will be affected. For our application,
parameterized Parse/Bind is a big win and we'll probably use it
regardless, but I don't know if my patches are going to be acceptable
for the official JDBC driver if it can reduce performance over the
current code which does parameter substitution on the client side.

The JDBC driver could have a driver-specific interface to control this,
but a) it's postgresql-specific which is bad for portable applications,
and b) the JDBC driver will need to maintain two code paths that do
essentially the same thing in different ways. Yuck.

From my point of view, if (2) and (3) are mutually exclusive then I'd
rather have (3).

>>>No, you can't replace Params with Consts.
>
>
>>Transforming the tree seemed the most reliable way to get a result
>>that's consistent with Const being in the tree from the start (i.e. the
>>simple query case), and doing the replacement hasn't broken anything in
>>my (admittedly brief) testing yet.
>
>
> This depends on the outcome of the above discussion. If you're not
> saving the plan then replacing params with constants is reasonable,
> but if you are saving the plan then you can't do that.

Ok, I understand: the replaced tree would be incorrect (not just
inefficient) if reused for subsequent parameter values, as it can modify
the tree based on the concrete Const values e.g. collapsing constant
subexpression trees to a single value.

This leads to my next problem (which was one of the original reasons I
went with node replacement): don't we get different performance between
a parameterized query and an equivalent unparameterized query in cases
such as this? :

SELECT * FROM sometable WHERE field = $1 * 10

The planner can't treat the multiplication expression as constant if $1
is a Param node when planning, even if we have concrete values for that
parameter -- so the selectivity estimates go out the window again.

This seems nontrivial to fix (you'd need a "constant parameterized
expression" node wrapping the expression, or something similar).

So with this approach a parameterized query via the unnamed statement
may perform worse than an equivalent unparameterized query, even if the
unnamed statement is not reused. This is the original problem I was
trying to solve in a slightly different guise.

>>Would it be safe to save-and-clear the global parameter state only at
>>the topmost planner() level as is done for PlannerParamList and friends?
>
>
> Can't see why not. Note that I do not see this state as "global" in the
> sense of affecting anything outside the planner.

Ok. I was concerned that the selectivity functions and similar places
that could use constant values for Param nodes might be called by code
conceptually "outside" the planner, but invoked when the planner ran
functions or similar. Is there any documentation on which nonstatic
functions are general utility functions and which are internal to the
planner code?

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> This leads to my next problem (which was one of the original reasons I
> went with node replacement): don't we get different performance between
> a parameterized query and an equivalent unparameterized query in cases
> such as this? :

> SELECT * FROM sometable WHERE field = $1 * 10

I don't think the run-time performance would be materially different in
most cases. What might happen is that if the selectivity functions are
stupid, they would fail to reduce the comparison value to a constant and
thus not be able to arrive at a good selectivity estimate, thus leading
to a bad plan choice. However we need not put up with the selectivity
functions being that stupid. I think it would be reasonable to
constant-fold expressions involving known parameter values *within the
context of selfuncs.c only*. This would let us get good estimates
without giving up the usability of the plan for fresh parameter values.

regards, tom lane

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>This leads to my next problem (which was one of the original reasons I
>>went with node replacement): don't we get different performance between
>>a parameterized query and an equivalent unparameterized query in cases
>>such as this? :
>
>
>> SELECT * FROM sometable WHERE field = $1 * 10
>
>
> I don't think the run-time performance would be materially different in
> most cases. What might happen is that if the selectivity functions are
> stupid, they would fail to reduce the comparison value to a constant and
> thus not be able to arrive at a good selectivity estimate, thus leading
> to a bad plan choice.

This appears to be true for all the selectivity functions in
utils/adt/selfuncs.c -- they rely on being given a constant-folded
expression tree.

> However we need not put up with the selectivity
> functions being that stupid. I think it would be reasonable to
> constant-fold expressions involving known parameter values *within the
> context of selfuncs.c only*. This would let us get good estimates
> without giving up the usability of the plan for fresh parameter values.

Ok, so something like this?

1) eval_const_expressions takes a list of parameter values and does
Param to Const replacement if given parameters.

2) The main planner does not pass parameters to eval_const_expressions.

3) When the selectivity functions care about a Const vs non-Const value
and they are dealing with a non-leaf expression node, they call
eval_const_expressions passing the expression tree & the planner-global
parameter values, and then look at the result's Const-ness again.

The alternative is to duplicate much of the logic of
eval_const_expressions into a helper function for anything that cares
about constants.

...

There appear to be a few other places where Const vs. Param affects the
resulting plan (clause_selectivity, LIMIT/OFFSET support, etc). Do the
same thing there?

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> Ok, so something like this?
> 1) eval_const_expressions takes a list of parameter values and does
> Param to Const replacement if given parameters.
> 2) The main planner does not pass parameters to eval_const_expressions.
> 3) When the selectivity functions care about a Const vs non-Const value
> and they are dealing with a non-leaf expression node, they call
> eval_const_expressions passing the expression tree & the planner-global
> parameter values, and then look at the result's Const-ness again.

Right.

> There appear to be a few other places where Const vs. Param affects the
> resulting plan (clause_selectivity, LIMIT/OFFSET support, etc). Do the
> same thing there?

clause_selectivity could reasonably do this. Not sure about
LIMIT/OFFSET.

regards, tom lane

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Greg Stark <gsstark(at)mit(dot)edu> writes:
> > If the planner had the expected value as well as the variance of the cost
> > distribution then it might realize that in this case for instance that the
> > penalty for guessing wrong with an index scan is only going to be a small
> > slowdown factor, perhaps 2-4x slower. Whereas the penalty for guessing wrong
> > with a sequential scan could be a factor in the thousands or more.
>
> Au contraire --- a full-table index scan can be vastly slower than a
> full-table seqscan.

Sure, but how much slower? 10x? 20? 100x? 1,000x? The old rule of thumb was
that the break-even point was somewhere around 15% selectivity which means it
would be about 7x slower. But whatever it is, it's going to be some
substantial but still linear slowdown. And the query will be slow but still
usable.

A mistaken sequential scan used when an index scan was needed could be
millions of times slower. The sequential scan time would have no relationship
at all with the index scan time with no upper bound on the slowdown at all.
In an OLTP environment the consequence of guessing wrong in this direction
would make the difference between the query working and it effectively failing
to work at all.

> I think it's wishful thinking to assume that picking an indexscan is the
> right thing when we don't know any better.

If we don't know any better then any solution is going to be wishful thinking.
It's kind of like a bridge game. If you don't know where the card is but you
need it somewhere in order to win, then you have to assume it's there and hope
for the best. If the index is wrong then the query was going to be slow either
way. If the index was right and you chose not to use it you're risking making
it slow unnecessarily and potentially when it was absoluetely required to be
fast.

As further evidence I'll mention Oracle falls back to the Rules-Based
optimizer if it has no statistics. The Rules-Based optimizer -- which was the
ONLY optimizer it used at all for many years -- always uses an index if it
can.

--
greg

Greg Stark <gsstark(at)MIT(dot)EDU> writes:

> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>
> > select * from mytable where entry_time >= $1;
> >
> > The planner will take a seqscan when it sees this because it is worried
> > about the downside if a large fraction of the table is being selected.

I'll mention another factor that's hidden here: The type of application that
cares about parse/optimization time enough and cares about plan stability
enough to reuse plans would be an OLTP application. The type of application
that would want to delay optimization until the parameters are known to
provide the best plan would be a DSS application or ad-hoc query.

So the very fact that the user is using placeholders like this is evidence
that the optimizer should err in the direction of assuming quick, very
selective queries.

If the specific value of $1 would help a large ad-hoc batch report run quicker
the user always has the option of providing it. The OLTP application running
thousands of queries per second doesn't have the option of doing that without
a serious performance hit.

--
greg

On Sat, 22 May 2004, Greg Stark wrote:

> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>
> > I think it's wishful thinking to assume that picking an indexscan is the
> > right thing when we don't know any better.
>
> If we don't know any better then any solution is going to be wishful thinking.
> It's kind of like a bridge game. If you don't know where the card is but you
> need it somewhere in order to win, then you have to assume it's there and hope
> for the best. If the index is wrong then the query was going to be slow either
> way. If the index was right and you chose not to use it you're risking making
> it slow unnecessarily and potentially when it was absoluetely required to be
> fast.

Could we try to plan for both cases? How about calculating the cutoff
point where the seqscan becomes faster than indexscan, creating a plan
with both paths, and picking which path to take at execute time?

More generally, keep *all* paths that make sense with *some* combination
of parameter values, and determine rules on which path to use with which
parameter values.

For example, if the query plan looks currently like this:

template1=# prepare b (int) AS SELECT * FROM foo WHERE bar > $1 ORDER BY bar*10;
PREPARE
template1=# explain EXECUTE b (2);
QUERY PLAN
-------------------------------------------------------------------------
Sort (cost=19.71..20.28 rows=230 width=4)
Sort Key: (bar * 10)
-> Index Scan using fooo on foo (cost=0.00..10.69 rows=230 width=4)
Index Cond: (bar > $1)
(4 rows)

It would become something like this:

template1=# prepare b (int) AS SELECT * FROM foo WHERE bar > $1 ORDER BY bar*10;
PREPARE
template1=# explain EXECUTE b (2);
QUERY PLAN
-------------------------------------------------------------------------
Sort (cost=19.71..20.28 rows=230 width=4)
Sort Key: (bar * 10)
if $1 > 400 then
-> Index Scan using fooo on foo (cost=0.00..10.69 rows=230 width=4)
Index Cond: (bar > $1)
else
-> Seq Scan on foo (cost=0.00..14.17 rows=629 width=4)
Filter: (bar > 100)

This means that execute stage would look at $1, and choose the seq scan if
it's > 400, otherwise use the seq scan.

I haven't looked at the planner code, I don't know how hard it would be to
implement, but I think it's something to consider.

Until we figure how to do the above, I think the plan-on-execute mode
would be very handy. However, it should not be on by default, IMHO.

I'm worried about plan stability if we enable it by default. It could
lead to nasty, hard to reproduce performance problems. Think about this
scenario:

A long-running server application prepares the query "SELECT * FROM foo
WHERE timestamp > $1". 99% of the transactions that use the prepared
query are online transactions that need to be very quick. They use
parameter values very close to now(), and should do an indexscan. The
rest are reports, running the same query with a parameter value of now() -
1 month. The reports should optimally use seqscan, but the slowness
of indexscan is acceptable too.

The application goes down every night for maintenance purposes, and is
restarted in the morning.

If the first transaction in the morning happens to be a report, all the
following online transactions will use a seqscan, and become veeery
slow. The operator gets angry phone calls, and reboots the system.
Everything starts to work ok.

Also keep in mind that at least some application servers have a
client-side prepared statement cache, so that even if the application
used a non-prepared statement for the reports, the middleware prepares it
anyway.

- Heikki

Heikki Linnakangas wrote:

> I'm worried about plan stability if we enable it by default. It could
> lead to nasty, hard to reproduce performance problems. Think about this
> scenario:

This is my main concern with the approach Tom suggested.

> Also keep in mind that at least some application servers have a
> client-side prepared statement cache, so that even if the application
> used a non-prepared statement for the reports, the middleware prepares it
> anyway.

It's less of an issue if we only use this behaviour when binding the
unnamed statement. The unnamed statement is quite "special" and is
unlikely to be reused accidentally (for one thing, you can only have one
unnamed statement..)

The patch I posted to -patches earlier uses this approach.

-O

I've applied the patch you sent in for this, with some editorializations
--- you were being too aggressive about substituting constants, with the
net effect that the plan was not still parameterized as it was supposed
to be.

I realized along the way that what we're really doing here is inventing
a notion of constant-folding expressions "for estimation purposes only".
As such, we don't have to be as rigid about making only provably safe
transformations as eval_const_expressions normally has to be. I didn't
do anything with the idea yet, but I'd like to look into having this
mode do more than just substitute Param values. An example that's been
causing us trouble for a long while is that the planner can't make any
nondefault selectivity estimate for
SELECT ... WHERE timestampcol > now() - '1 day';
because eval_const_expressions dare not reduce now() to current time.
But I think it would be entirely reasonable to do so "for estimation
purposes".

regards, tom lane

Tom Lane wrote:
> I've applied the patch you sent in for this, with some editorializations
> --- you were being too aggressive about substituting constants, with the
> net effect that the plan was not still parameterized as it was supposed
> to be.

Thanks. This should make my JDBC driver changes easier to sell.

> I realized along the way that what we're really doing here is inventing
> a notion of constant-folding expressions "for estimation purposes only".
> As such, we don't have to be as rigid about making only provably safe
> transformations as eval_const_expressions normally has to be. I didn't
> do anything with the idea yet, but I'd like to look into having this
> mode do more than just substitute Param values. An example that's been
> causing us trouble for a long while is that the planner can't make any
> nondefault selectivity estimate for
> SELECT ... WHERE timestampcol > now() - '1 day';
> because eval_const_expressions dare not reduce now() to current time.
> But I think it would be entirely reasonable to do so "for estimation
> purposes".

Something related I was pondering was adding a "constant expression at
execution" flag to various expression nodes. eval_const_expressions
would use this to mark expressions that are constant for a particular
execution, but can't be constant-folded safely at planning time
(essentially a STABLE modifier for expression trees).

The evaluate-for-estimation logic could use this to determine when it's
safe to evaluate the whole expression as constant. I think this handles
the now() case too, as STABLE functions are "constant at execution" if
their arguments are.

At execution time the executor can cache the results of expressions
flagged as constant at execution, assuming there's somewhere safe to
cache the result for just that execution (ExprState?). This should make
queries that use parameters in complex expressions go faster.

I took a quick look through the executor code, but couldn't see where
STABLE function results are cached (for the same arguments). Does this
currently happen? If not, we'd get that as well.

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> At execution time the executor can cache the results of expressions
> flagged as constant at execution, assuming there's somewhere safe to
> cache the result for just that execution (ExprState?).

That would be the problem; there isn't anyplace appropriate. I'm not
sure this is really worth pursuing...

> I took a quick look through the executor code, but couldn't see where
> STABLE function results are cached (for the same arguments).

They aren't. STABLE is not a cache-enabling modifier: what it is
actually for is to license the function to be used in an indexscan
qualification. Consider

where timestampcol > now() - '1 day';

If now() were considered volatile (ie, we had no guarantees at all about
its behavior --- consider random() as an example) then we could not
generate an indexscan on timestampcol, because an indexscan assumes that
the compared-to value is going to hold still throughout the indexscan.
Remember that the logical model defined by the SQL spec is that the
WHERE condition is evaluated at every row of the table --- we can only
optimize this if we can be sure that we know what the optimized-away
evaluations would produce.

This is why the definition of STABLE refers to holding still throughout
a table scan, rather than other reasonable alternatives one might
consider (such as being constant throughout one transaction).

I suppose you could envision the indexscan machinery as caching the
right-hand-side value in the index ScanKey, but this is far from being
a general purpose expression caching mechanism.

regards, tom lane

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>At execution time the executor can cache the results of expressions
>>flagged as constant at execution, assuming there's somewhere safe to
>>cache the result for just that execution (ExprState?).
>
>
> That would be the problem; there isn't anyplace appropriate. I'm not
> sure this is really worth pursuing...

Bear with me for a moment then :) .. It'd be nice to have for cases
where there's a frequently evaluated expensive expression that could be
constant-folded if it wasn't parameterized.

I guess that ExprState does not live long enough to be useful. How about
a single-entry cache in the expression node itself, with cache validity
tied to the ExprContext it was evaluated in? i.e. something like: use a
global counter to assign a sufficiently-unique ID to each ExprContext,
copy the context's ID to the cache when filling the cache, and only
treat the cache as valid when the cache's ID matches the current
context's ID.

>>I took a quick look through the executor code, but couldn't see where
>>STABLE function results are cached (for the same arguments).
>
>
> They aren't. STABLE is not a cache-enabling modifier: what it is
> actually for is to license the function to be used in an indexscan
> qualification.

> This is why the definition of STABLE refers to holding still throughout
> a table scan, rather than other reasonable alternatives one might
> consider (such as being constant throughout one transaction).

Ok. The CREATE FUNCTION documentation is a bit misleading: it does
specify the requirement to be immutable during a single table scan, but
the text and examples that follow describe a stronger requirement.

How about introducing a function modifier that provides stronger
guarantees than STABLE, along the lines of "immutable during execution
of a single SQL statement"? From a quick skim of pg_proc, it looks like
most if not all of the existing STABLE functions also meet the stronger
requirement.

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> I guess that ExprState does not live long enough to be useful.

Actually the opposite: it lasts too long, namely the entire execution of
a query. I don't think there's any convenient way to reset it on the
timescale appropriate for STABLE values (ie, once per scan, as opposed
to once per query).

> How about introducing a function modifier that provides stronger
> guarantees than STABLE, along the lines of "immutable during execution
> of a single SQL statement"?

Why?

I suspect that if we did have two flavors of STABLE, we'd just have a
lot of people getting it wrong :-(. A big advantage of the current
definition is exactly that it is pretty weak...

regards, tom lane

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>I guess that ExprState does not live long enough to be useful.
>
>
> Actually the opposite: it lasts too long, namely the entire execution of
> a query. I don't think there's any convenient way to reset it on the
> timescale appropriate for STABLE values (ie, once per scan, as opposed
> to once per query).

I think you misunderstand what I was suggesting. Given your earlier
clarification of what STABLE means, it isn't correct to mark expressions
involving a STABLE function as constant-at-execution-time, so those
results would not be cached. But there are still other expression trees
that would benefit, e.g. those involving an IMMUTABLE function with
parameterized arguments.

>>How about introducing a function modifier that provides stronger
>>guarantees than STABLE, along the lines of "immutable during execution
>>of a single SQL statement"?
>
> Why?

It's not directly useful currently, as there's no expression caching
going on. If there was expression caching, the stronger guarantees would
allow you to cache a wider range of expressions.

> I suspect that if we did have two flavors of STABLE, we'd just have a
> lot of people getting it wrong :-(. A big advantage of the current
> definition is exactly that it is pretty weak...

It seems quite hard to build a STABLE function that doesn't also satisfy
the stronger requirements. I can't think of how you'd do it as a SQL
function at all, off the top of my head. What sort of function were you
thinking of that is STABLE-safe but doesn't satisfy the stronger
requirements?

-O

Oliver Jowett <oliver(at)opencloud(dot)com> writes:
> But there are still other expression trees
> that would benefit, e.g. those involving an IMMUTABLE function with
> parameterized arguments.

Oh, you are thinking of some very-long-lived cache. This has been
proposed and rejected before; it's just not apparent that the costs of
maintaining and searching such a cache are justified by the possible
benefits. Most of the functions that actually appear in SQL commands
are cheap enough to evaluate that it'd not be worthwhile to do this at
all for them, ever --- the costs of executing datatype-specific
comparison functions to verify a hashtable hit would equal or exceed
the cost of evaluating the function.

There certainly are expensive user functions out there, and if we knew
which ones those were, it might be worth caching their values. But we
don't presently have any way to identify such functions. More, I'm not
convinced that very many of the ones that are that expensive can
reasonably be marked IMMUTABLE; an expensive function is likely one that
does database accesses.

> It seems quite hard to build a STABLE function that doesn't also satisfy
> the stronger requirements. I can't think of how you'd do it as a SQL
> function at all, off the top of my head. What sort of function were you
> thinking of that is STABLE-safe but doesn't satisfy the stronger
> requirements?

Anything at all that inspects database contents is probably STABLE and
not anything stronger, since it could potentially be affected by
intra-transaction updates. (The definition of STABLE is partly
motivated by MVCC semantics, particularly the fact that updates executed
by a command only become visible at CommandCounterIncrement boundaries.)

regards, tom lane

Tom Lane wrote:
> Oliver Jowett <oliver(at)opencloud(dot)com> writes:
>
>>But there are still other expression trees
>>that would benefit, e.g. those involving an IMMUTABLE function with
>>parameterized arguments.
>
> Oh, you are thinking of some very-long-lived cache. This has been
> proposed and rejected before; it's just not apparent that the costs of
> maintaining and searching such a cache are justified by the possible
> benefits. Most of the functions that actually appear in SQL commands
> are cheap enough to evaluate that it'd not be worthwhile to do this at
> all for them, ever --- the costs of executing datatype-specific
> comparison functions to verify a hashtable hit would equal or exceed
> the cost of evaluating the function.

I was actually thinking of only caching when the structure of the
expression tree means that it is known to be constant across some period
-- e.g. (non-subquery) Params remain constant across a single query
execution. So there's no hashtable or datatype-specific comparisons
involved. The cache only lives as long as you can guarantee the
expression tree remains constant. I'm just trying to work out the best
lifetime for the cache (or, equivalently, the types of expression tree
that can be marks as cacheable).

> There certainly are expensive user functions out there, and if we knew
> which ones those were, it might be worth caching their values. But we
> don't presently have any way to identify such functions. More, I'm not
> convinced that very many of the ones that are that expensive can
> reasonably be marked IMMUTABLE; an expensive function is likely one that
> does database accesses.

Fair enough. My concern is that if every query is parameterized by an
interface layer (as I'm planning to do with the JDBC driver), that one
expensive IMMUTABLE function is going to bite the application. So I'd
still like to see some sort of caching so that those few queries don't
run significantly slower, assuming that the cost of caching in the
common case is minor.

>>It seems quite hard to build a STABLE function that doesn't also satisfy
>>the stronger requirements. I can't think of how you'd do it as a SQL
>>function at all, off the top of my head. What sort of function were you
>>thinking of that is STABLE-safe but doesn't satisfy the stronger
>>requirements?
>
>
> Anything at all that inspects database contents is probably STABLE and
> not anything stronger, since it could potentially be affected by
> intra-transaction updates. (The definition of STABLE is partly
> motivated by MVCC semantics, particularly the fact that updates executed
> by a command only become visible at CommandCounterIncrement boundaries.)

Does that mean that these functions satisfy "IMMUTABLE until the next
CommandCounterIncrement"? That sounds more cacheable than the
tablescan-based definition.

-O