Multiple Query Optimization by Cache-Aware Middleware using Query Teamwork

The multiple-query optimization (MQO) problem has been well-studied in the research literature, usually by means of identifying and exploiting 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 the presence of sharable access patterns to underlying data, especially scans of large portions of tables or indexes, in environments where query queueing or batching is an acceptable approach. We show that simultaneous queries with such sharable accesses have a tendency to form synchronous groups (teams) which bene t each other through the operation of the disk cache, in eect using it as an implicit pipeline. We propose a novel method of optimization, exploiting this tendency by scheduling the queries to enhance this tendency, and show that this can be accomplished even from outside the database engine with application server middleware. We present an algorithm for scheduling from a queue of similar queries, designed to promote such teamwork. This is implemented as middleware for use with a commercial database engine. Finally, we present tests using the query mix from the TPC-R benchmark, achieving a speedup of 2.34 over the default scheduling provided by the database