ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Database Architecture Optimized for the New Bottleneck: Memory Access.

Peter A. Boncz, Stefan Manegold, Martin L. Kersten: Database Architecture Optimized for the New Bottleneck: Memory Access. VLDB 1999: 54-65
@inproceedings{DBLP:conf/vldb/BonczMK99,
  author    = {Peter A. Boncz and
               Stefan Manegold and
               Martin L. Kersten},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Database Architecture Optimized for the New Bottleneck: Memory
               Access},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {54-65},
  ee        = {db/conf/vldb/BonczMK99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the past decade, advances in speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore incresasingly a performance bottleneck for many computer applications, including database systems. In this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture; in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database System. We obtained exact statistics on events like TLB misses, L1 and L2 cache misses, by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms make them perform well, which is confirmed by experimental results.

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

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

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AvdBF+92]
Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut: PRISMA/DB: A Parallel Main Memory Relational DBMS. IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BQK96]
Peter A. Boncz, Wilko Quak, Martin L. Kersten: Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing. EDBT 1996: 147-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRK98]
Peter A. Boncz, Tim Rühl, Fred Kwakkel: The Drill Down Benchmark. VLDB 1998: 628-632 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BWK98]
Peter A. Boncz, Annita N. Wilschut, Martin L. Kersten: Flattening an Object Algebra to Provide Performance. ICDE 1998: 568-577 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CK85]
George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[htt96]
...
[htt97]
...
[Knu68]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley 1968
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LC86]
Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LN96]
Sherry Listgarten, Marie-Anne Neimat: Modelling Costs for a MM-DBMS. RTDB 1996: 72-78 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MBK99]
...
[McC95]
...
[MKW+98]
Sally A. McKee, Robert H. Klenke, Kenneth L. Wright, William A. Wulf, Maximo H. Salinas, James H. Aylor, Alan P. Baston: Smarter Memory: Improving Bandwidth for Streamed References. IEEE Computer 31(7): 54-63(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mow94]
...
[NBC+94]
Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ron98]
...
[Sil97]
...
[SKN94]
Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton: Cache Conscious Algorithms for Relational Query Processing. VLDB 1994: 510-521 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Val87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WK90]
Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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