CN202210137615.3_基于连接简图的数据库连接基数估计方法和系统_GoldenDB.pdf
免费下载
(19)国家知识产权局
(12)发明专利申请
(10)申请公布号
(43)申请公布日
(21)申请号 202210137615.3
(22)申请日 2022.02 .15
(71)申请人 北京大学
地址 100871 北京市海淀区颐和园路5号北
京大学
申请人 中兴通讯股份有限公司
(72)发明人 杨仝 王飞宇 屠要峰 杨洪章
(74)专利代理机构 北京君尚知识产权代理有限
公司 11200
专利代理师 邱晓锋
(51)Int.Cl.
G06F
16/2453
(2019 .01)
G06F
16/25
(2019 .01)
(54)发明名称
基于连接简图的数据库连接基数估计方法
和系统
(57)摘要
本发明涉及一种基于连接简图的数据库连
接基数估计方法和系统。该方法的步骤包括：利
用元素过滤器，将数据库表中的元素分为热元素
与冷元素；将热元素存储至热元素表中，将冷元
素存储至冷元素Sketch中；分别计算两个数据库
表的热元素表的连接基数、冷元素Sketch的连接
基数以及热元素表和冷元素Sketch的连接基数，
并相加，得到对该两个数据库表的连接基数的估
计结果。本发明通过将热元素和冷元素分离，可
以提高对数据库连接基数估计的精度，且算法的
时间和空间开销都有所下降；精确的连接基数估
计，有利于数据库管理系统给出最佳的连接顺
序，从而提升数据库复杂查询的性能。
权利要求书2页 说明书5页 附图1页
CN 114625760 A
2022.06.14
CN 114625760 A
1 .一种基于连接简图的数据库连接基数估计方法，其特征在于，包括以下步骤：
利用元素过滤器，将数据库表中的元素分为热元素与冷元素；
将热元素存储至热元素表中，将冷元素存储至冷元素Sketch中；
分别计算两个数据库表的热元素表的连接基数、冷元素Sketch的连接基数以及热元素
表和冷元素Sketch的连接基数，并相加，得到对该两个数据库表的连接基数的估计结果。
2.根据权利要求1所述的方法，其特征在于，所述热元素表用来存储热元素，其每一个
表项由元素指纹和计数器两部分组成，元素指纹是元素的一个哈希值，计数器记录热元素
出现的频数。
3 .根据权利要求1所述的方法，其特征在于，所述元素过滤器包括若干个桶，每个桶包
括若干个记录，每条记录由元素指纹和计数器两部分组成，元素指纹是元素的一个哈希值，
计数器记录元素出现的频数。
4 .根据权利要求1所述的方法，其特征在于，所述冷元素Sketch是CM Sketch，由若干个
计数器组成，并且有d个相互独立的哈希函数，哈希函数的作用是将一个元素随机映射到CM
Sketch的一个计数器内。
5 .根据权利要求1所述的方法，其特征在于，将数据库表的一个元素插入到热元素表和
冷元素Sketch中时，该元素首先被插入到元素过滤器中，元素过滤器计算该元素的哈希值，
然后将其映射到一个桶中，根据该桶中是否包含该元素有四种不同的处理情况：
如果该桶中包含这个元素，那么将该元素的计数器加1；
如果该桶不包含这个元素且有空的记录，则将该元素插入到空记录所在位置；
如果该桶不包含这个元素且桶是满的，则判断桶中频数最大的元素的频数是否超过阈
值T，如果超过，则认为这个最大的元素是热元素，把热元素插入到热元素表中，然后将待插
入的元素插入到热元素原来的位置；
如果该桶不包含这个元素且桶是满的，且桶中最大的元素数量不大于T，则通过某种选
择方式选择桶中的一个元素，将该元素视为冷元素，插入到冷元素Sketch中，然后将待插入
的元素插入到冷元素原来的位置。
6 .根据权利要求5所述的方法，其特征在于，所述选择桶中的一个元素，采用的选择方
式为下列中的一种：随机选择、依概率选择、选择频数最小元素。
7 .根据权利要求1所述的方法，其特征在于，所述计算不同数据库表的热元素表和冷元
素Sketch的连接基数，包括：
对于热元素表，将数据库表1和数据库表2的热元素表比较，如果指纹相同则认为是同
一个元素，对应的计数器相乘并对所有的乘积求和；
对于冷元素Sketch，将数据库表1和数据库表2的冷元素Sketch对应位置的计数器的值
相乘并求和；
对于数据库表1的热元素表中的每一个元素，在数据库表2中的冷元素Sketch中查询频
数的估计值；对于数据库表2的热元素表中的每一个元素，在数据库表1中的冷元素Sketch
中查询频数的估计值。
8.一种采用权利要求1～7中任一权利要求所述方法的基于连接简图的数据库连接基
数估计系统，其特征在于，包括：
元素过滤模块，用于利用元素过滤器，将数据库表中的元素分为热元素与冷元素；
权 利 要 求 书
1/2 页
2
CN 114625760 A
2
of 9
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论