Partially Preemptive Hash Joins.

HweeHwa Pang, Michael J. Carey, Miron Livny: Partially Preemptive Hash Joins. SIGMOD Conference 1993: 59-68

@inproceedings{DBLP:conf/sigmod/PangCL93,
  author    = {HweeHwa Pang and
               Michael J. Carey and
               Miron Livny},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Partially Preemptive Hash Joins},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {59-68},
  ee        = {http://doi.acm.org/10.1145/170035.170051, db/conf/sigmod/PangCL93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

With the advent of real-time and goal-oriented database systems, priority schedulirtg is likely to be an important feature in future database management systems. A consequence of priority scheduling is that a transaction may lose its buffers to higher-priority transactions, and may be given additional memory when transactions leave the system. Due to their heavy reliance on main memory, hash joins are especially vulnerable to fluctuations in memory availability. Previous studies have proposed modifications to the hash join algorithm to cope with these fluctuations, but the proposed algorithms have not been extensively evaluated or compared with each other. This paper contains a performance study of these algorithms. In addition, we introduce a family of memory-adaptive hash join algorithms that turns out to offer even better solutions to the memory fluctuation problem that hash joins experience.

Copyright © 1993 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

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/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993

, SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1390 KB]

References

[Bitt88]: Dina Bitton, Jim Gray: Disk Shadowing. VLDB 1988: 331-338
[Blas77]: Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977)
[DeWi84]: 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
[DeWi90]: 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)
[Ferg93]: Donald F. Ferguson, Leonidas Georgiadis, Christos Nikolaou, K. Davies: Goal Oriented, Adaptive Transaction Routing for High Performance Transaction Processing Systems. PDIS 1993: 138-147
[Kits83]: 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)
[Kits89]: Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi: The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method. VLDB 1989: 257-266
[Livn87]: Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. SIGMETRICS 1987: 69-77
[Livn90]: ...
[Naka88]: Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478
[Pang93]: ...
[REAL92]: ...
[Ries78]: ...
[Shap86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[Ston81]: Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981)
[Teng84]: James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984)
[Zell90]: Hansjörg Zeller, Jim Gray: An Adaptive Hash Join Algorithm for Multiuser Environments. VLDB 1990: 186-197