2. 基于等价变换的查询优化在线视频

下面我们就来讲解一下分布式查询的一些优化策略

在讲具体的优化策略之前，我们先看一个例子

让大家体会一下分布式查询当中它优化策略的重要性

我们拿这个例子来说，比如说在我们这个教学数据库当中

有这么几个表，有一个S表，表示学生的，它有一万个元组

它存放在一个A站点上，在这个关系里面，有男生女生各是一半

接下来，我们还有一张表叫SC，这张表来表达学生选课的情况

比如说这里面有一百万个元组，它也存放在A站点

这里面我们可以假设一下它的统计数据，每一个人选课的数据是100门

还有一张表是课程表，课程表有10万个元组，存放在B站点上

现在我们有这样一个假设，比如说每个元组的长度是100个比特

通讯系统的传输速率每秒是一万个比特，这样的话每一次通信它的延迟时间为1秒的话

从代价测量上来讲，我们的延迟C0是1秒，它的传输速率D就是每秒一万个比特

下面我们有这样一个查询，比如说我要查询一个选修课程名为maths

也就是选修数学的男生的学号和姓名

我要做这样一个查询的话，学号和姓名一定是在A站点

数学这是一个课程名是在B站点，学生选课的情况也在A站点

也就是说我这个查询是涉及到两个站点的，是一个全局查询

对于这样一个查询，我们可以写这样一个SQL语句

这个SQL语句如果我放到数据库上去执行的话，我可以有这样几种执行策略

比如第一个执行策略，我把关系C也就是课程的这些信息直接传到A站点

然后直接在A站点我们进行一个连接运算，然后进行查询，最后直接在A站点得出结果

那么这个代价是多少呢，我们只讲通信代价

这个代价实际上就等于C0等于1再加上传输C的数据量和传输的带宽的比率

最后我们算出来是需要16分钟，也就是说做这样一个查询需要16分钟

显然这个策略是不太好的，谁希望一个查询需要花16分钟，等16分钟才能出结果呢

然后我们看一下策略2，我们可以先在A站点上找出男生的选课情况

然后再把男生的选课情况，传送到B站点上

与它课程的基本情况进行一个自然连接，选择一下这些男生是否选择了数学这门课程

然后把选择数学的这些男生再把它这个结果传回到A站点

这样的话，我每一次去选出一个男生的话

都会要传送这个男生所选课程的情况，然后再传送到B站点上，在B站点上进行运算

这样的话，我们的通讯就会出现两次通讯

从A站点上发送学生的信息到C站点，接下来再从C站点上把运算结果返回给A站点

它的通讯传输的数据量基本上是这样

因为一问一答，我们刚才从s表里也发现男生基本上是占一半，是五千个

而且每个男生平均选课的数是100，所以说它每次从A到C发送大概是100个记录

要发送5000次，所以它的通信基本上就是一问一答各五十万次

它的通信基本上就是一百万次，它所用的时间我们计算一下，大概要花11天的时间

所以可以看出从策略二与策略一来对比，我们看到策略一比策略二要快的多

如果我们要用策略二的话，这个查询基本上就没有办法进行了

下面我们再看一下策略三，我们还可以这样去做

比如说我先在B站点上找出一个课程名为数学的这样一个元组

假设说这样的元组大概有10门，然后我把这个结果直接传到A站点上

然后在A站点上执行一个查询处理的话

这个时候它的通信代价基本上就是我只通讯一次

我在C站点上通讯一次，然后把数据传给A，A在本站点上执行运算就可以了

因为它每次传的数据量也不大，而且通讯只有一次

所以它所用的时间基本上只有1秒

那么从这我们就可以看出一个查询策略它设置的好和坏

所以好的查询策略要比坏的查询策略效率提高的不止是一倍两倍的问题，差距是非常的大的

因此在分布式查询数据库里面要力图要用一个好的策略来提高查询的效率

这样的话很多人包括一些科研工作者和一些公司他们都在探讨分布式查询里面的一些优化机制

这些优化机制其中一个比较朴素或者传统一点的就是基于关系代数等价变换的查询优化

这个查询优化和集中式的查询优化有相似的地方

也就是说它一般的来说也是在关系代数表达式树上来进行

根据关系代数的等价变换的一些其他规则，这个我们在第二章讲过，我们不再说

但是它与集中式数据库还有不同的地方吗

那就是因为在分布式数据库里面，我们有这个分片，数据有的分片

所以我们在进行查询优化的时候利用关系代数等价变换

我们主要是来利用它的分片的这样一种机制

我们希望查询能够在某一些片段上执行

而不是输入一些无用的数据，所以我们用这个例子来说一下

比如说我们也是刚才这个例子，还是学生和学生选课这个情况

他们两个都采用水平分片的话，比如说学生我按照性别分

学生选课我按照课程的编号来分，每一个关系分成两个片段

接下来如果我要做这样一个查询，比如说我要查询一个男生而且考试成绩大于90分的

这样我们就可以把一个查询转化成关系代数表达式

然后我们把它用一棵树的形式表示出来，接下来我们对它进行优化

可以把这个笛卡尔乘积和属性相等把它优化成一个自然连接运算

接下来我们就可以把一些条件向叶子节点进行推

比如说我可以把性别等于男生，向学生这个节点进行推

然后把分数大于90的向SC这个节点进行推

推完了之后，因为在分布式数据库里面S和SC进行分片了

把S分成S1和S2，把SC分成SC1和SC2

我们就可以把前面这颗表达式树变成下面这个样子

接下来我们就可以去判断，比如说我们这个条件片段他们之间的吻合程度

如果他们之间根本就是不相关的

我们就可以把不相关的片段去掉，所以这样我们就可以把原来的关系代数变成这样

比如性别等于男的S1这样一个片段，性别等于女的S2片段

S2与前面的选择式没有任何关系的，我们就把S2去掉，这就是优化的这样一个过程

所以说它实际上是基于片段的优化过程

也就是对于片段的一种选择，关于片段的选择，刚才我们举得例子是一个水平分片

对于垂直分片也是一样的，比如我们再举一个例子

这样一个全局关系，这个前面我们已经给出了它分两个片段

一个片段包含前三个属性，EMP比如说它分解成EMP1（#，Dept，Dname）和EMP2（E#,Ename，Sal）

如果我要做这样一个查询，比如说我select一个Ename和，Sal，从EMP里面去查

实际上这个Ename和Sal实际上在EMP的片段的第二个片段里面

这样的话，我们在查询的时候，当我们把它变化成关系代数表达式数的时候

我们就把原关系用片段来代替

接下来我们找出我们查询的字段和我们分解的片段之间有没有交集

如果没有交集我们就把那个片段给去掉

这个查询里面显然EMP1是没有关系的，所以我们保留EMP2

我们就可以利用这样一种方式确定我们查询需要集中在哪一个片段上

这就是基于关系代数等价变换的一种查询方式