Re: CBO with Foreign Key

Do you have concrete numbers. It''s been a while that I did my tests for the paper and I would have to dig out my old testcases, but I was left with the impression that the join cardinality "formula" was derived from parent-child relationship joins and that the cardinality estimates are OK for foreign key relationship joins.
for example let's say you have a parent table with 100 (distinct) parents => NDVp = 100; a child table with 1000 children but only 10 distinct parent keys => NDVc = 10. Each child must have a parent, therefore you have 90 childless parents and 10 parents with, on average, 100 children each (you can choose different numbers, it comes out to the same). If you join parent and child on the foreign key you should get all 1000 child rows together with their parent data. The cardinality estimate by the CBO would be:

  join cardinality = CARDp * CARDc * 1/max(NDVp, NDVc) = 100 * 1000 * 1/max(100,10) = 100 * 1000 / 100 = 1000 (= rows(child) as you correctly observed)

The problems I found - and they are shown with the examples in the paper - come when you do not have a parent-child relationship, either you have rows in both tables which do not have a match in the joined table, or if you have a many-to-many relationship.

But maybe I am missing something ( wouldn't be the first time).

At 02:19 PM 10/16/2003, you wrote:
>Is there any way to get the CBO (8.1.7) to recognize parent/child
>relationships? This seems to be an extreme example of the Join Independence
>Assumption Fallacy (or I guess maybe the Predicate Independence Assumption)
>discussed by Wolfgang Breitling in "Fallacies of the Cost Based Optimizer".
>If I am joining a parent and child table (parent PK [a,b]), Oracle assumes a
>resulting cardinality of :
>rows(parent)*rows(child)/{max(NDV[parent.a],NDV[child.a])*max(NDV[parent.b],
>NDV[child.b])}.
>
>This is assuming independence of field a and b. However, since they make up
>the PK of the parent, the denomenator is actually rows(parent) so the actual
>cardinality is rows(child). This causes the CBO to dramatically
>underestimate the join cardinality. If this is part of a multi-table join
>the entire execution plan can be thrown way off.
>
>I would assume that since the FK constraint is part of the data dictionary,
>Oracle would find a way to use this information. I checked by running
>autotraces with and without the FK, but the plan remained unchanged.
>
>Any suggestions?
>
>Thanks.
>
>Henry
>--
>Author: Henry Poras
> INET: hporas_at_etal.uri.edu

Wolfgang Breitling
Oracle7, 8, 8i, 9i OCP DBA
Centrex Consulting Corporation
http://www.centrexcc.com

-- 
Please see the official ORACLE-L FAQ: http://www.orafaq.net
-- 
Author: Wolfgang Breitling
  INET: breitliw_at_centrexcc.com

Fat City Network Services    -- 858-538-5051 http://www.fatcity.com
San Diego, California        -- Mailing list and web hosting services
---------------------------------------------------------------------
To REMOVE yourself from this mailing list, send an E-Mail message
to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
the message BODY, include a line containing: UNSUB ORACLE-L
(or the name of mailing list you want to be removed from).  You may
also send the HELP command for other information (like subscribing).