[20181130]如何猜测那些值存在hash冲突.txt

[20181130]如何猜测那些值存在hash冲突.txt

--//今年6月份开始kerrycode的1个帖子提到子查询结果缓存在哈希表中情况:
--//链接:http://www.cnblogs.com/kerrycode/p/9099507.html,摘要:
通俗来将，当使用标量子查询的时候，oracle会将子查询结果缓存在哈希表中， 如果后续的记录出现同样的值，优化器通过缓存在哈希
表中的值，判断重复值不用重复调用函数，直接使用上次计算结果即可。从而减少调用函数次数，从而达到优化性能的效果。另外在
oracle 10和11中， 哈希表只包含了255个buckets，也就是说它能存储255个不同值，如果超过这个范围，就会出现散列冲突，那些出现
散列冲突的值就会重复调用函数，即便如此，依然能达到大幅改善性能的效果。

--//我当时就非常想从作者了解"哈希表只包含了255个buckets",这个观点的出处.kerrycode给了我一个链接:
https://blogs.oracle.com/oraclemagazine/on-caching-and-evangelizing-sql

oracle database will use this hash table to remember the scalar subquery and the inputs to it—just :deptno in this case
—and the output from it. at the beginning of every query execution, this cache is empty, but suppose you run the query
and the first projects row you retrieve has a deptno value of 10. oracle database will assign the number 10 to a hash
value between 1 and 255 (the size of the hash table cache in oracle database 10g and oracle database 11g currently) and
will look in that hash table slot to see if the answer exists. in this case, it will not, so oracle database must run
the scalar subquery with the input of 10 to get the answer. if that answer (count) is 42, the hash table may look
something like this:

select count(*) from emp where emp.deptno = :deptno
:deptno     count(*)

you'll have saved the deptno value of 10 and the answer (count) of 42 in some slot—probably not the first or last slot,
but whatever slot the hash value 10 is assigned to. now suppose the second row you get back from the projects table
includes a deptno value of 20. oracle database will again look in the hash table after assigning the value 20, and it
will discover "no result in the cache yet." so it will run the scalar subquery, get the result, and put it into the hash
table cache. now the cache may look like this:

select count(*) from emp where emp.deptno = :deptno
:deptno     count(*)
select count(*) from emp where emp.deptno = :deptno
:deptno     count(*)
…     …
10     42

now suppose the query returns a third row and it again includes a deptno value of 10. this time, oracle database will
see deptno = 10, find that it already has that value in the hash table cache, and will simply return 42 from the cache
instead of executing the scalar subquery. in fact, it will never have to run that scalar subquery for the deptno values
of 10 or 20 again for that query—it will already have the answer.

what happens if the number of unique deptno values exceeds the size of the hash table? what if there are more than 255
values? or, more generally, if more than one deptno value is assigned to the same slot in the hash table, what happens
in a hash collision?

the answer is the same for all these questions and is rather simple: oracle database will not be able to cache the
second or nth value to that slot in the hash table. for example, what if the third row returned by the query contains
the deptno = 30 value? further, suppose that deptno = 30 is to be assigned to exactly the same hash table slot as deptno
= 10. the database won't be able to effectively cache deptno = 30 in this case—the value will never make it into the
hash table. it will, however, be "partially cached." oracle database still has the hash table with all the previous
executions, but it also keeps the last scalar subquery result it had "next to" the hash table. that is, if the fourth
row also includes a deptno = 30 value, oracle database will discover that the result is not in the hash table but is
"next to" the hash table, because the last time it ran the scalar subquery, it was run with an input of 30. on the other
hand, if the fourth row includes a deptno = 40 value, oracle database will run the scalar subquery with the deptno = 40
value (because it hasn't seen that value yet during this query execution) and overwrite the deptno = 30 result. the next
time oracle database sees deptno = 30 in the result set, it'll have to run that scalar subquery again.

--//我自己开始瞎尝试各种方法验证hash buckets是否是255.我开始先入为主,认为就是255(或者256),经历许多混乱,最后kerrycode给我
--//一个测试方法,链接如下:
http://blog.itpub.net/267265/viewspace-2156702/
http://www.cnblogs.com/kerrycode/p/9223093.html

--//按照这个方法很容易验证hash buckets大小,11.2.0.4是1024,10.2.0.4是512,12.1.0.1是1024.
--//我想起开始测试时,75与48存在冲突的情况,当时我没有想到这么靠前的值存在冲突,为了验证我几乎是1个1个尝试.
--//因为你根本不知道oracle的算法.
--//昨天看https://jonathanlewis.wordpress.com/2018/11/26/shrink-space-2/,验证为什么4与432存在冲突.

1.环境:
scott@book> @ &r/ver1
port_string                    version        banner
------------------------------ -------------- --------------------------------------------------------------------------------
x86_64/linux 2.4.xx            11.2.0.4.0     oracle database 11g enterprise edition release 11.2.0.4.0 - 64bit production

create or replace function f( x in varchar2 ) return number
as
begin
        dbms_application_info.set_client_info(userenv('client_info')+1 );
        return length(x);
end;
/

scott@book> create table t as select rownum id1,mod(rownum-1,10000)+1 id2 from dual connect by level<=20000;
table created.

scott@book> create table t1 ( a number ,b number);
table created.
--//字段a 记录调用函数次数.


2.建立测试脚本:
--//建立脚本cz.txt
exec dbms_application_info.set_client_info(0);
set term off
exec :x := &&1;
select count(distinct f_id2) from (select id2,(select f(id2) from dual) as f_id2 from t where id2 in (&&2,:x ));
set term on
insert into t1 values (userenv('client_info') ,:x) ;
commit ;

--//建立shell脚本cz.sh:
#! /bin/bash
sqlplus -s -l scott/book <<eof >> hz.txt
variable x number;
$(seq 500 | xargs -i{} echo @cz.txt {} $1)
quit
eof

3.测试:
--//执行脚本cz.sh:
$ . cz.sh 4

scott@book> select * from t1 where a<>2;
         a          b
---------- ----------
         1          4
         3        432
--//可以发现4,432存在冲突.函数调用了3次.

scott@book> delete t1;
500 rows deleted.

scott@book> commit ;
commit complete.

--//验证1与那个值存在冲突.

$ . cz.sh 1

scott@book> select * from t1 where a<>2;
         a          b
---------- ----------
         3        484
         1          1

--//可以验证1与484存在hash冲突.

4.再拿链接例子做测试:
--//链接:https://jonathanlewis.wordpress.com/2018/11/26/shrink-space-2/
scott@book> update emp set dept_no=484 where dept_no=432;
1 row updated.

scott@book> commit ;
commit complete.

scott@book> alter session set statistics_level = all;
session altered.

select
        /*+ gather_plan_statistics post-shrink  */
        count(*)
from    (
        select  /*+ no_merge */
                outer.*
        from emp outer
        where outer.sal >
                (
                        select /*+ no_unnest */ avg(inner.sal)
                        from emp inner
                        where inner.dept_no = outer.dept_no
                )
        )
;

  count(*)
----------
      9498

scott@book> @ dpc '' ''
plan_table_output
-------------------------------------
sql_id  gx7xb7rhfd2zf, child number 0
-------------------------------------
select         /*+ gather_plan_statistics post-shrink  */
count(*) from    (         select  /*+ no_merge */
outer.*         from emp outer         where outer.sal >
 (                         select /*+ no_unnest */ avg(inner.sal)
                  from emp inner                         where
inner.dept_no = outer.dept_no                 )         )

plan hash value: 322796046

------------------------------------------------------------------------------------------------------------------------
| id  | operation             | name | starts | e-rows |e-bytes| cost (%cpu)| e-time   | a-rows |   a-time   | buffers |
------------------------------------------------------------------------------------------------------------------------
|   0 | select statement      |      |      1 |        |       |   569 (100)|          |      1 |00:00:03.43 |     783k|
|   1 |  sort aggregate       |      |      1 |      1 |       |            |          |      1 |00:00:03.43 |     783k|
|   2 |   view                |      |      1 |    143 |       |   569   (1)| 00:00:07 |   9498 |00:00:03.42 |     783k|
|*  3 |    filter             |      |      1 |        |       |            |          |   9498 |00:00:03.42 |     783k|
|   4 |     table access full | emp  |      1 |  20001 |   156k|    71   (0)| 00:00:01 |  19001 |00:00:00.01 |     247 |
|   5 |     sort aggregate    |      |   3173 |      1 |     8 |            |          |   3173 |00:00:03.41 |     783k|
|*  6 |      table access full| emp  |   3173 |   2857 | 22856 |    71   (0)| 00:00:01 |     10m|00:00:02.71 |     783k|
------------------------------------------------------------------------------------------------------------------------
--//循环3173.

scott@book> select dept_no,count(*) from emp group by dept_no order by 1;
   dept_no   count(*)
---------- ----------
         0       3167
         1       3167
         2       3167
         3       3166
         4       3166
         5       3167
       484          1
7 rows selected.
--//dept_no=1出现hash冲突.
--//dept_no=484 循环1次
--//dept_no=0   循环1次
--//dept_no=1   循环3167次
--//dept_no=2   循环1次
--//dept_no=3   循环1次
--//dept_no=4   循环1次
--//dept_no=5   循环1次

--//这样累加: 1+1+3167+1+1+1+1 = 3173,这样就相互验证了.

4.我上面的测试纯粹是蛮力测试,改写为pl/sql脚本看看,pl/sql确实不熟练....

scott@book> create table t2 ( a number ,b number,c number);
table created.
--//字段a 记录调用函数次数.

--//脚本cy.txt
declare
x number;
  begin
   for i in 1..10000 loop
     dbms_application_info.set_client_info(0);
     select count(distinct f_id2) into x from (select id2,(select f(id2) from dual) as f_id2 from t where id2 in (i, &&1 ) );
     if ( userenv('client_info') =3 ) then  
          insert into t2 values (userenv('client_info') ,i,&&1) ;
          commit ;
          exit;
     end if;
   end loop;
end;
/
--//我加入发现后exit(退出).你可以注解或者取消,这样测试1..10000之间的hash buckets冲突值.

--//执行如下:
@ cy.txt 4
@ cy.txt 1
@ cy.txt 3
@ cy.txt 18
@ cy.txt 48
@ cy.txt 75

scott@book> select * from t2;
         a          b          c
---------- ---------- ----------
         3        432          4
         3        484          1
         3        735          3
         3       2071         18
         3         75         48
         3         48         75
6 rows selected.

--//这样就很快知道那些值会发生hash冲突了.
--//不知道那位还有什么更好的方法...