当前位置:Gxlcms > mysql > 关系代数的并行计算

关系代数的并行计算

时间:2021-07-01 10:21:17 帮助过:79人阅读

从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

人气教程排行