Performance of Oracle Object Collection Comparisons - Part2

In Blog: Blog Performance of Oracle Object Collection Comparisons - Part1 we discussed two functions: SET, Equal and Not Equal Comparisons. Now we continue to look on other two functions:

COLLECT
    COLLECT is an aggregate function that takes as its argument a column of any type and creates a nested table of the input type out of the rows selected.

Multiset Operators
   Multiset operators combine the results of two nested tables into a single nested table.

1. Setup the test (see appended Test Code)

2. Run the test by:
        truncate table test_stat;
    exec all_test_run_2(4);

3. Wait test finished, query the statistics by:

SET LINES 400
SET NUMWIDTH 12
SET NUMFORMAT 999,999,999
COLUMN TOTAL_COMP_EST_RATIO FORMAT 999.99

select s.*, round(s.total_comp_est/nullif(s.total_comp, 0), 2) total_comp_est_ratio
  from (select t.*, round(10*1000*elapsed/nullif(total_comp, 0), 2) us_per_comp,
         case test_name 
           when 'COLLECT_SORT'                     then round(cnt*ln(cnt)*3)
           when 'COLLECT_SORT_DIST'                then round(cnt*ln(cnt)*3/(greatest(log(10, cnt/disticnt_cnt), 1)))
           when 'COLLECT_DISTINCT'                 then 2*cnt
           when 'COLLECT_DISTINCT_DIST'            then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_UNION_ALL'               then 2*cnt
           when 'MULTISET_UNION_ALL_DIST'          then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_UNION_DISTINCT'          then 2*cnt
           when 'MULTISET_UNION_DISTINCT_DIST'     then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_EXCEPT_ALL'              then 2*cnt
           when 'MULTISET_EXCEPT_ALL_DIST'         then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_EXCEPT_DISTINCT'         then 2*cnt
           when 'MULTISET_EXCEPT_DISTINCT_DIST'    then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_INTERSECT_ALL'           then 2*cnt
           when 'MULTISET_INTERSECT_ALL_DIST'      then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
           when 'MULTISET_INTERSECT_DISTINCT'      then 2*cnt
           when 'MULTISET_INTERSECT_DISTINCT_DIST' then 2*cnt*(greatest(log(10, cnt/disticnt_cnt), 1))
         end total_comp_est 
     from test_stat t) s;

returns:

  


  
TEST_NAME
  
RUN_ID
  
CNT
  
DISTICNT_CNT
  
ELAPSED
  
TOTAL_COMP
  
SINGLE_COMP
  
US_PER_COMP
  
TOTAL_COMP_EST
  
TOTAL_COMP_EST_RATIO
  
    
COLLECT_SORT
    

1

    

10

    

10

    

0

    

50

    

5

    

0

    

69

    

1.38

  
    
COLLECT_SORT
    

2

    

100

    

100

    

2

    

1278

    

12.78

    

15.65

    

1382

    

1.08

  
    
COLLECT_SORT
    

3

    

1000

    

1000

    

38

    

21396

    

21.396

    

17.76

    

20723

    

0.97

  
    
COLLECT_SORT
    

4

    

10000

    

10000

    

517

    

302050

    

30.205

    

17.12

    

276310

    

0.91

  
    
COLLECT_SORT_DIST
    

1

    

10000

    

10

    

117

    

59990

    

5.999

    

19.5

    

92103

    

1.54

  
    
COLLECT_SORT_DIST
    

2

    

10000

    

100

    

212

    

117108

    

11.7108

    

18.1

    

138155

    

1.18

  
    
COLLECT_SORT_DIST
    

3

    

10000

    

1000

    

322

    

184044

    

18.4044

    

17.5

    

276310

    

1.5

  
    
COLLECT_SORT_DIST
    

4

    

10000

    

10000

    

515

    

302050

    

30.205

    

17.05

    

276310

    

0.91

  
    
COLLECT_DISTINCT
    

1

    

10

    

10

    

0

    

26

    

2.6

    

0

    

20

    

0.77

  
    
COLLECT_DISTINCT
    

2

    

100

    

100

    

1

    

214

    

2.14

    

46.73

    

200

    

0.93

  
    
COLLECT_DISTINCT
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
COLLECT_DISTINCT
    

4

    

10000

    

10000

    

45

    

20028

    

2.0028

    

22.47

    

20000

    

1

  
    
COLLECT_DISTINCT_DIST
    

1

    

10000

    

10

    

105

    

57968

    

5.7968

    

18.11

    

60000

    

1.04

  
    
COLLECT_DISTINCT_DIST
    

2

    

10000

    

100

    

200

    

116242

    

11.6242

    

17.21

    

40000

    

0.34

  
    
COLLECT_DISTINCT_DIST
    

3

    

10000

    

1000

    

279

    

164002

    

16.4002

    

17.01

    

20000

    

0.12

  
    
COLLECT_DISTINCT_DIST
    

4

    

10000

    

10000

    

45

    

20028

    

2.0028

    

22.47

    

20000

    

1

  
    
MULTISET_UNION_ALL
    

1

    

10

    

10

    

0

    

26

    

2.6

    

0

    

20

    

0.77

  
    
MULTISET_UNION_ALL
    

2

    

100

    

100

    

0

    

214

    

2.14

    

0

    

200

    

0.93

  
    
MULTISET_UNION_ALL
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
MULTISET_UNION_ALL
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_UNION_ALL_DIST
    

1

    

10000

    

10

    

104

    

57968

    

5.7968

    

17.94

    

60000

    

1.04

  
    
MULTISET_UNION_ALL_DIST
    

2

    

10000

    

100

    

199

    

116242

    

11.6242

    

17.12

    

40000

    

0.34

  
    
MULTISET_UNION_ALL_DIST
    

3

    

10000

    

1000

    

280

    

164002

    

16.4002

    

17.07

    

20000

    

0.12

  
    
MULTISET_UNION_ALL_DIST
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_UNION_DISTINCT
    

1

    

10

    

10

    

0

    

26

    

2.6

    

0

    

20

    

0.77

  
    
MULTISET_UNION_DISTINCT
    

2

    

100

    

100

    

1

    

214

    

2.14

    

46.73

    

200

    

0.93

  
    
MULTISET_UNION_DISTINCT
    

3

    

1000

    

1000

    

4

    

2020

    

2.02

    

19.8

    

2000

    

0.99

  
    
MULTISET_UNION_DISTINCT
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_UNION_DISTINCT_DIST
    

1

    

10000

    

10

    

104

    

57968

    

5.7968

    

17.94

    

60000

    

1.04

  
    
MULTISET_UNION_DISTINCT_DIST
    

2

    

10000

    

100

    

199

    

116242

    

11.6242

    

17.12

    

40000

    

0.34

  
    
MULTISET_UNION_DISTINCT_DIST
    

3

    

10000

    

1000

    

279

    

164002

    

16.4002

    

17.01

    

20000

    

0.12

  
    
MULTISET_UNION_DISTINCT_DIST
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_EXCEPT_ALL
    

1

    

10

    

10

    

1

    

26

    

2.6

    

384.62

    

20

    

0.77

  
    
MULTISET_EXCEPT_ALL
    

2

    

100

    

100

    

0

    

214

    

2.14

    

0

    

200

    

0.93

  
    
MULTISET_EXCEPT_ALL
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
MULTISET_EXCEPT_ALL
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_EXCEPT_ALL_DIST
    

1

    

10000

    

10

    

104

    

57968

    

5.7968

    

17.94

    

60000

    

1.04

  
    
MULTISET_EXCEPT_ALL_DIST
    

2

    

10000

    

100

    

199

    

116242

    

11.6242

    

17.12

    

40000

    

0.34

  
    
MULTISET_EXCEPT_ALL_DIST
    

3

    

10000

    

1000

    

280

    

164002

    

16.4002

    

17.07

    

20000

    

0.12

  
    
MULTISET_EXCEPT_ALL_DIST
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_EXCEPT_DISTINCT
    

1

    

10

    

10

    

0

    

26

    

2.6

    

0

    

20

    

0.77

  
    
MULTISET_EXCEPT_DISTINCT
    

2

    

100

    

100

    

1

    

214

    

2.14

    

46.73

    

200

    

0.93

  
    
MULTISET_EXCEPT_DISTINCT
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
MULTISET_EXCEPT_DISTINCT
    

4

    

10000

    

10000

    

47

    

20028

    

2.0028

    

23.47

    

20000

    

1

  
    
MULTISET_EXCEPT_DISTINCT_DIST
    

1

    

10000

    

10

    

104

    

57968

    

5.7968

    

17.94

    

60000

    

1.04

  
    
MULTISET_EXCEPT_DISTINCT_DIST
    

2

    

10000

    

100

    

200

    

116242

    

11.6242

    

17.21

    

40000

    

0.34

  
    
MULTISET_EXCEPT_DISTINCT_DIST
    

3

    

10000

    

1000

    

280

    

164002

    

16.4002

    

17.07

    

20000

    

0.12

  
    
MULTISET_EXCEPT_DISTINCT_DIST
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_INTERSECT_ALL
    

1

    

10

    

10

    

1

    

26

    

2.6

    

384.62

    

20

    

0.77

  
    
MULTISET_INTERSECT_ALL
    

2

    

100

    

100

    

0

    

214

    

2.14

    

0

    

200

    

0.93

  
    
MULTISET_INTERSECT_ALL
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
MULTISET_INTERSECT_ALL
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_INTERSECT_ALL_DIST
    

1

    

10000

    

10

    

105

    

57968

    

5.7968

    

18.11

    

60000

    

1.04

  
    
MULTISET_INTERSECT_ALL_DIST
    

2

    

10000

    

100

    

200

    

116242

    

11.6242

    

17.21

    

40000

    

0.34

  
    
MULTISET_INTERSECT_ALL_DIST
    

3

    

10000

    

1000

    

281

    

164002

    

16.4002

    

17.13

    

20000

    

0.12

  
    
MULTISET_INTERSECT_ALL_DIST
    

4

    

10000

    

10000

    

47

    

20028

    

2.0028

    

23.47

    

20000

    

1

  
    
MULTISET_INTERSECT_DISTINCT
    

1

    

10

    

10

    

0

    

26

    

2.6

    

0

    

20

    

0.77

  
    
MULTISET_INTERSECT_DISTINCT
    

2

    

100

    

100

    

0

    

214

    

2.14

    

0

    

200

    

0.93

  
    
MULTISET_INTERSECT_DISTINCT
    

3

    

1000

    

1000

    

5

    

2020

    

2.02

    

24.75

    

2000

    

0.99

  
    
MULTISET_INTERSECT_DISTINCT
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  
    
MULTISET_INTERSECT_DISTINCT_DIST
    

1

    

10000

    

10

    

105

    

57968

    

5.7968

    

18.11

    

60000

    

1.04

  
    
MULTISET_INTERSECT_DISTINCT_DIST
    

2

    

10000

    

100

    

201

    

116242

    

11.6242

    

17.29

    

40000

    

0.34

  
    
MULTISET_INTERSECT_DISTINCT_DIST
    

3

    

10000

    

1000

    

280

    

164002

    

16.4002

    

17.07

    

20000

    

0.12

  
    
MULTISET_INTERSECT_DISTINCT_DIST
    

4

    

10000

    

10000

    

46

    

20028

    

2.0028

    

22.97

    

20000

    

1

  

Test Code

-- At first run Test Code in precedent Blog: "Performance of Oracle Object Collection Comparisons - Part1"
-- (http://ksun-oracle.blogspot.ch/2016/01/performance-of-oracle-object-collection_13.html)

------------------------------- COLLECT_test ---------------------------------
create or replace procedure collect_test (p_name varchar2, p_size number default 1000, p_dist_val pls_integer := null) as
 l_dist_val  number := coalesce(p_dist_val, p_size);
 l_test_name   varchar2(40);
  l_tobj_tab_1  tobj_tab := tobj_tab();
  l_start_time  number;
  l_elapsed     number;
begin
 helper.p_num1_cnt := 0;
 l_start_time := dbms_utility.get_time;
 
 if p_name in ('COLLECT_SORT', 'COLLECT_SORT_DIST') then
  select cast(collect(tobj(num1, num2) order by tobj(num1, num2) desc) as tobj_tab) into l_tobj_tab_1
    from (select level num1, mod(level, l_dist_val) num2 from dual connect by level <= p_size);
 else
  -- Workaround due to PL/SQL: ORA-30482: DISTINCT option not allowed for this function
  -- DISTINCT option works for SQL, but not for PL/SQL  
  execute immediate q'[
   select cast(collect(distinct tobj(num1, num2)) as tobj_tab)
     from (select level num1, mod(level, :p_dist_val) num2 from dual connect by level <= :p_size)]'
   into l_tobj_tab_1 using l_dist_val, p_size; 
 end if;
    
 l_elapsed := dbms_utility.get_time - l_start_time;
 helper.record(p_name, p_size, l_dist_val,
        l_elapsed, helper.p_num1_cnt, (helper.p_num1_cnt/p_size));
 helper.format(p_name||' count=', l_tobj_tab_1.count);
 helper.format('  Total Number of Object Comparisons=', helper.p_num1_cnt);   
end;
/    

--exec collect_test('COLLECT_SORT', 100, 100);
--exec collect_test('COLLECT_SORT_DIST', 100, 10);
--exec collect_test('COLLECT_DISTINCT', 100, 100);
--exec collect_test('COLLECT_DISTINCT_DIST', 100, 10);

create or replace procedure collect_test_run(p_run number) as
begin
 for i in 1..p_run loop collect_test('COLLECT_SORT', power(10, i), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('COLLECT_SORT_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('COLLECT_DISTINCT', power(10, i), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('COLLECT_DISTINCT_DIST', power(10, p_run), power(10, i)); end loop; 
end;
/ 

--exec collect_test_run(3);

------------------------------- MULTISET_test ---------------------------------
create or replace procedure multiset_test (p_name varchar2, p_size number default 1000, p_dist_val pls_integer := null) as
 l_dist_val  number := coalesce(p_dist_val, p_size);
 l_test_name   varchar2(40);
  l_tobj_tab_1  tobj_tab := tobj_tab();
  l_tobj_tab_2 tobj_tab := tobj_tab();
  l_tobj_tab_3 tobj_tab := tobj_tab();
  l_start_time  number;
  l_elapsed     number;
begin
 select cast(multiset(select level, mod(level, l_dist_val) from dual connect by level <= p_size) as tobj_tab) 
  into l_tobj_tab_1 from dual;
 select cast(multiset(select level, mod(level, l_dist_val) from dual connect by level <= p_size) as tobj_tab) 
   into l_tobj_tab_2 from dual;
 
  helper.p_num1_cnt := 0;
  l_start_time := dbms_utility.get_time;
  
  case 
  when p_name in ('MULTISET_UNION_ALL', 'MULTISET_UNION_ALL_DIST') then 
     l_tobj_tab_3 := l_tobj_tab_1 MULTISET UNION ALL l_tobj_tab_2;
  when p_name in ('MULTISET_UNION_DISTINCT', 'MULTISET_UNION_DISTINCT_DIST') then 
     l_tobj_tab_3 := l_tobj_tab_1 MULTISET UNION DISTINCT l_tobj_tab_2;
  when p_name in ('MULTISET_EXCEPT_ALL', 'MULTISET_EXCEPT_ALL_DIST') then 
       l_tobj_tab_3 := l_tobj_tab_1 MULTISET EXCEPT ALL l_tobj_tab_2;
  when p_name in ('MULTISET_EXCEPT_DISTINCT', 'MULTISET_EXCEPT_DISTINCT_DIST') then 
       l_tobj_tab_3 := l_tobj_tab_1 MULTISET EXCEPT DISTINCT l_tobj_tab_2;
  when p_name in ('MULTISET_INTERSECT_ALL', 'MULTISET_INTERSECT_ALL_DIST') then 
       l_tobj_tab_3 := l_tobj_tab_1 MULTISET INTERSECT ALL l_tobj_tab_2;
  when p_name in ('MULTISET_INTERSECT_DISTINCT', 'MULTISET_INTERSECT_DISTINCT_DIST') then 
       l_tobj_tab_3 := l_tobj_tab_1 MULTISET INTERSECT DISTINCT l_tobj_tab_2;
 end case;
 
 l_elapsed := dbms_utility.get_time - l_start_time;
 helper.record(p_name, p_size, l_dist_val,
        l_elapsed, helper.p_num1_cnt, (helper.p_num1_cnt/p_size/2));
 helper.format(p_name||' count=', l_tobj_tab_3.count);  
 helper.format('  Total Number of Object Comparisons=', helper.p_num1_cnt);  
end;
/ 

--exec multiset_test('MULTISET_UNION_ALL', 100, 100);
--exec multiset_test('MULTISET_UNION_DISTINCT', 100, 100);
--exec multiset_test('MULTISET_UNION_DISTINCT_DIST', 100, 10);
--exec multiset_test('MULTISET_EXCEPT_ALL', 100, 100);
--exec multiset_test('MULTISET_EXCEPT_DISTINCT', 100, 100);
--exec multiset_test('MULTISET_INTERSECT_ALL', 100, 100);
--exec multiset_test('MULTISET_INTERSECT_DISTINCT', 100, 100);
--exec multiset_test('MULTISET_INTERSECT_DISTINCT_DIST', 100, 100);

create or replace procedure multiset_test_run(p_run number) as
begin
 for i in 1..p_run loop collect_test('MULTISET_UNION_ALL',    power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_UNION_ALL_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_UNION_DISTINCT',      power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_UNION_DISTINCT_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_EXCEPT_ALL',      power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_EXCEPT_ALL_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_EXCEPT_DISTINCT',      power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_EXCEPT_DISTINCT_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_INTERSECT_ALL',      power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_INTERSECT_ALL_DIST', power(10, p_run), power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_INTERSECT_DISTINCT',      power(10, i),     power(10, i)); end loop;
 for i in 1..p_run loop collect_test('MULTISET_INTERSECT_DISTINCT_DIST', power(10, p_run), power(10, i)); end loop;
end;
/ 

--exec multiset_test_run(3);

------------------------------- Test Control 2 ---------------------------------
create or replace procedure all_test_run_2(p_run number) as
begin
 collect_test_run(p_run);
 multiset_test_run(p_run);
end;
/ 

Performance of Oracle Object Collection Comparisons - Part1

Oracle object types are user-defined types that make it possible to model real-world entities, similar to the class mechanism in C++ and Java (Database Object-Relational Developer's Guide Performance of Object Comparisons).

This Blog presents an approach to investigate Performance of Oracle Object Collection Comparisons used in two functions:

• SET

    Converts a nested table into a set by eliminating duplicates. The function returns a nested table whose elements are distinct from one another. SET function requires map method, order method does NOT work.

• Equal and Not Equal Comparisons

    Two nested tables are equal if they have the same named type, have the same cardinality, and their elements are equal based on map method.

The next Blog:  Performance of Oracle Object Collection Comparisons - Part2 will talk about other two functions: COLLECT and Multiset Operators.

By implementing a map member function in Object (similar to Java Comparator/Comparable Interface), the number of calls can be recorded. In aid of such counter, this Blog is trying to find a way to study the complexity of applied algorithm (see appended test code).

1. Setup the test (see appended Test Code)

2. Run the test by:
    truncate table test_stat;
    exec all_test_run_1(4);

3. Wait test finished, query the statistics by:

SET LINES 400
SET NUMWIDTH 12
SET NUMFORMAT 999,999,999
COLUMN TOTAL_COMP_EST_RATIO FORMAT 999.99
select s.*, round(s.total_comp_est/nullif(s.total_comp, 0), 2) total_comp_est_ratio
  from (select t.*, round(10*1000*elapsed/nullif(total_comp, 0), 2) us_per_comp,
         case test_name 
           when 'SET_TEST'               then cnt*(cnt-1)
           when 'SET_TEST_DIST'          then cnt*(cnt-1)*(disticnt_cnt/cnt)
           when 'EQUAL_TEST'             then 2*cnt
           when 'EQUAL_TEST_DIST'        then 2*cnt
           when 'EQUAL_TEST_RANDOM'      then (cnt*disticnt_cnt/2)
           when 'EQUAL_TEST_DIST_RANDOM' then (cnt*disticnt_cnt/2)
         end total_comp_est 
     from test_stat t) s; 

returns:

  


  
TEST_NAME
  
RUN_ID
  
CNT
  
DISTICNT_CNT
  
ELAPSED
  
TOTAL_COMP
  
SINGLE_COMP
  
US_PER_COMP
  
TOTAL_COMP_EST
  
TOTAL_COMP_EST_RATIO
  
    
SET_TEST
    

1

    

10

    

10

    

0

    

90

    

9

    

0

    

90

    

1

  
    
SET_TEST
    

2

    

100

    

100

    

2

    

9900

    

99

    

2.02

    

9900

    

1

  
    
SET_TEST
    

3

    

1000

    

1000

    

193

    

999000

    

999

    

1.93

    

999000

    

1

  
    
SET_TEST
    

4

    

10000

    

10000

    

18826

    

99990000

    

9999

    

1.88

    

99990000

    

1

  
    
SET_TEST_DIST
    

1

    

10000

    

10

    

21

    

109980

    

10.998

    

1.91

    

99990

    

0.91

  
    
SET_TEST_DIST
    

2

    

10000

    

100

    

198

    

1009800

    

100.98

    

1.96

    

999900

    

0.99

  
    
SET_TEST_DIST
    

3

    

10000

    

1000

    

1932

    

10008000

    

1000.8

    

1.93

    

9999000

    

1

  
    
SET_TEST_DIST
    

4

    

10000

    

10000

    

18802

    

99990000

    

9999

    

1.88

    

99990000

    

1

  
    
EQUAL_TEST
    

1

    

10

    

10

    

0

    

20

    

1

    

0

    

20

    

1

  
    
EQUAL_TEST
    

2

    

100

    

100

    

0

    

200

    

1

    

0

    

200

    

1

  
    
EQUAL_TEST
    

3

    

1000

    

1000

    

1

    

2000

    

1

    

5

    

2000

    

1

  
    
EQUAL_TEST
    

4

    

10000

    

10000

    

95

    

20000

    

1

    

47.5

    

20000

    

1

  
    
EQUAL_TEST_DIST
    

1

    

10000

    

10

    

95

    

20000

    

1

    

47.5

    

20000

    

1

  
    
EQUAL_TEST_DIST
    

2

    

10000

    

100

    

95

    

20000

    

1

    

47.5

    

20000

    

1

  
    
EQUAL_TEST_DIST
    

3

    

10000

    

1000

    

95

    

20000

    

1

    

47.5

    

20000

    

1

  
    
EQUAL_TEST_DIST
    

4

    

10000

    

10000

    

95

    

20000

    

1

    

47.5

    

20000

    

1

  
    
EQUAL_TEST_RANDOM
    

1

    

10

    

10

    

0

    

54

    

2.7

    

0

    

50

    

0.93

  
    
EQUAL_TEST_RANDOM
    

2

    

100

    

100

    

1

    

4710

    

23.55

    

2.12

    

5000

    

1.06

  
    
EQUAL_TEST_RANDOM
    

3

    

1000

    

1000

    

101

    

501358

    

250.679

    

2.01

    

500000

    

1

  
    
EQUAL_TEST_RANDOM
    

4

    

10000

    

10000

    

10142

    

50549260

    

2527.463

    

2.01

    

50000000

    

0.99

  
    
EQUAL_TEST_DIST_RANDOM
    

1

    

10000

    

10

    

327

    

1184932

    

59.2466

    

2.76

    

50000

    

0.04

  
    
EQUAL_TEST_DIST_RANDOM
    

2

    

10000

    

100

    

956

    

4374904

    

218.7452

    

2.19

    

500000

    

0.11

  
    
EQUAL_TEST_DIST_RANDOM
    

3

    

10000

    

1000

    

2968

    

14358672

    

717.9336

    

2.07

    

5000000

    

0.35

  
    
EQUAL_TEST_DIST_RANDOM
    

4

    

10000

    

10000

    

9992

    

49718366

    

2485.9183

    

2.01

    

50000000

    

1.01

  

The above test result table shows:

 SET_TEST has a total number of comparison equal to cnt*(cnt-1), that means a complexity of o(n²).
 SET_TEST_DIST has a total number of comparison equal to cnt*(cnt-1)*(disticnt_cnt/cnt), which depends the ratio of distinct items.
    Therefore elapsed time (in centisecond) increasing with number of distinct values.

 EQUAL_TEST has a total number of comparison equal to cnt*(cnt-1). i.e, a complexity of o(n).
 EQUAL_TEST_DIST has the same complexity as EQUAL_TEST, and elapsed time is irrelevant with number of distinct values.

 EQUAL_TEST_RANDOM has an estimated total number of comparison equal to (cnt*disticnt_cnt/2).
 EQUAL_TEST_DIST_RANDOM has the same estimated complexity as EQUAL_TEST_RANDOM.

TOTAL_COMP is the number of calls on map method (comparator). For each comparing of two objects, two calls are counted.

The estimated complexity (TOTAL_COMP_EST) is not precise and only an attempt to approximate the real complexity. It would be interesting to determine the exact form of computation in a long term.

The discussed performance behavior was first raised during 2010 FIFA World Cup, it takes a long way to be a bit clear.

Map and Order Method

Oracle Documentation: Basic Components of Oracle Objects said:

 A map method maps object return values to scalar values and can order multiple values by their position on the scalar axis. 
 
 An order method is a function for an object (SELF), with one declared parameter that is an object of the same type. 
 The method must return either a negative number, zero, or a positive number. 
 
 You can declare a map method or an order method but not both.
 
 When sorting or merging a large number of objects, use a map method, which maps all the objects into scalars, then sorts the scalars. 
 An order method is less efficient because it must be called repeatedly (it can compare only two objects at a time). 

The above test shows that the TOTAL_COMP (calls of map method) is not linear to the number of objects, which does not match the description:

 ... use a map method, which maps all the objects into scalars, then sorts the scalars.

It seems that map method is repeatedly called for each comparison of object instances.

Test Code

------------------------------- Setup map method ---------------------------------
drop table test_stat;

create table test_stat
 (test_name      varchar2 (40),
   run_id         number,
   cnt            number,
   disticnt_cnt   number,
   elapsed        number,
   total_comp     number,
   single_comp    number);
   
create or replace package helper as
 p_num1_cnt number := 0;
 procedure format(p_name varchar2, p_value number);
 procedure record(p_test_name varchar2, p_cnt number, p_disticnt_cnt number, 
                  p_elapsed number, p_total_comp number, p_single_comp number);
end helper;
/

create or replace package body helper as
 procedure format(p_name varchar2, p_value number) as
 begin
  dbms_output.put_line(rpad(p_name, 40) || lpad(p_value, 10));
 end format;

 procedure record(p_test_name varchar2, p_cnt number, p_disticnt_cnt number, 
                  p_elapsed number, p_total_comp number, p_single_comp number) as
   l_run_id  number;
 begin
   select nvl(max(run_id), 0) + 1 into l_run_id from test_stat where test_name = p_test_name;
   insert into test_stat values(p_test_name, l_run_id, p_cnt, p_disticnt_cnt
                 ,p_elapsed, p_total_comp, p_single_comp);
   commit;
 end record; 
end helper;
/

drop type tobj_tab force;
drop type tobj force;

create or replace type tobj as object (
 p_num1 number,
 p_num2 number,
 map member function comp return integer);
/

create or replace type body tobj as
 map member function comp return integer is 
    begin 
      helper.p_num1_cnt := helper.p_num1_cnt + 1;
      return p_num2; 
    end; 
end;
/

create or replace type tobj_tab as table of tobj;
/

------------------------------- SET_test ---------------------------------
create or replace procedure set_test (p_name varchar2, p_size number default 1000
                   ,p_dist_val pls_integer := null) as
 l_dist_val     number := coalesce(p_dist_val, p_size);
  l_tobj_tab          tobj_tab := tobj_tab();
  l_tobj_tab_distinct tobj_tab := tobj_tab();
  l_start_time     number;
  l_elapsed        number;
begin
  select cast(collect(tobj(level, mod(level, l_dist_val))) as tobj_tab) into l_tobj_tab 
    from dual connect by level <= p_size; 
    
  helper.p_num1_cnt := 0;
  l_start_time := dbms_utility.get_time;
  l_tobj_tab_distinct := set(l_tobj_tab);
  l_elapsed := dbms_utility.get_time - l_start_time;
  
  -- SET test depends on number of objects, and also number of distinct objects
  helper.record(p_name, cardinality(l_tobj_tab), l_tobj_tab_distinct.count,
         l_elapsed, helper.p_num1_cnt, (helper.p_num1_cnt/p_size));
  
  helper.format(rpad('-', 40, '-'), null);
  helper.format('l_tobj_tab.count=', cardinality(l_tobj_tab));
  helper.format('l_tobj_tab_distinct.count=', l_tobj_tab_distinct.count);
  helper.format('elapsed(centi)=', l_elapsed);
  helper.format('Total Number of Object Comparisons=', helper.p_num1_cnt);
  helper.format('Number of Object Comparisons / Object=', (helper.p_num1_cnt/p_size));
  helper.format('l_dist_val=', l_dist_val);
end;
/

--exec set_test('SET_TEST_DIST', 10, 5);

create or replace procedure set_test_run(p_run number) as
begin
 for i in 1..p_run loop
  set_test('SET_TEST', power(10, i), power(10, i));
 end loop;
 
 for i in 1..p_run loop
  set_test('SET_TEST_DIST', power(10, p_run), power(10, i));
 end loop;
end;
/ 

--exec set_test_run(3);

------------------------------- EQUAL_test ---------------------------------
create or replace procedure equal_test (p_name varchar2, p_size number default 1000
             ,p_dist_val pls_integer := null, p_random boolean :=false) as
 l_dist_val  number := coalesce(p_dist_val, p_size);
 l_test_name   varchar2(40);
  l_tobj_tab_1  tobj_tab := tobj_tab();
  l_tobj_tab_2 tobj_tab := tobj_tab();
  l_start_time  number;
  l_elapsed     number;
begin
  select cast(collect(tobj(level, mod(level, l_dist_val))) as tobj_tab) into l_tobj_tab_1 
    from dual connect by level <= p_size; 
 
  if p_random then
   l_test_name := p_name ||'_RANDOM';
  select cast(collect(tobj(x, mod(x, l_dist_val))) as tobj_tab) into l_tobj_tab_2 
     from (select level x from dual connect by level <= p_size order by dbms_random.value);   
 else
  l_test_name := p_name;
  select cast(collect(tobj(x, mod(x, l_dist_val))) as tobj_tab) into l_tobj_tab_2 
     from (select level x from dual connect by level <= p_size);   
 end if;
    
  helper.p_num1_cnt := 0;
  l_start_time := dbms_utility.get_time;
  if (l_tobj_tab_1 = l_tobj_tab_2) then
   helper.format('l_tobj_tab_1 = l_tobj_tab_2', null);
  else 
   helper.format('l_tobj_tab_1 != l_tobj_tab_2', null);
  end if;
  l_elapsed := dbms_utility.get_time - l_start_time;
  
  helper.record(l_test_name, cardinality(l_tobj_tab_1), l_dist_val,
         l_elapsed, helper.p_num1_cnt, (helper.p_num1_cnt/p_size/2));
         
  helper.format('l_tobj_tab_1.count=', cardinality(l_tobj_tab_1));
  helper.format('l_tobj_tab_2.count=', l_tobj_tab_2.count);
  helper.format('elapsed(centi)=', l_elapsed);
  helper.format('Total Number of Object Comparisons=', helper.p_num1_cnt);
  helper.format('Number of Object Comparisons/Object=', (helper.p_num1_cnt/p_size/2));
  helper.format('l_dist_val=', l_dist_val);
end;
/

--exec equal_test(10, 5, false);
--exec equal_test(10, 5, true);

create or replace procedure equal_test_run(p_run number, p_random boolean :=false) as
begin
 for i in 1..p_run loop
  equal_test('EQUAL_TEST', power(10, i), power(10, i), p_random);
 end loop;
 
 for i in 1..p_run loop
  equal_test('EQUAL_TEST_DIST', power(10, p_run), power(10, i), p_random);
 end loop;
end;
/ 

--exec equal_test_run(3, false);
--exec equal_test_run(3, true);

------------------------------- Test Control 1 ---------------------------------
create or replace procedure all_test_run_1(p_run number, p_random boolean :=false) as
begin
 set_test_run(p_run);
 equal_test_run(p_run, false);
 equal_test_run(p_run, true);
end;
/

Foreign Keys and Library Cache Locks: Analysis

Blog: Foreign Keys and Library Cache Locks reveals one case of "Library Cache Locks" and demonstrated the test with a professional video show.

This Blog will try to provide a bit of author's understanding of such lock using the similar approaches listed in:
  Oracle 12c single session "library cache lock (cycle)" deadlock
  Oracle 11gR2 single session "library cache pin"

Setup Test by:

drop table child1;
drop table child2;
drop table parent;

create table parent as select rownum as id, cast(null as varchar2(100)) as pad from dual connect by level <= 1e3;
alter table parent add constraint parent_pk primary key (id);

create table child1 as select rownum as id, p1.id as parent_id, cast(null as varchar2(100)) as pad 
  from parent p1, parent p2, parent p3 where rownum <= 1e8;
alter table child1 add constraint child1_pk primary key (id);
alter table child1 add constraint child1_parent_fk foreign key (parent_id) references parent (id);

create table child2 as select rownum as id, cast(null as number) as parent_id, cast(null as varchar2(100)) as pad from dual;
alter table child2 add constraint child2_pk primary key (id);
alter table child2 add constraint child2_parent_fk foreign key (parent_id) references parent (id); 

Open two Sessions and execute statements sequentially:

Session_1(SID: 304)@T1
 ALTER TABLE child1 disable CONSTRAINT child1_parent_fk;

Session_1(SID: 304)@T2
 ALTER TABLE child1 ENABLE CONSTRAINT child1_parent_fk;

Session_2(SID: 331)@T3
 insert into child2 values (2, 2, null);

On a third Session, watch the blocking by query:

       with sq as(select /*+ materialize */ sid, saddr, event  
               ,to_char(p1, 'xxxxxxxxxxxxxxx') p1, p1text  
               ,to_char(p2, 'xxxxxxxxxxxxxxx') p2, p2text  
               ,to_char(p3, 'xxxxxxxxxxxxxxx') p3, p3text  
            from v$session where username in ('C1', 'C2') or sid in (304, 331))  
       select /*+ leading(s) */   
         (select kglnaobj||'('||kglobtyd||')'   
            from x$kglob v   
            where kglhdadr = object_handle and rownum=1) kglobj_name  
           ,s.*, v.*  
       from v$libcache_locks v, sq s  
       where 1=1 and v.holding_user_session = s.saddr   
        and object_handle in (select object_handle from v$libcache_locks where mode_requested !=0)  
        order by kglobj_name, holding_user_session, v.type, mode_held, mode_requested;   

Output:

 


  
KGLOBJ_NAME
  
SID
  
SADDR
  
EVENT
  
P1
  
P1TEXT
  
P2
  
P2TEXT
  
P3
  
P3TEXT
  
TYPE
  
ADDR
  
HOLDING_USER_SESSION
  
HOLDING_SESSION
  
OBJECT_HANDLE
  
LOCK_HELD
  
REFCOUNT
  
MODE_HELD
  
  
MODE_REQUESTED
  
SAVEPOINT_NUMBER
 

  
PARENT(TABLE)
  
304
  
000000018B731AB0
  
db file scattered read
  
6
  
file#
  
2273b0
  
block#
  
10
  
blocks
  
LOCK
  
000000016AF978A0
  
000000018B731AB0
  
000000018B731AB0
  
00000001736BBD20
  
0
  
1
  
3
  
0
  
5222
 

  
PARENT(TABLE)
  
304
  
000000018B731AB0
  
db file scattered read
  
6
  
file#
  
2273b0
  
block#
  
10
  
blocks
  
PIN
  
000000016EC0D488
  
000000018B731AB0
  
000000018B731AB0
  
00000001736BBD20
  
0
  
1
  
3
  
0
  
5222
 

  
PARENT(TABLE)
  
331
  
000000018C6EFF28
  
library cache lock
  
1736bbd20
  
handle address
  
142236f10
  
lock address
  
1069e000010002
  
100*mode+namespace
  
LOCK
  
0000000142236F10
  
000000018C6EFF28
  
000000018C6EFF28
  
00000001736BBD20
  
0
  
0
  
0
  
2
  
249740
 

where SID 304 executes at first:
 ALTER TABLE child1 ENABLE CONSTRAINT child1_parent_fk;
and SID 331 executes later:
 INSERT INTO child2 VALUES (2, 2, null);

SID 331 made a library cache LOCK request on PARENT(TABLE) with MODE_REQUESTED 2, however SID 304 already held a LOCK with MODE_HELD 3. Hence SID 331 was blocked, and has to wait till SID 304 released it.

In order to understand Library Cache Locks/Pins usage, a query before and after the statement will show the delta value.
For example (tested on Oracle 11.2.0.4.0), run:

 alter table child2 disable constraint child2_parent_fk;
 
 select name, loads, locks, pins, locked_total, pinned_total
 from v$db_object_cache v where (name like 'PARENT%' or name like 'CHILD%') order by name;
 
 ALTER TABLE child2 ENABLE CONSTRAINT child2_parent_fk;
 
 select name, loads, locks, pins, locked_total, pinned_total
 from v$db_object_cache v where (name like 'PARENT%' or name like 'CHILD%') order by name;

Output Before (some lines removed):
  NAME            LOADS      LOCKS       PINS LOCKED_TOTAL PINNED_TOTAL
  ---------- ---------- ---------- ---------- ------------ ------------
  CHILD2             13          0          0           75           77
  PARENT              2          0          0           60           59
 
Output After:
  NAME            LOADS      LOCKS       PINS LOCKED_TOTAL PINNED_TOTAL
  ---------- ---------- ---------- ---------- ------------ ------------
  CHILD2             14          0          0           82           85
  PARENT              2          0          0           66           65

We can see:
   LOCKED_TOTAL of CHILD2 increased 7, PARENT increased 6;
   PINNED_TOTAL of PARENT increased 8, PARENT increased 6;

 select name, loads, locks, pins, locked_total, pinned_total
 from v$db_object_cache v where (name like 'PARENT%' or name like 'CHILD%') order by name;
 
 -- pick a new ID to insert each time
 INSERT INTO child2 VALUES (22, 22, null);
 
 select name, loads, locks, pins, locked_total, pinned_total
 from v$db_object_cache v where (name like 'PARENT%' or name like 'CHILD%') order by name;

Output Before (some lines removed): 
 NAME                 LOADS      LOCKS       PINS LOCKED_TOTAL PINNED_TOTAL
 --------------- ---------- ---------- ---------- ------------ ------------
 CHILD2                  17          0          0          111          115
 PARENT                   2          0          0          157          156

Output After:
 NAME                 LOADS      LOCKS       PINS LOCKED_TOTAL PINNED_TOTAL
 --------------- ---------- ---------- ---------- ------------ ------------
 CHILD2                  17          0          0          112          116
 PARENT                   2          0          0          158          157

For insert, all LOCKED_TOTAL and PINNED_TOTAL are used exactly once.

The above Blog: Foreign Keys and Library Cache Locks attempts to find the explanation by looking on enqueue locks (OD, TM, TX and ORA-10704: Print out information about what en queues are being obtained). However, Library Cache Locks/Pins are probably about memory structures, which are evidenced by their memory address attributes.

Addendum (2016.01.21):

The Blog: Deadlock with a Virtual Column reveals one more interesting case of 'library cache lock' (cycle) deadlock, and demonstrated with the test code:

alter session set ddl_lock_timeout=37;

drop table emp;

create table emp (x number);  

-- No 'library cache lock' (cycle) deadlock for varchar2
-- create table emp (x varchar2(100));

create or replace function vc (p_ename in emp.x%type)
  return varchar2 deterministic is
begin
  return null;
end vc;
/

alter table emp add descr as (vc (x));

truncate table emp;

ORA-04020: deadlock detected while trying to lock object KSUN.EMP

Oracle Documentation said:
        ORA-04020: *Cause:  While trying to lock a library object, a deadlock is detected.

During the lock (about 9 seconds), run the above query on v$libcache_locks, and we can see:

 

 


  
KGLOBJ_NAME
  
SID
  
SADDR
  
EVENT
  
P1
  
P1TEXT
  
P2
  
P2TEXT
  
P3
  
P3TEXT
  
TYPE
  
ADDR
  
HOLDING_USER_SESSION
  
HOLDING_SESSION
  
OBJECT_HANDLE
  
LOCK_HELD
  
REFCOUNT
  
MODE_HELD
  
  
MODE_REQUESTED
  
SAVEPOINT_NUMBER
 

  
EMP(TABLE)
  
304
  
000000018B581078
  
library cache lock
  
13ae68ea0
  
handle address
  
15d317f88
  
lock address
  
14ec9500010003
  
100*mode+namespace
  
LOCK
  
000000015D317F88
  
000000018B581078
  
000000018B581078
  
000000013AE68EA0
  
00
  
0
  
0
  
3
  
17'670
 

  
EMP(TABLE)
  
304
  
000000018B581078
  
library cache lock
  
13ae68ea0
  
handle address
  
15d317f88
  
lock address
  
14ec9500010003
  
100*mode+namespace
  
LOCK
  
0000000164949B70
  
000000018B581078
  
000000018B581078
  
000000013AE68EA0
  
000000015BE24DB0
  
2
  
2
  
0
  
17'658
 

  
EMP(TABLE)
  
304
  
000000018B581078
  
library cache lock
  
13ae68ea0
  
handle address
  
15d317f88
  
lock address
  
14ec9500010003
  
100*mode+namespace
  
PIN
  
000000015BE24DB0
  
000000018B581078
  
000000018B581078
  
000000013AE68EA0
  
0000000164949B70
  
2
  
2
  
0
  
17'658
 

where SID 304 is the test session.

A select on v$wait_chains will also returns the similar info with CHAIN_SIGNATURE: 'library cache lock' (cycle).

In order to list the objects dependencies currently maintained in the library cache (shared pool), run query:

 
SQL > select fobj.name from_name, tobj.to_name
     from v$db_object_cache fobj, v$object_dependency tobj
    where tobj.to_name in ('EMP', 'VC')
      and tobj.from_hash = fobj.hash_value
   order by from_name, to_name;

 FROM_NAME                                          TO_NAME
 -------------------------------------------------- ----------
 LOCK TABLE "EMP" IN EXCLUSIVE MODE  WAIT 37        EMP
 LOCK TABLE "EMP" IN EXCLUSIVE MODE  WAIT 37        EMP
 LOCK TABLE "EMP" IN EXCLUSIVE MODE  WAIT 37        VC
 LOCK TABLE "EMP" IN EXCLUSIVE MODE  WAIT 37        VC
 VC                                                 EMP
 truncate table emp                                 EMP
 truncate table emp                                 EMP
 truncate table emp                                 VC
 truncate table emp                                 VC 

The above dependency diagram shows that "truncate table emp" depends on EMP, so it got a LOCK with MODE_HELD 2 (Share mode)
at SAVEPOINT_NUMBER 17'658. It has two direct dependency on EMP, which is indicated by REFCOUNT 2.
It has also a transitive dependency on EMP over VC, which requires a LOCK with MODE_REQUESTED 3 (Exclusive mode)
at a later SAVEPOINT_NUMBER 17'670.