Problem grasping the definitions of selectivity and cardinality
A reader, November 01, 2002 - 10:09 am UTC
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
November 01, 2002 - 3:42 pm UTC
selectivity is a measure of how "selective" something is (oh good -- I start with a recursive definition...).. Take the ALL_OBJECTS view for example, suppose you:
create table t as select * from all_objects where owner in ( 'SYS', 'SYSTEM' );
create index t_idx1 on t(object_id);
create index t_idx2 in t(owner);
The index t_idx1 will be very "selective" in general. object id is a very selective column in T (in fact it is UNIQUE). Using that index for a given object_id = :n will return 1 record.
The index t_idx2 on the other hand is not very "selective". owner has but two values -- using that index for a given OWNER = :n will return LOTS of records.
Hence t_idx1 is a selective index, t_idx2 is a non-selective index. The selectivity of t_idx1 is better then t_idx2....
cardinality is the number of elements in something (eg: if select count(*) from t returns 1000 -- the cardinality of T is 1000, it has 1000 rows).
selectivity of a join is computed based on number of distinct values ( NDV ) and cardinalities of the underlying columns.
Join selectivity
Wolfgang Breitling, November 02, 2002 - 2:29 am UTC
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
November 02, 2002 - 8:21 am UTC
comments are: I get headaches looking at traces like this. Personally -- I have so very very very rarely ever used 10053 traces (i mean -- only when forced by others to use them). I generally send them onto the guys who wrote them for interpretation.
Things change -- algorithms change -- I wish we didn't even "psuedo document" via support notes what you might expect to find in these things.
I guess I'm sort of saying "to me, it is not relevant.... To support or development in order to fix a bug, it would be super relevant. There are so many bigger fish to fry..."
Wow, that was quick
Wolfgang Breitling, November 02, 2002 - 10:52 am UTC
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.
How to deal with overestimated selectivity?
Vladimir Sadilovskiy, October 09, 2005 - 3:20 pm UTC
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>
October 09, 2005 - 4:12 pm UTC
my thoughts are that you'll be very interested in the new book by Jonathan Lewis that should be out in about one month...
But I can say that in single user mode, that nested loop might win because the latches required to get the data are "almost free", but take this into multi-user and the latches you need for each consistent get - will become a bottleneck.
The physcial IO in the hash join should be looked at - was it due to reading the table data, was it due to reads from temp? Could it have been avoided.
What about the final cardinality?
Vladimir Sadilovskiy, October 09, 2005 - 8:53 pm UTC
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