再上一篇:10.4索引组织表
上一篇:10.5索引聚簇表
主页
下一篇:10.7有序散列聚簇表
再下一篇:10.8嵌套表
文章列表

10.6散列聚簇表

Oracle 9i 10g编程艺术:深入数据库体系结构


散列聚簇表(Hash clustered table) 在概念上与前面介绍的索引聚簇表非常相似,只有一个主要 区别:聚簇键索引被一个散列函数所取代。表中的数据就是索引;这里没有物理索引。Oracle会取 得一 行的键值,使用每个内部函数或者你提供的每个函数对其计算散列,然后使用这个散列值得出数据应该在 磁盘上的哪个位置。不过,使用散列算法来定位数据有 一个副作用,如果不向表增加一个传统的索引,将 无法对散列聚簇中的表完成区间扫描。在一个索引聚簇中,如果有以下查询:
select * from emp where deptno between 10 and 20
它就能利用聚簇键索引来找到这些行。在一个散列聚簇中,这个查询会导致一个全表扫描,除非 DEPTNO列上已经有一个索引。如果没有使用一个支持区间扫描的索引,就只能在散列键上完成精确搜索(包 括列表和子查询)。
理 想情况下,散列键值均匀分布,并且有一个散列函数可以将这些散列键值均匀地分布到为散列聚 簇分配的所有块上,从查询利用一个I/O就能直接找到数据。但在 实际中,最后可能会有多个散列键值散 列到同一个数据库块地址,而且这个块上放不下这么多散列键值。这就会导致块串链,Oracle必须用一个 链表把块串起 来,来保存散列到这个块的所有行。现在,当需要获取与某个散列键匹配的行时,可能必须 访问多个块。
类似于编程语言中的散列表,数据库中的散列表有固定的“大小”。创建表时,必须确定这个表中将 有多少个散列键(而且这个数永远不变)。但散列表的大小并不限制其中能放的行数。
图10 -9是一个散列聚簇的图形表示,这里创建了表EMP。客户发出一个查询,其中的谓词条件中使 用了散列聚簇键,Oracle会应用散列函数确定数据应该在哪 个块中。然后读这个块来找到数据。如果存 在许多冲突,或者CREATE CLUSTER的SIZE参数估计过低,Oracle会分配溢出块与原来的块串链起来。

图10-9散列聚簇示意图
创 建散列聚簇时,还是使用创建索引聚簇时所用的同样的CREATE CLUSTER语句,不过选项不同。这 里只是要增加一个HASHKEYS选项来指定散列表的大小。Oracle得到你的HASHKEYS值,将其“舍入” 为 与之最接近的质数(散列键数总是一个质数)。然后Oracle再将SIZE参数乘以修改后的HASHKEYS值,计 算出一个值。再根据这个值为聚簇分配 空间,也就是说,至少要分配这么多字节的空间。这与前面的索引 聚簇有很大差别,索引聚簇会在需要时动态地分配空间,散列聚簇则要预留足够的空间来保
存 (HASHKEYS/trunc(blocksize/SIZE))字节的数据。例如,如果将SIZE设置为1,500 字节,而且块大 小为4KB, Oracle会在每个块上存储两个键。如果你计划有1,000个HASHKEY,Oracle就分配500个块。 有 意思的是,不同于计算机语言中的传统散列表,这里允许有散列冲突,实际上,许多情况下还需 要有冲突。还是用前面的DEPT/EMP例子,可以根据 DEPTNO列建立一个散列聚簇。显然,多个行会散列到
同一个值,这正是你希望的(因为它们有相同的DEPTNO)。这就反映了聚簇某些方面的特点:要把 类似 的数据聚簇在一起。正是由于这个原因,所以Oracle要求你指定HASHKEY(你预计一段时间会有多少个部 门号)和SIZE(与各个部门号相关联 的数据量)。Oracle会分配一个散列表来保存HASHKEY个部门,每 个部门有SIZE字节的数据。你想避免的是无意的散列冲突。显而易见,如果就散 列表的大小设置为1,000
(实际上是1,099,因为散列表的大小总是质数,而且Oracle会为你找出与之最接近的质数),而你在表
中放入了 1,010个部门,就至少会存在一个冲突(两个不同部门散列到同一个值)。无意的散列冲突是要 避免的,因为它们会增加开销,使块串链的可能性增加。
要 查看散列聚簇会用哪种空间,下面就使用一个小工具——存储过程SHOW_SPACE(有关这个过程的 详细介绍,请参见本书最前面的“环境配置”一节),这 一章和下一章都就使用这个小工具。这个例程只 是使用DBMS_SPACE提供的包来得到数据库中段所用存储空间的详细信息。
如果发出以下CREATE CLUSTER语句,可以看到它分配的存储空间如下:

ops$tkyte@ORA10GR1> create cluster hash_cluster
2 ( hash_key number )
3 hashkeys 1000
4 size 8192
5 tablespace mssm
6 /
ster created.
ops$tkyte@ORA10GR1> exec show_space( 'HASH_CLUSTER', user, 'CLUSTER' )

e Blocks.............................

0

al Blocks............................

1,024

al Bytes.............................

8,388,608

al MBytes............................

8

sed Blocks........................... 14

sed Bytes............................

114,688

t Used Ext FileId....................

9

t Used Ext BlockId...................

1,033

t Used Block......................... 114
PL/SQL procedure successfully completed.
可 以看到,为表分配的总块数为1,024。其中14个块未用(空闲)。另外有1个块用于维护表开销 , 以管理区段。因此,有1,099 个块在这个对象的HWM 之下,这些是聚簇使用的块。1,099 是一个质数,而 且正好是大于1000的最小质数,由于块大小为8KB,可以看到,Oracle实际上会分配 (8,192×1,099) 字节。由于区段的”舍入“而且/或者通过使用本地管理的表空间(区段的大小一致),实际分配的空间
(8,388,608)比这 个数稍高一些。
这 个例子指出,关于散列聚簇需要注意以下问题。一般地,如果创建一个空表,该表在HWM下的块 数为0.如果对它执行全表扫描,达到HWM就会停止。对于一个 散列聚簇,表一开始就很大,需要花更长 的时间创建,因为Oracle必须初始化各个块(而对于一般的表,这个动作通常在数据增加到表时才发生)。 散列聚簇 表有可能把数据放在第一个块和最后一个块中,而中间什么都没有。对一个几乎为空的散列聚簇 进行前面扫描与全面扫描一个满的散列聚簇所花的时间是一样的。这 不一定是件坏事:建立散列聚簇的本 来目的是为了根据散列键查找从而非常快地访问数据。而不是为了频繁地对它进行全面扫描。

现在可以开始把表放在散列聚簇中,仍采用前面索引聚簇所用的方法: Ops$tkyte@ORA10GR1> create table hashed_table
2 ( x number, data1 varchar2(4000), data2 varchar2(4000) )

3 cluster hash_cluster(x); Table created.
为 了看出散列聚簇可能有哪些区别,我建立了一个小测试。首先创建一个散列聚簇,在其中加载一 些数据,再将这些数据复制到一个有传统索引的“常规“表中,然后 对各个表完成一些随机读(对每个完 成的随机读是一样的)。通过使用runstats、SQL_TRACE和TKPPOF,可以确定各个表的特征。以下先完 成 散列聚簇和表的建立,其后是分析:

ops$tkyte@ORA10GR1> create cluster hash_cluster
2 ( hash_key number )
3 hashkeys 75000
4 size 150
5 /
Cluster created.
ops$tkyte@ORA10GR1> create table t_hashed
2 cluster hash_cluster(object_id)
3 as
4 select *
5 from all_objects
6 /
Table created.
ops$tkyte@ORA10GR1> alter table t_hashed add constraint
2 t_hashed_pk primary key(object_id)
3 /
Table altered. ops$tkyte@ORA10GR1> begin
2 dbms_stats.gather_table_stats( user, 'T_HASHED', cascade=>true );
3 end;
4 /
PL/SQL procedure successfully completed.
在此创建了一个SIZE为150字节的散列聚簇。这是因为,我认为我的表中一行的平均大小大约是100 字节,但是根据实际数据,具体的行大小可能会上下浮动。然后在这个聚簇中创建并填充一个表,作为 ALL_OBJECTS的一个副本。
接下来,创建这个表的传统版本的“克隆“(即相应的堆组织表):

ops$tkyte@ORA10GR1> create table t_heap
2 as
3 select *

4 from t_hashed
5 /
Table created.
ops$tkyte@ORA10GR1> alter table t_heap add constraint
2 t_heap_pk primary key(object_id)
3 /
Table altered.
ops$tkyte@ORA10GR1> begin
2 dbms_stats.gather_table_stats( user, 'T_HEAP', cascade=>true );
3 end;
4 /
PL/SQL procedure successfully completed.
现 在,我需要一些“随机“的数据,用来从各个表中抽取行。为此,我只是把所有OBJECT_ID选择 到一个数组中,然后随机地排序,从而以一种分散的方式命 中表的各个块。我使用了一个PL/SQL包来定 义和声明这个数组,并使用一些PL/SQL代码来”准备“这个数组,填入随机数据:

ops$tkyte@ORA10GR1> create or replace package state_pkg
2 as
3 type array is table of t_hashed.object_id%type;
4 g_data array;
5 end;
6 /
Package created.
ops$tkyte@ORA10GR1> begin
2 select object_id bulk collect into state_pkg.g_data
3 from t_hashed
4 order by dbms_random.random;
5 end;
6 /
PL/SQL procedure successfully completed. 要看到各个表完成的工作,我使用了以下代码块(如果把这里出现的HASHED都代之以HEAP,就可以
得到另一个要测试的代码块):

ops$tkyte@ORA10GR1> declare
2 l_rec t_hashed%rowtype;
3 begin
4 for i in 1 .. state_pkg.g_data.count
5 loop
6 select * into l_rec from t_hashed

7 where object_id = state_pkg.g_data(i);
8 end loop;
9 end;
10 /
PL/SQL procedure successfully completed.
接 下来,就前面的代码块(以及用HEAP取代HASHED得到的代码块)运行3次。第一次运行是系统 “热身“,以避免以后再完成硬解析。第二次运行这个代码 块时,我使用runstats来查看二者的主要差 别:先运行散列实现,然后运行堆实现。第三次运行代码块时,我启用了 SQL_TRACE,从而能看到一个 TKPPOF 报告。runstats运行的报告如下:

ops$tkyte@ORA10GR1> exec runstats_pkg.rs_stop(10000);
Run1 ran in 263 hsecs
Run2 ran in 268 hsecs
run 1 ran in 98.13% of the time
Name Run1 Ru n2 Diff
LATCH.cache buffers chains 99,891 148,031 48,140
STAT...Cached Commit SCN refer 48,144 0 -48,144
STAT...no work - consistent re 48,176 0 -
48,176
STAT...cluster key scans 48,176 0 -
48,176
STAT...cluster key scan block 48,176 0 -
48,176
STAT...table fetch by rowid 0 48,176 48,
176
STAT...rows fetched via callba 0 48,176 48,176
STAT...buffer is not pinned co 48,176 96,352 48,176
STAT...index fetch by key 0 48,176 48,
176
STAT...session logical reads 48,901 145,239 96,338
STAT...consistent gets 48,178 144,530 96,352
STAT...consistent gets from ca 48,178 144,530 96,352

STAT...consistent gets - exami 1 144,529 144,528
Run1 latches total versus runs -- difference and pct

Run1

Run2

Diff

Pct

347,515

401,961

54,446

86.45%

现 在,从墙上的时钟来看,两个仿真运行的时间是一样的。因为我有一个足够大的缓存区缓存来缓
存这些结果,所以这在预料之中。不过,要注意一个重要差别,缓存 区缓存链的闩大幅减少。第一个实现
(散列实现)使用的闩少得多,这说明在一个读密集型环境中,散列实现应该能更好地扩缩,因为它需要 的串行化资源(这些资 源要求某种程度的串行化)更少。其原因完全在于,与HEAP表相比,散列实现需 要的I/O显著减少,可以看到,报告中的一致获取统计就能反映出这点。 TKPPOF反映得更清楚:

SELECT * FROM T_HASHED WHERE OBJECT_ID = :B1
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
Parse 1 0.00 0.00 0
0 0 0
Execute 48174 4.77 4.83 0 2
0 0
Fetch 48174 1.50 1.46 0 48174 0
48174
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
total 96349 6.27 6.30 0 48176
0 48174
Rows Row Source Operation
------- ---------------------------------------------------
48174 TABLE ACCESS HASH T_HASHED (cr=48174 pr=0 pw=0 time=899962 us)
******************************************************************************** SELECT * FROM T_HEAP WHERE OBJECT_ID = :B1

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
Parse 1 0.00 0.00 0
0 0 0
Execute 48174 5.37 5.02 0 0
0 0
Fetch 48174 1.36 1.32 0 144522
0 48174
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
total 96349 6.73 6.34 0 144522
0 48174
Rows Row Source Operation
------- ---------------------------------------------------
48174 TABLE ACCESS BY INDEX ROWID T_HEAP (cr=144522 pr=0 pw=0 time=1266695 us)
48174 INDEX UNIQUE SCAN T_HEAP_PK (cr=96348 pr=0 pw=0 time=700017 us)(object ... HASHED实 现只是把传递到查询的OBJECT_ID转换为要读取的一个FILE/BLOCK,并且直接读,这里没
有索引。不过,HEAP表则不同,它必须对每一行在 索引上完成两个I/O。TKPROF Row Source Operation 行中的cr=96348清楚地显示了对索引做了多少次一致读。每次查找OBJECT_ID = :B1时,Oracle必须得 到索引的根块,然后找出包含该行位置的叶子块。接下来必须得到叶子块信息,其中包含行的ROWID,再 利用第3个I/O在表 中访问这个行。HEAP表完成的I/O是HASHED实现的3倍。
这里的要点是:
q 散 列聚簇完成的I/O(查询列)少得多。这正是我们期望的。查询只是取随机的 OBJECT_ID, 对其完成散列,然后找到块。散列聚簇至少要做一次I/O来 得到数据。有索引的传统表则必须 完成索引扫描,然后要根据rowid访问表,才能得到同样的答案。在这个例子中,索引表必须 至少完成3 个I/O才能得到数 据。
q 不 论用于什么目的,散列聚簇查询与索引查询所用的CPU是一样的,尽管它访问缓存区 缓存的次数只是后者的1/3。同样,这也在预料之中。执行散列是一个 CPU相当密集的操作, 执行索引查询则是一个I/O密集的操作,这里要做个权衡。不过,随着用户数的增加,可以想 见,散列聚簇查询能更好地扩缩,因为要想 很好地扩缩,就不能太过频繁地访问缓存区缓存。
最 后一点很重要。使用计算机时,我们所关心的就是资源及其利用。如果存在大量I/O,并且像这 里一样,所执行的查询要根据键做大量的读操作,此时散列聚簇就 能提供性能。如果已经占用了大量CPU
时间,再采用散列聚簇反而会降低性能,因为它需要更多的 CPU时间来执行散列。不过,如果耗用更多CPU 时间的原因 是缓冲区缓存的闩存在自旋,那么散列聚簇就能显著减少所需的CPU时间。这就说明了为什么 有些经验在实际系统中不适用;有些经验对于你来说也许很合适,但 是在类似但不同的条件下,这些经验 可能并不可行。
散列聚簇有一个特例,称为单表散列聚簇(single table hash cluster)。 这是前面介绍的一般散 列聚簇的优化版本。它一次只支持聚簇中的一个表(必须DROP(删除)单表散列聚簇中现有的表,才能在 其中创建另一个表)。另外,如 果散列键和数据行之间存在一对一的映射,访问行还会更快一些。这种散 列聚簇是为以下情况设计的:如果你想按主键来访问一个表,但是不关心其他表是否与这个 表聚簇在一起 存储。如果你需要按EMPNO快速地访问员工记录,可能就需要一个单表散列聚簇。我在一个单表散列聚簇 上执行了前面的测试,发现性能比一般的 散列聚簇还要好。不过,甚至还可以将这个例子更进一步,由于 Oracle允许你编写自己的散列函数(而不是使用Oracle提供的默认散列函数),所以能 利用这一点。不 过,你只能使用表中可用的列,而且编写自己的散列函数时只能使用Oracle的内置函数(例如,不能有 PL/SQL代码)。由于上例中 OBJECT_ID是一个介于1~75,000之间的数,充分利用这一点,我建立了自己 的“散列函数”:就是OBJECT_ID本身。采用这种方式,可以 保证绝对不会有散列冲突。综合在一起,我 如下创建一个单表散列聚簇(有我自己的散列函数):
ops$tkyte@ORA10GR1> create cluster hash_cluster
2 ( hash_key number(10) )
3 hashkeys 75000
4 size 150
5 single table
6 hash is HASH_KEY
7 /
Cluster created.

这里只是增加了关键字SINGLE TABLE, 使之作为一个单步散列聚簇。在这种情况下,我的散列函数

就是HASH_KEY聚簇键本身。这是一个SQL函数,所以如果我愿意,也可以使用trunc (mod(hash_key/324+278,555)/abs(hash_key+1))(并不是说这是一个好的散列函数,这只是说明,只要我 们愿意, 完全可以使用一个复杂的函数)。我使用了NUMBER(10)而不是NUMBER,这是因为散列值必须是 一个整数,所以不能有任何小数部分。下面,在这个 表单散列聚簇中创建表:
ops$tkyte@ORA10GR1> create table t_hashed
2 cluster hash_cluster(object_id)
3 as
4 select OWNER, OBJECT_NAME, SUBOBJECT_NAME,
5 cast( OBJECT_ID as number(10) ) object_id,
6 DATA_OBJECT_ID, OBJECT_TYPE, CREATED,
7 LAST_DDL_TIME, TIMESTAMP, STATUS, TEMPORARY,
8 GENERATED, SECONDARY
9 from all_objects
10 /
Table created.
以上建立了散列表。注意这里使用了CAST内置函数将OBJECT_ID强制转换为它本来的数据类型。像 前面一样运行测试(每个代码块运行3 次),这一次runstats的输出表明情况更好了:

Run1 ran in 224 hsecs
Run2 ran in 269 hsecs
run 1 ran in 83.27% of the time
Name Run1 Run2
Diff
STAT...index fetch by key 0 48,178 48,178
STAT...buffer is not pinned co 48,178 96,356 48,178
STAT...table fetch by rowid 0 48,178 48,178
STAT...cluster key scans 48,178 0 -48,178
STAT...session logical reads 48,889 145,245 96,356
STAT...consistent gets 48,184 144,540 96,356
STAT...consistent gets from ca 48,184 144,540 96,356
STAT...consistent gets - exami 48,184 144,540 96,356
LATCH.cache buffers chains 51,663 148,019 96,356
Run1 latches total versus runs -- difference and pct
Run1 Run2 Diff Pct
298,987 402,085 103,098 74.36% PL/SQL procedure successfully completed.
这个单表散列聚簇需要更少的缓冲区缓存闩来完成处理(它能更快地结束数据查找,而且能得到更多

的信息)。因此,TKPROF报告显示出这一次的CPU使用量大幅减少: SELECT * FROM T_HASHED WHERE OBJECT_ID = :B1
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
Parse 1 0.00 0.00 0
0 0 0
Execute 48178 4.45 4.52 0 2

0 0
Fetch 48178 0.67 0.82 0 48178
0 48178
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
total 96357 5.12 5.35 0 48180
0 48178
Rows Row Source Operation
------- ---------------------------------------------------
48178 TABLE ACCESS HASH T_HASHED (cr=48178 pr=0 pw=0 time=551123 us)
******************************************************************************** SELECT * FROM T_HEAP WHERE OBJECT_ID = :B1
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
Parse 1 0.00 0.00 0
0 0 0
Execute 48178 5.38 4.99 0 0
0 0
Fetch 48178 1.25 1.65 0 144534
0 48178
------- ------ -------- ---------- ---------- -----
----- ---------- ----------
total 96357 6.63 6.65 0 144534
0 48178

Rows Row Source Operation
------- ---------------------------------------------------
48178 TABLE ACCESS BY INDEX ROWID T_HEAP (cr=144534 pr=0 pw=0 time=1331049 us)
48178 INDEX UNIQUE SCAN T_HEAP_PK (cr=96356 pr=0 pw=0 time=710295 us)(object... 散列聚簇表小结 以上就是散列聚簇的核心。散列聚簇在概念上与索引聚簇很相似,只不过没有使用聚簇索引。在这里 ,
数据就是索引。聚簇键散列到一个块地址上,数据应该就在那个位置上。关于散列聚簇,需要了解以下要 点:
q 散 列聚簇一开始就要分配空间。Oracle根据你的HASHKEYS和SIZE来计算HASHKEYS/trunc
(blocksize/SIZE),立即 分配空间,并完成格式化,一旦将第一个表放入这个聚簇中,任何 全面扫描都会命中每一个已分配的块。在这方面,它与其他的所有表都不同。
q 散列聚簇中的HASHKEY数是固定大小的。除非重新聚簇,否则不能改变散列表的大小。这 并不会限制聚簇中能存储的数据量,它只是限制了能为这个聚簇生成的惟一散列键的个数。如 果HASHKEY值设置得太低,可能因为无意的散列冲突影响性能。
q 不 能在聚簇键上完成区间扫描。诸如WHERE cluster_key BETWEEN 50 AND 60谓词条件 不能使用散列算法。介于50~60之间的可能值有无限多个,服务器必须生成所有可能的值,并 分别计算散列,来查看相应位置是否有数据。这是不 可能的。如果你在一个聚簇键上使用区间 扫描,而且没有使用传统索引,实际上会全面扫描这个聚簇。
散列聚簇适用于以下情况:
你很清楚表中会有多少行,或者你知道一个合理的上界。HASHKEY和SIZE参数的大小要正确,这对 于避免聚簇重建至关重要。
与 获取操作相比,DML(特别是插入)很轻。这说明必须在数据获取的优化和新数据的创建之间有所 权衡。有多少个插入算轻,对此没有定论,对某些人来说,每个 单位时间有100,000个插入就算轻,而在 另一个人来看,可能每单位时间100个插入才算轻——这取决于具体的数据获取模式。更新不会引入严重 的开销, 除非更新了HASHKEY(不过这可不是一个好主意,因为更新HASHKEY会导致行迁移)。
经常按HASHKEY值访问数据。例如,假如有一个零件表,并按零件号来访问这些零件。查找表特别适 合采用散列聚簇。