深入内核丨12C 新特性之 TOP - N 频率柱状图原理和算法

作者简介

黄玮(Fuyuncat)

资深 Oracle DBA,致力于数据库底层技术的研究,其作品获得广大同行的高度评价。

个人网站 www.HelloDBA.com

在 Oracle 12c 当中,优化器的一个新特性就是提供了新类型的柱状图数据,Top - N 频率柱状图和混合柱状图。优化器利用它们可以更加高效、精确地计算执行计划代价,选择最优计划。这里将探究一下 Top - N 频率柱状图在什么情况下获得、以及它如何影响优化器的选择率的计算。 12c 在线文档描述: Top - N 频率柱状图是频率柱状图的一个变种,它忽略了那些"非流行数据"(即出现频率低的数值)。例如,1000枚硬币中只有一枚面值1分的硬币,那在创建柱状图分组时,它就可以被忽略。Top - N 频率柱状图能产生一个更利于"流行数据"(高频率数据)的柱状图。

如何产生 Top - N 频率柱状图

首先需要了解的一个事实是,在收集统计信息数据时,如果为估算值设置了一个非默认值,则统计数据过程就类似于11G,即不会产生新类型的柱状图。因此,产生 Top - N 频率柱状图的一个必要条件就是让估算比为默认值。

例如:

从在线文档对 Top - N 频率柱状图的描述可知,Top - N 频率柱状图分组数量一定小于唯一值数量(Distinct Value Number)。所以,产生 Top - N 频率柱状图的另外一个必要条件是设置的分组数或者默认分组数设置(默认254)小于其唯一值数。

在进一步为字段收集统计数据之前,统计数据收集过程首先会计算近似唯一值数。这一步骤会调用 SQL 分析器(SQL Analyzer)来分析当前输入参数所产生的一条 SQL 语句。例如如下语句:

SQL 分析器不光会获得这条查询语句的结果,还会根据输入选项(如TOPN, NIL, NIL, ACL, RWID, U25, UU)在执行和分析过程中调用内部函数获取更多的额外信息。其中就有 TOP - N 数值信息。然而,如果 TOP - N 数值的数据总数在该字段的非空值数据总数中的比例低于一个阈值(1-1/MNB,MNB 为最大分组数,Maximum Number of Buckets,它是影响选择频率柱状图还是高平衡柱状图的重要因素,参见http://www.hellodba.com/reader.php?ID=19&lang=EN)时,TOP - N 数据会被丢弃,也就是说,不会产生Top - N频率柱状图。因而,TOP - N 数值的数据总数在该字段的非空值数据总数中的比例大于(1-1/MNB)也成为产生 Top-N 频率柱状图的一个必要条件。

而字段的最大、最小唯一值必须包含在柱状图数据当中,因此统计过程还需要检查是否需要从现有 Top - N 数据中移除数据以容纳最大、最小值:如果最大、最小值已经在 Top - N 数据当中,则不需要移除,否则将数据量最小的数值移除以腾出位置给最大最小值。相应的,要根据调整后的 Top - N 数据记录总数在非空数值记录总数中的比例再与阈值比较以决定是否采纳 Top - N 频率柱状图。 概括产生 Top - N 频率柱状图的条件: 1. 估算比为默认值; 2. 柱状图分组数小于唯一值数; 3.(调整后的 Top - N 数据记录总数)/(非空数值记录总数)>(1-(1/MNB))

演示

以下用一个例子来演示 Top-N 频率柱状图的产生。

可以看到,尽管设置了分组数小于唯一值(30)的25,并采用了默认估算值,统计收集过程最终还是未给该字段收集 Top - N 频率柱状图。检查 Top - N 数据记录总数在非空数值记录总数中的比例以及阈值。

最初计算的 Top - N 数据记录总数在非空数值记录总数中的比例是大于阈值的。再看 Top - N 数据记录总数是否会被调整:

。。。。。。

最小值(1)并没有在最初的 Top - N 数值当中,它要替换 Top - N 数值当中的数据量(60)最少的数(6)。调整后计算得到的百分比为:

因此可以看到该值小于阈值(96),所以不会产生 Top - N 频率柱状图。

基于 Top - N 频率柱状图的选择率计算

基于 Top - N 频率柱状图的选择率计算并不复杂。

1. 如果判定谓词中数据位于柱状图当中,则采用柱状图数据计算选择率; 2. 如果判定谓词中数据不位于柱状图当中,则由柱状图以外的唯一值数及其数据数量来计算选择率。

举例说明:

。。。。。。

注意:因为最小值(1)没有被包含在最初分析的 Top-N 值当中,它替换了里面数据量最少的唯一值(5),并且数据量设置为1。

唯一值20的分组数据量为 200 (1951-1751),计算所得选择率为 200/取样大小 = 200 / 4650,因此,过滤后的数据记录数为 cardinality*selectivity = 200。

"2" 不是一个 Top - N 数值,这一谓词表达式的选择率为该字段的密度(Density)。然而,对于 Top - N 频率柱状图字段,优化器会根据非 Top - N 数值数据重新计算密度。本例当中,新的密度为(非空值总数 - Top - N 数值总数)/(非 Top-N 数值总数)/(非空值总数)= (4650-4501)/(30-26)/4650 = 0.008010753。因此,过滤后的数据记录为 cardinality*selectivity=trunc (4650*.008010753) = 37。

TIPS:新计算所得密度可以通过 10053 事件跟踪观察到。

注:

测试环境为:ORACLE 12.2.0.1 ON WIN10

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2018-03-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

策略模式

一、策略模式的相关介绍 1、定义:策略模式定义了一系列的算法,并将每一个算法封装起来,而且使它们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化。 2...

1788
来自专栏数据结构与算法

Kruskal重构树入门

在运行Kruskal算法的过程中,对于两个可以合并的节点$(x, y)$,断开其中的连边,并新建一个节点$T$,把$T$向$(x, y)$连边作为他们的父亲,同...

1115
来自专栏落影的专栏

程序员进阶之算法练习(二十六)

前言 金三银四,求职黄金月做算法面试题,热热身子。 正文 1.Chess For Three 题目链接 题目大意: 有三个人A,B,C玩剪刀石头布的游戏,但...

4616
来自专栏数据科学与人工智能

【数据挖掘】数据挖掘 特异群组挖掘的框架与应用

特异群组挖掘在证券金融、医疗保险、智能交通、社会网络和生命科学研究等领域具有重要应用价值。特异群组挖掘与聚类、异常挖掘都属于根据数据对象的相似性来划分数据集的数...

24010
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 行数据构成一个 2 x 1 的列向量。先看对 array 的做法:

831
来自专栏数据结构与算法

洛谷P2763 试题库问题(最大流)

733
来自专栏编程之旅

算法时间复杂度

很多程序员,做了很长时间的编程工作却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事情。因为弄不清楚,所以也就从不深究自己写的代码是否效率底下,是不是可...

671
来自专栏C语言及其他语言

[每日一题]矩阵转置(1242)

题目描述 输入N*N的矩阵,输出它的转置矩阵。 输入 第一行为整数N。 接着是一个N*N的矩阵。 输出 转置矩阵 样例输入 2 1 2 1 2 样例输出 1 ...

3119
来自专栏数据结构与算法

BZOJ4709: [Jsoi2011]柠檬(决策单调性)

那么设\(f[i]\)表示到第\(i\)个位置的最大价值,\(s[i]\)表示到\(i\)位置,\(a[i]\)的出现次数,转移方程为

302
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

3267

扫码关注云+社区