Database, SQL and PL/SQL

On Clustering Factor and Validating Keys

Our technologist explains different statistics and very foreign keys.

By Tom Kyte Oracle Employee ACE

September/October 2012

I created the following table and index to see the clustering factor, and I have a few questions.

create table t (a number);
insert into t (a)
with data (r)
(select 1 r from dual
union all
select r+1 from data where r+1 <= 10000000
select * from data
create index t_idx on t(a);
exec dbms_stats.gather_table_stats( user, 'T' );

When I query USER_INDEXES, I find that the number of LEAF_BLOCKS is 2,226 and the CLUSTERING_FACTOR is 1,516. If I drop that table, re-create it with a CHAR(8) datatype, and create the same index, I find that the number of LEAF_BLOCKS is 27,856 and the clustering factor has increased to 1,916,062.

Can you please tell me why CLUSTERING_FACTOR is so different between the two tables, given that they contain the same data—just in different datatypes?

Before I answer this, I’d like to explain the meaning and importance of the clustering factor statistic. This statistic is used by the optimizer during query optimization to determine the relative efficiency of an index. In short, the index clustering factor is a measure of how many I/Os the database would perform if it were to read every row in that table via the index in index order. If the rows of a table on disk are sorted in about the same order as the index keys, the database will perform a minimum number of I/Os on the table to read the entire table via the index. That is because the next row needed from an index key would likely be the next row in the table block as well. The query would not be skipping all over the table to find row after row—they are naturally next to each other on the block. Conversely, if the rows in the table are not in the same order on disk as the index keys—if the data is scattered—the query will tend to perform the maximum number of I/Os on the table, as many as one I/O for every row in the table. That is because as the database scans through the index, the next row needed will probably not be on the same block as the last row. The database will have to discard that block and get another block from the buffer cache. The query will end up reading every block from the buffer as many times as it has rows on it.

So if a table and an index key are in about the same order, the clustering factor will be near the number of blocks in the table and the index will be useful for very large index range scans and for retrieving numerous rows from the table. On the other hand, if the data is randomly scattered, the clustering factor will be near the number of rows in the table, and given that the number of rows in a table is usually at least an order of magnitude more than the number of blocks, the index will be less efficient for returning numerous rows. For example, if a table is 100 blocks in size and has 100 rows per block, an index with a clustering factor of 100 (near the number of blocks) will perform about 2 I/Os against the table to retrieve 200 rows. That is because when the database reads the first table block to get row #1, rows 2–100 are probably on that same block, so the query will be able to get the first 100 rows by reading the table block once. The process will be similar for rows 101–200. If the index has a clustering factor of 10,000—the number of rows in the table—the number of I/Os required against the table will be approximately 200, even though there are only 100 blocks! That is because the first row in the index will be on a different block than the second row, which, in turn, will be on a different block than the third row, and so on—the database will probably never be able to get more than one row from a table block at a time.

This is easy to observe. I’m going to take a copy of ALL_OBJECTS and put it into two tables. The STAGE table I am using is simply a copy of ALL_OBJECTS for starters:

SQL> create table organized
  2  as
  3  select x.*
  4    from (select * from stage 
             order by object_name) x
  5  /
Table created.
SQL> create table disorganized
  2  as
  3  select x.*
  4    from (select * from stage 
          order by dbms_random.random) x
  5  /
Table created.

Note that when I created these two tables, I used an ORDER BY statement. In the case of the first table, I sorted the data by OBJECT_NAME before loading it into the table. If I were to do a full table scan on the ORGANIZED table, the OBJECT_NAME column would be more or less sorted on the screen even without an ORDER BY (but you need the ORDER BY in the query if you want the data to be sorted). During the creation of the DISORGANIZED table, on the other hand, I sorted by a random value—I just scrambled the data. If I were to do a full table scan on that table, the OBJECT_NAME values would come out in an arbitrary order—I might see an object starting with the letter N first, then Z, then A, then Q, then B, then Z again, and so on.

Now I’ll index and gather statistics on these two tables and look at the statistics, as shown in Listing 1.

Code Listing 1: Creating indexes, generating statistics, and viewing information

SQL> create index organized_idx on organized(object_name);
Index created.
SQL> create index disorganized_idx on disorganized(object_name);
Index created.
SQL> begin
  2  dbms_stats.gather_table_stats
  3  ( user, 'ORGANIZED',
  4    estimate_percent => 100,
  5    method_opt=>'for all indexed columns size 254'
  6  );
  7  dbms_stats.gather_table_stats
  8  ( user, 'DISORGANIZED',
  9    estimate_percent => 100,
 10    method_opt=>'for all indexed columns size 254'
 11  );
 12  end;
 13  /
PL/SQL procedure successfully completed.
SQL> select table_name, blocks, num_rows from user_tables
  2  where table_name like '%ORGANIZED' order by 1;
————————————————  ———————  ——————— 
DISORGANIZED      1064     72839  
ORGANIZED         1064     72839  
SQL> select table_name, index_name, clustering_factor 
  2  from user_indexes
  3  where table_name like '%ORGANIZED' order by 1;
——————————————  ——————————————   ————————————————
ORGANIZED       ORGANIZED_IDX                1038

As you can see in Listing 1, both tables have the same number of rows and the same number of blocks. That is expected—they contain exactly the same rows, just in a different order. But when I look at the clustering factor, I see a large difference between the two. The ORGANIZED index has a clustering factor very near the number of blocks in the table, whereas the DISORGANIZED index has a clustering factor near the number of rows in the table. Again, this clustering factor metric is a measure of how many I/Os the database will perform against the table in order to read every row via the index. I can verify this fact by executing a query with tracing enabled that will, in fact, read every row of the table via the index. I’ll do that by using an index hint to force the optimizer to use my index and count the non-null occurrences of a nullable column that is not in the index. That will force the database to go from index to table for every single row:

SQL> select /*+ index( organized 
organized_idx) */
  2    count(subobject_name)
  3    from organized;
SQL> select /*+ index( disorganized 
disorganized_idx) */
  2    count(subobject_name)
  3    from disorganized;

Reviewing the TKPROF report for reading every row via the index, I discover the results in Listing 2.

Code Listing 2: Information on index scans on both tables

select /*+ index( organized organized_idx) */
 from organized
Row Source Operation
SORT AGGREGATE (cr=1401 pr=1038 pw=0 time=307733 us)
 TABLE ACCESS BY INDEX ROWID ORGANIZED (cr=1401 pr=1038 pw=0 tim...
  INDEX FULL SCAN ORGANIZED_IDX (cr=363 pr=0 pw=0 time=53562 ...
select /*+ index( disorganized disorganized_idx) */
 from disorganized
Row Source Operation
SORT AGGREGATE (cr=73123 pr=1038 pw=0 time=535990 us)
  INDEX FULL SCAN DISORGANIZED_IDX (cr=363 pr=0 pw=0 time=47207 us …

As you can see in Listing 2, I performed 363 I/Os for the ORGANIZED table against the index (cr=363 in the INDEX FULL SCAN ORGANIZED_IDX row source), and if I subtract 363 from the 1,401 total I/Os performed by the query, I’ll get 1,038, which is exactly the clustering factor of this index. Similarly, if I do the same analysis on the DISORGANIZED index, I’ll see 73,123 – 363 = 72,760 I/Os against the table, again the clustering factor of that index.

So, for one table, the database performs 1,401 total I/Os to retrieve exactly the same data as for the other table—which needed 73,123 I/Os.

Obviously, one of these indexes is going to be more useful for retrieving a larger number of rows than the other. If I am going to read more than 1,038 blocks of the table via the index, I certainly should be doing a full table scan instead of using an index. I can observe this fact as well, by using autotrace on a few queries against both tables, as shown in Listing 3.

Code Listing 3: Comparing costs of using an index on two tables

SQL> select * from organized where object_name like 'F%';
| Id  | Operation                   | Name          | Rows | Bytes | Cost  |
|   0 | SELECT STATEMENT            |               |  149 | 14602 |    6  |
|   1 |  TABLE ACCESS BY INDEX ROWID| ORGANIZED     |  149 | 14602 |    6  |
|*  2 |   INDEX RANGE SCAN          | ORGANIZED_IDX |  149 |       |    3  |
SQL> select * from disorganized where object_name like 'F%';
| Id  | Operation                   | Name             | Rows | Bytes | Cost |
|   0 | SELECT STATEMENT            |                  |  149 | 14602 |  152 |
|   1 |  TABLE ACCESS BY INDEX ROWID| DISORGANIZED     |  149 | 14602 |  152 |
|*  2 |   INDEX RANGE SCAN          | DISORGANIZED_IDX |  149 |       |    3 |

As you can see in Listing 3, both plans expect to return the same number of rows: 149. Both plans are using an index range scan. But the two plans have radically different costs: one has a low cost of 6 and the other a much higher cost of 152—even though both plans are going after exactly the same set of rows from two tables that contain the same data! The reason for the cost difference is easy to explain: the optimizer computes the cost column value as a function of the number of expected I/Os and the CPU cost. For this simple query, the CPU cost is negligible, so most of the cost is simply the number of I/Os. Walking through the first plan, I see there is a cost of 3 for using the index for the ORGANIZED table and index—about three I/Os against the index, which makes sense. The query will hit the root block, branch, and probably the leaf block. Then the query will be doing about three more I/Os against the table, because the rows needed are all next to each other on a few database blocks, for a total cost of 6. The DISORGANIZED index, on the other hand, does the math a little differently. The plan still has the same three I/Os against the index—that won’t change—but because the rows needed from the table are not next to each other, the optimizer estimates that the query will have to perform an I/O against the table for every row it retrieves, and its estimated cost for 149 rows is 149 rows + 3 I/Os = 152.

If I change the query slightly, I can see what kind of effect this might have on the query plans shown in Listing 4.

Code Listing 4: Changing queries, changing costs

SQL> select * from organized where object_name like 'A%';
| Id  | Operation                   | Name          | Rows  | Bytes | Cost |
|   0 | SELECT STATEMENT            |               |  1825 |  174K |   39 |
|   1 |  TABLE ACCESS BY INDEX ROWID| ORGANIZED     |  1825 |  174K |   39 |
|*  2 |   INDEX RANGE SCAN          | ORGANIZED_IDX |  1825 |       |   12 |
SQL> select * from disorganized where object_name like 'A%';
| Id  | Operation         | Name         | Rows  | Bytes | Cost |
|   0 | SELECT STATEMENT  |              |  1825 |  174K |  291 |
|*  1 |  TABLE ACCESS FULL| DISORGANIZED |  1825 |  174K |  291 |

As you can see in Listing 4, the estimated row count has jumped to 1,825 and the ORGANIZED table will still use the index. The cost of the query is 39 – 12 I/Os estimated against the index for the range scan and 27 more I/Os against the table. That makes sense, because the ALL_OBJECTS rows’ size means that about 70 or so fit on a database block—it would take about 27 blocks to hold 1,825 rows. When I look at the DISORGANIZED table, I see that it gets the same estimated row counts but that the plan is totally different. The optimizer chose not to use an index but instead to do a full table scan. What would the cost of using the index have been? I know from the result in Listing 4 that the cost of the index step (INDEX RANGE SCAN) would be 12, and given that the clustering factor of the index is near the number of rows in the table, I can assume that every row I need to retrieve will require an I/O. So, the query would need to perform 1,825 I/Os against the table, for a total query cost of 1,837—it would be less expensive to do a full table scan.

In fact, I have enough information to figure out when the optimizer would stop using this index. I know that the cost of a full table scan is 291, and I know that the cost of a query plan that uses an index against this table would be at least equal to the number of estimated rows plus the cost of the query. So if the query is getting around 285 rows, the cost of using the index would probably be around 5 or 6, the cost of the table access would be about 291, and the full table and index scan costs would be tied. Any cost above an estimated row count of 285 would cause the optimizer to do a full table scan. The cost of getting thousands of rows from the organized table is less than the cost of getting a few hundred from the disorganized table. And the clustering factor is what reports that cost, in general, for the index range scan.

So, now that you know what a clustering factor is and why you might care about it, I can address the original question. Why did the two tables—one created with a NUMBER and the other a CHAR(8)—have such different clustering factors? The data in both tables is in exactly the same order on disk—so the tables should presumably have the same clustering factor, shouldn’t they?

No, they won’t—and they can’t—for two reasons.

First, which table do you think is larger, the NUMBER implementation or the CHAR(8) implementation? I see that the number of index leaf blocks is more in the CHAR index than in the NUMBER index (storing a number in a CHAR or VARCHAR2 is always a bad idea, for many reasons—space being one of them).

The table with the CHAR(8) column is much larger than the table with the NUMBER column. And the clustering factor is, by definition, the number of I/Os that would be performed in order to read the entire table via the index in a single range scan, and the number of I/Os has to be at least the number of blocks in the table, reasonably assuming that more than one row exists per block.

So it would logically follow that if one table is much larger than another table, the clustering factor of the larger table has to be larger than the clustering factor of the smaller table.

That accounts for part of the issue here—the CHAR(8) table is obviously larger and hence would increase the clustering factor. But it doesn’t account for all of it. To see the rest, you need to look at the data.

The person posting the question believes he loaded two tables with the same data—stored once (properly) as a NUMBER and stored again (totally wrong) as a string. But he didn’t—he has two entirely different sets of data! Consider the following:

SQL> with data (r)
  2  as
  3  (select 1 r from dual union all 
  4     select r+1 from data 
  5       where r<= 1000 )
  6  select * from data 
  7  order by to_char(r);
Look at that: 1, 10, 100, 1000 . . . are returned first. The data in the index would have 1, 10, 100, and 1000 first. Well, in order to process that first leaf block, how many I/Os against the table would the query have to perform? Remember, the data in the table is 1, 2, 3, 4, 5. . . . The table is ordered numerically, because the data was generated in numeric order, and the index is ordered with character strings. A number value in a character string sorts entirely differently than a number value in a NUMBER datatype.

So, this accounts for the second issue: The data in the table is not sorted in the same fashion as the data in the index! By definition, that will pretty much increase the clustering factor.

The clustering factor is higher in the CHAR(8) table because

  • The table used a lot more space, making the lowest-possible clustering factor much higher
  • The table was loaded in an unsorted fashion, so the database must do reads and rereads of blocks over and over and over. With the NUMBER datatype, the table data and the index data were sorted identically.
When Is a Foreign Key Not a Foreign Key?

I learn or relearn something new about Oracle Database every day. Really.

For example, a short while ago I was in Belgrade, Serbia, delivering a seminar, and an attendee reminded me of something I knew once but had totally forgotten about. It had to do with foreign keys and the dreaded NULL value.

Many of you might think the following demonstration is not possible, but it is. I’ll start with the tables:

SQL> create table p
  2  ( x int,
  3    y int,
  4    z int,
  5    constraint p_pk primary key(x,y)
  6  )
  7  /
Table created.
SQL> create table c
  2  ( x int,
  3    y int,
  4    z int,
  5    constraint c_fk_p 
  6    foreign key (x,y) 
  7    references p(x,y)
  8  )
  9  / 
Table created.

Looks like a normal parent-child relationship: a row may exist in C if and only if a parent row exists in P. But if that is true, how can this happen?

SQL> select count( x||y ) from p;
SQL> select count( x||y ) from c;

There are zero records in P—none. There is at least one record in C, and that record has a non-null foreign key. What is happening?

It has to do with NULLs, foreign keys, and the default MATCH NONE rule for composite foreign keys. If your foreign key allows NULLs and your foreign key is a composite key, you must be careful of the condition in which only some of the foreign key attributes are not null. For example, to achieve the above magic, I inserted

SQL> insert into c values ( 1, null, 0 );
1 row created.

The database cannot validate a foreign key when it is partially null. In order to enforce the MATCH FULL rule for composite foreign keys, you would add a constraint to your table:

SQL> alter table c add constraint 
  2  check ( ( x is not null 
  3            and y is not null ) or
  4          ( x is null 
  5             and y is null ) ) 
  6  /
Table altered.

The constraint will ensure that either

  • All of the columns are NULL in the foreign key, or
  • None of the columns are NULL in the foreign key

As long as that constraint is in place, your foreign key will work as you probably think it should.

Next Steps

 ASK Tom
Tom Kyte answers your most difficult technology questions. Highlights from that forum appear in this column.

 FOLLOW Tom on Twitter

 more Tom
 Oracle Database Concepts 11g Release 2 (11.2)
 Expert Oracle Database Architecture: Oracle Database 9i, 10g, and 11g Programming Techniques and Solutions, Second Edition

 DOWNLOAD Oracle Database 11g Release 2

LEARN more about
 index clustering factor
 foreign key constraints and NULL values

FOLLOW Oracle Database
 on Twitter
 on Facebook

Photography by Dmitri Popov, Unsplash