An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew.

@inproceedings{DBLP:conf/icde/WolfDYT91,
  author    = {Joel L. Wolf and
               Daniel M. Dias and
               Philip S. Yu and
               John Turek},
  title     = {An Effective Algorithm for Parallelizing Hash Joins in the Presence
               of Data Skew},
  booktitle = {Proceedings of the Seventh International Conference on Data Engineering,
               April 8-12, 1991, Kobe, Japan},
  publisher = {IEEE Computer Society},
  year      = {1991},
  isbn      = {0-8186-2138-9},
  pages     = {200-209},
  ee        = {db/conf/icde/WolfDYT91.html},
  crossref  = {DBLP:conf/icde/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 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

[AKKL87]

Selim G. Akl, Nicola Santoro: Optimal Parallel Merging and Sorting Without Memory Conflicts. IEEE Trans. Computers 36(11): 1367-1369(1987) BibTeX

[BIC85]

...

[BLAS77]

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

[BTAT84]

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

[CHRI83]

Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983) BibTeX

[COFF78]

Edward G. Coffman Jr., M. R. Garey, David S. Johnson: An Application of Bin-Packing to Multiprocessor Scheduling. SIAM J. Comput. 7(1): 1-17(1978) BibTeX

[CORN86]

Douglas W. Cornell, Daniel M. Dias, Philip S. Yu: On Multisystem Coupling Through Function Request Shipping. IEEE Trans. Software Eng. 12(10): 1006-1017(1986) BibTeX

[DEMUS85]

...

[DEWI85]

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

[DEWI86]

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

[DEWI87]

David J. DeWitt, Marc G. Smith, Haran Boral: A Single-User Performance Evaluation of the Teradata Database Machine. HPTS 1987: 244-276 BibTeX

[GRAH69]

Ronald L. Graham: Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics 17(2): 416-429(1969) BibTeX

[HSIA83]

...

[HU89]

...

[KIT83]

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

[KNUT73]

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

[LAKS88]

M. Seetha Lakshmi, Philip S. Yu: Effect of Skew on Join Performance in Parallel Architectures. DPDS 1988: 107-120 BibTeX

[LYNC88]

Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251 BibTeX

[MONT83]

Anthony Y. Montgomery, Daryl J. D'Souza, S. B. Lee: The Cost of Relational Algebraic Operations on Skewed Data: Estimates and Experiments. IFIP Congress 1983: 235-241 BibTeX

[NECH84]

Jack Shermer, Philip M. Neches: The Genesis of a Database Computer. IEEE Computer 17(11): 42-56(1984) BibTeX

[OZKA86]

...

[QADA85]

...

[SALZ83]

Silvio Salza, Mario Terranova, Paola Velardi: Performance Modeling of the DBMAC Architecture. IWDM 1983: 74-90 BibTeX

[SCHN89]

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

[STON86]

Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986) BibTeX

[VALD84]

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

[WOLF90a]

Joel L. Wolf, Daniel M. Dias, Philip S. Yu: An Effective Algorithm for Parallelizing Sort Merge in the Presence of Data Skew. DPDS 1990: 103-115 BibTeX

[WOLF90b]

...

[WOLF90c]

...

[YU87]

...

[ZIPF49]

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