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

OLAP Foreign Join Algorithm for MIC Coprocessor

作　　者：张宇[1] 张延松[2,3,4] 陈红[2,3] 王珊[2,3] 

机构地区：[1]中国气象局国家卫星气象中心,北京100081 [2]数据工程与知识工程教育部重点实验室(中国人民大学),北京100872 [3]中国人民大学信息学院,北京100872 [4]中国人民大学中国调查与数据中心,北京100872

出　　处：《软件学报》2017年第3期490-501,共12页Journal of Software

基　　金：国家高技术研究发展计划(863)(2015AA015307);中央高校基本科研业务费专项资金(16XNLQ02);华为创新研究计划(HIRP 20140507;HIRP 20140510)~~

摘　　要：众核架构协处理器Xeon Phi成为新兴的主流高性能计算平台.对于数据库应用而言,内存分析处理是一种计算密集型负载,其性能主要取决于大事实表与维表之间的内存外键连接性能.关注于一种相对于缓存相关的分区哈希连接算法和缓存不相关的无分区哈希连接算法的缓存友好型外键连接算法,以适应Xeon Phi协处理器较小的LLC和高并发线程的特点.通过挖掘OLAP模式中的代理键特征,基于键值匹配的哈希探测操作,可以进一步简化为事实表与维表之间基于主-外键参照完整性约束的代理键参照访问,因此,复杂的哈希表和CPU代价较高的哈希探测操作可以简化为通过映射外键值为代理键向量内存偏移地址的方法对代理向量直接访问.基于代理向量参照访问的外键连接算法,能够简单并高效地应用于Xeon Phi协处理器平台,通过更多的核心和高并发线程来掩盖内存访问延迟.实验中,对传统的哈希连接算法(无分区哈希连接算法和基数分区哈希连接算法)和基于代理向量参照技术的外键连接算法在Xeon E5-2650 v3 10核处理器平台和Xeon Phi 5110P 60核协处理器平台进行性能测试和比较,实验结果给出了主流的内存外键连接算法在不同数据集和不同平台上全面的性能特征.The emerging many integrated core architecture （MIC） Xeon Phi coprocessor becomes the mainstream platform for high performance computing. For database applications, in-memory analytics requires computation intensive workload in which the in-memoryforeign key joins between big fact table and dimension tables dominate the OLAP performance. This paper focuses on a cache-friendly foreign key join with respect to cache-conscious radix partitioning oriented hash join and cache-oblivious no-partitioning hash join to adapt to the small LLC size and massive simultaneous multi-threading mechanism of Xeon Phi coprocessor. By exploiting the characteristic of surrogate key in OLAP schema, the key matching oriented hash probing can be further simplified as surrogate key referencing between fact table and dimension tables with PK-FK reference constraint, so that the complex hash table and CPU cycle consuming hash probing can be simplified as directly referencing surrogate vector by mapping foreign key to offset address of surrogate vector. The surrogate vector referencing oriented foreign key join is simple and efficient to be implemented for Xeon Phi coprocessor for more cores, and also offers massive simultaneous multi-threading mechanism to overlap memory access latency. In experiments, the surrogate vector referencing foreign key join algorithm and traditional hash join algorithms （NPO and PRO） are compared on both Xeon E5-2650 v3 10-core CPU platform and Xeon Phi 5110P 60-core platform, the experimental results provide a comprehensive perspective for how the mainstream in-memory foreign key join algorithms perform with different datasets on different platforms.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]