(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211170038.4 (22)申请日 2022.09.22 (71)申请人 宁夏大学 地址 750000 宁夏回族自治区银川市贺兰 山西路489号 (72)发明人 高锦涛　郑洁　姜璐璐　李弋杰　 王浩　莫先　 (74)专利代理 机构 宁夏三源鑫知识产权代理事 务所(普通 合伙) 6410 5 专利代理师 杨畅 (51)Int.Cl. G06F 16/242(2019.01) G06F 16/2455(2019.01) G06F 16/2457(2019.01) (54)发明名称 基于数据剪枝提升等值连接查询性能的方 法、 装置及设备 (57)摘要 本发明提供基于数据剪枝提升等值连接查 询性能的方法、 装置及设备， 属于数据库查询技 术领域。 方法包括： 步骤S1， 获取多路等值连接查 询操作所涉及的所有表、 以及各个所述表之间的 连接关系， 所述连接关系包括对应 关系和连接属 性； 步骤S2， 根据所有所述表、 以及所述对应连接 属性， 生成N个独立的传递闭包； 步骤S3， 令所述 传递闭包作为具有M个剪枝元素PE的剪枝单元 PU， 对所述传递闭包实施两段剪枝操作， 得到两 段剪枝后的传递闭包； 步骤S4， 基于所有所述两 段剪枝后的传递闭包执行所述多路等值连接查 询操作。 权利要求书2页 说明书9页 附图2页 CN 115470231 A 2022.12.13 CN 115470231 A 1.一种基于数据剪枝提升等 值连接查询性能的方法， 其特 征在于， 包括： 步骤S1， 获取多路等值连接查询操作所涉及的所有表、 以及各个所述表之间的对应连 接属性， 所述对应连接属性 通过解析器从输入的SQ L语句中获得； 步骤S2， 根据所有所述表、 以及所述对应连接属性， 生成N个 独立的传递闭包； 步骤S3， 令所述传递闭包作 为具有M个剪枝元素PE的剪枝单元PU， 对所述传递闭包实施 两段剪枝操作， 得到 两段剪枝后的传递闭包； 步骤S4， 基于所有所述两段剪枝后的传递闭包执行所述多路等值连接查询操作， 得出 查询结果。 2.如权利要求1所述的基于数据剪枝提升等值连接查询性 能的方法， 其特征在于， 所述 步骤S2根据所有所述表、 以及所述对应连接属性， 生成N个 独立的传递闭包 包括： 步骤S21， 对SQL语句进行语法解析， 得到所述SQL语句的语法树， 并对所述语法树进行 逻辑优化； 步骤S22， 深度优先遍历优化后的所述语法树， 从中提取出具有等值连接关系的表构成 的路径， 每一个所述路径作为 一个独立的传递闭包PU。 3.如权利要求2所述的基于数据剪枝提升等值连接查询性 能的方法， 其特征在于， 所述 步骤S3对所述传递闭包实施两段剪枝操作， 得到 两段剪枝后的传递闭包 包括： 步骤S31， 对所述传递闭包PU实施一段剪枝α ‑align， 根据区间对齐策略， 将所述PU中每 一个剪枝元素PE对齐， 得到{PU}1， 其中， 所述传 递闭包PU中的所述PE由表名和列名构成， PE ＝{r|r＝[x,y]}； 步骤S32， 所述对齐结果不为空时， 计算出所述{PU }1的空洞范 围HR， 根据所述空洞范 围 去除各个所述剪枝元 素PE中不存在的数据范围， 以使所述{PU}1离散化， 得到{PU}2； 步骤S33， 对所述{PU}2实施二段剪枝β ‑align， 构造出所述{PU}2的公共范围， 并基于所 述公共范围对 齐所述{PU}2中的每一个剪枝元素PE中的元素， 直至达到稳态得到{PU}3， 所述 稳态代表每一个所述PE中的元 素均实现所有数据范围对齐； 步骤S34， 所述{PU}3为所述两段剪枝后的传递闭包。 4.如权利要求3所述的基于数据剪枝提升等值连接查询性 能的方法， 其特征在于， 所述 步骤S32求 解出所述{PU}1的空洞范围HR包括： 步骤S321， 计算出用于限制所述空洞范围中元 素数目的上届O： O＝B+A*U/N 其中， B表示基本阈值， A表示默认值， U/N是扩展 因子， U表示所述表里第i列中值的总个 数， N表示第i列的基数； 步骤S322， 求解出所述表里第i列中数据范围跨度不低于预设值α 的所有候选空洞范 围； 步骤S323， 将各个所述候选空洞范围按照跨度进行降序排序， 选取前β ％的候选空洞范 围组成所述表里第i列对应的空洞范围， 所述空洞范围HR包括所述{PU}1中各所述表各列的 空洞范围。 5.如权利要求4所述的基于数据剪枝提升等值连接查询性 能的方法， 其特征在于， 所述 步骤S33对所述{PU}2实施二段剪枝包括： 步骤S331， 提取所述{P U}2中每一个 所述PE的最小数据范围上届构建成集合D， 提取出每权　利　要　求　书 1/2 页 2 CN 115470231 A 2一个所述PE的最大 数据范围下届构建成集 合U； 步骤S332， 对所述集合D降序排序形成降序序列， 对所述集合U升序排序形成升序序列， 取所述降序 序列的首个元 素和所述升序 序列的首个元 素构建出 所述公共范围； 步骤S333， 利用所述公共范围对每一个所述PE中的元 素实施一轮对齐； 步骤S334， 若对齐操作结束后未 能达到稳态， 则返回执行步骤S332， 选取降序序列的下 一个元素和升序序列的下一个元素构建出新的公共 范围， 利用新的公共范围对每一个P E中 的元素实施下一轮对齐， 直至 达到稳态。 6.如权利要求5所述的基于数据剪枝提升等值连接查询性 能的方法， 其特征在于， 所述 步骤S4基于所有所述两段剪枝后的传递闭包执 行所述多路等 值连接查询操作包括： 步骤S41， 将所述两段剪枝后的传递闭包中所有所述PE里包含的数据范围打散， 按照剪 枝度进行降序排序， 所述剪枝度P D(r)的表达式为： 其中， (r)为数据范围， ζ为求解数据范围(r)的基数的函数， ( ζ(r))表示剪枝前基数， ( ζ (r°))表示剪枝后基数； 步骤S42， 根据各个所述数据范围的所述剪枝度PD(r)求解所述数据范围的实施位置， 所述实施位置包括逻辑计划LT的实施位置和物理计划PT实施位置： 步骤S43， 在所述实时位置实施所述逻辑计划LT和所述物理计划PT； 步骤S44， 执行所述多路等 值连接查询操作。 7.一种等 值连接查询装置， 其特 征在于， 包括： 获取模块21， 用于获取多路等值连接查询操作所涉及的所有表、 以及各个所述表之间 的对应连接属性， 所述对应连接属性 通过解析器从输入的SQ L语句中获得； 传递闭包生成模块22， 用于根据所有所述表、 以及所述对应连接属性， 生成N个独立的 传递闭包； 剪枝模块23， 令所述传递闭包作 为具有M个剪枝元素PE的剪枝单元PU， 对所述传递闭包 实施两段剪枝操作， 得到 两段剪枝后的传递闭包； 查询模块24， 基于所有所述两段剪枝后的传递闭包执行多路等值连接查询操作， 得出 查询结果。 8.一种电子设备， 其特征在于， 包括： 一个或多个处理器和存储器， 所述存储器用于存 储一个或多个程序， 其中， 当所述一个或多个程序被所述一个或多个处理器执行时， 使得所 述一个或多个处 理器实现权利要求1～6中任一项所述的方法。 9.一种计算机可读存储介质， 其特征在于， 其上存储有可执行指令， 该指令被处理器执 行时使处 理器实现权利要求1～6中任一项所述的方法。 10.一种计算机程序产品， 其特征在于， 所述计算机程序产品包括计算机程序， 所述计 算机程序被处 理器执行时用于实现权利要求1～6中任一项所述的方法。权　利　要　求　书 2/2 页 3 CN 115470231 A 3