BQSched: A Non-intrusive Scheduler for Batch Concurrent Queries via Reinforcement Learning
作者: Chenhao Xu, Chunyu Chen, Jinglin Peng, Jiannan Wang, Jun Gao
分类: cs.DB, cs.AI
发布日期: 2025-04-27
备注: Accepted by ICDE '25
💡 一句话要点
BQSched：一种基于强化学习的非侵入式批量并发查询调度器
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 查询调度 强化学习 注意力机制 并发查询 PPO算法
📋 核心要点
- 现有并发查询调度方法依赖启发式规则，难以捕捉查询间的复杂关系，导致效率低下。
- BQSched利用强化学习，通过注意力机制学习查询模式，并设计IQ-PPO算法提升样本利用率。
- BQSched通过自适应掩码、查询聚类和增量模拟器等策略，显著提升了调度效率和可扩展性。
📝 摘要（中文）
大型企业通常构建预定义的数据管道，并定期执行这些管道，使用SQL查询处理各种任务的运营数据。最小化这些管道的总体完工时间的关键问题在于高效调度管道内的并发查询。由于难以表达查询的复杂特征和相互影响，现有工具主要依赖于简单的启发式规则。最新的基于强化学习（RL）的方法有潜力从反馈中捕获这些模式，但由于调度空间大、采样成本高和样本利用率低，直接应用它们并非易事。针对这些挑战，我们提出了BQSched，一种基于强化学习的非侵入式批量并发查询调度器。具体来说，BQSched设计了一种基于注意力的状态表示来捕获复杂的查询模式，并提出了IQ-PPO，一种辅助任务增强的近端策略优化（PPO）算法，以充分利用日志中单个查询完成的丰富信号。基于上述RL框架，BQSched进一步引入了三种优化策略，包括自适应掩码来修剪动作空间、基于调度增益的查询聚类来处理大型查询集，以及增量模拟器来降低采样成本。据我们所知，BQSched是第一个基于RL的非侵入式批量查询调度器。大量实验表明，BQSched可以显著提高批量查询调度的效率和稳定性，同时在数据和查询方面实现卓越的可扩展性和适应性。例如，在所有测试的DBMS和规模上，与常用的启发式策略和改进的基于RL的调度器相比，BQSched将TPC-DS基准测试中批量查询的总体完工时间平均减少了34%和13%。
🔬 方法详解
问题定义：论文旨在解决批量并发SQL查询的调度问题，目标是最小化整体完工时间。现有方法主要依赖启发式规则，无法有效捕捉查询之间的复杂依赖关系和资源竞争，导致调度效率低下。此外，直接应用强化学习方法面临调度空间巨大、采样成本高昂以及样本利用率低等挑战。
核心思路：论文的核心思路是利用强化学习自动学习高效的查询调度策略。通过设计合适的奖励函数和状态表示，使智能体能够从历史执行数据中学习查询之间的依赖关系和资源需求，从而做出更优的调度决策。为了解决强化学习的挑战，论文引入了辅助任务、动作空间剪枝和增量模拟等技术。
技术框架：BQSched的整体框架包括以下几个主要模块：1) 状态表示模块：使用基于注意力的机制提取查询的特征，并捕捉查询之间的相互影响。2) 强化学习智能体：使用IQ-PPO算法学习调度策略，该算法通过辅助任务提高样本利用率。3) 动作空间剪枝模块：使用自适应掩码减少动作空间，降低学习难度。4) 查询聚类模块：将相似的查询聚类，降低调度复杂性。5) 增量模拟器：通过增量方式模拟查询执行，降低采样成本。
关键创新：BQSched的关键创新在于：1) 提出了一种基于注意力的状态表示方法，能够有效捕捉查询之间的复杂关系。2) 提出了IQ-PPO算法，通过引入辅助任务显著提高了样本利用率。3) 结合了自适应掩码、查询聚类和增量模拟等多种优化策略，有效解决了强化学习在查询调度中的挑战。4) 实现了非侵入式的调度，无需修改底层数据库管理系统。
关键设计：1) 注意力机制：用于提取查询特征并捕捉查询间的依赖关系。具体实现未知，但推测使用了Transformer类似的结构。2) IQ-PPO：在PPO算法的基础上，增加了一个辅助任务，用于预测单个查询的完成时间，从而提供更丰富的奖励信号。3) 自适应掩码：根据当前状态动态地屏蔽掉一些不合理的调度动作，减少动作空间。4) 奖励函数：奖励函数的设计至关重要，需要综合考虑查询的完成时间、资源利用率等因素。具体形式未知。
🖼️ 关键图片
📊 实验亮点
实验结果表明，BQSched在TPC-DS基准测试中，与常用的启发式策略相比，批量查询的总体完工时间平均减少了34%；与改进的基于RL的调度器相比，平均减少了13%。这些结果证明了BQSched在效率、稳定性和可扩展性方面的显著优势。
🎯 应用场景
BQSched可应用于各种需要批量并发SQL查询调度的场景，例如数据仓库、大数据分析平台和ETL流程。通过优化查询调度，可以显著缩短数据处理时间，提高资源利用率，降低运营成本。该研究成果对于提升企业级数据处理效率具有重要意义，并有望推动数据库管理系统和数据分析技术的发展。
📄 摘要（原文）
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.