Source-linked AI summary
Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores
Felix Halim, Stratos Idreos, Panagiotis Karras, Roland H. C. Yap
TL;DR
Dynamic workloads leave little time for physical design and little advance knowledge of query patterns, while existing cracking can be sensitive to workload order. Stochastic cracking adds random reorganization choices to query-driven adaptation, and experiments report benefits across a wider variety of workloads. The paper also identifies initialization cost and choosing among variants as areas for further work.
Problem
Dynamic environments have scarce idle time and workload knowledge, while original cracking’s performance can deteriorate under certain query patterns.
Source: §1 · p. 1, §3 · p. 4, §7 · p. 12Method
Stochastic cracking adds random physical reorganization steps to incremental, query-driven cracking, with progressive variants sharing refinement operations across queries.
Source: §7 · p. 12Results
Stochastic cracking expands original cracking’s benefits to a much wider variety of workloads, while lighter, partial, or occasional stochastic operations do not bring equally good results.
Source: §7 · p. 12Takeaways & Limitations
The experiments support stochastic cracking as an approach that makes database cracking effective in a wider variety of scenarios.
Source: §7 · p. 12Further work includes reducing initialization cost, especially for queries that initiate workload changes, and dynamically choosing among stochastic algorithms.
Source: §6 · p. 12
Abstract
from arXiv · showhide
Modern business applications and scientific databases call for inherently dynamic data storage environments. Such environments are characterized by two challenging features: (a) they have little idle system time to devote on physical design; and (b) there is little, if any, a priori workload knowledge, while the query and data workload keeps changing dynamically. In such environments, traditional approaches to index building and maintenance cannot apply. Database cracking has been proposed as a solution that allows on-the-fly physical data reorganization, as a collateral effect of query processing. Cracking aims to continuously and automatically adapt indexes to the workload at hand, without human intervention. Indexes are built incrementally, adaptively, and on demand. Nevertheless, as we show, existing adaptive indexing methods fail to deliver workload-robustness; they perform much better with random workloads than with others. This frailty derives from the inelasticity with which these approaches interpret each query as a hint on how data should be stored. Current cracking schemes blindly reorganize the data within each query's range, even if that results into successive expensive operations with minimal indexing benefit. In this paper, we introduce stochastic cracking, a significantly more resilient approach to adaptive indexing. Stochastic cracking also uses each query as a hint on how to reorganize data, but not blindly so; it gains resilience and avoids performance bottlenecks by deliberately applying certain arbitrary choices in its decision-making. Thereby, we bring adaptive indexing forward to a mature formulation that confers the workload-robustness previous approaches lacked. Our extensive experimental study verifies that stochastic cracking maintains the desired properties of original database cracking while at the same time it performs well with diverse realistic workloads.
1. INTRODUCTION
Dynamic environments leave little time for physical design and little reliable workload knowledge, limiting traditional tuning. The paper argues that cracking’s query-driven adaptation can falter on realistic workload patterns and introduces stochastic cracking to improve robustness while retaining lightweight adaptation.
1. INTRODUCTION
- Traditional physical design assumes workload knowledge and idle time, both scarce in dynamic environments; tuning may become outdated, remain unfinished, or provide no indexing support while underway.Scientific workloads can change as new data arrives and exploratory queries follow earlier answers.Source: §1 · p. 1
- Database cracking incrementally builds and refines indexes during query processing, adapting on demand without requiring a separate indexing phase.The approach was proposed for column-stores and has been applied to selection, updates, and multi-attribute queries.Source: §1 · p. 1
- Existing cracking schemes interpret a selection as a hint to optimize its range, leaving the remaining data unindexed until later queries target it.This interpretation enables instant, lightweight adaptation but can create workload-robustness problems.Source: §1 · p. 1
- With sequential queries over consecutive ranges, cracking can repeatedly reorganize large data chunks for only minor benefit, and later queries may encounter large unindexed pieces.Such focused, exploratory access patterns occur, for example, when astronomers examine one part of the sky at a time.Source: §1 · pp. 1–2
- Exploratory queries may depend on earlier answers, making their future pattern difficult to know in advance; the paper frames robustness as maintaining performance when minor input or environmental details change.The paper describes robustness as distinct from performing every conceivable task efficiently.Source: §1 · p. 2
- Stochastic cracking adds arbitrary or random reorganization choices to query-driven cracking, while progressive cracking spreads one cracking action across multiple queries to contain overhead.Experiments report that it preserves original cracking’s benefits while extending them to a wider variety of realistic workloads.Source: §1 · p. 2
2. RELATED WORK
Offline and online tuning rely on workload analysis and can impose costs separate from, or during, query processing. Database cracking instead refines indexes incrementally as queries arrive, but its straightforward interpretation of query hints and adaptive alternatives reflect different design trade-offs.
Offline Analysis
- Offline analysis monitors workloads before choosing indexes, but requires workload knowledge and idle time, and its decisions may become invalid as workloads change.Index tuning and creation costs also affect the workload.Source: §2 · p. 2
Online Analysis
- Online analysis monitors workload and performance during query processing and may create or drop indexes after thresholds, but index creation can heavily penalize individual queries.Soft indexes reuse relevant data scans, yet full-index creation still significantly penalizes queries.Source: §2 · p. 2
Database Cracking
- Database cracking builds and refines indexes incrementally during query processing, optimizing only queried tables, columns, and key ranges.More frequent queries to a key range lead to further optimization of its representation.Source: §2 · p. 2
Selection Cracking
- Selection cracking uses a query’s predicate bounds to partition a column, so later queries can search and crack only pieces intersecting their ranges.Qualifying tuples are gathered in a contiguous area, and the reorganization occurs as part of query operators.Source: §2 · pp. 2–3
Adaptive Indexing
- Adaptive merging uses partition-and-merge logic with active sorting, while later adaptive-indexing algorithms combine insights from cracking and merging across a range of activity levels.The paper evaluates adaptive indexing against lightweight initialization and fast convergence goals.Source: §2 · p. 3
Database Cracking
- Cracking’s column-store design reorganizes referenced columns in bulk and returns a view of qualifying values in their contiguous area.Column-stores use fixed-width dense arrays and vector-wise processing.Source: §2 · p. 3
3. THE PROBLEM
Original cracking adapts continuously and can perform well on random workloads, but its improvement depends on query order. Sequential workloads can leave it touching many tuples, undermining its performance and lightweight-adaptation advantage.
Cracking Cost
- For range queries, cracking analyzes at most the two pieces intersecting the query’s range boundaries, and pieces become smaller as unmatched queries create new partitions.Reorganization cost is measured by the number of tuples touched during a select.Source: §3 · p. 3
Basic Cracking Performance
- For 108 tuples of unique integers under a completely random workload with random bounds and fixed selectivity of 10 tuples per query, Crack continuously improves performance without penalizing individual queries.Source: §3 · p. 3
Ideal and Non-ideal Workloads
- Cracking’s adaptation rate depends on query pattern and order: more prior queries can add useful structure, but performance may improve faster or slower depending on the sequence.In the idealized case, successive queries split pieces into equal halves.Source: §3 · p. 4
A Non-ideal Workload
- A sequential workload issues ranges that follow one another; with unique integer values, queries A<1, A<2, A<3, and so on cost N, N−1, N−2 comparisons, respectively.The example contrasts with an ideal first split that reduces the second query to N/2 comparisons.Source: §3 · p. 4
Basic Cracking Performance
- With sequential queries, Crack failed to outperform Scan, unlike its significant improvement after a handful of random queries; its touched-tuple count fell only negligibly rather than dropping swiftly.Sort and Scan behavior did not deviate significantly between the two tested workloads.Source: §3 · p. 4
- After 104 queries on the random workload, Sort still had not amortized its initialization overhead over Crack; on the sequential workload, Sort amortized it after 100 queries, while Crack resembled Scan for the first several thousand queries.The cumulative-response-time comparison contrasts the two workload patterns.Source: §3 · p. 4, Figure 2 · p. 4
4. STOCHASTIC CRACKING
This section presents stochastic cracking, which adds selective, data-driven randomness to query-guided reorganization to address workload fragility while retaining adaptive behavior. It also examines its behavior on real workloads and its applicability to cracking hybrids and updates.
Motivation
- Original cracking repeatedly reorganizes only query-requested ranges, reanalyzing large unindexed portions; stochastic cracking adds beneficial arbitrary actions while retaining query guidance and lightweight adaptation.Its design balances auxiliary reorganization against avoiding significant penalties to individual queries.Source: §4 · pp. 4–5
Algorithm DDC
- DDC recursively halves pieces containing requested bounds using median pivots until pieces reach a size threshold, then cracks on the bounds; an L1-cache-sized threshold performs best.It retains query-driven adaptation while adding data-driven partitions, limiting repeated-scan costs to smaller pieces.Source: §4 · pp. 5–6
Algorithms DDR and DD1C/DD1R
- DDR replaces DDC’s exact median pivots with random pivots until pieces meet a size threshold; DD1C and DD1R limit auxiliary reorganization to one operation to reduce initialization overhead.DDR avoids costly median searches, while DD1R uses one random reorganization and DD1C one center cut before ordinary query-bound cracking.Source: §4 · p. 6
Algorithm MDD1R
- MDD1R performs a random crack but skips query-bound cracking, integrating result materialization with that crack and materializing only when needed.Qualifying tuples from uncracked end pieces are materialized, while qualifying middle pieces can be returned as a view.Source: §4 · pp. 6–7, Figure 5 · p. 7
Progressive stochastic cracking
- PMDD1R further reduces initialization cost by completing random cracks over successive queries, limiting swaps per query and materializing qualifying tuples as needed.For pieces no larger than L2 cache, it switches to full MDD1R to avoid slow convergence.Source: §4 · p. 7
Selective stochastic cracking
- Selective cracking uses stochastic actions periodically with FiftyFifty or probabilistically with FlipCoin; ScrackMon triggers them when a piece’s access counter reaches a threshold.ScrackMon monitors individual pieces and applies stochastic cracking to frequently accessed areas.Source: §4 · pp. 7–8
Stochastic cracking results
- DDR and DDC avoid original cracking’s bottleneck; DD1R outperforms DD1C, while lighter DD1 variants reduce initialization cost but converge after around 10 queries.The convergence gap depends on data size: larger arrays require more queries to become sufficiently indexed.Source: §4 · p. 8
Progressive Stochastic Cracking / Naive Approaches
- Progressive Stochastic Cracking tackled the sequential workload with limited initialization overhead, whereas injecting random queries independently improved cumulative cost by one order of magnitude but did not converge even after 10^3 queries.P1% improved after 20 queries; less restrictive progressive variants converged faster. Integrated stochastic cracking gained another order of magnitude over the naive approaches and quickly reached low response times.Source: §4 · p. 9, Figure 9 · p. 9, Figure 12 · p. 9
Random Workload / Varying Selectivity
- On random workloads, Stochastic Cracking variants achieved performance similar to original cracking, with only marginally slower initialization; its sequential-workload advantage persisted across selectivities.For random workloads, the additional cumulative cost was amortized over queries; higher selectivity increased Scan and progressive-cracking costs because they materialized larger results.Source: §4 · p. 9, Figure 10 · p. 9, Figure 11 · p. 9
Adaptive Indexing Hybrids
- Adding stochastic actions to AICC and AICS let both hybrids adapt to the sequential workload and quickly converge to low response times, unlike the original partition/merge methods.AICC and AICS blindly followed the workload and were slightly slower than original cracking because of merging overhead.Source: §4 · p. 10, Figure 14 · p. 10
Various Workloads
- Across varied workloads, Stochastic Cracking remains robust while original cracking often performs significantly worse; where original cracking succeeds, Stochastic Cracking behaves similarly, with a 1.4-second disadvantage on the random workload.Original cracking loses its low-initialization-cost advantage in half the workloads and performs significantly worse than Stochastic Cracking and full indexing over the complete workload.Source: §4 · p. 10, Figure 13 · p. 10
Updates
- Stochastic Cracking maintained robust performance under interleaved updates by collecting updates as pending and merging qualifying ones during query cracking.The experiment used 10 random updates every 10 queries; the same behavior held at varying update frequencies.Source: §4 · p. 10, Figure 15 · p. 10
Stochastic Cracking on Real Workloads
- Stochastic Cracking answered 160,000 SkyServer queries in 25 seconds, versus more than 2,000 seconds for original cracking, 70 seconds for full indexing, and more than 8,000 seconds for a scan.The 4-terabyte SkyServer workload followed non-random query patterns; the tested Photoobjall table contains 500 million tuples.Source: §4 · pp. 10–11, Figure 16 · p. 11
Selective Stochastic Cracking
- Continuous Stochastic Cracking outperformed selective variants on SkyServer, while FlipCoin remained robust across workloads but was slower than pure Stochastic Cracking.FlipCoin took 35 seconds versus 62 seconds for FiftyFifty and 25 seconds for pure Stochastic Cracking; reducing stochastic-cracking frequency further degraded performance.Source: §4 · p. 11, Figure 17 · p. 11, Figure 18 · p. 11
- Monitoring individual pieces can target problematic access patterns, but increasing the query threshold before applying stochastic actions degrades performance; stopping stochastic cracking below an L1-cache-sized piece was 2–3 times slower on most workloads.The cache-threshold approach improved performance by 10–20% only on the random workload.Source: Figure 19 · p. 11, §4 · p. 11
6. FUTURE WORK
Future work spans open problems for database cracking generally and optimizations specific to stochastic cracking. The authors identify concurrency and disk-based processing challenges, alongside ways to reduce initialization costs and choose stochastic variants dynamically.
6. FUTURE WORK
- The authors distinguish open topics for cracking generally from optimizations for stochastic cracking.Source: §6 · p. 12
- Concurrency requires synchronizing physical reorganizations from concurrent queries, potentially through fine-grained locking.This remains an open topic for cracking in general.Source: §6 · p. 12
- Disk-based cracking must examine how much per-query reorganization is affordable without making disk I/O costs prohibitive.Continuous reorganization may cause continuous writes to disk.Source: §6 · p. 12
- Other open cracking topics include distribution, compression, optimization, maintenance, and performance studies across storage media.The listed media include flash disks, memory, caches, and hard disks.Source: §6 · p. 12
- Stochastic cracking could reduce initialization costs, especially for queries that initiate a workload change and incur higher costs.The authors also propose dynamically choosing among stochastic algorithms on the fly.Source: §6 · p. 12
7. CONCLUSIONS
Stochastic cracking broadens database cracking's effectiveness across workloads while retaining adaptive, incremental indexing with minimal impact on query processing. Progressive stochastic cracking shares index-refinement operations across queries to amortize their cost.
7. CONCLUSIONS
- Random physical reorganization steps address cracking's workload-robustness deficiency while still taking actual queries into account.The approach is adaptive and incremental, with minimal impact on query processing.Source: §7 · p. 12
- Stochastic cracking expands the benefits of original cracking to a much wider variety of workloads.The authors report thorough experimentation and conclude that database cracking is effective in a wider variety of scenarios.Source: §7 · p. 12
- Progressive stochastic cracking shares even one index-refinement operation among several queries to amortize its cost.Source: §7 · p. 12
- Lighter, partial, or occasional stochastic operations do not produce equally good results.Source: §7 · p. 12