高级数据库十七：优化器估价模型

谁借莪１个温暖的怀抱￠ 2022-06-02 07:35 231阅读 0赞

# Optimizer Cost Models #

我们在上两次讲查询优化文章中，提到了基于成本的查询计划，它们为数据库的当前状态生成执行特定查询计划的查询成本估计。

查询成本与我们上一节课讨论的优化器搜索查询策略的方式无关。就像二维平面上的最短路模型（不同的最短路算法，如Dikstra、Floyd）与它采用的距离模型（曼哈顿距离、欧氏距离、切比雪夫距离）无关。

那么这节课就是讲解不同的估价模型。

## Cost Models ##

选择1：物理成本

*  预测CPU周期，I/O，缓存未命中，RAM  
    消费，预取等
 *  严重依靠硬件。

选择2：逻辑成本

*  估计每个操作产生的结果大小（如，原表有109的数据，经过关系代数的select操作，还会剩下多少条数据）。
 *  独立于搜索算法，仅仅与逻辑查询计划有关。

选择3：算法成本

*  算法实现的复杂度

### DISK-BASED DBMS COST MODEL ###

通常来说，会结合计算规模继续计算，比如，我们需要线性扫描一张表，进行选择，那么我们的读取量将是整张表；如果我们是用索引访问，依据索引的层数，以及是随机访问的还是其他的方式有着不同的数据规模。

磁盘访问情况将始终主导查询的执行时间。

*  CPU成本可以忽略不计。
 *  可以轻松测量每个I/O的成本。
 *  对于分布式的数据库，网络I/O的成本主导着查询时间。

如果DBMS可以完全控制缓冲区管理，那么这更容易建模。

*  我们将知道如何更换策略，固定并假定独占访问磁盘。

### POSTGRES COST MODEL ###

使用CPU和I/O时间的玄学常数加权来估计。

默认设置显然是对于没有大量内存的磁盘数据库：

*  在内存中处理元组比从磁盘读取元组要快400倍。
 *  顺序I/O比随机I/O快4倍。

### IBM DB2 COST MODEL ###

结合了多种模型

*  系统目录中的数据库特征硬件环境（微基准，很多时候会根据开机时或者其他时候测试的结果进行估计）
 *  存储设备特征（微基准）
 *  通信带宽（仅分布式数据库）
 *  内存资源（缓冲池，排序堆）
 *  并发环境  
    
    
     *  平均用户数量
     *  隔离级别/阻塞
     *  可用锁的数量

### IN-MEMORY DBMS COST MODEL ###

内存数据库的成本估计更难。

此模型中没有I/O成本，但现在我们必须考虑CPU和内存访问成本。  
内存成本更难估计，因为DBMS没有控制缓存管理，它也没有办法选择将哪些数据存入内存（数据存在磁盘中的时候，会选择有用的数据存入内存，并且会设置内存缓冲区）。

*  未知的替换策略，没有共享缓存，非一致的内存访问。

每个运算符处理的元组数量是用于估计CPU成本的合理依据。

### SMALLBASE COST MODEL ###

两阶段模型，从逻辑模型自动生成硬件成本。

阶段1：识别执行原语

*  执行查询时，DBMS执行的操作的列表
 *  例子：谓词（>，<等），索引访问，排序。

第二阶段：Microbenchmark

*  在启动时，操作系统会去计算CPU/内存成本
 *  这些测量值用于根据表格大小计算操作成本的公式中。

### COST MODELS IN CASCADES ###

自顶向下的优化器，上面的搜索节点不知道其子节点的操作符，也就不知道作为输入传递给操作的元组数量。所以只能估计成本的上下界。

逻辑估计是估计该操作符的“最坏情况”情况。

*  上限：逻辑估计成本
 *  下限：物理估计成本

这个的例子在后面会有。

## Cost Estimation ##

每个运算符处理的元组数目取决于三个因素：

*  每个表格可用的访问方法
 *  数据库属性中值的分配
 *  查询中使用的谓词

简单的查询很容易估计。  
更复杂的查询不是。

### SELECTIVITY ###

运算符的选择性是谓词（或者其他限制）所访问的数据的百分比。

*  作为在任何给定元组上的谓词是否被满足的概率来建模。

DBMS使用以下方法估算选择性：

*  域约束
 *  预先计算的统计（区域图）
 *  直方图/近似值
 *  抽样

### IBM DB2 – LEARNING OPTIMIZER ###

在正常查询处理期间，DBMS扫描表时更新表统计信息。

检查优化器的估计值是否与实际数据中遇到的估计值相匹配，并逐步更新它们。

IBM DB2的LEO系统，实际效果特别糟糕，所以现在的默认状态是关闭的。

### APPROXIMATIONS ###

保存有关数据库的确切统计数据是昂贵和缓慢的。

使用称为sketches的近似数据结构来生成有误差的估计值。

*  计数不同
 *  分位数
 *  频繁项目
 *  Tuple素描  
    查看[Yahoo! Sketches Library][Yahoo_ Sketches Library]。

### SAMPLING ###

对目标数据集的随机样本执行一个谓词。

要检查的元组数量取决于表的大小。

DBMS可以使用READ UNCOMMITTED隔离执行此采样，即，不用关心其他正在执行的事务。因为仅仅是用于估计，不用担心数据的问题。

### RESULT CARDINALITY ###

假设1：Uniform Data

*  价值的分布（特别重的数据除外）是一样的。

假设2：Independent Predicates

*  属性的限制是独立的

假设3：Inclusion Principle

*  连接键的域重叠使得内部关系中的每个键也将存在于外部表中。

假设非常的少，在现实的工业界中，各个公司应该有更多有意义的假设，但是他们都不愿意公布出来。

### CORRELATED ATTRIBUTES ###

考虑一个汽车数据库：

*  \# of Makes = 10, \# of Models = 100

和以下查询：

*  （make =“Honda”AND model =“Accord”）

在独立性和一致性的假设下，选择后的结果是：

*  1/10×1/100 = 0.001

但是真是的结果是1/100 = 0.01

#### COLUMN GROUP STATISTICS ####

DBMS可以将一组属性进行统计，而不仅仅是将它们全部视为独立变量。

*  仅在商业系统中支持。
 *  需要DBA手动声明。

### ESTIMATION PROBLEM ###

![15153869694914.jpg][]

对于左侧的查询，我们花了一个简单的查询树作为我们评估查询代价的模型。

那么，对于最底层，我们就可以明确的知道A，B，C三个的大小，以及B.id>100的大小。

对于第二层的JOIN，我们估计起来就只能估计一个上限。

同样的，对于第三层的JOIN我们也只能估计一个上限，而且这个上限是在某个上限的基础上进行的，也就造成了更大的误差。

随着查询复杂度的增大，查询模型也更加复杂，所以查询树的复杂，那么估算的结果也就越发不准确。

## 参考资料 ##

[课件][Link 1]

[Yahoo_ Sketches Library]: https://datasketches.github.io
[15153869694914.jpg]: https://lh3.googleusercontent.com/-tvmOb0yiHzY/WlL5azcwkoI/AAAAAAAAAd0/CVgp_ThL07Ago03GdhNOE7rAkywzu6emgCHMYCw/I/15153869694914.jpg
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/16-costmodels.pdf