Re: Database Caching - Mailing list pgsql-hackers

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,
Pennsylvania19073