Skip to Main Content
  • Questions
  • Slow query because the cardinality estimate is wrong for joins on foreign keys

Breadcrumb

more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's latest video and Chris's latest video from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.

Question and Answer

Chris Saxon

Thanks for the question, Valer.

Asked: July 01, 2016 - 11:21 pm UTC

Answered by: Chris Saxon - Last updated: July 06, 2016 - 11:50 pm UTC

Category: Database - Version: 12c

Viewed 1000+ times

Whilst you are here, check out some content from the AskTom team: Partitioning Guide updated

You Asked

While investigating a very slow query in our OLTP db, I noticed that Oracle severly under estimates the cardinality for joins that are on foreign key. The following script replicates the issue.

create table A (part number not null, rec number not null, d varchar2(50), primary key (part, rec));
create table B (part number not null, rec number not null, t1_rec number not null, d varchar2(50), primary key (part, rec));
alter table B add constraint fkB_A foreign key (part, t1_rec) references A (part, rec);

begin
for i in 1..170 loop
insert into A values (i, mod(i, 17), 'a' || i);
insert into A values (i, mod(i, 17) + 20, 'aa' || i);
insert into A values (i, mod(i, 17) + 40, 'a' || i);
insert into A values (i, mod(i, 17) + 60, 'a' || i);
end loop;
end;
/

begin
for i in 1..17*230 loop
insert into B values (mod(i, 170) + 1, i, mod(mod(i, 170) + 1, 17), 'a' || i);
end loop;
end;
/

commit;

exec dbms_stats.gather_table_stats(null, 'A');
exec dbms_stats.gather_table_stats(null, 'B');

explain plan for select * from A, B where A.part = 5 and A.part = B.part and A.rec = B.t1_rec;


My script creates a parent (A) and child (B) table which are joined through a complex foreign key on 2 columns.
Next I insert some data into both tables, such that the data is balanced. After that I update the table stats.
Finally I run a query that joins A & B on the foreign key columns and filters one of the column by a value.

Oracle comes up with the plan below. The estimate on Ids 3, 4 & 5 is right on, but then, IMO, the cardinality estimate on the HASH JOIN is wrong, because the tables are in parent to child relationship the actual number of rows is equal to the number of rows fetched from the child table. That is 23.

------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 7 | 189 | 17 (0)| 00:00:01 |
|* 1 | HASH JOIN | | 7 | 189 | 17 (0)| 00:00:01 |
| 2 | TABLE ACCESS BY INDEX ROWID BATCHED| A | 4 | 44 | 3 (0)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | SYS_C00403559 | 4 | | 2 (0)| 00:00:01 |
| 4 | TABLE ACCESS BY INDEX ROWID BATCHED| B | 23 | 368 | 14 (0)| 00:00:01 |
|* 5 | INDEX RANGE SCAN | SYS_C00403563 | 23 | | 2 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

1 - access("A"."PART"="B"."PART" AND "A"."REC"="B"."T1_REC")
3 - access("A"."PART"=5)
5 - access("B"."PART"=5)



Why is this an issue for us? In our OLTP system we have multiple transaction tables and multiple dimension/satellite tables. Often the reporting queries join 2+ transaction tables and a larger number of dimensions. Because of this under-estimate of cardinality, Oracle chooses plans that would do Nested Loop joins in the order: Trx 1 -> dimension 1 -> dimmension 2 -> ... dimension n -> Trx2 -> dimension n+1 -> ...
That's on the assumption that even though it fetches a large number of rows from Trx 1 table, the joins with its dimensions will reduce the rows to a small number (usually the plans show 2 and 1 rows) so then it is OK to do a Nested Loop of that branch with the second Trx table. Of course, the reality is different, the joins with dimensions don't reduce the data at all!

Is there anything we could do at DB layer to improve these estimates?



and we said...

The number of rows returned from the child gives an upper bound for the total rows. But in the general case it's not guaranteed that num rows returned from hash join = num rows returned from child table.

Filtering on the parent could result in fewer rows than this!

For example, using your setup:

- For part = 5, there is one row in A where d = 'aa5'
- But there are no matching rows in B for this parent!

select /*+ gather_plan_statistics */* from A, B 
where  A.part = 5 and A.part = B.part and A.rec = B.t1_rec
and    a.d = 'aa5'; 

select * from table(dbms_xplan.display_cursor(null, null, 'IOSTATS LAST'));

-------------------------------------------------------------------------------------------------------                                                         
| Id  | Operation                    | Name         | Starts | E-Rows | A-Rows |   A-Time   | Buffers |                                                         
-------------------------------------------------------------------------------------------------------                                                         
|   0 | SELECT STATEMENT             |              |      1 |        |      0 |00:00:00.01 |      19 |                                                         
|*  1 |  HASH JOIN                   |              |      1 |      1 |      0 |00:00:00.01 |      19 |                                                         
|*  2 |   TABLE ACCESS BY INDEX ROWID| A            |      1 |      1 |      1 |00:00:00.01 |       3 |                                                         
|*  3 |    INDEX RANGE SCAN          | SYS_C0024994 |      1 |      4 |      4 |00:00:00.01 |       2 |                                                         
|*  4 |   TABLE ACCESS FULL          | B            |      1 |     23 |     23 |00:00:00.01 |      16 |                                                         
-------------------------------------------------------------------------------------------------------

There's 23 rows returned from B. But these don't match to any rows in A! So the whole query returns nothing. 23 rows for the hash join in this case is an overestimate.

In cases like this you could look at SQL profiles to improve the estimates:

https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:61313086268493
https://docs.oracle.com/database/121/TGSQL/tgsql_profiles.htm

Or SQL Plan Management (baselines) to lock queries to a particular execution plan:

http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-sql-plan-management-11gr2-133099.pdf
https://oracle-base.com/articles/11g/sql-plan-management-11gr1

and you rated our response

  (1 rating)

Is this answer out of date? If it is, please let us know via a Review

Reviews

July 06, 2016 - 7:03 pm UTC

Reviewer: A reader

I understand that the estimate should be different if there are extra predicates on the parent table. At the same time your example is an extreme, caused by the fact that my load scripts had a defect, so the data was skewed in table B instead of being balanced.

Let's correct the skewing by running this script for table B instead:
begin
for i in 1..17*230 loop
insert into B values (mod(i, 170) + 1, i, mod(mod(i, 170) + 1, 17), 'a' || i);
insert into B values (mod(i, 170) + 1, i + 4600, mod(mod(i, 170) + 1, 17) + 20, 'a' || i);
insert into B values (mod(i, 170) + 1, i + 2 * 4600, mod(mod(i, 170) + 1, 17) + 40, 'a' || i);
insert into B values (mod(i, 170) + 1, i + 4 * 4600, mod(mod(i, 170) + 1, 17) + 60, 'a' || i);
end loop;
end;
/

Now, it is obvious that the estimate is wrong.

SQL> select * from A, B where A.part = 5 and A.part = B.part and A.rec = B.t1_rec and a.d = 'aa5'; 

23 rows selected.
-------------------------------------------------------------------------------------------------------
| Id  | Operation                            | Name           | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                |     1 |    27 |    20   (0)| 00:00:01 |
|*  1 |  HASH JOIN                           |                |     1 |    27 |    20   (0)| 00:00:01 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| A              |     1 |    11 |     3   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN                  | SYS_C004190833 |     4 |       |     2   (0)| 00:00:01 |
|*  4 |   TABLE ACCESS FULL                  | B              |    92 |  1472 |    17   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------------

Chris Saxon

Followup  

July 06, 2016 - 11:50 pm UTC

Even with balanced data, the moment you have multiple columns/predicates in play, there are challenges for the optimizer

consider two columns

BIRTHDAY_MONTH
STAR_SIGN

Based on the standard population, the columns are balanced, each with 12 distinct values, and each value containing 100/12 =8.5% of the data.

But the predicate:

where birthday_month = 'January' and star_sign = 'Aquarius'

returns 8% of the data, whereas

where birthday_month = 'March' and star_sign = 'Aquarius'

returns 0% of the data.

So should the optimizer estimate 0 or 8 % ? In this simple example, we can use column grouping statistics (extended statistics) to help out, but you can see the challenge faced when (say) those columns are part of join conditions.

More to Explore

DBMS_XPLAN

More on PL/SQL routine DBMS_XPLAN here