A general framework for improving query processing performance on multi-level memory hierarchies

ABSTRACT

We propose a general framework for improving the query processing performance on multi-level memory hierarchies. Our motivation is that (1) the memory hierarchy is an important performance factor for query processing, (2) both the memory hierarchy and database systems are becoming increasingly complex and diverse, and (3) increasing the amount of tuning does not always improve the performance. Therefore, we categorize multiple levels of memory performance tuning and quantify their performance impacts. As a case study, we use this framework to improve the in-memory performance of storage models, B+-trees, nested-loop joins and hash joins. Our empirical evaluation verifies the usefulness of the proposed framework.

REFERENCES

• 1: Anastassia Ailamaki, Database Architectures for New Hardware, Proceedings of the 21st International Conference on Data Engineering, p.1148, April 05-08, 2005 [doi>10.1109/ICDE.2005.45]
• 2: 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
• 3: 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
• 4: AMD Corp. Software Optimization Guide for AMD64 Processors, 2005.
• 5: 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
• 6: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, v.53 n.2, p.115-136, November 2004 [doi>10.1016/j.jalgor.2004.04.014]
• 7: Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142385]
• 8: R. Berrendorf, H. Ziegler, and B. Mohr. PCL: Performance Counter Library. http://www.fz-juelich.de/zam/PCL/, 2002.
• 9: 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
• 10: 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
• 11: Gerth Stølting Brodal , Rolf Fagerberg, Cache Oblivious Distribution Sweeping, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.426-438, July 08-13, 2002
• 12: G. S. Brodal, R. Fagerberg, and K. Vinther. Engineering a cache-oblivious sorting algorith. In ALENEX/ANALC, pages 4--17, 2004.
• 13: Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Improving Hash Join Performance through Prefetching, Proceedings of the 20th International Conference on Data Engineering, p.116, March 30-April 02, 2004
• 14: Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Inspector joins, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, ACM SIGMOD Record, v.30 n.2, p.235-246, June 2001
• 16: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry , Gary Valentin, Fractal prefetching B⁺-Trees: optimizing both cache and disk performance, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564710]
• 17: 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
• 18: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 19: Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, Cache-conscious frequent pattern mining on a modern processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 20: Richard A. Hankins , Jignesh M. Patel, Data morphing: an adaptive, cache-conscious storage technique, Proceedings of the 29th international conference on Very large data bases, p.417-428, September 09-12, 2003, Berlin, Germany
• 21: N. Hardavellas, I. Pandis, R. Johnson, N. Mancheril, S. Harizopoulos, A. Ailamaki, and B. Falsafi. Database servers on chip multiprocessors: Limitations and opportunities. In CIDR '07: Proceedings of the Third International Conference on Innovative Data Systems Research, Asilomar, CA, USA, 2007.
• 22: Stavros Harizopoulos , Anastassia Ailamaki, Improving instruction cache performance in OLTP, ACM Transactions on Database Systems (TODS), v.31 n.3, p.887-920, September 2006 [doi>10.1145/1166074.1166079]
• 23: Stavros Harizopoulos , Vladislav Shkapenyuk , Anastassia Ailamaki, QPipe: a simultaneously pipelined relational query engine, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066201]
• 24: Bingsheng He , Qiong Luo, Cache-oblivious nested-loop joins, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183717]
• 25: B. He and Q. Luo. Cache-oblivious query processing. In CIDR '07: Proceedings of the Third International Conference on Innovative Data Systems Research, Asilomar, CA, USA, 2007.
• 26: Intel Corp. Intel(R) Itanium(R) 2 Processor Reference Manual for Software Development and Optimization, 2004.
• 27: Kihong Kim , Sang K. Cha , Keunjoo Kwon, Optimizing multidimensional index trees for main memory access, ACM SIGMOD Record, v.30 n.2, p.139-150, June 2001
• 28: Stefan Manegold , Peter Boncz , Martin Kersten, Optimizing Main-Memory Join on Modern Hardware, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.709-730, July 2002 [doi>10.1109/TKDE.2002.1019210]
• 29: 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
• 30: 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
• 31: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 32: Sun Corp. UltraSPARC (R) III Cu Users Manual, 1997.
• 33: Jingren Zhou , Kenneth A. Ross, Buffering accesses to memory-resident index structures, Proceedings of the 29th international conference on Very large data bases, p.405-416, September 09-12, 2003, Berlin, Germany