Association for Computing Machinery
Database cracking is an appealing approach to adaptive indexing: on every range-selection query, the data is partitioned using the supplied predicates as pivots. The core of database cracking is, thus, pivoted partitioning. While pivoted partitioning, like scanning, requires a single pass through the data it tends to have much higher costs due to lower CPU efficiency. In this paper, the authors conduct an in-depth study of the reasons for the low CPU efficiency of pivoted partitioning. Based on the findings, they develop an optimized version with significantly higher (single-threaded) CPU efficiency.