Buffer Pool Aware Query Scheduling via Deep Reinforcement Learning

Chi Zhang, Ryan Marcus, Anat Kleiman, Olga Papaemmanouil

Introduction

In modern database management systems (DBMS), disk I/O remains a primary performance bottleneck. To mitigate this, systems employ a buffer pool—a region of main memory used to cache frequently accessed data blocks. A "cache hit" allows a query to execute orders of magnitude faster by avoiding slow disk reads. However, the efficiency of the buffer pool is heavily dependent on the order in which queries are executed.

Traditional query scheduling often relies on simple heuristics like First-Come-First-Served (FCFS). While easy to implement, FCFS is agnostic to the current state of the buffer pool, often leading to suboptimal cache utilization. Even "greedy" approaches, which prioritize queries with the highest immediate cache overlap, can fail by ignoring the long-term impact of data eviction. This paper presents SmartQueue, a learned query scheduler that leverages Deep Reinforcement Learning (DRL) to optimize for long-term buffer pool efficiency.

The SmartQueue Architecture

SmartQueue treats query scheduling as a sequential decision-making problem. At its core is a Deep Q-Learning (DQN) agent designed to select the next query from a queue based on the current system state.

SmartQueue architecture using a DQN agent for query selection.

The system operates through a continuous feedback loop:

  1. State Representation: The agent receives a state vector consisting of a Buffer Bitmap (representing currently cached blocks) and a Query Vector (representing the data needs of pending queries, derived from EXPLAIN plans).
  2. Action Selection: A fully-connected neural network predicts "Q-values" for each query in the queue, representing the expected long-term reward of executing that specific query next.
  3. Reward Mechanism: After execution, the agent receives a reward based on the achieved buffer hit ratio. This allows the model to learn which scheduling decisions lead to better cache performance over time.

Experimental Evaluation

The researchers evaluated SmartQueue using the industry-standard TPC-DS benchmark on a PostgreSQL instance. The workload consisted of 1,000 query instances generated from 99 different templates. SmartQueue was compared against two baselines:

  • FCFS: The default database scheduling policy.
  • Greedy: A heuristic that selects the query with the highest immediate overlap with the current buffer pool.

Key Results

SmartQueue demonstrated significant improvements in both cache efficiency and overall system throughput. By learning to "prime" the cache for future requests, the DQN agent achieved a buffer hit ratio 65% higher than FCFS and 35% higher than the Greedy heuristic.

Performance comparison showing (a) average buffer hit ratio and (b) cumulative query execution time.

As shown in the results, the improved hit ratio translates directly into faster workload completion. SmartQueue finished the 1,000-query suite in approximately 40 hours, compared to over 60 hours for FCFS—a 55% improvement in total execution speed. Notably, the system also showed strong generalization capabilities, outperforming baselines on entirely new query templates after a brief period of online adaptation.

Discussion and Future Work

SmartQueue proves that learned schedulers can effectively navigate the complex trade-offs of buffer pool management. However, several avenues for future research remain:

  • Inductive Biases: Moving beyond fully-connected networks to architectures like locally connected networks might better capture the spatial nature of data block access.
  • SLA Integration: Real-world systems must often balance throughput with Service Level Agreements (SLAs). Future iterations could incorporate query urgency into the reward function.
  • Co-Optimization: A holistic approach that simultaneously optimizes query scheduling and the underlying cache eviction policy (e.g., LRU) could unlock even greater performance gains.

Summary updated

BibTeX
@inproceedings{zhang2020buffer,
  author = {Chi Zhang and Ryan Marcus and Anat Kleiman and Olga Papaemmanouil},
  title = {{Buffer Pool Aware Query Scheduling via Deep Reinforcement Learning}},
  booktitle = {AIDB@VLDB},
  year = {2020},
}
Figure