Cache Conscious Indexing for Decision-Support in Main Memory.

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

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)

[CLH98]

...

[Com79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)

[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)

[Eng98]

...

[Fre95]

Clark D. French: ``One Size Fits All'' Database Architectures Do Not Work for DDS. SIGMOD Conference 1995: 449-450

[Fre97]

Clark D. French: Teaching an OLTP Database Kernel Advanced Data Warehousing Techniques. ICDE 1997: 194-198

[GBC98]

Goetz Graefe, Ross Bunker, Shaun Cooper: Hash Joins and Hash Teams in Microsoft SQL Server. VLDB 1998: 86-97

[GMS86]

...

[GR93]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents

[Hag86]

Robert B. Hagmann: Crash Recovery Scheme for a Memory-Resident Database System. IEEE Trans. Computers 35(9): 839-843(1986)

[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

[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)

[Knu73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X

[LC86a]

Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250

[LC86b]

Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303

[LC87]

Tobin J. Lehman, Michael J. Carey: A Recovery Algorithm for A High-Performance Memory-Resident Database System. SIGMOD Conference 1987: 104-117

[LL96]

Anthony LaMarca, Richard E. Ladner: The Influence of Caches on the Performance of Heaps. ACM Journal of Experimental Algorithmics 1: 4(1996)

[LL97]

Anthony LaMarca, Richard E. Ladner: The Influence of Caches on the Performance of Sorting. SODA 1997: 370-379

[LN88]

Kai Li, Jeffrey F. Naughton: Multiprocessor Main Memory Transaction Processing. DPDS 1988: 177-187

[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)

[NBC+94]

Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242

[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

[SKN94]

Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton: Cache Conscious Algorithms for Relational Query Processing. VLDB 1994: 510-521

[Smi82]

Alan Jay Smith: Cache Memories. ACM Comput. Surv. 14(3): 473-530(1982)

[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)

[WL91]

Michael E. Wolf, Monica S. Lam: A Data Locality Optimizing Algorithm. PLDI 1991: 30-44