Database Caching

-----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(at)turnstep(dot)com
PGP Key: 0x14964AC8 200202281132

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

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