dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Join Algorithm Costs Revisited.

Evan P. Harris, Kotagiri Ramamohanarao: Join Algorithm Costs Revisited. VLDB J. 5(1): 64-84(1996)
@article{DBLP:journals/vldb/HarrisR96,
  author    = {Evan P. Harris and
               Kotagiri Ramamohanarao},
  title     = {Join Algorithm Costs Revisited},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {1},
  year      = {1996},
  pages     = {64-84},
  ee        = {db/journals/vldb/HarrisR96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A method of analysing join algorithms based upon the time required to access, transfer and perform the relevant CPU-based operations on a disk page is proposed. The costs of variations of several of the standard join algorithms, including nested block, sort-merge, GRACE hash and hybrid hash, are presented. For a given total buffer size, the cost of these join algorithms depends on the parts of the buffer allocated for each purpose. For example, when joining two relations using the nested block join algorithm, the amount of buffer space allocated for the outer and inner relations can significantly affect the cost of the join. Analysis of expected and experimental results of various join algorithms show that a combination of the optimal nested block and optimal GRACE hash join algorithms usually provide the greatest cost benefit, unless the relation size is a small multiple of the memory size. Algorithms to quickly determine a buffer allocation producing the minimal cost for each of these algorithms are presented. When the relation size is a small multiple of the amount of main memory available (typically up to three to six times), the hybrid hash join algorithm is preferable.

Key Words

Join algorithms, minimisation, optimal buffer allocation.

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[Aarts and Korst 1989]
...
[Bitton et al. 1983]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Blasgen and Eswaran 1977]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cheng et al. 1991]
Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeWitt and Gerber 1985]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeWitt et al. 1984]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Graefe 1993]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Haas and Swami 1992]
Peter J. Haas, Arun N. Swami: Sequential Sampling Procedures for Query Size Estimation. SIGMOD Conference 1992: 341-350 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hagmann 1986]
Robert B. Hagmann: An Observation on Database Buffering Performance Metrics. VLDB 1986: 289-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Harris and Ramamohanarao 1994]
Evan P. Harris, Kotagiri Ramamohanarao: Using Optimized Multi-Attribute Hash Indexes for Hash Joins. Australasian Database Conference 1994: 92-111 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hua and Lee 1991]
Kien A. Hua, Chiang Lee: Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning. VLDB 1991: 525-535 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kitsuregawa et al. 1983]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kitsuregawa et al. 1989]
Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi: The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method. VLDB 1989: 257-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knuth 1973]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lipton et al. 1990]
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McVoy and Kleiman 1991]
Larry W. McVoy, Steve R. Kleiman: Extent-like Performance from a UNIX File System. USENIX Winter 1991: 33-44 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Merrett 1981]
T. H. Merrett: Why Sort-Merge Gives the Best Implementation of the Natural Join. SIGMOD Record 13(2): 39-51(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mishra and Eich 1992]
Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nakayama et al. 1988]
Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Omiecinski 1991]
Edward Omiecinski: Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor. VLDB 1991: 375-385 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Omiecinski and Lin 1992]
...
[Pang et al. 1993]
HweeHwa Pang, Michael J. Carey, Miron Livny: Partially Preemptive Hash Joins. SIGMOD Conference 1993: 59-68 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Richardson et al. 1987]
James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Schneider and DeWitt 1989]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shapiro 1986]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shatdal and Naughton 1993]
Ambuj Shatdal, Jeffrey F. Naughton: Using Shared Virtual Memory for Parallel Join Processing. SIGMOD Conference 1993: 119-128 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sun et al. 1993]
Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vaghani et al. 1994]
Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey, Tim S. Leask, James Harland: The Aditi Deductive Database System. VLDB J. 3(2): 245-288(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Walton et al. 1991]
Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:10 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page