The uncracked pieces in database cracking

Abstract

Database cracking has been an area of active research in recent years. The core idea of database cracking is to create indexes adaptively and incrementally as a side-product of query processing. Several works have proposed different cracking techniques for different aspects including updates, tuple-reconstruction, convergence, concurrency-control, and robustness. However, there is a lack of any comparative study of these different methods by an independent group. In this paper, we conduct an experimental study on database cracking. Our goal is to critically review several aspects, identify the potential, and propose promising directions in database cracking. With this study, we hope to expand the scope of database cracking and possibly leverage cracking in database engines other than MonetDB.

We repeat several prior database cracking works including the core cracking algorithms as well as three other works on convergence (hybrid cracking), tuple-reconstruction (sideways cracking), and robustness (stochastic cracking) respectively. We evaluate these works and show possible directions to do even better. We further test cracking under a variety of experimental settings, including high selectivity queries, low selectivity queries, and multiple query access patterns. Finally, we compare cracking against different sorting algorithms as well as against different main-memory optimised indexes, including the recently proposed Adaptive Radix Tree (ART). Our results show that: (i) the previously proposed cracking algorithms are repeatable, (ii) there is still enough room to significantly improve the previously proposed cracking algorithms, (iii) cracking depends heavily on query selectivity, (iv) cracking needs to catch up with modern indexing trends, and (v) different indexing algorithms have different indexing signatures.

References

1. Generalized Heap Implementation. https://github.com/valyala/gheap.
2. O. R. Birkeland. Searching Large Data Volumes with MISD Processing. PhD thesis.
3. T. Finch. Incremental calculation of weighted mean and variance. University of Cambridge Computing Service, 2009.
4. G. Graefe, F. Halim, S. Idreos, et al. Concurrency Control for Adaptive Indexing. In PVLDB, pages 656--667, 2012.
5. G. Graefe and H. Kuno. Self-selecting, Self-tuning, Incrementally Optimized Indexes. In EDBT, pages 371--381, 2010.
6. F. Halim, S. Idreos, et al. Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores. In PVLDB, pages 502--513, 2012.
7. P. Hildebrandt and H. Isbitz. Radix Exchange - An Internal Sorting Method for Digital Computers. J. ACM, pages 156--163, 1959.
8. S. Idreos et al. Database Cracking. In CIDR, pages 68--78, 2007.
9. S. Idreos, M. Kersten, et al. Self-organizing Tuple Reconstruction In Column-stores. In SIGMOD, pages 297--308, 2009.
10. S. Idreos, M. Kersten, and S. Manegold. Updating a Cracked Database. In SIGMOD, pages 413--424, 2007.
11. S. Idreos, S. Manegold, H. Kuno, and G. Graefe. Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores. In PVLDB, pages 585--597, 2011.
12. A. Jindal, E. Palatinus, V. Pavlov, and J. Dittrich. A Comparison of Knives for Bread Slicing. In PVLDB, pages 361--372, 2013.
13. M. Kersten et al. Cracking the Database Store. In CIDR, pages 213--224, 2005.
14. C. Kim et al. FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs. In SIGMOD, pages 339--350, 2010.
15. V. Leis et al. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. In ICDE, pages 38--49, 2013.
16. X. Martinez-Palau, D. Dominguez-Sal, and J. L. Larriba-Pey. Two-way Replacement Selection. In PVLDB, pages 871--881, 2010.
17. J. Rao and K. A. Ross. Making B+-Trees Cache Conscious in Main Memory. In SIGMOD, pages 475--486, 2000.