# 1. Cost Models
## Cost-Based Query Planning
- 在当前数据库状态下，估算 执行特定 query plan 的成本
- 估算只在内部有意义（比如不同 DB 的 cost 数值不具备可比较性）
## Cost Model Components
- **Choice #1: Physical Costs**
- 预测 CPU cycles，IO，cache miss，RAM 占用，pre-fetching 等等
- 严重依赖硬件
- **Choice #2: Logical Costs**
- 估算每个 operator 结果集大小（比如 scan 多少记录）
- 与 operator 的算法无关
- 估算结果集大小不容易（算子间结果集有依赖）
- **Choice #3: Algorithmic Costs**
- operator 算法实现的复杂度
## Disk-Based DBMS Cost Model
- 磁盘的访问次数始终主导着查询的执行时间
- CPU 开销可以忽略
- 必须考虑顺序 vs. 随机 IO
- 如果 DBMS 可以访问控制 buffer management，则更容易建模
- 我们可以知道淘汰策略、pinning，并假设独占磁盘访问
## Postgres Cost Model
- 使用 magic constant factor 作为权重来 组合 CPU 和 IO 的 costs
- 默认配置：
- 在内存中处理一个 tuple 比从磁盘读取一个 tuple 快 400 倍
- 顺序IO 是 随机IO 的 4 倍
- [Doc: Planner Cost Constants](https://www.postgresql.org/docs/current/runtime-config-query.html#RUNTIME-CONFIG-QUERY-CONSTANTS)
## IBM DB2 Cost Model
包含如下多种 cost：
- Database characteristics in system catalogs(schema、indexes等)
- Hardware environment（microbenchmarks确定权重）
- Storage device characteristics（mircobenchmarks）
- Communications bandwidth（仅限分布式）
- Memory resources（buffer pools、sort heaps）
- Concurrency Envrionment
- 平均用户数
- Isolation level / blocking
- Number of available locks
## In-Memory DBMS Cost Model
- 不涉及 IO costs，只需要考虑 CPU 和 内存访问的 cost
- memory cost 很难控制因为 DBMS 无法干涉 cache management
- 无法感知 replacement、pinning、shared caches、NUMA
- CPU cost 可以根据每个 operator 处理的 tuples 数量相对合理地估计
## Smallbase Cost Model
- Two-phase model that automatically generates hardware costs from a logical model.
- **Phase #1 : Identify Execution Primitives**
- DBMS 执行查询时的一系列操作
- 例如：谓词求值、index probe、sorting
- **Phase #2: Microbenchmark**
- 启动后，profile 每个操作来计算它的 CPU / memory costs
- 这些测量值用于根据 table size 计算 operator cost 的公式中。
-----
# 2. Cost Estimation
## Selectivity
- 定义：一个 operator 的 selectivity 指的是一个 predicate 访问数据的百分比
- 即 tuple 满足 predicate 的概率
- DBMS 如何预估 selectivities：
- Domain constraints
- Precomputed Statistics（Zone Maps）
- Histograms / Approximations
- Sampling
## Observation
- 每个 operator 处理的 tuples 数量取决于三个因素：
- 每个 table 的 access methods（sequential scan、index scan）
- The distribution of values in the database's attributes（estimation stuff）
- query 中使用的 predicates
- 简单的查询很容易估算，很多复杂的查询却很难
## Approximations
- 维护 database 的精确统计很昂贵、且很慢
- 使用 **sketches** 这样的近似数据结构来生成误差有界（error-bounded）的预估
- Count Distinct
- Quantiles
- Frequent Items
- Tuple Sketch
- [Yahoo! Sketching Library](https://github.com/apache/datasketches-website/)
## Sampling
- Execute a predicate on a random sample of the target data set.
- 采样的 tuple 个数取决于 table 的大小
- **Approach #1 ： Maintain Read-Only Copy**
- offline 方式
- 定期 refresh 来保证准确度
- **Approach #2 ： Sample Real Tables**
- online 方式
- 实际去执行一部分查询
- Use READ UNCOMMITTED isolation，May read multiple versions of same logical tuple.
## Result Cardinality
- 每个 operator 输出的 tuples 数量等于：它的 selectivity 乘以 输入的 tuples 数量
- **Assumption #1: Uniform Data**
- values 的分布是均匀的（除了 heavy hitters）
- **Assumption #2: Independent Predicates**
- predicates 之间是相互独立的
- **Assumption #3: Inclusion Principle**
- join keys 的 domain 是重叠的：inner relation 中的每个 key 也存在于 outer table 中。
### Correlated Attributes
- [[15-optimization-2#^1b06de]]
- [IS QUERY OPTIMIZATION A “SOLVED” PROBLEM?](http://wp.sigmod.org/?p=1075)
### Column Group Statistics
- DBMS 可以跟踪一组 attributes 的统计信息，而非仅仅把它们看作是独立变量
- 只有商业系统支持（Oracle、DB2）
- 需要 DBA 手动指定
## Estimation Problem
```SQL
SELECT A.id
FROM A,B,C
WHERE A.id = B.id
AND A.id = C.id
AND B.id > 100
```
- 计算 base tables 的 cardinality
- $A \rightarrow |A|$
- $B.id > 100 \rightarrow |B| \times sel(B.id>100)$
- $C \rightarrow |C|$
- 计算 join 结果的 cardinality
- $A \bowtie B = (|A| \times |B| ) / max(sel(A.id=B.id), sel(B.id>100))$
- $(A \bowtie B) \bowtie C = (|A| \times |B| \times |C|) / max(sel(A.id=B.id), sel(B.id>100), sel(A.id=c.id))$
- join涉及的 tables 越多，预估就越可能出错
## Estimator Quality
- [How Good Are Query Optimizers, Really?](https://15721.courses.cs.cmu.edu/spring2017/papers/16-costmodels/p204-leis.pdf)
- 随着 joins 数量的增加，测试 DBMS 估算 cardinality 的正确性。
- 使用了 100k queries 比较了 5 款 DBMSs
- postgres: 基于估算的 cardinality 分配 hashtable for hash join
--------
# Lessons From The Germans
- 查询优化比一个快速的 engine 更重要
- cost-based join ordering 是必要的
- Cardinality estimates 通常是错误的
- 尽量使用不依赖于估算的 operators
- Hash joins + seq scans 是一个健壮的执行模型
- The more indexes that are available, the more brittle the plans become (but also faster on average)
- 在精确的模型上工作是浪费时间
- 最好是改进估算 cardinality
---------
# IBM DB2 - Learning Optimizer
- [LEO - DB2's LEarning Optimizer](https://dl.acm.org/doi/10.5555/645927.672349)
- 当 DBMS 执行查询扫描 table 时，更新 table statistics
- 检查 optimizer 的估算是否匹配遇到的真实数据，然后逐步更新它们。
----
# Parting Thoughts
- 对于内存 DBMSs，使用处理的 tuples 数量来作为 cost model 是合理的
- 但是计算也不可忽略
- sampling + sketches 是实现准确估算的方法。