An architecture for recycling intermediates in a column-store

ABSTRACT

Automatically recycling (intermediate) results is a grand challenge for state-of-the-art databases to improve both query response time and throughput. Tuples are loaded and streamed through a tuple-at-a-time processing pipeline avoiding materialization of intermediates as much as possible. This limits the opportunities for reuse of overlapping computations to DBA-defined materialized views and function/result cache tuning.

In contrast, the operator-at-a-time execution paradigm produces fully materialized results in each step of the query plan. To avoid resource contention, these intermediates are evicted as soon as possible.

In this paper we study an architecture that harvests the by-products of the operator-at-a-time paradigm in a column store system using a lightweight mechanism, the recycler. The key challenge then becomes selection of the policies to admit intermediates to the resource pool, their retention period, and the eviction strategy when facing resource limitations.

The proposed recycling architecture has been implemented in an open-source system. An experimental analysis against the TPC-H ad-hoc decision support benchmark and a complex, real-world application (SkyServer) demonstrates its effectiveness in terms of self-organizing behavior and its significant performance gains. The results indicate the potentials of recycling intermediates and charters a route for further development of database kernels.

REFERENCES

• 1: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 2: Peter A. Boncz , Martin L. Kersten , Stefan Manegold, Breaking the memory wall in MonetDB, Communications of the ACM, v.51 n.12, December 2008 [doi>10.1145/1409360.1409380]
• 3: C. Bornhövd, M. Altinel, C. Mohan, H. Pirahesh, and B. Reinwald. Adaptive Database Caching with DBCache. IEEE Data Eng. Bull., 27(2):11--18, 2004.
• 4: Nicolas Bruno , Surajit Chaudhuri, Physical design refinement: The ‘merge-reduce’ approach, ACM Transactions on Database Systems (TODS), v.32 n.4, p.28-es, November 2007 [doi>10.1145/1292609.1292618]
• 5: Chungmin Melvin Chen , Nicholas Roussopoulos, The implementation and performance evaluation of the ADMS query optimizer: integrating query result caching and matching, Proceedings of the 4th international conference on extending database technology: Advances in database technology, p.323-336, May 1994, Cambridge, United Kingdom
• 6: C.-H. Choi, J. X. Yu, and H. Lu. Dynamic Materialized View Management Based on Predicates. In APWeb, pages 583--594, 2003.
• 7: Roberto Cornacchia , Sándor Héman , Marcin Zukowski , Arjen P. Vries , Peter Boncz, Flexible and efficient IR using array databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.1, p.151-168, January 2008 [doi>10.1007/s00778-007-0071-0]
• 8: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 9: G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994 [doi>10.1109/69.273032]
• 10: Milena Ivanova , Martin L. Kersten , Niels Nes, Self-organizing strategies for a column-store database, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353366]
• 11: M. Ivanova , N. Nes , R. Goncalves , M. Kersten, MonetDB/SQL Meets SkyServer: the Challenges of a Scientific Database, Proceedings of the 19th International Conference on Scientific and Statistical Database Management, p.13, July 09-11, 2007 [doi>10.1109/SSDBM.2007.19]
• 12: Yannis Kotidis , Nick Roussopoulos, A case for dynamic view management, ACM Transactions on Database Systems (TODS), v.26 n.4, p.388-423, December 2001 [doi>10.1145/503099.503100]
• 13: Per-Åke Larson , Jonathan Goldstein , Jingren Zhou, MTCache: Transparent Mid-Tier Database Caching in SQL Server, Proceedings of the 20th International Conference on Data Engineering, p.177, March 30-April 02, 2004
• 14: G. Luo. Partial Materialized Views. In ICDE, pages 756--765, 2007.
• 15: Gang Luo , Philip S. Yu, Content-based filtering for efficient online materialized view maintenance, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458107]
• 16: Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.307-318, May 21-24, 2001, Santa Barbara, California, United States
• 17: MonetDB, http://monetdb.cwi.nl/, 2008.
• 18: Thomas Phan , Wen-Syan Li, Dynamic Materialization of Query Views for Data Warehouse Workloads, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.436-445, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497452]
• 19: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 20: Sloan Digital Sky Survey / SkyServer, 2008.
• 21: Alexander S. Szalay , Jim Gray , Ani R. Thakar , Peter Z. Kunszt , Tanu Malik , Jordan Raddick , Christopher Stoughton , Jan vandenBerg, The SDSS skyserver: public access to the sloan digital sky server data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564758]
• 22: Kian-Lee Tan , Shen-Tat Goh , Beng Chin Ooi, Cache-on-Demand: Recycling with Certainty, Proceedings of the 17th International Conference on Data Engineering, p.633-640, April 02-06, 2001
• 23: Transaction Processing Performance Council. TPC Benchmark H, Revision 2.6.2, 2008.
• 24: Jingren Zhou , Per-Ake Larson , Johann-Christoph Freytag , Wolfgang Lehner, Efficient exploitation of similar subexpressions for query processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247540]
• 25: J. Zhou, P.-Å. Larson, J. Goldstein, and L. Ding. Dynamic Materialized Views. In ICDE, pages 526--535, 2007.
• 26: Marcin Zukowski , Sandor Heman , Niels Nes , Peter Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, p.59, April 03-07, 2006 [doi>10.1109/ICDE.2006.150]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Management, Performance

Keywords:
caching, column-stores, databasekernels