On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces.

Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504

@inproceedings{DBLP:conf/vldb/LanzelotteVZ93,
  author    = {Rosana S. G. Lanzelotte and
               Patrick Valduriez and
               Mohamed Za\"{\i}t},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {On the Effectiveness of Optimization Search Strategies for Parallel
               Execution Spaces},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {493-504},
  ee        = {db/conf/vldb/LanzelotteVZ93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The cost of query optimization is affected by both the search space and the search strategy of the optimizer. In a parallel execution environment, the search space tends to be much larger than in the centralized case. This is due to the high number of execution alternatives which implies a significant increase in the optimization cost. In this paper, we investigate the trade-off between optimization cost and parallel execution cost using the DBS3 parallel query optimizer. We describe its cost model which captures all essential aspects of parallel executions. We show how the cost metrics imply a significant increase in the search space and optimization cost. However, instead of restricting the search space, which may lead to loosing better plans, we reduce the optimization cost bycontrolling the search strategy. We extend randomized strategies to adapt well to parallel query optimization. In particular, we propose Toured Simulation Annealing which provides a better trade-off between optimization cost and quality of the parallel execution plan.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents

References

[BCV91]: Björn Bergsten, Michel Couprie, Patrick Valduriez: Prototyping DBS3, a Shared-Memory Parallel Database System. PDIS 1991: 226-234
[EDS90]: ...
[GHK92]: Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18
[GV92]: Georges Gardarin, Patrick Valduriez: ESQL2: An Object-Oriented SQL with F-Logic Semantics. ICDE 1992: 320-327
[HS91]: Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. PDIS 1991: 218-225
[IC91]: Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177
[JKK90]: ...
[KBZ86]: Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137
[LV91]: Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
[LVZ92]: Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies. SIGMOD Conference 1992: 256-265
[MS79]: ...
[SD90]: Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480
[Se79]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[SW89]: Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376
[TL91]: Kian-Lee Tan, Hongjun Lu: A Note on the Strategy Space of Multiway Join Query Optimization Problem in Parallel Systems. SIGMOD Record 20(4): 81-82(1991)
[VG84]: Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
[Za90]: ...
[ZZB93]: Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing in DBS3. PDIS 1993: 93-102