(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210825987.5 (22)申请日 2022.07.13 (71)申请人 阿里云计算有限公司 地址 310024 浙江省杭州市西湖区转塘科 技经济区块12号 (72)发明人 吴宇昊　李飞飞　魏闯先　 (74)专利代理 机构 北京同钧律师事务所 16 037 专利代理师 柴海平　许怀远 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) (54)发明名称 哈希连接方法、 计算节点、 存储介质及程序 产品 (57)摘要 本申请提供一种哈希连接方法、 计算节点、 存储介质及程序产品， 该哈希连接方法包括： 基 于第一哈希函数， 对第一数据表进行哈希运算， 得到哈希表； 基于所述哈希表， 生成布隆过滤器； 根据所述布隆过滤器对第二数据表进行过滤； 对 所述哈希表以及过滤后的第二数据表进行哈希 连接， 得到并输出哈希连接表。 实现了在哈希连 接之前， 通过动态生成的布隆过滤器对数据表进 行过滤， 从而减少了数据表的数据量， 进而减少 了所需传输以及探测的数据量， 提高了哈希连接 的效率， 降低了哈希连接的成本 。 权利要求书2页 说明书14页 附图4页 CN 115062027 A 2022.09.16 CN 115062027 A 1.一种哈希连接方法， 其特 征在于， 包括： 基于第一哈希函数， 对第一数据表进行哈希运 算， 得到哈希 表； 基于所述哈希 表， 生成布隆过 滤器； 根据所述布隆过 滤器对第二数据表进行 过滤； 对所述哈希 表以及过 滤后的第二数据表进行哈希连接， 得到并输出哈希连接表。 2.根据权利要求1所述的方法， 其特 征在于， 基于所述哈希 表， 生成布隆过 滤器， 包括： 根据计算节点对应的哈希 表， 生成所述计算节点对应的子布隆过 滤器； 获取各个其他计算节点对应的子布隆过 滤器； 根据各个所述计算节点对应的子布隆过 滤器， 生成所述布隆过 滤器。 3.根据权利要求1所述的方法， 其特 征在于， 基于所述哈希 表， 生成布隆过 滤器， 包括： 根据计算节点对应的哈希 表， 生成所述计算节点对应的子布隆过 滤器； 获取各个其他计算节点对应的子布隆过 滤器的置位信息； 根据所述置位信息以及所述计算节点对应的子布隆过 滤器， 生成所述布隆过 滤器； 其中， 置位信息用于描述对应的子布隆过 滤器被置位的比特位。 4.根据权利要求2或3所述的方法， 其特征在于， 在根据所述计算节点对应的哈希表， 生 成所述计算节点对应的子布隆过 滤器之后， 所述方法还 包括： 分别计算以第一传输方式和第二传输方式传输 子布隆过 滤器所需的数据量； 根据传输所需的数据量， 从第 一传输方式和第 二传输方式中确定所述子布隆过滤器的 目标传输方式； 基于所述目标传输方式， 广播所述计算节点对应的子布隆过 滤器至其 他计算节点； 其中， 基于第一传输方式广播所述计算节点对应的子布隆过 滤器， 包括： 广播所述计算节点对应的子布隆过 滤器至其 他计算节点； 基于第二传输方式广播所述计算节点对应的子布隆过 滤器， 包括： 广播所述计算节点对应的子布隆过滤器的置位信 息至其他计算节点； 置位信 息用于描 述对应的子布隆过 滤器被置位的位置 。 5.根据权利要求2或3所述的方法， 其特征在于， 根据所述计算节点对应的哈希表， 生成 所述计算节点对应的子布隆过 滤器， 包括： 获取至少一个第二哈希函数； 根据至少一个第二哈希函数， 计算所述第一数据表中各 元组的第二哈希值； 根据第一哈希值以及所述第二哈希值， 构建所述计算节点对应的子布隆过 滤器； 其中， 所述第一哈希值 为所述哈希 表中的哈希值。 6.根据权利要求5所述的方法， 其特 征在于， 所述方法还 包括： 根据所述第一数据表， 确定哈希 代价； 根据所述第二数据表， 确定连接代价； 根据所述哈希代价以及所述连接代价， 确定所述计算节点对应的子布隆过滤器的哈希 函数的个数， 以根据所述哈希函数的个数， 获取对应数量的第二哈希函数。 7.根据权利要求1 ‑3任一项所述的方法， 其特征在于， 根据 所述布隆过滤器对第 二数据 表进行过滤， 包括： 当所述第二数据表与 所述第一数据表的哈希分布不同时， 广播所述布隆过滤器至第 二权　利　要　求　书 1/2 页 2 CN 115062027 A 2数据表对应的进程； 经由所述第 二数据表对应的进程， 根据所述布隆过滤器对扫描的第 二数据表中的元组 进行过滤， 得到过滤后的第二数据表， 并将过滤后的第二数据表发送至第一数据表对应的 进程， 以由第一数据表对应的进程对所述哈希 表以及过 滤后的第二数据表进行哈希连接 。 8.一种计算节点， 包括： 处理器， 以及与所述处 理器通信连接的存 储器； 所述存储器存储计算机执 行指令； 所述处理器执行所述存储器存储的计算机执行指令， 以实现如权利要求1 ‑7任一项所 述的方法。 9.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质中存储有计算机 执行指令， 所述计算机执行指令被处理器执行时用于实现如权利要求1 ‑7任一项所述的方 法。 10.一种计算机程序产品， 其特征在于， 包括计算机程序， 所述计算机程序被处理器执 行时实现权利要求1 ‑7任一项所述的方法。权　利　要　求　书 2/2 页 3 CN 115062027 A 3