Aarhus University Seal / Aarhus Universitets segl

Panagiotis Karras

Revisiting the theory and practice of database cracking

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review


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.

TitelAdvances in Database Technology - EDBT 2020 : 23rd International Conference on Extending Database Technology, Proceedings
RedaktørerAngela Bonifati, Yongluan Zhou, Marcos Antonio Vaz Salles, Alexander Bohm, Dan Olteanu, George Fletcher, Arijit Khan, Bin Yang
Antal sider4
ISBN (Elektronisk)9783893180837
StatusUdgivet - 2020
Begivenhed23rd International Conference on Extending Database Technology, EDBT 2020 - Copenhagen, Danmark
Varighed: 30 mar. 20202 apr. 2020


Konference23rd International Conference on Extending Database Technology, EDBT 2020
SerietitelAdvances in Database Technology - EDBT

Se relationer på Aarhus Universitet Citationsformater

ID: 187152171