Digital Symposium Collection 2000

Database Architecture Optimized for the New Bottleneck: Memory Access Peter A. Boncz, Stefan Manegold, and Martin L. Kersten   View Paper (PDF)   Return to Main-Memory Caching Abstract In the past decade, advances in speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore incresasingly a performance bottleneck for many computer applications, including database systems. In this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture; in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database System. We obtained exact statistics on events like TLB misses, L1 and L2 cache misses, by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms make them perform well, which is confirmed by experimental results. References Note: References link to DBLP on the Web. [AvdBF+92] Peter M. G. Apers , Carel A. van den Berg , Jan Flokstra , Paul W. P. J. Grefen , Martin L. Kersten , Annita N. Wilschut : PRISMA/DB: A Parallel Main Memory Relational DBMS. TKDE 4(6) : 541-554(1992) [BQK96] Peter A. Boncz , Wilko Quak , Martin L. Kersten : Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing. EDBT 1996 : 147-166 [BRK98] Peter A. Boncz , Tim Rühl , Fred Kwakkel : The Drill Down Benchmark. VLDB 1998 : 628-632 [BWK98] Peter A. Boncz , Annita N. Wilschut , Martin L. Kersten : Flattening an Object Algebra to Provide Performance. ICDE 1998 : 568-577 [CK85] George P. Copeland , Setrag Khoshafian : A Decomposition Storage Model. SIGMOD Conference 1985 : 268-279 [htt96] ... [htt97] ... [Knu68] Donald E. Knuth : The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley 1968 [LC86] Tobin J. Lehman , Michael J. Carey : A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986 : 294-303 [LN96] Sherry Listgarten , Marie-Anne Neimat : Modelling Costs for a MM-DBMS. RTDB 1996 : 72-78 [MBK99] ... [McC95] ... [MKW+98] Sally A. McKee , Robert H. Klenke , Kenneth L. Wright , William A. Wulf , Maximo H. Salinas , James H. Aylor , Alan P. Baston : Smarter Memory: Improving Bandwidth for Streamed References. IEEE Computer 31(7) : 54-63(1998) [Mow94] ... [NBC+94] Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , David B. Lomet : AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994 : 233-242 [Ron98] ... [Sil97] ... [SKN94] Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton : Cache Conscious Algorithms for Relational Query Processing. VLDB 1994 : 510-521 [Val87] Patrick Valduriez : Join Indices. TODS 12(2) : 218-246(1987) [WK90] Kyu-Young Whang , Ravi Krishnamurthy : Query Optimization in a Memory-Resident Domain Relational Calculus Database System. TODS 15(1) : 67-95(1990) BIBTEX @inproceedings{DBLP:conf/vldb/BonczMK99,   author    = {Peter A. Boncz and                 Stefan Manegold and                 Martin L. Kersten},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {Database Architecture Optimized for the New Bottleneck: Memory                 Access},    booktitle = {VLDB'99, Proceedings of 25th International Conference on Very                 Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {54-65},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM