Thread

1. [WIP] Caching constant stable expressions per execution

   Marti Raudsepp <marti@juffo.org> — 2011-09-10T22:27:17Z

   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
   

2. Re: [WIP] Caching constant stable expressions per execution

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-09-10T22:51:31Z

   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
   
   

3. Re: [WIP] Caching constant stable expressions per execution

   Josh Berkus <josh@agliodbs.com> — 2011-09-11T01:02:41Z

   > 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
   
   

4. Re: [WIP] Caching constant stable expressions per execution

   Josh Berkus <josh@agliodbs.com> — 2011-09-11T01:46:57Z

   > 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
   
   

5. Re: [WIP] Caching constant stable expressions per execution

   Marti Raudsepp <marti@juffo.org> — 2011-09-11T01:53:18Z

   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
   
   

6. Re: [WIP] Caching constant stable expressions per execution

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-09-11T21:22:26Z

   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 of
   	CASE 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
   
   

7. Re: [WIP] Caching constant stable expressions per execution

   Marti Raudsepp <marti@juffo.org> — 2011-09-12T21:27:48Z

   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
   
   

8. Re: [WIP] Caching constant stable expressions per execution

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-09-12T23:12:59Z

   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
   
   

9. Re: [WIP] Caching constant stable expressions per execution

   Marti Raudsepp <marti@juffo.org> — 2011-09-18T22:25:46Z

   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