一种哈希连接算子间数据传递的方法及装置

摘要

本发明实施例涉及数据库技术领域，公开了一种哈希连接算子间数据传递的方法及装置，该方法包括连接外表和预先生成的哈希表；根据所述外表更新所述哈希表，获得更新后的哈希表；检测是否存在下一个外表；若检测到存在所述下一个外表，则连接所述下一个外表和所述更新后的哈希表。实施本发明实施例，可以在哈希连接算子间以哈希表的方式进行数据传递，提高了数据库的查询性能。

说明书

技术领域

本发明涉及数据库技术领域，具体涉及一种哈希连接算子间数据传递的 方法及装置。

背景技术

SQL（Structured Query Language，结构化查询语言)中的连接语句可以将 数据库中的两个或多个表连接起来，且哈希连接是大多数数据库最常用的连 接算法，哈希连接利用哈希表实现两个或多个表的等值连接，其原理为：构 建哈希表，即在要进行连接的两个表中，选取元组较少的一个表（又称内表）， 将其中的元组采用某个哈希函数和某种冲突解决方法构建哈希表；探测哈希 表，即选取两个表中元组较多的表作为探测表（又称外表），取探测表中的每 一个元组到构建好的哈希表中进行哈希查找，找到能够实现等值连接的元组； 输出，即如果探测表中的某个元组与哈希表中的某个元组满足等值连接的条 件，则将它们进行连接并输出。

现有的哈希连接实现中，哈希连接算子之间通过元组的方式进行数据传 递，这种通过元组进行数据传递的方式会导致连接后的元组再次组成哈希表 的情况，这严重影响了数据库的查询性能。

发明内容

本发明实施例公开了一种哈希连接算子间数据传递的方法及装置，用于 解决现有的哈希连接算子间以元组的方式进行数据传递而造成数据库查询性 能降低的问题。

本发明实施例第一方面提供了一种哈希连接算子间数据传递的方法，所 述方法包括：

连接外表和预先生成的哈希表；

根据所述外表更新所述哈希表，获得更新后的哈希表；

检测是否存在下一个外表；

若检测到存在所述下一个外表，则连接所述下一个外表和所述更新后的 哈希表。

在本发明实施例第一方面的第一种可能的实现方式中，所述连接外表和 预先生成的哈希表之前，所述方法还包括：

生成哈希表。

结合本发明实施例第一方面或本发明实施例第一方面的第一种可能的实 现方式，在本发明实施例第一方面的第二种可能的实现方式中，所述连接外 表和预先生成的哈希表包括：

获取所述外表中的任意一条元组；

探测所述哈希表中是否存在能够与所述外表中的任意一条元组进行等值 连接的元组；

若探测出所述哈希表中存在能够与所述外表中的任意一条元组进行等值 连接的元组，则将所述哈希表中的所述元组与所述外表中的任意一条元组连 接并生成连接元组，其中，所述连接元组包括用于识别所述连接元组的标识 信息；

将所述连接元组插入所述哈希表。

结合本发明实施例第一方面的第二种可能的实现方式，在本发明实施例 第一方面的第三种可能的实现方式中，所述根据所述外表更新所述哈希表， 获得更新后的哈希表包括：

判断所述外表中是否还存在未探测所述哈希表的元组；

若判断出所述外表中不存在未探测所述哈希表的元组，则删除所述哈希 表中不包括所述标识信息的元组。

结合本发明实施例第一方面，在本发明实施例第一方面的第四种可能的 实现方式中，所述方法还包括：

若检测出不存在所述下一个外表，则输出所述更新后的哈希表。

本发明实施例第二方面提供了一种哈希连接算子间数据传递的装置，所 述装置包括：

连接单元，用于连接外表和预先生成的哈希表；

更新单元，用于根据所述外表更新所述哈希表，获得更新后的哈希表；

检测单元，用于检测是否存在下一个外表；

所述连接单元，还用于在所述检测单元检测到存在所述下一个外表时， 连接所述下一个外表和所述更新后的哈希表。

在本发明实施例第二方面的第一种可能的实现方式中，所述装置还包括：

生成单元，用于生成哈希表。

结合本发明实施例第二方面或本发明实施例第二方面的第一种可能的实 现方式，在本发明实施例第二方面的第二种可能的实现方式中，所述连接单 元包括获取子单元、探测子单元、连接子单元以及插入子单元，其中：

所述获取子单元，用于获取所述外表中的任意一条元组；

所述探测子单元，用于探测所述哈希表中是否存在能够与所述外表中的 任意一条元组进行等值连接的元组；

所述连接子单元，用于在所述探测子单元探测出所述哈希表中存在能够 与所述外表中的任意一条元组进行等值连接的元组时，将所述哈希表中的元 组与所述外表中的任意一条元组连接并生成连接元组，其中，所述连接元组 包括用于识别所述连接元组的标识信息；

所述插入子单元，用于将所述连接元组插入所述哈希表。

结合本发明实施例第二方面的第二种可能的实现方式，在本发明实施例 第二方面的第三种可能的实现方式中，所述更新单元包括判断子单元以及删 除子单元，其中：

所述判断子单元，用于判断所述外表中是否还存在未探测所述哈希表的 元组；

所述删除子单元，用于在所述判断子单元判断出所述外表中不存在未探 测所述哈希表的元组时，删除所述哈希表中不包括所述标识信息的元组。

结合本发明实施例第二方面，在本发明实施例第二方面的第四种可能的 实现方式中，所述装置还包括：

输出单元，用于在所述检测单元检测出不存在所述下一个外表时，输出 所述更新后的哈希表。

实施本发明实施例，具有如下有益效果：连接外表和预先生成的哈希表 并更新哈希表，若检测到还存在下一个外表，则连接下一个外表和更新后的 哈希表，可见，本发明实施例中哈希连接算子之间是以哈希表的方式进行数 据传递的，这种数据传递的方式提高了数据库的查询性能。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例中所需 要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明 的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提 下，还可以根据这些附图获得其他的附图。

图1是本发明实施例公开的一种哈希连接算子间数据传递的方法的流程 示意图；

图2是本发明实施例公开的另一种哈希连接算子间数据传递的方法的流 程示意图；

图3是本发明实施例公开的一种生成哈希表的流程示意图；

图4是本发明实施例公开的一种连接外表和哈希表的流程示意图；

图5是本发明实施例公开的一种更新后的哈希表的结构示意图；

图6是本发明实施例公开的一种哈希连接算子间数据传递的装置的结构 示意图；

图7是本发明实施例公开的另一种哈希连接算子间数据传递的装置的结 构示意图；

图8是本发明实施例公开的又一种哈希连接算子间数据传递的装置的结 构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行 清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而 不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做 出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例提供了一种哈希连接算子间数据传递的方法及装置，可以 在哈希连接算子间以哈希表的方式进行数据传递，提高了数据库的查询性能。 以下分别进行详细说明。

请参阅图1，图1是本发明实施例公开的一种哈希连接算子间数据传递的 方法的流程示意图。其中，图1所示的方法可以应用于多媒体数据库、移动数 据库、空间数据库、信息检索系统、分布式信息检索系统以及专家决策系统 等，本发明实施例不做限定。如图1所示，该方法可以包括以下步骤：

S101、连接外表和预先生成的哈希表。

连接（join）是关系数据库中最重要的查询，用于根据两个或多个表中的 列之间的关系从两个或多个表中查询结果，且哈希连接是比较常用的一种两 个或多个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接算 法。

进行哈希连接的两个或多个表可以分为两类：内表和外表，其中，内表 是两个或多个表中的小表且是用于生成哈希表的表，剩余的表是不需要生成 哈希表的外表，又称之为探测表。其中，生成哈希表的方法可以包括直接定 址法、数字分析法、平方取中法、折叠法、除留余数法以及随机数法等，本 发明实施例不做限定。

本发明实施例中的哈希表可以由内表的每条元组（每行记录）根据某个 哈希函数和某种冲突解决方法构建而成。举例来说，假设用于生成哈希表的 内表为table1，该内表table1有两个属性id和city，则生成哈希表的过程可以如 图3所示，图3是本发明实施例公开的一种生成哈希表的流程示意图，如图3所 示，生成哈希表的方法为除留余数法，内表中的两条元组采用Hash(key)=id%10 （1%10=1，11%10=1）的哈希函数构建出图3中的哈希表。

作为一种可选的实施方式，连接外表和预先生成的哈希表可以具体包括 以下步骤：

获取外表中的任意一条元组；

探测哈希表中是否存在能够与外表中的任意一条元组进行等值连接的元 组；

若探测出哈希表中存在能够与外表中的任意一条元组进行等值连接的元 组，则将哈希表中的元组与外表中的任意一条元组连接并生成连接元组，其 中，连接元组包括用于识别连接元组的标识信息；

将连接元组插入哈希表。

举例来说，如图4所示，图4是本发明实施例公开的一种连接外表和哈希 表的流程示意图。表table2是要与哈希表进行等值连接的外表（又称探测表）， 假设进行等值连接的SQL语句为：select table1.id,table1.city,table2.level from  table1,table2where table1.id=table2.id，连接外表和哈希表的流程可以为：取出 table2中的一条元组（1，level1），然后元组（1，level1）到哈希表中去探测， 探测出哈希表中的（1，beijing）可以实现与元组（1，level1）的等值连接， （1，beijing）与（1，level1）进行连接后的元组为（1，beijing，level1），将 连接后的元组插入到哈希表中，之后取外表table2中的下一条元组到哈希表中 进行探测，过程与（1，level1）的探测过程一样，这里不再详细描述，直到 外表table2中的元组全部探测了哈希表，外表和哈希表的连接才算结束。

本发明实施例中，区分哈希表中的连接元组与一般元组的标识信息可以 是元组中属性的个数，也可以是为连接元组添加的一个flag属性（若哈希表要 与多个外表进行连接，则每连接一次就更新flag的值），本发明实施例不做限 定。

S102、根据外表更新哈希表，获得更新后的哈希表。

作为一种可选的实施方式，根据外表更新哈希表，获得更新后的哈希表 可以包括：

判断外表中是否还存在未探测哈希表的元组；

若判断出外表中不存在未探测哈希表的元组，则删除哈希表中不包括标 识信息的元组。

本发明实施例中，当外表中还存在未探测哈希表的元组时，则继续取外 表中的元组探测哈希表；当外表中的元组全部探测了哈希表之后，就更新哈 希表，即删除哈希表中的非连接元组。

举例来说，更新后的哈希表可以如图5所示，图5是本发明实施例公开的 一种更新后的哈希表的结构示意图，图5是由图4中的哈希表删除非连接元组 （1，beijing）以及（11，shanghai）后得到的。

S103、检测是否存在下一个外表。

本发明实施例中，要进行等值连接的表可以是两个表，也可以是多个表， 若检测到存在下一个外表，则执行步骤S104，若检测到不存在下一个外表， 则直接输出更新后的哈希表。

S104、若检测到存在下一个外表，则连接下一个外表和更新后的哈希表。

本发明实施例中，若还存在下一个外表，则将步骤S102中更新后的哈希 表作为新的哈希表与下一个外表进行连接，其连接过程与步骤S101中的过程 一样，这里不再进行详细的描述。

实施本发明实施例具有如下有益效果：连接外表和预先生成的哈希表后， 更新哈希表，若存在下一个外表，则连接更新后的哈希表和下一个外表。本 发明实施例中，无论有多少个要进行连接的表，一个连接过程和下一个连接 过程之间传递的是哈希表，即从第一个连接开始到最后一个连接结束，整个 过程中只有一个不断更新的哈希表，这提高了数据库的查询性能。

请参阅图2，图2是本发明实施例公开的另一种哈希连接算子间数据传递 的方法的流程示意图。其中，图2所示的方法可以应用于多媒体数据库、移动 数据库、空间数据库、信息检索系统、分布式信息检索系统以及专家决策系 统等，本发明实施例不做限定。如图2所示，该方法可以包括以下步骤：

S201、生成哈希表。

本发明实施例中，哈希表可以由内表中的每条元组根据某个哈希函数和 某种冲突解决方法构建而成，生成哈希表的方法可以包括直接定址法、数字 分析法、平方取中法、折叠法、除留余数法以及随机数法等，本发明实施例 不做限定。

举例来说，假设用于生成哈希表的内表为table1，该内表table1有两个属性 id和city，则生成哈希表的过程可以如图3所示，图3是本发明实施例公开的一 种生成哈希表的流程示意图。

S202、连接外表和预先生成的哈希表。

作为一种可选的实施方式，连接外表和预先生成的哈希表可以包括以下 步骤：

获取外表中的任意一条元组；

探测哈希表中是否存在能够与外表中的任意一条元组进行等值连接的元 组；

若探测出哈希表中存在能够与外表中的任意一条元组进行等值连接的元 组，则将哈希表中的元组与外表中的任意一条元组连接并生成连接元组，其 中，连接元组包括用于识别连接元组的标识信息；

将连接元组插入哈希表。

举例来说，如图4所示，图4是本发明实施例公开的一种连接外表和哈希 表的流程示意图。表table2是要与哈希表进行等值连接的外表（又称探测表）， 假设进行等值连接的SQL语句为：select table1.id,table1.city,table2.level from  table1,table2where table1.id=table2.id，连接外表和哈希表的流程可以为：取出 table2中的一条元组（1，level1），然后元组（1，level1）到哈希表中去探测， 探测出哈希表中的（1，beijing）可以实现与元组（1，level1）的等值连接， （1，beijing）与（1，level1）进行连接后的元组为（1，beijing，level1），将 连接后的元组插入到哈希表中，之后取外表table2中的下一条元组到哈希表中 进行探测，过程与（1，level1）的探测过程一样，这里不再详细描述，直到 外表table2中的元组全部探测了哈希表，外表和哈希表的连接才算结束。

本发明实施例中，区分哈希表中的连接元组与一般元组的标识信息可以 是元组中属性的个数，也可以是为连接元组添加的一个flag属性（若哈希表要 与多个外表进行连接，则每连接一次就更新flag的值），本发明实施例不做限 定。

S203、根据外表更新哈希表，获得更新后的哈希表。

作为一种可选的实施方式，根据外表更新哈希表，获得更新后的哈希表 可以包括：

判断外表中是否还存在未探测哈希表的元组；

若判断出外表中不存在未探测哈希表的元组，则删除哈希表中不包括标 识信息的元组。

本发明实施例中，当外表中还存在未探测哈希表的元组时，则继续取外 表中的元组探测哈希表；当外表中的元组全部探测了哈希表之后，就更新哈 希表，即删除哈希表中的非连接元组。

举例来说，更新后的哈希表可以如图5所示，图5是本发明实施例公开的 一种更新后的哈希表的结构示意图，图5是由图4中的哈希表删除非连接元组 （1，beijing）以及（11，shanghai）后得到的。

S204、检测是否存在下一个外表。

本发明实施例中，要进行等值连接的表可以是两个表，也可以是多个表， 若检测到不存在下一个外表，则执行步骤S205，若检测到存在下一个外表， 则连接下一个外表和更新后的哈希表，且其连接过程可以如步骤S202一样， 这里不再详细描述。

S205、若检测出不存在下一个外表，则输出更新后的哈希表。

实施本发明实施例具有如下有益效果：本发明实施例中，无论有多少个 要进行连接的表，一个连接过程和下一个连接过程之间传递的是哈希表，即 从第一个连接开始到最后一个连接结束，整个过程中只有一个不断更新的哈 希表，这提高了数据库的查询性能。

请参阅图6，图6是本发明实施例公开的一种哈希连接算子间数据传递的 装置的结构示意图。如图6所示，该装置600可以包括连接单元601、更新单元 602以及检测单元603，其中：

连接单元601用于连接外表和预先生成的哈希表。

更新单元602用于根据外表更新哈希表，获得更新后的哈希表。

本发明实施例中，当外表中还存在未探测哈希表的元组时，则继续取外 表中的元组探测哈希表；当外表中的元组全部探测了哈希表之后，就更新哈 希表，即删除哈希表中的非连接元组。

举例来说，更新后的哈希表可以如图5所示，图5是本发明实施例公开的 一种更新后的哈希表的结构示意图，图5是由图4中的哈希表删除非连接元组 （1，beijing）以及（11，shanghai）后得到的。

检测单元603用于检测是否存在下一个外表。

连接单元601还用于在检测单元603检测到存在下一个外表时，连接下一 个外表和更新后的哈希表。

本发明实施例中，若检测单元603检测到还存在下一个外表，则连接单元 601将更新单元602获得的更新后的哈希表作为新的哈希表与下一个外表进行 连接。

实施本发明实施例具有如下有益效果：连接单元601连接外表和预先生成 的哈希表后，更新单元602更新哈希表，若检测单元603检测到存在下一个外 表，则连接单元601还用于连接更新后的哈希表和检测单元603检测到的下一 个外表。本发明实施例中，无论有多少个要进行连接的表，一个连接过程和 下一个连接过程之间传递的是哈希表，即从第一个连接开始到最后一个连接 结束，整个过程中只有一个不断更新的哈希表，这提高了数据库的查询性能。

请参阅图7，图7是本发明实施例公开的另一种哈希连接算子间数据传递 的装置的结构示意图。如图7所示，该装置700可以包括生成单元701、连接单 元702、更新单元703以及检测单元704，其中：

生成单元701用于生成哈希表。

本发明实施例中，哈希表可以由内表中的每条元组根据某个哈希函数和 某种冲突解决方法构建而成，生成哈希表的方法可以包括直接定址法、数字 分析法、平方取中法、折叠法、除留余数法以及随机数法等，本发明实施例 不做限定。

举例来说，生成哈希表的过程可以如图3所示。

连接单元702用于连接外表和预先生成的哈希表。

作为一种可选的实施方式，连接单元702可以包括获取子单元7021、探测 子单元7022、连接子单元7023以及插入子单元7024，其中：

获取子单元7021用于获取外表中的任意一条元组；

探测子单元7022用于探测哈希表中是否存在能够与外表中的任意一条元 组进行等值连接的元组；

连接子单元7023用于在探测子单元7022探测出哈希表中存在能够与外表 中的任意一条元组进行等值连接的元组时，将哈希表中的元组与外表中的任 意一条元组连接并生成连接元组，其中，连接元组包括用于识别连接元组的 标识信息；

插入子单元7024用于将连接元组插入哈希表。

本发明实施例中，区分哈希表中的连接元组与一般元组的标识信息可以 是元组中属性的个数，也可以是为连接元组添加的一个flag属性（若哈希表要 与多个外表进行连接，则每连接一次就更新flag的值），本发明实施例不做限 定。

更新单元703用于根据外表更新哈希表，获得更新后的哈希表。

作为一种可选的实施方式，更新单元703可以包括判断子单元7031以及删 除子单元7032，其中：

判断子单元7031用于判断外表中是否还存在未探测哈希表的元组；

删除子单元7032用于在判断子单元7031判断出外表中不存在未探测哈希 表的元组时，删除哈希表中不包括标识信息的元组。

本发明实施例中，当外表中还存在未探测哈希表的元组时，则继续取外 表中的元组探测哈希表；当外表中的元组全部探测了哈希表之后，就更新哈 希表，即删除哈希表中的非连接元组。

举例来说，更新后的哈希表可以如图5所示。

检测单元704用于检测是否存在下一个外表。

连接单元702还用于在检测单元704检测到存在下一个外表时，连接下一 个外表和更新后的哈希表。

作为一种可选的实施方式，若检测单元704检测出不存在下一个外表时， 如图7所示，该装置700还可以包括输出单元705，其中：

输出单元705用于在检测单元704检测出不存在下一个外表时，输出更新 后的哈希表。

实施本发明实施例具有如下有益效果：本发明实施例中，无论有多少个 要进行连接的表，一个连接过程和下一个连接过程之间传递的是哈希表，即 从第一个连接开始到最后一个连接结束，整个过程中只有一个不断更新的哈 希表，这提高了数据库的查询性能。

请参阅图8，图8是本发明实施例公开的又一种哈希连接算子间数据传递 的装置的结构示意图。如图8所示，该装置800包括：输入装置801、输出装置 802、存储器803和处理器804，其中，存储器803存储一组程序代码，且处理 器804用于调用存储器803中存储的程序代码，用于执行以下操作：

连接外表和预先生成的哈希表；

根据外表更新哈希表，获得更新后的哈希表；

检测是否存在下一个外表；

若检测到存在下一个外表，则连接下一个外表和更新后的哈希表。

在一个实施例中，处理器804用于调用存储器803中存储的程序代码，还 用于执行以下操作：

生成哈希表。

在一个实施例中，处理器804连接外表和预先生成的哈希表可以包括：

获取外表中的任意一条元组；

探测哈希表中是否存在能够与外表中的任意一条元组进行等值连接的元 组；

若探测出哈希表中存在能够与外表中的任意一条元组进行等值连接的元 组，则将哈希表中的元组与外表中的任意一条元组连接并生成连接元组，其 中，连接元组包括用于识别连接元组的标识信息；

将连接元组插入哈希表。

在一个实施例中，处理器804根据外表更新哈希表，获得更新后的哈希表 可以包括：

判断外表中是否还存在未探测哈希表的元组；

若判断出外表中不存在未探测哈希表的元组，则删除哈希表中不包括标 识信息的元组。

在一个实施例中，若处理器804检测出不存在下一个外表，则处理器804 用于调用存储器803中存储的程序代码，还用于执行以下操作：

输出更新后的哈希表。

本发明实施例具有如下有益效果：本发明实施例中，处理器803在执行多 个表连接时，一个连接过程和下一个连接过程之间传递的是哈希表，即从第 一个连接开始到最后一个连接结束，整个过程中只有一个不断更新的哈希表， 这提高了数据库的查询性能。

需要说明的是，在上述实施例中，对各个实施例的描述都各有侧重，某 个实施例中没有详细描述的部分，可以参见其它实施例的相关描述。其次， 本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例， 所涉及的动作、单元以及子单元并不一定是本发明所必须的。

本发明实施例方法中的步骤可以根据实际需要进行顺序调整、合并和删 减。

本发明实施例装置中的单元或子单元可以根据实际需要进行合并、划分 和删减。

本发明实施例中的单元或子单元，可以通过通用集成电路，例如CPU （Central Processing Unit，中央处理器），或通过ASIC（Application Specific  Integrated Circuit，专用集成电路）来实现。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流 程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于 计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例 的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体（Read-Only  Memory，ROM）或随机存储记忆体（Random Access Memory，RAM）等。

以上对本发明实施例所提供的一种哈希连接算子间数据传递的方法及装 置进行了详细介绍，本文中应用了具体实例对本发明的原理及实施方式进行 了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想； 同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及 应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明 的限制。