ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Cache Conscious Indexing for Decision-Support in Main Memory.

Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89
@inproceedings{DBLP:conf/vldb/RaoR99,
  author    = {Jun Rao and
               Kenneth A. Ross},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Cache Conscious Indexing for Decision-Support in Main Memory},
  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     = {78-89},
  ee        = {db/conf/vldb/RaoR99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study indexing techniques for main memory, including hash indexes, binary search trees, T-trees, B+-trees, interpolation search, and binary search on arrays. In a decision-support context, our primary concerns are the lookup time, and the space occupied by the index structure.

Our goal is to provide faster lookup times than binary search by paying attention to reference locality and cache behavior, with- out using substantial extra space. We propose a new indexing technique called ``Cache-Sensitive Search Trees'' (CSS-trees). Our technique stores a directory structure on top of a sorted array. Nodes in this directory have size matching the cache-line size of the machine. We store the directory in an array and do not store internal-node pointers; child nodes can be found by performing arithmetic on array o sets.

We compare the algorithms based on their time and space requirements. We have implemented all of the techniques, and present a performance study on two popular modern machines. We demonstrate that with a small space overhead, we can reduce the cost of binary search on the array by more than a factor of two. We also show that our technique dominates B+-trees, T-trees, and binary search trees in terms of both space and time. A cache simulation verifies that the gap is due largely to cache misses.

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

[AHK85]
...
[BBC+98]
Philip A. Bernstein, Michael L. Brodie, Stefano Ceri, David J. DeWitt, Michael J. Franklin, Hector Garcia-Molina, Jim Gray, Gerald Held, Joseph M. Hellerstein, H. V. Jagadish, Michael Lesk, David Maier, Jeffrey F. Naughton, Hamid Pirahesh, Michael Stonebraker, Jeffrey D. Ullman: The Asilomar Report on Database Research. SIGMOD Record 27(4): 74-80(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CLH98]
...
[Com79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CS83]
Francesca Cesarini, Giovanni Soda: An Algorithm to Construct a Compact B-Tree in Case of Ordered Keys. Inf. Process. Lett. 17(1): 13-16(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Eng98]
...
[Fre95]
Clark D. French: ``One Size Fits All'' Database Architectures Do Not Work for DDS. SIGMOD Conference 1995: 449-450 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre97]
Clark D. French: Teaching an OLTP Database Kernel Advanced Data Warehousing Techniques. ICDE 1997: 194-198 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GBC98]
Goetz Graefe, Ross Bunker, Shaun Cooper: Hash Joins and Hash Teams in Microsoft SQL Server. VLDB 1998: 86-97 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GMS86]
...
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hag86]
Robert B. Hagmann: Crash Recovery Scheme for a Memory-Resident Database System. IEEE Trans. Computers 35(9): 839-843(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Inc99]
...
[JLRS94]
H. V. Jagadish, Daniel F. Lieuwen, Rajeev Rastogi, Abraham Silberschatz, S. Sudarshan: Dalí: A High Performance Main Memory Storage Manager. VLDB 1994: 48-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JTR87]
Wiebren de Jonge, Andrew S. Tanenbaum, Reind P. van de Riet: Two Access Methods Using Compact Binary Trees. IEEE Trans. Software Eng. 13(7): 799-810(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knu73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LC86a]
Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LC86b]
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
[LC87]
Tobin J. Lehman, Michael J. Carey: A Recovery Algorithm for A High-Performance Memory-Resident Database System. SIGMOD Conference 1987: 104-117 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LL96]
Anthony LaMarca, Richard E. Ladner: The Influence of Caches on the Performance of Heaps. ACM Journal of Experimental Algorithmics 1: 4(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LL97]
Anthony LaMarca, Richard E. Ladner: The Influence of Caches on the Performance of Sorting. SODA 1997: 370-379 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LN88]
Kai Li, Jeffrey F. Naughton: Multiprocessor Main Memory Transaction Processing. DPDS 1988: 177-187 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LSC92]
Tobin J. Lehman, Eugene J. Shekita, Luis-Felipe Cabrera: An Evaluation of Starburst's Memory Resident Storage Component. IEEE Trans. Knowl. Data Eng. 4(6): 555-566(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[Pet57]
...
[SAC+79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[Smi82]
Alan Jay Smith: Cache Memories. ACM Comput. Surv. 14(3): 473-530(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sof97]
...
[Syb97]
...
[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
[WL91]
Michael E. Wolf, Monica S. Lam: A Data Locality Optimizing Algorithm. PLDI 1991: 30-44 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)