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

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) #

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