首页 > 其他分享 >论文笔记：An Overview of Query Optimization in Relational Systems

论文笔记：An Overview of Query Optimization in Relational Systems

时间：2022-10-01 15:35:09浏览次数：63  
标签：Join did Overview 查询 Dept Optimization Systems 代价 Emp

论文笔记：An Overview of Query Optimization in Relational Systems

这篇文章发表于 1998 年，是数据库系统查询优化领域的入门必读文章。

执行计划

image

物理算子构成的树状结构，每个节点都是一个物理算子（也就用于实现该算子功能的代码），称为执行计划，最后会交给执行引擎去执行。这个树状结构也表示了数据的流动方向。

查询优化

执行计划的复杂性体现在，算术表达式的等价转换以及物理算子的多种实现上。不同的执行计划的执行效率差别十分的大，所以谨慎的选择一个执行计划是一个非常重要和非常难的问题。通过上述表达，我们可以知道查询优化是一个搜索问题。

为了解决这个问题我们需要从以下三方面入手。

image

  1. 搜索空间（低代价）
  2. 代价估计（准确）
  3. 枚举算法（高效）

System-R

SPJ queries 搜索空间

引入 System-R 解释上述问题的实现方案，使用 Select-Project-Join (SPJ) queries，因为这个模型被广泛的应用于数据库系统的研究中。

SPJ 语句涉及到一个 linear scqucncc of join operations，如下图所示：
image

根据 Join 算子的 associative 和 commutative 性质， Figure2（a), (b) 等价。
image

代价模型

System-R 对于算子的代价评估主要考虑一下方面：

image

如果使用自底向上的方法遍历计划，那么上层的代价会依赖于下层算子的代价。

枚举算法

System-R 展示了两种重要的技术，动态规划和 interesting orders。
使用动态规划算法的基础是代价模型满足最优化原理。

动态规划

对于 SPJ queries 当我们要计算 k-join 的最优解时，需要知道 (k-1)-join 的最优解。

image

求 Join{R1, R2, R3, R4} 的最优解，我们可以从：

  1. Join{R1, R2, R3} 的最优解 + R4 的代价来获得
  2. Join{R1, R2, R4} 的最优解 + R3 的代价来获得
  3. Join{R1, R3, R4} 的最优解 + R2 的代价来获得
  4. Join{R2, R3, R4} 的最优解 + R1 的代价来获得

这样我们就不需要再去枚举 Join{R1, R2, R3, R4} 的所有情况了。
该算法的思路使用如下代码描述:

R = [R1, R2, R3, ..., Rn]
optjoin[i][j] # 表示第 j 个 i 长度的子集的最优代价。
opt = MAX_COST # 保存最后的最优方案
for i in enumerate{ R 的所有非空子集的长度}:
	for j in enumerate{所有长度为 i 的子集}:
		# Rk 为 i 长度的子集的所有 R 中，不在 i-1 长度中的那个 Rk
		optjoin[i][j] = min(optjoin[i-1][j]+cost(Rk), optjoin[i-1][j])
opt = optjoin[n][1]

因此可以将枚举规模：
$$O(n!)$$
降到枚举所有子集的问题规模:$$O(n2^{n-1})$$

Interesting Oders

对于 Join{R1, R2, R3}，如果 Join{R1, R2} 如果使用 sort-merge join，那么其结果是有序的，可以在对 R3 进行 Join 时提供额外的信息，加快 R3 的 Join 速度。如果 Join{R1, R2} 使用 nest-loop join 那其对 R3 的 Join 并没有帮助。Interesting Order 就是指考虑这样的情况。

System-R 的缺陷

System-R 框架同时也存在一些问题，不容易处理 Join 之外的代数变换。

Search Space

搜索空间取决于代数变换以及物理算子的多种实现。这个部分将介绍一些重要的代数变换，这些代数变换并不一定会减少代价，需要靠枚举算法来保证最后计划是最优的。
优化器的主要工作就是将 SQL parser 之后的语法树，经过一系列的转换，变成执行计划，也就是 Operator Tree。在这个变换的过程中，使用 logical operator tree (query trees) 来表示中间的数据结构，Figure2 就是 query tree。

Starburst 使用了 QGM(Query Graph Model) 来进行表示 SPJ queries。并介绍了其存的在问题，如下图所示：
img

Exodus 使用了 query tree 和 operator tree 在所有的优化阶段。

Commuting Between Operators

Join Sequence

System-R 它只能处理 linear sequences, 并且笛卡尔积被推迟到所有 Join 操作完成。

使用 bushy join 也就是 Figure2(b), 需要物化中间结果，可以得到更高效的执行计划，但是其也大大的增加了需要枚举的 search space。

推迟笛卡尔积可能会导致性能的下降尤其是在 OLAP 系统中。因为在 AP 系统中存在大量的维度表。

Outerjoin and Join

outerjoin 与 join 构成的 joins 序列是不能进行交换的。在特定条件下存在如下公式：

img

有了这个公式，我们就可以将大量的 Join 操作放到 Outerjoin 操作之前执行，因此可以对前置的 Join 进行变换来优化性能。

Group-By and Join

提前进行 Group-By，对于 SELECT DISTINCT 这样的语句，提前进行 Group-By 可以大量减少所需处理的 Tuple 数量。

img

如图所示，Group-By 操作不仅仅能在特定情况下进行下推，如 Figure4(b) 所示，还可以在特定场景下进行分阶段 Group-By。如 Figure4(c) 所示。

Reducing Multi-Block Queries to Single-Block

这部分介绍了如何在特定条件下进行子查询"打平"。

Merging Views

以 SELECT ANY 语句为例，有如下图所示公式：
img

如果 V 是一个 View，我们可以将其直接展开，然后应用各种 Join 的优化手段。这个过程要注意对 View 中的对象进行重命名。

Merging Nested Subqueries

考虑嵌套查询的情况，有如下 SQL

SELECT Emp.Name
FROM Emp
WHERE Emp.Dept# IN 
(
	SELECT Dept.Dept#
	FROM Dept
	WHERE Dept.Loc='Denver' AND Emp.Emp#=Dept.Mgr
)

在这个查询中外层的列 Emp.Emp# 出现在嵌套的子查询中，所以这个子查询称为关联子查询。

如果这个查询是非关联子查询，这个查询在遍历每个 Tuple 时，其子查询都会执行一次，可以看到的一个优化点是，我们可以只执行一次这个子查询。
但是如果碰到关联的子查询，如上 SQL，根据一些研究（参考引用论文）。我们可将其”打平“后得到如下 SQL

SELECT E.Name
FROM EMP E, Dept D
WHERE E.Dept# = D.Dept#
AND D.Loc='Denver' AND E.Emp#=D.Mgr

这个 query 等价于:

Semijoin(Emp, Dept, Empt.Dept#=Dept.Dept#) = Project(Join(Emp, Dept), Emp.*)

需要注意的是，当子查询中有 Agg 的时候就比较难以处理。有如下查询：

SELECT Dept.name
FROM Dept
WHERE Dept.num-of-machine >= (
	SELECT COUNT(Emp.*) FROM Emp
	WHERE Dept.name=Emp.Dept_name
);

这个查询需要从 Agg 中拉取数据还要不违反子查询的语义。保留 duplicate 和 nulls 是非常 tricky 的事情。当这个子查询中的谓词一直为假，这个子查询还是会返回一个 tuple，最后导致这个查询可能会返回tuple。如果采用第一部分，将子查询转成 Join 的方法，那么就不会返回 tuple。这样这个转换是的原 query 的语义发生了改变。
因此，当子查询中有 Agg 我们需要使用 outjoin 来进行转换。转换结果为

SELECT Dept.name
FROM Dept left outer join Empt
ON (Dept.name=Empt.dept_name)
GROUP BY Dept.name
HAVING Dept.num-of-machine < count(Emp.*);

除了上述描述的方法，另一种“打平”的技术是使用 table-expressions 或者 views。

Using Semijoin Like Techniques for Optimizing Multi-Block Queries

提供一种补充方法，有如下 SQL

CREATE VIEW  DepAvgSal As ( 
SELECT E.did, Avg(E.Sal) AS avgsal FROM Emp E 
GROUP BY  E.did);

SELECT E.did, E.Sal 
FROM Emp E, Dept D, DepAvgSal V 
WHERE  E.did = D.did AND E.did = V.did AND E.age < 30 AND  D.budget > 100k 
AND E.sal > V.avgsal

我们可以创建几个 View 仅仅让 Emp 和 Dept 进行 Join。所以有如下 SQL

CREATE VIEW partialresult AS
( SELECT E.id, E.sal, E.did
  FROM Emp E, Dept D
  WHERE E.did=D.did AND E.age<30 AND D.budget>100k
);
CREATE VIEW Filter AS
( SELECT DISTINCT P.did FROM PartialResult P);
CREATE VIEW LimitedAvgSal AS
( SELECT E.did, Avg(E.Sal) AS avgsal
  FROM Emp E, Filter F
  WHERE E.did=F.did GROUP BY E.did
);
SELECT P.eid, P.sal
FROM PartialResult P, LimitedDepAvgSal V
WHERE P.did=V.did AND P.sal>V.avgsal;

使用上述技术的时候也要考虑计算 View 代价和使用 View 减少的计算量之间的取舍。

统计信息和代价估计

需要考虑的资源包括

  1. CPU Time
  2. I/O cost
  3. memory
  4. bandwidth
  5. all of them

代价估计的计算过程必须高效，因为这个代码会被频繁的执行。

System-R 提供的基本代价评估框架

img

下面介绍如何高效的获取统计信息，如何传播它们。

Statistical Summaries Of Data

Statistical Information on Base Data

  1. the number of tuples。
  2. histograms(直方图)，直方图指的是将 column 中的值放入 k 个 bucket 中。使用直方图来
    表示数据的分布的情况。
  3. column 中的 max value, min value, second hightest/lowest value。
  4. distinct values。
  5. 列之间的关系，大多数系统值记录不同的 pair 数量。

Estimating Statistics on Base Data

数据量太大，为了更高效和准确的估计统计信息，使用抽样的方法。
对于大数据量，可能会丢失一些信息。

Propagation Of Statistical Information

由于存在大量的算子，所以信息还需要在算子间进行传播。

Cost Computation

除了 CPU，I/O，Communicattion 的代价，buffer 的使用情况也要考虑。

Enumeration Architectures

Enumeration Architectures 需要适应以下方面
search space, new transformation, new physical operator， change cost estimation techniques。
本文介绍了两种架构:

  1. Starburst
  2. Volcano/Cascades

Starburst

使用 QGM 表示一条 Query，然后介绍了 QGM 的是什么样的。

  1. query rewrite （进行 QGM 的等价转换（涉及到一系列规则），并没有代价信息的涉及）。
  2. plan optimization（使用一种特定的语言实现物理算子，加入代价估计）。

Volcano/Cascades

Volcano/Cascades 使用自顶向下的动态规划算法进行遍历 search space, 所以需要借助 memo 来实现。

Volcano/Cascades 与 Starburst 不同之处在于

  1. 不需要有两个阶段，所有的转换都是基于代数和代价的。
  2. 逻辑算子到物理算子的转换是一步实现的
  3. 不像 Starburst 要提前应用某种规则，Volcano/Cascades 是 goal-driven 的。

高级主题

分布式和并行并行数据库

介绍了分布式数据库的查询优化需要考虑节点通信代价以及多个节点间数据一致性。
并行数据库需要注意的一些问题，比如算子的执行的独立性，以及流水线。介绍了 XPRS 项目查询优化过程。

用户自定义函数

使用 UDF 函数可以将应用层应用的语义融入查询之中。
UDF 为查询优化的代价模型和枚举算法提出了新的问题。
UDF 难以优化是因为其语义复杂。

物化视图

通过物化中间结果来进行查询优化。

  1. 需要能将查询进行 reformulating，以便于应用中间结果。
  2. reformulating，会使代价增加。

其他优化点

  1. 推迟生成完整计划，以便利用运行时的一些信息。
  2. 考虑其他资源用于决定执行计划的选择。
  3. 适用于多媒体数据的查询。
  4. OLAP 系统的扩展 SQL。

CONCLUSION

查询优化不仅仅是等价转换，高效正确的 SQL 转换，代价度量，可扩展的枚举算法都十分重要和困难。了解现存的技术是十分必要的。

词汇

take liberty of 冒昧地

标签：Join,did,Overview,查询,Dept,Optimization,Systems,代价,Emp
From： https://www.cnblogs.com/qwerty-ll/p/14072418.html

相关文章

  • Overview of Database Link数据库链接概述
    什么是数据库链接？数据库链接是一个指针，它定义了从Oracle数据库服务器到另一个数据库服务器的单向通信路径。对于公共和私有数据库链接，链接指针实际上被定义为数据字典......
  • Lecture2 Linear methods for regression, Optimization
    书接上回，KNN模型有两个好处，一个是它很简单，另一个就是它既可以用来做回归，又可以用来做分类。但是坏处也很明显，就是它太粗暴了，基本上不怎么学习，只是对数据做一个简单的存储，等......
  • 论文被 AIMLSystems 2022 接受
    论文被AIMLSystems2022接受我们的论文“Q-commerce的地址位置校正系统”已在2022年10月12日至15日举行的第二届AI-ML系统国际会议(AIMLSystems'22)上被业......
  • DropoutNet: Addressing Cold Start in Recommender Systems阅读笔记
    动机本文是2017年nips上的一篇论文。在当时对于冷启动问题，大部分工作是针对colditem的，或是将偏好和内容都结合在目标函数中使其非常复杂。本文作者提出了DropoutNet，这个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99