Analysis of common subexpression exploitation models in multiple-query processing

In multiple-query processing, a subexpression that appears in more than one query is called a common subexpression (CSE). A CSE needs to he evaluated once only to produce a temporary result that can then be used to evaluate all the queries containing the CSE. Therefore, the cost of evaluating the CSE is amortized over the queries requiring its evaluation. Two queries, posed simultaneously to the optimizer, may however contain subexpression that are not equivalent but are, nevertheless related by implication (the extension of one is a proper subset of the other) or intersection (the intersection of the two extensions is a proper subset of both extensions). In order to exploit the opportunity for cost amortization offered by the two latter relationships. the optimizer must rewrite the two queries in such a way that a CSE is induced. This paper compares, empirically and analytically, the performance of the various query execution models that are implied by different approaches to query rewriting