欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

关系代数的并行计算

程序员文章站 2022-06-13 20:05:46
...

从Dremel和Impala的学习引申出了SQL查询的并行执行问题,于是借此机会深入学习一下关系数据库以及关系代数的并行计算。 Speedup和Scaleup Speedup指用两倍的硬件换来一半的执行时间。Scaleup指两倍的硬件换来同等时间内执行两倍的任务。但往往事情不是那么简

从Dremel和Impala的学习引申出了SQL查询的并行执行问题,于是借此机会深入学习一下关系数据库以及关系代数的并行计算。

Speedup和Scaleup

Speedup指用两倍的硬件换来一半的执行时间。Scaleup指两倍的硬件换来同等时间内执行两倍的任务。但往往事情不是那么简单,两倍的硬件也会带来其他问题:更多CPU带来的长启动时间和通信开销,以及并行计算带来的数据倾斜问题。

关系代数的并行计算

多处理器架构

共享内存喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPqO6yM7S4kNQVba8xNy3w87KyM7S4rXExNq05ijIq77WubLP7Sm6zbTFxcyho9PFtePKx7zytaWjrMixtePKx8Cp1bnQ1LLuo6y/ydPD0NS1zaGjPC9wPjxwIGFsaWduPQ=="center">关系代数的并行计算

共享磁盘:任意CPU都能访问任何的磁盘,但是只能访问自己的主存。优点是可用性和扩展性比较好,缺点是实现复杂以及潜在的性能问题。

关系代数的并行计算

不共享:任意CPU都只能访问自己的主存和磁盘。优点也是扩展性和可用性,缺点是实现复杂以及复杂均衡。

关系代数的并行计算

混合型:系统整体上是shared nothing架构,但结点内部可能是其他架构。这样就混合了多种架构的优点。

关系代数的并行计算

数据分区

数据分区的目的就是:让数据库能够并行地读写数据,最大程度地挖掘I/O的潜力。常见的分区算法有:round-robin、范围索引、哈希。

关系代数的并行计算

关系运算并行化

关系代数自身的属性允许关系操作的并行化

关系代数的并行计算

并行查询处理主要分为四步:

? 翻译:将关系代数表达式翻译成查询树。

? 优化:重排join顺序,并选择不同join算法来最小化执行开销。

? 并行:将查询树转换成物理操作树,并加载到处理器。

? 执行:并行运行最终的执行计划。

首先将一条SQL语句翻译成查询树。

关系代数的并行计算

然后根据表大小、索引等情况,重新排列join顺序,并选择合适的算法。

关系代数的并行计算

关于join算法,常见的有以下几种:

? Nested Loop join:思路很简单,相当于两层循环遍历,外层是驱动表,返回满足关联条件的行。适用于驱动表小(经过条件过滤后),而被驱动表上join字段有索引的情况。在两表都很大时效率很差。

for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)

? Sort-merge join:思路也很简单,就是按join字段排序,然后进行归并排序。当join字段存在重复值时,相当于每个重复值形成了一个分区。Join字段是否排序和重复值的多少决定了sort-merge的效率。适用于两表都很大的情况,尤其当join字段上存在聚集索引时(相当于已经排好序了),效率很高。算法主要消耗在磁盘上。

? Hash join:类似于存在重复值情况时的sort-merge,只不过是人为的使用哈希函数进行分区。思路是扫描小表建立哈希表(build阶段,小表也叫build表),然后逐行扫描大表进行比较(probe阶段,大表也叫probe表)。适用于两表都很大又没有索引的情况,限制是只适用于等值连接。算法主要消耗在CPU上。

关系代数的并行计算

此外,对于子查询还有semi joinanti join等算法。

最后将查询树变成物理操作树,也就是真正的执行计划。然后根据集群的资源情况,调度到合适的结点上进行并行计算。

关系代数的并行计算

参考资料

1 Parallel Query Processing