Memory-Contention Responsive Hash Joins.
Diane L. Davison, Goetz Graefe:
Memory-Contention Responsive Hash Joins.
VLDB 1994: 379-390@inproceedings{DBLP:conf/vldb/DavisonG94,
author = {Diane L. Davison and
Goetz Graefe},
editor = {Jorge B. Bocca and
Matthias Jarke and
Carlo Zaniolo},
title = {Memory-Contention Responsive Hash Joins},
booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
publisher = {Morgan Kaufmann},
year = {1994},
isbn = {1-55860-153-8},
pages = {379-390},
ee = {db/conf/vldb/vldb94-379.html},
crossref = {DBLP:conf/vldb/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In order to maximize system performance in environments with
fluctuating memory contention, memory-intensive algorithms such as hash
join must gracefully adapt to variations in available memory. Mixed
workloads, creating fluctuations of erratic frequency and magnitude,
make responsiveness to memory contention particularly important.
Previous studies on adaptable hash joins have focused on lowering I/O
costs by reducing the I/O volume, as measured in the number of pages,
by spilling partitions from memory to disk and then restoring them into
memory if more memory becomes available. In this paper, we present
memory-contention responsive hash joins that (i) reduce the amount of
time spent on I/O by using large I/O buffers, or clusters, (ii)
dynamically vary the cluster size in response to fluctuations in memory
availability, and (iii) employ earlier techniques of dynamic destaging
and restoration. Our simulation results demonstrate that these combined
techniques provide better performance than previous algorithms,
particularly in environments with medium to high memory contention or
with very frequent changes in memory availability.
Copyright © 1994 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.):
VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile.
Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX
References
- [BiG88]
- Dina Bitton, Jim Gray:
Disk Shadowing.
VLDB 1988: 331-338 BibTeX
- [Bra84]
- Kjell Bratbergsengen:
Hashing Methods and Relational Algebra Operations.
VLDB 1984: 323-333 BibTeX
- [DKO84]
- 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
- [DeG85]
- David J. DeWitt, Robert H. Gerber:
Multiprocessor Hash-Based Join Algorithms.
VLDB 1985: 151-164 BibTeX
- [Gra93a]
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
- [Gr93b]
- ...
- [Gr94]
- Goetz Graefe:
Sort-Merge-Join: An Idea Whose Time Has(h) Passed?
ICDE 1994: 406-417 BibTeX
- [GLS94]
- Goetz Graefe, Ann Linville, Leonard D. Shapiro:
Sort versus Hash Revisited.
IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994) BibTeX
- [KNT89]
- 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
- [NKT88]
- Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi:
Hash-Partitioned Join Method Using Dynamic Destaging Strategy.
VLDB 1988: 468-478 BibTeX
- [PCL93a]
- HweeHwa Pang, Michael J. Carey, Miron Livny:
Partially Preemptive Hash Joins.
SIGMOD Conference 1993: 59-68 BibTeX
- [PCL93b]
- ...
- [Sal90]
- Betty Salzberg:
Merging Sorted Runs Using Large Main Memory.
Acta Inf. 27(3): 195-215(1989) BibTeX
- [Sha86]
- Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
- [SSU91]
- Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman:
Database Systems: Achievements and Opportunities.
Commun. ACM 34(10): 110-120(1991) BibTeX
- [ZeG90]
- Hansjörg Zeller, Jim Gray:
An Adaptive Hash Join Algorithm for Multiuser Environments.
VLDB 1990: 186-197 BibTeX
Referenced by
- Weiye Zhang, Per-Åke Larson:
Dynamic Memory Adjustment for External Mergesort.
VLDB 1997: 376-385
- Ming-Ling Lo, Chinya V. Ravishankar:
Towards Eliminating Random I/O in Hash Joins.
ICDE 1996: 422-429
- HweeHwa Pang, Michael J. Carey, Miron Livny:
Multiclass Query Scheduling in Real-Time Database Systems.
IEEE Trans. Knowl. Data Eng. 7(4): 533-551(1995)
- Erhard Rahm, Robert Marek:
Dynamic Multi-Resource Load Balancing in Parallel Database Systems.
VLDB 1995: 395-406
- Diane L. Davison, Goetz Graefe:
Dynamic Resource Brokering for Multi-User Query Execution.
SIGMOD Conference 1995: 281-292
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:01 2009