Database architecture evolution
Proceedings of the VLDB EndowmentPublished 1 August 2009
Stefan Manegold, Martin Kersten, Peter Boncz
Citations111
SJR quartileQ1
SJR score1.83
SNIP1.80
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A trip report on the quest to find a database architecture solution that is Scalable & Speedy, to run on anything from small ARM processors up to globally distributed compute clusters, Stable & Secure, to service a broad user community, Small & Simple.
Abstract
The holy grail for database architecture research is to find a solution that is Scalable & Speedy , to run on anything from small ARM processors up to globally distributed compute clusters, Stable & Secure , to service a broad user community, Small & Simple , to be comprehensible to a small team of programmers, Self-managing , to let it run out-of-the-box without hassle. In this paper, we provide a trip report on this quest, covering both past experiences, ongoing research on hardware-conscious algorithms, and novel ways towards self-management specifically focused on column store solutions.
Keywords
Computer Science
C-store: a column-oriented DBMS
923 Citations2005Mike Stonebraker, Daniel J. Abadi +12 more
Very Large Data BasesThe end of an architectural era: (it's time for a complete rewrite)
575 Citations2007Michael Stonebraker, Samuel Madden +4 more
ACM Transactions on Database SystemsJoin indices
504 Citations1987Patrick Valduriez
This paper proposes a simple data structure, called a join index, for improving the performance of joins in the context of complex queries, and analysis of the join algorithm using join indices shows its excellent performance.
Improved query performance with variant indexes
482 Citations1997Patrick E. O׳Neil, Dallan Quass
A new method whereby multi-dimensional group-by queries, reminiscent of OLAP/Datacube queries but with more flexibility, can be very efficiently performed is introduced.
Super-Scalar RAM-CPU Cache Compression
478 Citations2006Marcin Żukowski, Sándor Héman +2 more
This work proposes three new versatile compression schemes (PDICT, PFOR, and PFOR-DELTA) that are specifically designed to extract maximum IPC from modern CPUs and compares these algorithms with compression techniques used in (commercial) database and information retrieval systems.
Infoscience (Ecole Polytechnique Fédérale de Lausanne)DBMSs on a Modern Processor: Where Does Time Go?
455 Citations1999Anastassia Ailamaki, David J. DeWitt +2 more
This paper examines four commercial DBMSs running on an Intel Xeon and NT 4.0 and introduces a framework for analyzing query execution time, and finds that database developers should not expect the overall execution time to decrease significantly without addressing stalls related to subtle implementation issues.
A decomposition storage model
421 Citations1985George P. Copeland, Setrag Khoshafian
This report examines the relative advantages of a storage model based on decomposition over conventional n-ary storage models and claims that neither is clearly better until a closer analysis is made along the many dimensions of a database system.
ACM SIGMOD RecordMaking B+- trees cache conscious in main memory
378 Citations2000Jun Rao, Kenneth A. Ross
CWI's Institutional Repository (Centrum Wiskunde & Informatica)Database Architecture Optimized for the New Bottleneck: Memory Access
348 Citations1999Peter Boncz, Stefan Manegold +1 more
Weaving Relations for Cache Performance
326 Citations2001Anastassia Ailamaki, David J. DeWitt +2 more
This paper proposes a new data organization model called PAX (Partition Attributes Across), that significantly improves cache performance by grouping together all values of each attribute within each page, and demonstrates that in-page data placement is the key to high cache performance.
MonetDB/XQuery
294 Citations2006Peter Boncz, Torsten Grust +4 more
The main features, key contributions, and lessons learned while implementing a purely relational XQuery system, which implements all essential XML database functionalities such that it can learn from the full consequences of the architectural decisions.
Elsevier eBooksDB2 Design AdvisorIntegrated Automatic Physical Database Design
292 Citations2004Daniel C. Zilio, Jun Rao +5 more
Cache Conscious Indexing for Decision-Support in Main Memory
249 Citations1998Jun Rao, Kenneth A. Ross
A new indexing technique called \Cache-Sensitive Search Trees" (CSS-trees) is proposed, to provide faster lookup times than binary search by paying attention to reference locality and cache behavior, without using substantial extra space.
ACM SIGMOD RecordThe Asilomar report on database research
231 Citations1998Phil Bernstein, Michael L. Brodie +14 more
The database research community should embrace a broader research agenda — broadening the definition of database management to embrace all the content of the Web and other online data stores, and rethinking the authors' fundamental assumptions in light of technology shifts.
Elsevier eBooksDatabase Tuning Advisor for Microsoft SQL Server 2005
208 Citations2004Sanjay Agrawal, Surajit Chaudhuri +4 more
Proceedings of the VLDB EndowmentColumn-store support for RDF data management
208 Citations2008Lefteris Sidirourgos, Romulo Gonçalves +3 more
This paper reports on the results of an independent evaluation of the techniques presented in the VLDB 2007 paper "Scalable Semantic Web Data Management Using Vertical Partitioning", as well as a complementary analysis of state-of-the-art RDF storage solutions.
Making B+- trees cache conscious in main memory
185 Citations2000Jun Rao, Kenneth A. Ross
A new indexing technique called CSB+-Trees is proposed that stores all the child nodes of any given node contiguously, and keeps only the address of the first child in each node, and introduces two variants of CSB+, which can reduce the copying cost when there is a split and preallocate space for the full node group to reduce the split cost.
Minds at UW (University of Wisconsin)Cache Conscious Algorithms for Relational Query Processing
185 Citations1994Ambuj Shatdal, Chander Kant +1 more
It is shown that there are significant benefits in redesigning traditional query processing algorithms so that they can make better use of the cache, and new algorithms run 8%-200% faster than the traditional ones.
Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the NetherlandsOptimizing main-memory join on modern hardware
178 Citations2002Boncz, Peter, Manegold, Stefan +1 more
QPipe
173 Citations2005Stavros Harizopoulos, Vladislav Shkapenyuk +1 more
On-demand simultaneous pipelining (OSP), a novel query evaluation paradigm for maximizing data and work sharing across concurrent queries at execution time, is introduced and QPipe, a new operator-centric relational engine that effortlessly supports OSP is introduced.
Self-organizing tuple reconstruction in column-stores
166 Citations2009Stratos Idreos, Martin Kersten +1 more
A novel design, partial sideways cracking, is proposed that achieves performance similar to using presorted data, but without requiring the heavy initial presorting step itself, and brings significant performance benefits for multi-attribute queries.
The VLDB JournalA case for fractured mirrors
146 Citations2003Ravishankar Ramamurthy, David J. DeWitt +1 more
A new mirroring scheme is proposed, termed fractured mirrors, using both NSM and DSM models, that combines the best aspects of both models, along with the added benefit of mirroring to better serve an ad hoc query workload.
ACM Transactions on Database SystemsImproving hash join performance through prefetching
133 Citations2007Shimin Chen, Anastassia Ailamaki +2 more
This work shows that the standard hash join algorithm/or disk-oriented databases (i.e. GRACE) spends over 73% of its user time stalled on CPU cache misses, and explores the use of prefetching to improve its cache performance.
Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the NetherlandsCooperative scans: dynamic bandwidth sharing in a DBMS
121 Citations2007Marcin Żukowski, Sándor Héman +2 more
This paper analyzes the performance of concurrent (index) scan operations in both record (NSM/PAX) and column (DSM) disk storage models and proposes the Cooperative Scans framework that enhances performance in such scenarios by improving data-sharing between concurrent scans.
Elsevier eBooksGeneric Database Cost Models for Hierarchical Memory Systems
115 Citations2002Stefan Manegold, Peter Boncz +1 more
A generic technique to create accurate cost functions for database operations and provides insight to tune algorithms not only in a main-memory DBMS, but also in a disk-based DBMS with a large main- memory buffer cache.
Elsevier eBooksData Morphing
94 Citations2003Richard A. Hankins, Jignesh M. Patel
The Data Morphing technique provides a significant performance improvement over both the traditional N-ary storage model and the PAX model, and also presents a versatile storage model that accommodates the dynamic reorganization of the attributes in a file.
Query execution in column-oriented database systems
90 Citations2008Samuel Madden, Daniel J. Abadi
This dissertation provides (to the best of the knowledge) the only detailed study of multiple implementation approaches of such systems, categorizing the different approaches into three broad categories, and evaluating the tradeoffs between approaches.
Communications of the ACMThe Claremont report on database research
88 Citations2009Rakesh Agrawal, Anastasia Ailamaki +25 more
Buffering databse operations for enhanced instruction cache performance
83 Citations2004Jingren Zhou, Kenneth A. Ross
This work answers the question "Why does a database system incur so many instruction cache misses" and proposes techniques to buffer database operations during query execution to avoid instruction cache thrashing.
Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the NetherlandsBalancing Vectorized Query Execution with Bandwidth-Optimized Storage
79 Citations2009Marcin Żukowski
A new database system architecture is presented, realized in the MonetDB/X100 prototype, that combines a coherent set of new architecture-conscious techniques that are designed to work well together and achieves in-memory performance often one or two orders of magnitude higher than the existing approaches.
An architecture for recycling intermediates in a column-store
76 Citations2009Milena G. Ivanova, Martin Kersten +2 more
This paper studies 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, and indicates the potentials of recycling intermediates and charters a route for further development of database kernels.
CWI's Institutional Repository (Centrum Wiskunde & Informatica)Understanding, modeling, and improving main-memory database performance
70 Citations2002Stefan Manegold
This thesis analyzes the impact of modern hardware on main-memory database performance and develops new techniques to better exploit the available hardware resources and designs detailed cost models to predict the performance behavior of database algorithms.
Data Archiving and Networked Services (DANS)What Happens During a Join? Dissecting CPU and Memory Optimization Effects
70 Citations2000Stefan Manegold, Peter Boncz +1 more
This work presents a calibration tool that automatically extracts the relevant parameters about the memory subsystem from any hardware and demonstrates how a database system equipped with this calibrator can automatically tune memory-conscious database algorithms to their optimal settings.
Elsevier eBooksBuffering Accesses to Memory-Resident Index Structures
64 Citations2003Jingren Zhou, Kenneth A. Ross
This work proposes techniques to buffer accesses to memory-resident tree-structured indexes to avoid cache thrashing, and studies several alternative designs of the buffering technique, including whether to use fixed-size or variable-sized buffers, and how to support bulk access while there are concurrent updates happening to the index.
OPAL (Open@LaTrobe) (La Trobe University)Scientific Data Management: Challenges, Technology, and Deployment
63 Citations2009Arie Shoshani, Doron Rotem
The VLDB JournalFlexible and efficient IR using array databases
51 Citations2007Roberto Cornacchia, Sándor Héman +3 more
It turns out that these optimization rules enable SRAM to automatically translate the BM25 array queries into the relational equivalent of inverted list processing including compression, score materialization and quantization, such as employed by custom-built IR systems.
UvA-DARE (University of Amsterdam)Cracking the Database Store
51 Citations2004Martin Kersten, Stefan Manegold
This work developed a small representative multi-query benchmark and ran experiments against several open-source DBMSs to study the potentials for a significant reduction in system complexity with clear performance benefits.
Elsevier eBooksSTEPS Towards Cache-Resident Transaction Processing
48 Citations2004Stavros Harizopoulos, Anastassia Ailamaki
Steps is proposed, a technique that minimizes instruction cache misses in OLTP workloads by multiplexing concurrent transactions and exploiting common code paths, and yields up to 96.7% reduction in instruction caches misses for each additional concurrent transaction.
DSM vs. NSM
48 Citations2008Marcin Żukowski, Niels Nes +1 more
This paper focuses on the CPU efficiency tradeoffs of tuple representations inside the query execution engine, while tuples flow through a processing pipeline, and analyzes the performance in the context of query engines using so-called "block-oriented" processing.
Exploiting the power of relational databases for efficient stream processing
47 Citations2009Erietta Liarou, Romulo Gonçalves +1 more
A complete architecture is proposed, the DataCell, which is implemented on top of an open-source column-oriented DBMS, which allows batch processing of tuples and selectively pick tuples from a basket based on the query requirements exploiting a novel query component, the basket expressions.
ROX
33 Citations2009Riham Abdel Kader, Peter Boncz +2 more
This research proposes to radically depart from the traditional path of separating the query compilation and query execution phases, by having the optimizer execute, materialize partial results, and use sampling based estimation techniques to observe the characteristics of intermediates.
Elsevier eBooksClotho
29 Citations2004Minglong Shao, Jiří Schindler +3 more
Clotho is a new buffer pool and storage management architecture that decouples in-memory page layout from data organization on non-volatile storage devices to enable independent data layout design at each level of the storage hierarchy.
Elsevier eBooksCache-Conscious Radix-Decluster Projections
28 Citations2004Stefan Manegold, Peter Boncz +2 more
It turns out, that the strategy of first executing the join and only afterwards dealing with the projection columns on DSM, in combination with a new finely tunable algorithm called Radix-Decluster, outperforms all previously reported projection strategies.
Spinning relations
27 Citations2009Philip W. Frey, Romulo Gonçalves +2 more
Cache-oblivious query processing
13 Citations2008Bingsheng He
This thesis presents the design, implementation, and evaluation of the first cache-oblivious, in-memory query processor, EaseDB, and shows that its cache-OBlivious algorithms achieve a performance comparable to their fine-tuned cache-conscious counterparts.
Data Archiving and Networked Services (DANS)A Query Language for a Data Refinery Cell
9 Citations2007Martin Kersten, Erietta Liarou +1 more
The DataCell provides an orthogonal extension to SQL’03, called “basket expressions”, which behave as predicate windows over multiple streams and which can be bulk processed for good resource utilization.