ABSTRACT
This paper proposes and evaluate Prefetching B+-Trees (pB+-Trees), which use prefetching to accelerate two important operations on B+-Tree indices: searches and range scans. To accelerate searches, pB+-Trees use prefetching to effectively create wider nodes than the natural data transfer size: e.g., eight vs. one cache lines or disk pages. These wider nodes reduce the height of the B+-Tree, thereby decreasing the number of expensive misses when going from parent to child without significantly increasing the cost of fetching a given node. Our results show that this technique speeds up search and update times by a factor of 1.21-1.5 for main-memory B+-Trees. In addition, it outperforms and is complementary to “Cache-Sensitive B+-Trees.” To accelerate range scans, pB+-Trees provide arrays of pointers to their leaf nodes. These allow the pB+-Tree to prefetch arbitrarily far ahead, even for nonclustered indices, thereby hiding the normally expensive cache misses associated with traversing the leaves within the range. Our results show that this technique yields over a sixfold speedup on range scans of 1000+ keys. Although our experimental evaluation focuses on main memory databases, the techniques that we propose are also applicable to hiding disk latency.
- 1.A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a Modern Processor: Where Does Time Go? In Proceedings of the 25th VLDB, pages 266-277, Sept. 1999. Google ScholarDigital Library
- 2.L. A. Barroso, K. Gharachorloo, and E. D. Bugnion. Memory System Characterization of Commercial Workloads. In Proceedings of the 25th ISCA, pages 3-14, June 1998. Google ScholarDigital Library
- 3.L. A. Barroso, K. Gharachorloo, A.Nowatzyk, and B. Verghese. Impact of Chip-Level Integration on Performance of OLTP Workloads. In Proceedings of the 6th HPCA, pages 3-14, Jan. 2000.Google Scholar
- 4.R. Bayer and K. Unterauer. Prefix B-trees. ACM Trans. on Database Systems, 2(1):11-26, March 1977. Google ScholarDigital Library
- 5.M. A. Bender, E. D. Demaine, and M. Farach-Colton. Cache-Oblivious B-Trees. In Proceedings of the 41st IEEE FOCS, pages 399-409, Nov. 2000. Google ScholarDigital Library
- 6.P. Bohannon, P. McIlroy, and R. Rastogi. Improving Main-Memory Index Performance with Partial Key Information. In Proceedings of the 2001 SIGMOD Conference, May 2001. Google ScholarDigital Library
- 7.S. Chen, P. B. Gibbons, and T. C. Mowry. Improving Index Performance through Prefetching. Technical Report CMU-CS-00-177, School of Computer Science, Carnegie Mellon University, Dec. 2000.Google ScholarCross Ref
- 8.Z. Cvetanovic and R. E. Kessler. Performance Analysis of the Alpha 21264-Based Compaq ES40 System. In Proceedings of the 27th ISCA, pages 192-202, June 2000. Google ScholarDigital Library
- 9.J. Goldstein, R. Ramakrishnan, and U. Shaft. Compressing Relations and Indexes. In Proceedings of the 14th ICDE, pages 370-379, Feb. 1998. Google ScholarDigital Library
- 10.K. Keeton, D. A. Patterson, Y. Q. He, R. C. Raphael, and W. E. Baker. Performance Characterization of a Quad Pentium Pro SMP using OLTP Workloads. In Proceedings of the 25th ISCA, pages 15-26, June 1998. Google ScholarDigital Library
- 11.T. J. Lehman and M. J. Carey. A Study of Index Structures for Main Memory Database Management Systems. In Proceedings of the 12th VLDB, pages 294-303, Aug. 1986. Google ScholarDigital Library
- 12.T. J. Lehman and M. J. Carey. Query Processing in Main Memory Database Management Systems. In Proceedings of the 1986 SIGMOD Conference, pages 239-250, May 1986. Google ScholarDigital Library
- 13.C.-K. Luk and T. C. Mowry. Compiler-Based Prefetching for Recursive Data Structures. In Proceedings of the 7th ASPLOS, pages 222-233, Oct. 1996. Google ScholarDigital Library
- 14.C.-K. Luk and T. C. Mowry. Automatic Compiler-Inserted Prefetching for Pointer-Based Applications. IEEE Transactions on Computers, 48(2):134-141, Feb. 1999. Google ScholarDigital Library
- 15.S. McFarling. Combining Branch Predictors. Technical Report WRL Technical Note TN-36, Digital Equipment Corporation, June 1993.Google Scholar
- 16.T. C. Mowry, M. S. Lam, and A. Gupta. Design and Evaluation of a Compiler Algorithm for Prefetching. In Proceedings of the 5th ASPLOS, pages 62-73, Oct. 1992. Google ScholarDigital Library
- 17.C. Nyberg, T. Barclay, Z.Cvetanovic, J. Gray, and D. Lomet. AlphaSort: A RISC Machine Sort. In Proceedings of the 1994 SIGMOD Conference, pages 233-242, May 1994. Google ScholarDigital Library
- 18.P. Ranganathan, K. Gharachorloo, S. V. Adve, and L. A. Barroso. Performance of Database Workloads on Shared-Memory Systems with Out-of-Order Processors. In Proceedings of the 8th ASPLOS, pages 307-318, Oct. 1998. Google ScholarDigital Library
- 19.J. Rao and K. A. Ross. Cache Conscious Indexing for Decision-Support in Main Memory. In Proceedings of the 25th VLDB, pages 78-89, Sept. 1999. Google ScholarDigital Library
- 20.J. Rao and K. A. Ross. Making B + -Trees Cache Conscious in Main Memory. In Proceedings of the SIGMOD 2000 Conference, pages 475-486, May 2000. Google ScholarDigital Library
- 21.A. Shatdal, C. Kant, and J. F. Naughton. Cache Conscious Algorithms for Relational Query Processing. In Proceedings of the 20th VLDB, pages 510-521, Sept. 1994. Google ScholarDigital Library
- 22.A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts. McGraw Hill, New York, New York, 3rd edition, 1997. Google ScholarDigital Library
- 23.K. C. Yeager. The MIPS R10000 Superscalar Microprocessor. IEEE Micro, 16(2):28-40, April 1996. Google ScholarDigital Library
Index Terms
- Improving index performance through prefetching
Recommendations
Improving index performance through prefetching
This paper proposes and evaluate Prefetching B+-Trees (pB+-Trees), which use prefetching to accelerate two important operations on B+-Tree indices: searches and range scans. To accelerate searches, pB+-Trees use prefetching to effectively create wider ...
Improving hash join performance through prefetching
Hash join algorithms suffer from extensive CPU cache stalls. This article shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 80% of its user time stalled on CPU cache misses, and explores the use of CPU ...
Comments