Denormalize tables to improve cardinality estimate

I was working on the example from an earlier blog post that showed how the optimizer could not correctly estimate the number of rows accessed on a table if the non-join condition was on a different table.  Number of rows = cardinality.  This example from the blog post mirrors a real situation we have where we have a small table joined to a large one and conditions on the small table resulting in incorrect cardinality estimates on the larger table.  Something like this:

select SUM(B.cost)
from DIVISION A,SALES B
where
a.DIVNUM=B.DIVNUM and
A.REGION=’North East’;

The optimizer has no idea how many sales rows are in the North East region because of the join.  Duh! It dawned on me that we just need to denormalize the two tables so that region is part of the sales table.  Like this:

select SUM(B.cost)
from SALES B
where
B.REGION=’North East’;

This seems simple, but the reasons are – at least to me – pretty cool and sophisticated.

To prove all this out I build a test case with the previous blog post as the first part of the script.  First here is the original schema:

create table DIVISION (DIVNAME VARCHAR2(2000),DIVNUM NUMBER);
create table SALES (DIVNUM NUMBER);
create index SALESINDEX on SALES(DIVNUM);

Next, here is the slow query that doesn’t use the index because of the cardinality estimate being way off:

SQL> select B.DIVNUM
  2  from DIVISION A,SALES B
  3  where
  4  a.DIVNUM=B.DIVNUM and
  5  A.DIVNAME='Mayberry';

    DIVNUM
----------
         2

Elapsed: 00:00:00.11

Plan hash value: 480645376

-------------------------------------------------------
| Id  | Operation                  | Name     | Rows  |
-------------------------------------------------------
|   0 | SELECT STATEMENT           |          |       |
|*  1 |  HASH JOIN                 |          |   500K|
|*  2 |   TABLE ACCESS STORAGE FULL| DIVISION |     1 |
|   3 |   TABLE ACCESS STORAGE FULL| SALES    |  1000K|
-------------------------------------------------------

Note that it says it will access 1 million sales rows when it really will access 1.  It uses a full table scan on sales because it thinks we will be accessing a large percentage of the rows.

Here is the new denormalized schema with the two tables merged into one:

create table SALESWITHDIVNAME as
select d.divname,d.divnum
from
SALES s,
DIVISION d
where
s.divnum=d.divnum;

create index SWDNINDEX on SALESWITHDIVNAME(divname);

And here is the faster query which chooses an index:

SQL> select DIVNUM
  2  from SALESWITHDIVNAME
  3  where
  4  DIVNAME='Mayberry';

    DIVNUM
----------
         2

Elapsed: 00:00:00.00

Plan hash value: 447456343

----------------------------------------------------------------
| Id  | Operation                   | Name             | Rows  |
----------------------------------------------------------------
|   0 | SELECT STATEMENT            |                  |       |
|   1 |  TABLE ACCESS BY INDEX ROWID| SALESWITHDIVNAME |     1 |
|*  2 |   INDEX RANGE SCAN          | SWDNINDEX        |     1 |
----------------------------------------------------------------

Notice that the optimizer knows that the query will only access 1 row in the SALESWITHDIVNAME table and so it chooses an index range scan which is more efficient than a full scan when accessing a small percentage of rows from a table.

This may seem simplistic, but the profound fact is that the optimizer can not know which div_num is associated with the DIVNAME=’Mayberry’ condition in the two table query.  It uses the column statistics on DIVISION.DIVNAME to figure out that only one DIVISION row meets the condition.  But, since it doesn’t know that DIVNAME=’Mayberry’ translates into DIVNUM=2 it can’t use the histogram on SALES.DIVNUM to figure out that only one row will be retrieved from SALES.  But, if you merge the two tables together then the histogram on SALESWITHDIVNAME.DIVNAME tells the optimizer it only will access one row and so it should use the index instead of a full scan.

So, this is getting me thinking about the benefits of denormalizing the tables.  Also, maybe if you smash your small tables into your large one you can use multi-column histograms on the various columns you added as well.  In our case we have small division and date dimension tables and a large sales fact table.  What if the query was something like this:

select SUM(cost)
from SALES
where
REGION='North East' and
Quarter='2013Q1';

You might have a multi-column histogram on region and quarter.  You couldn’t have this if the query was normalized like this:

select SUM(cost)
from SALES S,
TIME T,
DIVISION D 
where
D.REGION='North East' and
T.Quarter='2013Q1'and
D.DIVNUM=S.DIVNUM and
T.sdate=s.sdate;

You can’t have a histogram across the three tables but you can across the columns of the one denormalized table.

– Bobby