Partially preemptible hash joins

ABSTRACT

With the advent of real-time and goal-oriented database systems, priority scheduling 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.

REFERENCES

• Bitt88: Dina Bitton , Jim Gray, Disk Shadowing, Proceedings of the 14th International Conference on Very Large Data Bases, p.331-338, August 29-September 01, 1988
• Blas77: M. Blasgen, K. Eswaran, "Storage and Access in Relational Databases", IBM Systems Journal, 16(4), 1977.
• DeWi84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• DeWi90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• Ferg93: Donald F. Ferguson , L. Georgiadis , Christos Nikolaou , K. Davies, Goal Oriented, Adaptive Transaction Routing for High Performance Transaction Processing Systems, Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, p.138-147, January 20-23, 1993
• Kits83: M. K.itsuregawa, H. Tanaka, T. Moto-oka, "Application of Hash to Data Base Machine and its Architecture", New Generation Computing, 1(1), 1983.
• Kits89: M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
• Livn87: Miron Livny , Setrag Khoshafian , Haran Boral, Multi-disk management algorithms, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.69-77, May 11-14, 1987, Banff, Alberta, Canada
• Livn90: M. Livny, "DeNet User's Guide", CS Dept., UW-Madison, 1990.
• Naka88: Masaya Nakayama , Masaru Kitsuregawa , Mikio Takagi, Hash-Partitioned Join Method Using Dynamic Destaging Strategy, Proceedings of the 14th International Conference on Very Large Data Bases, p.468-478, August 29-September 01, 1988
• Pang93: H, P#ngj M. C#r#y# M. Livny, "PartiMly Pr#mptibl# Ha#h Joins", CS Technical Report, UW-Madison, 1993.
• REAL92: Real-Time Systems, 4(3), Special Issue on Real-Time Databases, 1992.
• Ries78: D. Ries, R, Epstein, "Evaluation of Distributio4a Criteria for Distributed Database Systems", UCB/ERL Technical Report M78/22, UC Berkeley, 1978.
• Shap86: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• Ston81: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• Teng84: J. Teng, R. Gumaer, "Managing IBM Database 2 Buffers to Maximize Performance", IBM Systems Journal, 23(2), 1984.
• Zell90: Hansjorrg Zeller , Jim Gray, An adaptive hash join algorithm for multiuser environments, Proceedings of the sixteenth international conference on Very large databases, p.186-197, September 1990, Brisbane, Australia

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Performance