Fractal prefetching B+-Trees: optimizing both cache and disk performance

ABSTRACT

B⁺-Trees have been traditionally optimized for I/O performance with disk pages as tree nodes. Recently, researchers have proposed new types of B⁺-Trees optimized for CPU cache performance in main memory environments, where the tree node sizes are one or a few cache lines. Unfortunately, due primarily to this large discrepancy in optimal node sizes, existing disk-optimized B⁺-Trees suffer from poor cache performance while cache-optimized B⁺-Trees exhibit poor disk performance. In this paper, we propose fractal prefetching B⁺-Trees (fpB⁺-Trees), which embed "cache-optimized" trees within "disk-optimized" trees, in order to optimize both cache and I/O performance. We design and evaluate two approaches to breaking disk pages into cache-optimized nodes: disk-first and cache-first. These approaches are somewhat biased in favor of maximizing disk and cache performance, respectively, as demonstrated by our results. Both implementations of fpB⁺-Trees achieve dramatically better cache performance than disk-optimized B⁺-Trees: a factor of 1.1-1.8 improvement for search, up to a factor of 4.2 improvement for range scans, and up to a 20-fold improvement for updates, all without significant degradation of I/O performance. In addition, fpB⁺-Trees accelerate I/O performance for range scans by using jump-pointer arrays to prefetch leaf pages, thereby achieving a speed-up of 2.5-5 on IBM's DB2 Universal Database.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 2: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 3: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 4: M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
• 5: Philip Bohannon , Peter Mcllroy , Rajeev Rastogi, Main-memory index structures with fixed-size partial keys, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.163-174, May 21-24, 2001, Santa Barbara, California, United States
• 6: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.235-246, May 21-24, 2001, Santa Barbara, California, United States
• 7: S. Chen, P. B. Gibbons, T. C. Mowry, and G. Valentin. Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance. Technical Report CMU-CS-02-115, School of Computer Science, Carnegie Mellon University, Mar. 2002.
• 8: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Zarka Cvetanovic , R. E. Kessler, Performance analysis of the Alpha 21264-based Compaq ES40 system, Proceedings of the 27th annual international symposium on Computer architecture, p.192-202, June 2000, Vancouver, British Columbia, Canada
• 10: Goetz Graefe, The Value of Merge-Join and Hash-Join in SQL Server, Proceedings of the 25th International Conference on Very Large Data Bases, p.250-253, September 07-10, 1999
• 11: Goetz Graefe , Per-Åke Larson, B-Tree Indexes and CPU Caches, Proceedings of the 17th International Conference on Data Engineering, p.349-358, April 02-06, 2001
• 12: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• 13: IBM Corp. IBM DB2 Universal Database Administration Guide Version 7. 2000.
• 14: 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
• 15: David Lomet, B-tree page size when caching is considered, ACM SIGMOD Record, v.27 n.3, p.28-32, Sept. 1, 1998 [doi>10.1145/290593.290598]
• 16: David Lomet, The evolution of effective B-tree: page organization and techniques: a personal account, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603878]
• 17: S. McFarling. Combining Branch Predictors. Technical Report WRL Technical Note TN-36, Digital Equipment Corporation, June 1993.
• 18: 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
• 19: 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
• 20: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

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

General Terms:
Algorithms, Documentation, Theory