An experimental evaluation and analysis of database cracking
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/106180 |
| _version_ | 1826191839942672384 |
|---|---|
| author | Schuhknecht, Felix Martin Jindal, Alekh Dittrich, Jens |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Schuhknecht, Felix Martin Jindal, Alekh Dittrich, Jens |
| author_sort | Schuhknecht, Felix Martin |
| collection | MIT |
| description | 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. Our 2014 VLDB paper “The Uncracked Pieces in Database Cracking” (PVLDB 7:97–108, 2013/VLDB 2014) was the first comparative study of these different methods by an independent group. In this article, we extend our published experimental study on database cracking and bring it to an up-to-date state. 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. Additionally to our conference paper, we now also look at a recently published study about CPU efficiency (predication cracking). We evaluate these works and show possible directions to do even better. As a further extension, we evaluate the whole class of parallel cracking algorithms that were proposed in three recent works. Altogether, in this work we revisit 8 papers on database cracking and evaluate in total 18 cracking methods, 6 sorting algorithms, and 3 full index structures. Additionally, we test cracking under a variety of experimental settings, including high selectivity (Low selectivity means that many entries qualify. Consequently, a high selectivity means, that only few entries qualify) queries, low selectivity queries, varying selectivity, and multiple query access patterns. Finally, we compare cracking against different sorting algorithms as well as against different main memory optimized indexes, including the recently proposed adaptive radix tree (ART). Our results show that: (1) the previously proposed cracking algorithms are repeatable, (2) there is still enough room to significantly improve the previously proposed cracking algorithms, (3) parallelizing cracking algorithms efficiently is a hard task, (4) cracking depends heavily on query selectivity, (5) cracking needs to catch up with modern indexing trends, and (6) different indexing algorithms have different indexing signatures. |
| first_indexed | 2024-09-23T09:02:05Z |
| format | Article |
| id | mit-1721.1/106180 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:02:05Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1061802022-09-30T12:59:20Z An experimental evaluation and analysis of database cracking Schuhknecht, Felix Martin Jindal, Alekh Dittrich, Jens Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Jindal, Alekh 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. Our 2014 VLDB paper “The Uncracked Pieces in Database Cracking” (PVLDB 7:97–108, 2013/VLDB 2014) was the first comparative study of these different methods by an independent group. In this article, we extend our published experimental study on database cracking and bring it to an up-to-date state. 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. Additionally to our conference paper, we now also look at a recently published study about CPU efficiency (predication cracking). We evaluate these works and show possible directions to do even better. As a further extension, we evaluate the whole class of parallel cracking algorithms that were proposed in three recent works. Altogether, in this work we revisit 8 papers on database cracking and evaluate in total 18 cracking methods, 6 sorting algorithms, and 3 full index structures. Additionally, we test cracking under a variety of experimental settings, including high selectivity (Low selectivity means that many entries qualify. Consequently, a high selectivity means, that only few entries qualify) queries, low selectivity queries, varying selectivity, and multiple query access patterns. Finally, we compare cracking against different sorting algorithms as well as against different main memory optimized indexes, including the recently proposed adaptive radix tree (ART). Our results show that: (1) the previously proposed cracking algorithms are repeatable, (2) there is still enough room to significantly improve the previously proposed cracking algorithms, (3) parallelizing cracking algorithms efficiently is a hard task, (4) cracking depends heavily on query selectivity, (5) cracking needs to catch up with modern indexing trends, and (6) different indexing algorithms have different indexing signatures. Germany. Federal Ministry of Education and Research 2016-12-29T20:48:43Z 2016-12-29T20:48:43Z 2015-08 2015-05 2016-08-18T15:28:38Z Article http://purl.org/eprint/type/JournalArticle 1066-8888 0949-877X http://hdl.handle.net/1721.1/106180 Schuhknecht, Felix Martin, Alekh Jindal, and Jens Dittrich. “An Experimental Evaluation and Analysis of Database Cracking.” The VLDB Journal 25.1 (2016): 27–52. en http://dx.doi.org/10.1007/s00778-015-0397-y The VLDB Journal Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag Berlin Heidelberg application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Schuhknecht, Felix Martin Jindal, Alekh Dittrich, Jens An experimental evaluation and analysis of database cracking |
| title | An experimental evaluation and analysis of database cracking |
| title_full | An experimental evaluation and analysis of database cracking |
| title_fullStr | An experimental evaluation and analysis of database cracking |
| title_full_unstemmed | An experimental evaluation and analysis of database cracking |
| title_short | An experimental evaluation and analysis of database cracking |
| title_sort | experimental evaluation and analysis of database cracking |
| url | http://hdl.handle.net/1721.1/106180 |
| work_keys_str_mv | AT schuhknechtfelixmartin anexperimentalevaluationandanalysisofdatabasecracking AT jindalalekh anexperimentalevaluationandanalysisofdatabasecracking AT dittrichjens anexperimentalevaluationandanalysisofdatabasecracking AT schuhknechtfelixmartin experimentalevaluationandanalysisofdatabasecracking AT jindalalekh experimentalevaluationandanalysisofdatabasecracking AT dittrichjens experimentalevaluationandanalysisofdatabasecracking |