
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


I had to make a relatively long drive yesterday, so I had lots of free time 
to do some thinking...and my thoughts were turning to caching and databases. 
The following is what I came up with: forgive me if it seems to be just an 
obvious ramble...

Why does a database need caching?

Normally, when one thinks of a database (or to be precise, a RDBMS) the 
ACID acronym comes up. This is concerned with having a stable database that 
can reliably be used by many users at the same time. Caching a query is 
unintuitive because it involves sharing information from transactions that 
may be separated by a great amount of time and/or by different users. 
However, from the standpoint of the database server, caching increases 
efficiency enormously. If 800 users all make the same query, then caching 
can help the database server backend (hereafter simply "database") to 
save part or all of the work it performs so it doesn't have to repeat the 
entire sequence of steps 800 times.

What is caching?

Caching basically means that we want to save frequently-used information 
into an easy to get to area. Usually, this means storing it into memory. 
Caching has three main goals: reducing disk access, reducing computation 
(i.e. CPU utilization), and speeding up the time as measured by how long a 
it takes a user to seea  result.  It does all this at the expense of RAM, 
and the tradeoff is almost always worth it.

In a database, there are three basic types of caching: query results, 
query plans, and relations.

The first, query result caching, simply means that we store into memory 
the exact output of a SELECT query for the next time that somebody performs 
that exact same SELECT query. Thus, if 800 people do a "SELECT * FROM foo", 
the database runs it for the first person, saves the results, and simply 
reads the cache for the next 799 requests. This saves the database from doing 
any disk access, practically removes CPU usage, and speeds up the query.

The second, query plan caching, involves saving the results of the optimizer, 
which is responsible for figuring out exactly "how" the databse is going to 
fetch the requested data. This type of caching usually involves a "prepared" 
query, which has almost all of the information needed to run the query with 
the exception of one or more "placeholders" (spots that are populated with 
variables at a later time). The query could also involve non-prepared 
statments as well. Thus, if someone prepares the query "SELECT flavor FROM 
foo WHERE size=?", and then executes it by sending in 300 different values 
for "size", the prepared statement is run through the optimizer, the r
esulting path is stored into the query plan cache, and the stored path is 
used for the 300 execute requests. Because the path is already known, the 
optimizer does not need to be called, which saves the database CPU and time.

The third, relation caching, simply involves putting the entire relation 
(usually a table or index) into memory so that it can be read quickly. 
This saves disk access, which basically means that it saves time. (This type 
of caching also can occur at the OS level, which caches files, but that will 
not be discussed here).

Those are the three basic types of caching, ways of implementing each are 
discussed below. Each one should complement the other, and a query may be 
able to use one, two, or all three of the caches.

I. Query result caching:

A query result cache is only used for SELECT queries that involve a 
relation (i.e. not for "SELECT version") Each cache entry has the following 
fields: the query itself, the actual results, a status, an access time, an 
access number, and a list of all included columns. (The column list actually 
tells as much information as needed to uniquely identify it, i.e. schema, 
database, table, and column). The status is merely an indicator of whether or 
not this cached query is valid. It may not be, because it may be invalidated 
for a user within a transaction but still be of use to others. 

When a select query is processed, it is first parsed apart into a basic common 
form, stripping whitespace, standardizing case, etc., in order to facilitate 
an accurate match. Note that no other pre-processing is really required, 
since we are only interested in exact matches that produce the exact same 
output. An advanced version of this would ideally be able to use the cached 
output of "SELECT bar,baz FROM foo" when it receives the query "SELECT 
baz,bar FROM foo", but that will require some advanced parsing. Possible, 
but probably not something to attempt in the first iteration of a query 
caching function. :) If there *is* a match (via a simple strcmp at first), 
and the status is marked as "valid", then the database simply uses the 
stored output, updates the access time and count, and exits. This should be 
extremely fast, as no disk access is needed, and almost no CPU. The 
complexity of the query will not matter either: a simple query will run just 
as fast as something with 12 sorts and 28 joins.

If a query is *not* already in the cache, then after the results are found 
and delivered to the user, the database will try and store them for the 
next appearance of that query. First, the size of the cache will be compared 
to the size of the query+output, to see if there is room for it. If there 
is, the query will be saved, with a status of valid, a time of 'now', a count 
of 1, a list of all affected columns found by parsing the query, and the total 
size of the query+output. If there is no room, then it will try to delete one 
or more to make room. Deleting can be done based on the oldest access time, 
smallest access count, or size of the query+output. Some balance of the first 
two would probably work best, with the access time being the most important. 
Everything will be configurable, of course.

Whenever a table is changed, the cache must be checked as well. A list of 
all columns that were actually changed is computed and compared against 
the list of columns for each query. At the first sign of a match, the 
query is marked as "invalid." This should happen before the changes are made 
to the table itself. We do not delete the query immediately since this may 
be inside of a transaction, and subject to rollback. However, we do need 
to mark it as invalid for the current user inside the current transaction: 
thus, the status flag. When the transaction is commited, all queries that have 
an "invalid" flag are deleted, then the tables are changed. Since the only 
time a query can be flagged as "invalid" is inside your own transaction, 
the deletion can be done very quickly.


II. Query plan caching

If a query is not cached, then it "falls through" to the next level of 
caching, the query plan. This can either be automatic or strictly on a 
user-requested format (i.e. through the prepare-execute paradigm). The latter 
is probably better, but it also would not hurt much to store non-explicitly 
prepared queries in this cache as long as there is room. This cache has a 
field for the query itself, the plan to be followed (i.e. scan this table, 
that index, sort the results, then group them), the columns used, the access 
time, the access count, and the total size. It may also want a simple flag 
of "prepared or non-prepared", where prepared indicates an explicitly 
prepared statment that has placeholders for future values. A good optimizer 
will actually change the plan based on the values plugged in to the prepared 
queries, so that information should become a part of the query itself as 
needed, and multiple queries may exist to handle different inputs. In 
general, most of the inputs will be similar enough to use the same path (e.g. 
"SELECT flavor FROM foo WHERE size=?" will most usually result in a simple 
numeric value for the executes). If a match *is* found, then the database 
can use the stored path, and not have to bother calling up the optimizer 
to figure it out. It then updates the access time, the access count, and 
continues as normal. If a match was *not* found, then it might possibly 
want to be cached. Certainly, explicit prepares should always be cached. 
Non-explicitly prepared queries (those without placeholders) can also be 
cached. In theory, some of this will also be in the result cache, so that 
should be checked as well: it it is there, no reason to put it here. Prepared 
queries should always have priority over non-prepared, and the rest of the 
rules above for the result query should also apply, with a caveat that things 
that would affect the output of the optimizer (e.g. vacuuming) should also 
be taken into account when deleting entries.


III. Relation caching

The final cache is the relation itself, and simply involves putting the entire 
relation into memory. This cache has a field for the name of the relation, 
the table info itself, the type (indexes should ideally be cached more than 
tables, for example), the access time, and the acccess number. Loading could 
be done automatically, but most likely should be done according to a flag 
on the table itself or as an explicit command by the user.


Notes:

The "strcmp" used may seem rather crude, as it misses all but the exact 
same query, but it does cover most of the everyday cases. Queries are 
usually called through an application that keeps it in the same format, 
time after time, so the queries are very often exactly identical. A better 
parser would help, of course, but it would get rather complicated quickly.
Two quick examples: a web page that is read from a database is a query that 
is called many times with exactly the same syntax; a user doing a "refresh" 
to constantly check if something has changed since they last looked.

Sometimes a query may jump back to a previous type of cache, especially 
for things like subselects. The entire subselect query may not match, 
but the inner query should also be checked against the query result cache.

Each cache should have some configurable parameters, including the size in 
RAM, the maximum number of entries, and rules for adding and deleting.
They should also be directly viewable through a system table, so a DBA 
can quickly see exactly which queries are being cached and how often 
they are being used. There should be a command to quickly flush the cache, 
remove "old" entries, and to populate the query plan cache via a prepare 
statment. It should also be possible to do table changes without stopping 
to check the cache: perhaps flushing the cache and setting a global 
"cache is empty" flag would suffice.

Another problem is the prepare and execute: you are not always guaranteed 
to get a cached prepare if you do an execute, as it may have expired or 
there may simply be no more room. Those prepared statements inside a 
transaction should probably be flagged as "non-deletable" until the 
transaction is ended.

Storing the results of an execute in the query result cache is another 
problem. When a prepare is made, the database returns a link to that 
exact prepared statement in cache, so that all the client has to say is 
"run the query at 0x4AB3 with the value "12". Ideally, the database 
should be able to check these against the query result cache as well. It 
can do this by reconstructing the resulting query (by plugging the value into 
the prepared statement) or it can store the execute request as a type of 
query itself; instead of "SELECT baz FROM bar WHERE size=12" it would 
store "p0x4aB3:12".


The result cache would probaby be the easiest to implement, and also gives 
the most "bang for the buck." The path cache may be a bit harder, but is 
a very necessary feature. I don't know about the relation caching: it looks 
to be fairly easy, and I don't trust that, so I am guessing it is actually 
quite difficult.

Greg Sabino Mullane  greg@turnstep.com
PGP Key: 0x14964AC8 200202281132

-----BEGIN PGP SIGNATURE-----
Comment: http://www.turnstep.com/pgp.html

iD8DBQE8fqybvJuQZxSWSsgRAps9AKDwCkIH7GKSBjflyYSA0F7mQqD1MwCeJLCw
hqE1SxJ2Z7RxFGCu3UwIBrI=
=jlBy
-----END PGP SIGNATURE-----



Thu, 28 Feb 2002 22:23:46 -0000
"Greg Sabino Mullane" <greg@turnstep.com>
Database Caching
"Greg Sabino Mullane" <greg@turnstep.com> writes:
> III. Relation caching

> The final cache is the relation itself, and simply involves putting the entire 
> relation into memory. This cache has a field for the name of the relation, 
> the table info itself, the type (indexes should ideally be cached more than 
> tables, for example), the access time, and the acccess number. Loading could 
> be done automatically, but most likely should be done according to a flag 
> on the table itself or as an explicit command by the user.

This would be a complete waste of time; the buffer cache (both Postgres'
own, and the kernel's disk cache) serves the purpose already.

As I've commented before, I have deep misgivings about the idea of a
query-result cache, too.

			regards, tom lane

Thu, 28 Feb 2002 18:27:26 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Database Caching 
On Thu, Feb 28, 2002 at 10:23:46PM -0000, Greg Sabino Mullane wrote:

> The first, query result caching, simply means that we store into memory 
> the exact output of a SELECT query for the next time that somebody performs 
> that exact same SELECT query. Thus, if 800 people do a "SELECT * FROM foo", 
> the database runs it for the first person, saves the results, and simply 
> reads the cache for the next 799 requests. This saves the database from doing 
> any disk access, practically removes CPU usage, and speeds up the query.

 How expensive is keep cache in consistent state? May be maintain
 the result cache is simular to read raw data from disk/buffer cache.

 The result cache may be speeds up SELECT, but probably speeds down
 UPDATE/INSERT.

> The second, query plan caching, involves saving the results of the optimizer, 
> which is responsible for figuring out exactly "how" the databse is going to 
> fetch the requested data. This type of caching usually involves a "prepared" 
> query, which has almost all of the information needed to run the query with 
> the exception of one or more "placeholders" (spots that are populated with 
> variables at a later time). The query could also involve non-prepared 
> statments as well. Thus, if someone prepares the query "SELECT flavor FROM 
> foo WHERE size=?", and then executes it by sending in 300 different values 
> for "size", the prepared statement is run through the optimizer, the r
> esulting path is stored into the query plan cache, and the stored path is 
> used for the 300 execute requests. Because the path is already known, the 
> optimizer does not need to be called, which saves the database CPU and time.

 IMHO query plan cache maintained by user's PREPARE/EXECUTE/DEALLOCATE 
 statements is sufficient, because user good know what change in DB
 scheme (drop function, relation...).

 The "transparent" query cache for each query that go into backend
 (IMHO) will too expensive, because you must check/analyze each query. 
 I mean more effective is keep in memory fragments of query, for example
 operator, relation description -- the cache like this PostgreSQL already
 have (syscache).

> The third, relation caching, simply involves putting the entire relation 
> (usually a table or index) into memory so that it can be read quickly. 

 Already done by buffers :-)

        Karel

-- 
 Karel Zak  <zakkr@zf.jcu.cz>
 http://home.zf.jcu.cz/~zakkr/
 
 C, PostgreSQL, PHP, WWW, http://docs.linux.cz, http://mape.jcu.cz

Fri, 1 Mar 2002 11:02:05 +0100
Karel Zak <zakkr@zf.jcu.cz>
Re: Database Caching
Tom Lane wrote:
> 
> "Greg Sabino Mullane" <greg@turnstep.com> writes:
> > III. Relation caching
> 
> > The final cache is the relation itself, and simply involves putting the entire
> > relation into memory. This cache has a field for the name of the relation,
> > the table info itself, the type (indexes should ideally be cached more than
> > tables, for example), the access time, and the acccess number. Loading could
> > be done automatically, but most likely should be done according to a flag
> > on the table itself or as an explicit command by the user.
> 
> This would be a complete waste of time; the buffer cache (both Postgres'
> own, and the kernel's disk cache) serves the purpose already.
> 
> As I've commented before, I have deep misgivings about the idea of a
> query-result cache, too.

I appreciate your position, and I can see your point, however, where caching is
a huge win is when you have a database which is largely static, something like
the back end of a web server.

The content is updated regularly, but not constantly. There is a window, say 4
hours, where the entire database is static, and all it is doing is running the
same 100 queries, over and over again.

My previous company, www.dmn.com, has a music database system. We logged all
the backed info, most of the queries were duplicated many times. This can be
explained by multiple users interested in the same thing or the same user
hitting "next page"

If you could cache the "next page" or similar hit results, you could really
increase throughput and capaciy of a website.

Fri, 01 Mar 2002 07:49:24 -0500
mlw <markw@mohawksoft.com>
Re: Database Caching
Tom Lane wrote:
> "Greg Sabino Mullane" <greg@turnstep.com> writes:
> > III. Relation caching
>
> > The final cache is the relation itself, and simply involves putting the entire
> > relation into memory. This cache has a field for the name of the relation,
> > the table info itself, the type (indexes should ideally be cached more than
> > tables, for example), the access time, and the acccess number. Loading could
> > be done automatically, but most likely should be done according to a flag
> > on the table itself or as an explicit command by the user.
>
> This would be a complete waste of time; the buffer cache (both Postgres'
> own, and the kernel's disk cache) serves the purpose already.
>
> As I've commented before, I have deep misgivings about the idea of a
> query-result cache, too.

    I  wonder how this sort of query result caching could work in
    our MVCC and visibility world  at  all.  Multiple  concurrent
    running  transactions  see  different snapshots of the table,
    hence different result sets for  exactly  one  and  the  same
    querystring  at the same time ... er ...  yeah, one cache set
    per query/snapshot combo, great!

    To really gain some speed with this sort of query cache, we'd
    have to adopt the #1 MySQL design rule "speed over precision"
    and ignore MVCC for query-cached relations, or what?


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#================================================== JanWieck@Yahoo.com #



_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com


Fri, 1 Mar 2002 09:22:29 -0500 (EST)
Jan Wieck <janwieck@yahoo.com>
Re: Database Caching
On Fri, 1 Mar 2002, Jan Wieck wrote:

> Tom Lane wrote:
> > "Greg Sabino Mullane" <greg@turnstep.com> writes:
> > > III. Relation caching
> >
> > > The final cache is the relation itself, and simply involves putting the entire
> > > relation into memory. This cache has a field for the name of the relation,
> > > the table info itself, the type (indexes should ideally be cached more than
> > > tables, for example), the access time, and the acccess number. Loading could
> > > be done automatically, but most likely should be done according to a flag
> > > on the table itself or as an explicit command by the user.
> >
> > This would be a complete waste of time; the buffer cache (both Postgres'
> > own, and the kernel's disk cache) serves the purpose already.
> >
> > As I've commented before, I have deep misgivings about the idea of a
> > query-result cache, too.
>
>     I  wonder how this sort of query result caching could work in
>     our MVCC and visibility world  at  all.  Multiple  concurrent
>     running  transactions  see  different snapshots of the table,
>     hence different result sets for  exactly  one  and  the  same
>     querystring  at the same time ... er ...  yeah, one cache set
>     per query/snapshot combo, great!
>
>     To really gain some speed with this sort of query cache, we'd
>     have to adopt the #1 MySQL design rule "speed over precision"
>     and ignore MVCC for query-cached relations, or what?

Actually, you are missing, I think, as is everyone, the 'semi-static'
database ... you know?  the one where data gets dumped to it by a script
every 5 minutes, but between dumps, there are hundreds of queries per
second/minute between the updates that are the same query repeated each
time ...

As soon as there is *any* change to the data set, the query cache should
be marked dirty and reloaded ... mark it dirty on any update, delete or
insert ...

So, if I have 1000 *pure* SELECTs, the cache is fine ... as soon as one
U/I/D pops up, its invalidated ...




Fri, 1 Mar 2002 11:07:28 -0400 (AST)
"Marc G. Fournier" <scrappy@hub.org>
Re: Database Caching
mlw <markw@mohawksoft.com> writes:
> My previous company, www.dmn.com, has a music database system. We logged all
> the backed info, most of the queries were duplicated many times. This can be
> explained by multiple users interested in the same thing or the same user
> hitting "next page"

> If you could cache the "next page" or similar hit results, you could really
> increase throughput and capaciy of a website.

Sure, but the most appropriate place to do that sort of thing is in the
application (in this case, probably a cgi/php-ish layer).  Only the
application can know what its requirements are.  In the case you
describe, it'd be perfectly okay for a "stale" cache result to be
delivered that's a few minutes out of date.  Maybe a few hours out of
date would be good enough too, or maybe not.  But if we do this at the
database level then we have to make sure it won't break *any*
applications, and that means the most conservative validity assumptions.
(Thus all the angst about how to invalidate cache entries on-the-fly.)

Likewise, the application has a much better handle than the database on
the issue of which query results are likely to be worth caching.

I think that reports of "we sped up this application X times by caching
query results on the client side" are interesting, but they are not good
guides to what would happen if we tried to put a query-result cache into
the database.

			regards, tom lane

Fri, 01 Mar 2002 10:15:28 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Database Caching 
Marc G. Fournier wrote:
> On Fri, 1 Mar 2002, Jan Wieck wrote:
>
> > Tom Lane wrote:
> > > "Greg Sabino Mullane" <greg@turnstep.com> writes:
> > > > III. Relation caching
> > >
> > > > The final cache is the relation itself, and simply involves putting the entire
> > > > relation into memory. This cache has a field for the name of the relation,
> > > > the table info itself, the type (indexes should ideally be cached more than
> > > > tables, for example), the access time, and the acccess number. Loading could
> > > > be done automatically, but most likely should be done according to a flag
> > > > on the table itself or as an explicit command by the user.
> > >
> > > This would be a complete waste of time; the buffer cache (both Postgres'
> > > own, and the kernel's disk cache) serves the purpose already.
> > >
> > > As I've commented before, I have deep misgivings about the idea of a
> > > query-result cache, too.
> >
> >     I  wonder how this sort of query result caching could work in
> >     our MVCC and visibility world  at  all.  Multiple  concurrent
> >     running  transactions  see  different snapshots of the table,
> >     hence different result sets for  exactly  one  and  the  same
> >     querystring  at the same time ... er ...  yeah, one cache set
> >     per query/snapshot combo, great!
> >
> >     To really gain some speed with this sort of query cache, we'd
> >     have to adopt the #1 MySQL design rule "speed over precision"
> >     and ignore MVCC for query-cached relations, or what?
>
> Actually, you are missing, I think, as is everyone, the 'semi-static'
> database ... you know?  the one where data gets dumped to it by a script
> every 5 minutes, but between dumps, there are hundreds of queries per
> second/minute between the updates that are the same query repeated each
> time ...
>
> As soon as there is *any* change to the data set, the query cache should
> be marked dirty and reloaded ... mark it dirty on any update, delete or
> insert ...
>
> So, if I have 1000 *pure* SELECTs, the cache is fine ... as soon as one
> U/I/D pops up, its invalidated ...

    But  in that case, why not caching the entire HTML result for
    the URL or search request? That'd save some wasted cycles  in
    Tomcat as well.


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#================================================== JanWieck@Yahoo.com #



_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com


Fri, 1 Mar 2002 10:17:57 -0500 (EST)
Jan Wieck <janwieck@yahoo.com>
Re: Database Caching
Tom Lane wrote:
> 
> mlw <markw@mohawksoft.com> writes:
> > My previous company, www.dmn.com, has a music database system. We logged all
> > the backed info, most of the queries were duplicated many times. This can be
> > explained by multiple users interested in the same thing or the same user
> > hitting "next page"
> 
> > If you could cache the "next page" or similar hit results, you could really
> > increase throughput and capaciy of a website.
> 
> Sure, but the most appropriate place to do that sort of thing is in the
> application (in this case, probably a cgi/php-ish layer).  Only the
> application can know what its requirements are.  In the case you
> describe, it'd be perfectly okay for a "stale" cache result to be
> delivered that's a few minutes out of date.  Maybe a few hours out of
> date would be good enough too, or maybe not.  But if we do this at the
> database level then we have to make sure it won't break *any*
> applications, and that means the most conservative validity assumptions.
> (Thus all the angst about how to invalidate cache entries on-the-fly.)
> 
> Likewise, the application has a much better handle than the database on
> the issue of which query results are likely to be worth caching.
> 
> I think that reports of "we sped up this application X times by caching
> query results on the client side" are interesting, but they are not good
> guides to what would happen if we tried to put a query-result cache into
> the database.

I would like to respectfully differ with you here. If query results are cached
in an ACID safe way, then many things could be improved.

The problem with applications caching is that they do not have intimate
knowledge of the database, and thus do not know when their cache is invalid. On
top of that, many web sites have multiple web servers connected to a single
database. The caching must sit between the web software and the DB. The logical
place for caching is in the database.

If we went even further, and cached multiple levels of query, i.e. the result
of the sub-select within the whole query, then things like views and more
complex queries would could get an increase in performance.

Take this query:

select * from (select * from T1 where field = 'fubar') as Z right outer join
    (select alt from T2,  (select * from T1 where field = 'fubar') as X where
T2.key = X.key) as Y 
	on T3.key = Y.key) on (Z.key = Y.alt) where Z.key = NULL;


Forgive this query, it is probably completely wrong, the actual query it is
intended to represent is quite a bit larger. The intention is to select a set
of alternate values based on a set of initial values, but also eliminating any
alternate values which may also be in the initial set. Anyway, we have to query
"Select * from T1 where field = 'fubar'" twice.

If that subselect could be cached, it could speed up the query a bit. Right now
I use a temp table, which is a hassle.

Caching results can and do speed up duplicate queries, there can really be no
argument about it. The argument is about the usefulness of the feature and the
cost of implementing it. If maintaining the cache costs more than the benefit
of having it, obviously it is a loser. If implementing it takes up the
biological CPU cycles of he development team that would be spent doing more
important things, then it is also a loser. If however, it is relatively "easy"
(hehe) to do, and doesn't affect performance greatly, is there any harm in
doing so?

Fri, 01 Mar 2002 10:46:48 -0500
mlw <markw@mohawksoft.com>
Re: Database Caching
> >     I  wonder how this sort of query result caching could work in
> >     our MVCC and visibility world  at  all.  Multiple  concurrent
> >     running  transactions  see  different snapshots of the table,
> >     hence different result sets for  exactly  one  and  the  same
> >     querystring  at the same time ... er ...  yeah, one cache set
> >     per query/snapshot combo, great!
> >
> >     To really gain some speed with this sort of query cache, we'd
> >     have to adopt the #1 MySQL design rule "speed over precision"
> >     and ignore MVCC for query-cached relations, or what?
>
> Actually, you are missing, I think, as is everyone, the 'semi-static'
> database ... you know?  the one where data gets dumped to it by a script
> every 5 minutes, but between dumps, there are hundreds of queries per
> second/minute between the updates that are the same query repeated each
> time ...
>
> As soon as there is *any* change to the data set, the query cache should
> be marked dirty and reloaded ... mark it dirty on any update, delete or
> insert ...
>
> So, if I have 1000 *pure* SELECTs, the cache is fine ... as soon as one
> U/I/D pops up, its invalidated ...

The question is, when it's invalidated, how does it become valid again?
I don't see that there's a way to do it only by query string that doesn't
result in meaning that the cache cannot cache a query again until any
transactions that can see the prior state are finished since otherwise
you'd be providing the incorrect results to that transaction. But I
haven't spent much time thinking about it either.


Fri, 1 Mar 2002 08:47:12 -0800 (PST)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: Database Caching
Hi guys,

Stephan Szabo wrote:
<snip> 
> The question is, when it's invalidated, how does it become valid again?
> I don't see that there's a way to do it only by query string that doesn't
> result in meaning that the cache cannot cache a query again until any
> transactions that can see the prior state are finished since otherwise
> you'd be providing the incorrect results to that transaction. But I
> haven't spent much time thinking about it either.

It seems like a good idea to me, but only if it's optional.  It could
get in the way for systems that don't need it, but would be really
beneficial for some types of systems which are read-only or mostly-read
only (with consistent queries) in nature.

i.e.  Lets take a web page where clients can look up which of 10,000
records are either .biz, .org, .info, or .com.

So, we have a database query of simply:

SELECT name FROM sometable WHERE tld = 'biz';

And lets say 2,000 records come back, which are cached.

Then the next query comes in, which is :

SELECT name FROM sometable WHERE tld = 'info';

And lets say 3,000 records come back, which are also cached.

Now, both of these queries are FULLY cached.  So, if either query
happens again, it's a straight memory read and dump, no disk activity
involved, etc (very fast in comparison).

Now, lets say a transaction which involves a change of "sometable"
COMMITs.  This should invalidate these results in the cache, as the
viewpoint of the transaction could now be incorrect (there might now be
less or more or different results for .info or .biz).  The next queries
will be cached too, and will keep upon being cached until the next
transaction involving a change to "sometable" COMMITs.

In this type of database access, this looks like a win.

But caching results in this matter could be a memory killer for those
applications which aren't so predictable in their queries, or are not so
read-only.  That's why I feel it should be optional, but I also feel it
should be added due to what looks like massive wins without data
integrity nor reliability issues.

Hope this helps.

:-)

Regards and best wishes,

Justin Clift

 
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly

-- 
"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
   - Indira Gandhi

Sat, 02 Mar 2002 04:47:50 +1100
Justin Clift <justin@postgresql.org>
Re: Database Caching
On Sat, 2 Mar 2002, Justin Clift wrote:

> Hi guys,
>
> Stephan Szabo wrote:
> <snip>
> > The question is, when it's invalidated, how does it become valid again?
> > I don't see that there's a way to do it only by query string that doesn't
> > result in meaning that the cache cannot cache a query again until any
> > transactions that can see the prior state are finished since otherwise
> > you'd be providing the incorrect results to that transaction. But I
> > haven't spent much time thinking about it either.
>
> i.e.  Lets take a web page where clients can look up which of 10,000
> records are either .biz, .org, .info, or .com.
>
> So, we have a database query of simply:
>
> SELECT name FROM sometable WHERE tld = 'biz';
>
> And lets say 2,000 records come back, which are cached.
>
> Then the next query comes in, which is :
>
> SELECT name FROM sometable WHERE tld = 'info';
>
> And lets say 3,000 records come back, which are also cached.
>
> Now, both of these queries are FULLY cached.  So, if either query
> happens again, it's a straight memory read and dump, no disk activity
> involved, etc (very fast in comparison).
>
> Now, lets say a transaction which involves a change of "sometable"
> COMMITs.  This should invalidate these results in the cache, as the
> viewpoint of the transaction could now be incorrect (there might now be
> less or more or different results for .info or .biz).  The next queries
> will be cached too, and will keep upon being cached until the next
> transaction involving a change to "sometable" COMMITs.

But, if there's a transaction that started before the change committed,
then you may have two separate sets of possible results for the same query
string so query string doesn't seem unique enough to describe a set of
results.  Maybe I haven't read carefully enough, but most of the proposals
seem to gloss over this point.



Fri, 1 Mar 2002 10:19:56 -0800 (PST)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: Database Caching
I'm sneaking out of my cave here.. ;)

mlw wrote:
> Tom Lane wrote:
> 
>>mlw <markw@mohawksoft.com> writes:
>>
>>>My previous company, www.dmn.com, has a music database system. We logged all
>>>the backed info, most of the queries were duplicated many times. This can be
>>>explained by multiple users interested in the same thing or the same user
>>>hitting "next page"
>>>
>>>If you could cache the "next page" or similar hit results, you could really
>>>increase throughput and capaciy of a website.

Well, I'm going to assume that the records in question have been 
completely cached in cases like this.  So isn't the primary source of 
improvement the query parse and plan generation?  As Tom seems to think, 
wouldn't it make more sense to optimize the parse/plan generation rather 
than caching the result set?  After all, if the plan can be pinned how 
much of a performance boost do you expect to get from processing a 
cached plan versus returning a cached result set?

Seriously, I am curious as to what the expected return is?  Still a 
multiple or simply some minor percent?


>>>
>>Sure, but the most appropriate place to do that sort of thing is in the
>>application (in this case, probably a cgi/php-ish layer).  Only the
>>application can know what its requirements are.  In the case you
>>describe, it'd be perfectly okay for a "stale" cache result to be
>>delivered that's a few minutes out of date.  Maybe a few hours out of
>>date would be good enough too, or maybe not.  But if we do this at the
>>database level then we have to make sure it won't break *any*
>>applications, and that means the most conservative validity assumptions.
>>(Thus all the angst about how to invalidate cache entries on-the-fly.)
>>
>>Likewise, the application has a much better handle than the database on
>>the issue of which query results are likely to be worth caching.
>>
>>I think that reports of "we sped up this application X times by caching
>>query results on the client side" are interesting, but they are not good
>>guides to what would happen if we tried to put a query-result cache into
>>the database.
>>
> 
> I would like to respectfully differ with you here. If query results are cached
> in an ACID safe way, then many things could be improved.
> 
> The problem with applications caching is that they do not have intimate
> knowledge of the database, and thus do not know when their cache is invalid. On
> top of that, many web sites have multiple web servers connected to a single
> database. The caching must sit between the web software and the DB. The logical
> place for caching is in the database.
> 


But hybrid application cache designs can mostly if not completely 
address this and also gets some added benefits in many cases.  If you 
have a "cache" table which denotes the tables which are involved in the 
cached results that you desire, you can then update it's state via 
triggers or even exposed procedures accordingly to reflect if the client 
side cache has been invalidated or not.  This means that a client need 
only query the cache table first to determine if it's cache is clean or 
dirty.  When it's dirty, it mearly needs to query the result set again.

Let's also not forget that client side caching can also yield 
significant networking performance improvements over a result set that 
is able to be cached on the server.  Why?  Well, let's say a query has a 
result set of 10,000 rows which are being cached on the server.  A 
remote client queries and fetches 10,0000 results over the network.  Now 
then, even though the result set is cached by the database, it is still 
being transfered over the wire for each and every query.  Now then, 
let's assume that 10 other people perform this same query.  That's 
100,000 rows which get transfered across the wire.  With the client side 
caching scheme, you have 10,010 rows (initial 10,000 result set lpus a 
single row result set which indicates the status of the cache) returned 
across the wire which tell the client that it's cache is clean or dirty.

Let's face it, in order for the cache to make sense, the same result set 
needs to be used over and over again.  In these cases, it would seem 
like in real world situations, a strong client side hybrid caching 
scheme wins in most cases.

I'd also like to toss out that I'd expect somewhere there would be a 
trade off between data cache and result set cache.  On systems without 
infinite memory, where's the line of deliniation?  It seems somewhere 
you may be limiting the size of the generalized cache at the expense of 
the cached result sets.  If this happens, the cases where a cached 
result set may be improved but refreshing that result set my be hindered 
as well might all other queries on the system.


> If we went even further, and cached multiple levels of query, i.e. the result
> of the sub-select within the whole query, then things like views and more
> complex queries would could get an increase in performance.
> 
> Take this query:
> 
> select * from (select * from T1 where field = 'fubar') as Z right outer join
>     (select alt from T2,  (select * from T1 where field = 'fubar') as X where
> T2.key = X.key) as Y 
> 	on T3.key = Y.key) on (Z.key = Y.alt) where Z.key = NULL;
> 
> 
> Forgive this query, it is probably completely wrong, the actual query it is
> intended to represent is quite a bit larger. The intention is to select a set
> of alternate values based on a set of initial values, but also eliminating any
> alternate values which may also be in the initial set. Anyway, we have to query
> "Select * from T1 where field = 'fubar'" twice.
> 
> If that subselect could be cached, it could speed up the query a bit. Right now
> I use a temp table, which is a hassle.
> 

It's funny you say that because I was thinking that should server side 
result set caching truely be desired, wouldn't the use of triggers, a 
procedure for client interface and a temporary table be a poor-man's 
implementation yeilding almost the same results?  Though, I must say I'm 
assuming that the queries will *be* the same and *not nearly* the same. 
  But in the web world, isn't this really the situation we're trying to 
address?  That is, give me the front page?


> Caching results can and do speed up duplicate queries, there can really be no
> argument about it. The argument is about the usefulness of the feature and the
> cost of implementing it. If maintaining the cache costs more than the benefit
> of having it, obviously it is a loser. If implementing it takes up the
> biological CPU cycles of he development team that would be spent doing more
> important things, then it is also a loser. If however, it is relatively "easy"
> (hehe) to do, and doesn't affect performance greatly, is there any harm in
> doing so?
> 


Are any of the ideas that I put forth a viable substitute?

Greg


Fri, 01 Mar 2002 17:06:20 -0600
Greg Copeland <greg@CopelandConsulting.Net>
Re: Database Caching

Do we want to add "query caching" to the TODO list, perhaps with a
question mark?

---------------------------------------------------------------------------

Greg Sabino Mullane wrote:
[ There is text before PGP section. ]
> 
[ PGP not available, raw data follows ]
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> I had to make a relatively long drive yesterday, so I had lots of free time 
> to do some thinking...and my thoughts were turning to caching and databases. 
> The following is what I came up with: forgive me if it seems to be just an 
> obvious ramble...
> 
> Why does a database need caching?
> 
> Normally, when one thinks of a database (or to be precise, a RDBMS) the 
> ACID acronym comes up. This is concerned with having a stable database that 
> can reliably be used by many users at the same time. Caching a query is 
> unintuitive because it involves sharing information from transactions that 
> may be separated by a great amount of time and/or by different users. 
> However, from the standpoint of the database server, caching increases 
> efficiency enormously. If 800 users all make the same query, then caching 
> can help the database server backend (hereafter simply "database") to 
> save part or all of the work it performs so it doesn't have to repeat the 
> entire sequence of steps 800 times.
> 
> What is caching?
> 
> Caching basically means that we want to save frequently-used information 
> into an easy to get to area. Usually, this means storing it into memory. 
> Caching has three main goals: reducing disk access, reducing computation 
> (i.e. CPU utilization), and speeding up the time as measured by how long a 
> it takes a user to seea  result.  It does all this at the expense of RAM, 
> and the tradeoff is almost always worth it.
> 
> In a database, there are three basic types of caching: query results, 
> query plans, and relations.
> 
> The first, query result caching, simply means that we store into memory 
> the exact output of a SELECT query for the next time that somebody performs 
> that exact same SELECT query. Thus, if 800 people do a "SELECT * FROM foo", 
> the database runs it for the first person, saves the results, and simply 
> reads the cache for the next 799 requests. This saves the database from doing 
> any disk access, practically removes CPU usage, and speeds up the query.
> 
> The second, query plan caching, involves saving the results of the optimizer, 
> which is responsible for figuring out exactly "how" the databse is going to 
> fetch the requested data. This type of caching usually involves a "prepared" 
> query, which has almost all of the information needed to run the query with 
> the exception of one or more "placeholders" (spots that are populated with 
> variables at a later time). The query could also involve non-prepared 
> statments as well. Thus, if someone prepares the query "SELECT flavor FROM 
> foo WHERE size=?", and then executes it by sending in 300 different values 
> for "size", the prepared statement is run through the optimizer, the r
> esulting path is stored into the query plan cache, and the stored path is 
> used for the 300 execute requests. Because the path is already known, the 
> optimizer does not need to be called, which saves the database CPU and time.
> 
> The third, relation caching, simply involves putting the entire relation 
> (usually a table or index) into memory so that it can be read quickly. 
> This saves disk access, which basically means that it saves time. (This type 
> of caching also can occur at the OS level, which caches files, but that will 
> not be discussed here).
> 
> Those are the three basic types of caching, ways of implementing each are 
> discussed below. Each one should complement the other, and a query may be 
> able to use one, two, or all three of the caches.
> 
> I. Query result caching:
> 
> A query result cache is only used for SELECT queries that involve a 
> relation (i.e. not for "SELECT version") Each cache entry has the following 
> fields: the query itself, the actual results, a status, an access time, an 
> access number, and a list of all included columns. (The column list actually 
> tells as much information as needed to uniquely identify it, i.e. schema, 
> database, table, and column). The status is merely an indicator of whether or 
> not this cached query is valid. It may not be, because it may be invalidated 
> for a user within a transaction but still be of use to others. 
> 
> When a select query is processed, it is first parsed apart into a basic common 
> form, stripping whitespace, standardizing case, etc., in order to facilitate 
> an accurate match. Note that no other pre-processing is really required, 
> since we are only interested in exact matches that produce the exact same 
> output. An advanced version of this would ideally be able to use the cached 
> output of "SELECT bar,baz FROM foo" when it receives the query "SELECT 
> baz,bar FROM foo", but that will require some advanced parsing. Possible, 
> but probably not something to attempt in the first iteration of a query 
> caching function. :) If there *is* a match (via a simple strcmp at first), 
> and the status is marked as "valid", then the database simply uses the 
> stored output, updates the access time and count, and exits. This should be 
> extremely fast, as no disk access is needed, and almost no CPU. The 
> complexity of the query will not matter either: a simple query will run just 
> as fast as something with 12 sorts and 28 joins.
> 
> If a query is *not* already in the cache, then after the results are found 
> and delivered to the user, the database will try and store them for the 
> next appearance of that query. First, the size of the cache will be compared 
> to the size of the query+output, to see if there is room for it. If there 
> is, the query will be saved, with a status of valid, a time of 'now', a count 
> of 1, a list of all affected columns found by parsing the query, and the total 
> size of the query+output. If there is no room, then it will try to delete one 
> or more to make room. Deleting can be done based on the oldest access time, 
> smallest access count, or size of the query+output. Some balance of the first 
> two would probably work best, with the access time being the most important. 
> Everything will be configurable, of course.
> 
> Whenever a table is changed, the cache must be checked as well. A list of 
> all columns that were actually changed is computed and compared against 
> the list of columns for each query. At the first sign of a match, the 
> query is marked as "invalid." This should happen before the changes are made 
> to the table itself. We do not delete the query immediately since this may 
> be inside of a transaction, and subject to rollback. However, we do need 
> to mark it as invalid for the current user inside the current transaction: 
> thus, the status flag. When the transaction is commited, all queries that have 
> an "invalid" flag are deleted, then the tables are changed. Since the only 
> time a query can be flagged as "invalid" is inside your own transaction, 
> the deletion can be done very quickly.
> 
> 
> II. Query plan caching
> 
> If a query is not cached, then it "falls through" to the next level of 
> caching, the query plan. This can either be automatic or strictly on a 
> user-requested format (i.e. through the prepare-execute paradigm). The latter 
> is probably better, but it also would not hurt much to store non-explicitly 
> prepared queries in this cache as long as there is room. This cache has a 
> field for the query itself, the plan to be followed (i.e. scan this table, 
> that index, sort the results, then group them), the columns used, the access 
> time, the access count, and the total size. It may also want a simple flag 
> of "prepared or non-prepared", where prepared indicates an explicitly 
> prepared statment that has placeholders for future values. A good optimizer 
> will actually change the plan based on the values plugged in to the prepared 
> queries, so that information should become a part of the query itself as 
> needed, and multiple queries may exist to handle different inputs. In 
> general, most of the inputs will be similar enough to use the same path (e.g. 
> "SELECT flavor FROM foo WHERE size=?" will most usually result in a simple 
> numeric value for the executes). If a match *is* found, then the database 
> can use the stored path, and not have to bother calling up the optimizer 
> to figure it out. It then updates the access time, the access count, and 
> continues as normal. If a match was *not* found, then it might possibly 
> want to be cached. Certainly, explicit prepares should always be cached. 
> Non-explicitly prepared queries (those without placeholders) can also be 
> cached. In theory, some of this will also be in the result cache, so that 
> should be checked as well: it it is there, no reason to put it here. Prepared 
> queries should always have priority over non-prepared, and the rest of the 
> rules above for the result query should also apply, with a caveat that things 
> that would affect the output of the optimizer (e.g. vacuuming) should also 
> be taken into account when deleting entries.
> 
> 
> III. Relation caching
> 
> The final cache is the relation itself, and simply involves putting the entire 
> relation into memory. This cache has a field for the name of the relation, 
> the table info itself, the type (indexes should ideally be cached more than 
> tables, for example), the access time, and the acccess number. Loading could 
> be done automatically, but most likely should be done according to a flag 
> on the table itself or as an explicit command by the user.
> 
> 
> Notes:
> 
> The "strcmp" used may seem rather crude, as it misses all but the exact 
> same query, but it does cover most of the everyday cases. Queries are 
> usually called through an application that keeps it in the same format, 
> time after time, so the queries are very often exactly identical. A better 
> parser would help, of course, but it would get rather complicated quickly.
> Two quick examples: a web page that is read from a database is a query that 
> is called many times with exactly the same syntax; a user doing a "refresh" 
> to constantly check if something has changed since they last looked.
> 
> Sometimes a query may jump back to a previous type of cache, especially 
> for things like subselects. The entire subselect query may not match, 
> but the inner query should also be checked against the query result cache.
> 
> Each cache should have some configurable parameters, including the size in 
> RAM, the maximum number of entries, and rules for adding and deleting.
> They should also be directly viewable through a system table, so a DBA 
> can quickly see exactly which queries are being cached and how often 
> they are being used. There should be a command to quickly flush the cache, 
> remove "old" entries, and to populate the query plan cache via a prepare 
> statment. It should also be possible to do table changes without stopping 
> to check the cache: perhaps flushing the cache and setting a global 
> "cache is empty" flag would suffice.
> 
> Another problem is the prepare and execute: you are not always guaranteed 
> to get a cached prepare if you do an execute, as it may have expired or 
> there may simply be no more room. Those prepared statements inside a 
> transaction should probably be flagged as "non-deletable" until the 
> transaction is ended.
> 
> Storing the results of an execute in the query result cache is another 
> problem. When a prepare is made, the database returns a link to that 
> exact prepared statement in cache, so that all the client has to say is 
> "run the query at 0x4AB3 with the value "12". Ideally, the database 
> should be able to check these against the query result cache as well. It 
> can do this by reconstructing the resulting query (by plugging the value into 
> the prepared statement) or it can store the execute request as a type of 
> query itself; instead of "SELECT baz FROM bar WHERE size=12" it would 
> store "p0x4aB3:12".
> 
> 
> The result cache would probaby be the easiest to implement, and also gives 
> the most "bang for the buck." The path cache may be a bit harder, but is 
> a very necessary feature. I don't know about the relation caching: it looks 
> to be fairly easy, and I don't trust that, so I am guessing it is actually 
> quite difficult.
> 
> Greg Sabino Mullane  greg@turnstep.com
> PGP Key: 0x14964AC8 200202281132
> 
> -----BEGIN PGP SIGNATURE-----
> Comment: http://www.turnstep.com/pgp.html
> 
> iD8DBQE8fqybvJuQZxSWSsgRAps9AKDwCkIH7GKSBjflyYSA0F7mQqD1MwCeJLCw
> hqE1SxJ2Z7RxFGCu3UwIBrI=
> =jlBy
> -----END PGP SIGNATURE-----
> 
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
> 
> http://www.postgresql.org/users-lounge/docs/faq.html
> 
[ Decrypting message... End of raw data. ]

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Sun, 25 Aug 2002 20:15:45 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Database Caching
I'm not sure about query result caching or 'relation caching', since the
first would seem to run into problems with concurrent updates, and the
second is sort-of what the buffer cache does.

Query plan caching sounds like a really good idea though. Neil Conway's
PREPARE patch already does this for an individual backend. Do you think
it would be hard to make it use shared memory, and check if a query has
already been prepared by another backend? Maybe it could use something
like a whitespace insensitive checksum for a shared hash key.

Regards,

	John Nield

On Sun, 2002-08-25 at 20:15, Bruce Momjian wrote:
> 
> Do we want to add "query caching" to the TODO list, perhaps with a
> question mark?
> 
> ---------------------------------------------------------------------------
> 
> Greg Sabino Mullane wrote:
[snip]
> 
-- 
J. R. Nield
jrnield@usol.com




25 Aug 2002 21:35:24 -0400
"J. R. Nield" <jrnield@usol.com>
Re: Database Caching
On Sun, 25 Aug 2002, Bruce Momjian wrote:

> Do we want to add "query caching" to the TODO list, perhaps with a
> question mark?

I'd love to have query plans cached, preferably across backends.

cjs
-- 
Curt Sampson  <cjs@cynic.net>   +81 90 7737 2974   http://www.netbsd.org
    Don't you know, in this new Dark Age, we're all light.  --XTC


Mon, 26 Aug 2002 13:17:45 +0900 (JST)
Curt Sampson <cjs@cynic.net>
Re: Database Caching
On Sun, Aug 25, 2002 at 09:35:24PM -0400, J. R. Nield wrote:
> I'm not sure about query result caching or 'relation caching', since the
> first would seem to run into problems with concurrent updates, and the
> second is sort-of what the buffer cache does.
> 
> Query plan caching sounds like a really good idea though. Neil Conway's
> PREPARE patch already does this for an individual backend. Do you think
> it would be hard to make it use shared memory, and check if a query has
> already been prepared by another backend? Maybe it could use something
> like a whitespace insensitive checksum for a shared hash key.

 The original version of query plan cache allows exactly this. But
 after some discussion the shared memory usage in qcache was remove.

 I think better and more robus solution is store cached planns in
 backend memory and allows to run backend as persistent (means not
 startup/stop for each client connection).

    Karel

-- 
 Karel Zak  <zakkr@zf.jcu.cz>
 http://home.zf.jcu.cz/~zakkr/
 
 C, PostgreSQL, PHP, WWW, http://docs.linux.cz, http://mape.jcu.cz

Mon, 26 Aug 2002 10:39:10 +0200
Karel Zak <zakkr@zf.jcu.cz>
Re: Database Caching