Sort-Merge-Join: An Idea Whose Time Has(h) Passed?

@inproceedings{DBLP:conf/icde/Graefe94,
  author    = {Goetz Graefe},
  title     = {Sort-Merge-Join: An Idea Whose Time Has(h) Passed?},
  booktitle = {Proceedings of the Tenth International Conference on Data Engineering,
               February 14-18, 1994, Houston, Texas, USA},
  publisher = {IEEE Computer Society},
  year      = {1994},
  isbn      = {0-8186-5400-7},
  pages     = {406-417},
  ee        = {db/conf/icde/Graefe94.html},
  crossref  = {DBLP:conf/icde/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

ACM SIGMOD 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/An2-6 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/aDVD1 or /dvd

Printed Edition

References

[1]

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

[2]

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

[3]

Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, Honesty C. Young: Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins. VLDB 1992: 15-26 BibTeX

[4]

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

[5]

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

[6]

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

[7]

David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider: A Performance Analysis of the Gamma Database Machine. SIGMOD Conference 1988: 350-360 BibTeX

[8]

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

[9]

Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka: An Overview of The System Software of A Parallel Relational Database Machine GRACE. VLDB 1986: 209-219 BibTeX

[10]

...

[11]

Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX

[12]

...

[13]

Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) BibTeX

[14]

Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994) BibTeX

[15]

Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277 BibTeX

[16]

Philip J. Janus, Edmund A. Lamagna: An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting. IEEE Trans. Computers 34(4): 367-372(1985) BibTeX

[17]

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

[18]

Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi: The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method. VLDB 1989: 257-266 BibTeX

[19]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[20]

Sai Choi Kwan, Jean-Loup Baer: The I/O Performance of Multiway Mergesort and Tag Sort. IEEE Trans. Computers 34(4): 383-387(1985) BibTeX

[21]

C. M. McCulloch: Why Merge? - An Examination of Disk Sorting Strategy. IEEE Trans. Computers 34(4): 387-391(1985) BibTeX

[22]

Betty Salzberg: File Structures: An Analytic Approach. Prentice-Hall 1988, ISBN 0-13-314550-6
BibTeX

[23]

Betty Salzberg: Merging Sorted Runs Using Large Main Memory. Acta Inf. 27(3): 195-215(1989) BibTeX

[24]

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 BibTeX

[25]

Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480 BibTeX

[26]

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

[27]

Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX

[28]

...

Referenced by

1. Alfons Kemper, Donald Kossmann, Christian Wiesner: Generalised Hash Teams for Join and Group-by. VLDB 1999: 30-41
2. Fa-Chung Fred Chen, Margaret H. Dunham: Common Subexpression Processing in Multiple-Query Processing. IEEE Trans. Knowl. Data Eng. 10(3): 493-499(1998)
3. Sven Helmer, Till Westmann, Guido Moerkotte: Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships. VLDB 1998: 98-109
4. Goetz Graefe, Ross Bunker, Shaun Cooper: Hash Joins and Hash Teams in Microsoft SQL Server. VLDB 1998: 86-97
5. Per-Åke Larson, Goetz Graefe: Memory Management During Run Generation in External Sorting. SIGMOD Conference 1998: 472-483
6. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
7. Peter A. Buhr, Anil K. Goel, Naomi Nishimura, Prabhakar Ragde: Parallel Pointer-Based Join Algorithms in Memory-mapped Environments. ICDE 1996: 266-275
8. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
9. Diane L. Davison, Goetz Graefe: Memory-Contention Responsive Hash Joins. VLDB 1994: 379-390
10. Gennady Antoshenkov: Query Processing in DEC Rdb: Major Issues and Future Challenges. IEEE Data Eng. Bull. 16(4): 42-52(1993)
11. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)