05-An Autonomous Materialized View Management System with Deep Reinforcement Learning.pdf

虎头虎脑

412

6页

4次

2022-03-02

免费下载

An Autonomous Materialized View Management

System with Deep Reinforcement Learning

Yue Han, Guoliang Li, Haitao Yuan, Ji Sun

Department of Computer Science, Tsinghua University, Beijing, China

{han-y19@mails.,liguoliang@,yht16@mails.,sun-j16@mails.}tsinghua.edu.cn

Abstract—Materialized views (MVs) can signicantly opti-

mize the query processing in databases. However, it is hard

to generate MVs for ordinary users because it relies on

background knowledge, and existing methods rely on DBAs

to generate and maintain MVs. However, DBAs cannot handle

large-scale databases, especially cloud databases that have

millions of database instances and support millions of users.

us it calls for an autonomous MV management system.

In this paper, we propose an autonomous materialized view

management system, AutoView. It analyzes query workloads,

estimates the costs and benets of materializing queries as

views, and selects MVs to maximize the benet within a space

budget. We propose a deep reinforcement learning model to

select high-quality MVs, which enriches the state representa-

tion with query and MVs’ embe dding. Experimental results

show that our method outperforms existing studies in terms

of MV selection quality.

Index Terms—materialized views, database, deep learning,

deep reinforcement learning.

I. introduction

Materialized views (MVs) are very important in DBMS that

utilize views to improve the query performance based on

the space-for-time trade-o principle. Specically for online

analytical processing (OLAP), many queries share equivalent

sub-queries and there are many redundant computations

among these queries. MVs can alleviate this problem by

utilizing views to avoid such redundant computations.

However, it is hard to automatically generate MVs for

ordinary users [10], [13], [14], because it relies on background

knowledge. Existing methods rely on DBAs to generate and

maintain MVs. However, DBAs cannot handle large-scale

databases, especially cloud databases that have millions of

database instances and support millions of users. erefore,

it calls for an autonomous MVs management system, which,

given a query workload, selects potential queries (subqueries)

as views and uses the views to answer subsequent queries.

MV management systems have four main modules. (1)

MV candidate generation. It analyzes the query workload,

selects common sub-queries, and takes them as candidates

to generate MVs. (2) MV Cost/Benet estimation. It esti-

mates the cost and benet of materializing subqueries as

views, where the cost includes the space/time overhead and

the benet is the saved execution time using the view to

optimize queries. (3) MV selection. It selects high-quality

∗

Guoliang Li is the corresponding author. is work was supported by

NSF of China (61632016,61925205,62041204), National Key R&D Program of

China (2020AAA0104500), Huawei, BNRist, and TAL education.

MV candidates to generate MVs based on the estimation

model, aiming to maximize the benet within a given cost

budget. (4) MV-aware query rewriting. Given a new query,

it selects appropriate views and rewrites the query based on

the selected views. ere are several challenges in these four

modules. First, MV selection relies on benet estimation of

using a view to optimize a query, and existing methods [1],

[12] do not consider the complicated eect of views on

queries and cannot capture the correlation between views

and queries. Second, traditional MV selection methods model

it as the knapsack problem and use greedy algorithms to

choose which MVs to materialize. However, the knapsack

problem relies highly on the estimation model and cannot

nd high-quality views. ird, MV rewriting also relies on

the estimation model, but existing models depend on the cost

model of optimizers and cannot eectively estimate the cost

and benet of using an MV to answer a query.

To address these challenges, we propose an end-to-end

autonomous MV management system, AutoView. It rst ana-

lyzes the query workloads, extracts common subqueries, and

selects the subqueries with high frequency as MV candidates.

en it estimates the benets of MV candidates and selects

the candidates with the highest benets as MVs. We use a

recurrent neural network (RNN) model, Encoder-Reducer,

to estimates queries and views and embed them as embedding

vectors. Next, to eectively select the MVs, we propose a re-

inforcement learning (RL) model, Encoder-Reducer Double

Deep Q-learning Network (ERDDQN), to select MVs. Finally,

for MV rewriting, we use the ERDDQN model to select MVs

to rewrite queries.

Contributions. We make the following contributions.

(1) We propose an autonomous materialized view manage-

ment system, AutoView, with deep reinforcement learning.

(2) We propose a reinforcement model to select MVs for ma-

terialization, and integrate the embedding vectors of queries

and MVs into the model.

(3) Our experimental results on real datasets showed that our

method signicantly outperformed existing solutions.

II. AutoView Overview

A. Problem Formulation

MV Selection. Given a set of SQL queries, Q = {q

}, we

aim to generate a set of views V = {v

}, such that (1) the

Execution time of different MV selection plans.

title AS t

movie_companies AS mc

company_type AS ct

info_type AS it

movie_info_idx AS mi_idx

movie_info AS mi

movie_keyword AS mk

Keyword AS k

info_type

info

movie_keyword

mv_id

kw_id

movie_info_idx

mv_id

if_tp_id

Title

title

pdn_year

movie_companies

mv_id

cpy_id

cpy_tp_id

company_name

name

cty_code

company_type

kind

keyword

Query Origin With v

With v

10.67ms 4.61ms 139.79ms 8.37ms 3.28ms

0.39ms 0.26ms 130.08ms ⇥ ⇥

169.12ms ⇥ 230.67ms 167.14ms ⇥

size ⇥ 111MB 103MB 43MB 154MB

<latexit sha1_base64="gbKLhFc+t7KEYWuRTKIpPsEuuBc=">AAAEgXicjVHbbtNAEJ24BtpwS+GRl1UTEEjVymsHJxEvVXnpS0UDTVOpriLb2Sar+oYvlULIl/EhiD+Av2B24yYOFYK1kj1z5pzZnR0vCUSWG8aPmral37v/YHun/vDR4ydPG7vPzrK4SH0+8OMgTs89N+OBiPggF3nAz5OUu6EX8KF3/V7mhzc8zUQcneazhF+G7iQSV8J3c6RGu7VvjscnIprnLloW9XVUBG66mH/1K9+COFN5UH2nX/B0Rl6RD6lAOYKhyKekdTNirUpgVgOrGrB9IhnHWVVsfV56mUHtTpghalObKcCsHu30FOxSa5m0qNlFsFlAnWdQa6k1qGmXfoMaXQVbTi5CnrUqcLOEuiWze5SZfxpMa3U1Zncoa28I1mUIycQXvulljB0fqu4stbeXG3vbPj5cOx0ejVdPX3cC1+PB/FQO5hMPuC8ntliJcFqjRhM7U4vcBawETSjXSdz4Dg6MIQYfCgiBQwQ54gBcyPC7AAYGJMhdwhy5FJFQeQ4LqKO3QBVHhYvsNf5PMLoo2QhjWTNTbh9PCfCXopPAS/TEqEsRy9OIyheqsmT/Vnuuasq7zXD3ylohsjlMkf2X71b5vz7ZSw5X0FU9COwpUYzszi+rFOpV5M1JpascKyTISTzGfIrYV87bdybKk6ne5du6Kv9TKSUrY7/UFvBL3lINuCeXvRrnXXBmUmZRq282D/bLUW/DC9iD1zjPDhzAEZzAAHxtTzvS+tpHfUt/oxu6uZRqtdLzHDaW/u438mUPFg==</latexit>



<latexit sha1_base64="PFsNAqRIwNX3k8ZxGOeeQvFhna4=">AAACyXicjVHLSsNAFD2Nr1pfVZdugkVwVVIrPnZFN4KbCvYBbZFJOq1j8zKZiLW48gfc6o+Jf6B/4Z0xFaWI3pDkzLn3nJk71w5dEUvLes0YU9Mzs3PZ+dzC4tLySn51rR4HSeTwmhO4QdS0Wcxd4fOaFNLlzTDizLNd3rAHxyrfuOFRLAL/XA5D3vFY3xc94TBJVL0di77HLvIFq2jpMCdBKQUFpFEN8i9oo4sADhJ44PAhCbtgiOlpoQQLIXEdjIiLCAmd57hHjrQJVXGqYMQO6NunVStlfVorz1irHdrFpTcipYkt0gRUFxFWu5k6n2hnxf7mPdKe6mxD+tupl0esxCWxf+nGlf/VqV4kejjQPQjqKdSM6s5JXRJ9K+rk5reuJDmExCncpXxE2NHK8T2bWhPr3tXdMp1/05WKVWsnrU3wrk6pB3yoYu9rnJOgvlMslYvls91C5SgddRYb2MQ2zXMfFZygihp5X+ERT3g2To1r49a4+yw1MqlmHT/CePgA7PGR2w==</latexit>



kind = 'pdc'

info = 'top 250'

<latexit sha1_base64="f6fTwr9yxrLXD3QmJ9Pi3hsahEI=">AAACyHicjVHLTsJAFD3UF+ILdemmkZi4IkWMjx3RjWGFiQUSIKYtA07oK9OphhA3/oBb/TLjH+hfeGcsRkOM3qbtmXPvOTN3rhv7PJGW9Zoz5uYXFpfyy4WV1bX1jeLmVjOJUuEx24v8SLRdJ2E+D5ktufRZOxbMCVyftdzRucq3bplIeBReyXHMeoEzDPmAe44kyu7WIx5eF0tW2dJhzoJKBkrIohEVX9BFHxE8pAjAEEIS9uEgoaeDCizExPUwIU4Q4jrPcI8CaVOqYlThEDui75BWnYwNaa08E632aBefXkFKE3ukiahOEFa7mTqfamfF/uY90Z7qbGP6u5lXQKzEDbF/6aaV/9WpXiQGONE9cOop1ozqzstcUn0r6uTmt64kOcTEKdynvCDsaeX0nk2tSXTv6m4dnX/TlYpVay+rTfGuTqkHfKri6Gucs6B5UK5Uy9XLw1LtLBt1HjvYxT7N8xg1XKABm7w5HvGEZ6NuxMadMf4sNXKZZhs/wnj4AJJBkVA=</latexit>

t.title

<latexit sha1_base64="6T3Vcx4agBY9LC6RwABkVTJZip8=">AAACxnicjVHLTsJAFD3UF+ILdemmkZi4Iq0YHzuiG5YYRUiQkLYM2NCX06mGEBN/wK1+mvEP9C+8Mw5GQ4zepu2Zc+85M3eumwR+KizrNWfMzM7NL+QXC0vLK6trxfWNyzTOuMcaXhzEvOU6KQv8iDWELwLWSjhzQjdgTXd4KvPNW8ZTP44uxChhndAZRH7f9xxB1PlN1+4WS1bZUmFOA1uDEnTU4+ILrtBDDA8ZQjBEEIQDOEjpacOGhYS4DsbEcUK+yjPco0DajKoYVTjEDuk7oFVbsxGtpWeq1B7tEtDLSWlihzQx1XHCcjdT5TPlLNnfvMfKU55tRH9Xe4XEClwT+5duUvlfnexFoI8j1YNPPSWKkd152iVTtyJPbn7rSpBDQpzEPcpzwp5STu7ZVJpU9S7v1lH5N1UpWbn2dG2Gd3lKNeBjGQdf45wGl3tlu1KunO2Xqid61HlsYRu7NM9DVFFDHQ3yHuART3g2akZkZMbdZ6mR05pN/Ajj4QMWJZBR</latexit>



kind = 'pdc'

info = 'bottom 10'



info = 'top 250'

pdn_year

BETWEEN 2005 AND 2010



pdn_year > 2005



<latexit sha1_base64="yDcY7ZlUDao/dpj7K4O3umAJO90=">AAACxnicjVHLTsJAFD3UF+ILdemmkZi4IgWMjx3RDUuM8kiQkHYYsKEv26mGEBN/wK1+mvEP9C+8Mw5GQ4zepu2Zc+85M3euE3luIizrNWPMzS8sLmWXcyura+sb+c2tZhKmMeMNFnph3HbshHtuwBvCFR5vRzG3fcfjLWd0JvOtWx4nbhhcinHEu749DNyBy2xB1MVNr9zLF6yipcKcBSUNCtBRD/MvuEIfIRhS+OAIIAh7sJHQ00EJFiLiupgQFxNyVZ7jHjnSplTFqcImdkTfIa06mg1oLT0TpWa0i0dvTEoTe6QJqS4mLHczVT5VzpL9zXuiPOXZxvR3tJdPrMA1sX/pppX/1cleBAY4Vj241FOkGNkd0y6puhV5cvNbV4IcIuIk7lM+JsyUcnrPptIkqnd5t7bKv6lKyco107Up3uUp1YBPZBx+jXMWNMvFUqVYOT8oVE/1qLPYwS72aZ5HqKKGOhrkPcQjnvBs1IzASI27z1IjozXb+BHGwwcYhZBS</latexit>

<latexit sha1_base64="N42nT7EwdYemrN2RLzCfA0MHIJ0=">AAACxnicjVHLTsJAFD3UF+ILdemmkZi4IkWMjx3RDUuMIiRISFsGnFDaOp1qCDHxB9zqpxn/QP/CO+NgNMTobdqeOfeeM3PnenHAE+k4rxlrZnZufiG7mFtaXlldy69vXCZRKnxW96MgEk3PTVjAQ1aXXAasGQvmDr2ANbzBqco3bplIeBReyFHM2kO3H/Ie911J1PlNp9zJF5yio8OeBiUDCjBRi/IvuEIXEXykGIIhhCQcwEVCTwslOIiJa2NMnCDEdZ7hHjnSplTFqMIldkDfPq1ahg1prTwTrfZpl4BeQUobO6SJqE4QVrvZOp9qZ8X+5j3WnupsI/p7xmtIrMQ1sX/pJpX/1aleJHo40j1w6inWjOrONy6pvhV1cvtbV5IcYuIU7lJeEPa1cnLPttYkund1t67Ov+lKxaq1b2pTvKtT6gEfqzj4Guc0uNwrlsrF8tl+oXJiRp3FFraxS/M8RAVV1FAn7z4e8YRnq2qFVmrdfZZaGaPZxI+wHj4AGuWQUw==</latexit>

<latexit sha1_base64="DjrU99leJSCqGBlQwOpE/B9dECA=">AAACxnicjVHLSsNAFD3GV62vqks3wSK4KokVH7uimy4r2gfUUpJ0WkPzYjKplCL4A27108Q/0L/wzjgVpYjekOTMufecmTvXTQI/FZb1OmfMLywuLedW8qtr6xubha3tRhpn3GN1Lw5i3nKdlAV+xOrCFwFrJZw5oRuwpju8kPnmiPHUj6NrMU5YJ3QGkd/3PUcQdTXq2t1C0SpZKsxZYGtQhI5aXHjBDXqI4SFDCIYIgnAAByk9bdiwkBDXwYQ4TshXeYZ75EmbURWjCofYIX0HtGprNqK19EyV2qNdAno5KU3skyamOk5Y7maqfKacJfub90R5yrON6e9qr5BYgVti/9JNK/+rk70I9HGqevCpp0QxsjtPu2TqVuTJzW9dCXJIiJO4R3lO2FPK6T2bSpOq3uXdOir/piolK9eers3wLk+pBnwm4/hrnLOgcViyy6Xy5VGxcq5HncMu9nBA8zxBBVXUUCfvAR7xhGejakRGZtx9lhpzWrODH2E8fAAiD5BW</latexit>

<latexit sha1_base64="Y3JEJiEqCrQVAgpwMPcQuGaLXng=">AAACxnicjVHLTsJAFD3UF+ILdemmkZi4IgWMjx3RDUuM8kiQkLYMOKGvTKcYQkz8Abf6acY/0L/wzliMhhi9Tdsz595zZu5cJ/J4LC3rNWMsLC4tr2RXc2vrG5tb+e2dZhwmwmUNN/RC0XbsmHk8YA3JpcfakWC273is5YwuVL41ZiLmYXAtJxHr+vYw4APu2pKoq3Gv3MsXrKKlw5wHpRQUkEY9zL/gBn2EcJHAB0MASdiDjZieDkqwEBHXxZQ4QYjrPMM9cqRNqIpRhU3siL5DWnVSNqC18oy12qVdPHoFKU0ckCakOkFY7WbqfKKdFfub91R7qrNN6O+kXj6xErfE/qWbVf5Xp3qRGOBU98Cpp0gzqjs3dUn0raiTm9+6kuQQEadwn/KCsKuVs3s2tSbWvau7tXX+TVcqVq3dtDbBuzqlHvCZiuOvcc6DZrlYqhQrl0eF6nk66iz2sI9DmucJqqihjgZ5D/GIJzwbNSMwEuPus9TIpJpd/Ajj4QMkb5BX</latexit>

<latexit sha1_base64="kL8p6D2R5s32dNX/lvuTvfOqNOg=">AAACxnicjVHLSsNAFD3GV62vqks3wSK4KqkVH7uimy4r2gfUUpLptIamSZhMKqUI/oBb/TTxD/QvvDNORSmiNyQ5c+49Z+bO9eLAT6TjvM5Z8wuLS8uZlezq2vrGZm5ru55EqWC8xqIgEk3PTXjgh7wmfRnwZiy4O/QC3vAGFyrfGHGR+FF4Lccxbw/dfuj3fOZKoq5GnVInl3cKjg57FhQNyMNENcq94AZdRGBIMQRHCEk4gIuEnhaKcBAT18aEOEHI13mOe2RJm1IVpwqX2AF9+7RqGTaktfJMtJrRLgG9gpQ29kkTUZ0grHazdT7Vzor9zXuiPdXZxvT3jNeQWIlbYv/STSv/q1O9SPRwqnvwqadYM6o7ZlxSfSvq5Pa3riQ5xMQp3KW8IMy0cnrPttYkund1t67Ov+lKxao1M7Up3tUp9YDPVBx/jXMW1A8LxVKhdHmUL5+bUWewiz0c0DxPUEYFVdTIu49HPOHZqlihlVp3n6XWnNHs4EdYDx8mz5BY</latexit>

⇡

<latexit sha1_base64="9GxX6Svwpwr2IIOPV2IoMm+yK0I=">AAACxnicjVHLSsNAFD2Nr1pfVZdugkVwVVIrPnZFN11WtA9oiyTTaR2aJmEyUUoR/AG3+mniH+hfeGdMRSmiNyQ5c+49Z+bO9SJfxMpxXjPW3PzC4lJ2Obeyura+kd/casRhIhmvs9APZctzY+6LgNeVUD5vRZK7I8/nTW94rvPNWy5jEQZXahzx7sgdBKIvmKuIuuxE4jpfcIqOCXsWlFJQQBq1MP+CDnoIwZBgBI4AirAPFzE9bZTgICKuiwlxkpAweY575EibUBWnCpfYIX0HtGqnbEBr7RkbNaNdfHolKW3skSakOklY72abfGKcNfub98R46rON6e+lXiNiFW6I/Us3rfyvTvei0MeJ6UFQT5FhdHcsdUnMreiT29+6UuQQEadxj/KSMDPK6T3bRhOb3vXduib/Zio1q9csrU3wrk9pBnyq4+hrnLOgcVAslYvli8NC5SwddRY72MU+zfMYFVRRQ528B3jEE56tqhVYiXX3WWplUs02foT18AGRjJCF</latexit>

mv_id,

cpy_id

⇡

info,

mv_id,

minfo

⇡

info,

mv_id,

minfo

⇡

t.title

⇡

t.title

⇡

info

LIKE '%sequel%'

t mc

mi_idx

t mc

mi_idx t

mi_idx k mk



kind = 'pdc’

mi_idx



info = 'top 250'

mi_idx

Queries

Views

Database Schema

Fig. 1. MV selection example.

⇡

t.title



kind = 'pdc’



kind = 'pdc'

info = 'top 250'

t.title

⇡

mi_idx



info = 'top 250'

}

<latexit sha1_base64="LdwopafjOkHfaSzQGXrFmdoQvAs=">AAAC13icjVHLSsNAFD2Nr1pftS7dBIvgQkpixceu6MZlBfuQVkOSTmtomsRkUiyluBO3/oBb/SPxD/QvvDOmohTRG5KcOfeeM3PnWoHrRFzTXlPK1PTM7Fx6PrOwuLS8kl3NVSM/Dm1WsX3XD+uWGTHX8ViFO9xl9SBkZs9yWc3qHot8rc/CyPG9Mz4I2EXP7HhO27FNTpSRzV0b+uWwOewb+rbaN4rN0cjI5rWCJkOdBHoC8kii7Gdf0EQLPmzE6IHBAyfswkRETwM6NATEXWBIXEjIkXmGETKkjamKUYVJbJe+HVo1EtajtfCMpNqmXVx6Q1Kq2CSNT3UhYbGbKvOxdBbsb95D6SnONqC/lXj1iOW4IvYv3bjyvzrRC0cbB7IHh3oKJCO6sxOXWN6KOLn6rStODgFxArcoHxK2pXJ8z6rURLJ3cbemzL/JSsGKtZ3UxngXp5QDPhSx9zXOSVDdKejFQvF0N186Skadxjo2sEXz3EcJJyijQt43eMQTnpVz5Va5U+4/S5VUolnDj1AePgDaHJZ4</latexit>

Fig. 2. ery rewriting example.

total size of views in V is within a space budget

, and (2) the

performance of using views in V to answer queries in Q is

optimized. Figure 1 shows an example with three queries

Q = {q

, q

} and three views V = {v

, v

}. e

execution time of dierent optimization plans are also shown

in Figure 1. e spaces occupied by v

, v

are 111MB,

103MB and 43MB respectively. If the MV space budget is

50MB, we will materialize {v

} and utilize it to optimize

with a benet of (10.67-8.37)+(169.12-167.14)=4.28ms. If

the budget is 120MB, we will materialize {v

} and get

a benet of (10.67-4.61)+(0.39-0.26)=6.19ms. If the budget

is 200MB, we will materialize {v

, v

} and get a benet

of (10.67-3.28)+(0.39-0.26)+(169.12-167.14)=9.50ms. We do not

materialize v

, because it does not improve the performance.

ery Rewriting with MVs. Given a set of views V = {v

}

and a query q, we select a subset of views, V

⊆ V , and use

the views in V

to answer query q, such that the performance

of answering q with MVs in V is optimized. For example,

given three MVs v

, v

, query q

can be optimized using

and v

, and the optimized plan is shown in Figure 2.

B. System Overview

To address the MV generation and query rewriting prob-

lem with MVs, we propose an autonomous MV management

system as shown in Figure 3. e goal of AutoView is to

automatically generate MVs by analyzing the query workload

and utilize the MVs to optimize queries. e system includes

four mo dules, MV candidate generation, MV cost/benet

estimation, MV selection, and MV-aware query rewriting.

Our method can also support the case that the total time of generating

views in V is within a time constraint.

MV Candidate Generator. We analyze the workload to

nd common subqueries for MV candidate generation, where

a subquery is a subtree of the syntax tree for relational

algebra. Common subqueries are the equivalent or similar

rewrien subqueries among dierent queries. Common sub-

queries with a high quality will be selected as MV candidates.

Equivalent subqueries will be rewrien in the same form [2],

[3], [9]. And subqueries that have similar selection conditions

will be merged into a large one. For example, “WHERE

country IN (’Sweden’, ’Norway’) GROUP BY country” and

“WHERE country IN (’Bulgaria’) GROUP BY country” will

be merged into “WHERE country IN (’Sweden’, ’Norway’,

’Bulgaria’) GROUP BY country”. We discuss the details of

MV candidate generation in Section III.

MV Estimation. Let V = {v

} denote the set of MV

candidates. is module estimates the saved execution time

(called benet) from executing q

∈ Q by making use of a

set of views V

⊆ V . e benet of using V

to answer q

can be calculated by the formula below:

B(q

, V

) = t

− t

(1)

where t

is the execution time of q

without using views

and t

is the execution time of executing q

using V

ere are several ways to estimate the benet. e most

straightforward way is utilizing the cost estimation of op-

timizer. e dierence of the COST of a query and the

rewrien query can be the estimation of benet. Due to that

optimizer has a large error on the estimation, we can use

deep learning model [8] as cost estimation. Furthermore, we

propose an RNN model, Encoder-Reducer, to estimate the

benet and embed queries and MVs. Encoder-Reducer will

be introduced in future works.

MV Selection. Given a space budget τ, this module selects

a subset of MV candidates to maximize the total benet of

answering queries in Q within the space budget. We model

this selection problem as an integer programming problem

and propose a reinforcement learning (RL) model to address

it. e details of MV selection are presented in Section IV.

MV-aware ery Rewriting. Given a query, if the query

can be optimized using the MVs, we use our estimation model

An Autonomous Materialized View Management

System with Deep Reinforcement Learning

Yue Han, Guoliang Li, Haitao Yuan, Ji Sun

Department of Computer Science, Tsinghua University, Beijing, China

{han-y19@mails.,liguoliang@,yht16@mails.,sun-j16@mails.}tsinghua.edu.cn

Abstract—Materialized views (MVs) can signicantly opti-

mize the query processing in databases. However, it is hard

to generate MVs for ordinary users because it relies on

background knowledge, and existing methods rely on DBAs

to generate and maintain MVs. However, DBAs cannot handle

large-scale databases, especially cloud databases that have

millions of database instances and support millions of users.

us it calls for an autonomous MV management system.

In this paper, we propose an autonomous materialized view

management system, AutoView. It analyzes query workloads,

estimates the costs and benets of materializing queries as

views, and selects MVs to maximize the benet within a space

budget. We propose a deep reinforcement learning model to

select high-quality MVs, which enriches the state representa-

tion with query and MVs’ embe dding. Experimental results

show that our method outperforms existing studies in terms

of MV selection quality.

Index Terms—materialized views, database, deep learning,

deep reinforcement learning.

I. introduction

Materialized views (MVs) are very important in DBMS that

utilize views to improve the query performance based on

the space-for-time trade-o principle. Specically for online

analytical processing (OLAP), many queries share equivalent

sub-queries and there are many redundant computations

among these queries. MVs can alleviate this problem by

utilizing views to avoid such redundant computations.

However, it is hard to automatically generate MVs for

ordinary users [10], [13], [14], because it relies on background

knowledge. Existing methods rely on DBAs to generate and

maintain MVs. However, DBAs cannot handle large-scale

databases, especially cloud databases that have millions of

database instances and support millions of users. erefore,

it calls for an autonomous MVs management system, which,

given a query workload, selects potential queries (subqueries)

as views and uses the views to answer subsequent queries.

MV management systems have four main modules. (1)

MV candidate generation. It analyzes the query workload,

selects common sub-queries, and takes them as candidates

to generate MVs. (2) MV Cost/Benet estimation. It esti-

mates the cost and benet of materializing subqueries as

views, where the cost includes the space/time overhead and

the benet is the saved execution time using the view to

optimize queries. (3) MV selection. It selects high-quality

∗

Guoliang Li is the corresponding author. is work was supported by

NSF of China (61632016,61925205,62041204), National Key R&D Program of

China (2020AAA0104500), Huawei, BNRist, and TAL education.

MV candidates to generate MVs based on the estimation

model, aiming to maximize the benet within a given cost

budget. (4) MV-aware query rewriting. Given a new query,

it selects appropriate views and rewrites the query based on

the selected views. ere are several challenges in these four

modules. First, MV selection relies on benet estimation of

using a view to optimize a query, and existing methods [1],

[12] do not consider the complicated eect of views on

queries and cannot capture the correlation between views

and queries. Second, traditional MV selection methods model

it as the knapsack problem and use greedy algorithms to

choose which MVs to materialize. However, the knapsack

problem relies highly on the estimation model and cannot

nd high-quality views. ird, MV rewriting also relies on

the estimation model, but existing models depend on the cost

model of optimizers and cannot eectively estimate the cost

and benet of using an MV to answer a query.

To address these challenges, we propose an end-to-end

autonomous MV management system, AutoView. It rst ana-

lyzes the query workloads, extracts common subqueries, and

selects the subqueries with high frequency as MV candidates.

en it estimates the benets of MV candidates and selects

the candidates with the highest benets as MVs. We use a

recurrent neural network (RNN) model, Encoder-Reducer,

to estimates queries and views and embed them as embedding

vectors. Next, to eectively select the MVs, we propose a re-

inforcement learning (RL) model, Encoder-Reducer Double

Deep Q-learning Network (ERDDQN), to select MVs. Finally,

for MV rewriting, we use the ERDDQN model to select MVs

to rewrite queries.

Contributions. We make the following contributions.

(1) We propose an autonomous materialized view manage-

ment system, AutoView, with deep reinforcement learning.

(2) We propose a reinforcement model to select MVs for ma-

terialization, and integrate the embedding vectors of queries

and MVs into the model.

(3) Our experimental results on real datasets showed that our

method signicantly outperformed existing solutions.

II. AutoView Overview

A. Problem Formulation

MV Selection. Given a set of SQL queries, Q = {q

}, we

aim to generate a set of views V = {v

}, such that (1) the

Execution time of different MV selection plans.

title AS t

movie_companies AS mc

company_type AS ct

info_type AS it

movie_info_idx AS mi_idx

movie_info AS mi

movie_keyword AS mk

Keyword AS k

info_type

info

movie_keyword

mv_id

kw_id

movie_info_idx

mv_id

if_tp_id

Title

title

pdn_year

movie_companies

mv_id

cpy_id

cpy_tp_id

company_name

name

cty_code

company_type

kind

keyword

Query Origin With v

With v

10.67ms 4.61ms 139.79ms 8.37ms 3.28ms

0.39ms 0.26ms 130.08ms ⇥ ⇥

169.12ms ⇥ 230.67ms 167.14ms ⇥

size ⇥ 111MB 103MB 43MB 154MB



kind = 'pdc'

info = 'top 250'

t.title



kind = 'pdc'

info = 'bottom 10'



info = 'top 250'

pdn_year

BETWEEN 2005 AND 2010



pdn_year > 2005



⇡

mv_id,

cpy_id

⇡

info,

mv_id,

minfo

⇡

info,

mv_id,

minfo

⇡

t.title

⇡

t.title

⇡

info

LIKE '%sequel%'

t mc

mi_idx

t mc

mi_idx t

mi_idx k mk



kind = 'pdc’

mi_idx



info = 'top 250'

mi_idx

Queries

Views

Database Schema

Fig. 1. MV selection example.

⇡

t.title



kind = 'pdc’



kind = 'pdc'

info = 'top 250'

t.title

⇡

mi_idx



info = 'top 250'

}

Fig. 2. ery rewriting example.

total size of views in V is within a space budget

, and (2) the

performance of using views in V to answer queries in Q is

optimized. Figure 1 shows an example with three queries

Q = {q

, q

} and three views V = {v

, v

}. e

execution time of dierent optimization plans are also shown

in Figure 1. e spaces occupied by v

, v

are 111MB,

103MB and 43MB respectively. If the MV space budget is

50MB, we will materialize {v

} and utilize it to optimize

with a benet of (10.67-8.37)+(169.12-167.14)=4.28ms. If

the budget is 120MB, we will materialize {v

} and get

a benet of (10.67-4.61)+(0.39-0.26)=6.19ms. If the budget

is 200MB, we will materialize {v

, v

} and get a benet

of (10.67-3.28)+(0.39-0.26)+(169.12-167.14)=9.50ms. We do not

materialize v

, because it does not improve the performance.

ery Rewriting with MVs. Given a set of views V = {v

}

and a query q, we select a subset of views, V

⊆ V , and use

the views in V

to answer query q, such that the performance

of answering q with MVs in V is optimized. For example,

given three MVs v

, v

, query q

can be optimized using

and v

, and the optimized plan is shown in Figure 2.

B. System Overview

To address the MV generation and query rewriting prob-

lem with MVs, we propose an autonomous MV management

system as shown in Figure 3. e goal of AutoView is to

automatically generate MVs by analyzing the query workload

and utilize the MVs to optimize queries. e system includes

four mo dules, MV candidate generation, MV cost/benet

estimation, MV selection, and MV-aware query rewriting.

Our method can also support the case that the total time of generating

views in V is within a time constraint.

MV Candidate Generator. We analyze the workload to

nd common subqueries for MV candidate generation, where

a subquery is a subtree of the syntax tree for relational

algebra. Common subqueries are the equivalent or similar

rewrien subqueries among dierent queries. Common sub-

queries with a high quality will be selected as MV candidates.

Equivalent subqueries will be rewrien in the same form [2],

[3], [9]. And subqueries that have similar selection conditions

will be merged into a large one. For example, “WHERE

country IN (’Sweden’, ’Norway’) GROUP BY country” and

“WHERE country IN (’Bulgaria’) GROUP BY country” will

be merged into “WHERE country IN (’Sweden’, ’Norway’,

’Bulgaria’) GROUP BY country”. We discuss the details of

MV candidate generation in Section III.

MV Estimation. Let V = {v

} denote the set of MV

candidates. is module estimates the saved execution time

(called benet) from executing q

∈ Q by making use of a

set of views V

⊆ V . e benet of using V

to answer q

can be calculated by the formula below:

B(q

, V

) = t

− t

(1)

where t

is the execution time of q

without using views

and t

is the execution time of executing q

using V

ere are several ways to estimate the benet. e most

straightforward way is utilizing the cost estimation of op-

timizer. e dierence of the COST of a query and the

rewrien query can be the estimation of benet. Due to that

optimizer has a large error on the estimation, we can use

deep learning model [8] as cost estimation. Furthermore, we

propose an RNN model, Encoder-Reducer, to estimate the

benet and embed queries and MVs. Encoder-Reducer will

be introduced in future works.

MV Selection. Given a space budget τ, this module selects

a subset of MV candidates to maximize the total benet of

answering queries in Q within the space budget. We model

this selection problem as an integer programming problem

and propose a reinforcement learning (RL) model to address

it. e details of MV selection are presented in Section IV.

MV-aware ery Rewriting. Given a query, if the query

can be optimized using the MVs, we use our estimation model

of 6

免费下载

paper 李国良

关注

评论