open-courses
  • 公开课笔记
  • 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
On this page
  • Query Optimization Techniques
  • Query Rewriting
  • Cost-based Search
  1. CMU 15-445/645 Database Systems

Query Optimization

PreviousJoin AlgorithmsNextParallel Execution

Last updated 6 years ago

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

这里的 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,都保存着以下信息:

利用上面两条数据,可以得到 selection cardinality,即 R 中 A 属性下每个值的平均记录个数:

需要注意的是,这种估计假设 R 中所有数据在 A 属性下均匀分布 (data uniformity)。

利用以上信息和假设,DBMS 可以估计不同 predicates 的 selectivity:

  • Equality

  • Range

  • Negation

  • Conjunction

  • Disjunction

Equality Predicate

SELECT * FROM people WHERE age = 2;

Range Predicate

SELECT * FROM people WHERE age >= 2;

Negation Query

SELECT * FROM people WHERE age != 2;

利用 equality query 可以反向推导出 negation query 的情况:

实际上这里所谓的 Selectivity 就是基于 uniformly distribution 假设下的 Probability。

Conjunction Query

SELECT * FROM people
 WHERE age = 2
   AND name LIKE 'A%';

若假设两个 predicates 之间相互独立,则可以推导出:

其韦恩图如下所示:

Disjunction Query

SELECT * FROM people
 WHERE age = 2
    OR name LIKE 'A%';

若假设两个 predicates 之间相互独立,则可以推导出:

其韦恩图如下所示:

Joins

Result Size Estimation for Joins

综合两个方向,取小的:

Samling

现代 DBMSs 也会使用采样技术来降低成本估计本身的成本,比如面对如下查询:

SELECT AVG(age)
  FROM people
 WHERE age > 50;

我们可以等间隔从表中对数据采样:

然后再估计:

当然,为了避免重复采样,DMBS 会保存一份采样表,待 table 的变动较大时,再更新采样表。

NRN_RNR​ :R 中 tuples 的数量

V(A,R)V(A, R)V(A,R) :R 中 A 属性的不同取值 (distinct values) 个数

Amax,AminA_{max}, A_{min}Amax​,Amin​ :A 属性取值的最大和最小值

SC(A,R)=NR/ V(A,R)SC(A, R) = N_R / \ V(A, R)SC(A,R)=NR​/ V(A,R)

设 people 表中有 5 条个人信息,即 NR=5N_R = 5NR​=5 所有信息中的 age 有 5 个取值,即 V(age,people)=5V(age, people) = 5V(age,people)=5:

sel(A=constant)=SC(P)/V(A,R)=15sel(A=constant) = SC(P) / V(A, R) = \frac{1}{5}sel(A=constant)=SC(P)/V(A,R)=51​

可以利用 Amax,AminA_{max}, A_{min}Amax​,Amin​ 来估计:

sel(A>=a)=(Amax−a)/(Amax−Amin)sel(A>= a) = (A_{max}-a)/(A_{max}-A_{min})sel(A>=a)=(Amax​−a)/(Amax​−Amin​)
sel(not P)=1−sel(P)=1−SC(age=2)=45sel(not \ P) = 1 - sel(P) = 1 - SC(age=2) = \frac{4}{5}sel(not P)=1−sel(P)=1−SC(age=2)=54​
sel(P1∧P2)=sel(P1)∙sel(P2)sel(P1 \wedge P2) = sel(P1)\bullet sel(P2) sel(P1∧P2)=sel(P1)∙sel(P2)
sel(P1∨P2)=sel(P1)+sel(P2)−sel(P1∧P2)=sel(P1)+sel(P2)−sel(P1)∙sel(P2)sel(P1 \vee P2) = sel(P1) + sel(P2) - sel(P1 \wedge P2) = sel(P1) + sel(P2) - sel(P1)\bullet sel(P2)sel(P1∨P2)=sel(P1)+sel(P2)−sel(P1∧P2)=sel(P1)+sel(P2)−sel(P1)∙sel(P2)

考虑最通用的情况:假设 Rcols∩Scols={A}R_{cols} \cap S_{cols} = \{A\}Rcols​∩Scols​={A} ,其中 A 不是 R 或 S 的 key,可以从两个方向思考:

对 R 中的每个 tuple,找到 S 中相应的 tuples: estSize≈NR∙NS/V(A,S)estSize \approx N_{R} \bullet N_{S} / V(A, S)estSize≈NR​∙NS​/V(A,S)

对 S 中的每个 tuple,找到 R 中相应的 tuples: estSize≈NR∙NS/V(A,R)estSize \approx N_{R} \bullet N_{S} / V(A, R)estSize≈NR​∙NS​/V(A,R)

estSize≈NR∙NS/max({V(A,S),V(A,R)})estSize \approx N_R \bullet N_S / max(\{V(A, S), V(A, R)\})estSize≈NR​∙NS​/max({V(A,S),V(A,R)})
Query Planning Overview