# Abstract
- Query optimizer 必须知道**如何以及何时**使用物化视图。
- 本论文提供了一种快速可扩展的算法，用于决策一个查询的部分或整体是否可以借助物化视图来计算，并且描述了如何将其集成到 transformation-based optimizers。
- 仍然**保持基于成本的优化**
生成多个 rewrites，然后优化器基于成本来选择最优的。
-------------
# 1. Introduction
- 使用物化视图可以带来数量级的加速。
- 需要解决的问题：
- **View design：** 决定物化什么视图，包括如何存储和索引
- **View maintenance：** 当基础表的数据更新后如何高效更新物化视图
- **View exploitation：** 如何有效利用物化视图来加速查询处理
- 在 transformation-based optimizer 中实现
在查询的子表达式上应用 local transformion rules，将子表达式进行替换（可能为物化视图）
这一过期可能会在优化期间中调用多次（每次针对不同的子表达式）
transformation-based optimizer 基于 [[cascades-optimizer | Cascades framework ]]
- 论文主要贡献：
- 高效的**视图匹配**算法（适用于 SPJG views）
- 一种新型的**索引结构**（索引视图的定义，而非视图的数据），匹配时可以快速缩小搜索范围到一小组候选视图上
> 论文只讨论将算法应用到 SPJG viewa 和 单个视图，算法是可以扩展到更多场景的。
- 我们的视图匹配算法是快速和可扩展的：
- 复杂查询需要调用多次，因此速度很关键
- 可扩展：高效地支持几千个视图（ query result cache 也可以看作是一种临时性的视图）
--------
# 2. Defining the problem
- SQL Server 2000 中的物化视图：
- 通过在已有的视图上创建**唯一的** **clustered index** 来实现物化视图，唯一意味着视图的输出必须包含一个 unique key。这是必要的，以确保视图可以增量更新
- clustered index 创建后，可以创建额外的二级索引
- 并非所有的视图都是可索引的：
> An indexable view must be defined by a single-level SQL statement containing selections, (inner) joins, and an optional group-by
- FROM 从句不能包含 derived tables（必须是 base tables，不允许子查询）
- 聚合视图的输出必须包含所有 grouping 列（它们决定了 key）
例子：
```sql
-- 创建普通 view
create view v1 with schemabinding as
select p_partkey, p_name, p_retailprice,
count_big(*) as cnt,
sum(l_extendedprice*l_quantity) as gross_revenue
from dbo.lineitem, dbo.part
where p_partkey < 1000
and p_name like ‘%steel%’
and p_partkey = l_partkey
group by p_partkey, p_name, p_retailprice
-- 物化视图，将结果存储到 clustered index
create unique clustered index v1_cidx on v1(p_partkey)
-- 在物化视图上创建二级索引
create index v1_sidx on v1( gross_revenue, p_name)
```
- **View Matching with Single-View Substitutes**
给定一个关系表达式（SPJG），找到所有可以计算该表达式的物化视图（SPJG）。
对于找到的每个视图，构建跟原表达等价的替代表达式。
不同的视图可以用来计算一个查询的不同部分。
生成的所有替换都会像正常方式一样参与 CBO。
此外，物化视图上的二级索引也会像普通 base tables 一样被考虑在内。
---------
# 3. Computing a query expression from a view
- 本章：如何判断某个表达式是否可以从一个视图中计算，以及如何构建替代表达式。
- 算法利用了四种类型的约束：
- 列上的 not-null 约束
- 主键约束
- 唯一约束
- 外键约束
- 算法假定条件：
- 视图的 selection predicates 和 查询表达式都已经被转换转 CNF。
- 执行过 join elimination，因此查询和视图的表达式不包含冗余的 tables
## 3.1 Join-select-project views and queries
- 可以通过视图计算的查询表达式，必须满足以下条件：
1. 视图包含了查询表达式需要的所有行（我们只考虑单视图替换，如果是 union 多个视图则不需要） **行限制**
2. 所有需要的行都可以从视图中查询出来（有不意味着能查，例如 selection predicate 需要的列在视图中不存在） **列限制**
3. 查询的所有输出表达式（如投影）都可以从视图中计算出来 **列限制**
4. 正确的 duplication factor。即表达式的结果如果有重复的行，则重复次数也需要是正确的。
### 3.1.1 Column equivalence classes
设表达式的过滤谓词 $W=P_1\ \wedge P_2 \ \wedge \ \cdots \wedge \ P_n$ （ CNF 形式）
可以重写为 $W = PE \wedge PNE$，其中 PE 由列相等条件组成，即形式为 $T_i.C_p \ = \ T_i.C_q$ 。
在列相等的谓词应用完后，对于 PNE 谓词 和 output columns ， 一些列彼此之间是可以相互替换的（如 $C_p$ 和 $C_q$），是等价的。
可以通过 PE 条件来寻找列的等价类。
### 3.1.2 Do all required rows exist in the view
$W_q$：Query 的 where 条件
$W_v$：View 的 where 条件
Query的结果必须是 View 的子集。**这可以由 $W_q \implies Wv$** **来保证**。
需要一种算法来检测 $W_q \implies Wv$ 。
将谓词进行重写：
$W_q = P_{q,1} \wedge P_{q,2} \wedge \ \cdots \ \wedge P_{q,m}$
$W_v = P_{v,1} \wedge P_{v,2} \wedge \ \cdots \ \wedge P_{v,n}$
最简单保守的方法就是针对 $W_v$ 中的每个合取 $P_{v,i}$ ，检查是否匹配 $W_q$ 中的某个 $P_{v,i}$
如何检测两个合取是否匹配？
例如可以转换为字符串进行比较。缺点：无法匹配 $A > B$ 和 $B < A$
更复杂的：$(A/2 + B/5)\ast10 \ = \ A\ast5+B\ast2$
算法：将谓词分为三个组件，蕴含式变为：
$PE_q \wedge PR_q \wedge PU_q \implies PE_v \wedge PR_v \wedge PU_v$
- PE：所有列相等谓词
- PR：range predicates，形式 $T_i.C_p \ op \ c$，c为常量，op为
lt;$，$\leq$等
- PU：剩余的谓词
进一步将蕴含式切分为三步：
$(PE_q \wedge PR_q \wedge PU_q \implies PE_v) \\ \ \wedge \ (PE_q \wedge PR_q \wedge PU_q \implies PR_v) \ \wedge (PE_q \wedge PR_q \wedge PU_q \implies PU_v)$
再有 $(A\implies C) \implies (AB\implies C)$ ，最终将测试转换为：
- $(PE_q \implies PE_v)$ // Equijoin subsumption test
- $(PE_q \wedge PR_q) \implies PR_v$ // Range subsumption test
- $(PE_q \wedge PU_q) \implies PUv$ // Residual subsumption test
第一步执行完后，就可以应用列等价类对列进行 reroute（到其等价类）。