知识卡片
分裂预算与低误差合并
反馈按桶归组,按信息量分配分裂预算,选查询边界并修正桶深;太小的桶不继续分。控制总桶数时,优先合并预计误差较低的旧桶,避免刚为热点细化的桶立即被吞回。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 9 处
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
首先,由于桶与桶之间的反馈信息不相关,为了方便,先将 QueryFeedback 用 buildBucketFeedback 拆分了每一个桶的反馈信息,并存放在 BucketFeedback 中。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
接着,使用 getSplitCount 来根据可用的桶的个数和反馈信息的总数来决定分裂的数目。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
对于每一个桶,将可以分裂的桶按照反馈信息数目的比例均分,然后用 splitBucket 来分裂出需要的桶的数目:
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
首先,getBoundaries 会每隔几个点取一个作为边界,得到新的桶。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
然后,对于每一个桶,refineBucketCount 用与新生成的桶重合部分最多的反馈信息更新桶的深度。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
值得注意的是,在分裂的时候,如果一个桶过小,那么这个桶不会被分裂;如果一个分裂后生成的桶过小,那么它也不会被生成。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
在分裂的时候,会记录每一个桶是不是新生成的,这样,对于原先就存在的桶,用 getBucketScore 计算合并的之后产生的误差,令第一个桶占合并后桶的比例为 r,那么令合并后产生的误差为 abs(合并前第一个桶的高度 - r * 两个桶的高度和)/ 合并前第一个桶的高度。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
接着,对每一桶的合并的误差进行排序。
- TiDB 源码阅读系列文章(十四)统计信息(下) · 查看原书依据
最后,按照合并的误差从下到大的顺序,合并需要的桶。
参考来源
- 位置:《TiDB源码阅读系列文章》第14章《TiDB 源码阅读系列文章(十四)统计信息(下)》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十四)统计信息(下).html;阅读段落 32,33,34,35,36,37,39,40,41;均为书中版本)
- 结论依据:原文对分裂预算与低误差合并给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。
- 原始内容:首先,由于桶与桶之间的反馈信息不相关,为了方便,先将 QueryFeedback 用 buildBucketFeedback 拆分了每一个桶的反馈信息,并存放在 BucketFeedback 中。 …… 接着,使用 getSplitCount 来根据可用的桶的个数和反馈信息的总数来决定分裂的数目。 …… 对于每一个桶,将可以分裂的桶按照反馈信息数目的比例均分,然后用 splitBucket 来分裂出需要的桶的数目: …… 首先,getBoundaries 会每隔几个点取一个作为边界,得到新的桶。 …… 然后,对于每一个桶,refineBucketCount 用与新生成的桶重合部分最多的反馈信息更新桶的深度。 …… 值得注意的是,在分裂的时候,如果一个桶过小,那么这个桶不会被分裂;如果一个分裂后生成的桶过小,那么它也不会被生成。 …… 在分裂的时候,会记录每一个桶是不是新生成的,这样,对于原先就存在的桶,用 getBucketScore 计算合并的之后产生的误差,令第一个桶占合并后桶的比例为 r,那么令合并后产生的误差为 abs(合并前第一个桶的高度 - r * 两个桶的高度和)/ 合并前第一个桶的高度。 …… 接着,对每一桶的合并的误差进行排序。 …… 最后,按照合并的误差从下到大的顺序,合并需要的桶。