Main-memory index structures with fixed-size partial keys

ABSTRACT

The performance of main-memory index structures is increasingly determined by the number of CPU cache misses incurred when traversing the index. When keys are stored indirectly, as is standard in main-memory databases, the cost of key retrieval in terms of cache misses can dominate the cost of an index traversal. Yet it is inefficient in both time and space to store even moderate sized keys directly in index nodes. In this paper, we investigate the performance of tree structures suitable for OLTP workloads in the face of expensive cache misses and non-trivial key sizes. We propose two index structures, pkT-trees and pkB-trees, which significantly reduce cache misses by storing partial-key information in the index. We show that a small, fixed amount of key information allows most cache misses to be avoided, allowing for a simple node structure and efficient implementation. Finally, we study the performance and cache behavior of partial-key trees by comparing them with other main-memory tree structures for a wide variety of key sizes and key value distributions.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: J. Baulier , P. Bohannon , S. Gogate , C. Gupta , S. Haldar, DataBlitz storage manager: main-memory database performance for critical applications, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.519-520, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173-189, 1972.
• 4: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 5: Peter A. Boncz , Stefan Manegold , Martin L. Kersten, Database Architecture Optimized for the New Bottleneck: Memory Access, Proceedings of the 25th International Conference on Very Large Data Bases, p.54-65, September 07-10, 1999
• 6: T.M. Chilimbi, J.R. Larus, and M. Hill. Imporving pointer-based codes through cache-conscious data placement. Technical Report 98, University of Wisconsin-Madison, 1998.
• 7: Intel Corporation. Pentium III processor for the SC242 at 450 MHz to 800 MHz datasheet. http://developer.intel.com/design/pentiumiii/datashts/244452.htm, 2000.
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: R. Embody and B. Moore. Perfmon user's guide. http://www.cse.msu.edu/ enbody/perfmon.html.
• 11: David E. Ferguson, Bit-Tree: a data structure for fast file processing, Communications of the ACM, v.35 n.6, p.114-120, June 1992 [doi>10.1145/129888.129896]
• 12: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 13: Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, Compressing Relations and Indexes, Proceedings of the Fourteenth International Conference on Data Engineering, p.370-379, February 23-27, 1998
• 14: Bruce Jacob , Trevor Mudge, Virtual Memory in Contemporary Microprocessors, IEEE Micro, v.18 n.4, p.60-75, July 1998 [doi>10.1109/40.710872]
• 15: H. V. Jagadish , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Sudarshan, Dalí: A High Performance Main Memory Storage Manager, Proceedings of the 20th International Conference on Very Large Data Bases, p.48-59, September 12-15, 1994
• 16: T. J. Lehman , E. J. Shekita , L.-F. Cabrera, An Evaluation of Starburst's Memory Resident Storage Component, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.555-566, December 1992 [doi>10.1109/69.180606]
• 17: Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th International Conference on Very Large Data Bases, p.294-303, August 25-28, 1986
• 18: L. McVoy and C. Staelin. lmbench: Portable tools for performance analysis. In USENIX, editor, USENIX 1996 Annual Technical Conference, January 22-26, 1996. San Diego, CA, pages 279-294, Berkeley, CA, USA, January 1996. USENIX.
• 19: Sun Microsystems. The Ultra 30 architecture, technical white paper. http://www.sun.com/desktop/products/Ultra30/u30.pdf, 1997.
• 20: Sun Microsystems. Ultra 60 workstation datasheet. http://www.sun.com/desktop/products/Ultra60/ultra60 datasheet.html, 1998.
• 21: C. Mohan. ARIES/KVL: A key-value locking method for concurrency control of multiaction transactions operating on Btree indexes. In IBM Almaden Res.Ctr, Res.R. No.RJ7008, 27pp., March 1990.
• 22: J.P. Morgenthal. Microsoft COM+ will challenge application server market. Technical Whitepaper: http://www.microsoft.com/Com/wpaper/complus-appserv.asp, 1999.
• 23: Wee Keong Ng , Chinya V. Ravishankar, Block-Oriented Compression Techniques for Large Statistical Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.314-328, March 1997 [doi>10.1109/69.591455]
• 24: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 25: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 26: Rajeev Rastogi , S. Seshadri , Philip Bohannon , Dennis W. Leinbaugh , Abraham Silberschatz , S. Sudarshan, Logical and Physical Versioning in Main Memory Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.86-95, August 25-29, 1997
• 27: Theodore H. Romer , Wayne H. Ohlrich , Anna R. Karlin , Brian N. Bershad, Reducing TLB and memory overhead using online superpage promotion, Proceedings of the 22nd annual international symposium on Computer architecture, p.176-187, June 22-24, 1995, S. Margherita Ligure, Italy
• 28: Mikael Ronstrom. Design and Modelling of a Parallel Data Server for Telecom Applications. PhD thesis, Link oping University, 1998.
• 29: CORPORATE TimesTen Team, In-memory data management for consumer transactions the timesten approach, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.528-529, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
B-trees, T-tree, cache coherence, key compression, main-memory indices