oracle ndv,算法分析：Oracle 11g 中基于哈希算法对唯一值数(NDV)的估算

分手后的思念是犯贱 2023-01-18 06:59 62阅读 0赞

原标题：算法分析：Oracle 11g 中基于哈希算法对唯一值数(NDV)的估算

作者简介

![25397b4e83672fe697e27bc9fd234f9b.png][]

黄玮(Fuyuncat)

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

个人网站www.HelloDBA.com

1

为什么引入新 NDV 算法

字段的统计数据是 CBO 优化器估算执行计划代价的重要依据。而字段的统计数据可以分为两类：

1. 概要统计数据：如 NDV 字段平均长度 ACL 最大、最小值等

2. 柱状图数据：也叫直方图(histograms)记录 NDV 和它们出现的频率

NDV 也叫做唯一值数，是对表的字段唯一值个数的统计，对于第一类数据，实际上可以通过一次扫描表获取所有字段的统计数据。

但是，对于大型表的分析，为减少资源消耗，需要通过采样分析。由于采样具有随机性，对于一些数据分布不均匀的字段，通过采样数据获取统计数据可能会导致获取到的数据与实际数据产生较大差异。

尤其对于一些海量数据表，通常采样比较低，因而每次分析对象获取到的数据的精度会存在较大的不确定性。这种不确定性可能会对系统的整体性能造成重大影响。

举个例子

一个字段的里面的数据如下：

\[0,1,1,1...(100\*1)...1,2,3,4,5,6,7,8,9\]

其实际的 NDV 是10，通过采样(假设采样比为10%)获取 NDV 时，由于采样的随机性，可能就会出现以下情况：

\[1...(10\*1)...,2,6\]

得到的 NDV 是3，和实际值存在很大的出入(如果除以采样比的话，NDV 为3/10×100=30)。而如果优化器采样了这样数据进行执行计划代价估算的话，就很有可能获取不到最优的执行计划。

而降低这种不确定性的手段就是提高采样比例。但是，对于大型表来说，提高采样比又会带来更多的资源消耗，尤其是获取 NDV 数值时。

由于获取 NDV 数值需要消除重复值(通过 count (distinct col) 方式获取)，Oracle 是通过排序的方法将已经读取的唯一值保持在 PGA 当中，以便消除后续的重复值。因此，当取样比增加时，PGA 的消耗也会线性增加。

对于大型表，PGA 可能不足以容纳全部数据，从而会导致临时磁盘空间的读写，导致重大的性能问题。

2

新 NDV 算法介绍

在11g中，采用了一种新的算法消除 NDV 计算时，数据量与 PGA 消耗之间的线性关系，从而使得通过完全扫描表获得精确统计数据成为可能。因此，在 11g，自动采样模式下不再进行快速取样，而是直接进行全表扫描获取统计数据。这一新算法称为唯一值数估计(Approximate NDV)。

默认情况下，在进行自动采样时，也就是 AUTO \_SAMPLE\_SIZE 时，就采样该算法。

这个新特性也可以通过隐含参数 "APPROXIMATE \_NDV" 来关闭。

SQL 代码：

HELLODBA.COM>exec dbms\_stats.set\_param('APPROXIMATE\_NDV','FALSE');

PL/SQL procedure successfully completed.

注意：11g 中，对分区表全局统计数据的增量(INCREMENTAL)计算方式，也是利用了该算法。

3

新NDV算法过程

该算法充分利用了哈希算法的分布均衡特性。其基本算法过程如下：

它将每个扫描到的数值通过哈希算法转换为一个二进制数值，并放入一个数据结构中，我们称该数据结构为一个纲要(synopsis)；

扫描下一个数值，获取到其哈希二进制数值，将其与纲要中已有哈希值比较，如果已经存在相同值，则丢弃该值，否则就插入纲要中；

纲要是有大小限制的，当新插入哈希值时，纲要已经达到大小限制，则按照一定规则分裂该纲要、并丢弃其中一份数据(例如，将首位为0的数值丢弃掉)，此时，纲要级别也相应增加(起始为0，分裂一次加1)；

获取到新的哈希数值时，如果其符合被丢弃数据的规则，则不再插入纲要中；

再次分裂时，按照递进的规则(如将前2为都为0的数值分裂)丢弃数据，并以此类推，直到扫描完所有数据；

我们称纲要中最终剩下数值数成为集数 (S) ，纲要分裂次数称为级数 (I)

而 NDV 的估算公式是：NDV = S\*2^I

在这种算法下，由于每个字段在 PGA 中仅保存一个纲要数据结构，因此，它不会随着读取的数据量的增加而导致 PGA 消耗的增加。返回搜狐，查看更多

责任编辑：

[25397b4e83672fe697e27bc9fd234f9b.png]: /images/20221021/89b0711b0ce5453c826b828e1fbf6274.png

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关 Oracle 11g 哈希、LIST分区测试

哈希分区中，如果分区字段的值是相同的，相同值的条目都会存放在相同的分区中； LIST分区则易于管理，而对于哈希分区，则不好控制各个值所存放的分区，有的分区会存放两个或...

淡淡的烟草味﹌/ 2024年04月18日 00:08/ 0 赞/ 69 阅读

相关简单哈希算法和一致性哈希算法和哈希槽对比

目录简单哈希算法一致性哈希算法哈希槽简单哈希算法 > 假设有三台机，数据落在哪台机的算法为： > c = Ha

落日映苍穹つ/ 2024年03月27日 14:00/ 0 赞/ 102 阅读

相关哈希算法

include<bits/stdc++.h> using namespace std; const int MAXN=1000001; int

不念不忘少年蓝@/ 2023年03月04日 03:22/ 0 赞/ 8 阅读

相关 oracle ndv,算法分析：Oracle 11g 中基于哈希算法对唯一值数(NDV)的估算

原标题：算法分析：Oracle 11g 中基于哈希算法对唯一值数(NDV)的估算作者简介 ![25397b4e83672fe697e27bc9fd234f9b.png][

分手后的思念是犯贱/ 2023年01月18日 06:59/ 0 赞/ 63 阅读

相关一致性哈希算法的原理分析

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 一致性哈希算法的原理分析环形Hash空间按照

朱雀/ 2022年10月02日 07:44/ 0 赞/ 144 阅读

相关 Oracle 11g索引的碎片分析

数据被删除之后，索引只是加了一个标记，并没有真正的删除，在11g之后，删除的索引在数据块中，下次插入数据或者删除数据时候会以数据块为单位清除。这样可以查看碎片率。 dro

爱被打了一巴掌/ 2022年07月12日 02:09/ 0 赞/ 315 阅读

相关算法一致性哈希算法

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正

亦凉/ 2022年06月07日 01:40/ 0 赞/ 304 阅读

相关算法之哈希算法

哈希算法定义将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法。哈希算法实现的要求从哈希出来的值不能反向推导出原始数据。也就

我不是女神ヾ/ 2022年04月17日 04:38/ 0 赞/ 216 阅读

相关哈希算法

对于哈希算法，在我们平时的开发中，都是基本上拿来就用就行了，所以这节我们将重点放在如何使用，并不进行哈希算法的原理剖析和如何设计一个哈希算法的讲解．什么是哈希算法？

我就是我/ 2022年03月25日 13:50/ 0 赞/ 258 阅读

相关一致性哈希算法

场景如下: 有三台缓存服务器分别为A、B、C,编号依次为1、2、3，现在有N张名称不重复的图片平均分配到每台服务器上进行缓存，如何设计一套算法，使得每次图片请求都能

快来打我*/ 2021年06月10日 20:40/ 0 赞/ 587 阅读