Database cracking is a method to create partial indices as a side-e ect of processing queries. Cracking e ciently smears out the cost of creating a full index over a stream of queries, creating an index that is over tted to queried parts of the data. This core characteristic of cracking leads to unpredictable performance and unreliable convergence towards a full index. These problems are aggravated when considering updates and multidimensional queries. We envision a new indexing technique, Progressive Indexing that improves database cracking by strictly limiting per-query indexing cost to a budget (e.g., a user-de ned fraction of scan costs), allowing the rst and subsequent queries to complete without heavy penalties. At the same time, all indexing e ort is spent towards predictable convergence towards a full index. We discuss di erent algorithms to deal with multidimensional queries and updates while maintaining a robust and convergent index, we then explore the research space and new challenges that arise from this new technique.
Index creation is one of the major di cult decisions in
database schema design [
Automatic physical design tuning [
Adaptive indexing techniques, such as database
cracking [
However, database cracking and its variations are not robust against varying workload patterns. Since the index is only re ned in the areas targeted by the workload. Queries that deviate from them will target unre ned sections of the index, leading to large and unpredictable spikes in performance. This problem is exacerbated when dealing with updates. In case the most re ned area is also the most updated, and multidimensional queries (i.e., queries with selections in multiple columns) since one must maintain multiple indices, one for each column.
To address these needs we propose a novel approach for incremental indexes, Progressive Indexing. Where every query that is issued to the database results in a xed re nement of the index, leading to a robust query execution and full convergence towards a full index. While maintaining a low extra cost per query.
Figure 1 depicts how progressive indexing works. Considering an unindexed column, a pivot and a budget = 0:1, we start by indexing a fraction of the data while scanning the remaining 1 piece of data. After 3 queries, 30% of our column is already indexed around . The fourth query starts by performing an index lookup on the fraction of the data that has already been indexed while scanning the unindexed 1 piece and expanding the index by another fraction of the total column. Finally, after 10 queries, we fully indexed and we continue this process by selecting another .
Paper Structure. The rest of this paper is structured as follows. Section 2 provides an overview of related work. Then, section 3, describes progressive indexing. Section 4 presents a brief proof of concept and experimental analysis. Finally, in section 5, we discuss our research plan.
Automatic physical database design has been an active research eld for the past twenty years. These work resulted in two di erent areas; self-tuning tools and adaptive indexing.
Self-Tuning Tools [
Adaptive Indexing [
Database cracking has multiple issues: (1) poor convergence towards a full index, (2) ine cient tuple reconstruction, (3) unpredictable performance and (4) ine cient updates. Below we brie y discuss the research that addresses these issues.
Convergence. Hybrid cracking [
Tuple Reconstruction. Sideways cracking [
Robustness. Stochastic cracking [
Generalization. Adaptive adaptive indexing [
Updates. SPST-Index [
The previous section gave us the necessary motivation for progressive indexing. Motivated by: (1) The workload dependent pivot selection causes performance spikes and does not guarantee convergence towards a full index. (2) Cracking is not able to e ciently handle multidimensional queries since it must maintain multiple indices and intersect their points, and (3) the robustness is penalized when dealing with updates due to partial index removal and the possibility of updates being focused in re ned cracked pieces.
We propose progressive indexing. Progressive indexing is designed to be e cient when dealing with multiple types of queries and updates without sacri cing robustness or convergence. We believe that the following modi cations from adaptive indexing must be taken: (1) the pivot-selection does not need to be workload dependent, every query must have a budget to spend on indexing creation or maintenance and when an indexed piece is smaller than L1 cache it is fully ordered. (2) Progressive indexing generates a unique index for multiple columns, and (3) other sorting algorithms, besides quick-sort adaptations, are exploited in order to e ciently merge updates while maintaining robustness and convergence.
As a result of the small initial cost, progressive indexing occurs without signi cant impact on query performance and has a near-immediate return on investment over performing naive scans. Even if the column is only queried a few times, progressive indexing will still provide a performance bene t. On the other hand, if the column is queried thousands of times, the index will reliably converge towards a full index and queries will be answered at the same performance as if a full index had been built.
Single Column. Figure 3 depicts an example of progressive quick-sort. In this example, we de ne a budget = 0:5. Query Q1 starts by triggering the initialize phase from progressive quick-sort. First, it allocates an uninitialized column of the same size of the original column and then selects 9 as a pivot . The original column is scanned and n , where n is the column size, elements are copied either to the top or the bottom of the copied column, depending on the pivot, while doing so we also select the elements that ful ll Q1 predicates. A binary search tree (BST) is also formed to keep track of the pivot points. The subsequent queries can already leverage from the sorted data by performing lookups in the BST. Later, query Q2 triggers the re ne phase fully indexing the column around . Q3 then select another , and the re nement process continues until we reach a full index. The main disadvantage of progressive quick-sort is that fast convergence relies entirely on good pivot point selection. 1136 Initialize 24
Refine 12
Updates. Updates are stored in an extra vector. When a query is executed this extra column is also fully scanned. When our original column is fully sorted, we drop the BST, since we can now perform a binary search on the ordered column, and start the merging process with the column that holds the updates. To e ciently merge the updates into our original column we use progressive merge-sort. Progressive merge-sort consists of two build phases. In the rst build phase, one unsorted chunk of size n is sorted, where n is the column size and is our budget. In order to answer queries, we perform a binary search in the sorted chunks while scanning the unsorted data. In the second build phase, we merge the sorted chunks together using a cascading twoway merge. Note that we do not necessarily complete a full merge in one query, as this would result in large drops in performance when we merge two large chunks together. Instead, we merge at most n 2 elements and keep track of how far along the merge we are. After a merge is completed, we replace the two original chunks with the merged chunk. Figure 4 depicts the progressive merge-sort algorithm with = 0:5, in the rst phase half the column is ordered in a chunk. The second phase orders the remaining of the column in another chunk and nally both chunks are merged resulting in a fully ordered column. The main disadvantage of merge-sort is that while we have many sorted chunks, we are performing many random accesses, as we are doing a full binary search in each of the 1= chunks.
Multi-column. We adapt progressive quick-sort to work with multidimensional queries by generating a KD-Tree on top of the columns. In a KD-Tree every level of the tree consists of only one column. To maintain this property we interleave our pivots through the columns. Multidimensional progressive quick-sort can be visualized in gure 5. For simplicity in our example we set = 1 (i.e., every iteration fully indexes one pivot). In the rst iteration we select a = 3 to use as a pivot for column X. Since our = 1 at the end of the rst query, we will have fully copied the columns and fully indexed the column X around 3, while keeping the alignment with column Y . A KD-Tree is then created to keep track of the indexed pivot. Later, when Q2 is executed it triggers another iteration of progressive indexing. However, this time we are going to reorder the column Y over a new = 5. Since we have already indexed X on 3, we need to reorder Y in the two pieces of X to maintain the alignment.T he main disadvantage of multidimensional progressive quicksort is that it does not provide progressive usage of space, after fully indexing the rst pivot, we have already made full copies of all the columns.
In this section, we present a brief experimental analysis to demonstrate the strong potential bene ts of progressive indexing.
Setup. We implemented progressive quick-sort in a standalone program written in C++ and optimized using level 3. All experiments were conducted on a machine running Fedora 26, with an Intel Core i7-2600K CPU @ 3.40 GHz with 8 cores, 16 GB of main memory and 8192 KB L3 cache size.
We use an 8-byte integer array with 108 uniformly distributed values as our dataset. All queries are of the form: SELECT SUM(R.A) FROM R WHERE R.A BETWEEN V1 AND V2. All the queries have selectivity equal to 0.1 and we de ne our budget = 0:1. All the progressive quick-sort pivots are randomly selected.
In Figure 6 we depict the per-query performance evaluation of progressive quick-sort, database cracking, stochastic cracking, coarse-granular index (i.e., a stochastic cracking variant), a B+tree as a full index and column scans. We can observe that adaptive indexing techniques show a very ) ) s (g 1.0 o l ( e m i TScan y r e u Q Index 0 100
300 200
Query (#) volatile performance with much more spikes throughout our query stream. This is due to the index re ned by the workload. One can observe that progressive quick-sort has a more robust performance but still presents performance spikes due to the partial index creation depending entirely on the pivot selection. Additionally one can observe that progressive quick-sort converges to a full index around query 120, whereas the adaptive index techniques never converge.
Progressive indexing introduces new aspects that were unexplored by adaptive indexing and that require further investigation. We envision, as our ultimate goal, the creation of a formal cost-model with a decision tree that is able to choose and interleave from di erent progressive indexes. In order to optimize the query response time without penalizing robustness or convergence. We describe the following as the aspects that shall be explored:
Sorting-algorithms. We discussed two di erent algorithms adapted to work as progressive indexes. However, many other well-known algorithms (e.g., radixsort, bucket-sort, heap-sort) can be adapted to work in a progressive fashion as well.
Pivot-selection. Some sorting algorithms (e.g.,
quicksort) require a good pivot point selection. Di erent
strategies can be applied to select a pivot. It can
be workload dependent, data dependent, completely
random or even a mix from all of the above;
Data Structure. Di erent data structures can be
used to exploit modern processes and boost access to
the ordered data, like the ART-tree [
We point out the following as the research steps that we will follow in the next coming years: 1. Adapt other sorting algorithms to work progressively and analyze their advantages and disadvantages de ning a cost-model with a decision tree to unify all solutions; 6.