Optimization of Multi-Way Join Queries for Parallel Execution.
Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan:
Optimization of Multi-Way Join Queries for Parallel Execution.
VLDB 1991: 549-560@inproceedings{DBLP:conf/vldb/LuST91,
author = {Hongjun Lu and
Ming-Chien Shan and
Kian-Lee Tan},
editor = {Guy M. Lohman and
Am\'{\i}lcar Sernadas and
Rafael Camps},
title = {Optimization of Multi-Way Join Queries for Parallel Execution},
booktitle = {17th International Conference on Very Large Data Bases, September
3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
publisher = {Morgan Kaufmann},
year = {1991},
isbn = {1-55860-150-3},
pages = {549-560},
ee = {db/conf/vldb/LuST91.html},
crossref = {DBLP:conf/vldb/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Most of the existing relational database query optimizers generate multi-way join plans only from those linear ones to reduce the optimization overhead.
For multiprocessor computer systems, this strategy seems inadequate since it may reduce the search space too much to generate near-optimal plans.
In this paper we present a framework for optimization of multi- way join queries in multiprocessor computer systems.
The optimization process not only determines the order and method in which eachjoin should be performed, but also determines the number of joins should be executed in parallel, and the number of processors should be allocated to each join.
The preliminary performance study shows that the optimizer usually generate optimal or near-optimal plans when the number of joins is relatively small.
Even when the number of joins increases, the algorithm still gives reasonably good performance.
Furthermore, the optimization overhead is much lesser compared to exhaustive search.
Copyright © 1991 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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Guy M. Lohman, Amílcar Sernadas, Rafael Camps (Eds.):
17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings.
Morgan Kaufmann 1991, ISBN 1-55860-150-3
References
- [Bora90]
- Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez:
Prototyping Bubba, A Highly Parallel Database System.
IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)
- [Bult89]
- Günter von Bültzingsloewen, Cirano Iochpe, Rolf-Peter Liedtke, Ralf Kramer, Michael Schryro, Klaus R. Dittrich, Peter C. Lockemann:
Design and Implementation of KARDAMOM - A Set-oriented Data Flow Database Machine.
IWDM 1989: 18-33
- [Deen90]
- S. Misbah Deen, D. N. P. Kannangara, Malcolm C. Taylor:
Multi-Join on Parallel Processors.
DPDS 1990: 92-102
- [DeWi85]
- David J. DeWitt, Robert H. Gerber:
Multiprocessor Hash-Based Join Algorithms.
VLDB 1985: 151-164
- [DeWi90]
- David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen:
The Gamma Database Machine Project.
IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990)
- [Ioan90]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321
- [Kits90]
- Masaru Kitsuregawa, Yasushi Ogawa:
Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC).
VLDB 1990: 210-221
- [Kris86]
- Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo:
Optimization of Nonrecursive Queries.
VLDB 1986: 128-137
- [Lohm85]
- Guy M. Lohman, C. Mohan, Laura M. Haas, Dean Daniels, Bruce G. Lindsay, Patricia G. Selinger, Paul F. Wilms:
Query Processing in R*.
Query Processing in Database Systems 1985: 31-47
- [Lu90]
- Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan:
Hash-Based Join Algorithms for Multiprocessor Computers.
VLDB 1990: 198-209
- [Ono90]
- Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325
- [Schn89]
- Donovan A. Schneider, David J. DeWitt:
A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment.
SIGMOD Conference 1989: 110-121
- [Schn90]
- Donovan A. Schneider, David J. DeWitt:
Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.
VLDB 1990: 469-480
- [Seli79]
- 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
- [Ston88]
- Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout:
The Design of XPRS.
VLDB 1988: 318-330
- [Su88]
- ...
- [Swam88]
- Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17
- [Swam89]
- Arun N. Swami:
Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques.
SIGMOD Conference 1989: 367-376
- [Sysl83]
- ...
- [Tera83]
- ...
- [Vald84]
- Patrick Valduriez, Georges Gardarin:
Join and Semijoin Algorithms for a Multiprocessor Database Machine.
ACM Trans. Database Syst. 9(1): 133-161(1984)
- [Wolf90]
- Joel L. Wolf, Daniel M. Dias, Philip S. Yu:
An Effective Algorithm for Parallelizing Sort Merge in the Presence of Data Skew.
DPDS 1990: 103-115
Copyright © Tue Mar 16 02:22:02 2010
by Michael Ley (ley@uni-trier.de)
