LSched：A Workload-Aware Learned Query Scheduler for Analytical Database Systems.pdf

Bigbig

193

15页

0次

2022-07-20

免费下载

LSched: A Workload-Aware Learned ery Scheduler for

Analytical Database Systems

Ibrahim Sabek

sabek@mit.edu

Massachusetts Institute of Technology

United States

Tenzin Samten Ukyab

∗

ukyab@berkeley.edu

University of California, Berkeley

United States

Tim Kraska

kraska@mit.edu

Massachusetts Institute of Technology

United States

ABSTRACT

Query scheduling is a crucial task for analytical database systems

that can greatly aect the query latency. However, existing sched-

uling approaches are based on heuristics and not optimal. A recent

trial proposed to use reinforcement learning for automatically learn-

ing end-to-end scheduling policies. However, such trial was not

capable of considering the database-specic characteristics (e.g., op-

erator types, pipelining), and hence becomes not ecient for analyt-

ical database systems. In this paper, we try to ll this gap and intro-

duce LSched (

earned

Sched

uler), a fully learned workload-aware

query scheduler for in-memory analytical database systems. LSched

provides an ecient inter-query and intra-quer y scheduling for dy-

namic analytical workloads (i.e., dierent queries can arrive/depart

at any time). We integrated LSched with an ecient in-memory

analytical database system, and evaluated it with TPCH, SSB, and

JOB benchmarks. Our evaluation shows that LSched improves over

the performance of existing state-of-the-art query schedulers and

heuristic-based ones by at least 35% and 50% in both streaming and

batching query workloads.

CCS CONCEPTS

• Information systems → Database query processing.

KEYWORDS

Databases, Query Scheduling and Execution, Machine Learning,

Reinforcement Learning

ACM Reference Format:

Ibrahim Sabek, Tenzin Samten Ukyab, and Tim Kraska. 2022. LSched: A

Workload-Aware Learned Query Scheduler for Analytical Database Systems.

In Proceedings of the 2022 International Conference on Management of Data

(SIGMOD ’22), June 12–17, 2022, Philadelphia, PA, USA. ACM, New York, NY,

USA, 15 pages. https://doi.org/10.1145/3514221.3526158

1 INTRODUCTION

Scheduling of tasks in an analytical query processing system can

have a profound impact on the query latency and query through-

put [

]. In modern database systems, a query is typ-

ically composed of one or more sub-tasks, i.e., operators, and a

∗

Work done when author was at MIT.

This work is licensed under a Creative Commons

Attribution International 4.0 License.

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA.

ACM ISBN 978-1-4503-9249-5/22/06..

https://doi.org/10.1145/3514221.3526158

Figure 1: Example on the scheduling quality of dierent three

query sche dulers: Critical path, Decima and LSched.

query scheduler is responsible of nding an execution order for

all tasks from all currently running queries in order to optimize

some goal (e.g., minimizing latency [

] or minimizing the schedule

makespan [

]). The optimization goal then determines how re-

sources (e.g., CPU, memory, threads) are shared among concurrent

queries and how various parts of the system function together.

However, for the most common optimization goals (e.g., overall

latency), it is impossible or computationally impractical to derive

an optimal algorithm. For example, scheduling

𝑁

queries on

𝑀

cores such that the makespan of the schedule is minimum, is

𝑁 𝑃

complete [

]. As a result, commonly used scheduling algorithms

rely on specic heuristics including FIFO, fair scheduling [

short job rst (SJF), highest priority rst (HPF), packing [

], and

approximation algorithms [47].

Although these standard techniques are easy-to-implement and

transparent (i.e., decisions are taken based on guidelines and hence

are understandable), they obviously miss major performance op-

timization opportunities when scheduling analytical workloads.

Heuristics tend to make simplifying assumptions and it is noto-

riously hard to extend them to consider more complex system

behavior. For example, it would be extremely hard to develop a

good scheduling heuristic, which considers not only the hardware

conguration, but also the current state of the system (e.g., what

data is cached), the query plan structure, the type of operations

(e.g., performance of hash vs index-joins), pipelining opportunities,

as well as, the unpredictability because of data dependent factors

(e.g., the selectivity of a predicate).

To overcome the complexity challenge of building a workload-

specic scheduling policy, a recent attempt, namely Decima [

proposed to use reinforcement learning (RL) to automatically build a

specic end-to-end scheduling policy for the input workload. While

the work laid the foundation to learn scheduling policies, it turned

out that the neural network design and RL solutions of Decima

Session 17: Query Processing and Optimization 2

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1228

are not capable of considering the database-specic characteristics,

such as the query structure, dierent operators (e.g., aggregation

vs join), and the pipelining opportunities. For example, Decima

assumes that any query is a DAG of tasks, where each task is a

black box and can not be scheduled unless all its parent tasks are

completed (i.e., no support for pipelining). However, in the case

of relational queries, it is crucial to consider each task as a white

box and optimize the scheduling policy according to its details and

relationships with other tasks. Figure 1 shows an example on how

using the proper degree of pipelining could aect the scheduling

quality. In this example, a query

𝑄

, which consists of 5 select

and 1 join operators (i.e., tasks), is scheduled using three dierent

schedulers over 5 threads. These schedulers are (1) typical critical

path pipelining [

] (a heuristic that runs the pipeline containing

more aggregate work rst), (2) Decima, and (3) our proposed learned

scheduler.

𝑄

has two sets of operators that can be pipelined. The

rst set has

𝑜

, and

𝑜

, while the second one has

𝑜

and

𝑜

. The gure shows the scheduling decisions (yellow rectangle)

for the three schedulers. As seen, the critical path results in two

scheduling decisions, where each decision performs one aggressive

pipelining (highlighted in bold). Decima has a lack of pipelining

support, yet, it still learns a good scheduling policy that packs tasks

eciently over threads. In contrast to both critical path (aggressive

pipelining) and Decima (non-pipelining), our proposed scheduler

provides the best scheduling (the total time is 20 compared to 23

and 27 for other schedules) as it learns proper pipelining (

𝑜

2 and

𝑜

in 𝑆

, and 𝑜

and 𝑜

in 𝑆

) as well as ecient tasks packing.

Besides Decima, the database literature has some trials to lever-

age machine learning (ML) for scheduling queries in analytical

workloads. However, such trials tend to use ML to predict the query

or task latency to make better decisions, rather than trying to learn

an entire scheduling policy. For example, Quickstep [

] uses linear

regression to predict the execution times of the future work orders

for a given query based on its execution history. Such prediction

is used to control the resource allocation decisions coming from

the running heuristic scheduling policy (e.g., HPF). More recently,

SelfTune [

] employs a constrained optimization technique to

tune the hyper-parameters of its xed scheduling policy for the

input workload. In both works, the scheduling policy is still based

on heuristics, and is not specically built from scratch for the input

workload. Another work [

] uses RL to automatically learn the

order of executing dierent queries that maximizes the utilization

of buer pool items (i.e., improving the hits ratio). However, opti-

mizing the schedule according to the buer pool hits only, without

considering other scheduling factors (e.g., parallelism degree for

each query) and the current state of execution environment, does

not necessarily lead to a better multi-query execution plan.

In this paper, we introduce LSched (

earned

Sched

uler), a fully

RL-based learned workload-aware query scheduler for in-memory

analytical database systems. LSched provides an ecient inter-query

and intra-query scheduling for dynamic analytical workloads (i.e.,

dierent queries can arrive and depart at any time). Given a set of

executed query plans from the past (e.g., workload logs), LSched

automatically learns how to make the following decisions at each

scheduling event: (1) which subset of queries to execute, (2) which

subset of operators from these queries to execute, and (3) how much

resources (e.g., threads) to be assigned to these operators. LSched

optimizes these scheduling decisions for the specic input workload

and according to a user-dened high-level policy objective (e.g.,

minimizing the user-perceived latency).

LSched works as follows: it takes a query to be scheduled as

an input (queries can arrive in batches or streaming fashion) and

generates a query plan (i.e., DAG of operators) for it using a typical

analytical DBMS (e.g., Quickstep [

]). Then, this query plan is

fed to the LSched’s scheduling agent, which consists of a query

encoder and a scheduling predictor, to predict a sequence of sched-

uling decisions for executing this query along with other queries

that already exist in the system at the moment. Each scheduling

decision is triggered by a scheduling event (e.g., arrival of a new

query, or nishing the execution of an operator), and is designed to

minimize the expected latency of all existing queries after running

the whole sequence of scheduling decisions (i.e., long-term execu-

tion plan). As LSched discovers better scheduling decisions over

time, LSched’s scheduling predictor improves and results in better

execution plans. This improvement procedure continues until the

predictor converges.

In summary, LSched has the following contributions that over-

come the limitations of Decima and outline how an end-to-end

query scheduling is learned in the database context:

(1) Employing ecient physical plan features. The accuracy

of RL-based query scheduling mainly depends on extracting rep-

resentative features that capture the relational query execution

environment well. Therefore, unlike Decima [

] which only ex-

tracts black-box features (e.g., number of tasks), LSched extracts a

representative set of white-box features from the physical plans of

the running queries (e.g., ne-grained level work orders) as well

as their interaction with the execution environment (e.g., status of

running execution threads).

(2) Ecient and accurate query encoding. Query encoding is a

crucial part in the learned scheduler as it has to digest large amount

of information, coming from the extracted features, accurately and

in an ecient manner. Therefore, unlike Decima [

] which uses

graph convolution networks (GCN) [

], LSched proposes a novel

Query Encoder that combines a customized tree convolution [

]

technique with importance weighting mechanisms from graph

attention networks (GAT) [

] to learn an ecient and accurate

query encoding that suits the nature of our scheduling problem.

(3) Flexible sche duling decisions. LSched proposes a Scheduling

Predictor, which is a deep neural network that eciently leverages

the Query Encoder output, to decide which relational operators from

running queries to be scheduled next and how much resources (e.g.,

threads) are needed for them. In addition, the Scheduling Predictor

can explicitly determine the eective degree of operators pipelining

that should be used at each execution step (i.e., neither aggressively

pipeline nor completely execute in a sequential mode). As far as

we know, automatically controlling the operators pipelining was

never introduced before by previous schedulers including Decima.

(4) Balance between average and tail latency. Unlike Decima

which focuses only on minimizing average query time, LSched

proposes a novel rewarding function that optimizes the scheduling

policy to minimize both average and tail latency at the same time.

(5) Eective training time. LSched performs its training in an

ecient manner. Moreover, unlike Decima which learns any new

Session 17: Query Processing and Optimization 2

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1229

of 15

免费下载

关注

评论