TY - GEN
T1 - Query Optimization in the Presence of Limited Access Patterns
AU - Florescu, Daniela
AU - Levy, Alon
AU - Manolescu, Ioana
AU - Suciu, Dan
N1 - Publisher Copyright:
© 1999 ACM.
PY - 1999/6/1
Y1 - 1999/6/1
N2 - We consider the problem of query optimization in the presence of limitations on access patterns to the data (i.e., when one must provide values for one of the attributes of a relation in order to obtain tuples). We show that in the presence of limited access patterns we must search a space of 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 and 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, and it also uses a best-first search strategy in order to produce a first complete plan early in the search. We describe experiments to illustrate the performance of our algorithm.
AB - We consider the problem of query optimization in the presence of limitations on access patterns to the data (i.e., when one must provide values for one of the attributes of a relation in order to obtain tuples). We show that in the presence of limited access patterns we must search a space of 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 and 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, and it also uses a best-first search strategy in order to produce a first complete plan early in the search. We describe experiments to illustrate the performance of our algorithm.
U2 - 10.1145/304182.304210
DO - 10.1145/304182.304210
M3 - Conference contribution
AN - SCOPUS:85134309148
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 311
EP - 322
BT - SIGMOD/PODS 1999 - Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data and Symposium on Principles of Database Systems
PB - Association for Computing Machinery
T2 - 1999 ACM SIGMOD International Conference on Management of Data and Symposium on Principles of Database Systems, SIGMOD/PODS 1999
Y2 - 31 May 1999 through 3 June 1999
ER -