Adaptive Physical Design for Dynamic Database Workloads

187 concepts148 papers1 proposal

Traditional database systems operate under a comfortable assumption: tomorrow’s queries will look exactly like yesterday’s. In this static paradigm, a database administrator (DBA) or an automated tool analyzes a representative workload log, runs a heavy optimization routine, and deploys a fixed set of indexes and data partitions.

This approach breaks down in modern cloud environments, exploratory data analysis, and real-time applications. Real-world workloads are volatile, ad-hoc, and non-stationary. When query patterns drift, a rigid physical design transforms from a performance accelerator into a severe bottleneck.

To solve this, researchers have shifted toward adaptive physical design—building database engines that continuously reorganize their internal layouts, indexes, and storage structures on-the-fly in response to live query traffic.

The Cost of Rigidity

Why do static designs fail when workloads fluctuate? The core issue is that traditional optimization is a one-time compilation step detached from runtime execution feedback.

Early work by Ming-Syan Chen et al. in On Index Selection Schemes for Nested Object Hierarchies highlighted that relying on a predefined, static workload profile prevents a database from adjusting to evolving query patterns. As Sunita Sarawagi notes in Letter from the VLDB 2011 Research Track Co-Chair, this structural rigidity forces manual intervention and blocks incremental optimization. If user interest shifts to a different column or data range, existing indexes become obsolete, and the engine must revert to slow, exhaustive full-table scans.

In modern cloud settings, this mismatch is amplified. As R. Malinga Perera et al. observe in DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees, traditional physical design tools are fundamentally incompatible with ad-hoc, non-stationary analytical workloads because they lack real-time execution feedback. Without the ability to observe actual performance and adapt dynamically, the system cannot optimize for the true data distributions and access patterns it encounters.

Mechanism 1: Database Cracking (Just-in-Time Indexing)

One of the most intuitive mechanisms for dynamic adaptation is database cracking. Instead of building indexes upfront or during batch updates, a cracking engine physically reorganizes data incrementally as a direct byproduct of query processing.

Martin L. Kersten introduces this paradigm in Database Cracking, showing how a database can "learn" a workload purely through execution. When a query requests a specific range of values (e.g., WHERE constant1 < A < constant2), the engine uses those constants as pivots to physically partition the column array.

Initial State (Unordered):
[ 42, 12, 89, 5, 67, 23, 51 ]

Query: WHERE A < 30
The engine uses '30' as a pivot to "crack" the array on-the-fly:
[ 12, 5, 23 | 42, 89, 67, 51 ]
            ^ Pivot point (Index piece created)

As more queries arrive, the data array becomes increasingly fragmented and sorted around the exact ranges users care about. As Fatemeh Zardbani et al. demonstrate in Revisiting the Theory and Practice of Database Cracking, this deferred data structuring avoids massive upfront index construction costs and naturally matches the granularity of user interest.

This concept has expanded beyond traditional relational tables into complex data types. For example, Vasilis Mageirakos et al. apply this to high-dimensional vector spaces in Cracking Vector Search Indexes. Rather than constructing a global vector index based on the entire dataset, their approach refines the index structure incrementally within frequently queried regions of the vector space, bypassing massive initialization latencies.

Mechanism 2: Continuous Learning and Reinforcement Learning

While database cracking is a passive byproduct of queries, modern adaptive systems also use active machine learning to forecast workload shifts and reconfigure physical structures.

Andrew Pavlo et al. outline this vision in Self-Driving Database Management Systems, proposing an architecture that integrates deep learning for workload forecasting with control models for action planning. By predicting upcoming transitions—such as a shift from transactional (OLTP) to analytical (OLAP) processing—the system can plan non-disruptive physical layout changes.

To handle environments where internal cost models are inaccurate, R. Malinga Perera et al. leverage contextual multi-armed bandits (MAB) in No DBA? No Regret! Multi-Armed Bandits for Index Tuning of Analytical and HTAP Workloads With Provable Guarantees. By learning directly from actual query execution times rather than fallible optimizer estimates, their framework dynamically tunes indexes while providing provable "no-regret" safety guarantees.

+-------------------------------------------------------------+
|                      Database Engine                        |
|  +------------------+                 +------------------+  |
|  |  Physical Layout |                 |  Query Execution |  |
|  |  (LSM/Indexes)   |                 |  (Live Traffic)  |  |
|  +--------+---------+                 +--------+---------+  |
+-----------|------------------------------------|------------+
            |                                    |
    Adjusts | Compaction /                       | Observes
    Layout  | Indexing Actions                   | Performance
            |                                    v
+-----------+------------------------------------+------------+
|  |  Reinforcement Learning / Bandit Agent             |     |
|  |  Evaluates state and rewards based on execution    |     |
|  +----------------------------------------------------+     |
|                     Feedback Loop                           |
+-------------------------------------------------------------+

This active learning extends down to low-level storage engine mechanics. In Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads, Dingheng Mo et al. demonstrate how reinforcement learning can optimize Log-Structured Merge (LSM) tree compaction policies on the fly. When the workload swings between write-heavy insertions and read-heavy queries, the RL agent dynamically alters compaction behavior to balance read amplification against write stall risks, maintaining stability without human intervention.

Mechanism 3: Dynamic Data Partitioning and Layout Reconfiguration

Adaptive physical design also dictates how data is distributed across storage blocks or cluster nodes. Statically partitioned systems suffer from severe network and CPU bottlenecks when query patterns shift.

As Katja Hose et al. point out in Partout: a distributed engine for efficient RDF processing, partitioning schemes that rely on static historical logs degrade quickly if user access patterns evolve, leading to misaligned data placement and high cross-node network overhead.

To maintain high performance, storage engines must support low-overhead, real-time layout adjustments. Martin Grund et al. address this in An overview of HYRISE - a Main Memory Hybrid Storage Engine by utilizing a cache-aware cost model to automatically partition database tables into vertical "containers" of varying widths, dynamically restructuring the layout for mixed workloads.

Similarly, Badrish Chandramouli et al. introduce the qd-tree in Qd-tree: Learning Data Layouts for Big Data Analytics. This framework uses deep reinforcement learning to learn workload-aware data layouts that route records into storage blocks tailored to specific query expressions, maximizing data skipping and minimizing the data volume scanned during analytical operations.

Why It Works: Amortized Adaptation

The core intuition behind why adaptive physical design works lies in the concept of amortization.

Traditional systems treat physical design as an expensive, global compilation step. If a database has to build a B-tree index or re-partition a multi-terabyte table, it must lock resources and perform a massive batch operation. This creates a high barrier to adaptation, making the system highly sensitive to workload drift.

Adaptive physical design converts this heavy batch cost into a continuous control loop. By embedding small, localized structural adjustments directly into query execution (as seen in database cracking) or running lightweight background optimization agents (such as reinforcement learning and multi-armed bandits), the system shifts the cost of data reorganization to match the exact utility of the queries.

If a specific region of data or a particular column is never queried, the system spends zero cycles indexing or partitioning it. If a region suddenly becomes a hot spot, the system incrementally refines its layout. This ensures that the database's physical structure naturally mirrors the localized density, skew, and volatility of the actual workload, achieving near-optimal performance without the overhead of global, static recalculations.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_workload_adaptation_static_workl_70f34ca6,
  title = {dynamic workload adaptation (static workload assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-workload-adaptation-static-workload-assumption/rdr_70f34ca6bd31479bbc6657d25d5ce537},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_dynamic_workload_adaptation_static_workl_70f34ca6_v1,
  title = {dynamic workload adaptation (static workload assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-workload-adaptation-static-workload-assumption/rdr_70f34ca6bd31479bbc6657d25d5ce537/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake