面向MIC协处理器的OLAP外键连接算法

来源：软件学报杂志2017年第3期北京时间：

作者：张宇,张延松,陈红,王珊

单位：张宇，中国气象局 国家卫星气象中心, 北京 10008111,张延松，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 100872;中国人民大学 中国调查与数据中心, 北京 10087202,陈红，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087203,王珊，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087204

摘要：众核架构协处理器Xeon Phi成为新兴的主流高性能计算平台.对于数据库应用而言，内存分析处理是一种计算密集型负载，其性能主要取决于大事实表与维表之间的内存外键连接性能.关注于一种相对于缓存相关的分区哈希连接算法和缓存不相关的无分区哈希连接算法的缓存友好型外键连接算法，以适应Xeon Phi协处理器较小的LLC和高并发线程的特点.通过挖掘OLAP模式中的代理键特征，基于键值匹配的哈希探测操作，可以进一步简化为事实表与维表之间基于主-外键参照完整性约束的代理键参照访问，因此，复杂的哈希表和CPU代价较高的哈希探测操作可以简化为通过映射外键值为代理键向量内存偏移地址的方法对代理向量直接访问.基于代理向量参照访问的外键连接算法，能够简单并高效地应用于Xeon Phi协处理器平台，通过更多的核心和高并发线程来掩盖内存访问延迟.实验中，对传统的哈希连接算法（无分区哈希连接算法和基数分区哈希连接算法）和基于代理向量参照技术的外键连接算法在Xeon E5-2650 v3 10核处理器平台和Xeon Phi 5110P 60核协处理器平台进行性能测试和比较，实验结果给出了主流的内存外键连接算法在不同数据集和不同平台上全面的性能特征.

关键词：内存OLAP;外键连接;代理键;代理键参照

基金资助：国家高技术研究发展计划（863）（2015AA015307）；中央高校基本科研业务费专项资金（16XNLQ02）；华为创新研究计划（HIRP20140507，HIRP20140510）