ACM SIGMOD Anthology TKDE dblp.uni-trier.de

Large Join Optimization on a Hypercube Multiprocessor.

Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili: Large Join Optimization on a Hypercube Multiprocessor. IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
@article{DBLP:journals/tkde/LinOY94,
  author    = {Eileen Tien Lin and
               Edward Omiecinski and
               Sudhakar Yalamanchili},
  title     = {Large Join Optimization on a Hypercube Multiprocessor},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {6},
  number    = {2},
  year      = {1994},
  pages     = {304-315},
  ee        = {db/journals/tkde/LinOY94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Optimizing large join queries that consist of many joins has been recognized as NP-hard. Most of the previous work focuses on a uni-processor environment. In a multiprocessor, the location of each join adds another dimension to the complexity of the problem. In this paper, we examine the feasibility of exploiting the inherent parallelism in optimizing large join queries, on a hypercube multiprocessor. This includes not only using the multiprocessor to answer the large join query, but also to optimize it. We propose an algorithm to estimate the cost of a parallel large join plan. Three heuristics are provided for generating an initial solution, which is further optimized by an iterative local-improvement method. The entire process of parallel query optimization and execution is simulated on an Intel iPSC/2 hypercube machine. Our experimental results show that the performance of each heuristic depends on the characteristics of the query.

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) BibTeX
[2]
Peter Bodorik, J. Spruce Riordon: Heuristic Algorithms for Distributed Query Processing. DPDS 1988: 144-155 BibTeX
[3]
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) BibTeX
[4]
S. Misbah Deen, D. N. P. Kannangara, Malcolm C. Taylor: Multi-Join on Parallel Processors. DPDS 1990: 92-102 BibTeX
[5]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX
[6]
Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111 BibTeX
[7]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX
[8]
Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX
[9]
...
[10]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[11]
...
[12]
Raymond A. Lorie, Jean-Jacques Daudenarde, Gary Hallmark, James W. Stamos, Honesty C. Young: Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience. IEEE Data Eng. Bull. 12(1): 2-8(1989) BibTeX
[13]
Edward Omiecinski, Eileen Tien Lin: Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers. IEEE Trans. Knowl. Data Eng. 1(3): 329-343(1989) BibTeX
[14]
Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480 BibTeX
[15]
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 BibTeX
[16]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[17]
Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 BibTeX
[18]
Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[19]
Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX

Referenced by

  1. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
  2. Nadejda Biscondi, André Flory, Lionel Brunie: Parallel Databases: Structured Query Optimization. ADBIS 1996: 146-152
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:28:02 2009