Breaking the memory wall in MonetDB

ABSTRACT

In the past decades, advances in speed of commodity CPUs have far outpaced advances in RAM latency. Main-memory access has therefore become a performance bottleneck for many computer applications; a phenomenon that is widely known as the "memory wall." In this paper, we report how research around the MonetDB database system has led to a redesign of database architecture in order to take advantage of modern hardware, and in particular to avoid hitting the memory wall. This encompasses (i) a redesign of the query execution model to better exploit pipelined CPU architectures and CPU instruction caches; (ii) the use of columnar rather than row-wise data storage to better exploit CPU data caches; (iii) the design of new cache-conscious query processing algorithms; and (iv) the design and automatic calibration of memory cost models to choose and tune these cache-conscious algorithms in the query optimizer.

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 , 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
• 3: Boncz, P.A., Zukowski, M., and Nes, N. MonetDB/X100: Hyper-pipelining query execution. In International Conference on Innovative Data Systems Research (CIDR), Jan. 2005, 225--237.
• 4: Surajit Chaudhuri , Gerhard Weikum, Rethinking Database System Architecture: Towards a Self-Tuning RISC-Style Database System, Proceedings of the 26th International Conference on Very Large Data Bases, p.1-10, September 10-14, 2000
• 5: 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
• 6: Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Improving hash join performance through prefetching, ACM Transactions on Database Systems (TODS), v.32 n.3, p.17-es, August 2007 [doi>10.1145/1272743.1272747]
• 7: 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
• 8: George P. Copeland , Setrag N. Khoshafian, A decomposition storage model, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.268-279, May 1985, Austin, Texas, United States
• 9: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 10: Stavros Harizopoulos , Anastassia Ailamaki, Steps towards cache-resident transaction processing, Proceedings of the Thirtieth international conference on Very large data bases, p.660-671, August 31-September 03, 2004, Toronto, Canada
• 11: Manegold, S. Understanding, modeling, and improving main-memory database performance. PhD thesis, Universiteit van Amsterdam, Amsterdam, the Netherlands, Dec. 2002.
• 12: Stefan Manegold , Peter Boncz , Martin L. Kersten, Generic database cost models for hierarchical memory systems, Proceedings of the 28th international conference on Very Large Data Bases, p.191-202, August 20-23, 2002, Hong Kong, China
• 13: 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]
• 14: 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
• 15: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• 16: David A. Patterson, Latency lags bandwith, Communications of the ACM, v.47 n.10, p.71-75, October 2004 [doi>10.1145/1022594.1022596]
• 17: 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
• 18: Kenneth A. Ross, Conjunctive selection conditions in main memory, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543628]
• 19: 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
• 20: 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
• 21: Michael Stonebraker , Samuel Madden , Daniel J. Abadi , Stavros Harizopoulos , Nabil Hachem , Pat Helland, The end of an architectural era: (it's time for a complete rewrite), Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 22: Jingren Zhou , Kenneth A. Ross, Implementing database operations using SIMD instructions, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564709]
• 23: 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:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems