Sort versus Hash Revisited.

@article{DBLP:journals/tkde/GraefeLS94,
  author    = {Goetz Graefe and
               Ann Linville and
               Leonard D. Shapiro},
  title     = {Sort versus Hash Revisited},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {6},
  number    = {6},
  year      = {1994},
  pages     = {934-944},
  ee        = {db/journals/tkde/GraefeLS94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

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-3 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]

Alok Aggarwal, Jeffrey Scott Vitter: The Input/Output Complexity of Sorting and Related Problems. Commun. ACM 31(9): 1116-1127(1988)

[2]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976)

[3]

Micah Beck, Dina Bitton, W. Kevin Wilkinson: Sorting Large Files on a Backend Multiprocessor. IEEE Trans. Computers 37(7): 769-778(1988)

[4]

Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983)

[5]

...

[6]

...

[7]

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

[8]

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

[9]

Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985)

[10]

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

[11]

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

[12]

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

[13]

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

[14]

David J. DeWitt: The Wisconsin Benchmark: Past, Present, and Future. The Benchmark Handbook 1991: 119-165

[15]

David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291

[16]

...

[17]

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)

[18]

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

[19]

Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111

[20]

Goetz Graefe, Diane L. Davison: Encapsulation of Parallelism and Architecture-Independence in Extensible Database Query Execution. IEEE Trans. Software Eng. 19(8): 749-764(1993)

[21]

...

[22]

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

[23]

Goetz Graefe, Shreekant S. Thakkar: Tuning a Parallel Database Algorithm on a Shared-memory Multiprocessor. Softw., Pract. Exper. 22(7): 495-517(1992)

[24]

...

[25]

Balakrishna R. Iyer, Daniel M. Dias: System Issues in Parallel Sorting for Database Systems. ICDE 1990: 246-255

[26]

...

[27]

Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374

[28]

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)

[29]

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

[30]

Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173

[31]

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

[32]

Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980

[33]

Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134

[34]

Jai Menon: A Study of Sort Algorithms for Multiprocessor Database Machines. VLDB 1986: 197-206

[35]

Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478

[36]

John K. Ousterhout: Why Aren't Operating Systems Getting Faster As Fast as Hardware? USENIX Summer 1990: 247-256

[37]

Joel E. Richardson, Michael J. Carey: Programming Constructs for Database System Implementation in EXODUS. SIGMOD Conference 1987: 208-219

[38]

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

[39]

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

[40]

Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan: FastSort: A Distributed Single-Input Single-Output External Sort. SIGMOD Conference 1990: 94-101

[41]

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

[42]

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

[43]

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

[44]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976)

[45]

...

[46]

Stephen Todd: PRTV: An Efficient Implementation for Large Relational Data Bases. VLDB 1975: 554-556

[47]

Hansjörg Zeller, Jim Gray: An Adaptive Hash Join Algorithm for Multiuser Environments. VLDB 1990: 186-197

[48]

George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949