Learned Cardinality Estimation：An In-depth Study.pdf

Bigbig

305

14页

6次

2022-07-20

免费下载

Learned Cardinality Estimation: An In-depth Study

Kyoungmin Kim

†

Jisung Jung

†

In Seo

†

Wook-Shin Han

†∗

Kangwoo Choi

‡

Jaehyok Chong

‡

Pohang University of Science and Technology (POSTECH), Korea

†

SAP Labs, Korea

‡

{kmkim, jsjeong, iseo, wshan}@dblab.postech.ac.kr

†

{kangwoo.choi, ja.chong}@sap.com

‡

ABSTRACT

Learned cardinality estimation (CE) has recently gained signicant

attention for replacing long-studied traditional CE with machine

learning, especially for deep learning. However, these estimators

were developed independently and have not been fairly or compre-

hensively compared in common settings. Most studies use a subset

of IMDB data which is too simple to measure their limits and deter-

mine whether they are ready for real, complex data. Furthermore,

they are regarded as black boxes, without a deep understanding of

why large errors occur.

In this paper, we rst provide a taxonomy and a unied workow

of learned estimators for a better understanding of estimators. We

next comprehensively compare recent learned CE methods that

support joins, from a subset of tables to full IMDB and TPC-DS

datasets. Under the experimental results, we then demystify the

black-box models and analyze critical components that cause large

errors. We also measure their impact on query optimization. Finally,

based on the ndings, we suggest realizable research opportunities.

We believe that a deeper understanding of the behavior of exist-

ing methods can provide a more comprehensive and substantial

framework for developing better estimators.

CCS CONCEPTS

• Information systems → Query optimization

;

• Computing

methodologies → Machine learning.

KEYWORDS

Cardinality estimation

ACM Reference Format:

Kyongmin Kim, Jisung Jeong, In Seo, Wook-Shin Han, Kangwoo Choi, and

Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-depth Study.

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, 14 pages. https://doi.org/10.1145/3514221.3526154

1 INTRODUCTION

Recent advances in deep learning have inuenced database research

areas as well, including the query optimization in DBMSs [11, 31].

Especially, the cardinality estimation (CE) of intermediate results

has gained signicant attention [

] since it lies at

∗

corresponding author

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than ACM

must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,

to post on servers or to redistribute to lists, requires prior specic permission and/or a

fee. Request permissions from permissions@acm.org.

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

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

https://doi.org/10.1145/3514221.3526154

the core of query optimization for producing good execution plans

[9].

We focus on the learned CE based on machine learning (ML)

and deep learning (DL) techniques, to replace the traditional CE

methods relying on ad-hoc assumptions of the data, e.g., uniformity

and independence [

]. By removing such assumptions, learned

estimators improve estimation accuracy by a large margin. However,

as raised in [

], the question remains whether learned estimators

are ready for production, especially for real, complex data with

joins.

Existing learned CE benchmarks [

] and methods [

] neither compare against existing methods comprehensively nor

reect real, complex data. They either 1) use single-table datasets

only [

], 2) use multi-table datasets that are too simple

(star-shaped schema with six tables only) [

], or 3) compare

with a few DL architectures or traditional methods only [

Furthermore, all these studies treat the learned estimators as black-

box models [

] without a deep understanding of why large errors

occur. Without such understanding, using them in commercial

DBMSs with real data would be dangerous.

In this paper, we conduct in-depth experiments and analysis of

the learned estimators (published at major conferences and journals

before July 2021) using the simple settings of previous studies to

more complex settings, including high-dimensional data in IMDB

and TPC-DS benchmarks over 20 tables and 400 columns. We add-

ress the limitation of the learned estimators, demystify when and

where they fail, and suggest research opportunities to overcome

their problems. Apart from suggestions, we provide meaningful

improvements over the existing methods that even outperform

state-of-the-art methods without relying on ensemble learning.

In summary, we

•

provide a taxonomy and a unied workow of learned esti-

mators for a high-level understanding (Section 2);

•

propose new variations of the learned estimators that of-

ten outperform state-of-the-art methods on a database com-

monly used in previous studies (Section 2);

•

comprehensively compare learned estimators using various

datasets and workloads, including our synthetic environ-

ments (Section 3);

•

demystify the black-box models and analyze the critical com-

ponents that aect the performance (Section 4);

•

improve the query optimization quality by injecting the

learned cardinalities (Section 5); and

•

summarize lessons learned and propose practical research

opportunities that can facilitate future studies (Section 6).

Session 17: Query Processing and Optimization 2

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

1214

Table 1: Taxonomy of learned cardinality estimators including ours.

Estimator Category Learning Model Table Groups Inductive Bias

FCN (ours) Query Supervised Fully Connected Network 1 Strong inter-/intra-table predicate correlation

FCN+Pool (ours) Query Supervised Fully Connected Network + Pooling 1 Strong intra-table predicate correlation

MSCN [8] Query Supervised Multi-Set Convolutional Network 1 Weak predicate correlation

E2E [24] Query Multi-task sup. TreeLSTM 1 Recursive representation of subplans

DeepDB [5] Data Unsupervised Sum-Product Network N Hierarchy of independent subtables

DeepDB+JCT (ours) Data Unsupervised Sum-Product Network N DeepDB + Removed bias from training data

DeepDB+NARU (ours) Data Self-supervised Deep Autoregressive Model N Dependencies following a certain attribute order

NeuroCard [28] Data Self-supervised Deep Autoregressive Model 1 Dependencies following a certain attribute order

UAE [26] Query+Data Supervised+Self-sup. Deep Autoregressive Model 1 Dependencies following a certain attribute order

2 LEARNED CARDINALITY ESTIMATION

2.1 Problem Denition

In this paper, we focus on the CE of SPJ queries with inner joins as

it is the scope of the most current learned estimators. Extending

our problem to group by queries, UDFs, and theta joins, would be

interesting future work.

Denition 1. (Database).

A database

is a triple (

𝑇

𝐽

𝐴

), where

𝑇

𝐽

, and

𝐴

represent the sets of tables, PK-FK joins,

and attributes. A table 𝑇 ∈ D

𝑇

has a set of attributes A

𝑇

⊆ D

𝐴

Denition 2. (Query).

A query

𝑄

dened over a database

is a

triple (

𝑇 (𝑄)

𝐽 (𝑄)

𝑅(𝑄)

) where

𝑇 (𝑄)

𝐽 (𝑄)

, and

𝑅(𝑄)

represent the

set of tables (

⊆ D

𝑇

), inner join predicates (

⊆ D

𝐽

), and conjunction

of selection predicates, i.e., ∧{(𝐴, 𝑜𝑝, 𝑣𝑎𝑙) | 𝐴 ∈ D

𝐴

Denition 3. (Cardinality Estimation).

Given a database

= (

𝑇

𝐽

𝐴

) and a query

𝑄

= (

𝑇 (𝑄)

𝐽 (𝑄)

𝑅(𝑄)

), our problem is

to estimate the cardinality

𝑐𝑎𝑟𝑑(𝑄)

𝑄

, i.e., the result of SQL "select

count(*) from 𝑇 (𝑄) where 𝐽 (𝑄) and 𝑅(𝑄)."

We dene the domain and range as follows. The domain

𝑑𝑜𝑚(𝐴)

is dened for each column 𝐴 ∈ D

𝐴

as the set of all distinct values

that appear in

𝐴

. The range of

𝐴

w.r.t.

𝑄

𝑅

𝑄

(𝐴)

, is the set of values

𝑑𝑜𝑚(𝐴)

satisfying all relevant predicates

(𝐴, 𝑜𝑝, 𝑣𝑎𝑙) ∈ 𝑅(𝑄)

𝑄

does not specify any predicate on

𝐴

, i.e., wildcards of the

form

𝐴 ∈ ∗

, then

𝑅

𝑄

(𝐴)

𝑑𝑜𝑚(𝐴)

. We dene the query range as

𝐴∈ D

𝐴

𝑅

𝑄

(𝐴)

, which is a hyper-rectangle of

𝐴

dimension. If

𝑄 is clear from the context, we use 𝑅(𝐴) instead of 𝑅

𝑄

(𝐴).

2.2 Taxonomy and Trade-Os

For a high-level view of learned estimators supporting joins, we

provide a taxonomy in Table 1. We divide the estimators as query-

/data-driven methods (Query/Data in the Category dimension).

We explain each dimension along with the trade-os of learned

estimators in Figure 1.

Category.

Query-driven methods use discriminative models that are

trained on a set of labeled training queries

(𝑄

′

, 𝑐𝑎𝑟𝑑 (𝑄

′

))

to predict

the

𝑐𝑎𝑟𝑑(𝑄)

for a given query

𝑄

. To take

𝑄

as an input to an ML

model,

𝑇 (𝑄)

𝐽 (𝑄)

, and

𝑅(𝑄)

are featurized into numerical vectors

(embeddings). We can then regard the problem as indirectly learning

a distribution from these embeddings to (normalized)

𝑐𝑎𝑟𝑑(𝑄)

, i.e.,

how will 𝑐𝑎𝑟𝑑(𝑄) change if we slightly perturb 𝑄?

Data-driven methods use generative models that are trained from

the data without labeled queries. These models learn the joint dis-

tribution

𝑃

𝑉

𝐴

) = 𝑃

𝑉

(𝐴

, 𝐴

, ..., 𝐴

𝑛

)

of the data, where

𝑉

is the

full outer join of the tables

𝑇

using PK-FK joins

𝐽

, and each

𝐴

𝑖

∈ D

𝐴

is regarded as a random variable over

𝑑𝑜𝑚(𝐴

𝑖

)

. For any

𝑎

𝑖

∈ 𝑑𝑜𝑚(𝐴

𝑖

)

over

𝑖

𝑃

𝑉

(𝐴

= 𝑎

, ..., 𝐴

𝑛

= 𝑎

𝑛

)

is dened as the

fraction of tuples

(𝑎

, ..., 𝑎

𝑛

)

𝑉

. Once a model is trained, to pre-

dict

𝑐𝑎𝑟𝑑(𝑄)

𝑄

is translated into its query range (hyper-rectangle).

Its query density,

𝑃

𝑉

(𝑄) B 𝑃

𝑉

(𝐴

∈ 𝑅(𝐴

), ..., 𝐴

𝑛

∈ 𝑅(𝐴

𝑛

))

, is

estimated instead of

𝑐𝑎𝑟𝑑(𝑄)

directly. Since

𝑃

𝑉

(𝑄)

represents the

fraction of tuples in the query range,

𝑐𝑎𝑟𝑑(𝑄)

can be induced as

|𝑉 | · 𝑃

𝑉

(𝑄). We can also rewrite 𝑃

𝑉

(𝑄) using an expectation as:

𝑃

𝑉

(𝐴

∈ 𝑅 (𝐴

), ..., 𝐴

𝑛

∈ 𝑅 (𝐴

𝑛

)) = E

𝑡∼𝑉



𝑖

𝑡 [𝐴

𝑖

] ∈𝑅 (𝐴

𝑖

)



[28],

(1)

where

𝑐

is an indicator variable; the value is 1 if

𝑐

is true and 0

otherwise.

𝑡

is a tuple in

𝑉

with projection on column(s)

𝐴

𝑡 [𝐴]

However,

𝑐𝑎𝑟𝑑(𝑄) = |𝑉 | · 𝑃

𝑉

(𝑄)

holds i

𝑇 (𝑄) = D

𝑇

, where

each tuple

𝑟

in the result of

𝑄

is a tuple in

𝑉

. If

𝑇 (𝑄) ⊊ D

𝑇

a tuple

𝑟

in the result of

𝑄

appears

𝑚

times in

𝑉

, where

𝑚 =

|𝑟 ⊲⊳ ( ⊲⊳

𝑇 ∈D

𝑇

\𝑇 (𝑄)

𝑇 ) |

. Therefore,

|𝑉 | · 𝑃

𝑉

(𝑄)

would count

𝑟

𝑚 times, but 𝑟 must be counted only once in computing 𝑐𝑎𝑟𝑑 (𝑄).

To correct this fanout eect, the

above is divided by the fanout

𝑓

of each

𝑡 ∈ 𝑉

[

]. To compute

𝑓

, a pairwise fanout column

𝐹

𝐽

added to

𝐴

for each PK-FK join

𝐽 = (𝑇

𝑎

,𝑇

𝑏

) ∈ D

𝐽

, storing

|𝑡

𝑎

⊲⊳

𝑇

𝑏

for every

𝑡

𝑎

∈ 𝑇

𝑎

. Then,

𝑓

is computed as

𝑇

𝑏

∉𝑇 (𝑄)

𝑡 [𝐹

(𝑇

𝑎

,𝑇

𝑏

)

]

For example, if

𝑇

= {𝑇

,𝑇

}

𝐽

= {(𝑇

,𝑇

), (𝑇

,𝑇

)}

, and

𝑇 (𝑄) = {𝑇

}

, then

𝑓 = 𝑡 [𝐹

(𝑇

,𝑇

)

] · 𝑡 [𝐹

(𝑇

,𝑇

)

]

. If

𝑇 (𝑄) = {𝑇

}

, then

𝑓 = 𝑡 [𝐹

(𝑇

,𝑇

)

]

. In addition, a Boolean not-null column

𝑁

𝑇

for each

table

𝑇 ∈ D

𝑇

is added to

𝐴

;

𝑡 [𝑁

𝑇

]

is true i a tuple

𝑡

contains

𝑇

Since we consider inner joins only, we should only count the tuples

𝑡 ∈ 𝑉 where 𝑡 [𝑁

𝑇

] is true for every 𝑇 ∈ 𝑇 (𝑄). Altogether,

𝑐𝑎𝑟𝑑(𝑄) = |𝑉 | · E

𝑡∼𝑉



𝑖

𝑡 [𝐴

𝑖

] ∈𝑅 (𝐴

𝑖

)

𝑇 ∈𝑇 (𝑄)

𝑡 [𝑁

𝑇

]

𝑇

𝑏

∉𝑇 (𝑄)

𝑡 [𝐹

(𝑇

𝑎

,𝑇

𝑏

)

]



(2)

is estimated at inference (e.g., via sampling), and

|𝑉 |

is precom-

puted once in

𝑂 (

𝑇 ∈D

𝑇

|𝑇 |)

time using dynamic programming

(DP), assuming that the schema is acyclic [

]. From the DP,

auxiliary data called join count tables (JCTs) are also precomputed,

and are used to sample unbiased training tuples from 𝑉 [28].

Figure 1 shows the performance of learned estimators over vary-

ing database sizes, and we focus on the trade-os of query- and

data-driven methods. Each method has a three-point trajectory over

three databases (please refer to Section 3.1 for details),

𝐷

𝐼𝑀𝐷𝐵−𝑠𝑚𝑎𝑙𝑙

(triangle),

𝐷

𝐼𝑀𝐷𝐵−𝑚𝑒𝑑𝑖𝑢𝑚

(square), and

𝐷

𝐼𝑀𝐷𝐵−𝑙𝑎𝑟𝑔𝑒

(circle), given

a xed workload

𝑊

𝐼𝑀𝐷𝐵−𝑠𝑚𝑎𝑙𝑙

. The q-error measures accuracy, de-

ned as

max(

𝑐𝑎𝑟𝑑(𝑄)/𝑐𝑎𝑟𝑑(𝑄),𝑐𝑎𝑟𝑑(𝑄)/

𝑐𝑎𝑟𝑑(𝑄))

[

], where the

hat (

) denotes estimates. If

𝑐𝑎𝑟𝑑(𝑄)

is less than 1, it is

set to 1. We can rst observe that accurate methods have larger infer-

ence time, and larger models require

larger training time in general.

Query-driven methods tend to have higher errors than data-

driven methods, since query-driven methods heavily depend on

training queries. They are accurate only if the distributions of train-

ing and test queries are similar. Note that the set of test queries in

Figure 1 is xed. As

𝑇

and

𝐴

increase, the training queries

Session 17: Query Processing and Optimization 2

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

1215

of 14

免费下载

关注

评论