计算机工程 ›› 2019, Vol. 45 ›› Issue (6): 60-66.doi: 10.19678/j.issn.1000-3428.0050655

• 先进计算与数据处理 • 上一篇    下一篇

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

孟庆强1,何浩奇2,毕倪飞2,赵斌2,吉根林2   

  1. 1.南瑞集团有限公司(国网电力科学研究院有限公司),南京 211100;2.南京师范大学 计算机科学与技术学院,南京 210023
  • 收稿日期:2018-03-07 出版日期:2019-06-15 发布日期:2019-06-15
  • 作者简介:孟庆强(1975—),男,高级工程师、硕士,主研方向为数据挖掘、大数据平台软件研发;何浩奇,硕士研究生;毕倪飞,本科 生;赵斌,副教授;吉根林,教授。
  • 基金项目:
    国家自然科学基金(41471371)。

Non-Equi join operation algorithm for multi-attribute

MENG Qingqiang 1,HE Haoqi 2,BI Nifei 2,ZHAO Bin 2,JI Genlin 2   

  1. 1.NARI Group Corporation(State Grid Electric Power Research Institute),Nanjing 211100,China;2.School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China
  • Received:2018-03-07 Online:2019-06-15 Published:2019-06-15

摘要: 为降低多属性不等值连接操作的计算代价,提出一种基于属性优选的不等值连接操作算法MIEJoin。按照连接属性对元 组进行排序,计算各连接属性的候选集大小,在最小候选集中根据连接谓词进行筛选得到最终的结果集。在此基础上,为 提升系统的缓存命中率,提出一种缓存敏感的多属性不等值连接算法CMIEJoin。基于MIEJoin算法建立元组的排列顺序 数组,在内存中邻近存储连续访问的数据,以降低缓存的缺失次数并提升算法的运行效率。在TPC-H数据集上的实验结果 表明,与BIEJoin算法和NLJoin算法相比,CMIEJoin算法具有较高的运行效率。

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

Abstract: 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.

Key words: non-equi query, non-equi join, minimal candidate set, cache-sensitive algorithm, query processing

中图分类号: