Join Processing in Database Systems with Large Main Memories.

@article{DBLP:journals/tods/Shapiro86,
  author    = {Leonard D. Shapiro},
  title     = {Join Processing in Database Systems with Large Main Memories},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {3},
  year      = {1986},
  pages     = {239-264},
  ee        = {http://doi.acm.org/10.1145/6314.6315, db/journals/tods/Shapiro86.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study algorithms for computing the equijoin of two relations in a system with a standard architecture but with large amounts of main memory. Our algorithms are especially efficient when the main memory available is a significant fraction of the size of one of the relations to he joined; but they can be applied whenever there is memory equal to approximately the square root of the size of one relation. We present a new algorithm which is a hybrid of two hash-based algorithms and which dominates the other algorithma we present, including sort-merge. Even in a virtual memory environment, the hybrid algorithm dominates all the others we study.

Finally, we describe how three popular tools to increase the efficiency ofjoins, namely filters, Babb arrays, and semijoins, can he grafted onto any of our algorithms.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 or /cdrom

• 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/aDVD2 or /dvd

References

[1]

Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX

[2]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX

[3]

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

[4]

Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX

[5]

Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX

[6]

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 BibTeX

[7]

David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 BibTeX

[8]

...

[9]

Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX

[10]

Hector Garcia-Molina, Richard J. Lipton, Jacobo Valdes: A Massive Memory Machine. IEEE Trans. Computers 33(5): 391-399(1984) BibTeX

[11]

...

[12]

Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX

[13]

...

[14]

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) BibTeX

[15]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[16]

Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276 BibTeX

[17]

Giovanni Maria Sacco, Mario Schkolnick: A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model. VLDB 1982: 257-262 BibTeX

[18]

Dennis G. Severance, Richardo Duhne: A Practitioner's Guide To Addressing Algorithms. Commun. ACM 19(6): 314-326(1976) BibTeX

[19]

D. L. Slotnick: Logic per Track Devices. Advances in Computers 10: 291-296(1970) BibTeX

[20]

Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) BibTeX

[21]

Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX

[22]

Yasuo Yamane: A Hash Join Technique for Relational Database Systems. FODO 1985: 515-528 BibTeX