Revisiting the theory and practice of database cracking

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

DOI

Database cracking (DBC) provides an adaptive data storage environment that meets the needs of modern applications in business and science, reorganizing data on demand and adapting indexes on the fly, automatically, and collaterally to query processing. Despite intensive research on cracking and other adaptive indexing variants, their theoretical side has scarcely been investigated. Yet, quite surprisingly, as we show, an antecedent of database cracking in a pure, no-frills form had been developed in the theory community 24 years ahead of its time by the name of deferred data structuring (DDS). While lacking system implementations, DDS corresponds to what we would call, by the terminology used in the database community, materialization-based data-driven center cracking for point lookup queries, as well as a stochastic variant thereof. Further, DDS has gone beyond regular cracking proposals by suggesting a policy that reorganizes index ranges along the median of a sample set, i.e., a mediocre element. In this paper, we reanalyze state-of-the-art database cracking algorithms with the benefit of hindsight provided by deferred data structuring, and propose new alternatives that use a mediocre element as cracking pivot instead of a random or a median one. In a thorough experimental study, we determine that a logarithmic or linear sample size yields best performance on a standard benchmark across the board of cracking algorithms.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2020 : 23rd International Conference on Extending Database Technology, Proceedings
EditorsAngela Bonifati, Yongluan Zhou, Marcos Antonio Vaz Salles, Alexander Bohm, Dan Olteanu, George Fletcher, Arijit Khan, Bin Yang
Number of pages4
Publisheropenproceedings.org
Publication year2020
Pages415-418
ISBN (Electronic)9783893180837
DOIs
Publication statusPublished - 2020
Event23rd International Conference on Extending Database Technology, EDBT 2020 - Copenhagen, Denmark
Duration: 30 Mar 20202 Apr 2020

Conference

Conference23rd International Conference on Extending Database Technology, EDBT 2020
LandDenmark
ByCopenhagen
Periode30/03/202002/04/2020
SeriesAdvances in Database Technology - EDBT
Volume2020-March

See relations at Aarhus University Citationformats

ID: 187152171