Digital Symposium Collection 2000

Query Optimization in the Presence of Limited Access Patterns Daniela Florescu, Alon Y. Levy, Ioana Manolescu, and Dan Suciu   View Paper (PDF)   Return to Adaptive Query Optimization Abstract 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. References Note: References link to DBLP on the Web. [1] Surajit Chaudhuri , Umeshwar Dayal , Tak W. Yan : Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995 : 410-422 [2] Surajit Chaudhuri , Kyuseok Shim : Query Optimization in the Presence of Foreign Functions. VLDB 1993 : 529-542 [3] Surajit Chaudhuri , Kyuseok Shim : Optimization of Queries with User-defined Predicates. VLDB 1996 : 87-98 [4] Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997) [5] Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang : Optimizing Queries Across Diverse Data Sources. VLDB 1997 : 276-285 [6] Joseph M. Hellerstein , Jeffrey F. Naughton : Query Execution Techniques for Caching Expensive Methods. SIGMOD Conf. 1996 : 423-434 [7] Joseph M. Hellerstein , Michael Stonebraker : Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993 : 267-276 [8] Kiyoshi Ono , Guy M. Lohman : Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990 : 314-325 [9] Alon Y. Levy , Anand Rajaraman , Joann J. Ordille : Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996 : 251-262 [10] Katherine A. Morris : An Algorithm for Ordering Subgoals in NAIL! PODS 1988 : 82-88 [11] Michael Steinbrunn , Guido Moerkotte , Alfons Kemper : Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB Journal 6(3) : 191-208(1997) [12] Arjan Pellenkoft , César A. Galindo-Legaria , Martin L. Kersten : The Complexity of Transformation-Based Join Enumeration. VLDB 1997 : 306-315 [13] Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112 [14] Raghu Ramakrishnan , Jeffrey D. Ullman : A survey of deductive database systems. JLP 23(2) : 125-149(1995) [15] Berthold Reinwald , Hamid Pirahesh : SQL Open Heterogeneous Data Access. SIGMOD Conference 1998 : 506-507 [16] Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan : Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conf. 1996 : 435-446 [17] Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996) [18] Vasilis Vassalos , Yannis Papakonstantinou : Describing and Using Query Capabilities of Heterogeneous Sources. VLDB 1997 : 256-265 [19] Wolfgang Scheufele , Guido Moerkotte : Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections. EDBT 1998 : 201-215 [20] Ramana Yerneni , Chen Li , Hector Garcia-Molina , Jeffrey D. Ullman : Computing Capabilities of Mediators. SIGMOD Conference 1999 : 443-454 [21] Ramana Yerneni , Chen Li , Jeffrey D. Ullman , Hector Garcia-Molina : Optimizing Large Join Queries in Mediation Systems. ICDT 1999 : 348-364 BIBTEX @inproceedings{DBLP:conf/sigmod/FlorescuLMS99,   author    = {Daniela Florescu and                 Alon Y. Levy and                 Ioana Manolescu and                 Dan Suciu},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Query Optimization in the Presence of Limited Access Patterns},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {311-322},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM