Cache-conscious buffering for database operators with state

ABSTRACT

Database processes must be cache-efficient to effectively utilize modern hardware. In this paper, we analyze the importance of temporal locality and the resultant cache behavior in scheduling database operators for in-memory, block oriented query processing. We demonstrate how the overall performance of a workload of multiple database operators is strongly dependent on how they are interleaved with each other. Longer time slices combined with temporal locality within an operator amortize the effects of the initial compulsory cache misses needed to load the operator's state, such as a hash table, into the cache. Though running an operator to completion over all of its input results in the greatest amortization of cache misses, this is typically infeasible because of the large intermediate storage requirement to materialize all input tuples to an operator. We show experimentally that good cache performance can be obtained with smaller buffers whose size is determined at runtime. We demonstrate a low-overhead method of runtime cache miss sampling using hardware performance counters. Our evaluation considers two common database operators with state: aggregation and hash join. Sampling reveals operator temporal locality and cache miss behavior, and we use those characteristics to choose an appropriate input buffer/block size. The calculated buffer size balances cache miss amortization with buffer memory requirements.

REFERENCES

• 1: 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
• 2: Peter A. Boncz , Martin L. Kersten, MIL primitives for querying a fragmented world, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.101-119, October 1999 [doi>10.1007/s007780050076]
• 3: John Cieslewicz , Kenneth A. Ross, Adaptive aggregation on chip multiprocessors, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 4: John Cieslewicz , Kenneth A. Ross , Ioannis Giannakakis, Parallel buffers for chip multiprocessors, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China [doi>10.1145/1363189.1363192]
• 5: 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
• 6: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: 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]
• 8: D. Karger, C. Stein, and Joel Wein. Scheduling algorithms. In M. J. Atallah, editor, Handbook of Algorithms and Theory of Computation. CRC Press, 1997.
• 9: Li Liu , Eric Li , Yimin Zhang , Zhizhong Tang, Optimization of frequent itemset mining on multiple-core processor, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: Roger MacNicol , Blaine French, Sybase IQ multiplex - designed for analytics, Proceedings of the Thirtieth international conference on Very large data bases, p.1227-1230, August 31-September 03, 2004, Toronto, Canada
• 11: 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]
• 12: Stefan Manegold , Peter Boncz , Niels Nes , Martin Kersten, Cache-conscious radix-decluster projections, Proceedings of the Thirtieth international conference on Very large data bases, p.684-695, August 31-September 03, 2004, Toronto, Canada
• 13: Biswadeep Nag , David J. DeWitt, Memory allocation strategies for complex decision support queries, Proceedings of the seventh international conference on Information and knowledge management, p.116-123, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288647]
• 14: Sriram Padmanabhan , Timothy Malkemus , Ramesh C. Agarwal , Anant Jhingran, Block Oriented Processing of Relational Database Operations in Modern Computer Architectures, Proceedings of the 17th International Conference on Data Engineering, p.567-574, April 02-06, 2001
• 15: 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
• 16: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, ACM SIGMOD Record, v.29 n.2, p.475-486, June 2000
• 17: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, John Wiley & Sons, 2006
• 18: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: Jingren Zhou , John Cieslewicz , Kenneth A. Ross , Mihir Shah, Improving database performance on simultaneous multithreading processors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 20: 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
• 21: Jingren Zhou , Kenneth A. Ross, Buffering databse operations for enhanced instruction cache performance, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007592]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.8 Performance
          Subjects: Operational analysis

General Terms:
Algorithms, Design, Management, Performance