Thread: [WIP] Caching constant stable expressions per execution

Hi,

This is a proof of concept patch for recognizing stable function calls
with constant arguments and only calling them once per execution. I'm
posting it to the list to gather feedback whether this is a dead end
or not.

Last time when this was brought up on the list, Tom Lane commented
that doing the checks for constant folding probably outweigh the
gains. http://archives.postgresql.org/pgsql-hackers/2010-11/msg01641.php

Yesterday I was looking at evaluate_function(), where currently
function constant folding happens, and realized that most of the
knowledge needed to implement this for FuncExpr and OpExpr (and
combinations thereof) is already there. This would probably cover 90%
of the use cases with very little overhead. Other expression types
can't be supported very well with this approach, notably case
expressions and AND/OR/NOT.

However, the code isn't very pretty. It works by changing
evaluate_function() to recognize stable/immutable functions with
constant stable/immutable arguments that aren't eligible for constant
folding. It sets a new boolean attribute FuncExpr.stableconst which is
checked during the function's first execution. If true, the result is
stored in ExprState and evalfunc is replaced with a new one that
returns the cached result.

Most common use cases cover timestamptz expressions (because they are
never immutable) such as:
ts>=to_timestamp('2010-01-01', 'YYYY-MM-DD')
ts>=(now() - interval '10 days')

Typically an index on the column would marginalize performance lost by
repeatedly evaluating the function.

----

Test data (1,051,777 rows, 38MB):
create table ts as select generate_series(timestamptz '2001-01-01',
'2011-01-01', '5min') ts;

Test query (using pgbench -T 30, taking the best of 3 runs):
select * from ts where ts>=to_timestamp('2001-01-01', 'YYYY-MM-DD')
and ts<=to_timestamp('2001-01-01', 'YYYY-MM-DD');

Unpatched tps = 0.927458
Patched tps = 6.729378

There's even a measurable improvement from caching now() calls:
select * from ts where ts>now();

Unpatched tps = 8.106439
Patched tps = 9.401684

Regards,
Marti

Marti Raudsepp <marti@juffo.org> writes:
> This is a proof of concept patch for recognizing stable function calls
> with constant arguments and only calling them once per execution. I'm
> posting it to the list to gather feedback whether this is a dead end
> or not.

Hmm.  This is an interesting hack, but I'm not sure it's more than a
hack.

Usually what people have meant when they ask for "function caching"
is that multiple executions of a given stable function with the same
argument values be folded to just one execution.  In the general case
that would require some sort of hash table in which we memoize sets of
argument values and the corresponding result.  The reason that I've
generally discouraged this line of thought is that I see no way that
such a hash table could be managed or searched with sufficient
efficiency to make it a win.

What you've done here is to solve the problem for the special case of
a single (textual) instance of the function called with
plan-time-constant arguments.  While that's probably a common case,
I'm not sure it's common enough to justify extra planner and executor
complexity.

The patch as given has a bunch of implementation issues, but I think
it's close enough for crude performance testing, and your numbers do
show a potential performance benefit.  The question that I think is
unresolved is whether the set of cases covered is wide enough to be
useful in practice.  I have no data on that ...
        regards, tom lane

> The patch as given has a bunch of implementation issues, but I think
> it's close enough for crude performance testing, and your numbers do
> show a potential performance benefit.  The question that I think is
> unresolved is whether the set of cases covered is wide enough to be
> useful in practice.  I have no data on that ...

Well, I think its use for timestamp/interval/casting functions alone
covers a pretty substantial set of common user actions.  Frankly, the
case of not re-evaluating now() alone would be a significant real-life
improvement.

If I understand the limitations correctly, though, what this would do is
cause functions to perform substantially differently if called with
expressions as arguments instead of text constants, no?  Seems like that
would lead to some user confusion.  Although, with stuff like now(), we
already have that.

-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

> If I understand the limitations correctly, though, what this would do is
> cause functions to perform substantially differently if called with
> expressions as arguments instead of text constants, no?  Seems like that
> would lead to some user confusion.  Although, with stuff like now(), we
> already have that.

After some discussion on IRC, I realized I misunderstood the limitations
of the patch.  I'd say that this would be a significant improvement for
a large number of real-world cases.  The more in-depth solution ... that
is, one which would accept column parameters ... would of course make
this patch obsolete, but AFAIK nobody is working on that yet.


-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Sun, Sep 11, 2011 at 01:51, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Usually what people have meant when they ask for "function caching"
> is that multiple executions of a given stable function with the same
> argument values be folded to just one execution. In the general case
> that would require some sort of hash table

Right, this is more like execution-time constant folding. But I
decided not to call it that since I'm not "folding" the expression.

I know some people are writing queries like ts>=(SELECT now()-interval
'10 days') just to cache the single value from the expression.

> What you've done here is to solve the problem for the special case of
> a single (textual) instance of the function called with
> plan-time-constant arguments.

With a small tweak it can also support functions whose arguments are
(prepared query) placeholder variables.

> The patch as given has a bunch of implementation issues

This is my first patch that touches the more complicated internals of
Postgres. I'm sure I have a lot to learn. :)

Regards,
Marti

Marti Raudsepp <marti@juffo.org> writes:
> On Sun, Sep 11, 2011 at 01:51, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The patch as given has a bunch of implementation issues

> This is my first patch that touches the more complicated internals of
> Postgres. I'm sure I have a lot to learn. :)

Well, people seem to think that this is worth pursuing, so here's a
couple of thoughts about what needs to be done to get to something
committable.

First off, there is one way in which you are cheating that does have
real performance implications, so you ought to fix that before trusting
your performance results too much.  You're ensuring that the cached
datum lives long enough by doing this:

+    /* This cache has to persist for the whole query */
+    oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
+
+    fcache->cachedResult = ExecMakeFunctionResult(fcache, econtext, isNull, isDone);
+    fcache->cachedIsNull = *isNull;
+
+    /* Set-returning functions can't be cached */
+    Assert(!isDone || *isDone == ExprSingleResult);
+
+    MemoryContextSwitchTo(oldcontext);

IMO this is no good because it means that every intermediate result
computed within the cacheable expression will be leaked into
per_query_memory.  Yeah, you're only doing it once, but once could still
be too much.  Consider for instance the case where the function
internally generates a lot of cruft over multiple operations, and it
thinks it's cleaning up by resetting ecxt_per_tuple_memory every so
often.  If CurrentMemoryContext isn't pointing to ecxt_per_tuple_memory,
this loses.  I think what you need to do is run the function in the
normal environment and then use datumCopy() to save the value into
per_query_memory.  The reason this is performance-relevant is that the
datum copy step represents real added cycles.  I think it probably
doesn't invalidate the idea, but it'd be good to fix it and recheck
your performance numbers before putting in more work.  Assuming
that passes ...

The concept you're trying to encapsulate here is not really specific to
FuncExpr or OpExpr nodes.  Rather, the idea you want to implement is
"let's cache the result of any expression tree that contains no Vars,
internal Params, or volatile functions".  An example of this is that
the result ofCASE WHEN f1() > 42 THEN f2() ELSE NULL END
ought to be perfectly cacheable if f1 and f2 (and the > operator) are
stable or immutable.  Now it doesn't seem like a good plan to me to
plaster "stableconst" flags on every expression node type, nor to
introduce logic for handling that into everything in execQual.c.
So what I suggest is that you should invent a new expression node
type CacheExpr (that's just the first name that came to mind, maybe
somebody has a better idea) that takes an expression node as input
and caches the result value.  This makes things simple and clean in
the executor.  The planner would have to figure out where to inject
CacheExpr nodes into expression trees --- ideally only the minimum
number of nodes would be added.  I think you could persuade
eval_const_expressions to do that, but it would probably involve
bubbling additional information back up from each level of recursion.
I haven't thought through the details.

The other thing that is going to be an issue is that I'm fairly sure
this breaks plpgsql's handling of simple expressions.  (If there's not
a regression test that the patch is failing, there ought to be ...)
The reason is that we build an execution tree for a given simple
expression only once per transaction and then re-use it.  So for
example consider a plpgsql function containing
    x := stablefunction();

I think your patch means that stablefunction() would be called only once
per transaction, and the value would be cached and returned in all later
executions.  This would be wrong if the plpgsql function is called in
successive statements that have different snapshots, or contains a loop
around the assignment plus operations that change whatever state
stablefunction() looks at.  It would be legitimate for stablefunction()
to have different values in the successive executions.

The quick and dirty solution to this would be for plpgsql to pass some
kind of planner flag that disables insertion of CacheExpr nodes, or
alternatively have it not believe that CacheExpr nodes are safe to have
in simple expressions.  But that gives up all the advantage of the
concept for this use-case, which seems a bit disappointing.  Maybe we
can think of a better answer.
        regards, tom lane

On Mon, Sep 12, 2011 at 00:22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Well, people seem to think that this is worth pursuing, so here's a
> couple of thoughts about what needs to be done to get to something
> committable.

Thanks, that's exactly the kind of feedback I need.

> IMO this is no good because it means that every intermediate result
> computed within the cacheable expression will be leaked into
> per_query_memory.

Agreed, that's not ideal.

> type CacheExpr (that's just the first name that came to mind, maybe
> somebody has a better idea)

StableConstExpr? But we can leave the bikeshedding for later :)

> The planner would have to figure out where to inject
> CacheExpr nodes into expression trees --- ideally only the minimum
> number of nodes would be added.

Yeah, that occured to me, but seemed complicated at first, so I didn't
want to do it before having a confirmation from the list. However,
after looking at the expression tree walking code for a bit, it
doesn't seem that scary anymore.

> The other thing that is going to be an issue is that I'm fairly sure
> this breaks plpgsql's handling of simple expressions.

Oh, I would have never thought of that.

Regards,
Marti

Marti Raudsepp <marti@juffo.org> writes:
> On Mon, Sep 12, 2011 at 00:22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> type CacheExpr (that's just the first name that came to mind, maybe
>> somebody has a better idea)

> StableConstExpr? But we can leave the bikeshedding for later :)

Well, FWIW, I found that terminology entirely detestable.
        regards, tom lane

On Mon, Sep 12, 2011 at 00:22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The other thing that is going to be an issue is that I'm fairly sure
> this breaks plpgsql's handling of simple expressions.

> The quick and dirty solution to this would be for plpgsql to pass some
> kind of planner flag that disables insertion of CacheExpr nodes, or
> alternatively have it not believe that CacheExpr nodes are safe to have
> in simple expressions.  But that gives up all the advantage of the
> concept for this use-case, which seems a bit disappointing.  Maybe we
> can think of a better answer.

I got around to this and I think there's a better way.

PL/pgSQL "simple expressions" are queries that return a single row, a
single column, don't reference any tables, have no WHERE clauses etc.

All expressions in such queries would be evaluated only once anyway,
so don't benefit from cache -- and indeed could potentially be hurt by
the added overheads.

It seems that we could pre-empt this in the planner by recognizing
potentially-simple queries right from the start and forbidding
CacheExpr. Maybe add a new boolean to PlannerInfo?

However, I got stuck because set-returning functions aren't
immediately obvious -- I'd have to walk the whole expression tree to
find out. A query like "SELECT now(), generate_series(1,10)" isn't a
simple expression and could still benefit from cache for the now()
call.

Or we could just let it slip and not cache anything if there's no
FROM/WHERE clause.

Thoughts?

Regards,
Marti