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.
- Ailamaki, A.G., DeWitt, DJ., Hill, M.D., and Wood, D.A. DBMSs on a modern processor: Where does time go? In International Conference on Very Large Data Bases (VLDB), Sept. 1999, 266--277. Google ScholarDigital Library
- Boncz, P.A., Manegold, S., and Kersten, M.L. Database architecture optimized for the new bottleneck: Memory access. In International Conference on Very Large Data Bases (VLDB), Sept. 1999, 54--65. Google ScholarDigital Library
- 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.Google Scholar
- Chaudhuri, S. and Weikum, G. Rethinking database system architecture: Towards a self-tuning RISC-style database system. In International Conference on Very Large Data Bases (VLDB), Sept. 2000, 1--10. Google ScholarDigital Library
- Chen, S., Ailamaki, A., Gibbons, PB., and Mowry, T.C. Inspector joins. In International Conference on Very Large Data Bases (VLDB), Aug. 2005. Google ScholarDigital Library
- Chen, S., Ailamaki, A., Gibbons, PB., and Mowry, T.C. Improving hash join performance through prefetching ACM Trans. Database Syst., 32, 3,2007). Google ScholarDigital Library
- Chen, S., Gibbons, PB., and Mowry T.C. Improving index performance through prefetching. In ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2001. Google ScholarDigital Library
- Copeland, G.P. and Khoshafian, S. A decomposition storage model. In ACM SIGMOD International Conference on Management of Data (SIGMOD), May 1985, 268--279. Google ScholarDigital Library
- Govindaraju, N., Gray, J., Kumar, R., and Manocha, D. GPUTeraSort: High performance graphics coprocessor sorting for large database management. In ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2006. Google ScholarDigital Library
- Harizopoulos, S. and Ailamaki, A. STEPS towards cache-resident transaction processing. In International Conference on Very Large Data Bases (VLDB), Aug. 2004. Google ScholarDigital Library
- Manegold, S. Understanding, modeling, and improving main-memory database performance. PhD thesis, Universiteit van Amsterdam, Amsterdam, the Netherlands, Dec. 2002.Google Scholar
- Manegold, S., Boncz, P.A., and Kersten, M.L. Generic database cost models for hierarchical memory systems. In International Conference on Very Large Data Bases (VLDB), Aug. 2002, 191--202. Google ScholarDigital Library
- Manegold, S., Boncz, P.A., and Kersten, M.L. Optimizing main-memory join on modern hardware. IEEE Trans, Knowl, Data Eng., 14, 4 (July 2002), 709--730. Google ScholarDigital Library
- Manegold, S., Boncz, P.A., Nes, N., and Kersten, M.L. Cache-conscious radix-decluster projections. In International Conference on Very Large Data Bases (VLDB), Aug. 2004, 684--695. Google ScholarDigital Library
- Maynard, A.M.G., Donnelly, CM., and Olszewski, B.R. Contrasting characteristics and cache performance of technical and multi-user commercial workloads. SIGOPS Oper. Syst. Rev., 28, 5 (Aug. 1994), 145--156. Google ScholarDigital Library
- Patterson, D. Latency lags bandwidth. Commun. ACM 47,10 (Oct. 2004), 71--75. Google ScholarDigital Library
- Rao, J. and Ross, K.A. Making B+ -Trees cache conscious in main memory. In ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2000. Google ScholarDigital Library
- Ross, K.A. Conjunctive selection conditions in main memory. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), June 2002. Google ScholarDigital Library
- Shatdal, A., Kant, C., and Naughton, J. Cache conscious algorithms for relational query processing. In International Conference on Very Large Data Bases (VLDB), Sept. 1994. 510--512. Google ScholarDigital Library
- Stonebraker, M., Abadi, DJ., Batkin, A., Chen, X., Cherniack, M., Ferreira, M., Lau, E., Lin, A., Madden, S.R., O'Neil, E.J., O'Neil, P.E., Rasin, A., Tran, N., and Zdonik, S.B. C-Store: A column-oriented DBMS. In International Conference on Very Large Data Bases (VLDB), Sept. 2005, 553--564. Google ScholarDigital Library
- Stonebraker, M., Madden, S.R., Abadi, D.J., Harizopoulos, S., Hachem, N., and Heiland, P. The end of an architectural era (it's time for a complete rewrite). In International Conference on Very Large Data Bases (VLDB), Sept. 2007 1150--1160. Google ScholarDigital Library
- Zhou, J. and Ross, K.A. Implementing database operations using SIMD instructions. In ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2002. Google ScholarDigital Library
- Zhou, J. and Ross, K.A. Buffering database operations for enhanced instruction cache performance. In ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2004. Google ScholarDigital Library
Index Terms
- Breaking the memory wall in MonetDB
Recommendations
Missing the memory wall: the case for processor/memory integration
Special Issue: Proceedings of the 23rd annual international symposium on Computer architecture (ISCA '96)Current high performance computer systems use complex, large superscalar CPUs that interface to the main memory through a hierarchy of caches and interconnect systems. These CPU-centric designs invest a lot of power and chip area to bridge the widening ...
Cache Design with Domain Wall Memory
Domain wall memory (DWM) is a recently developed spin-based memory technology in which several bits of data are densely packed into the domains of a ferromagnetic wire. DWM has shown great promise in enabling non-volatile memory with very high density and ...
Overcoming Memory Capacity Wall of GPUs With Heterogeneous Memory Stack
We propose to overcome the memory capacity limitation of GPUs with a <italic>Heterogeneous Memory Stack (HMS)</italic> that integrates Storage Class Memory (SCM) and DRAM in a 3D memory stack. By effectively utilizing the DRAM as a cache, the HMS ...
Comments