Hi Tom:

I am having a mental block trying to understand the terms cardinality and selectivity as applied to a table and an index.
Any explanation or pointers to existing doc/ref material will be greatly appreciated. An example from you usually is right on the mark and will be greatly appreciated. I searched the archives but could not find anything on this subject and this thread was the closest you came to explaining these terms.

Thanks a 10**6

I found that in many simple cases the join selectivity formula given in note 68992.1 leads to the number seen in the 10053 trace. However, in many cases, especially more complex ones, it seems obvious that the cbo uses other formulas. Just as it does for other selectivity formulas (e.g. the one for range selectivities). I can give the following real example, slightly simplified to fit in 1000 words. All the pieces are from the same 10053 trace.
This is the sql. I left out the list of select columns, the group by and order by clause and any non-join predicates:
SELECT ...
from PS_PAY_CALENDAR A
, PS_JOB B
, PS_RETROPAY_EARNS C
, PS_RETROPAY_RQST D
, PS_RETROPAYPGM_TBL E
where B.COMPANY=A.COMPANY
and B.PAYGROUP=A.PAYGROUP
and C.EMPLID=B.EMPLID
and C.EMPL_RCD#=B.EMPL_RCD#
and D.RETROPAY_SEQ_NO=C.RETROPAY_SEQ_NO
and E.RETROPAY_PGM_ID=D.RETROPAY_PGM_ID
and E.OFF_CYCLE=A.PAY_OFF_CYCLE_CAL

The following table lists the column NDVs, 1/NDVs and 1/max(NDV):
NDV1 NDV2 1/NDV1 1/NDV2 1/max(NDV1,NDV2)
B.COMPANY A.COMPANY 10 11 1.0000E-01 9.0909E-02 9.0909E-02
B.PAYGROUP A.PAYGROUP 14 15 7.1429E-02 6.6667E-02 6.6667E-02
C.EMPLID B.EMPLID 12328 41639 8.1116E-05 2.4016E-05 2.4016E-05
C.EMPL_RCD# B.EMPL_RCD# 1 1 1.0000E+00 1.0000E+00 1.0000E+00
D.RETROPAY_SEQ_NO C.RETROPAY_SEQ_NO 13679 14532 7.3105E-05 6.8814E-05 6.8814E-05
E.RETROPAY_PGM_ID D.RETROPAY_PGM_ID 15 14 6.6667E-02 7.1429E-02 6.6667E-02
E.OFF_CYCLE A.PAY_OFF_CYCLE_CAL 1 2 1.0000E+00 5.0000E-01 5.0000E-01

There is a difference in how join selectivity is calculated for ps_job (alias B) depending where in the join order it is:

Join order[2]: PS_PAY_CALENDAR [ A] PS_RETROPAYPGM_TBL [ E] PS_RETROPAY_RQST [ D] PS_JOB [ B] PS_RETROPAY_EARNS [ C]
Now joining: PS_RETROPAYPGM_TBL [ E] *******
Join cardinality: 45 = outer (6) * inner (15) * sel (5.0000e-001) [flag=0]
Now joining: PS_RETROPAY_RQST [ D] *******
Join cardinality: 41037 = outer (45) * inner (13679) * sel (6.6667e-002) [flag=0]
Now joining: PS_JOB [ B] *******
Join cardinality: 79458326 = outer (41037) * inner (319483) * sel (6.0606e-003) [flag=0]
Now joining: PS_RETROPAY_EARNS [ C] *******
Join cardinality: 31403 = outer (79458326) * inner (239142) * sel (1.6526e-009) [flag=0]
All selectivities are as expected: 1/A.PAY_OFF_CYCLE_CAL, 1/E.RETROPAY_PGM_ID, 1/A.COMPANY * 1/A.PAYGROUP, and 1/B.EMPLID * 1/B.EMPL_RCD# * C.RETROPAY_SEQ_NO

But later on the cbo comes up with these selectivities:
Join order[10]: PS_PAY_CALENDAR [ A] PS_RETROPAY_RQST [ D] PS_JOB [ B] PS_RETROPAYPGM_TBL [ E] PS_RETROPAY_EARNS [ C]
Now joining: PS_RETROPAY_RQST [ D] *******
Join cardinality: 82074 = outer (6) * inner (13679) * sel (1.0000e+000) [flag=0]
Now joining: PS_JOB [ B] *******
Join cardinality: 187294627 = outer (82074) * inner (319483) * sel (7.1429e-003) [flag=0]
Now joining: PS_RETROPAYPGM_TBL [ E] *******
Join cardinality: 93647314 = outer (187294627) * inner (15) * sel (3.3333e-002) [flag=0]

There is no join predicate between tables A and D, so the first selectivity is 1. The second should be 1/A.COMPANY * 1/A.PAYGROUP = 6.0606e-003 as before, but it is 7.1429e-003 which seems to be 1/B.COMPANY * 1/B.PAYGROUP. The 3rd one follows the formula again: 1/E.RETROPAY_PGM_ID * 1/A.PAY_OFF_CYCLE_CAL. There is no selectivity for joining C because pruning kicked in.

Looking at all the permutations in the trace and the corresponding join selectivities, the difference appears to be related to the position of tables B and E in the join order. If E precedes B then the expected formula is used. If B precedes E then not.
Any comments

I agree, to a degree. I became interested in the CBO's selectivity calculations trying to understand why it comes up with some of the ridiculously low cardinality estimates ( like 1 when in reality there are 80,000+ ) which then lead to disastrous access plans that take hours, provided they finish at all, instead of minutes or seconds.

I didn't really expect an explanation. I mostly wanted to point out that the CBO and its estimation engine are a very complex pieces of software and the rules and calculations that are pseudo-documented, as you say, in notes are applicable verbatim only in basic and simple cases. Also, as you said, things change and some of the notes are several years old, probably written in Oracle 7 days. Some e.g. 104817.1 "Discussion on Oracle Joins - Costs - Algorithms & Hints" are getting pulled "due to problems with the content found during review" according to Helen Schoone in a recent response on metalink.

Tom,

It is obvious that CBO selectivity estimation does wonders if two sets are highly related or one is completely included into another. 

I have a very different situation. Two sets have only very small intersection portion.

My tests show that using smaller table as a left input in nested loops gives better performance than using hash join.

Not to mention that the estimated join cardinality is much higher than the actual one.

Could you share your thoughts on this matter?

Thanks,

- Vlad

drop table t1;
create table t1 as select * from all_objects;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
insert /*+ append */ into t1 select * from t1;
commit;
drop sequence s1;
create sequence s1;
update t1 set object_id=s1.nextval;
commit;
create unique index t1_idx1 on t1(object_id);
exec dbms_stats.gather_table_stats(null,'t1',method_opt=> -
'for all indexed columns size auto', cascade => true);

col next_id new_va next_id
select max(object_id)+1 next_id
from t1;

drop table t2;
create table t2 as 
select * from t1
where rownum <= &next_id*.2;
drop sequence s1;
create sequence s1 start with &next_id;

rem updating table t2 and leaving very small amount of common values (i.e. about .5%).
update t2 set object_id = s1.nextval where rownum <= &next_id*.2*.995;
create unique index t2_idx1 on t2(object_id);
exec dbms_stats.gather_table_stats(null,'t2',method_opt=> -
'for all indexed columns size auto', cascade => true);

Queries and results:
SQL> set timi on
SQL> set autotrace traceonly
SQL> select * from t1 where object_id in
  2  (select object_id from t2);

11619 rows selected.

Elapsed: 00:01:01.95

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=94459 Card=2349084
           Bytes=227861148)
   1    0   HASH JOIN (Cost=94459 Card=2349084 Bytes=227861148)
   2    1     INDEX (FAST FULL SCAN) OF 'T2_IDX1' (INDEX (UNIQUE)) (Co
          st=1150 Card=2330297 Bytes=13981782)
   3    1     TABLE ACCESS (FULL) OF 'T1' (TABLE) (Cost=33942 Card=116
          84926 Bytes=1063328266)

Statistics
----------------------------------------------------------
        243  recursive calls
          0  db block gets
     158767  consistent gets
     122535  physical reads
          0  redo size
     691016  bytes sent via SQL*Net to client
       9026  bytes received via SQL*Net from client
        776  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
      11619  rows processed

SQL>
SQL> select * from t1 where object_id in
  2  (select /*+ cardinality(t2 10000) */ object_id from t2);

11619 rows selected.

Elapsed: 00:00:08.57

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=11208 Card=10081 B
          ytes=977857)
   1    0   NESTED LOOPS (Cost=11208 Card=10081 Bytes=977857)
   2    1     INDEX (FAST FULL SCAN) OF 'T2_IDX1' (INDEX (UNIQUE)) (Co
          st=1150 Card=10000 Bytes=60000)
   3    1     TABLE ACCESS (BY INDEX ROWID) OF 'T1' (TABLE) (Cost=2 Ca
          rd=1 Bytes=91)
   4    3       INDEX (UNIQUE SCAN) OF 'T1_IDX1' (INDEX (UNIQUE)) (Cos
          t=1 Card=1)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
    4665690  consistent gets
          0  physical reads
          0  redo size
     582269  bytes sent via SQL*Net to client
       9026  bytes received via SQL*Net from client
        776  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
      11619  rows processed

SQL> 

Tom,

Do you mean Cost based Oracle vol 1? I'll try it out. Thanks.

autotrace dosn't show sorts (???), but indeed 10046 trace shows that most of the time in hash join spent on direct writing and direct reading and scattered reading (about 15sec per each operation).

I was mostly consearned about incorrect final cardinality of the join not the performance. It negatively affects CBO in its consequent decisions. 

Your argument about performance of NLs in fact is very interesting to me. On the other hand, it doesn't justify CBO's poor calculations. Following test shows CBO can choose NL plan that cause even more LIOs than were in the first test.

Thanks in advance for your time,

- Vlad

col next_id new_va next_id
select max(object_id)+1 next_id
from t1;
drop table t3;
create table t3 as 
select * from t1
where rownum <= &next_id*.02;
create unique index t3_idx1 on t3(object_id);
exec dbms_stats.gather_table_stats(null,'t3',method_opt=> -
'for all indexed columns size auto', cascade => true);

SQL> select t1.* from t1,t3
  2  where t1.object_id=t3.object_id;

232366 rows selected.

Elapsed: 00:01:16.32

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=48718 Card=233658
          Bytes=22431168)

   1    0   NESTED LOOPS (Cost=48718 Card=233658 Bytes=22431168)
   2    1     TABLE ACCESS (FULL) OF 'T1' (TABLE) (Cost=33942 Card=116
          84926 Bytes=1063328266)

   3    1     INDEX (UNIQUE SCAN) OF 'T3_IDX1' (INDEX (UNIQUE)) (Cost=
          0 Card=1 Bytes=5)

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
   11802422  consistent gets
      99837  physical reads
          0  redo size
   11172497  bytes sent via SQL*Net to client
     170913  bytes received via SQL*Net from client
      15493  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     232366  rows processed
     
SQL> select /*+ use_hash(t1 t3) */ t1.* from t1,t3
  2  where t1.object_id=t3.object_id;

232366 rows selected.

Elapsed: 00:00:51.53

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=91571 Card=233658
          Bytes=22431168)

   1    0   HASH JOIN (Cost=91571 Card=233658 Bytes=22431168)
   2    1     INDEX (FAST FULL SCAN) OF 'T3_IDX1' (INDEX (UNIQUE)) (Co
          st=109 Card=231789 Bytes=1158945)

   3    1     TABLE ACCESS (FULL) OF 'T1' (TABLE) (Cost=33942 Card=116
          84926 Bytes=1063328266)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
     169116  consistent gets
      99840  physical reads
          0  redo size
   11172497  bytes sent via SQL*Net to client
     170913  bytes received via SQL*Net from client
      15493  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     232366  rows processed