Hashjoin算子矢量化优化

总第３０１期　计算机与数字工程　Ｃｏｍｐｕｔｅｒ　８．Ｄｉｇｉｔａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｏ１．４２　Ｎｏ．１］　２０４１　２０１４年第１ｌ期　Ｈａｓｈｊ　ｏｉｎ算子矢量化优化　徐庆岳　何清法。　蒋志勇　赵殿奎。　（１．中国航天系统科学与工程研究院北京１０００３７）（２．北京神舟航天软件技术有限公司北京１０００９４）　摘要针对Ｈａｓｈｊｉｏｎ性能瓶颈，为了提高数据库性能，加快查询响应能力，提出矢量化方法优化Ｈａｓｈｊｏｉｎ。矢量化　又叫批处理，是针对目前数据库处理系统存在的按行迭代，流水线操作方式而提出的一种优化思路。矢量是构建阶段使用　大小为ｎ作为输人向量，并允许任意列的组合的原则处理它们的输入。执行器执行查询计划树，每次迭代算子执行以矢量　即批量元组为单位而不是以行为单位。通过仿真实验得出批处理最终加快了Ｈａｓｈｊｏｉｎ算子处理速度近３Ｏ倍，结果在查询　中涉及到Ｈａｓｈｊｏｉｎ的查询分析性能大大提升。　关键词哈希连接；矢量化；哈希表；算子　ＴＰ３１１．１３　ＤＯ１：１０．３９６９／ｊ．ｉｓｓｎ１６７２—９７２２．２Ｏ１４．１１．０１２　中图分类号Ｈａｓｈｊｏｉｎ　Ｏｐｅｒａｔｏｒ　Ｖｅｃｔｏｒｉｚａｔｉｏｎ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＸＵ　Ｑｉｎｇｙｕｅ　ＨＥ　Ｑｉｎｇｆ２　ＪＩＡＮＧ　Ｚｈｉｙｏｎｇ２　ＺＨＡＯ　Ｄｉａｎｋｕｉ。　（１．Ｃｈｉｎａ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｐａｃｅ　Ｓｙｓｔｅｍｓ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｊｉｎｇ　１０００３６）　（２．Ｂｅｉｊｉｎｇ　Ｓｈｅｎｚｈｏｕ　Ａｅｒｏｓｐａｃｅ　Ｓｏｆｔｗａｒｅ　Ｔｅｃｈｎｏｌｏｇｙ　Ｃｏ．，ＩＡｄ．，Ｂｅｉｊｉｎｇ　１０００９４）　Ａｂｓｔｒａｃｔ　Ｆｏｒ　Ｈａｓｈｊ　ｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ｂｏｔｔｌｅｎｅｃｋｓ，ｉｎ　ｏｒｄｅｒ　ｔｏ　ｉｍｐｒｏｖｅ　ｄａｔａｂａｓｅ　ｐｅｒｆｏｒｍａｎｃｅ，ａｃｃｅｌｅｒａｔｅ　ｑｕｅｒｙ　ｒｅｓｐｏｎｓｅ　ｃａｐａｂｉｌｉｔｙ，Ｈａｓｈｊｏｉｎ　ｏｐｅｒａｔｏｒ　ｉｓ　ｏｐｔｉｍｉｚｅｄ　ｔｈｒｏｕｇｈ　ｖｅｃｔｏｒｉｚａｔｉｏｎ　ｍｅｔｈｏｄ．Ｖｅｃｔｏｒｉｚａｔｉｏｎ　ｉｓ　ｋｎｏｗｎ　ａｓ　Ｂａｔｃｈ．Ｉｔ　ｉｓ　ｆｏｒ　ａ　ｒｏｗ　ｉｔ　ｅｒａｔｉｏｎ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｐｉｐｅｌｉｎｅ　ｏｐｅｒａｔｉｏｎ　ａｎｄ　ｐｒｏｃｅｓｓｉｎｇ　ｓｙｓｔｅｍｓ　ｃｕｒｒｅｎｔｌｙ　ｅｘｉｓｔ　ｉｎ　ｔｈｅ　ｄａｔａｂａｓｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｉｄｅａｓ．Ｔｈｅ　ｖｅｃ—　ｔｏｒｉｚｅｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｂｕｉｌｄ　ｐｈａｓｅ　ｕｓｅｓ　ｖｅｃｔｏｒｓ　ｏｆ　ｓｉｚｅ　ａｓ　ｉｎｐｕｔ　ａｎｄ　ａｌｌｏｗｓ　ａｒｂｉｔｒａｒｙ　ｃｏｌｕｍｎ　ｃｏｍｂｉｎａｔｉｏｎｓ　ｉｎ　ｔｈｅ　ｉｎｐｕｔ．　Ａｃｔｕａｔｏｒｓ　ｃａｒｒｉｅｓ　ｏｕｔ　ｑｕｅｒｙ　ｐｌａｎ　ｔｒｅｅ，ｅａｃｈ　ｉｔｅｒａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ｉｎ　ｖｅｃｔｏｒ　ｅｘｅｃｕｔｉｏｎ　ｕｎｉｔ　ｉｓ　ｂａｔｃｈ　ｏｆ　ｔｕｐｌｅｓ　ｒａｔｈｅｒ　ｔｈａｎ　ｉｎ　ｕｎｉｔｓ．　Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｏｂｔａｉｎｅｄ　ｆｉｎａｌ　ｂａｔｃｈ　ｏｐｅｒａｔｏｒ　ｔｏ　ｓｐｅｅｄ　ｕｐ　ｔｈｅ　ｐｒｏｃｅｓｓｉｎｇ　ｓｐｅｅｄ　Ｈａｓｈｊｏｉｎ　ｎｅａｒｌｙ　３０　ｔｉｍｅｓ，Ｉｎ　ｃｏｎｃｌｕｓｉｏｎ　Ｈａｓｈｊｏｉｎ　ｏｐｅｒａｔｏｒ　ｏｆ　ａｎａｌｙｓｉｓ　ｉｎｖｏｌｖｅｓ　Ｈａｓｈｊｏｉｎ　ｑｕｅｒｙ　ｐｅｒｆｏｒｍａｎｃｅ　ｇｒｅａｔｌｙ　ｉｍｐｒｏｖｅｄ．　Ｋｅｙ　Ｗｏｒｄｓ　ｈａｓｈｉｏｉｎ，ｖｅｃｔｏｒｉｚｅｄ，ｈａｓｈ－ｔａｂｌｅ，ｏｐｅｒａｔｏｒ　Ｃｌａｓｓ　Ｎｕｍｂｅｒ　ＴＰ３１］．］３　１　引言　数据，已经渗透到当今每一个行业和业务职能　领域，成为重要的生产因素。人们对于海量数据的　挖掘和运用，预示着新一波生产率增长和消费者盈　的连接效率而被选中。　但是，随着数据库技术的发展和应用，数据库　存储的数据量从２０世纪８Ｏ年代的兆（Ｍ）字节及　千兆（Ｇ）字节过渡到现在的兆兆（Ｔ）字节和＿下兆兆　（Ｐ）字节，同时，用户的查询需求也越来越复杂，涉　及的已不仅是查询或操纵一张关系表中的一条或　几条记录，而且要对多张表中千万条记录的数据进　行数据分析和信息综合，关系数据库系统已不能全　部满足这一要求。　余浪潮的到来。　Ｈａｓｈｊｏｉｎ算子是在数据库系统涉及到数据查　询时，表与表的连接经常会用到的算子。数据库的　优化器在计算优化路径时，Ｈａｓｈｊｉｏｎ通常因为高效　＊收稿日期：２０１４年５月１５日，修回日期：２０１４年６月２４日　基金项目：核高基：神通大型通用数据库管理系统产品研发及产业化（编号：２０１０ＺＸ０１０４２—００１　００１—０１）资助。　作者简介：徐庆岳，男，硕士研究生，研究方向：数据库。何清法，男。研究员，硕士生导师，研究方向：数据库、信息安　全、网络和信息检索等。蒋志勇，男，高级工程师，研究方向：数据库技术、分布式计算等。赵殿奎，男，工程师，研究方　向：数据库、网络技术等。　徐庆岳等：Ｈａｓｈｊｏｉｎ算子矢量化优化　第４２卷　在国外，不少软件厂商采取了发展其前端产品　来弥补关系数据库管理系统支持的不足，力图统一　分散的公共应用逻辑，在短时间内响应非数据处理　专业人员的复杂查询要求。　因此，如何提高数据管理系统的数据处理能力　越来越成为当今社会的一个挑战。如何对现有的　数据处理系统做优化越来越成为当今世界的一个　挑战。数据库管理系统中，Ｈａｓｈｊｉｏｎ有着举足轻重　的位置。因此，如何对大数据量的表做哈希连接　（Ｈａｓｈｊｉｏｎ）也成为了当前的研究难点。　２　现有涉及Ｈａｓｈｊｏｉｎ算子的查询方式　数据库客户端查询处理后台服务器需要做一　系列的工作。首先，数据库管理系统调用解析器对　查询请求进行词法分析与转换，得到一个内部数据　结构——查询树。接着重写系统利用规则对查询　树中的部分节点进行重写。然后，规划优化器采用　动态编程或遗传算法优化，根据查询树生存所有的　可能查询路径，然后评估每个路径的代价，从中选　择一个查询代价最小的，即最终的查询规划。最后　将查询规划传递给查询执行器，进行处理而得到结　果。　在每个查询中，一般都会涉及到ｊｏｉｎ操作，ｊｉｏｎ　算子包含有Ｎｅｓｔｌｏｏｐ　ｊｏｉｎ、Ｈａｓｈｊｊｉｏｎ和Ｓｏｒｔ　ｍｅｒｇｅ　ｊｏｉｎ等算子，针对目前数据量越来越大的问　题，海量数据分析处理和Ｏｌａｐ系统中Ｈａｓｈｊｏｉｎ在　处理大数据量时具有优势比较明显，但对其进行优　化的也显得尤为迫切。　尽管现有的Ｈａｓｈｊｏｉｎ效率极高，但Ｈａｓｈｊｉｏｎ　执行器按行迭代，每个执行的查询计划是包含多个　算子的二叉树，算子间通过流水方式执行，每个算　子提供Ｏｐｅｎ初始化算子和Ｏｐｅｎ孩子算子，Ｇｅｔ—　Ｎｅｘｔ，Ｃｌｏｓｅ三个通用接口，每次ＧｅｔＮｅｘｔ调用返　回包含多列的一行元组。即通过按行迭代模式完　成元组操作。ｋｓｔｏｒｅ执行器按照按行迭代模型执　行，每次只处理一行数据，每行数据在由各算子构　成的查询树上进行自下而上流动即每行数据在当　前算子处理完毕后交给上层算子继续处理，直到将　此行数据返回给用户。那么按行迭代模型在性能　上存在如下劣势：　１）ＣＰＵ指令缓存：对于包含有多个算子的查　询计划树，那这些算子指令合并在一起所需要的指　令空间要远大于ＣＰＵ的指令缓存，因此导致每行　元组在计划树的各算子间执行进行上下文切换时，　导致需要访问的部分指令发生缓冲区丢失。　２）算子执行状态数据缓存：每个算子都有一　个用于存放执行数据的Ｐｌａｎｓｔａｔｅ，如果其中的算子　ｐｌａｎｓｔａｔｅ包含的状态信息太多，无法存放到ＣＰＵ　的数据缓存中，导致缓冲区丢失。　３）函数调用消耗：算子以及算子问每次迭代　都需要执行很多函数调用，如果算子中每行元组执　行需要十个函数调用，则对于１Ｍ行数据，则需要　１０＊１Ｍ＝１０Ｍ次函数调用。因为每次函数调用都　需要至少数十个ＣＰＵ周期，特别是对于需要动态　调度的函数（如有数据依赖的函数）需要的ＣＰＵ周　期更多，如果函数有多个参数需要传递，那ＣＰＵ周　期就需要更多了。　４）元组维护：对于物化元组即ＥｘｅｃＴｕｐｌｅ，由　于这些元组是按照属性列组织的，所以每次读取其　中的某个属性首先需要计算属性位置，然后才能读　取数据，如果这个元组包含有多个属性，那么读取　这些属性需要频繁地执行上述动作，消耗大量　ＣＰＵ周期。　若Ｈａｓｈｊｉｏｎ采用按行迭代模型，那么效率很　低，面对海量数据的时候，处理的速度还是比较缓　慢，为此，引入矢量化的概念，对Ｈａｓｈｊｏｉｎ进行优　化。　３　Ｈａｓｈｊｏｉｎ算子矢量化改进的算法　研究　鉴于以上原因，提出了Ｈａｓｈｊｉｏｎ的矢量化改　进方案。　矢量是矢量迭代模型中数据维护和传输的基　本单元，每个矢量是包含有属性数据的简单一维数　组，每个矢量包含的元素个数可以根据需要动态调　整的，范围介于１２８～１０２４之间，具体可以根据机　器的Ｃａｃｈｅ大小决定，目标是每次Ｖｅｃｔｏｒ运算都　在Ｃａｃｈｅ中进行。　矢量化又叫批处理，是针对目前数据库处理系　统存在的按行迭代，流水线操作方式而提出的一种　优化思路。执行器执行查询计划树，每次迭代算子　执行以矢量ｇｌＪｔｔＬ量元组为单位而不是以行为单位。　在矢量化模型中，算子的功能被分解成一系列　小的功能执行模块。这要归功于数据库的高度专　业化，使用矢量化方法编写的代码，很容易优化编　译器，并且让现代的ＣＰＵ有效地执行。　矢量化执行的大部分时间是花在数据处理的　小功能模块上。因此，提供有效率的执行模块是相　当重要的。为了获得最佳性能，矢量化功能执行模　块必须满足以下要求。但并非对每一个数据的处　２０１４年第１１期　计算机与数字工程　一理操作都必须满足下面所描述的要求：　・和下一个阵列来完成。算法如下：　ｈａｓｈＴａｂｌｅＩｎｓｅｒｔ（ｇｒｏｕｐｆｄＶ，ｈａｓｈＴａｂｌｅ，ｂｕｃｋｅｔＶ，　ｎ）｛　原始独立性——第一步是使功能模块处理　在一个函数调用的多个数据项时不需要与其他功　能模块进行通信。　・ｆｏｒ（ｉ一０；ｉ＜ｎ；ｉ＋＋）｛　操作独立性——如果一个元组的处理独立　ｇｒｏｕｐｌｄＶ［ｉ］一ｈａｓｈＴａｂｌｅ．ｃｏｕｎｔ＋＋：　于其他的人，相同的计算可以在多个元组并行执　ｈａｓｈＴａｈｌｅ．ｎｅｘｔ［ｇｒｏｕｐｌｄＶ［ｉ］］一ｈａｓｈＴａｂｌｅ．ｆｉｒｓｔ　［ｂｕｃｋｅｔＶ［ｉ］］；　行。这对于现代ＣＰＵ的提高了执行效益，并提供　ＳＩＭＤ（单指令多数据流）机会。　・ＣＰＵ指令独立性——处理一个给定的元组　时，独立执行算子与ＣＰＵ指令相分离是非常重要　的。　矢量化的Ｈａｓｈｊｏｉｎ操作分为建哈希表和探测　两个阶段，也称为构建阶段和探测阶段。　３．１建哈希表　矢量化实现构建哈希表阶段首先要确定同时　处理的批量数，使用大小为　作为输人向量，并允　许任意列的组合作为的输入。简化的算法步骤如　下：　输入：构建与Ｎ属性和Ｋ键的表，计算每个元　组桶号码，存储在ｂｕｃｋｅｔＶ中。　ｆｏｒ（ｉ一０；ｉ＜Ｋ；ｉ＋＋）ｈａｓｈ［ｉ］（ｈａｓｈＶａｌ—　ｕｅＶ，ｂｕｉｌｄ．ｋｅｙｓ［ｉ］，ｎ）；　ｍｏｄｕｌｏ（ｂｕｃｋｅｔＶ，ｈａｓｈＶａｌｕｅＶ，ｎｕｍＢｕｃｋ—　ｅｔｓ，ｎ）；　准备组织哈希表，计算在ｇｒｏｕｐｌｄＶ每个元组　位置。　ｈａｓｈＴａｂｌｅＩｎｓｅｒｔ（ｇｒｏｕｐｌｄＶ，ｈａｓｈＴａｂｌｅ，　ｂｕｃｋｅｔＶ。ｎ）　插入所有属性ｆｏｒ（ｉ一０；ｉ＜Ｎ；ｉ＋＋）　ｓｐｒｅａｄ［ｉ］（ｈａｓｈＴａｂｌｅ．ｖａｌｕｅｓ［ｉ］，ｇｒｏｕｐＩｄＶ，　ｂｕｉｌｄ．ｖａｌｕｅｓ［ｉ］，ｎ）；　构建阶段的首要任务是找到每个生成元组的　桶号码。支持任意数目和关键属性的组合处理。　该阶段又被分解成一组步骤，如下所示：　使用Ｈａｓｈ＊（例如散列ＳＩ　ＮＧ）函数计算一个　特定类型的哈希函数，利用第一键列作为参数计算　ｈａｓｈＶａｌｕｅＶ矢量。　通过应用，结合现有的哈希值与第二个键列的　哈希值类型特定的ｒｅｈａｓｈ＊函数调整ｈａｓｈＶａＩｕｅＶ　载体。重复其余键列。　计算包含使用一个模（或和）函数作为每个元　组的桶号构成ｂｕｃｋｅｔＶ矢量。　所得ｂｕｃｋｅｔＶ是与普通的Ｈａｓｈｉｏｉｎ里桶变量　的向量化等同。因此，插入过程适用于所有元组。　该算法的步骤２）中，哈希表的组织是通过调节第　ｈａｓｈＴａｂｌｅ．ｆｉｒｓｔ［ｂｕｃｋｅｔＶ［ｉ］］一ｇｒｏｕｐｌｄＶ［ｉ］：　）｝　同时，ｇｒｏｕｐＩｄＶ矢量被计算，保持每个输入元　组在哈希表中的位置。在步骤３）中，所有的输入　属性被插入到特定类型ｓｐｒｅａｄ函数的哈希表中匹　配位置。算法如下：　ｓｐｒｅａｄ（ｈａｓｈＴａｂｌｅＶａｌｕｅｓ，ｇｒｏｕｐＩｄＶ，ｉｎｐｕｔＶａｌｕｅｓ，ｎ）　｛ｆｏｒ（ｉ一０；ｉ＜ｎ；ｉ＋＋）ｈａｓｈＴａｂｌｅＶａｌｕｅｓ　［ｇｒｏｕｐｌｄＶ［ｉ］］一ｉｎｐｕｔＶａｌｕｅｓ［ｉ］；｝　３．２探测阶段　探测阶段面临特别具有挑战性的两个问题。　首先，遍历链表的过程中，相等比较可以是任意复　杂的，这取决于键结构。其次，链表的遍历需要每　个元组的循环，内部将会需要执行这个复杂的相等　性检查。　探测实施阶段，我们利用的以上事实，内部循　环长度不同的元组可以显著不同，步骤的数量是有　限的，并且大多数元组需要检查只有一个或两个哈　希表中的元素。这允许我们修改链表遍历所有元　组的方式。首先在列表中每一个元组找到第一个　元素。然后比较这些元素是否能够与之前的探测　键配对。对于具有值差异的元组，查找在列表中的　下一个元素并且重复该过程。　假设探测表具有Ｍ个属性和Ｋ个键，哈希表　包含Ｎ个构建属性。步骤如下所示。　３．２．１　计算每个探头元组的桶数　以在构建阶段相同的方式构造探测表的ｂｕｃｋ—　ｅｔＶ。　３．２．２找到在哈希表中的位置　首先，找到链表的每个元组的第一个元素，把　它放在ｇｒｏｕｐＩｄＶ，并且同时初始化ｔｏＣｈｅｃｋＶ和输　入索引的完整序列（Ｏ，…，　一１个）。　ｌｏｏｋｕｐＩｎｉｔｉａｌ（ｇｒｏｕｐＩｄＶ，ｔｏＣｈｅｃｋＶ，ｂｕｃｋｅｔＶ，ｎ）；　ｍ—ｎ：　ｗｈｉｌｅ（ｍ＞Ｏ）｛　其次，ｔｏＣｈｅｃｋＶ包含输人键比较需要被执行　的元组ｍ个位置。对于每个元组ｇｒｏｕｐＩｄＶ包含　在哈希表中当前分析的偏移。使用特定类型的　ｃｈｅｃｋ（）／ｒｅｃｈｅｃｋ（）函数产生ｄｉｆｆｅｒｓＶ来完成多列　徐庆岳等：Ｈａｓｈｊｏｉｎ算子矢量化优化　第４２卷　值检查。　ｆｏｒ（ｉ一０；ｉ＜Ｋ；ｉ＋＋）　组产生不同的步骤。同样地，它产生了数据和控制　依赖，这不利于现代ＣＰＵ结构。因此，它也使得链　表遍历过程中产生重叠的缓冲区丢失成为可能。　图１是一个在Ｋｓｔｏｒｅ系统中，对两种不同矢　ｃｈｅｃｋ［｜］（ｄｉｆｆｅｒｓＶ，ｔｏＣｈｅｃｋＶ，ｇｒｏｕｐｌｄＶ，ｈａｓｈ—　Ｔａｂｌｅ．ｖａｌｕｅｓ￣ｉ］，ｐｒｏｂｅ．ｋｅｙｓ￣ｉ］，ｍ）；　再次，ｄｉｆｆｅｒｓＶ中若包含１，为至少有一个键不　同的元组，选择这些列，然后对这些列进一步处理。　ｍ—ｓｅｌｅｃｔＭｉｓｓｅｓ（ｔｏＣｈｅｃｋＶ。ｄｉｆｆｅｒＶ，ｍ）；　最后，对于不同的元组，找到哈希表中的下一　个偏移量，把它放在ｇｒｏｕｐＩｄＶ。　ｆｉｎｄＮｅｘｔ（ｔｏＣｈｅｃｋＶ，ｈａｓｈＴａｂｌｅ．ｎｅｘｔ，ｇｒｏｕｐｌｄＶ，ｍ）；　３．２．３投影出需要元组　ｇｒｏｕｐｌｄＶ为每探头元组包含匹配元组哈希表　中的偏移量。用它来从哈希表投影属性（探头的属　性只是传递）。　ｆｏｒ（ｉ一０；ｉ＜Ｎ；ｉ＋＋）　ｇａｔｈｅｒＥｉ］（ｒｅｓｕｌｔ．ｖａｌｕｅｓ［Ｍ＋ｉ］，ｇｒｏｕｐｌｄＶ，ｈａｓｈ　Ｔａｂｌｅ．ｖａｌｕｅｓＥｉ］，ｎ）；　４仿真实验和总结　为了实现矢量化算法描述的计算效率，数据处　理小模块应遵循批量处理的设想，对多个元组独立　地执行相同的操作。因此需要对矢量化算法进行　仿真测试。　仿真程序通过实验比较进行分析矢量化　Ｈａｓｈｊｏｉｎ算法的性能。矢量化算法的执行性能用　两种不同大小的向量进行测试。１个元组在一次　时间内完成迭代的方法（按行迭代）和１０２４个元组　一次完成迭代（矢量化）：两个２一和３一属性列的表被　使用时，各自用１一和２一属性键做链接键。探测表总　是包含４Ｍ元组，均具有在构建表的匹配的键。因　此在构建的哈希表中，包含独立键的元组从１６到　４Ｍ。　由于Ｋｓｔｏｒｅ系统的测试中提供了以上算法描　述大部分所需的性能，并基于以下四点实际情况：　构建阶段，处理一个向量不同的元组不是完全　独立的。如果有多个键落人同一个桶，它们需要一　个接一个处理。这可能会导致一些数据依赖，但在　哈希表组织过程中它又是不可避免的。　探测阶段，不同元组的处理是完全独立的，这　是因为假设其为』＼，一１连接：每个探测元组产生只　有一个元组的结果，因此，每个结果元组的位置是　已知的。　构建表和探测表执行阶段期间，寻找其在哈希　表中的位置是一次性消耗，每次构建和探测表可以　完成快速插入或多个属性的查询。　链表中的内循环在探测阶段可能因不同的元　量执行测试所得出的数据图，系统的ＣＰＵ为睿２　四核，２．４ＧＨｚ。　７２９０　．　．．．２４３０　／　桃８１０　麓２７０　／　＋迭代行数＝１　一一一—　．。　／　十迭代行数＝１０２４　３Ｏ　ｌＯ　ｌ６　２５６　４ｋ　２５６ｋ　１Ｍ　构建表大小（元组对数表）　图１构建表迭代数－眭能对比（１一链接键）　７２９０　／，　．　一　一　一　一—２４３０　０　＿／．　莨２７０　＋迭代行数＝１　９０　Ｉ　／　＋迭代行数＝１０２４　３Ｏ　】０　１６　２５６　４ｋ　２５６ｋ　１Ｍ　构建表大小（元组对数表）　图２构建迭代数性能对比（２一链接键）　图１和图２，显著地表明开销的元组在每一个执　行受到影响，并且对哈希表的大小不那么敏感。最　终，矢量化后提供３０倍的改进高速缓存驻留数据，　这种改善下降了驻留在内存中的数据。这表明矢量　化结合现代的ＣＰＵ特性与执行缓存优化特点对数　据库处理性能有大幅提升。采用矢量化的技术可以　达到近乎３Ｏ倍的响应速度，还得考虑以下方面。　矢量化的Ｈａｓｈｊｉｏｎ的高速缓存提升效率很　高，但是从性能上随着内存处理元组数显著退化，　因为随机存储器工作时受到访问关联到该链接表　的遍历。这个问题可以通过使用不使用一个链表　Ｈａｓｈ的方法得到解决，例如Ｃｕｃｋｏｏ—ｈａｓｈｉｎｇ。不　过，即使使用这种改进，缓冲区丢失的开销可以抵　消每个元组处理的成本。有两种主要的技术可以　解决这一问题。　第一种技术，利用哈希查找程序内显式的内存　预取指令。这种转变哈希查找，吞吐量从内存延迟　限制到一个内存带宽受限的转变，它可以强烈地提　高整体散列连接表现。然而，ＣＰＵ优化哈希对内存　带宽来说已经变得太陕，从优化ｃｕｃｋｏｏ－ｈａｓｈｉｎｇ每次　（下转第２２１ｌ页）　２０１４年第１１期　工大学学报（自然科学），２０１Ｉ（Ｉ１）：８６—９１．　计算机与数字工程　２２１１　Ｅ７］Ｓｉｅｂｅｌ［ＥＢ／（）Ｉ　］．ｈｔｔｐ：／／ｂａｉｋ￣ｂａｉｄｕ．ｃｏｒｎ／ｖｉｅｗ／６０１５３４．　ｈｔｍ．　ＨＵＡＮＧ　Ｃｈｕｎｙｉｎｇ．Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔ　ｏｆ　ＣＲＭ　Ｓｙｓｔｅｍ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｏｎｇｑｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌ—　ｏｇｙ，２０１１（１１）：８６—９１．　Ｅ８］Ｓｉｅｂｅｌ　Ｂｏｏｋｓｈｅｌｆ　８．１［ＥＢ／ＯＩ　］．ｈｔｔｐ：／／ｄｏｃｓ．ｏｒａｃｌｅ．　ｃｏｍ／ｃｄ／Ｅ１４００４０１／ｈｏｍｅｐａｇｅ．ｈｔｍ．　Ｉ－ｓ３赵钧．中国电信ＣＲＭ系统建设经验与展望ｒ－ｊ］．电信科　学，２００８，２４（１）：７－１０．　ＺＨＡ０　Ｊｕｎ．Ｃｈｉｎａ　Ｔｅｌｅｃｏｍ　ＣＲＭ　Ｓｙｓｔｅｍ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　［９３方芳，刘大有．电信ＣＲＭ技术发展研究ＥＪ］．计算机Ｔ　程，２Ｏ１Ｏ，３６（５）：２７７—２８１．　ＦＡＮＧ　Ｆａｎｇ，ＬＩＵ　Ｄａｙｏｕ．Ｓｔｕｄｙ　ｏｎ　Ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　Ｅｘｐｅｒｉｅｎｃｅ　ａｎｄ　Ｐｒｏｓｐｅｃｔ［Ｊ］．Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｃｉ—　ｅｎｃｅ，２００８，２４（１）：７－１０．　Ｔｅｌｅｃｏｍ　ＣＲＭ　Ｔｅｃｈｎｏｌｏｇｙ１，Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，　２０１０，３６（５）：２７７　２８１．　Ｅ６］李敏，王海亮．中国通信企业如何实施ＣＲＭ１，Ｊ］．机械管　理开发，２００９，２４（２）：１２６—１２９．　ＬＩ　Ｍｉｎ，ＷＡＮＧ　Ｈａｉｌｉａｎｇ．Ｐｒａｃｔｉｃｅ　ｏｆ　ＣＲＭ　ｉｎ　Ｃｈｉｎｅｓｅ　［１ｏ］卢捍华，张凌云．电信ＣＲＭ中的客户特征管理［Ｊ］．电　信科学，２００７，２３（８）：４３—４６．　Ｉ　Ｕ　Ｈａｎｈｕａ，ＺＨＡＮＧ　Ｌｉｎｇｙｕｎ．Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｃｕｓ—　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｂｕｓｉｎｅｓｓ［Ｊ］．Ｍｅｃｈａｎｉｃａｌ　Ｍａｎａｇｅ—　ｍｅｎｔ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００９，２４（２）：１２６—１２９．　ｔｏｍｅｒ　Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｉｎ　ＣＲＭ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｔｅｌｅｃｏｍ［Ｊ￣．　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｓｃｉｅｎｃｅ，２００７，２３（８）：４３　４６．　乖　乖　尔　尔　乖　乔　替　！　不　带　彳　矫　币　’矫．　乖　乖　尔　（上接第２０４４页）　查找到实施仅花费七次ＣＰＵ周期和接触至少两个　高速缓存行。１．３ＧＨｚ的ＣＰＵ意味着２４ＧＢ／ｓ的　带宽使用量，这超过了可用的ＲＡＭ带宽。出于这　个原因，我们采用第二种方法，基于哈希表的分区。　基于哈希表分区技术的问题是需要所有的数　据首先被完全分割，然后才被处理。这个步骤在基　于磁盘的情况下，作为分区的临时空间通常被认为　ｔｅｃｔｕｒｅ－Ｃｏｎｓｅｉｏｕｓ　Ｈａｓｈｉｎｇ［Ｃ］／／Ｐｒｏｃ．ＳＩＧＭＯＤ　Ｄａ—　ＭｏＮ　Ｗｏｒｋｓｈｏｐ，Ｃｈｉｃａｇｏ，ＩＬ，ＵＳＡ，２００６．　Ｅ３３　Ｍ．一Ｃ．Ａｌｂｕｔｉｕ，Ａ．Ｋｅｍｐｅｒ，Ｔ．Ｎｅｕｍａｎｎ．Ｍａｓｓｉｖｅ　ｌｙｐａｒａｌｌｅｌ　ｓｏｒｔ—ｍｅｒｇｅ　ｊｏｉｎｓ　ｉｎ　ｍａｉｎ　ｍｅｍｏｒｙ　ｍｕｌｔｉ—ｃｏｒｅ　ｄａｔａｂａｓｅｓｙｓｔｅｍｓ１，Ｊ３．ＰＶＬＤＢ，２０１２，５（１０）：１０６４　１０７５．　［４］Ｓ．Ｆｕｓｈｉｍｉ，Ｍ　Ｋｉｔｓｕｒｅｇａｗａ，Ｈ．Ｔａｎａｋａ．Ａｎ　Ｏｖｅｒ—　ｖｉｅｗ　ｏｆ　ｔｈｅ　Ｓｙｓｔｅｍ　Ｓｏｆｔｗａｒｅ　ｏｆ　Ａ　Ｐａｒａｌｌｅｌ　Ｒｅｌａｔｉｏｎａｌ　Ｄａｔａｂａｓｅ　Ｍａｃｈｉｎｅ　ＧＲＡＣＥ￣Ｃ］／／Ｐｒｏｃ．ＶＬＤＢ，Ａｕｇｕｓｔ　１９８６．　是无限的。但是，主存储器容量不能认为是无限　的，这意味着如果数据划分期间不适合在ＲＡＭ　［５］ｃ．Ｂａｌｋｅｓｅｎ，Ｊ．Ｔｅｕｂｎｅｒ，Ｇ．Ａｌｏｎｓｏ，ｅｔ　ａ１．Ｍａｉｎ－　ｍｅｍｏｒｙ　ｈａｓｈ　ｊｏｉｎｓ　ｏｎ　ｍｕｌｔｉ—ｃｏｒｅ　ＣＰＵｓ：Ｔｕｎｉｎｇ　ｔｏ　ｔｈｅ　中，它不得不被保存到磁盘。由于优化时，在缓冲　区只有在极端情况下的处理是合理使用磁盘。为　此，使用尽可能分区（ＢＥＰ）方法，ＢＥＰ是交错划分　与执行基于散列的查询处理算子不使用Ｉ／Ｏ的技　术的分区方法。　ｕｎｄｅｒｌｙｉｎｇ　ｈａｒｄｗａｒｅ［Ｃ３／／Ｉｎ　ＩＣＤＥ，２０１３．　－Ｉ６］Ｍａｒｃｉｎ　Ｚｕｋｏｗｓｋｉ，Ｓａｎｄｏｒ　Ｈｅｍａｎ，Ｐｅｔｅｒ　ｏｎｃＢｚ．Ａｒｃｈｉ—　ｔｅｃｔｕｒｅ－Ｃｏｎｓｃｉｏｕｓ　Ｈａｓｈｉｎｇ［Ｃ］／／Ｐｒｏｃ．ＳＩＧＭＯＤ　Ｄａ—　ＭｏＮ　Ｗｏｒｋｓｈｏｐ，Ｃｈｉｃａｇｏ，ＩＬ，ＵＳＡ，２００６．　Ｈａｓｈｊｏｉｎ的矢量化方法，在应对未来大数据时　代，将是一个提高查询效率的优化方法，给优化器　生成查询计划树提供更多的组合。在执行器层面，　［７］Ｒａｓｍｕｓ　Ｐａｇｈ　ａｎｄ　Ｆｌｅｍｍｉｎｇ　Ｆｒｉｃｈｅ　Ｒｏｄｌｅｒ．Ｃｕｃｋｏｏ　ｈａｓｈｉｎｇ［Ｊ］．Ｊ．Ａｌｇｏｒｉｔｈｍｓ，２００４，５１（２）：１２２—１４４．　［８２　Ｎ．Ｓａｔｉｓｈ，Ｃ．Ｋｉｍ，Ｊ．Ｃｈｈｕｇａｎｉ，ｅｔ　ａ１．Ｆａｓｔ　ｓｏｒｔ　ｏｎ　ＣＰＵｓ　ａｎｄ　ＧＰＵｓ：Ａ　ｃａｓｅ　ｆｏｒ　ｂａｎｄｗｉｄｔｈ　ｏｂｌｉｖｉｏｕｓ　矢量化Ｈａｓｈｊｉｏｎ算子相对于Ｈａｓｈｊｏｉｎ算子　能有　大幅提高。针对目前的海量数据分析趋势，以及大　数据时代的到来，相信未来矢量化的方法提高　Ｈａｓｈｊｏｉｎ的效率将会得到大幅度的应用验证，也将　会大幅提升海量数据管理系统的响应性能。　参考文献　ＳＩＭＤ　ｓｏｒｔ［ｑ／／Ｉｎ　ＳＩＧＭＯＤ，２０１０．　Ｅ９］Ｒ．Ｍｕｌｌｅｒ，Ｊ．Ｔｅｕｂｎｅｒ，Ｇ．Ａｌｏｎｓｏ．Ｓｏｒｔｉｎｇ　ｎｅｔｗｏｒｋｓ　ｏｎＦＰＧＡｓ［Ｊ］．ＶＬＤＢ　Ｊ．，２０１２，２１（１）：１１２—１３２．　［１ｏ］ｃ．Ｋｉｍ，Ｅ．Ｓｅｄｌａｒ，Ｊ．Ｃｈｈｕｇａｎｉ，ｅｔ　ａ１．Ｓｏｒｔ　ｖｓ．ｈａｓｈ　ｒｅｖｉｓｉｔｅｄ：Ｆａｓｔ　ｏｉｎ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｎ　ｍｏｄｅｒｎ　ｍｕｌｔｉ－　ｃｏｒｅ　ＣＰＵｓＥＪ］．ＰＶＬＤＢ，２００９，２（２）：１３７８—１３８９．　，１１１３　Ｉｎｔｅｌ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｃｏｄｅ　ａｎａｌｙｚｅｒ［ＯＬ］．ｈｔｔｐ：／／ｓｏｆｔ—　ｗａｒｅ．ｉｎｔｅ１．ｃｏｍ／ｅｎ　ｕｓ／ａｒｔｉｃ１ｅｓ／ｉｎｔｅｌ—ａｒｃｈｉｔｅｃｔｕｒｅ—ｃｏｄｅ－　ａｎａｌｙｚｅｒ．Ｏｎｌｉｎｅ，ａｃｃｅｓｓｅｄ　Ｆｅｂｒｕａｒｙ　２０１３．　［１３　Ｓｔｅｆａｎ　Ｍａｎｅｇｏｌｄ，Ｐｅｔｅｒ　Ａ．Ｂｏｎｃｚ，Ｍａｒｔｉｎ　Ｌ．Ｋｅｒｓｔｅｎ．　Ｏｐｔｉ．一ｍｉｚｉｎｇ　Ｍａｉｎ－Ｍｅｍｏｒｙ　Ｊｏｉｎ　Ｏｎ　Ｍｏｄｅｒｎ　Ｈａｒｄｗａｒｅ　［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇ．，　２００２，１４（４）：７０９—７３０．　Ｉ　１２　ｌ　Ｃ．Ｋｉｍ，ｊ．Ｐａｒｋ，Ｎ．Ｓａｔｉｓｈ，ｅｔ　ａ１．ＣｌｏｕｄＲＡＭＳＯｒｔ：　ｆａｓｔ　ａｎｄ　ｅｃｉｅｎｔ　ｌａｒｇｅ－ｓｃａｌｅ　ｄｉｓｔｒｉｂｕｔｅｄ　ＲＡＭ　ｓｏｒｔ　ｏｎ　２２３　Ｍａｒｃｉｎ　Ｚｕｋｏｗｓｋｉ，Ｓａｎｄｏｒ　Ｈｅｍａｎ，Ｐｅｔｅｒ　ｏｎｃｚＢ．Ａｒｃｈｉ一　ｓｈａｒｅｄ—ｎｏｔｈｉｎｇ　ｃｌｕｓｔｅｒ［Ｃ］／／Ｉｎ　ＳＩＧＭＯＤ，２０１２．