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 [EMAIL PROTECTED] > 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 [EMAIL PROTECTED] | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square, Pennsylvania 19073 ---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives? http://archives.postgresql.org
