Multiple Query Optimization by Cache-Aware Middleware Using Query Teamwork

The multiple-query optimization (MQO) problem has been well-studiedin the research literature, usually by means of identifying andexploiting the occurence of common subexpressions, and has required implementation in the database engine.Observing that common subexpressions derive from common data,and that the amount of data is usually greatest at the source,we propose an optimization technique that exploits thepresence of sharable access patterns to underlying data, especiallyscans of large portions of tables or indexes, in environments wherequery queueing or batching is an acceptable approach. We show thatsimultaneous queries with such sharable accesses have a tendency toform synchronous groups (teams) which benefit each other throughthe operation of the disk cache, in effect using it as an implicitpipeline. We propose a novel method of optimization, exploitingthis tendency by scheduling the queries to enhance this tendency,and show that this can be accomplished even from outside thedatabase engine with application server middleware. We present analgorithm for scheduling from a queue of similar queries, designedto promote such teamwork. This is implemented as middleware foruse with a commercial database engine. Finally, we present testsusing the query mix from the TPC-R benchmark, achieving a speedupof 2.34 over the default scheduling provided by the database.