基于共享Cache多核处理器的数据库哈希连接方法

摘要

本发明公开了一种基于共享Cache多核处理器的数据库哈希连接方法，该方法分为连接表划分和聚集连接两个阶段；连接表划分首先通过临时表生成模块生成临时表，然后临时表划分线程对临时表执行临时表划分，划分前根据临时表的大小确定合适的数据划分策略，并在临时表划分过程中决定临时表划分线程的合适启动时机以减少Cache访问冲突；聚集连接时，采用基于聚集大小分类的聚集连接执行方法，并优化了哈希连接时的内存访问。本发明确保哈希连接充分利用多核处理器的计算资源，哈希连接执行的加速比接近于处理器核心个数，从而大大的缩短了哈希连接执行时间。

说明书

技术领域

本发明主要涉及数据库查询执行技术，具体涉及数据库哈希连接的多线程执行优化方法。

背景技术

随着处理器晶体管数量的不断增加，处理器频率已达到现有条件下的极限，且能耗越来越大，所以处理器的发展趋势正从高主频的单核处理器转向片上多核处理器，从依靠指令级的并行转向线程级并行。目前2核和4核的处理器正成为市场的主流，而且内核数量仍在不断增加，极大地提高了单处理器的并行计算性能，相比较多核处理器普及之前，并行计算正成为主要的程序运行模式，并日益受到重视。与传统的SMP(Symmetrical Multi-Processing)系统相比，多核处理器不但从硬件成本上更易被采纳，而且由于芯片内的通信速度大大高于芯片间，多核处理器并行效率要高于SMP系统。对数据库而言，共享Cache可以减少数据重复，提高Cache利用率。但也正由于多核处理器一般共享二级Cache，造成了多线程之间比较容易发生共享Cache访问冲突，造成性能下降。与此同时，在多缓存体系结构中，随着内存价格不断下降和内存容量的不断增大，大容量内存数据库服务器正成为主流配置，磁盘I/O延迟逐渐得到缓解，而内存访问速度相对于Cache和寄存器差距明显，并且仍在不断扩大，Cache访问性能成为影响数据库性能的重要因素，处理器等待Cache从上一级存储器取数据造成的延迟正成为数据库系统的主要瓶颈。

目前的数据库服务器一般都已采用多核处理器和大容量内存，甚至一些高端服务器配置了多个多核处理器，并行计算能力得到极大提高。虽然数据库采用的一个客户端对应一个线程的体系结构，使得多个客户端提高的查询请求，在服务器端执行时能够利用多核处理器的并行计算优势，但目前查询内部的执行多采用单线程，使得单个查询的执行不能充分利用处理器技术进步带来的性能提升。而且多核处理器普遍采用共享二级Cache的体系结构，在某些类型的数据库查询执行时，给传统的多线程执行方式带来了潜在的性能瓶颈，特别是在大内存容量数据库服务器中，这个问题更加突出。数据库中哈希连接时最常见的连接运算之一，对数据库系统的性能起着至关重要的作用。针对哈希连接的性能优化主要有两种途径，利用线程级并行优化哈希连接或改善哈希连接执行时的Cache访问性能来提高性能。上述两种优化方法在共享二级Cache多核处理器中会存在以下缺点：

1)多线程哈希连接执行时，由于哈希表需要被重复访问，在共享二级Cache的多核处理器中，发生Cache访问冲突的概率较高。严重的Cache访问冲突会极大地降低多线程的优化效果。

2)通过优化Cache访问性能优化哈希连接在多核处理器中不能充分发挥其并行线程执行的优势，极大地浪费了处理器的计算资源，导致性能相比较多线程哈希连接有巨大的差距。

最近几年哈希连接的多线程优化研究主要有，微软研究中心的Zhou JinRen等人提出在SMT(Simultaneous Multithreading)处理器中，将元组分为奇偶两类在两个线程之间划分，实现并行执行数据库操作。还提出利用主线程和Helper线程模式优化Data Cache，从而达到优化哈希连接性能的目的；美国威斯康星大学的Philip等人提出利用流水线式多线程模式优化哈希连接，但其未研究如何避免线程间的共享Cache访问冲突带来的问题。所以目前尚未有基于共享二级Cache CMP优化哈希连接的研究工作，特别是减少多线程之间的共享二级Cache访问冲突的研究。

发明内容

本发明要解决的技术问题是：针对目前数据库哈希连接在配置了共享二级Cache多核处理器的大内存容量数据库服务器中，处理器并行计算资源利用率低下的问题，本发明提供了一种基于数据划分的多线程哈希连接处理方法。该方法充分利用处理器的并行计算资源的同时，根据共享二级Cache的数据访问特点，优化多线程执行时的Cache访问性能。

本发明解决其技术问题所采用的技术方案是：分为连接表划分和聚集连接两个步骤；连接表划分阶段首先由临时表生成模块读取表中的页面生成临时表，再由临时表划分模块将临时表划分成若干个小的聚集得到聚集表，连接表划分中的两种优化模块在运行时设定连接表划分中各种线程运行的参数，以减少共享Cache访问冲突；聚集连接阶段由多个聚集连接线程同时执行聚集连接操作，连接线程工作集分配模块在运行时设定聚集连接线程的各种参数。

所述的连接表划分阶段包含三个模块：临时表生成模块，临时表划分模块和线程优化模块；线程优化模块则包括页面读取优化模块和临时表划分优化模块；临时表由Hash Cell组成，Hash Cell的结构为<HashValue，KeyValue，TID>，其中HashValue为连接列哈希值，KeyValue为连接列的值，TID为元组ID；临时表划分时，处理HashValue的D位二进制数据，每次数据划分处理D_i位HashValue值，通过P次划分将表分成$H={\Pi }_1^p{H}_p$个聚集。

所述的临时表生成模块，包含两类线程：页面预取线程和页面读取线程；在页面读取线程执行前，根据表的页面号范围，从页面缓存模块获取连接执行前已在页面缓存中的页面集合和未在页面缓存中的页面集合；页面预取线程首先从磁盘读取连接执行前未在页面缓存中的页面，由页面读取线程处理，然后页面读取线程再处理连接执行前已在页面缓存中的页面集合；页面读取优化模块则用于协调页面预取线程和页面读取线程的执行，并设置线程执行参数。

所述的临时表划分模块，在运行时根据参与划分的临时表数据量的大小确定合适的临时表划分策略；在临时表划分时，临时表划分优化模块根据每次数据划分后产生的聚集情况确定临时表划分线程的启动时机；具体如下：根据临时表划分参数D的阙值MaxD，结合处理器核心数N决定具体的数据划分策略：

(1)D＜MaxD时，可令D_i＝1，即每次数据划分处理1位HashValue，从而避免使用交换表，减少Cache访问冲突；

(2)D≥MaxD时，为了减少数据划分次数较多造成的数据划分代价，令D_i＝D/P，即一个数据划分处理DII位HashValue，减少数据划分次数。

所述的页面读取优化模块，用于设置最佳的页面读取线程启动时机，当页面预取线程预取的页面数据量与处理这些页面所需的临时表数据量之和接近于二级Cache容量时，即可启动页面读取线程处理被预取的页面。

所述的临时表划分优化模块，在运行时根据聚集的平均大小决定临时表划分线程的启动时机；具体方法如下：

(I)D＜MaxD时，令$H_j=\underset{i=1}{\overset{j}{\Pi }}{H}_i$为第j次临时表划分后生成的聚集数，

TTSize＝L.tuple*CellSize为临时表大小；根据每次临时表划分后生成的聚集数在确定具体的临时表划分线程启动策略。

(II)D≥MaxD时，在临时表划分前，判断是否大于C；如果大于C则在第一次临时表划分完成后启动Min(H₁，N)个临时表划分线程，否则在每次临时表划分完成后，判断$\frac{2i*\mathrm{TTSize}}{H_j}\le C$是否成立，i表示启动的临时表划分线程个数，下同，2≤i≤N，如果成立则可启动Max(i)个临时表划分线程。而在时，如果仍不存在满足条件的i，则可立即启动N个临时表划分线程。

所述的聚集连接阶段，首先连接线程工作集分配模块基于聚集大小分类的原则为聚集线程划分好工作集；聚集连接执行时根据聚集分类的大小，启动合适的聚集连接线程个数，从大到小处理每个聚集分类中的聚集对，并通过减少哈希桶所需的内存量，优化了聚集连接执行的内存访问。

所述的连接线程工作集分配模块，用于遍历临时表划分生成的两个聚集集合，根据每对聚集的大小ClusterPairSize，结合聚集连接线程个数JTNum和二级Cache容量C将聚集划分至对应的聚集分类WorkSet中，保证聚集连接线程处理某个聚集分类中的聚集对时，处理的数据小于或等于二级Cache容量，减少Cache访问冲突。

所述聚集连接执行，除了WorkSet[0]，对于WorkSet[j]中的聚集对，根据2j≤N是否满足分为两种情况：

(a)2j≤N满足，将聚集连接线程分为j组，每组由个聚集连接线程组成，执行一个聚集对的连接运算；

(b)如果2j＞N，启动j个连接线程，每个聚集连接线程均匀分配聚集对即可；

所述聚集连接执行时，首先处理WorkSet[1]中的聚集对，接着处理WorkSet[2]，以此类推；最后启动N个聚集连接线程处理WorkSet[0]。

本发明与现有技术相比所具有的优点：与传统的多线程哈希连接算法相比，本发明能够极大地减少线程访问共享二级Cache时的Cache访问冲突，并且使得处理器各个核心的负载均衡，从而充分利用多核处理器的计算资源。

由于本发明基于多线程执行哈希连接，并充分考虑了共享二级Cache对多线程执行的影响，以及处理器负载均衡，因而使得本发明提出的多线程执行框架在执行时能够极大地减少因Cache访问冲突造成的处理器等待数据从内存取到Cache的时间，而且处理器核心间的负载在多数情况下是均衡的，所以本发明能够充分地利用多核处理器的并行计算资源，从而取得最大的性能提升。

附图说明

图1为多线程Hash连接执行框架；

图2为并发内存访问；

图3为哈希连接内存访问优化示意图；

具体实施方式

下面结合附图及具体实施方式详细介绍本发明。

本发明的基于共享Cache多核处理器的多线程数据库哈希连接方法，包括连接表划分和聚集连接两个步骤。

第一步：连接表划分。对参与连接的两个表(L和R)，按照连接列的哈希值进行数据划分。如图1所示，图的左半部分为连接表划分阶段框架图。连接表划分执行时，首先由临时表生成模块生成临时表，然后由临时表划分模块对临时表进行数据划分。具体步骤如下：

A、获取表中所有页面的页面号集合，然后遍历该页面号集合，通过数据库页面缓存模块的哈希表映射函数计算页面映射至哈希表中的具体位置，判断该页面当前是否在页面缓存中。遍历完该页面号集合后，即可获得两个页面号集合：未在页面缓存中的页面集合(PageNotInBuf)和已在页面缓存中的页面集合(PageInBuf)。

B、临时表生成时，处理上述A获得的两个页面集合PageNotInBuf和PageInBuf。首先处理PageNotInBuf中的页面，通过页面预取线程从磁盘将页面读入页面缓存中，并将已读取的页面号放入一个全局队列，供页面读取线程并行处理，其中通过页面读取优化模块决定最佳的页面读取线程启动时机。页面预取线程处理PageNotInBuf时，根据页面号是否连续，分为两种执行模式：组读取和单页面读取。组读取为读取页面号连续的页面，因此可以利用数据库支持的页面组读取功能，一次I/O操作读取多个页面。当PageNotInBuf中页面处理完毕，页面读取线程处理PageInBuf，完成临时表生成运算。

C、临时表划分时，处理上述B生成的临时表，根据键值的哈希值，将临时表中的键值划分至对应的聚集中。临时表划分需要多次划分用于处理二进制的哈希值，每次处理D_i位，通过P次划分将临时表划分成${H=\Pi }_1^p{H}_p$个聚集，其中通过临时表划分优化模块决定在第几次聚集划分完成后启动临时表划分线程，以最大限度的减少临时表划分线程间的Cache访问冲突。由于完成划分后的每个聚集非常小，适合于通过简单的哈希连接算法执行连接操作，也便于连接时能全部读入二级Cache。

上述步骤B中，页面读取优化模块在页面预取线程组读取或单页面读取的页面达到一定数量时再启动页面读取线程，以避免页面读取线程的频繁启动代价。同时为了减少因页面读取线程访问临时表将预取的数据页面替换出二级Cache造成的Cache访问冲突，需要设置页面读取线程最佳启动时机MaxPageNum。MaxPageNum的设置方法如下，令预取的数据页面达到MaxPageNum时启动页面读取线程，可得对应的页面读取线程需要访问的临时表数据量为MaxPageNum*M.tuple*Cellsize，其中M.tuple表示页面中元组个数，CellSize表示临时表数据项的大小。因此该次页面处理线程启动所需要访问的全部数据量Totalsize＝MaxPageNum*M.tuple*Cellsize+Maxpage*M.size，令Totalsize≤C，可得$\mathrm{MaxPageNum}=\frac{C}{M.\mathrm{size}+M.\mathrm{tuple}*\mathrm{CellSize}}.$

上述步骤C中，临时表划分优化模块在每次聚集划分完成后根据当前的聚集的平均大小，然后结合启动的临时表划分线程个数判断此时启动多线程划分，临时表划分线程之间是否会产生比较严重的Cache访问冲突，如果Cache访问冲突较少，则可立即启动多线程划分，否则继续进行单线程临时表划分处理。根据不同的数据划分策略，采用不同的临时表划分方法，具体如下：

(1)、D＜MaxD时，具体的数据划分方法为：每次临时表划分只处理一个比特的哈希值。比如有临时表，其D＝3、P＝3，即需要3次临时表划分，每次处理1比特的哈希值。第一次临时表划分时，从临时表TempTable的起始位置遍历其中的Hash Cell，如果第D位为0，则继续遍历TempTable，直到其值为1。然后从TempTable尾部开始遍历，如果第D位为1，则继续遍历TempTable直到其值为0，然后交换这两个Hash Cell，然后从顶部开始继续开始遍历，重复上述运算。当第一次临时表划分完成后，对于生成的各个子聚集，按照上述步骤处理HashValue的第D-1位数据。当处理完D位数据后，即完成了临时表划分阶段。

临时表划分优化模块则根据每次临时表划分后生成的聚集数，将临时表划分线程的启动时机分为三种情况，令$H_j=\underset{i=1}{\overset{j}{\Pi }}{H}_i$为第j次临时表划分后生成的聚集数，TTSize＝L.tuple*CellSize为临时表大小。

(a)H_j≤N且TTSize≤C，表明数据量很少，第一次临时表划分完成后，即可完成连接表划分进入聚集连接阶段；

(b)H_j≤N且TTSize＞C时，在每次临时表划分完成后，判断$\frac{i*\mathrm{TTSize}}{H_j}\le C$是否满足，i表示启动的线程个数，下同，2≤i≤H_j。如果存在i满足该条件，启动Max(i)个临时表划分线程(Max(i)表示满足条件的i中最大的i，下同)，此时不会出现较严重的Cache访问冲突，如果不存在i满足该条件，则进入情况(C)；

(c)此时H_j＞N，在每次临时表划分完成后，判断$\frac{i*\mathrm{TTSize}}{H_j}\le C$是否满足，其中2≤i≤N，如果存在满足该条件的i且Max(i)＜N，此时启动Max(i)个临时表划分线程。

(2)、D≥MaxD时，每次临时表划分可以处理多个比特哈希值。比如有临时表，其D＝3，P＝2，即需要2次临时表划分，第一次处理2比特哈希值，第二次处理1比特哈希值，同时需要交换表实现临时表划分时的数据交换。临时表划分优化模块在临时表划分前，判断是否大于C。如果大于C则在第一次临时表划分完成后启动Min(H₁，N)个临时表划分线程，否则在每次临时表划分完成后，判断$\frac{2i*\mathrm{TTSize}}{H_j}\le C$是否成立(2≤i≤N)，如果成立则可启动Max(i)个临时表划分线程，而在时，如果仍不存在满足条件的i，则可立即启动N个临时表划分线程。

上述处理过程中，MaxD的取值由实验证实最佳的取值为7。启动聚集线程的时机$j={\log }_2\frac{\mathrm{Max}\left(i\right)}{C}*\mathrm{TTSize},$如果j接近P则失去了启动多线程的意义。因此需要在临时表划分开始前，先由$j={\log }_2\frac{i}{C}*\mathrm{TTSize}$(其中i取值为2≤i≤N)计算出(i，j)值，再以(i，j)为参数，根据临时表划分的加速比公式$S(A_i,P,j)=\frac{{\mathrm{PA}}_i}{P+j(A_i-1)}$计算出加速比s(其中A_i为临时表划分线程数，j为在P次聚集划分中，聚集划分线程的启动时机)，选择最大s对应的(i，j)，如果此j值大于MaxJ则无需$\frac{i*\mathrm{TTSize}}{H_j}\le C$满足(实验测试表明MaxJ＝D/2)，在H_j≥N时即可启动N个聚集划分。在第j次临时表划分完成后启动，这时有H_j个聚集，启动N个临时表划分线程，将H_j个聚集均匀分配给N个临时表划分线程。

第二步：聚集连接。如图1的右半部分所示，处理临时表划分生成的两个聚集表L和R。对于第一步生成的两个聚集表，对满足连接条件的聚集之间执行多线程哈希连接操作。首先由连接线程工作机分配模块遍历临时表划分生成的两个聚集表，根据每对聚集的大小ClusterPairSize，结合聚集连接线程个数JTNum和二级Cache容量C将聚集划分至对应的聚集分类中，保证聚集连接线程处理某个聚集分类中的聚集对时，处理的数据小于或等于二级Cache容量，减少Cache访问冲突。具体如下：

如果$\frac{C}{K+1}<\mathrm{ClusterPairSize}\le \frac{C}{K}(1\le K\le \mathrm{JTNum}-1),$则可将该聚集对归于WorkSet[K]；如果$0<\mathrm{ClusterPairSize}\le \frac{C}{\mathrm{JTNum}},$则将该聚集对归于WorkSet[JTNum]；如果ClusterPairSize＞C，则将该聚集对归于WorkSet[0]。比如

令L[j]表示一个聚集，L[j].hashvalue表示该聚集对应的hashvalue值，如图1的L[0].hashvalue＝000。聚集连接线程执行前，由连接线程工作集分配模块遍历L和R，获取满足连接条件的聚集对，如图1中所示，满足连接条件的聚集对为(L[0]，R[0])，(L[1]，R[1])，(L[2]，R[4])，(L[3]，R[5])，(L[6]，R[6])，在获得聚集对的同时，根据这些聚集对各自的ClusterPairSize放入对应的WorkSet中。根据上述聚集分类的结果WorkSet即可执行聚集连接，将聚集对分配给各个聚集连接线程执行。获得WorkSet后根据启动聚集连接线程前，WorkSet的数组下标j与N的关系2j≤N是否满足分为两种情况分别进行处理：

(I)如果2j≤N满足，将连接线程分为j组，每组由个聚集连接线程组成，执行一个聚集对的连接运算，每组线程之间平均分配该聚集对中Probe表的元组。同时指定某个线程在Probe操作执行前构建Hash表，将Hash桶加入Hash表中，组内其它线程需等待Hash表构建完成。

(II)如果2j＞N，启动j个连接线程，每个连接线程均匀分配聚集对即可；，然后根据WorkSet的下标启动合适个数的聚集连接线程处理该WorkSet中的聚集对。比如对于WorkSet[2]中的聚集对，处理器核心个数为4，将聚集连接线程分为2组，每组由2个连接线程组成，每组中的聚集连接线程同时只处理一个聚集对的哈希连接运算，即该线程组中的两个聚集连接线程平分Probe表中的数据，同时访问哈希表。

聚集连接阶段的Hash连接内存访问优化方法如下：

在连接表划分阶段，生成临时表的同时构建数据量较大的表的Hash表数组H[i]，同时记录映射到每个H[i]的元组个数H[i].BucketNum，避免Hash桶插入Hash表时浪费内存空间。聚集连接阶段生成Hash桶时，如果有数据映射到H[i]，则一次性从已分配好的内存中获取能容纳H[i].BucketNum个Hash桶的内存块。该存储结构减少了Hash表所需内存量，从而降低了Cache访问冲突的可能性，因为Hash桶以数组存储，无须指针即可遍历H[i]中所有Hash桶。

图1中的各种线程以背景线程方式实现，在适当的时机被启动，赋予工作集，完成任务后进入”睡眠”状态。在数据库服务启动时，生成并初始化图1中的各种线程，并进入”睡眠”状态。连接表划分和聚集连接处理过程启动的线程，在完成任务后同样也作为背景线程进入”睡眠”状态。

如图2所示，为本发明所采用的并发内存访问结构图。用于临时表生成时，页面读取线程并行的向临时表中写入Hash Cell。它将临时表分成若干个小的buffer chunk，每个页面读取线程都以buffer chunk为单位读/写内存，线程访问时无需并发访问控制，只需要对该并发内存的管理数据进行互斥访问即可。比如标识该缓存中已经被写入数据的buffer chunk个数，空闲buffer chunk个数等。

如图3所示，为本发明的Hash连接内存访问优化。通过在临时表划分时，构建哈希表数据H[i]，同时记录映射到每个H[i]的元组个数H[i].Bucket-Num。聚集连接阶段生成哈希桶时，如果有数据映射到H[i]，则一次性从已分配好的内存中获取能容纳H[i].BucketNum个哈希桶的内存块。比如图2中，对R[0]构建哈希表时，根据R[0].Hashvalue对应的H[R[0].Hashvalue].BucketNum即可获得映射到该哈希表数组中的哈希桶的个数，然后即可分配H[R[0].Hashvalue].BucketNum个哈希桶，避免了指针存储空间。

本发明说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。