A model for multiple-query processing based upon strong factoring

This paper proposes a model for interleaving the execution of multiple queries simultaneously. The queries are rewritten, in the context of each other, in order to induce common subexpressions (CSEs). A CSE will then need to be evaluated once only and its result is used in the evaluation of the queries that contain it, thereby leading to cost saving over the conventional query-at-a-time scenario. Two important aspects characterize the proposed model. First, it rewrites the queries in such a way that the isolated CSEs are, themselves, heuristically efficient to evaluate during query execution. Second, it reduces the optimization overhead (due to query rewriting) by using a divide-and-conquer approach to deduce relationships among inter-query selection conditions on base relations while using only pattern matching to find relationships among higher-order subexpressions (those involving an arbitrary number of joins).