article

Main-memory index structures with fixed-size partial keys

Authors:

Philip Bohannon,

Rajeev RastogiAuthors Info & Claims

ACM SIGMOD Record, Volume 30, Issue 2

Pages 163 - 174

https://doi.org/10.1145/376284.375681

Published: 01 May 2001 Publication History

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]

A. Aho, J. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

Digital Library

[2]

J. Baulier, P. Bohannon, S. Gogate, C. Gupta, S. Haldar, S. Joshi, A. Khivesera, H. Korth, P. Mcilroy, J. Miller, P.P.S. Narayan, M. Nemeth, R. Rastogi, S. Seshardi, A. Silberschatz, S. Sudarshan, M. Wilder, and C. Wei. Datablitz storage manager: Main memory database performance for critical applications. In Proceedings of the 1999 ACM SIGMOD/PIDS International Conference on Management of Data, June 1999.

Digital Library

[3]

R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173-189, 1972.

Digital Library

[4]

R. Bayer and K. Unterauer. Prefix B-trees. ACM Transactions on Database Systems, 2(1), March 1977.

Digital Library

[5]

P. Boncz, S. Manegold, and M. Kersten. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the Twenty-Fifth International Conference on Very Large Databases, Edinburgh, August 1999.

Digital Library

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

T. Cover and J. Thomas. Elements of Information Theory. John Wiley & Sons, New York, 1991.

Digital Library

[9]

D.J. DeWitt, R. Katz, F. Olken, D. Shapiro, M. Stonebraker, and D. Wood. Implementation techniques for main memory database systems. In Proc. of ACM-SIGMOD Int'l Conference on Management of Data, pages 1-8, Boston, Mass., June 1984.

Digital Library

[10]

R. Embody and B. Moore. Perfmon user's guide. http://www.cse.msu.edu/ enbody/perfmon.html.

[11]

D. Ferguson. Bit-tree a data structure for fast file processing. Communications of the ACM, 35(6):114-120, June 1992.

Digital Library

[12]

H. Garcia-Molina and K. Salem. Main memory database systems: An overview. IEEE Transactions on Knowledge and Data Engineering, 4(6):509-516, December 1992.

Digital Library

[13]

J. Goldstein, R. Ramakrishnan, and U. Shaft. "Compressing Relations and Indexes". In Proceedings of the International Conference on Data Engineering, Orlando, Florida, 1998.

Digital Library

[14]

B. Jacob and T. Mudge. Virtual memory in contemporary microprocessors. IEEE Micro, 18(4), July 1998.

Digital Library

[15]

H. V. Jagadish, D. Lieuwen, R. Rastogi, A. Silberschatz, and S. Sudarshan. Dali: A high performance main-memory storage manager. In Proc. of the Int'l Conf. on Very Large Databases, 1994.

Digital Library

[16]

T. Lehman, E. J. Shekita, and L. Cabrera. An evaluation of Starburst's memory resident storage component. IEEE Transactions on Knowledge and Data Engineering, 4(6):555-566, December 1992.

Digital Library

[17]

T. J. Lehman and M. J. Carey. A study of index structures for main memory database management systems. In Proc. of the Int'l Conf. on Very Large Databases, pages 294-303, August 1986.

Digital Library

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

Digital Library

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

W.K. Ng and C.V. Ravishankar. Block-oriented compression techniques for large statistical databases. IEEE Transactions on Knowledge and Data Engineering, 9(2):314-328, 1997.

Digital Library

[24]

J. Rao and K.A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the Twenty-Fifth International Conference on Very Large Databases, Edinburgh, August 1999.

Digital Library

[25]

J. Rao and K.A. Ross. Making B* -trees cache conscious in main memory. In (to be published) Proceedings of ACM-SIGMOD 2000 International Conference on Management of Data, May 2000.

Digital Library

[26]

R. Rastogi, S. Seshadri, P. Bohannon, D. Leinbaugh, A. Silberschatz, and S. Sudarshan. Logical and physical versioning in main-memory databases. In Proceedings of the 23rd Int'l Conference on Very Large Databases, August 1997.

Digital Library

[27]

T. Romer, W. Ohlrich, A. Karlin, and B. Bershad. Reducing TLB and memory overhead using online superpage promotion. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 176-187, 1995.

Digital Library

[28]

Mikael Ronstrom. Design and Modelling of a Parallel Data Server for Telecom Applications. PhD thesis, Link oping University, 1998.

[29]

The TimesTen Team. In-memory data management for consumer transactions the timesten approach. In Proceedings of the 1999 ACM SIGMOD/PIDS International Conference on Management of Data, June 1999.

Digital Library

Cited By

Gao CBallijepalli SWang J(2024)Revisiting B-tree Compression: An Experimental StudyProceedings of the ACM on Management of Data10.1145/36549722:3(1-25)Online publication date: 30-May-2024
https://doi.org/10.1145/3654972
Wang ZChen HWang YTang CWang H(2022)The Concurrent Learned Indexes for Multicore Data StorageACM Transactions on Storage10.1145/347828918:1(1-35)Online publication date: 29-Jan-2022
https://dl.acm.org/doi/10.1145/3478289
Wang YTang CWang ZChen HKim TLee P(2020)SIndexProceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3409963.3410496(17-24)Online publication date: 24-Aug-2020
https://dl.acm.org/doi/10.1145/3409963.3410496
Show More Cited By

Index Terms

Main-memory index structures with fixed-size partial keys
1. Information systems
  1. Information retrieval
  2. Information storage systems
    1. Record storage systems
      1. Directory structures
        B-trees
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Main-memory index structures with fixed-size partial keys
SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of data

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 ...
Minimizing the Directory Size for Large-Scale Shared-Memory Multiprocessors

Directory-based cache coherence schemes are commonly used in large-scale shared-memory multiprocessors, but most of them rely on heuristics to avoid large hardware requirements. We proposed using physical address mapping on directories to significantly ...
An efficient cache design for scalable glueless shared-memory multiprocessors
CF '06: Proceedings of the 3rd conference on Computing frontiers

Traditionally, cache coherence in large-scale shared-memory multiprocessors has been ensured by means of a distributed directory structure stored in main memory. In this way, the access to main memory to recover the sharing status of the block is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 30, Issue 2

June 2001

625 pages

ISSN:0163-5808

DOI:10.1145/376284

Editors:
Timos Sellis
National Technical Univ. of Athens
,
Sharad Mehrotra
Univ. of California at Irvine

Issue’s Table of Contents

SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of data
May 2001
630 pages
ISBN:1581133324
DOI:10.1145/375663
Editors:
Timos Sellis,
Sharad Mehrotra

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2001

Published in SIGMOD Volume 30, Issue 2

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
1,408
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)7

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao CBallijepalli SWang J(2024)Revisiting B-tree Compression: An Experimental StudyProceedings of the ACM on Management of Data10.1145/36549722:3(1-25)Online publication date: 30-May-2024
https://doi.org/10.1145/3654972
Wang ZChen HWang YTang CWang H(2022)The Concurrent Learned Indexes for Multicore Data StorageACM Transactions on Storage10.1145/347828918:1(1-35)Online publication date: 29-Jan-2022
https://dl.acm.org/doi/10.1145/3478289
Wang YTang CWang ZChen HKim TLee P(2020)SIndexProceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3409963.3410496(17-24)Online publication date: 24-Aug-2020
https://dl.acm.org/doi/10.1145/3409963.3410496
Elsayed EKise K(2018)Design and Evaluation of a Configurable Hardware Merge Sorter for Various Output Records2018 IEEE 12th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)10.1109/MCSoC2018.2018.00041(201-208)Online publication date: Sep-2018
https://doi.org/10.1109/MCSoC2018.2018.00041
Yu CBoyd J(2016)FB+-tree for Big Data ManagementBig Data Research10.1016/j.bdr.2015.11.0034:C(25-36)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.bdr.2015.11.003
Binna RPacher DMeindl TSpecht G(2015)The DCB-Tree: A Space-Efficient Delta Coded Cache Conscious B-TreeIn Memory Data Management and Analysis10.1007/978-3-319-13960-9_10(126-138)Online publication date: 14-Jan-2015
https://doi.org/10.1007/978-3-319-13960-9_10
Paradies MRudolf MBornhövd CLehner WBoncz PPey J(2014)GRATINProceedings of Workshop on GRAph Data management Experiences and Systems10.1145/2621934.2621941(1-6)Online publication date: 22-Jun-2014
https://dl.acm.org/doi/10.1145/2621934.2621941
Mao YKohler EMorris RFelber PBellosa FBos H(2012)Cache craftiness for fast multicore key-value storageProceedings of the 7th ACM european conference on Computer Systems10.1145/2168836.2168855(183-196)Online publication date: 10-Apr-2012
https://dl.acm.org/doi/10.1145/2168836.2168855
Wassenberg JSanders P(2011)Engineering a Multi-core Radix SortEuro-Par 2011 Parallel Processing10.1007/978-3-642-23397-5_16(160-169)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23397-5_16
Cambazoglu BAykanat C(2006)Performance of query processing implementations in ranking-based text retrieval systems using inverted indicesInformation Processing and Management: an International Journal10.1016/j.ipm.2005.06.00442:4(875-898)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1016/j.ipm.2005.06.004
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents