【数据蒋堂】第33期:join提速 -欧洲杯在线开户

发布时间:2017-12-07 分类:数据蒋堂 tag:,,

sjjt-33

我们再来看重新定义join后如何能够提高运算性能,先看外键式join的情况。

设有两个表:

products商品信息表
id        商品编号
name  商品名称
price   单价
sales商品销售记录
seq            序号
date          日期
productid  商品编号
quantity    销售数量

其中sales表中的productid是指向products表中id字段的外键,id是products表的主键。

现在我们想计算销售额有多少(为简化讨论,就不再设定条件了),用sql写出来:

select sum(sales.quantity*products.price) from sales join products on sales.productid=products.id

基于笛卡尔积定义的join,原则上只能两层循环全遍历来计算,不过这个计算量实在太大,关系数据库一般采用hash分段方法优化,即分别计算两表关联字段的hash值,将hash同值记录拼到一起再做小范围遍历。网上有很多文章介绍这个算法,这里就不详述了。这样做后的复杂度能显著降低,但仍然要做多次hash值计算和比对。

 

我们再用前述的简化的join语法写出这个运算:

select sum(quantity*productid.price) from sales

而这个写法其实也就预示了它还可以有更好的优化方案,下面来看看怎样实现。

 

我们先考虑全内存的情况,如果所有数据都能够装入内存,我们可以实现外键指针化。

将事实表sales中的外键字段productid,转换成指向维表products记录的指针,即productid的取值就已经是某个products表中的记录,那么就可以直接引用记录的字段进行计算了。

用sql不方便描述这个运算的细节过程了,我们采用过程式语法、并用文件作为数据源来说明计算过程:

1. p=file(“products.txt”).import()                       读入商品信息表p
2. p.index(id)                                                          为p的主键id建立索引方便查找
3. s=file(“sales.txt”).import()                              读入商品销售记录s
4. s.switch(productid,p:id)                                   将s中的productid字段根据p的主键转换成p的记录
5. s.sum(quantity*productid.price)                    计算销售额。productid字段取值已经转换为对象,可以直接引用其price字段

上面算法中,第2步建主键索引一般也是用hash办法,对id计算hash值,第4步转换指针还是计算productid的hash值与p的hash索引表对比。这样的话,如果只做一次关联运算,指针化的方案和传统hash分段方案的计算量基本上一样,没有根本优势。

但不同的是,如果数据能在内存中放下,这个指针一旦建立起来之后可以复用,也就是说第2和第4步只要做一次,下次再做关于这两个字段的关联运算时就不必再计算hash值和比对了,性能就能大幅提高。而关系代数体系下没有对象指针这个概念,并且基于笛卡尔积定义的join运算也无法假定外键指向记录的唯一性,没办法使用外键指针化的方法,每次关联时都要计算hash值并比对。

而且,如果事实表中有多个外键分别指向多个维表,传统的hash分段join方案每次只能解析掉一个,有n个join要执行n遍动作,每次关联后都需要保持中间结果供下一轮使用,计算过程复杂得多,数据也会被遍历多次。而外键指针化方案在面对多个外键时,只要对事实表遍历一次, 没有中间结果,计算过程要清晰很多。

还有一点,内存本来应当是很适合并行计算的,但hash分段join算法却不容易并行。即使把数据分段并行计算hash值,但要把相同hash值的记录归聚到一起供下一轮比对,就会发生共享资源冲突的事情,这会把并行计算的优势完全抵消掉。而外键式join模型下,关联两表的地位不对等,明确区分出维表和事实表后,只要简单地将事实表分段就可以并行计算。

将hash分段技术参照外键属性方案进行改造后,也能一定程度地改善多外键一次解析和并行能力,有些数据库能在工程层面上实施这种优化。不过,这种优化在只有两个表join时问题不大,在有很多表及各种join混在一起时,数据库并不容易识别出应当把哪个表当作事实表去并行遍历、而把其它表当作维表建立hash索引,这时优化并不总是有效的。所以我们经常会发现当join的表变多时性能会急剧下降的现象(常常到四五个表时就会发生,结果集并无显著增大)。而从join模型上引入外键概念后,将这种join专门处理时,就总能分清事实表和维表,更多的join表只会导致性能的线性下降。

内存数据库是当前比较火热的技术,但上述分析表明,采用sql模型的内存数据库在join运算上是很难快起来的!

 
网站地图