BQSched: A Non-intrusive Scheduler for Batch Concurrent Queries via Reinforcement Learning

• URL: http://arxiv.org/abs/2504.19142v1
• Date: Sun, 27 Apr 2025 07:49:01 GMT
• Title: BQSched: A Non-intrusive Scheduler for Batch Concurrent Queries via Reinforcement Learning
• Authors: Chenhao Xu, Chunyu Chen, Jinglin Peng, Jiannan Wang, Jun Gao,
• Abstract summary: A key issue in minimizing the overall makespan of data pipelines is the efficient scheduling of concurrent queries.<n>To our knowledge, BQSched is the first non-intrusive batch query scheduler via reinforcement learning.<n>Extensive experiments show that BQSched can significantly improve the efficiency and stability of batch query scheduling.
• Score: 7.738546538164454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most large enterprises build predefined data pipelines and execute them periodically to process operational data using SQL queries for various tasks. A key issue in minimizing the overall makespan of these pipelines is the efficient scheduling of concurrent queries within the pipelines. Existing tools mainly rely on simple heuristic rules due to the difficulty of expressing the complex features and mutual influences of queries. The latest reinforcement learning (RL) based methods have the potential to capture these patterns from feedback, but it is non-trivial to apply them directly due to the large scheduling space, high sampling cost, and poor sample utilization. Motivated by these challenges, we propose BQSched, a non-intrusive Scheduler for Batch concurrent Queries via reinforcement learning. Specifically, BQSched designs an attention-based state representation to capture the complex query patterns, and proposes IQ-PPO, an auxiliary task-enhanced proximal policy optimization (PPO) algorithm, to fully exploit the rich signals of Individual Query completion in logs. Based on the RL framework above, BQSched further introduces three optimization strategies, including adaptive masking to prune the action space, scheduling gain-based query clustering to deal with large query sets, and an incremental simulator to reduce sampling cost. To our knowledge, BQSched is the first non-intrusive batch query scheduler via RL. Extensive experiments show that BQSched can significantly improve the efficiency and stability of batch query scheduling, while also achieving remarkable scalability and adaptability in both data and queries. For example, across all DBMSs and scales tested, BQSched reduces the overall makespan of batch queries on TPC-DS benchmark by an average of 34% and 13%, compared with the commonly used heuristic strategy and the adapted RL-based scheduler, respectively.

Related papers

• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Improving DBMS Scheduling Decisions with Fine-grained Performance Prediction on Concurrent Queries -- Extended [15.354441937462271]
  This work introduces IconqSched, a new, principled non-intrusive scheduler that optimize execution order and timing of queries.<n>IconqSched features a novel fine-grained predictor, Iconq, which treats the system runtime as a black box.<n>We compare IconqSched to other schedulers in terms of end-to-end runtime using real workload traces.
  arXiv  Detail & Related papers  (2025-01-27T17:55:39Z)
• Multi-Bin Batching for Increasing LLM Inference Throughput [19.652542432683234]
  Large language models (LL) grow in popularity improving the efficiency of their systems.<n> requests is a critical step in scheduling jobs on servers.<n> requests often have varying generation lengths, causing resource underutilization.<n>We formalize this problem from a queueing-theoretic perspective, and aim to design a throughput control policy.
  arXiv  Detail & Related papers  (2024-12-03T03:16:12Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• MinPrompt: Graph-based Minimal Prompt Data Augmentation for Few-shot Question Answering [64.6741991162092]
  We present MinPrompt, a minimal data augmentation framework for open-domain question answering. We transform the raw text into a graph structure to build connections between different factual sentences. We then apply graph algorithms to identify the minimal set of sentences needed to cover the most information in the raw text. We generate QA pairs based on the identified sentence subset and train the model on the selected sentences to obtain the final model.
  arXiv  Detail & Related papers  (2023-10-08T04:44:36Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)
• Scheduling in Parallel Finite Buffer Systems: Optimal Decisions under Delayed Feedback [29.177402567437206]
  We present a partially observable (PO) model that captures the scheduling decisions in parallel queuing systems under limited information of delayed acknowledgements. We numerically show that the resulting policy outperforms other limited information scheduling strategies. We show how our approach can optimise the real-time parallel processing by using network data provided by Kaggle.
  arXiv  Detail & Related papers  (2021-09-17T13:45:02Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• Balanced Order Batching with Task-Oriented Graph Clustering [28.05598654297136]
  We propose an end-to-end learning and optimization framework named Balanced Task- Clustering Network (BTOGCN) to solve the Balanced Order Estimation Problem (BOBP) BOBP arises from the process of picking in Cainiao, the largest logistics platform in China.
  arXiv  Detail & Related papers  (2020-08-19T08:42:50Z)
• Buffer Pool Aware Query Scheduling via Deep Reinforcement Learning [12.388301931687893]
  We introduce SmartQueue, a learned scheduler that leverages overlapping data reads among incoming queries. SmartQueue relies on deep reinforcement learning to produce workload-specific scheduling strategies. We present results from a proof-of-concept prototype, demonstrating that learned schedulers can offer significant performance improvements.
  arXiv  Detail & Related papers  (2020-07-21T02:28:59Z)

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.