面向多属性的不等值连接操作算法  

Non-Equi Join Operation Algorithm for Multi-attribute

作　　者：孟庆强 何浩奇 毕倪飞 赵斌[2] 吉根林 MENG Qingqiang;HE Haoqi;BI Nifei;ZHAO Bin;JI Genlin(NARI Group Corporation(State Grid Electric Power Research Institute),Nanjing 211100,China;School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China)

机构地区：[1]南瑞集团有限公司(国网电力科学研究院有限公司),南京211100 [2]南京师范大学计算机科学与技术学院,南京210023

出　　处：《计算机工程》2019年第6期60-66,共7页Computer Engineering

基　　金：国家自然科学基金(41471371)

摘　　要：为降低多属性不等值连接操作的计算代价,提出一种基于属性优选的不等值连接操作算法MIEJoin。按照连接属性对元组进行排序,计算各连接属性的候选集大小,在最小候选集中根据连接谓词进行筛选得到最终的结果集。在此基础上,为提升系统的缓存命中率,提出一种缓存敏感的多属性不等值连接算法CMIEJoin。基于MIEJoin算法建立元组的排列顺序数组,在内存中邻近存储连续访问的数据,以降低缓存的缺失次数并提升算法的运行效率。在TPC-H数据集上的实验结果表明,与BIEJoin算法和NLJoin算法相比,CMIEJoin算法具有较高的运行效率。To reduce the computational cost of multi-attribute non-equi join operation,an non-equi join operation algorithm MIEJoin based on attribute optimization is proposed.The tuples are sorted by join attribute,the candidate set size of each join attribute is calculated,and the final result set is filtered according to the join predicate in the minimal candidate set.On this basis,a cache-sensitive multi-attribute non-equi join algorithm CMIEJoin is proposed to improve the hit rate of the system cache.Based on the MIEJoin algorithm,the array of sorted tuples is established,and the continuousty accessed data is stored in memory in proximity to reduce the number of cache missings and improve the efficiency of the algorithm.Experimental results on the TPC-H dataset show that CMIEJoin algorithm has higher efficiency than BIEJoin algorithm and NLJoin algorithm.

关 键 词：不等值查询 不等值连接 最小候选集 缓存敏感算法 查询处理 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]