Query Optimization in the Presence of Limited Access Patterns

Daniela Florescu*       Alon Levy       Ioana Manolescu
INRIA       Univ of Washington       INRIA
Daniela.Florescu@inria.fr       alon@cs.washington.edu       Ioana.Manolescu@inria.fr

Dan Suciu
AT&T Labs
suciu@research.att.com

Abstract

We consider the problem of query optimization in the presence of limitations on access patterns to the data (e.g., in order to obtain tuples of a relation, one must provide values for one of the attributes). We show that in the presence of limited access patterns we must search a space of {\em annotated query plans}, where the annotations describe the inputs that must be given to the plan. We describe a theoretical and experimental analysis of the resulting search space. Based on the conclusions of this analysis, we describe a novel query optimization algorithm that is designed to perform well under the different conditions that may arise. The algorithm searches the set of annotated query plans, pruning invalid and non-viable plans as early as possible in the search space. The algorithm also uses a best-first search strategy in order to produce a first complete plan early in the search. We describe experiments that show that the algorithm indeeds performs well in practice, and studies the different tradeoffs in designing the algorithm.