> Ed Loehr wrote:
>
> > What would persuasive numbers look like?
> >
> > As a novice, I'd guess key questions would seem to be...
> >
> >         How often is a query run in which the results are identical to previous
> > invocations of that query?
> >
> >         Typically send/recv rates vs. typical query planning/exec time?
>
> So wouldn't you get most of what you want if you could store a query plan?

    This  should wait until after the proposed querytree overhaul
    we have in mind. I already discussed it with  Tom  Lane.  The
    idea goes like this:

    After  the  overhaul,  the rewriter is a very simple and fast
    step. So we could hook into  the  rewriter,  who  builds  for
    EVERY  query  kinda  key  based  on  the nodes, relations and
    functions that appear in the querytree.

    These keys could be managed in a shared LRU table, and if the
    same  key  appears  a  number  of  times  (0-n),  it's entire
    querytree + plan (after planning)  will  be  saved  into  the
    shared  mem.  At  a subsequent occurence, the querycache will
    look  closer  onto  the  two  trees,  if  they   are   really
    identically  WRT  all the nodes. If only constant values have
    changed, the already known plan could be reused.

    Postmaster startup options for tuning  that  come  into  mind
    then  are  querycache memsize, minimum # of appearence before
    caching, maximum lifetime or # usage of a plan and the  like.
    So  setting  the  memsize to zero will completely disable and
    fallback to current behavior.

    After that, the entire parsing is still done for every  query
    (so  application  level  controlled  query  cacheing is still
    another thing to care for). We would only be able to skip the
    planner/optimizer step. The question therefore is how much of
    the entire processing time  for  a  query  can  be  saved  if
    replacing  this  step by some shared memory overhead. I'm not
    sure if this is worth the entire efford at all,  and  we  can
    only  judge after the querytree overhaul is done. Then again,
    improving the query optimizer directly, so he's able to  make
    better join order decisions faster, might be the way to go.


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#========================================= wieck@debis.com (Jan Wieck) #



Mon, 3 Apr 2000 19:07:07 +0200 (CEST)
wieck@debis.com (Jan Wieck)
Re: caching query results


On Mon, 3 Apr 2000, Jan Wieck wrote:

>     This  should wait until after the proposed querytree overhaul
>     we have in mind. I already discussed it with  Tom  Lane.  The
>     idea goes like this:

 This is very interesting discussion for me, I have prepared code for 
7.1? with PREPARE/EXECUTE commands and SPI changes for query cache. This
features allow users define cache entry (via SPI or PREPARE). But it is 
already discussed before now. A validity of plans is a problem.

>     After  the  overhaul,  the rewriter is a very simple and fast
>     step. So we could hook into  the  rewriter,  who  builds  for
>     EVERY  query  kinda  key  based  on  the nodes, relations and
>     functions that appear in the querytree.

It is good idea. What exactly is a key? If I good understand this key
is for query identification only. Right?

>     These keys could be managed in a shared LRU table, and if the

My current code is based on HASH table with keys and query&plan is 
saved in special for a plan created MemoryContext (it is good for
a example SPI_freeplan()).  

>     same  key  appears  a  number  of  times  (0-n),  it's entire
>     querytree + plan (after planning)  will  be  saved  into  the
>     shared  mem.  

Here I not understend. Why is here any time checking? 

>     At  a subsequent occurence, the querycache will
>     look  closer  onto  the  two  trees,  if  they   are   really
>     identically  WRT  all the nodes. If only constant values have
>     changed, the already known plan could be reused.

IMHO users can use PREPARE / EXECUTE for same query. Suggested idea is 
really good if this query cache will in shared memory and more backends 
can use it.

Good. It is solution for 'known-query' and allow it skip any steps in the
query path. But we still not have any idea for cached plans validity. What
if user changes oid for any operator, drop column (etc)?  

Or I anything overlook?

>     We would only be able to skip the
>     planner/optimizer step. 

Instead a PREPARE/EXECUTE which allow skip all in the query path (only
executor is called. But it works for user defined query not for every
query.

>     The question therefore is how much of
>     the entire processing time  for  a  query  can  be  saved  if
>     replacing  this  step by some shared memory overhead. I'm not
>     sure if this is worth the entire efford at all,  and  we  can
>     only  judge after the querytree overhaul is done. Then again,
>     improving the query optimizer directly, so he's able to  make
>     better join order decisions faster, might be the way to go.

Is really sure that this will faster? (it must create key for nodes, 
search same query in any table (cache), copy new query&plan to cache 
..etc.)

							Karel




Tue, 4 Apr 2000 13:55:39 +0200 (CEST)
Karel Zak <zakkr@zf.jcu.cz>
Re: caching query results
Karel Zak wrote:

> On Mon, 3 Apr 2000, Jan Wieck wrote:
>
> It is good idea. What exactly is a key? If I good understand this key
> is for query identification only. Right?

    Right.  Imagine  a querytree (after overhaul) that looks like
    this:

                       +------+
                       | SORT |
                       +------+
                          ^
                          |
           +-----------------------------+
           | JOIN                        |
           | atts: rel1.att1, rel2.att2  |
           | qual: rel1.att2 = rel2.att1 |
           +-----------------------------+
                ^                     ^
                |                     |
      +------------------+  +------------------+
      | SCAN             |  | SCAN             |
      | rel:  rel1       |  | rel:  rel2       |
      | atts: att1, att2 |  | atts: att1, att2 |
      +------------------+  +------------------+

    which is a node structure describing a query of:

    SELECT rel1.att1, rel2.att2 FROM rel1, rel2
        WHERE rel1.att2 = rel2.att1;

    The "key" identifying this querytree now could look like

    SORT(JOIN(1.1,2.2;SCAN(78991;1,2),SCAN(78995;1,2);))

    78991 and 78995 are the OIDs of rel1 and rel2. So the key  is
    a  very  simplified  description  of what the query does, and
    maybe the qualification should  be  included  too.  But  it's
    enough to find a few candidates to look at closer on the node
    level out of hundreds of cached plans.

> >     These keys could be managed in a shared LRU table, and if the
>
> My current code is based on HASH table with keys and query&plan is
> saved in special for a plan created MemoryContext (it is good for
> a example SPI_freeplan()).

    IIRC our hash table code insists on using global, per backend
    memory.   I thought about managing the entire querycache with
    a new type of memory context, using  different  routines  for
    palloc()/pfree(),  working  in  a shared memory area only and
    eventually freeing  longest  unused  plans  until  allocation
    fits.  Let's  see  if using hash tables here would be easy or
    not.

> >     same  key  appears  a  number  of  times  (0-n),  it's entire
> >     querytree + plan (after planning)  will  be  saved  into  the
> >     shared  mem.
>
> Here I not understend. Why is here any time checking?

    There's not that big of a win if you do all the shared memory
    overhead  for  any  query  at  it's  first  occurance. Such a
    generic query cache only makes sense for queries  that  occur
    often.  So  at  it's first to n-th occurance we only count by
    key and after we know that it's one  of  these  again'n'again
    thingies, we pay the cache overhead.

    Also  I  think,  keeping  the number of exclusive cache locks
    (for writing) as small as possible would be a good  idea  WRT
    concurrency.

> IMHO users can use PREPARE / EXECUTE for same query. Suggested idea is
> really good if this query cache will in shared memory and more backends
> can use it.

    Exactly  that's  the idea. And since the postmaster will hold
    the shared memory as it does  for  the  block  and  syscache,
    it'll survive even times of no DB activity.

> Good. It is solution for 'known-query' and allow it skip any steps in the
> query path. But we still not have any idea for cached plans validity. What
> if user changes oid for any operator, drop column (etc)?

    That's  why  the  key  is only good to find "candidates". The
    cacheing has to look very close to the nodes in the tree  and
    maybe  compare  down  to pg_attribute oid's etc. to decide if
    it's really the same query or not.

> Is really sure that this will faster? (it must create key for nodes,
> search same query in any table (cache), copy new query&plan to cache
> ..etc.)

    Only some timing code put into backends in various real world
    databases  can tell how much of the entire processing time is
    spent in the optimizer.

    And I'd not be surprised if most of the time is already spent
    during   the  parse  step,  which  we  cannot  skip  by  this
    technique.


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#========================================= wieck@debis.com (Jan Wieck) #



Tue, 4 Apr 2000 16:27:37 +0200 (CEST)
wieck@debis.com (Jan Wieck)
Re: caching query results

On Tue, 4 Apr 2000, Jan Wieck wrote:

>     Right.  Imagine  a querytree (after overhaul) that looks like
>     this:
> 
>                        +------+
>                        | SORT |
>                        +------+
>                           ^
>                           |
>            +-----------------------------+
>            | JOIN                        |
>            | atts: rel1.att1, rel2.att2  |
>            | qual: rel1.att2 = rel2.att1 |
>            +-----------------------------+
>                 ^                     ^
>                 |                     |
>       +------------------+  +------------------+
>       | SCAN             |  | SCAN             |
>       | rel:  rel1       |  | rel:  rel2       |
>       | atts: att1, att2 |  | atts: att1, att2 |
>       +------------------+  +------------------+
> 
>     which is a node structure describing a query of:
> 
>     SELECT rel1.att1, rel2.att2 FROM rel1, rel2
>         WHERE rel1.att2 = rel2.att1;
> 
>     The "key" identifying this querytree now could look like
> 
>     SORT(JOIN(1.1,2.2;SCAN(78991;1,2),SCAN(78995;1,2);))

 The nice picture. Thanks, I undestend you now. A question is where create 
this key - create a specific function that look at to querytree and return 
key or calculate it during statement transformation (analyze.c ..etc.). 
Or is any other idea?

> > >     These keys could be managed in a shared LRU table, and if the
> >
> > My current code is based on HASH table with keys and query&plan is
> > saved in special for a plan created MemoryContext (it is good for
> > a example SPI_freeplan()).

I thought about it, and what for SPI and PREPARE/EXECUTE query cache 
use shared memory too? I'm vote for one query cache in postgresql. IMHO
is not good create a specific cache for SPI_saveplan()+PREPARE and second
for your suggested query cache.

If plans saved via SPI (under defined key - 'by_key' interface) will shared
under all backends a lot of features will faster (FK, PLangs ..etc) and
shared plans cached via PREPARE will persistent across more connetions.
(Some web developers will happy :-) 

But I not sure with this...
 
>     IIRC our hash table code insists on using global, per backend
>     memory.   I thought about managing the entire querycache with
>     a new type of memory context, using  different  routines  for
>     palloc()/pfree(),  working  in  a shared memory area only and
>     eventually freeing  longest  unused  plans  until  allocation
>     fits.  Let's  see  if using hash tables here would be easy or
>     not.

I look at the current shmem routines - create specific space and hash 
table for a query cache is not a problem, hash routines are prepared 
for usage under shmem. The current lock management code is very simular.   
With hash is not a problem here. 

A problem is how store (copy) query & plan tree to this (shared) memory.
The current copyObject() is based on palloc()/pfree() and as you said
we haven't memory management routines (like palloc()) that working in 
shmem. 

Would be nice have MemoryContext routines for shmem - example 
CreateGlobalMemory_in_shmem() and palloc() that knows work with this
specific context. It is a dream?

A solution is convert query & plan tree to string (like pg_rewrite (views))
and save to cache this string, (and what a speed during (vice versa) parsing?). 
IMHO for this solution we not need a hash table, we can use a standard system 
table and a syscache.   

But more nice is variant with non-string and full plan-tree-structs in a 
shmem.

> > Good. It is solution for 'known-query' and allow it skip any steps in the
> > query path. But we still not have any idea for cached plans validity. What
> > if user changes oid for any operator, drop column (etc)?
> 
>     That's  why  the  key  is only good to find "candidates". The
>     cacheing has to look very close to the nodes in the tree  and
>     maybe  compare  down  to pg_attribute oid's etc. to decide if
>     it's really the same query or not.

OK.

						Karel


Wed, 5 Apr 2000 13:33:56 +0200 (CEST)
Karel Zak <zakkr@zf.jcu.cz>
Re: caching query results