A Mass Production Technique to Speed Multiple-Query Optimization and Physical Database Design

The logic of many query optimizers corresponds to searching a graph that contains all alternative intermediate results considered by the optimizer. We consider the problem, “Given a query Q, determine the cost of a best strategy that uses intermediate result v to compute Q, assuming that v is available at no cost.” Our main result is an algorithm that mass-produces such cost information for all intermediates v considered by the query optimizer, in time linear in the size of the graph. To illustrate potential applications for the algorithm, we describe rules for identifying and eliminating suboptimal alternatives in multiple query optimization and demonstrate how the algorithm rapidly computes the necessary cost bounds. We also describe applications of the algorithm to speeding physical database design.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.