open-courses
Search…
公开课笔记
CMU 15-445/645 Database Systems
Relational Data Model
Advanced SQL
Database Storage
Buffer Pools
Hash Tables
Tree Indexes
Index Concurrency Control
Query Processing
Sorting&Aggregations
Join Algorithms
Query Optimization
Parallel Execution
Embedded Database Logic
Concurrency Control Theory
Two Phase Locking
Timestamp Ordering Concurrency Control
Multi-Version Concurrency Control
Logging Schemes
Database Recovery
Introduction to Distributed Databases
Distributed OLTP Databases
Distributed OLAP Databases
UCB - CS162
OS intro
Introduction to the Process
Processes, Fork, I/O, Files
I/O Continued, Sockets, Networking
Concurrency: Processes & Threads
Cooperating Threads, Synchronization
Semaphores, Condition Variables, Readers/Writers
Scheduling
Resource Contention & Deadlock
Address Translation, Caching
File System (18,19,20)
Distributed Systems, Networking, TCP/IP, RPC (21,22)
Distributed Storage, Key-Value Stores, Security (23)
Security & Cloud Computing (24)
Topic: Ensuring Data Reaches Disk
MIT - 6.006
Sequence and Set Interface
Data Structure for Dynamic Sequence Interface
Computation Complexity
Algorithms and Computation
Structure Of Computation
Graph & Search
Tree & Search
Weighted Shortest Paths
String Matching, Karp-Rabin
Priority Queue Interface & Implementation
Dictionary Problem & Implementation
Sorting
Dynamic Programming
Backtracking
Self-Balancing Tree
MIT - 6.824
2PC & 3PC
Introduction and MapReduce
RPC and Threads
Primary/Backup Replication
Lab: Primary/Backup Key/Value Service
Google File System (GFS)
Raft
Lab: Raft - Leader Election
Lab: Raft - Log Replication
Stanford-CS107
原始数据类型及相互转化
指鹿为马
泛型函数
泛型栈
运行时内存结构
从 C 到汇编
函数的活动记录
C 与 C++ 代码生成
编译的预处理过程
编译的链接过程
函数的活动记录续、并发
从顺序到并发和并行
信号量与多线程 1
信号量与多线程 2
复杂多线程问题
函数式编程 - Scheme 1
函数式编程 - Scheme 2
函数式编程 - Scheme 3
函数式编程 - Scheme 4
函数式编程 - Scheme 5
Python 基础
MIT - 6.001 - SICP
什么是程序
程序抽象
替代模型
时间/空间复杂度
数据抽象
高阶函数
Symbol
数据驱动编程与防御式编程
数据抽象中的效率与可读性
数据修改
环境模型
面向对象-消息传递
面向对象 - Scheme 实现
构建 Scheme 解释器
Eval-Apply Loop
Normal Order (Lazy) Evaluation
通用机
寄存器机器
子程序、栈与递归
在寄存器机器中执行
内存管理
MIT - 6.046
Randomized Algorithms
Skip Lists
System Design
Twitter
Cache Consistency & Coherence
DDIA 笔记
Replication
Transactions
The Trouble with Distributed Systems
Consistency & Consensus
Papers We Love
Consistent Hashing and Random Trees (1997)
Dynamic Hash Tables (1988)
LFU Implementation With O(1) Complexity (2010)
Time, Clocks, and the Ordering of Events in a Distributed System (1978)
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
Release It 笔记
Anti-patterns & Patterns in Microservice Architecture
Database Design
Log Structured Merge (LSM) Tree & Usages in KV Stores
Prometheus
Powered By
GitBook
Query Optimization
SQL 语句让我们能够描述想要获取的数据,而 DBMS 负责来根据用户的需求来制定高效的查询计划。不同的查询计划的效率可能出现多个数量级的差别,如 Join Algorithms 一节中的 Simple Nested Loop Join 与 Hash Join 的时间对比 (1.3 hours vs. 0.45 seconds)。
Query Optimizer 第一次出现在 IBM System R,那时人们认为 DBMS 指定的查询计划永远无法比人类指定的更好。System R 的 optimizer 中的一些理念至今仍在使用。
Query Optimization Techniques
Heuristics/Rules
Rewrite the query to remove stupid/inefficient things
Does not require a cost model
Cost-based Search
Use a cost model to evaluate multiple equivalent plans and pick the one with the lowest cost
Query Planning Overview
这里的 Rewriter 负责 Heuristics/Rules,Optimizer 则负责 Cost-based Search。
Query Rewriting
如果两个关系代数表达式 (Relational Algebra Expressions) 如果能产生相同的 tuple 集合,我们就称二者等价。DBMS 可以通过一些 Heuristics/Rules 来将关系几何表达式转化成成本更低的等价表达式,从而达到查询优化的目的。这些规则通常试用于所有查询,如:
Predicate Pushdown
Projections Pushdown
Predicate Pushdown
Predicate 通常有很高的选择性,可以过滤掉许多无用的数据。将 Predicate 推到查询计划的底部,可以在查询开始时就更多地过滤数据,举例如下:
核心思想如下:
越早过滤越多数据越好
重排 predicates,使得选择性大的排前面
将复杂的 predicate 拆分,然后往下压,如
X=Y AND Y=3
可以修改成
X=3 AND Y=3
Projections Pushdown
本方案对列存储数据库不适用。在行存储数据库中,越早过滤掉不用的字段越好,因此将 Projections 操作往查询计划底部推也能够缩小中间结果占用的空间大小,举例如下:
Cost-based Search
除了 Predicates 和 Projections 以外,许多操作没有通用的规则,如 Join:Join 操作既符合交换律又符合结合律,等价关系代数表达式数量庞大,这时候就需要一些成本估算技术,将过滤性大的表作为 Outer Table,小的作为 Inner Table,从而达到查询优化的目的。
Cost Estimation
一个查询需要花费多长时间,取决于许多因素
CPU: Small cost; tough to estimate
Disk: #block transfers
Memory: Amount of DRAM used
Network: #messages
但本质上取决于:
整个查询过程需要读入和写出多少 tuples
因此 DBMS 需要保存每个 table 的一些统计信息,如 attributes、indexes 等信息,有助于估计查询成本。值得一提的是,不同的 DBMS 的搜集、更新统计信息的策略不同。
Statistics
通常,DBMS 对任意的 table R,都保存着以下信息:
N
R
N_R
N
R
:R 中 tuples 的数量
V
(
A
,
R
)
V(A, R)
V
(
A
,
R
)
:R 中 A 属性的不同取值 (distinct values) 个数
A
m
a
x
,
A
m
i
n
A_{max}, A_{min}
A
ma
x
,
A
min
:A 属性取值的最大和最小值
利用上面两条数据,可以得到 selection cardinality,即 R 中 A 属性下每个值的平均记录个数:
S
C
(
A
,
R
)
=
N
R
/
V
(
A
,
R
)
SC(A, R) = N_R / \ V(A, R)
SC
(
A
,
R
)
=
N
R
/
V
(
A
,
R
)
需要注意的是,这种估计假设 R 中所有数据在 A 属性下均匀分布 (data uniformity)。
利用以上信息和假设,DBMS 可以估计不同 predicates 的 selectivity:
Equality
Range
Negation
Conjunction
Disjunction
Equality Predicate
SELECT
*
FROM
people
WHERE
age
=
2
;
设 people 表中有 5 条个人信息,即
N
R
=
5
N_R = 5
N
R
=
5
所有信息中的 age 有 5 个取值,即
V
(
a
g
e
,
p
e
o
p
l
e
)
=
5
V(age, people) = 5
V
(
a
g
e
,
p
eo
pl
e
)
=
5
:
s
e
l
(
A
=
c
o
n
s
t
a
n
t
)
=
S
C
(
P
)
/
V
(
A
,
R
)
=
1
5
sel(A=constant) = SC(P) / V(A, R) = \frac{1}{5}
se
l
(
A
=
co
n
s
t
an
t
)
=
SC
(
P
)
/
V
(
A
,
R
)
=
5
1
Range Predicate
SELECT
*
FROM
people
WHERE
age
>=
2
;
可以利用
A
m
a
x
,
A
m
i
n
A_{max}, A_{min}
A
ma
x
,
A
min
来估计:
s
e
l
(
A
>
=
a
)
=
(
A
m
a
x
−
a
)
/
(
A
m
a
x
−
A
m
i
n
)
sel(A>= a) = (A_{max}-a)/(A_{max}-A_{min})
se
l
(
A
>=
a
)
=
(
A
ma
x
−
a
)
/
(
A
ma
x
−
A
min
)
Negation Query
SELECT
*
FROM
people
WHERE
age
!=
2
;
利用 equality query 可以反向推导出 negation query 的情况:
s
e
l
(
n
o
t
P
)
=
1
−
s
e
l
(
P
)
=
1
−
S
C
(
a
g
e
=
2
)
=
4
5
sel(not \ P) = 1 - sel(P) = 1 - SC(age=2) = \frac{4}{5}
se
l
(
n
o
t
P
)
=
1
−
se
l
(
P
)
=
1
−
SC
(
a
g
e
=
2
)
=
5
4
实际上这里所谓的 Selectivity 就是基于 uniformly distribution 假设下的 Probability。
Conjunction Query
SELECT
*
FROM
people
WHERE
age
=
2
AND
name
LIKE
'A%'
;
若假设两个 predicates 之间相互独立,则可以推导出:
s
e
l
(
P
1
∧
P
2
)
=
s
e
l
(
P
1
)
∙
s
e
l
(
P
2
)
sel(P1 \wedge P2) = sel(P1)\bullet sel(P2)
se
l
(
P
1
∧
P
2
)
=
se
l
(
P
1
)
∙
se
l
(
P
2
)
其韦恩图如下所示:
Disjunction Query
SELECT
*
FROM
people
WHERE
age
=
2
OR
name
LIKE
'A%'
;
若假设两个 predicates 之间相互独立,则可以推导出:
s
e
l
(
P
1
∨
P
2
)
=
s
e
l
(
P
1
)
+
s
e
l
(
P
2
)
−
s
e
l
(
P
1
∧
P
2
)
=
s
e
l
(
P
1
)
+
s
e
l
(
P
2
)
−
s
e
l
(
P
1
)
∙
s
e
l
(
P
2
)
sel(P1 \vee P2) = sel(P1) + sel(P2) - sel(P1 \wedge P2) = sel(P1) + sel(P2) - sel(P1)\bullet sel(P2)
se
l
(
P
1
∨
P
2
)
=
se
l
(
P
1
)
+
se
l
(
P
2
)
−
se
l
(
P
1
∧
P
2
)
=
se
l
(
P
1
)
+
se
l
(
P
2
)
−
se
l
(
P
1
)
∙
se
l
(
P
2
)
其韦恩图如下所示:
Joins
Result Size Estimation for Joins
考虑最通用的情况:假设
R
c
o
l
s
∩
S
c
o
l
s
=
{
A
}
R_{cols} \cap S_{cols} = \{A\}
R
co
l
s
∩
S
co
l
s
=
{
A
}
,其中 A 不是 R 或 S 的 key,可以从两个方向思考:
对 R 中的每个 tuple,找到 S 中相应的 tuples:
e
s
t
S
i
z
e
≈
N
R
∙
N
S
/
V
(
A
,
S
)
estSize \approx N_{R} \bullet N_{S} / V(A, S)
es
tS
i
ze
≈
N
R
∙
N
S
/
V
(
A
,
S
)
对 S 中的每个 tuple,找到 R 中相应的 tuples:
e
s
t
S
i
z
e
≈
N
R
∙
N
S
/
V
(
A
,
R
)
estSize \approx N_{R} \bullet N_{S} / V(A, R)
es
tS
i
ze
≈
N
R
∙
N
S
/
V
(
A
,
R
)
综合两个方向,取小的:
e
s
t
S
i
z
e
≈
N
R
∙
N
S
/
m
a
x
(
{
V
(
A
,
S
)
,
V
(
A
,
R
)
}
)
estSize \approx N_R \bullet N_S / max(\{V(A, S), V(A, R)\})
es
tS
i
ze
≈
N
R
∙
N
S
/
ma
x
({
V
(
A
,
S
)
,
V
(
A
,
R
)})
Samling
现代 DBMSs 也会使用采样技术来降低成本估计本身的成本,比如面对如下查询:
SELECT
AVG
(
age
)
FROM
people
WHERE
age
>
50
;
我们可以等间隔从表中对数据采样:
然后再估计:
当然,为了避免重复采样,DMBS 会保存一份采样表,待 table 的变动较大时,再更新采样表。
CMU 15-445/645 Database Systems - Previous
Join Algorithms
Next - CMU 15-445/645 Database Systems
Parallel Execution
Last modified
3yr ago
Copy link
Outline
Query Optimization Techniques
Query Rewriting
Cost-based Search