ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Hash-Partitioned Join Method Using Dynamic Destaging Strategy.

Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478
@inproceedings{DBLP:conf/vldb/NakayamaK88,
  author    = {Masaya Nakayama and
               Masaru Kitsuregawa and
               Mikio Takagi},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Hash-Partitioned Join Method Using Dynamic Destaging Strategy},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {468-478},
  ee        = {db/conf/vldb/NakayamaK88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we propose a new hash-partitioned join method using a dynamic destaging strategy for large scale databases.

The traditional hash-partitioned join methods such as the Hybrid Hash Join Method assume that the size of each bucket can be controlled by selecting a split function, and the characteristics of the buckets are statically specified. For materializing this assumption, we have to collect information about distributions of the join attribute value before processing a job. In general, however, join operations are applied to relations in which some restrictions are applied, and so it is not easy to collect that information before processing. If we cannot collect the information, the tuple distributions of each bucket may differ from the estimation. An example shows that the processing time in such a case becomes 1.4 times worse than the ideal one.

In this paper we propose a strategy in which the destaging buckets are selected dynamically, instead of a static decision of them during the split phase. Using this strategy, we don't have to collect information before processing and this method can be applied in many cases, which are unsuited to traditional methods. When we apply this method to that example which we mentioned, we can get the same performance as the ideal one.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bit83]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeW84]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeW85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ger86]
...
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sha86]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sto76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)