No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees

• URL: http://arxiv.org/abs/2108.10130v1
• Date: Mon, 23 Aug 2021 12:54:48 GMT
• Title: No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees
• Abstract summary: We propose a self-driving approach to online index selection that eschews the DBA and query optimiser. We view the problem as one of sequential decision making under uncertainty. Our solution provides up to 59% speed-up on shifting and 51% speed-up on static workloads.
• Score: 9.965853054511163
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Automating physical database design has remained a long-term interest in database research due to substantial performance gains afforded by optimised structures. Despite significant progress, a majority of today's commercial solutions are highly manual, requiring offline invocation by database administrators (DBAs) who are expected to identify and supply representative training workloads. Even the latest advancements like query stores provide only limited support for dynamic environments. This status quo is untenable: identifying representative static workloads is no longer realistic; and physical design tools remain susceptible to the query optimiser's cost misestimates. Furthermore, modern application environments such as hybrid transactional and analytical processing (HTAP) systems render analytical modelling next to impossible. We propose a self-driving approach to online index selection that eschews the DBA and query optimiser, and instead learns the benefits of viable structures through strategic exploration and direct performance observation. We view the problem as one of sequential decision making under uncertainty, specifically within the bandit learning setting. Multi-armed bandits balance exploration and exploitation to provably guarantee average performance that converges to policies that are optimal with perfect hindsight. Our comprehensive empirical evaluation against a state-of-the-art commercial tuning tool demonstrates up to 75% speed-up on shifting and ad-hoc workloads and up to 28% speed-up on static workloads in analytical processing environments. In HTAP environments, our solution provides up to 59% speed-up on shifting and 51% speed-up on static workloads. Furthermore, our bandit framework outperforms deep reinforcement learning (RL) in terms of convergence speed and performance volatility (providing up to 58% speed-up).

Related papers

• CAST: Critique-Aware Supervision for Training Reliable Long-Horizon Tool-Calling Agents [66.9575676266637]
  Large language model (LLM) agents are increasingly deployed in long-horizon, interactive, and stateful environments.<n>In these settings, a single wrong action, such as refunding the wrong purchase, can cause irreversible task failure and must be intercepted before execution.<n>We develop CAST, a critique-aware training framework that converts sparse task outcomes into action-level supervision for critique learning and policy optimization.
  arXiv  Detail & Related papers  (2026-08-31T01:59:51Z)
• A Comparative Study of Bayesian Contextual Bandits for Real-Time Warehouse Sorter Optimization [1.8807636852384417]
  In this study, we use an inbound receiving sorter at a high-volume e-commerce warehouse as our primary use case.<n>To address this real-time sorter diversion optimization challenge, we conducted a comparative study of three candidate hybrid machine learning frameworks.<n>Our results demonstrate that while tree-based reward models offer slightly better predictive power, the BCB framework achieved overall higher performance with 2.03% reward uplift over the baseline.
  arXiv  Detail & Related papers  (2026-06-22T22:07:36Z)
• DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents [11.212756680882444]
  We introduce textbfDynaSchedBench, a diagnostic framework for DFJSP that rigorously controls the instance-generation process.<n>Instead of relying on parameter sampling, our approach utilizes Sequential Event-Space Calibrator (SESC) that computes a novel Schedule Stress Index (SSI) to stratify instances by difficulty.
  arXiv  Detail & Related papers  (2026-05-26T18:36:54Z)
• AgentOpt v0.1 Technical Report: Client-Side Optimization for LLM-Based Agent [18.58248061903799]
  We introduce AgentOpt, the first framework-agnostic Python package for client-side AI optimization.<n>We first study model selection, a high-impact optimization lever in multi-step agent pipelines.<n>To efficiently explore the exponentially growing combination space, AgentOpt implements ten search algorithms.
  arXiv  Detail & Related papers  (2026-04-07T17:13:47Z)
• Dynamic analysis enhances issue resolution [53.50448142467294]
  DAIRA (Dynamic Analysis-enhanced Issue Resolution Agent) is an automated repair framework that embeds dynamic analysis into the agent's reasoning cycle.<n> Driven by a Test Tracing-Driven methodology, DAIRA utilizes lightweight monitors to extract critical runtime data.<n>When powered by Gemini 3 Flash Preview, DAIRA establishes a new state-of-the-art (SOTA) performance, achieving a 79.4% resolution rate on the SWE-bench Verified dataset.
  arXiv  Detail & Related papers  (2026-03-23T14:48:54Z)
• EmboCoach-Bench: Benchmarking AI Agents on Developing Embodied Robots [68.29056647487519]
  Embodied AI is fueled by high-fidelity simulation and large-scale data collection.<n>However, this scaling capability remains bottlenecked by a reliance on labor-intensive manual oversight.<n>We introduce textscEmboCoach-Bench, a benchmark evaluating the capacity of LLM agents to autonomously engineer embodied policies.
  arXiv  Detail & Related papers  (2026-01-29T11:33:49Z)
• ROAD: Reflective Optimization via Automated Debugging for Zero-Shot Agent Alignment [1.6968020497268546]
  ROAD is a novel framework that treats optimization as a dynamic debug investigation rather than a search.<n>Road is highly sample-efficient, achieving a 5.6 percent increase in success rate and a 3.8 percent increase in search accuracy.<n>These findings suggest that mimicking the human engineering loop of failure analysis and patching offers a viable, data-efficient alternative to resource-intensive training.
  arXiv  Detail & Related papers  (2025-12-30T07:31:34Z)
• Towards High Data Efficiency in Reinforcement Learning with Verifiable Reward [54.708851958671794]
  We propose a Data-Efficient Policy Optimization pipeline that combines optimized strategies for both offline and online data selection.<n>In offline phase, we curate a high-quality subset of training samples based on diversity, influence, and appropriate difficulty.<n>During online RLVR training, we introduce a sample-level explorability metric to dynamically filter samples with low exploration potential.
  arXiv  Detail & Related papers  (2025-09-01T10:04:20Z)
• OmniEAR: Benchmarking Agent Reasoning in Embodied Tasks [52.87238755666243]
  We present OmniEAR, a framework for evaluating how language models reason about physical interactions, tool usage, and multi-agent coordination in embodied tasks.<n>We model continuous physical properties and complex spatial relationships across 1,500 scenarios spanning household and industrial domains.<n>Our systematic evaluation reveals severe performance degradation when models must reason from constraints.
  arXiv  Detail & Related papers  (2025-08-07T17:54:15Z)
• The Cost of Dynamic Reasoning: Demystifying AI Agents and Test-Time Scaling from an AI Infrastructure Perspective [3.0868637098088403]
  Large-language-model (LLM)-based AI agents have recently showcased impressive versatility by employing dynamic reasoning.<n>This paper presents the first comprehensive system-level analysis of AI agents, quantifying their resource usage, latency behavior, energy consumption, and test-time scaling strategies.<n>Our findings reveal that while agents improve accuracy with increased compute, they suffer from rapidly diminishing returns, widening latency variance, and unsustainable infrastructure costs.
  arXiv  Detail & Related papers  (2025-06-04T14:37:54Z)
• Win Fast or Lose Slow: Balancing Speed and Accuracy in Latency-Sensitive Decisions of LLMs [48.653022530291494]
  Large language models (LLMs) have shown remarkable performance across diverse reasoning and generation tasks.<n>This work presents the first systematic study of this latency quality trade off in real time decision making tasks.<n>We propose FPX, an adaptive framework that dynamically selects model size and quantization level based on real time demands.
  arXiv  Detail & Related papers  (2025-05-26T04:03:48Z)
• AegisLLM: Scaling Agentic Systems for Self-Reflective Defense in LLM Security [74.22452069013289]
  AegisLLM is a cooperative multi-agent defense against adversarial attacks and information leakage. We show that scaling agentic reasoning system at test-time substantially enhances robustness without compromising model utility. Comprehensive evaluations across key threat scenarios, including unlearning and jailbreaking, demonstrate the effectiveness of AegisLLM.
  arXiv  Detail & Related papers  (2025-04-29T17:36:05Z)
• Thinking Longer, Not Larger: Enhancing Software Engineering Agents via Scaling Test-Time Compute [61.00662702026523]
  We propose a unified Test-Time Compute scaling framework that leverages increased inference-time instead of larger models.<n>Our framework incorporates two complementary strategies: internal TTC and external TTC.<n>We demonstrate our textbf32B model achieves a 46% issue resolution rate, surpassing significantly larger models such as DeepSeek R1 671B and OpenAI o1.
  arXiv  Detail & Related papers  (2025-03-31T07:31:32Z)
• How Robust Are Router-LLMs? Analysis of the Fragility of LLM Routing Capabilities [62.474732677086855]
  Large language model (LLM) routing has emerged as a crucial strategy for balancing computational costs with performance. We propose the DSC benchmark: Diverse, Simple, and Categorized, an evaluation framework that categorizes router performance across a broad spectrum of query types.
  arXiv  Detail & Related papers  (2025-03-20T19:52:30Z)
• DARS: Dynamic Action Re-Sampling to Enhance Coding Agent Performance by Adaptive Tree Traversal [55.13854171147104]
  Large Language Models (LLMs) have revolutionized various domains, including natural language processing, data analysis, and software development. We present Dynamic Action Re-Sampling (DARS), a novel inference time compute scaling approach for coding agents. We evaluate our approach on SWE-Bench Lite benchmark, demonstrating that this scaling strategy achieves a pass@k score of 55% with Claude 3.5 Sonnet V2.
  arXiv  Detail & Related papers  (2025-03-18T14:02:59Z)
• Microservices-Based Framework for Predictive Analytics and Real-time Performance Enhancement in Travel Reservation Systems [1.03590082373586]
  The paper presents a framework of architecture dedicated to enhancing the performance of real-time travel reservation systems. Our framework includes real-time predictive analytics, through machine learning models, that optimize forecasting customer demand, dynamic pricing, as well as system performance. Future work will be an investigation of advanced AI models and edge processing to further improve the performance and robustness of the systems employed.
  arXiv  Detail & Related papers  (2024-12-20T07:19:42Z)
• Adaptive Stream Processing on Edge Devices through Active Inference [5.5676731834895765]
  We present a novel Machine Learning paradigm based on Active Inference (AIF) AIF describes how the brain constantly predicts and evaluates sensory information to decrease long-term surprise. Our method guarantees full transparency on the decision making, making the interpretation of the results and the troubleshooting effortless.
  arXiv  Detail & Related papers  (2024-09-26T15:12:41Z)
• Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents [44.34340798542]
  Large Language Models (LLMs) have shown remarkable capabilities in natural language tasks requiring complex reasoning. Traditional supervised pre-training on static datasets falls short in enabling autonomous agent capabilities. We propose a framework that combines guided Monte Carlo Tree Search (MCTS) search with a self-critique mechanism and iterative fine-tuning on agent interactions.
  arXiv  Detail & Related papers  (2024-08-13T20:52:13Z)
• Controllable Prompt Tuning For Balancing Group Distributional Robustness [53.336515056479705]
  We introduce an optimization scheme to achieve good performance across groups and find a good solution for all without severely sacrificing performance on any of them. We propose Controllable Prompt Tuning (CPT), which couples our approach with prompt-tuning techniques. On spurious correlation benchmarks, our procedures achieve state-of-the-art results across both transformer and non-transformer architectures, as well as unimodal and multimodal data.
  arXiv  Detail & Related papers  (2024-03-05T06:23:55Z)
• Sibyl: Forecasting Time-Evolving Query Workloads [9.16115447503004]
  Database systems often rely on historical query traces to perform workload-based performance tuning. Real production workloads are time-evolving, making historical queries ineffective for optimizing future workloads. We propose SIBYL, an end-to-end machine learning-based framework that accurately forecasts a sequence of future queries.
  arXiv  Detail & Related papers  (2024-01-08T08:11:32Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  This work pioneers an exploration into the critical role of dataset characteristics for DARTS bi-level optimization. We introduce a new progressive data pruning strategy that utilizes supernet prediction dynamics as the metric. Comprehensive evaluations on the NAS-Bench-201 search space, DARTS search space, and MobileNet-like search space validate that BDP reduces search costs by over 50%.
  arXiv  Detail & Related papers  (2023-12-21T02:48:44Z)
• Towards General and Efficient Online Tuning for Spark [55.30868031221838]
  We present a general and efficient Spark tuning framework that can deal with the three issues simultaneously. We have implemented this framework as an independent cloud service, and applied it to the data platform in Tencent.
  arXiv  Detail & Related papers  (2023-09-05T02:16:45Z)
• Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with Online Learning [60.17407932691429]
  Open Radio Access Network systems, with their base stations (vBSs), offer operators the benefits of increased flexibility, reduced costs, vendor diversity, and interoperability. We propose an online learning algorithm that balances the effective throughput and vBS energy consumption, even under unforeseeable and "challenging'' environments. We prove the proposed solutions achieve sub-linear regret, providing zero average optimality gap even in challenging environments.
  arXiv  Detail & Related papers  (2023-09-04T17:30:21Z)
• Mastering the Unsupervised Reinforcement Learning Benchmark from Pixels [112.63440666617494]
  Reinforcement learning algorithms can succeed but require large amounts of interactions between the agent and the environment. We propose a new method to solve it, using unsupervised model-based RL, for pre-training the agent. We show robust performance on the Real-Word RL benchmark, hinting at resiliency to environment perturbations during adaptation.
  arXiv  Detail & Related papers  (2022-09-24T14:22:29Z)
• Federated Learning with Unreliable Clients: Performance Analysis and Mechanism Design [76.29738151117583]
  Federated Learning (FL) has become a promising tool for training effective machine learning models among distributed clients. However, low quality models could be uploaded to the aggregator server by unreliable clients, leading to a degradation or even a collapse of training. We model these unreliable behaviors of clients and propose a defensive mechanism to mitigate such a security risk.
  arXiv  Detail & Related papers  (2021-05-10T08:02:27Z)
• DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees [14.913550078203448]
  Physical database design has remained a long-term interest in database research. Recent advancements like query stores provide only limited support for dynamic environments. We propose a self-driving approach to online index selection that eschews the DBA and query optimiser.
  arXiv  Detail & Related papers  (2020-10-19T04:24:10Z)
• GOAT: GPU Outsourcing of Deep Learning Training With Asynchronous Probabilistic Integrity Verification Inside Trusted Execution Environment [0.0]
  Machine learning models based on Deep Neural Networks (DNNs) are increasingly deployed in a range of applications ranging from self-driving cars to COVID-19 treatment discovery. To support the computational power necessary to learn a DNN, cloud environments with dedicated hardware support have emerged as critical infrastructure. Various approaches have been developed to address these challenges, building on trusted execution environments (TEE)
  arXiv  Detail & Related papers  (2020-10-17T20:09:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.