jump to navigation

Index Rebuild, the Need vs the Implications Support Note 989093.1 (Getting Better) March 5, 2014

Posted by Richard Foote in Doc 122008.1, Doc 989093.1, Index Rebuild, Oracle Indexes, Oracle Myths.
4 comments

Once upon a time, Oracle Support had a note called Script: Lists All Indexes that Benefit from a Rebuild (Doc ID 122008.1) which lets just say I didn’t view in a particularly positive light :) Mainly because it gave dubious advice which included that indexes should be rebuilt if:

  • Deleted entries represent 20% or more of current entries
  • The index depth is more than 4 levels

It then detailed a script that ran a Validate Structure across all indexes in the database that didn’t belong in either the SYS or SYSTEM schema.

This script basically read through and sequentially locked all tables (maybe multiple times) in the database in order to list indexes that might not actually need a rebuild while potentially missing out on some that do. I could write a script that achieved the same result with far less overheads. For example, SELECT index_name FROM DBA_INDEXES where index_name like ‘A%’ and owner not in (‘SYS’, ‘SYSTEM’) would achieve a very similar result :)

Thankfully, note 122008.1 was eventually removed from My Oracle Support (MOS) some time ago, interestingly soon after I discussed the ramifications of this script in my Oracle Index seminars :)

I recently stumbled upon another related note on MOS regarding index rebuilds, Index Rebuild, the Need vs the Implications (Doc ID 989093.1). Although not perfect (for example while it mentions ANALYZE INDEX VALIDATE STRUCTURE can now be performed online, doing so means that INDEX_STATS is not populated making it a little pointless in this context), it is a significant improvement on the previous note and certainly well worth a read for Oracle newbies. 

It also references a script to investigate a b-tree index structure (Doc ID 989186.1) that doesn’t rely on the Validate Structure of an index, making it a far less problematic to use, while also keeping a useful history of index characteristics. Also worth checking out.

So What Is A Good Cardinality Estimate For A Bitmap Index Column ? (Song 2) April 13, 2010

Posted by Richard Foote in Bitmap Indexes, Non-Unique Indexes, Oracle Indexes, Oracle Myths.
16 comments

As I’ve discussed previously, using a Bitmap index on a unique column makes little sense as the underling index must be larger than a corresponding B-tree index due to the implicit additional overheads associated with Bitmap indexes. As such, Oracle doesn’t permit the use of a Bitmap Index on a declared unique column or to police a unique constraint.  Therefore, some amount of index entry duplication is necessary for a Bitmap index to be considered.

However, an interesting question is how much duplication is actually necessary ? At what point does a Bitmap index have the potential to be equivalent or better than a corresponding B-Tree index ?  The answer will perhaps surprise many, especially those that only consider Bitmap Indexes to be viable for so-called “low cardinality”columns on large tables where there could be many millions of occurrences of each distinct value in a column.
 
If one actually looks at what comprises an index entry in each type of index and understands somewhat how the bitmap column is comprised and effectively compressed, the rough ballpark answer becomes quite easy to determine.
 
Remember, for a non-compressed, non-unique B-Tree index, an index entry comprises:
 
The indexed column or columns (however long the index column values might be)
6 bytes for the rowid (assuming a local index or index on non-partitioned tables)
2 bytes for flag and lock bytes
1 byte for each index column (a minimum of 2 bytes)
 
So that’s 10 bytes plus the size of the actual indexed column for a single column B-Tree index. The key point here however is that there’s an index entry for each and every not null index value.
 
For a Bitmap index, an index entry comprises:
 
The index column(s)
2 x 6 byte rowid
2 bytes for flag and lock bytes
1 byte for each index column (a minimum of 4 bytes)
? bytes for the actual bitmap sequence
 
So the additional overheads comes down to the additional 6 byte rowid and the length of the bitmap column. The key point here though is that there may only need be one index entry (or Bitmap index “piece”) for each distinct indexed value. However, if the number of occurrences of each index value is very low (eg: say single figures), then it’s almost certain only one bitmap index entry (piece) would be necessary for each indexed value.
 
The number of bytes required for the actual bitmap column depends on many factors, including the number of occurrences of each indexed value and the clustering of the data in the table. However again, if the number of occurrences of each index value is very low (eg: say single figures), it means the vast majority of bits are 0 (false) within each bitmap sequence and so can be compressed extremely efficiently. If there are only a handful of 1 (true) bits within a bitmap index entry, the bitmap column is going to be tiny and effectively compressed to only a few bytes.
 
Therefore, the actual additional overheads for a bitmap index with few repeated values is only the 7 byte overhead for the additional rowid and its length and a few bytes for the actual bitmap column. But remember, this single bitmap index entry can cater for all occurrences of the indexed column, whereas the B-Tree index requires an index entry for each and every occurrence of the index column.
 
It doesn’t take much for these additional overheads for each Bitmap index entry to start to cancel out …
 
If we look at an indexed column (say length 4 bytes) that has on average just the one duplicate value:
 
Total for a B-Tree Index would be:
 
4 bytes index column
6 bytes rowid
2 bytes for each index column length byte(remembering the rowid is an index column in a non-unique index)
2 bytes for flag and lock bytes
 
= 14 bytes x 2 (for each index entry as there’s a duplicate value) = 28 bytes in total
 
For a corresponding Bitmap index:
 
4 bytes index column
12 bytes for the two rowids
4 bytes for each index column length byte (remembering the rowids and bitmap sequence are effectively additional indexed columns)
2 bytes for flag and lock bytes
2 bytes is all it takes for the bitmap sequence column (if there’s only 2 actual true bits per index entry)
 
= 24 bytes in total.
 
So we’re already in a position for a Bitmap index to potentially be the smaller and more efficient index type, even when there’s only just one duplicate on average per index column value …
 
If we have another duplicate value (so there are on average 3 occurrences of each index value), then the overheads for such a B-Tree becomes:
 
3 x 14 bytes = 42 bytes
 
but the overheads for the bitmap index only increases by a byte or so for the necessary increase in the bitmap column. So the difference in space between the two index types starts to widen significantly.
 
Obviously, the size of the index column becomes a factor in the potential savings with a Bitmap index as it only has to potentially store the index column once whereas the (non-compressed) B-Tree index needs to store all occurrences of the index value. To illustrate the comparative differences between a B-Tree and a Bitmap Index, I’m going to create various tables with columns that have different levels of cardinality and different clustering attributes for their indexed columns and compare the size differences between B-Tree and Bitmap indexes. The indexed column will simply be a small NUMBER type column to make it just that bit harder for the Bitmap index to be the more efficient.

In the first example, 1/3 of all values are unique while the remaining 2/3 of values have just 2 occurrences of each value. The column is certainly not unique but is arguably “approaching” uniqueness.
Initially, the indexed column is very well clustered within the table (although with a bitmap index, the clustering factor in the index statistics is useless as it simply denotes the number of index entries within the index).
 

SQL> create table bowie as select rownum id, ceil(rownum/1.5) key, 'David Bowie' name from dual connect by level <= 1000000;
 
Table created.
 
SQL> select count(distinct key) from bowie;
 
COUNT(DISTINCTKEY)
------------------
            666667
 
SQL> create bitmap index bowie_bitmap_i on bowie(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BITMAP_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BITMAP_I           2129            666667
 
SQL> drop index bowie_bitmap_i;
 
Index dropped.
 
SQL> create index bowie_btree_i on bowie(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BTREE_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BTREE_I            1999              3738

 

Although some may claim such a Bitmap index, one with 666,667 distinct values in a 1 million row table would be thousands of times larger and less efficient than an equivalent B-Tree index, it’s actually quite a close call. The bitmap index is only 124 leaf blocks different or approximately 6.5% larger in size than the B-Tree index.
 
If we create an equivalent table but this time with the clustering of the data all over the place:
 
 


SQL> drop table bowie2;
 
Table dropped.
 
SQL> create table bowie2 as select * from bowie order by mod(id, 100);
 
Table created.
 
SQL> create bitmap index bowie2_bitmap_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BITMAP_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE2_BITMAP_I          2246            666667
 
SQL> drop index bowie2_bitmap_i;
 
Index dropped.
 
SQL> create index bowie2_btree_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BTREE_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE2_BTREE_I           1999            999722

 

We notice that the B-Tree index remains the same size but the Bitmap index is now a little larger by 117 additional leaf blocks. So even with an awful clustering, the Bitmap index is only 247 leaf blocks or approximately 12.3% larger than the B-Tree index. So the B-Tree just wins out in this case, the column is still just that bit too unique for the Bitmap index where we have 666,667 distinct values in a 1 million row table.
 
OK, let’s see how the indexes compare when the index column has on average 1 duplicate for each and every indexed value. There are just 2 values for each and every indexed value, 500,000 distinct values in a 1 million row table: 
 

 
SQL> drop table bowie;

Table dropped.

SQL> create table bowie as select rownum id, ceil(rownum/2) key, 'David Bowie' name from dual connect by level <= 1000000;

Table created.

SQL> create bitmap index bowie_bitmap_i on bowie(key) pctfree 0;

Index created.

SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BITMAP_I';

INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BITMAP_I           1628            500000

SQL> drop index bowie_bitmap_i;

Index dropped.

SQL> create index bowie_btree_i on bowie(key) pctfree 0;

Index created.

SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BTREE_I';

INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BTREE_I            1998              3728

 

OK, now the Bitmap index is well ahead. On a well clustered column that has 500,000 distinct values in a 1 million row table, the B-Tree index is now larger by 370 leaf blocks or by 22.7%. What if the data is poorly clustered:


SQL> drop table bowie2;
 
Table dropped.
 
SQL> create table bowie2 as select * from bowie order by mod(id, 100);
 
Table created.
 
SQL> create bitmap index bowie2_bitmap_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BITMAP_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE2_BITMAP_I          1806            500000
 
SQL> drop index bowie2_bitmap_i;
 
Index dropped.
 
SQL> create index bowie2_btree_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BTREE_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE2_BTREE_I           1998            999803

 

OK, the Bitmap index is now larger by 178 leaf blocks than it was before, but the equivalent B-Tree index is still larger by 10.6%.
 
Again, this is on a relatively small, extremely poorly clustered indexed column that has 500,000 distinct values in just a 1 million row table. The Bitmap index is smaller and more efficient than the equivalent B-Tree index.
 
If we now use a column that has on average 4 occurrences for each distinct column value (with 250,000 distinct values in a 1 million row table), the differences between a Bitmap and a B-Tree index begin to widen significantly.
 


SQL> drop table bowie;
 
Table dropped.
 
SQL> drop table bowie2;
 
Table dropped.
 
SQL> create table bowie as select rownum id, ceil(rownum/4) key, 'David Bowie' name from dual connect by level <= 1000000;
 
Table created.
 
SQL> create bitmap index bowie_bitmap_i on bowie(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BITMAP_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BITMAP_I            829            250000
 
SQL> drop index bowie_bitmap_i;
 
Index dropped.
 
SQL> create index bowie_btree_i on bowie(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE_BTREE_I';
 
INDEX_NAME        LEAF_BLOCKS CLUSTERING_FACTOR
----------------- ----------- -----------------
BOWIE_BTREE_I            1995              3753

 

On a well clustered column with 250,000 distinct values in a 1 million row table, the Bitmap index is less that 1/2 the size of that of an equivalent B-Tree index. If the data were less so clustered:


SQL> create table bowie2 as select * from bowie order by mod(id, 100);
 
Table created.
 
SQL> create bitmap index bowie2_bitmap_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BITMAP_I';
 
INDEX_NAME      LEAF_BLOCKS CLUSTERING_FACTOR
--------------- ----------- -----------------
BOWIE2_BITMAP_I        1145            250000
 
SQL> drop index bowie2_bitmap_i;
 
Index dropped.
 
SQL> create index bowie2_btree_i on bowie2(key) pctfree 0;
 
Index created.
 
SQL> select index_name, leaf_blocks, clustering_factor from dba_indexes where index_name = 'BOWIE2_BTREE_I';
 
INDEX_NAME      LEAF_BLOCKS CLUSTERING_FACTOR
--------------- ----------- -----------------
BOWIE2_BTREE_I         1995            999881

 

Even with a really poor clustered index column, the B-Tree index is still some 74% larger than the Bitmap index with some 250,000 distinct values.
 
Despite many claims to the contrary, including the rewrite of the awful Burleson article  that started this series on Bitmap Indexes, where it still claims that “there are rare cases where a bitmap on a column with 10,000 key values might be appropriate” and “in most cases, there will not be a lot of adjacent index values, so it quite rare to see extensive compression“, in reality it’s not that rare at all for a column with “large” numbers of distinct values to be indexed effectively via a Bitmap Index. But, you actually need to understand Bitmap Indexes to appreciated this fact and have at least some understanding on how Oracle stores and compresses the bitmap column. The Burleson description of Bitmap index compression in the above article is totally wrong and so hence are its overall conclusions. 

Here’s an actual, “real life” example. On a 2.2 million row table with a column on people last names, (name columns are often considered way too distinct for Bitmap indexes), there were approximately 6.5 occurrences of each last name on average over the whole table. The most compact B-Tree index on the Last Name column required 5286 leaf blocks but the equivalent Bitmap index only required 2151 leaf blocks, way less than 1/2 the size, even though the clustering factor was terrible at nearly 2 million.
 
As a rough rule, any column that has an on average of just 1 duplicate per distinct column value (just 2 occurrences per distinct value) is a potential candidate for a bitmap index.
 
Bitmap indexes should only be considered in Data Warehouse, low concurrency DML type environments due to their locking implications and certainly pre 10g, Bitmap indexes had growth issues after significant DML changes. However it’s a complete nonsense to suggest that Bitmap indexes should only be considered with columns with “few” distinct values, else things will run 100s of times slower.
 
500,000 distinct values in a 1 million row table is not really that “few” at all is it …

Myth: Bitmap Indexes With High Distinct Columns (Supermassive Black Hole) March 3, 2010

Posted by Richard Foote in Bitmap Indexes, CBO, Clustering Factor, Oracle Indexes, Oracle Myths.
34 comments

As discussed in my previous post, it’s a silly myth to suggest a bitmap index should only be used for so-called “low cardinality” columns else the resultant index would be “huge”. I thought it might be worth a quick refresh to see a simple little demonstration why such claims are a nonsense.  There is in fact no limit to the number of distinct values by which a column could be considered a candidate for a bitmap index.  

I’ve already shown how a bitmap index on a column with 10,000 distinct values could potentially be smaller than an index with just 4 distinct values, even with the same data type and size. The number of distinct values in a column is but one small consideration, the number of rows in the table and the average ratio of repeated values are just as important. The other important consideration that can significant impact the size of a bitmap index is the distribution and clustering of the data within the table as we shall see.    

Using the same demo as the previous post, a reminder of the size of our bitmap index on a column with 10,000 distinct values in a 1 million row table.
 

SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks from dba_indexes where index_name = 'BIG_BOWIE_CODE_BITMAP_I';
 
INDEX_NAME                INDEX_TYPE DISTINCT_KEYS  BLEVEL LEAF_BLOCKS
------------------------- ---------- ------------- ------- -----------
BIG_BOWIE_CODE_BITMAP_I   BITMAP             10000       1          52
 

  

 
Let’s now see if the CBO will actually use this bitmap index on its own: 

  

SQL> select * from big_bowie where code = 42;

100 rows selected.

Execution Plan
----------------------------------------------------------
Plan hash value: 4280385727

--------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                    | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                         |   100 |  7300 |    22   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | BIG_BOWIE               |   100 |  7300 |    22   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                         |       |       |            |          |
|*  3 |    BITMAP INDEX SINGLE VALUE | BIG_BOWIE_CODE_BITMAP_I |       |       |            |          |
--------------------------------------------------------------------------------------------------------

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

   3 - access("CODE"=42)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          6  consistent gets
          0  physical reads
          0  redo size
       1854  bytes sent via SQL*Net to client
        396  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed

 
 

Absolutely it does. As there are on average just 100 rows per distinct value, that's a small enough selectivity for the CBO to use the bitmap index on its own. Note the query has used just 6 consistent gets to return the 100 rows of data.
 
Let's now drop the bitmap index and see how a regular B-Tree index would compare and perform:
 

  
SQL> drop index big_bowie_code_bitmap_i;
 
Index dropped.
 
SQL> create index big_bowie_code_i on big_bowie(code);
 
Index created.
 
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks, clustering_factor as cf from dba_indexes where index_name = 'BIG_BOWIE_CODE_I';
 
INDEX_NAME           INDEX_TYPE DISTINCT_KEYS  BLEVEL LEAF_BLOCKS         CF
-------------------- ---------- ------------- ------- ----------- ----------
BIG_BOWIE_CODE_I     NORMAL             10000       2        2090      10895

  

The first thing we notice is that the B-Tree index is significantly larger than the equivalent bitmap index. 1090 leafs blocks whereas the bitmap index was only 56 leaf blocks. So it's not the bitmap index that's so-called "huge" here on a column with 10,000 distinct values but the corresponding B-Tree index. Notice also that the Clustering Factor of the index is quite good at 10,895 in a 1 million row table.   

If we now run the same query as before: 

 
SQL> select * from big_bowie where code = 42;
 
100 rows selected.
 
Execution Plan
----------------------------------------------------------
Plan hash value: 1856845120
 
------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                  |   100 |  7300 |     5 (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| BIG_BOWIE        |   100 |  7300 |     5 (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | BIG_BOWIE_CODE_I |   100 |       |     3 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("CODE"=42)
 
Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          8  consistent gets
          0  physical reads
          0  redo size
       1854  bytes sent via SQL*Net to client
        396  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed
 
 

 

The query also uses the index but as the B-Tree index is somewhat larger, the overall number of consistent reads has increased from 6 up to 8. So not only is the bitmap index substantially smaller despite having 10,000 distinct values, but it's also more efficient to use as a result.A key reason why the bitmap index is so small and compact is because the effective Clustering Factor of the indexed column is excellent. The data was inserted into the table in CODE column order and so all the values with the same CODE value are grouped, ordered and clustered together within the table. Within the bitmap index, this means there are large and few grouping of zeros (0) that can be compressed extremely efficiently. 

For example, for the first CODE value of 1, the bitmap sequence would look something like: 

111111 .... 1110000000000000000000000000000000........000000 

with the 100 values of 1 (true) grouped together followed only by a series of effectively 999,900 zeros (o representing false). The 999,900 zeros can be compressed back almost nothing at all. Note there could actually be somewhat more false (0) values than actual rows in the table but that's a discussion for another day. 

The next value of 2 would have a bitmap sequence something like: 

00000000....0001111111...11111100000000000000000000...0000 

with 100 zeros followed by 100 1s followed by effectively 999,800 zeros, with again the two grouping of zeros compressed down to almost nothing at all. 

And so on ... 
Let's now create a different table that contains the identical data but  this time with the CODE values effectively randomized throughout the table. The Clustering Factor of the CODE column in this case will be terrible: 

 
 
SQL> create table big_bowie_2 as select * from big_bowie order by mod(id,100);
 
Table created.
 
SQL> create bitmap index big_bowie_2_code_bm_i on big_bowie_2(code);
 
Index created.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>'BIG_BOWIE_2', estimate_percent=>null, method_opt=> 'FOR ALL COLUMNS SIZE 1');
 
PL/SQL procedure successfully completed.
 
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks from dba_indexes where index_name = 'BIG_BOWIE_2_CODE_BM_I';
 
INDEX_NAME             INDEX_TYPE DISTINCT_KEYS  BLEVEL LEAF_BLOCKS
---------------------- ---------- ------------- ------- -----------
BIG_BOWIE_2_CODE_BM_I  BITMAP             10000       1         520
 

 

The first thing we notice is that the bitmap index is now substantially larger than it was previously. It's gone from just 52 leaf blocks all the up to 520 blocks, a whole 10 times larger than before. The reason is all to do with the clustering of the data as now values for CODE are littered all over the table and are no longer grouped together. 

The bitmap sequence for the first CODE value of 1 would now look something like: 

00000000000100000000000000000..0000010000000000000000...0000010000000000001000000000...00000100000.... 

with the 1s now littered all over the place. This means it's far less efficient to compress the groups of zeros as there are now substantially more such groupings than before. The index is now 10 times larger as a result. 

If we now run the same query as before: 

  

SQL> select * from big_bowie_2 where code = 42;
 
100 rows selected.
 

Execution Plan
----------------------------------------------------------
Plan hash value: 1324437154
 
------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                  | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                       |   100 |  7300 |  22     (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | BIG_BOWIE_2           |   100 |  7300 |  22     (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                       |       |       |            |          |
|*  3 |    BITMAP INDEX SINGLE VALUE | BIG_BOWIE_2_CODE_BM_I |       |       |            |          |
------------------------------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("CODE"=42)
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        103  consistent gets
          0  physical reads
          0  redo size
       1854  bytes sent via SQL*Net to client
        396  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed
 

 

 Although the CBO is still using the bitmap index on its own, the performance of the query has deteriorated substantially with the number of consistent gets increasing from 6 all the way up to 103.  

So the bitmap index is now nowhere near as efficient. A bitmap index isn't that great with large numbers of distinct values if the associated clustering is poor and so the B-Tree index is the way to go after all, right ? 

Well just wait a minute. If the clustering is poor for a bitmap index, the clustering will likewise be poor for a corresponding B-Tree index as well.  Most of these consistent reads are due to reading the data out of the table, not from reading the index directly. So the performance of using an equivalent B-Tree index is also likely to be impacted as well. 

Let's compare the difference with a B-Tree index: 

   
SQL> drop index big_bowie_2_code_bm_i;
 
Index dropped.
 
SQL> create index big_bowie_2_code_i on big_bowie_2(code);
 
Index created.
 
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks, clustering_factor as cf from dba_indexes where index_name = 'BIG_BOWIE_2_CODE_I';
 
INDEX_NAME             INDEX_TYPE DISTINCT_KEYS  BLEVEL LEAF_BLOCKS         CF
---------------------- ---------- ------------- ------- ----------- ----------
BIG_BOWIE_2_CODE_I     NORMAL             10000       2        2090     999922
 
 

 

The first thing to note here is that the B-Tree index is still 2090 leaf blocks in size. Even compared with the now far less efficient Bitmap index, at 520 leaf blocks it's still approximately just 25% the size of the B-Tree index. So the 10,000 distinct value bitmap index, even when it's as inefficient as possible, still can't be described as "huge"  here as it's still only a 1/4 the size of the corresponding B-Tree index. With a Clustering Factor of 999,992 on a 1 million rows table, it doesn't really get much worse than that and yet the Bitmap index on a 10,000 distinct column is still way ahead of the B-Tree index.  

Let's see how the query performs now: 

 
SQL> select * from big_bowie_2 where code = 42;
 
100 rows selected.
 

Execution Plan
----------------------------------------------------------
Plan hash value: 2550134594
 
--------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name               | Rows  | Bytes |  Cost(%CPU)| Time     |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                    |   100 |  7300 |   103   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| BIG_BOWIE_2        |   100 |  7300 |   103   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | BIG_BOWIE_2_CODE_I |   100 |       |     3   (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("CODE"=42)
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        105  consistent gets
          0  physical reads
          0  redo size
       1854  bytes sent via SQL*Net to client
        396  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed

As we can see, the performance of the B-Tree index has likewise deteriorated with such a bad Clustering Factor. At 105 consistent gets, it's still worse than the corresponding Bitmap index which only needed 103 consistent gets. 

With a Bitmap index that is as inefficient as it can be, on a column that has 10,000 distinct values in a table of only 1 million rows, the Bitmap index still outperforms the corresponding B-Tree index. 

It's a complete myth and utter nonsense that a bitmap index is only suitable for low cardinality columns and would become "HUGE" and be 100s of times slower if created on so-called high cardinality column 

Let me repeat: There is no limit to the number of distinct values in a column for it to be considered for a Bitmap index.

Myth: Bitmap Indexes With High Distinct Columns (Blow Out) February 18, 2010

Posted by Richard Foote in Bitmap Indexes, Oracle Indexes, Oracle Myths.
81 comments

I just couldn’t resist.  

One of the great myths in Oracle is that bitmap indexes are only suitable and should only be used with columns that have so-called low cardinality (few distinct) values. A classic example of this myth being propagated is in this latest Burleson news item, “Oracle bitmap index maximum distinct values“, from Feb 16 2010 (article itself updated January 8, 2010): 

It says “As the number if distinct values increases, the size of the bitmap increases exponentially, such that an index with 100 values may perform thousands of times faster than a bitmap index on 1,000 distinct column values.” 

It also mentions some so-called rules of thumb whereby: 

“1 – 7 distinct values – Queries against bitmap indexes with a low cardinality are very fast.

8-100 distinct values – As the number if distinct values increases, performance decreases proportionally.

100 – 10,000 distinct values – Over 100 distinct values, the bitmap indexes become huge and SQL performance drops off rapidly.

Over 10,000 distinct values – At this point, performance is ten times slower than an index with only 100 distinct values”

Now this of course is all generalised nonsense. Not only can a column with 10,000+ distinct values be perfect as a bitmap index but it can be considerably smaller than a bitmap index with only a handful of distinct values, even with columns of the same size and data type

A very simple example to demonstrate. First, I’m going to create a table with 1 million rows and have a CODE column that has 10,000 distinct values and a TYPE column with just 4 distinct values:

SQL> create table big_bowie (id number, code number, type number, name varchar2(100));
Table created.
SQL> declare
  2  i number;
  3  begin
  4  i:=0;
  5  for j in 1..10000 loop
  6     for k in 1..100 loop
  7      i:=i+1;
  8      insert into big_bowie values (i, j, mod(k,4)+1, 'The Rise And Fall Of Ziggy Stardust And The Spiders From Mars');
  9     end loop;
 10  end loop;
 11  commit;
 12  end;
 13  /
PL/SQL procedure successfully completed.
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>'BIG_BOWIE', estimate_percent=>null, method_opt=> 'FOR ALL COLUMNS SIZE 1');
PL/SQL procedure successfully completed.

 
OK, I’m just going to create a standard B-Tree index on the TYPE column and see how large it is:

SQL> create index big_bowie_type_i on big_bowie(type) pctfree 0;
Index created.
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks from dba_indexes where index_name = 'BIG_BOWIE_TYPE_I';
  
INDEX_NAME                INDEX_TYPE DISTINCT_KEYS     BLEVEL LEAF_BLOCKS
------------------------- ---------- ------------- ---------- -----------
BIG_BOWIE_TYPE_I          NORMAL                 4          2        1752

 

OK, so it’s a BLEVEL 2 index with 1752 leaf blocks. Let’s now compare it with an equivalent bitmap index. As the column only has 4 distinct values, it should be perfect as a bitmap index and much smaller than the B-Tree:


SQL> drop index big_bowie_type_i;
Index dropped.
SQL> create bitmap index big_bowie_type_bitmap_i on big_bowie(type) pctfree 0;
Index created.
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks from dba_indexes where index_name = 'BIG_BOWIE_TYPE_BITMAP_I';
  
INDEX_NAME                INDEX_TYPE DISTINCT_KEYS     BLEVEL LEAF_BLOCKS
------------------------- ---------- ------------- ---------- -----------
BIG_BOWIE_TYPE_BITMAP_I   BITMAP                 4          1          84

 

Indeed it is smaller. It’s now just 84 leaf blocks in size, down from the previous 1752 leaf blocks. The Blevel has even reduced to just 1.

OK, let’s attempt something really silly and outrageous. Let’s create a bitmap index on the CODE column, a column with 10,000 distinct values. I know, I’m crazy to even suggest such a thing as the resultant bitmap will simply be “HUGE” right ?

Let’s see.


SQL> create bitmap index big_bowie_code_bitmap_i on big_bowie(code) pctfree 0;
Index created.
SQL> select index_name, index_type, distinct_keys, blevel, leaf_blocks from dba_indexes where index_name = 'BIG_BOWIE_CODE_BITMAP_I';
  
INDEX_NAME                INDEX_TYPE DISTINCT_KEYS     BLEVEL LEAF_BLOCKS
------------------------- ---------- ------------- ---------- -----------
BIG_BOWIE_CODE_BITMAP_I   BITMAP             10000          1          52

 

Well, would you look at that. It’s not “huge” at all, it’s just a tiny 52 leaf blocks !! In fact, it’s actually smaller and just 62% the size of the TYPE bitmap index that only had 4 distinct values.

So a bitmap index with 10,000 distinct values is actually smaller, more compact and more efficient that a bitmap index with just 4 distinct values !!

Why so small ?

Because the size and efficiency of a bitmap index doesn’t just depend on the number of distinct values but a whole range of other factors as well, not least the size and the clustering of the data in the table. Clue: I inserted the data into my BIG_BOWIE table in a very careful manner. However, one does need to actually understand how bitmap indexes work and how they actually store data to appreciate and determine whether a column is suitable for a bitmap index.

In short, there is no limit to the number of distinct values by which a column is suitable for a bitmap index. You could have a column with 10s of millions of distinct values (in say a billion row table) and a bitmap index might be perfectly suitable and significantly smaller than an equivalent B-Tree index. This is because a B-Tree index needs to store each and every occurence of a column value (unless the index is compressed) as well as a corresponding rowid whereas a Bitmap index might only need to store each distinct column value once with just 2 corresponding rowids. The savings in space can be massive, even if there are relatively few repeated occurences of each distinct value on average.

The next time you unfortunately read that bitmap indexes should only be used with very “few” distinct values and would be “huge” otherwise, well hopefully you’ll appreciate that’s simply not correct.

How Does An Execution Plan Suddenly Change When The Statistics (And Everything Else) Remains The Same ? (In Limbo) February 16, 2010

Posted by Richard Foote in CBO, Index Access Path, Oracle Cost Based Optimizer, Oracle Indexes, Oracle Myths.
109 comments

I’ve slipped this post in as there have been a number of discussions recently on how execution plans have changed while nothing else appears to have changed in the database. How can an execution plan suddenly change when no one has made any changes to the database ?
 
By no changes, it means that there have been no alterations to any segments, no new indexes have been added, no changes associated  bind peeking (indeed, there may not even be any bind variables), no parameters changes, no new patches or upgrades, no new outlines or profiles, no new system stats and perhaps most prevalent of all, no changes to any CBO statistics.
 
The DBA hasn’t touched a thing and yet suddenly, for no apparent reason, execution plans suddenly change and (say) an inappropriate index is suddenly used and causes performance degradation.
 
How can this be possible ?
 
There are two key points I want to emphasise.
 
The first is that there’s a common misperception that if no new statistics are gathered (and assuming nothing else is altered in the database), that execution plans must always remain the same. That by not collecting statistics, one somehow can ensure and guarantee the database will simply perform in the same manner and generate the same execution plans.
 
This is fundamentally not true. In fact, quite the opposite can be true. One might need to collect fresh statistics to make sure vital execution plans don’t change. It’s the act of not refreshing statistics that can cause execution plans to suddenly change.
 
The second point is that when one goes through all the things that might have changed in the database, two important aspects are often overlooked.
 
The first thing that does usually change within most databases is the actual data within the database. Those damn users log on and keep adding new data and modifying data all the time. It might not be a database change as such but the fact the data changes within a database is a critical change that can directly influence CBO behaviour. When pointing the finger at what might have caused an execution plan to change, many simply ignore the fact the data is constantly changing in the background.
 
The other aspect that always changes is time. People have tried but it’s very difficult to stop time. When things worked well, it was at a different point in time than now when things have suddenly gone wrong.
 
So some things do change that are not in direct control of the DBA.
 
But if we don’t collect fresh statistics, even though the data might have changed, won’t those data changes be effectively invisible to the CBO? Won’t the statistics not reflect any possible data changes and if the CBO doesn’t think the data has changed, doesn’t that mean it can’t suddenly change how it determines an execution plan ?
 
Not true. It’s quite possible that because the statistics haven’t changed, the CBO is forced into makings changes in how it costs and determines an execution plan.
 
A very simple example follows, a classic case of why not refreshing statistics has caused the CBO to suddenly change an execution plan for no apparent reason.
 
I’ll begin by creating a simple little table and populate it with approximately 5 years worth of data.

 
SQL> create table muse (id number, muse_date date, name varchar2(10));
 
Table created.
 
SQL> declare
  2  v_count  number;
  3  begin
  4  v_count:=0;
  5  for i in 1..1830 loop
  6     for j in 1..1000 loop
  7     v_count:= v_count+1;
  8     insert into muse values (v_count, sysdate-i, 'MUSE');
  9     end loop;
 10  end loop;
 11  commit;
 12  end;
 13  /
 
PL/SQL procedure successfully completed.
 
SQL> create index muse_i on muse(muse_date);
 
Index created.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>'BOWIE', tabname=>'MUSE', casca
de=>true, estimate_percent=>null, method_opt=>'FOR ALL COLUMNS SIZE 1');
 
PL/SQL procedure successfully completed.

So the procedure basically populates the table, setting the MUSE_DATE column with approximately 5 years worth of data, with 1000 rows for each day so the data is evenly distributed across those 5 years.

Note that I’ve collected statistics on the table and index and they’re fully up to date.

The following query is a typical query in our application, where we’re only interested in looking at the previous year’s worth of data. It simply selects all data that is only a year old. This is a query that’s run all the time and only looks at a “moving window” of data, that being just those rows that were inserted up to a year ago.


 
SQL> select * from muse where muse_date > sysdate - 365;
 
364000 rows selected.
 
 
Execution Plan
----------------------------------------------------------
Plan hash value: 2738706195
 
--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   363K|  6390K|  1330  (11)| 00:00:07 |
|*  1 |  TABLE ACCESS FULL| MUSE |   363K|  6390K|  1330  (11)| 00:00:07 |
--------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter("MUSE_DATE">SYSDATE@!-365)
 
Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
       5992  consistent gets
       5912  physical reads
          0  redo size
    3638996  bytes sent via SQL*Net to client
       1188  bytes received via SQL*Net from client
         74  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     364000  rows processed
 

Notice how the CBO has decided to use a Full Table Scan (FTS) as a year is quite a chunk of the table and is more effectively accessed in this manner. Notice also how the CBO has got the cardinality spot on and has correctly predicted the number of rows to be returned. If the CBO gets the selectivity and so the cardinality of the query correct, we have some confidence that it has indeed come up with the most efficient execution plan. Indeed, the users are perfectly happy with the performance of the query, the DBAs are happy and because we don’t really want to risk the CBO suddenly changing things, we decide to not collect statistics on this table any more.

However, more data is pumped into the table each and every day by the end-users.

The following procedure will add another years worth of data into the table to simulate how the table will be populated in a year’s time …

SQL> declare
  2  v_count  number;
  3  begin
  4  v_count:=1830000;
  5  for i in 1..365 loop
  6     for j in 1..1000 loop
  7     v_count:= v_count+1;
  8     insert into muse values (v_count, sysdate+i, 'MUSE');
  9     end loop;
 10  end loop;
 11  commit;
 12  end;
 13  /
 
PL/SQL procedure successfully completed.

Note that we have NOT collected any new statistics.

OK, let’s now fast track ourselves one year into the future and run the same query again. Note in a year’s time, we will be 365 days past the current sysdate. So we’ll mimic running the identical query by simply adding 365 days to the sysdate and again querying for the latest year’s worth of data:


 
SQL> select * from muse where muse_date > (sysdate+365) - 365;
 
365000 rows selected.
 
 
Execution Plan
----------------------------------------------------------
Plan hash value: 1682432684
 
--------------------------------------------------------------------------------------
| Id  | Operation                   | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |        |   944 | 16992 |     9   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| MUSE   |   944 | 16992 |     9   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | MUSE_I |   944 |       |     5   (0)| 00:00:01 |
--------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("MUSE_DATE">SYSDATE@!+365-365)
 
Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
       4005  consistent gets
       1301  physical reads
     134192  redo size
    4024147  bytes sent via SQL*Net to client
       1188  bytes received via SQL*Net from client
         74  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     365000  rows processed
 

We notice that the execution plan has now changed !!

It’s now suddenly starting to use an index where previously it was using a FTS. Notice also that the CBO has got the cardinalty estimate way wrong, predicting only 944 rows will be returned. Instead of estimating it will get a year’s worth of data, the CBO is estimating only approximately 1 days worth of data or the selectivity based on one distinct value. If the CBO get’s this so terribly wrong, it’s a good chance it has also got the execution plan terribly wrong as well.

The query is effectively the same query that would be run in a year’s time, the statistics have not been changed and yet the execution plan has indeed changed. The CBO suddenly using this index may be a terrible thing, resulting in a really inefficient execution plan and a massive increase in LIOs.

Why has the plan changed when the statistics have not ?

The key issue here is that the CBO thinks the maximum date in the table was from a year ago when the statistics were last calculated. However, the query is attempting to select data that is beyond the range of values known to the CBO. How can it now know the estimated cardinality of the query, the number of expected rows to be returned when we’re only interested in rows that are beyond its maximum known range of data ?

The answer is that it can’t. Not accurately anyway.

The CBO has to guess and depending on the version of Oracle and the type of query being parsed, it can guess in a number of different ways. Because the query is effectively after data that is greater than the maximum known value, the CBO is basically “guessing” there will only be a days worth of data greater than its maximum known value, not the full years worth that’s really in the table. The CBO having to guess is not a good thing, especially when it’s more than likely to get the guess hopelessly wrong.

Note this change will have occurred suddenly one day into the future when the CBO  starts to consider there are so few days worth returning that the index suddenly becomes the best and cheapest option.

How do we fix this inefficient execution plan ?

Rather than having the CBO guess how many rows might be returned, let it actually know. Simply collect fresh statistics and let the CBO know that we actually have a full year’s worth of data since the statistics were previously collected:

SQL> exec dbms_stats.gather_table_stats(ownname=>'BOWIE', tabname=>'MUSE', cascade=>true, estimate_percent=>null, method_opt=>'FOR ALL COLUMNS SIZE 1');
PL/SQL procedure successfully completed.

 

If we run the same query again now …


 
SQL> select * from muse where muse_date > (sysdate+365) - 365;
 
365000 rows selected.
 
 
Execution Plan
----------------------------------------------------------
Plan hash value: 2738706195
 
--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   364K|  6413K|  1652  (14)| 00:00:09 |
|*  1 |  TABLE ACCESS FULL| MUSE |   364K|  6413K|  1652  (14)| 00:00:09 |
--------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter("MUSE_DATE">SYSDATE@!+365-365)
 
Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
       7205  consistent gets
       6709  physical reads
          0  redo size
    4024147  bytes sent via SQL*Net to client
       1188  bytes received via SQL*Net from client
         74  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
     365000  rows processed

 

We now notice the CBO has got the cardinality spot on again and choses to use the efficient FTS.

So yes, an execution plan can change even if we don’t make any changes to the database, including not collecting fresh statistics. If you think by not collecting statistics, things will simply remain the same, one day when you least expect it, things might suddenly go terribly wrong.

Solving such issues can be extremely different if you try to do so by looking at what might have changed, especially if you don’t know what you’re looking for …

An Index Only Performs How Much Work ??? November 12, 2009

Posted by Richard Foote in Index Rebuild, Oracle Indexes, Oracle Myths.
34 comments

One of the main reasons suggested for performing periodic index rebuilds is to improve “performance”. After rebuilding indexes, applications now run so much faster. Users notice a significant improvement in performance. And so on.
 
There are of course situations when rebuilding specific indexes can indeed improve performance, here’s but one example I’ve discussed previously.
 
However, the question I always ask when someone claims an index rebuild has made things run faster is to simply ask why. Why is such a simple, but powerful question. Why have things improved ? What has specifically changed as a result of rebuilding the index, that Oracle has now reduced the overall work associated with performing the activity, to the point that things run noticeably faster.
 
Knowing why is really important because it confirms that indeed there was an improvement and that it was indeed associated directly with the index rebuild. It means when a similar situation arises again, you know how to directly resolve the problem appropriately and effectively next time. Also knowing why means you can determine the specific root cause, perhaps preventing things from deteriorating so bad in the first place, such that rebuilding the index becomes unnecessary. Prevention being the best cure …
 
Now the most common answer I get for why rebuilding an index has been so beneficial is because the index is now so much smaller after the rebuild that the overheads of reading the index have substantially reduced. If the index is smaller, it means one can read the same amount of index related data with less I/Os. Less I/Os means better performance.
 
For example, if you can reduce the index by half, you can fit the index into only half the number of leaf blocks and that’s a 50% performance improvement right there.
 
Well, firstly it assumes that the index has indeed reduced by half. It would actually be a relatively unusual index for it to be so poorly fragmented or for it to have so much “wasted” space that it could be rebuilt into only half the number of leaf blocks.
 
Possible but somewhat unusual.
 
However, it also assumes that by having a 50% performance improvement, reading the index blocks constitutes the vast majority of the work. Again possible in some scenarios.
 
With most index related activities though, reading the index blocks actually constitutes only a small percentage of the overall work. In most cases, the index only contributes a very small percentage of the overall I/O activity. Therefore by potentially only reducing a small percentage of the overall work by rebuilding just the index, the overall impact is generally going to be minimal.
 
I thought I might perform some basic mathematics to illustrate and put into perspective just what little impact index rebuilding can have in improving performance, even if by doing so the index dramatically reduces in size, because the index itself actually constitutes only a small percentage of the overall costs.
 
Let say we have one of these more unusual indexes that is so poorly fragmented that it has approximately 50% wasted space throughout the entire index structure. Let’s say rebuilding such an index reduces the overall size of the index by half.
 

Before the index rebuild, an index has 50% of wasted space and say:
 
Height of 3
 
1 Root Block
 
50 Intermediate Branch Blocks
 
20,000 Leaf blocks
 

After the rebuild, the index has no wasted space and has now:
 
Height of 3
 
1 Root Block
 
25 Intermediate Branch Blocks
 
10,000 Leaf Blocks
 

Let’s assume the table contains 2M rows and that they fit in 100,000 blocks (i.e. the index is about 1/10 that of the table and the average row size is such that we fit say 20 rows on average per block). Let’s also assume there’s nothing special about this index and that it has an “average” clustering factor of 1M, before and after the rebuild ;) 1M being somewhere in the middle of possible clustering factor values.

The first thing to note is that the height remains the same after such a rebuild, even though the index is only now half the size. It would be extremely unlikely and the index would have to be particularly small and within a very narrow range of sizes for all the contents of all the intermediate branch blocks to fit within just the one root block. The only way for the index height to reduce down from 3 would be for the contents of all intermediate branches to fit within the root block. Possible, but again quite unusual. 

OK, let’s look at the cost of various scans before and after the rebuild, using the index costing formula I’ve discussed recently.
 
If we’re after just one row (a unique index perhaps), then to read the one row before the rebuild would be:
 
1 I/O for the root block + 1 I/O for a branch block + 1 I/O for a leaf block + 1 I/O for the table block = 4 LIOs.
 
After the rebuild, the total cost would be:
 
1 I/O for the root block + 1 I/O for a branch block + 1 I/O for a leaf block + 1 I/O for the table block = 4 LIOs.
 
In effect, no change. Well, we’re not likely to have too much of a performance improvement there.

 
 
Let’s increase the size of the range scan. What if we retrieve 100 rows (or approx. 0.005% of data):
 
Before the rebuild it would be
 
1 I/O for the root block +
1 I/O for a branch block +
1 for all the leaf blocks (0.00005 x 20000) +
50 for all the table blocks (0.00005 x 1M)
= 53.
 
After the rebuild it would be:
 
1 I/O for the root block +
1 I/O for a branch block +
1 for all the leaf blocks (0.00005 x 10000) +
50 for all the table blocks (0.00005 x 1M)
= 53.
 
Again, no difference …

 
 
OK, let’s increase the number of rows accessed substantially to 10,000 (or approx. 0.5% of the data).
 
Before the rebuild it would be:
 
1 I/O for the root block +
1 I/O for a branch block +
100 for all the leaf blocks (0.005 x 20000) +
5000 for all the table blocks (0.005 x 1M)
= 5102.
 

After the rebuild it would be:
 
1 I/O for the root block +
1 I/O for a branch block +
50 for all the leaf blocks (0.005 x 10000) +
5000 for all the table blocks (0.005 x 1M)
= 5052.
 
Or in percentage terms, a reduction of I/Os of approximately 1%. That’s just 1 tiny little percent …
 
So even an index that accesses 10,000 rows, a reasonable number and at 0.5% a reasonable percentage of the overall table, even an index that has reduced in size by half, a substantial reduction in size, only reduces the overall number of I/Os by an unimpressive 1% for such a query in the above scneario.
 
Would reducing I/Os on such a query by 1% really improve performance “substantially” ? Will users really notice much of a difference ?
 
It’s of course all in the numbers and in how much work the actual index is performing, in how many I/Os are actually performed by the index itself and in how much of a reduction in the overall I/Os an index rebuild will actually contribute. I’ll leave it to you to plug in different ranges of selectivity to see what impact rebuilding such an index with the above characteristics might have.
 
The point is that for the vast majority of index related queries, most of the work is performed in getting the data out of the table, not the index.
 
Therefore, reducing the size of an index, even by possibly a substantial amount, may not necessarily reduce the overall I/Os associated with a query if the index only performs a tiny fraction of all the work. You could eliminate the index entirely and providing Oracle could still magically retrieve just the 0.5% of rows of interest in the above example, performance for such a query would unlikely improve “significantly”.
 
So not only must an index reduce in size but the activities associated with directly reading the index must constitute a significant proportion of the overall work (eg. fast full index scan, index only scans, etc.) or something else must have changed for performance to have improved “significantly”.

Larger Block Tablespace For Indexes Revisited Part III (Prove Yourself) March 2, 2009

Posted by Richard Foote in Oracle Indexes, Oracle Myths, Index Height, Index Block Size, Index Internals, Index Rebuild.
10 comments

Time to look a little at an Index Fast Full Scan (IFFS) with respect to moving indexes into a larger block tablespace.

To start, a few points about an IFFS. When performing an IFFS, Oracle will read each and every block in the index structure, including all branch and leaf blocks (up to the HWM), using multi-block read operations. So although an IFFS has its place, it’s a relatively expensive operation, especially if the index is large, as it needs to read all blocks in the current index structure. Therefore, it’s not generally considered a “common” operation, as in traditional index range scans, especially in OLTP environments. Effectively, an IFFS is the index equivalent of a Full Table Scan (FTS) and is performed in a similar fashion. During an IFFS, Oracle basically treats the index as if it were an smaller version of the table from which it can extract the necessary data.

So if an IFFS were indeed to be very common and could be performed so much more effectively in a larger block tablespace, this begs the question why not move tables in a larger block tablespace as well, so FTS can have the same benefits as the index. And if you move both tables and indexes into a larger block tablespace, why not create the database in the larger block and have done with it? Which brings us around to the question of selecting an appropriate block size for the database, which is a different discussion to the so-called benefits of just moving indexes into a larger block tablespace. For another day perhaps …

Now, although Robin’s demo clearly shows consistent gets are basically halved when an index is rebuilt with double the block size (which all sounds very impressive), what it doesn’t highlight however is that during an IFFS, approximately the same amount of data is still actually being read. Although there are certainly some efficiencies in having fewer logical reads, if each consistent gets is more expensive while the overall data being read is similar, you’re simply not going to get an enormous performance boost that simply halving consistent gets might suggest. Claims that things will suddenly run twice as fast (or 120 times as fast) purely by moving indexes into a larger block tablespace are shall we say “exaggerated” to say the least. However, as all index blocks within an index are being read with no subsequent table accesses, an IFFS is going to be as good as it gets when we talk about any possible performance improvements of moving indexes into a larger block tablespace.

Again, it’s all very simple to “give it a go” and see for yourself exactly what improvements one might expect. Move an index into a larger block tablespace and see those IFFS fly. Using exactly the same setup from Robin’s demo as in Parts I and II, let’s see the actual differences …

First, get some current session stats:

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session         35856
consistent gets               10685006
physical reads                    2582
index fast full scans (full)     33003

Now execute 1000 IFFS using the index in an 8K block tablespace …
SQL> declare
  2  v_count number;
  3  begin
  4    for i in 1..1000 loop
  5       select /*+ index_ffs(bowie) */ count(*) into v_count from bowie;
  6    end loop;
  7  end;
  8  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:11.23

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session         36952
consistent gets               11106006
physical reads                    2582
index fast full scans (full)     34003

 
Note that response times are roughly 11.23 secs, mostly consisting of CPU at 10.96 secs. Note also consistent gets are 1000 x 421 as one would expect from Robin’s demo. Now lets see how things differ when we move the index into a 16K block tablespace.

 
SQL> alter index bowie_idx rebuild tablespace ts_16k;

Index altered.

 
SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session         43192
consistent gets               12372513
physical reads                    2789
index fast full scans (full)     40003

SQL> declare
  2  v_count number;
  3  begin
  4    for i in 1..1000 loop
  5       select /*+ index_ffs(bowie) */ count(*) into v_count from bowie;
  6    end loop;
  7  end;
  8  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:11.14

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                               VALUE
----------------------------- ----------
CPU used by this session           44260
consistent gets                 12583513
physical reads                      2789
index fast full scans (full)       41003

 
Note there’s only a slight improvement in response times and CPU usage of a couple of percentage points, even though the number of consistent gets has halved. Now your milage may vary a tad but what you will not see is things suddenly using 1/2 the resources or running twice as fast (or running 120 times as fast). Because at the end of the day, both sets of IFFS are reading and processing approximately the same amount of data.

Note also that any such possible minor improvments in IFFS performance is likely going to be cancelled out or more likely overtaken by the increased costs associated with more typical index range scans due to the index not actually reducing in height as discussed in Part II. Again, what’s more common, smaller index range scans or IFFS ?

Robin’s demo and the demo above however assumes the index is fully cached, with no physical I/O (PIO) operations being performed. Now as an IFFS needs to read the entire index, it’s quite likely that an IFFS would require some physical I/O, especially if the index is large. Surely then, if an index is in a larger block tablespace, such physical I/Os would be more efficient because Oracle would be able to read more data with a multi-block read based on a larger block  size?

The answer is unfortunately no.  Another (rather poor) analogy to get the point across.

You go to the bank to take some money out. You’re only allowed to take out a maximum of $1000 per day from your account. You ask for this in $50 notes and you get 20 x $50 = $1000 in total. Your mate wants to take out more money and asks for the money in $100 notes. However, as the limit is set to $1000 a day, regardless of the denomination of the bank notes, he simply gets 10 x $100 = $1000. You both end up with exactly the same amount of money, it’s just that you have more bank notes.

An Oracle multi-block read works in exactly the same manner. There’s a maximum amount of data you can read which is calculated by the default block size x db_file_multiblock_read_count. If the default block size is 8K and the db_file_multiblock_read_count = 8, then the maximum size of a multiblock read is 8K x 8 = 64K.

If you attempt to perform a multi-block read using a non-default block size, Oracle simply divides the 64K by the default block size to determine how many blocks to read. So if you now attempt to perform a multi-block read from a 16K tablespace, Oracle will only read 16K x 4 blocks = 64K. The I/O size is the same regardless of the blocksize.

And this makes perfect sense. If you’ve tuned the size of a multi-block read perfectly with the default block size in mind, why would you want to (say) suddenly double this perfect size when you double the block size in another tablespace. If doubling a multi-block read size were to suddenly improved things, why not also double the multi-block read size for the default block size as well …

Again, it’s very easy and simple to test how changing the block size in a specific tablespace makes no difference to the behaviour of an associated multi-block read.

First flush the buffer cache and trace a session, while performing a multi-block read via an IFFS , first with a default 8K block size index:

SQL> show parameter db_file_m

NAME                             TYPE VALUE
----------------------------- ------- -----
db_file_multiblock_read_count integer     8

SQL> alter system flush buffer_cache;

System altered.

SQL> alter session set events ’10046 trace name context forever, level 12′;

Session altered.

SQL> select /*+ index_ffs(bowie) */ count(*) from bowie;
 
The trace file will show that blocks=8 are being read during the IFFS multiblock read operation as the following extract from the trace file highlights:

 
WAIT #2: nam=’db file scattered read’ ela= 22897 file#=7 block#=38929 blocks=8 obj#=95742 tim=1217521768059
WAIT #2: nam=’db file scattered read’ ela= 47158 file#=7 block#=38937 blocks=8 obj#=95742 tim=1217521816003
WAIT #2: nam=’db file scattered read’ ela= 37776 file#=7 block#=38945 blocks=8 obj#=95742 tim=1217521854530

However, when you trace a session as it performs the IFFS with a 16K block

WAIT #1: nam=’db file scattered read’ ela= 55181 file#=6 block#=1030 blocks=4obj#=95742 tim=867071895617
WAIT #1: nam=’db file scattered read’ ela= 68932 file#=6 block#=1034 blocks=4obj#=95742 tim=867071965238
WAIT #1: nam=’db file scattered read’ ela= 67136 file#=6 block#=1038 blocks=4obj#=95742 tim=867072142114
 

We notice that Oracle is now only reading 4 blocks at a time, ensuring that the same 64K is read each time. So increasing the blocksize of an index doesn’t suddenly impact the manner or efficiency in which multi-block PIOs are performed.

Next, we’ll perform a similar test as before, comparing the difference between the 8K and 16K block index during an IFFS but this time with PIOs introduced. There are various ways one could do this. Make the buffer cache too small to fit an index or make the index too big for the buffer cache. Keeping with Robin’s demo, I’ll use exactly the same index definitions but this time run the following procedure in another session that constantly flushes the buffer caches. So in one session:

SQL> begin
  2  for i in 1..10000 loop
  3    execute immediate (‘alter system flush buffer_cache’);
  4  end loop;
  5  end;
  6  /

PL/SQL procedure successfully completed.

 
Meanwhile in another session, run a number of IFFS (200 this time) with an 8K block size index:

 
SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session          4851
consistent gets                1536024
physical reads                  423992
index fast full scans (full)      3205

 
SQL> declare
  2  v_count number;
  3  begin
  4    for i in 1..200 loop
  5     select /*+ index_ffs(bowie) */ count(*) into v_count from bowie;
  6   end loop;
  7  end;
  8  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:35.92

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session          5248
consistent gets                1620224
physical reads                  507651
index fast full scans (full)      3405

 

Note the response time is 35.92 secs and that we used approximately 3.97 secs. This time we have performed a how bunch of PIO operations.

Same thing, this time with the 16K index:

 
SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session          6695
consistent gets                1789531
physical reads                  633216
index fast full scans (full)      4205

 
SQL> declare
  2  v_count number;
  3  begin
  4    for i in 1..200 loop
  5     select /*+ index_ffs(bowie) */ count(*) into v_count from bowie;
  6   end loop;
  7  end;
  8  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:36.59

 
SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 137 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’ or n.name = ‘index fast full scans (full)’);

NAME                             VALUE
---------------------------- ---------
CPU used by this session          7118
consistent gets                1831731
physical reads                  674861
index fast full scans (full)      4405

 
We now note that the 16K block index has the slightly slower response time at 36.59 secs and uses a tad more CPU at 4.23 secs. As soon as we introduce PIOs, the PIOs contribute significantly to the overall costs and may well result in the larger block index being more costly depending on how the PIO is performed. So even in Robin’s example, depending on the nature of PIOs, even an IFFS can potentially run slower with an index in a larger block tablespace. Remembering of course that larger indexes are less likely to be fully cached and are more likely to incur PIOs during an IFFS.

Here’s a demo I’ve used before that uses a different approach to highlight the same issue (which doesn’t rely on a different session “interfering” with things). Another excellent example is this one by Greg Rahn on this OTN thread where he shows an IFFS performing a tad slower in a larger block tablespace. As I’ve been saying, just give it a go and see for yourself.

Perhaps, simply halving the consistent gets when doubling the index block size doesn’t tell the whole story …

The next time you see someone reference Robin’s demo as some sort of “proof” that by moving indexes into a larger block tablespace and (perhaps) reducing the number of consistent reads, the index will somehow be flatter and/or more efficient, just remember that the index may not necessarily be flatter, it might actually have the same height and that subsequent index operations, including index range scans and IFFS could very well be more expensive, not less expensive, to perform.

The next time you see someone claim that by moving indexes into a larger block tablespace, performance has suddenly improved by 100% or that things suddenly run 120 times faster, just ask one simple question. Why ?Ask what else has changed, what else might be contributing to the incredible performance improvements, because when you actually test things out for yourself, you’ll noticed results are not anywhere near as “impressive”.

Larger Block Tablespace For Indexes Revisted: Part II (Money) February 23, 2009

Posted by Richard Foote in Oracle Indexes, Oracle Myths, Index Height, Index Block Size, Index Rebuild.
7 comments

In Part I I looked at Robin Schumacher’s “classic” example of the “so-called” benefits of rebuilding an index into a larger block tablespace. I started by highlighting that by simply rebuilding an index in a larger block tablespace and (say) halving the number of associated index blocks, it doesn’t necessarily mean the index will result in a “flatter structure” , that the index height will reduce. Robin’s demo is in fact a perfect example of this.

Let me start Part II by following this up with a little story …

“I went with a friend of mine to get some cash from the bank the other day in order to buy the latest David Bowie Box-Set. I got my cash in $50 notes but being an efficient, cost saving sort of bloke, my mate got out the same amount of cash in $100 notes. Although we both had the same amount of cash, his wallet was that little bit more compact and “efficient” than mine as he had less actual bank notes to carry.

However, when we got to the record store, we were surprised to discover that the actual “cost” of the David Bowie Box-Set was 2 bank notes of any domination, but with no change being given. Therefore, it cost me 2 x $50 notes to make my purchase. Unfortunately for my mate, it cost him 2 x $100 for the same thing as $100 notes were the smallest denomination he could use. Yes, I was a little bit mean not lending him some of my $50 notes but I was a little disappointed myself for not having any $5 notes on me at the time ;)

OK, it’s not a perfect analogy but you perhaps get the point …

If you have to pay with a quantity of bank notes and you only have larger bank notes, you end up paying more than you would if you could only have paid with the same number of smaller denomination bank notes.

If you have to pay for an index scan in database blocks and you’re forced to use larger index blocks, you actually end up paying more if you have to read the same number of index blocks anyways.

This is one of the potential dangers with rebuilding indexes in a larger block tablespace. And like I said, Robin’s little demo is a perfect example of this. You might indeed reduce and halve the number of index blocks but this might not be sufficient to actually flatten the index structure and reduce the actual height of the index. The height of the index after rebuilding the index can remain the same, so the minimum cost of performing a small range scan increases. Even if you reduce the index height, you can still end up paying more if the savings do not compensate you enough for the additional overhead associated with now having to read and process larger index blocks. 

Therefore, you potentially start paying more for smaller index range scans because you might not actually reduce the number of index blocks you visit for these types of index scans.

Taking exactly the same table/index definitions and data used to replicate Robin’s example in Part I, let’s see if there’s any difference in the costs associated with performing a number of small index range scans after rebuilding the index in a 16K block tablespace.

Again, it’s a simple case of just giving it a go and see for yourself. What resources are used if you perform a series of small index scans ? Do things really run faster ? Do we really use less resources ?  Having rebuilt such an index in a larger block tablespace and halved the number of associated leaf blocks, are we really better off ?

Let’s begin by setting up the same example as Robin’s demo as before …

SQL> create table bowie (id number not null, value varchar2(10));

Table created.

SQL> insert into bowie select rownum, ‘BOWIE’ from dual connect by level <=187200;

187200 rows created.

SQL> commit;

Commit complete.

SQL> create index bowie_idx on bowie(id);

Index created.

SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>’BOWIE’, cascade=>true, estimate_percent=>null, method_opt=> ‘FOR ALL COLUMNS SIZE 1′);

PL/SQL procedure successfully completed.

SQL> select index_name, blevel from user_indexes where index_name = ‘BOWIE_IDX’;

INDEX_NAME BLEVEL
---------- ------
BOWIE_IDX       1

SQL> analyze index bowie_idx validate structure;

Index analyzed.

SQL> select height, btree_space, used_space from index_stats;

HEIGHT BTREE_SPACE USED_SPACE
------ ----------- ----------
     2     3336032    2988168

 

Note the index height when built in an 8K block tablespace is 2 …

Let’s now capture the current amount of CPU used by the session:

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 134 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’);

NAME                          VALUE
------------------------ ----------
CPU used by this session      36555
consistent gets            22520369
physical reads                 3750

 

Now we run a series of small index range scans …

SQL> set timing on

SQL> declare
  2  v_id    number;
  3  v_value varchar2(10);
  4  begin
  5   for o in 1..10 loop
  6    for i in 1..187200 loop
  7    select id, value into v_id, v_value from bowie where id = i;
  8    end loop;
  9  end loop;
 10  end;
 11  /

PL/SQL procedure successfully completed.

Elapsed: 00:01:28.42

 

Let’s see how our resource stats have changed …

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 134 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’);

NAME                          VALUE
------------------------ ----------
CPU used by this session      45346
consistent gets            28140519
physical reads                 3750

 

We note we have used approximately 87.91 CPU seconds. (Note: You can run this a number of times and determine an average figure).

Let’s now rebuild the index again in a 16K block tablespace:

SQL> alter index bowie_idx rebuild tablespace ts_16k;

Index altered.

SQL> select index_name, blevel from user_indexes where index_name = ‘BOWIE_IDX’;

INDEX_NAME BLEVEL
---------- ------
BOWIE_IDX       1

SQL> analyze index bowie_idx validate structure;

Index analyzed.

SQL> select height, btree_space, used_space from index_stats;

    HEIGHT BTREE_SPACE USED_SPACE
---------- ----------- ----------
         2     3351776    2985662 

Note the index height remains at 2 …

If we run the same series of small index scans:

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 134 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’);

NAME                          VALUE
------------------------ ----------
CPU used by this session      45381
consistent gets            28142640
physical reads                 3957

SQL> declare
  2  v_id    number;
  3  v_value varchar2(10);
  4  begin
  5   for o in 1..10 loop
  6    for i in 1..187200 loop
  7    select id, value into v_id, v_value from bowie where id = i;
  8    end loop;
  9  end loop;
 10  end;
 11  /

PL/SQL procedure successfully completed.

Elapsed: 00:01:42.44

SQL> select n.name, s.value from v$sesstat s, v$statname n where s.statistic# = n.statistic# and s.sid = 134 and (n.name = ‘CPU used by this session’ or n.name = ‘consistent gets’ or n.name = ‘physical reads’);

NAME                          VALUE
------------------------ ----------
CPU used by this session      54484
consistent gets            33760690
physical reads                 3957

We note that elapsed times have increased and we have now increased our overall CPU consumption to 91.03 CPU seconds as well.

As we can see, there has been no advantage with rebuilding the in index in the 16K block tablespace for these smaller index scans. In fact, there’s actually been an increase in the overall elapsed times and an increase in the overall CPU. Performance has not improved but has in fact worsened overall for these queries after rebuilding the index in a larger block tablespace.

You begin to get the point …

And of course, indexes are generally far more typically to be used in small index range scan operations than they are in performing Index Fast Full Index Scans. Just compare the numbers of index fast full scans vs. index fetch by key operations in your databases if you want some indication. 

However, Robin’s specific example used a SQL statement that performed an Index Fast Full Scan. Surely, such operations would improve dramatically if indexes were only rebuilt in a larger block tablespace ? Surely such operations would be able to read data more quickly, especially if we have to go to disk, as we would be able to read more data with each associated multiblock read if the index were built in a larger block tablespace ? Surely it would be worth all the extra effort and management considerations ?

Things will run at least 2 times faster, maybe even 150 times faster, right  ;)

We’ll see how the results can be a tad “disappointing” in the next post …

Larger Block Tablespace For Indexes Revisited: Part I (The Tourist) February 18, 2009

Posted by Richard Foote in Index Block Size, Index Height, Oracle Indexes, Oracle Myths.
15 comments

I’ve previously discussed the various issues and myths relating to the so-called benefits of creating a separate, larger block tablespace for indexes and why it’s not recommended and generally a bad idea:

Store Indexes In A Larger Block Tablespace:  Some Thoughts (Big Brother)

Store Indexes In A Larger Block Tablespace: The Multiblock Read Myth (Karma Police)

Store Indexes In A Larger Block Tablespace: The Multiblock Read Myth Part II (The Fly)

Store Indexes In A Larger Block Tablespace: Height Reduction 1/2 Myth (Five Foot One)

Larger Block Tablespace and Small Index Scans – Performance Improvement ? (Let Down)

However, some myths have a habit of lingering ;)

A recent question on reverse indexes (which could so easily have been answered by the person asking the question if they had only just “given it a go”) had me thinking that so many of these myths and misconceptions can be easily challenged and unproven.

Perhaps the most repeated example I’ve seen where the “so-called” benefits of moving indexes into larger block size tablespace is misunderstood is this one by Robin Schumacher. He demonstrates how by moving an index from an 8K block size to a 16K block size, “the amount of logical reads has been reduced in half”, with consistent gets reducing from 421 to 211, during an Index Fast Full Scan operation.

Sounds impressive, but only if one doesn’t understand what the numbers actually represent and if one doesn’t understand what Oracle actually does under the covers. In actual fact, the reduction in consistent gets in this specific example is somewhat meaningless …

Some folks even go on to say that “When can we “prove” a benefit from an index rebuild?  Here, Robin Schumacher proves that an index that is rebuilt in a larger tablespace will contain more index entries be block, and have a flatter structure”.

So I thought I might demonstrate just how easy it is to “give it a go” and see for yourself whether or not these sorts of claims are actually true.

In Part I, I’m just going to focus on the specific claim that this example somehow proves indexes have a “flatter structure” when rebuilt in a larger block tablepsace. That by recreating an index in a larger block tablespace and halving the consistent gets from 421 to 211, the index will somehow have a “flatter structure” as result.

The key message I want to convey however is how easy it is to actually determine the accuracy of these sorts of claims yourself, simply by “giving it a go”. Trust but verify (or in some cases just verify). I’ll revisit some of the other misconceptions with these claims, such as why the reduction in consistent gets is not as impressive as it sounds, in later posts.

The first thing we need to do is reproduce the example and test the results for ourselves. Unfortunately we don’t have a script to reproduce the data used by Robin but we have enough clues at hand to reproduce the same demonstration. We need to basically create an index in an 8K block that performs 421 consistent gets during an Index Fast Full Scan when performing a count(*)SQL operation. So with a little bit of experimenting with different volumes of data, inserting 187,200 numbers into an index produced the necessary volume of data to replicate the scenario. Note: your mileage may vary slightly depending on database version, tablespace options, the specific query you use to test the results, etc.

SQL> create table bowie (id number not null, value varchar2(10));

Table created.

SQL> insert into bowie select rownum, ‘BOWIE’ from dual connect by level <=187200;

187200 rows created.

SQL> commit;

Commit complete.

SQL> create index bowie_idx on bowie(id);

Index created.

SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>’BOWIE’, cascade=>true, estimate_percent=>null, method_opt=> ‘FOR ALL COLUMNS SIZE 1′);

PL/SQL procedure successfully completed.

As in Robin’s example, running the following simple count(*) SQL statement a couple of times to cache the data produced the following results:

SQL> select /*+ index_ffs(bowie) */ count(*) from bowie;

Execution Plan
-------------------------------------------
Plan hash value: 1410776261
-------------------------------------------
| Id  | Operation             | Name      |
-------------------------------------------
|   0 | SELECT STATEMENT      |           |
|   1 |  SORT AGGREGATE       |           |
|   2 |   INDEX FAST FULL SCAN| BOWIE_IDX |
-------------------------------------------
Statistics
----------------------------------------------------------
  0  recursive calls
  0  db block gets
421  consistent gets
  0  physical reads
  0  redo size
412  bytes sent via SQL*Net to client
396  bytes received via SQL*Net from client
  2  SQL*Net roundtrips to/from client
  0  sorts (memory)
  0  sorts (disk)
  1  rows processed

 

OK, so now we have an index that produces 421 consistent gets when performing an Index Fast Full Scan when performing a count(*) SQL operation.

Let’s now see look at the height and size of such an index …

SQL> select index_name, blevel from user_indexes where index_name = ‘BOWIE_IDX’;

INDEX_NAME BLEVEL
---------- ------
BOWIE_IDX       1

SQL> analyze index bowie_idx validate structure;

Index analyzed.

SQL> select height, btree_space, used_space from index_stats;

HEIGHT BTREE_SPACE USED_SPACE
------ ----------- ----------
     2     3336032    2988168

OK, so the index has a height of 2 (or a blevel of 1).

So would rebuilding such an index in a 16K block tablespace really give the index a “flatter structure” ? Will it really reduce the height of the index ? Well, let’s give it a go and see …

SQL> alter index bowie_idx rebuild tablespace ts_16k;

Index altered.

Let’s ensure our test case matches the one used by Robin and see if the number of consistent gets drops as expected by running the same select count(*) statement a number of times:

SQL> select /*+ index_ffs(bowie) */ count(*) from bowie;

Execution Plan
----------------------------------------------------------
Plan hash value: 1410776261
-------------------------------
| Id  | Operation             |
-------------------------------
|   0 | SELECT STATEMENT      |
|   1 |  SORT AGGREGATE       |
|   2 |   INDEX FAST FULL SCAN|
-------------------------------
Statistics
----------------------------------------------------------
  0  recursive calls
  0  db block gets
211  consistent gets
  0  physical reads
  0  redo size
412  bytes sent via SQL*Net to client
396  bytes received via SQL*Net from client
  2  SQL*Net roundtrips to/from client
  0  sorts (memory)
  0  sorts (disk)
  1  rows processed

Indeed it does, consistent gets have indeed reduced from 421 down to 211, exactly as in Robin’s example. Exciting stuff  !! Well, not really, I’ll demonstrate later why these numbers don’t actually mean as much as they appear…

Let’s see if indeed the index does have a “flatter structure” …

SQL> select index_name, blevel from user_indexes where index_name = ‘BOWIE_IDX’;

INDEX_NAME BLEVEL
---------- ------
BOWIE_IDX       1

SQL> select height, btree_space, used_space from index_stats;

     HEIGHT BTREE_SPACE USED_SPACE
---------- ----------- ----------
         2     3351776    2985662

No !!

The index in the 16K block tablespace does not have a flatter structure. In fact the index has exactly the same height of 2 as it did previously and practically the same amount of index space.

As you can see, it’s very easy to give it a go, to test and validate these types of claims yourself. So no, even Robin’s “infamous” test case does not in fact “prove” indexes will have a “flatter structure” if rebuilt in a larger block tablespace. This is the first of the key points I want to get across. Just because you rebuild an index in a larger block tablespace, it doesn’t necessarily mean the index height will reduce or that the resultant index will have a flatter structure. In many many cases, depending on the size of the index and the increase in block size, the height of an index will not reduce at all. I’ve explained why this is the case in some detail in this previous post.

In fact, in some ways, the index height has now INCREASED, not decreased as a result of moving the index to a larger block size. The index had a “flatter structure” when it was in the 8K block tablespace than it does after it was rebuilt in the 16K block tablespace. Robin’s demo is actually a perfect example of this !!

Why ?

Well previously, we had an index structure that had a height of 2 with each “level” being 8K. Now we have an index structure that also has a height of 2 but each level now consists of 16K index blocks. Previously to perform an Index range scan we had to read at least 2 x 8K index blocks or 16K in total. Now we have to read at least 2 x 16K or 32K in total when performing an index range scan.

We’ve just rebuilt the index with larger sized blocks. Imagine a new building that has the same number of floors as the older building but each floor is now double the “size” (height) than it was previously. Although the new building is still a 2 storey building, the actual physical height of the building has just doubled … 

And guess what ? For many many common queries and processes, there’s now potentially an additional overhead associated with having to always read in an index block that is double the size.

To be discussed next …

Updates and Indexes Part II (Down Is The New Up) February 9, 2009

Posted by Richard Foote in Index Delete Operations, Oracle Myths, Update Indexes.
8 comments

In Updates and Indexes Part I, I described how there’s no such things as an “update” operation as such on a index and that an update is effectively a delete followed by an insert operation.

I also showed how Oracle only marks index entries as deleted and doesn’t physically delete the index entry at the time of the transaction.

This leads some folk into (incorrectly) thinking indexes that experience lots of update (or delete) operations need to be frequently rebuilt as the delete space might accumulate and waste space within the index structure over time .

However I also showed how deleted space is actually generally automatically reused by Oracle. For example, all it takes is one subsequent tiny little insert operation into a leaf block for all deleted entries within the leaf block to be automatically cleaned out by Oracle.

Therefore just because an index experiences lots of update activity doesn’t necessarily mean the index needs to be rebuilt. Generally, all deleted space is reused and is effectively nothing but free and available space within the index.

To emphasise this key point and attempt to really get the message across, I thought it might be worth going through a little demo of an index that does indeed experience lots of update operations and see what impact it actually has on the index.

Let’s first just create a simple little table that will have two numeric columns:

SQL> create table bowie (id number, value number);

Table created.

Now let’s populate the first column with a monotonically increasing unique identifier and the second column with a random number:

SQL> insert into bowie select rownum, ceil(dbms_random.value(0,50000))
     from dual connect by level <=50000;

50000 rows created.

SQL> commit;

Commit complete.

Now we’ll create an index on the value column that is populated with a bunch of random numbers:

SQL> create index bowie_idx on bowie(value);

Index created.

Let’s collect some statistics and see how much space is being used by this “freshly” created index:

SQL> analyze index bowie_idx validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used, del_lf_rows from index_stats;

BLOCKS LF_BLKS BTREE_S PCT_USED DEL_LF_ROWS
------ ------- ------- -------- -----------
   128     110  888032       90           0

Specifically note the number of leaf blocks and the overall btree space usage of the index. Also note that as the index has only just been created, we currently have no deleted index entries.

OK, next we’re going to update the index column with a new random number, one row at a time, for effectively 50% of all rows in the entire table. The table currently has 50,000 rows and we will update every other row (that’s 25,000 rows for those mathematically challenged) with a new random value. Now that will be effectively 25,000 separate delete operations and 25,000 separate insert operations.

There are some folk who would think such an exercise would result in 25,000 deleted index entries which need to be cleaned up at some point via an index rebuild.

There are some folk who would think updating 50% of all index column values would result in so much wasted space that the index would grow in an inefficient manner in order to store all these deleted index entries, likely causing performance issues.

There are some folk who think that such a regular and high proportion of updates on an index column in a table is a clear indication that such an index should be rebuilt on a regular basis.

Well, let’s see what happens. First, let’s update every other row in the entire table with a new random number for the value column:

SQL> begin
  2  for i in 1..25000 loop
  3    update bowie set value = ceil(dbms_random.value(0,50000)) where id = i*2;
  4    commit;
  5  end loop;
  6  end;
  7  /

PL/SQL procedure successfully completed.

Let’s see how badly the index has been impacted:

SQL> analyze index bowie_idx validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used, del_lf_rows from index_stats;

BLOCKS LF_BLKS BTREE_S PCT_USED DEL_LF_ROWS
------ ------- ------- -------- -----------
   128     110  888032       90          60

How interest !!

The first thing to note is that there aren’t actually 25,000 deleted index entries at all, even though we’ve just updated 25,000 index entries. There are just 60 deleted entries currently in the index. Just 60, that’s it !!

Why ?

Because the index is effectively just a random based index and while we may update (and hence effectively delete) an index entry from a specific leaf block, at some later time we’re likely to insert another index entry into this same leaf block, thereby cleaning out any deleted entries it may contain. Effectively, almost all the deleted index entries are being automatically cleaned out by subsequent random inserts throughout the index structure.

The relative handful of currently marked deleted index entries (60) happen to exist in leaf blocks that have not had a subsequent insert since the last delete operation in the specific leaf block. But even these deleted entries will eventually be cleaned out and the space reused by any other subsequent inserts in the specific leaf blocks.

The deleted space is simply not an issue, the vast majority of it has been cleaned out and reused and those entries that haven’t yet been cleaned out will likely be reused by subsequent insert operations anyways.

If we look at the actual space used by the index, after 50% of all index entries have been updated and we note that the index has not changed at all. It has exactly the same number of leaf blocks and is using exactly the same amount of btree space. (Note: because the index values are random, it’s likely that the new values will not be exactly distributed as it was previously and there might be the possibility that the odd index leaf block could fill and split as it contains more associated values than previously. Regardless, as the index grows with more index entries, this is not going to be an issue anyways).

There is nothing “wrong” or inefficient or fragmented with this index, even though we’ve just updated (and hence deleted) 50% of all its index entries.

With deleted index entries being trivial and likely to be reused at some later time anyways and with the index having the same leaf blocks and btree space as it did when the index was newly created, rebuilding such an index would be a total and utter waste of time and resources.

Again, just because an index column is frequently updated, it doesn’t necessarily mean the index is a candidate for a periodic index rebuilds. Any such suggestions are simply misguided …

Updates and Indexes Part I (Fashion) January 17, 2009

Posted by Richard Foote in Index Delete Operations, Oracle Indexes, Oracle Myths, Update Indexes.
27 comments

Let’s start with a few basic concepts.

Simplistically, Oracle doesn’t generally care where or in what order data is stored in heap tables, unless the table is partitioned or clustered. Therefore, when an update operation is performed on a column value, Oracle can basically make the change “in place” within the table block. If the value of a name column changes from say “BOWIE” to a new value of “FOOTE”, Oracle can simply just make the necessary change to the specific table block. Only if the new value is larger and there’s not sufficient space within the current table block for the new value does the picture get a little more complicated, with Oracle having to migrate the row.

However, the story isn’t quite so simple for corresponding changes to index column values. The key difference (no pun intended) is that unlike most heap tables, the location and order of the data within the index is very much an issue. All index entries must be and must always be in the order of the indexed columns. Otherwise, it would be impossible for Oracle to efficiently navigate down the index structure to find within the index all the  necessary indexed values required for an index range scan. Imagine for one moment how difficult it would be to find someones phone details if the telephone book wasn’t ordered on names or to use an index in the back of a reference book if the index wasn’t ordered.

The order of an index is crucial and must always be in the order of the indexed column values. Therefore, if a specific indexed value of  say “BOWIE” is updated to a new value of “FOOTE”, Oracle can’t simply make the change “in place” within the leaf block as this would result in the index order no longer being maintained. The new value of “FOOTE” would be surrounded by index values starting with “B” and there would be no easy way to subsequently find it within the index. It would likely not even be in the same index leaf block as those other index entries beginning with “F” where the new value should actually reside.

Therefore, Oracle doesn’t actually “update” an index value. The old index entry is marked as deleted and the a new index entry is inserted in the appropriate location within the index to ensure the index order is maintained. So the update of an index value is effectively a delete operation followed by an insert.

Simple example to demonstrate. Let’s first create a little table and index.

SQL> create table test_update (id number, name varchar2(10));

Table created.

SQL> create index test_update_idx on test_update (name);

Index created.

Now, let’s insert one row.

SQL> insert into test_update values (1, ‘BOWIE’);

1 row created.

SQL> commit;

Commit complete.

Let’s have a quick look at a block dump of our little index. As the index only contains the one index entry, the index will only consist of a single leaf block. This specific block is located next to the segment header of the index.

SQL> select header_file, header_block from dba_segments where segment_name = ‘TEST_UPDATE_IDX’;

HEADER_FILE HEADER_BLOCK
----------- ------------
          7       118537

We just need to add 1 to the header_block to get us the specific block id we need to dump.

SQL> alter system dump datafile 7 block 118538;

System altered.

Following is the portion of interest from the index block dump:

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0×26
kdxcofeo 8021=0x1f55
kdxcoavs 7983
kdxlespl 0
kdxlende 0
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 0
kdxlebksz 8036
row#0[8021] flag: ——, lock: 2, len=15
col 0; len 5; (5):  42 4f 57 49 45
col 1; len 6; (6):  01 c1 ce 8a 00 00

—– end of leaf block dump —–

We note for now that the index indeed just has the one index entry (with a row# 0).

Let’s now update this indexed column and see what impact this has in the index.

SQL> update test_update set name = ‘ZIGGY’ where id = 1;

1 row updated.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 7 block 118538;

System altered.

New block dump follows:

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 2
kdxcofbo 40=0×28
kdxcofeo 8006=0x1f46
kdxcoavs 7966
kdxlespl 0
kdxlende 1
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 0
kdxlebksz 8036
row#0[8021] flag: —D–, lock: 2, len=15
col 0; len 5; (5):  42 4f 57 49 45
col 1; len 6; (6):  01 c1 ce 8a 00 00
row#1[8006] flag: ——, lock: 2, len=15
col 0; len 5; (5):  5a 49 47 47 59
col 1; len 6; (6):  01 c1 ce 8a 00 00
—– end of leaf block dump —–

We notice of few interesting things. Firstly, even though we’ve only ever inserted the one row in the table, the index now actually has two index entries (note the index row count kdxconro value has increased from 1 to 2 and we can see two actual index entries, row#0 and row#1).

Another interesting point is that the initial index entry has been marked as deleted (via the “D” flag highlighted in blue) and that the deleted row count kdxlende value has gone up to 1.

So yes indeed, an update index operation actually consists of a delete operation followed by an insert, even if the new index value were to reside in the same index leaf block as the previous value. Note the deleted index entry isn’t actually physically deleted, it’s only marked as deleted and so continues to consume space within the index leaf block.

If we look at the index_stats for this index:

SQL> analyze index test_update_idx validate structure;

Index analyzed.

SQL> select del_lf_rows from index_stats …

DEL_LF_ROWS
-----------
          1

We notice that we do indeed have a deleted index entry listed in the statistics.

Now it’s at this point of the story when some people go “Aaah haa !! So if we have lots of updates, we effectively have lots deletes and we therefore have lots of deleted space that wastes space within the index. Therefore we would need to periodically rebuild such an index as the deleted space will just continue to grow, making the index larger and less efficient over time”.

Not necessarily.

The point that many don’t quite understand is that this “wasted” delete space can be subsequently reused by Oracle. It’s just free space that in the vast majority of indexes is automatically cleaned out and reused by Oracle.

To illustrate, let’s now insert a second row into this table. Notice the new row has an indexed value that is completely different to the previous values but because we still have available space in our current index leaf block, Oracle will simply insert the new value in this leaf block as well.

SQL> insert into test_update values (2, ‘PINK FLOYD’);

1 row created.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 7 block 118538;

System altered.

Let’s have a look at our block dump now …

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 2
kdxcofbo 40=0×28
kdxcofeo 7986=0x1f32
kdxcoavs 7961
kdxlespl 0
kdxlende 0
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 0
kdxlebksz 8036
row#0[7986] flag: ——, lock: 2, len=20
col 0; len 10; (10):  50 49 4e 4b 20 46 4c 4f 59 44
col 1; len 6; (6):  01 c1 ce 8a 00 01
row#1[8006] flag: ——, lock: 0, len=15
col 0; len 5; (5):  5a 49 47 47 59
col 1; len 6; (6):  01 c1 ce 8a 00 00
—– end of leaf block dump —–

Now isn’t that interesting. The previously marked deleted index entry has disappeared. It’s been automatically cleaned out by Oracle and the deleted row count value kdxlende is now back to 0

We only have an index row count  kdxconro value of 2 for the two actual index entries corresponding to the two rows in the table. The previously deleted index entry is no longer recorded or stored in any way within the index.

When the new index entry was inserted, Oracle basically needed to reorganise the index leaf block to accommodate for the new index entry and automatically cleaned out any deleted index entries there may have been in the leaf block in the process. That’s all it takes to clean out deleted index entries from an index leaf block, just one subsequent insert in the leaf block.

If we now look at the index_stats …

SQL> analyze index test_update_idx validate structure;

Index analyzed.

SQL> select del_lf_rows from index_stats;

DEL_LF_ROWS
-----------
          0

We note that indeed, no deleted index entries are now stored within the index. Periodically rebuilding such an index may not be necessary after all …

Regular readers will recall I’ve previously discussed how deleted index entries are generally cleaned out by Oracle automatically. Sometimes, it’s worth hammering the point a few times ;)

More on the topic of update operations and indexes to come …

How To Rebuild And Make An Index Bigger, Not Smaller (Carry That Weight) January 13, 2009

Posted by Richard Foote in Index Shrink, Oracle Myths.
22 comments

I sometimes hear suggestions along the lines of:

 “when you rebuild an index, at least you make the index as small and efficient as possible, even if it doesn’t necessarily improve performance”

or

“when you rebuild an index, at least you’ll always save some space and storage if nothing else”.

However, this of course is not necessarily the case. There are many scenarios where by rebuilding an index, you can actually make the index bigger, not smaller, you can make the index use more storage, not less storage, you can make the index less efficient, not more efficient and hence you can make the exercise worse than useless, not just useless.

It all depends.

Here are just a few little examples whereby rebuilding the index has resulted in a larger index than it was before the index was rebuilt. Note in all of these scenarios, I’ll be sticking with the default PCTFREE value of 10%, which is by far the most commonly set PCTFREE value of every Oracle index out there in existence.

The first example is very simple and so very common. It’s simply an index on a monotonically increasing value, as used by many Primary Keys out there in the “real world”. 

First we create the table and associated index. Nice and simple …

SQL> create table bowie (id number);

Table created.

SQL> create index bowie_i on bowie(id);

Index created.

We now populate the index with a whole bunch of monotonically increasing values …

SQL> insert into bowie select rownum from dual connect by level <=1000000;

1000000 rows created.

SQL> commit;

Commit complete

Let’s see how big our index might now be …

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2048    1999    16024128      100

Note the index has a “perfect” PCT_USED value of 100%, you can’t get any better than that !! Why ? Because as the index is on a monotonically increasing value, all the inserts take place on the “right hand side” of the index and Oracle performs it’s 90-10 index block split operation, rather than the 50-50 block split. 

If we try and rebuild such an index …

SQL> alter index bowie_i rebuild;

Index altered.

SQL> analyze index bowie_i validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2304    2226    17848160       90

We notice that the index is now actually bigger, not smaller. Not only that, but we have now introduced 10% free space that will likely not be reused.

 

Another example.

This time we build a similar table but this time populate it with randomly generated numbers, not monotonically increasing values.

SQL> drop table bowie;

Table dropped.

SQL> create table bowie (id number);

Table created.

SQL> insert into bowie select ceil(dbms_random.value(0,100000)) from dual connect by level <=1000000;

1000000 rows created.

SQL> commit;

Commit complete.

Let’s now create an index on this numeric column …

SQL> create index bowie_i on bowie(id);

Index created.

Let’s now add more random numbers to the table …

SQL> insert into bowie select ceil(dbms_random.value(0,100000)) from dual connect by level <=50000;

50000 rows created.

SQL> commit;

Commit complete.

OK, let’s check out the index …

SQL> analyze index bowie_i validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2304    2214    17760192       95

OK, the index has a PCT_USED value of 95%.

However, after the rebuild …

SQL> alter index bowie_i rebuild;

Index altered.

SQL> analyze index bowie_i validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2432    2324    18640192       90

The index is now bigger, with more leaf blocks and a worse PCT_USED value.

If we rebuild an index before the index has had the opportunity to use its available free space, an index rebuild can introduce more free space, not less. Now this may not necessarily be a bad thing, but it’s another example of the index potentially being bigger, not smaller after a rebuild.

 

Here’s yet another example.

Similar to the previous example, but this time we’ll throw in a whole bunch of update statements as well. As we know, an update statement within an index is effectively a delete statement, followed by an insert statement. All that “wasted” deleted space should be nicely cleaned up after an index rebuild, resulting in a smaller index structure. Or so we might think …

First, create and populate the table with randomly generated numbers similar to before …

SQL> drop table bowie;

Table dropped.

SQL> create table bowie (id number, value number);

Table created.

SQL> insert into bowie select rownum, ceil(dbms_random.value(0,100000)) from dual connect by level <=1000000;

1000000 rows created.

SQL> commit;

Commit complete.

Now let’s create the index and aftewards insert a bunch of new rows as before.

SQL> create index bowie_i on bowie(value);

Index created.

SQL> insert into bowie select rownum+1000000, ceil(dbms_random.value(0,100000)) from dual connect by level <=50000;

50000 rows created.

SQL> commit;

Commit complete.

Now let’s run a little procedure that will update roughly 10% of all the data (a  reasonable overall percentage), with new random numbers.

SQL> begin
  2  for i in 1..105000 loop
  3    update bowie set value = ceil(dbms_random.value(0,100000))
  4    where id = i;
  5    commit;
  6  end loop;
  7  end;
  8  /

PL/SQL procedure successfully completed.

OK, let’s now look at the index, wasted space and all …

SQL> analyze index bowie_i validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2304    2234    17952320       94

Interestingly, even with all the random updates (and associated deletes), the index is relatively efficient at 2234 leaf blocks.

Let’s see how many of the 105,000 updated entries have remained deleted:

SQL> select del_lf_rows from index_stats;

DEL_LF_ROWS
-----------
       1129

Not many at all, just 1129 deleted entries remain, less than 1% !!

In fact, the vast majority of the deleted entries have all been automatically cleaned out by Oracle. Much more on the myth that an index with lots of update activity needs to be rebuilt to come in the near future …

Let’s rebuild this index now.

SQL> alter index bowie_i rebuild;

Index altered.

SQL> analyze index bowie_i validate structure;

Index analyzed.

SQL> select blocks, lf_blks, btree_space, pct_used from index_stats;

BLOCKS LF_BLKS BTREE_SPACE PCT_USED
------ ------- ----------- --------
  2432    2324    18640192       90

The index is again bigger than it was previously. Even after we’ve added in a bunch of rows and updated 10% of the entire table.

The point here of course is that even if an index is heavily updated, the deleted space can generally be subsequently reused. Like I said, more on all this in a future post.

For now however, just note that rebuilding an index doesn’t necessarily mean the resultant index will now be smaller or more efficient or more pristine. In many cases, rebuilding an index blindly can result in a larger index structure than it was prior to the rebuild.

Bear this in mind the next time you read or hear someone suggest an index rebuild will always ensure the new index is smaller and as efficient as possible …

Deleted Index Entries Part IV (Breaking Glass) June 25, 2008

Posted by Richard Foote in Index Delete Operations, Oracle General, Oracle Indexes, Oracle Myths.
6 comments

Yet another method of cleaning out deleted space Oracle has up its sleeve is the recycling of index blocks that contain nothing but deleted index entries.

In some cases, it’s possible for an index block to contain no current index entries with all the corresponding index entries within the index block having been deleted. The index block may be totally empty of index entries or it may contain just deleted index entries.

Once an index block has no current index entries, Oracle places the block on the segment freelist and is now a candidate block to be recycled and reused elsewhere within the index structure after a subsequent index block split operation.

When recycled, the index block becomes “unattached” from its current location within the logical index structure and is reallocated elsewhere within the logical index structure as the new index block in an index block split operation.

Any previously deleted index entries are removed and the contents of the index block are replaced with new index entries associated with its new logical location within the index structure.

A simple little demo to illustrate this process.

First, I create a simple table and associated index and populate it with a 10000 rows:

SQL> CREATE TABLE test_empty_block (id NUMBER, name VARCHAR2(30));

Table created.

SQL> INSERT INTO test_empty_block SELECT rownum, ‘BOWIE’ FROM dual
     CONNECT BY level <= 10000;

10000 rows created.

SQL> COMMIT;

SQL> CREATE INDEX test_empty_block_idx ON test_empty_block(id);

Index created.

I next delete the vast majority of the rows, leaving only a handful behind that are likely only found in the last one or maybe two leaf blocks within the index. All the other index leaf blocks therefore only contain nothing but deleted index entries:

SQL> DELETE test_empty_block WHERE id between 1 and 9990;

9990 rows deleted.

SQL> COMMIT;

Commit complete.

If we look at some statistics, we’ll find we have lots of deleted row entries that are all found in leaf blocks that are totally empty, except perhaps the right most leaf block within the index:

SQL> ANALYZE INDEX test_empty_block_idx VALIDATE STRUCTURE;

Index analyzed.

SQL> SELECT lf_blks, del_lf_rows FROM index_stats;

LF_BLKS DEL_LF_ROWS
------- -----------
     21        9990 

We next insert a bunch of new rows into the table, but importantly, all these new rows have index entry values that are greater than the previous values. Therefore, all these new index entries will be inserted into the right most side of the index structure and not into the index where we have nothing but the previously deleted index entries. 

Oracle will need to allocate new index leaf blocks to accommodate these new index entries, but from where will Oracle get these new index blocks ?

SQL> INSERT INTO test_empty_block SELECT rownum+20000, ‘ZIGGY’
     FROM dual CONNECT BY level <= 10000;

10000 rows created.

SQL> COMMIT;

Commit complete.

If we now look at the index statistics, we notice something very interesting:

SQL> ANALYZE INDEX test_empty_block_idx VALIDATE STRUCTURE;

Index analyzed.

SQL> SELECT lf_blks, del_lf_rows FROM index_stats;

LF_BLKS DEL_LF_ROWS
------- -----------
     21           0

The number of deleted leaf entries has disappeared back to zero and the number of allocated leaf blocks has remained the same at 21.

Oracle has both removed the previously deleted index entries and has also recycled all the previously empty leaf blocks and reused them again to accommodate the new index entries. The index is effectively the same size as it was previously even though we’ve added new values that were greater than the previously deleted values.

So index blocks that are totally empty or contain nothing but deleted index entries become “free” again, are placed on the freelist within the index segment and can be reused or recycled again somewhere else within the logical index structure at some later point in time.

Again, yet another example of Oracle cleaning out these unwanted deleted index entries for us.

However, these empty index blocks can potentially be problematic and can cause performance issues until eventually they actually get reused and recycled.

But that’s a topic for another day.

Deleted Index Entries Part III (Slip Away) June 23, 2008

Posted by Richard Foote in Oracle General, Oracle Indexes, Oracle Myths.
5 comments

Another little post while I look after some unwell munchkins …

I’ve already looked at the most common example of when Oracle will automatically clean out deleted index entries, that being any subsequent insert into a leaf block will clean out the deleted entries that may exist from the associated leaf block.

Another example of Oracle automatically removing deleted index entries is that associated with a variation of delayed block cleanout. If an Oracle index block with deleted index entries is written to disk before the associated transaction performing the index delete operation is committed, the next time the index block is accessed, Oracle will not only clean out the transaction details from the index block (such as the lock byte) but the deleted index entries themselves may also be cleaned out as well.

This scenario is most likely to occur during large or long running transaction operations (such as batch operations) where many rows are likely to be accessed and/or modified and the associated modified index blocks may get aged out of the buffer cache and written to disk before the transaction ends via the COMMIT.

Note this delayed clean out does not require the index block to be accessed via a subsequent DML operation, even a simple SELECT statement will be sufficient to perform the necessary clean out of deleted index entries.

To illustrate this behaviour, basically create a table with a bunch of rows, deleted some of them but flush the buffer cache prior to issuing the commit on the delete.

SQL> CREATE TABLE del_stuff (id NUMBER, name VARCHAR2(30));

Table created.

SQL> CREATE INDEX del_stuff_i ON del_stuff(id);

Index created.

SQL> INSERT INTO del_stuff SELECT rownum, ‘Bowie’ FROM dual CONNECT BY level <=1000;

1000 rows created.

SQL> COMMIT;

Commit complete.

Next, deleted say 1/2 of the rows from the table.

SQL> DELETE del_stuff WHERE mod(id,2) = 0;

500 rows deleted.

At this point, we flush the associated blocks to disk to simulate a large or long running transaction is which blocks may be aged from the buffer cache and written to disk before the COMMIT is performed.

SQL> ALTER SESSION SET EVENTS ‘immediate trace name flush_cache’;

Session altered.

in 9i, or since 10g:

SQL> ALTER SYSTEM FLUSH BUFFER_CACHE;

System altered.

It’s only at this point after the blocks are flushed to disk that the COMMIT is performed.

SQL> COMMIT;

Commit complete.

Once the index blocks are subsequently accessed, we notice the deleted index entries may have already been cleaned out …

NOTE: The following results do not consistently occur if the index consists of just a single block (the root block is a “special” case),  but does appear to be more consistent if the index has a blevel of one or more (as in the demo) and as would be more typical with indexes involved in long running transactions.

A view of INDEX_STATS after a ANALYZE … VALIDATE STRUCTURE command will show the following:

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN
------- ----------- ---------------
    500           0               0

Note: There are no deleted index entries, none. They’ve already been cleaned out.

 

A treedump will show the following:

 

—– begin tree dump

leaf: 0x1402e4a 20983370 (0: nrow: 500 rrow: 500)

—– end tree dump

 

Note: It only shows 500 rrow and 500 nrow values, clearly highlighting there are no deleted index entries.

 

A partial index block dump will show the following:

 

kdxlende 0

 

The deleted index entry count kdxlende is 0, with no deleted index entries existing in the block. None.

 

All the deleted index entries have already been cleaned out, with not a subsequent DML operation in sight.

 

So yes, again Oracle can clean out deleted index entries as part of it’s general processing so that the need to do so manually via an index rebuild, coalesce or shrink is a somewhat rare occurrence.

 

But wait, there’s still more cases to come when Oracle will simply automatically remove deleted index entries entries …

Deleted Index Entries – Part I (Let It Be) June 8, 2008

Posted by Richard Foote in Index Delete Operations, Oracle General, Oracle Indexes, Oracle Myths.
9 comments

Just before I hop on a plane to do some training in Europe, thought I might begin a little series on deleted space within an index. I’ll begin with a short piece on how we can determine what deleted space an index may currently have before beginning a discussion on whether this deleted space can indeed be reused by Oracle.

Generally speaking, when an index entry is deleted, Oracle doesn’t physically remove the index entry, it’s simply marked as deleted. It’s another case of Oracle putting off what could be an expensive operation for the current transaction and leaving any potential clean up operations to future processes. However, there’s often some confusion whether these deleted index entries remain “deadwood” within the index structure or whether they are somehow cleaned out later and the space potentially reused by subsequent inserts in the relevant index block.

To set the scene, we begin by creating a very simple scenario. Here we create a little table and associated index, insert a single row, commit it and then delete and commit the row afterwards. We can then have a bit of a look around to see how this deleted index entry is recorded by Oracle.

 SQL> CREATE TABLE test_delete (id NUMBER, name VARCHAR2(10));

Table created.

 

SQL> CREATE INDEX test_delete_idx ON test_delete (name);

 

Index created.

 

SQL> INSERT INTO test_delete VALUES (1, ‘BOWIE’);

 

1 row created.

 

SQL> COMMIT;

 

Commit complete.

 

SQL> DELETE test_delete WHERE id = 1;

 

1 row deleted.

 

SQL> COMMIT;

 

Commit complete.

 

We begin by looking at statistics related to the deleted index entries within the INDEX_STATS view.

 

SQL> ANALYZE INDEX test_delete_idx VALIDATE STRUCTURE;

 

Index analyzed.

 

SQL> SELECT lf_rows, del_lf_rows, del_lf_rows_len FROM index_stats;

 

   LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN
---------- ----------- ---------------
         1           1              17 

 

So yes, the one and only index entry is a deleted index entry.

 

We can also see how many current deleted entries we have by looking at an index tree dump of the index.

 

SQL> SELECT object_id FROM dba_objects WHERE object_name = ‘TEST_DELETE_IDX’;

 

 OBJECT_ID
----------
     61198

 

SQL> ALTER SESSION SET EVENTS ‘immediate trace name treedump level 61198‘;

 

Session altered.

 

Following is the index tree dump generated by the above operation.

 

—– begin tree dump
leaf: 0x14008d2 20973778 (0: nrow: 1 rrow: 0)
—– end tree dump

 

We notice that the rrow count which is the number of non-deleted index row entries is 0 but the nrow count which is the total index row entries, including deleted entries is 1. Therefore, yes the index currently consists of just the one deleted index row entry.

 

We can also view the deleted index details by performing a dump of the associated index block.

 

SQL> SELECT file_id,block_id FROM dba_extents WHERE segment_name=’TEST_DELETE_IDX’;

 

   FILE_ID   BLOCK_ID
---------- ----------
         5       2257

 

SQL> ALTER SYSTEM DUMP DATAFILE 5 BLOCK 2257;

 

 

System altered.

Below is an  extract from the above index block dump:

     Itl                    Xid                                    Uba                Flag  Lck            Scn/Fsc

0×01   0×0000.000.00000000  0×00000000.0000.00  —-      0  fsc 0×0000.00000000

0×02  0×0008.024.0000075b  0x00804e29.0078.0b  –U-      1  fsc 0×0011.00000000

  ……

kdxlende 1

kdxlenxt 0=0×0

kdxleprv 0=0×0

kdxledsz 0

kdxlebksz 8036

row#0[8021] flag: —D–, lock: 2, len=15

col 0; len 5; (5):  42 4f 57 49 45

col 1; len 6; (6):  01 40 10 0a 00 00

 

From the above, kdxlende 1 is a count of the deleted index entries. The index entry has a D flag set, signifying that the index entry has been deleted. Also note that the index entry was locked and deleted by the ITL entry associated with ITL number 2.

 

So yes, when we perform a delete that results in the deletion of an index row entry, the deleted index entry is marked as deleted but is not physically cleaned out at the time of the delete. All the above checks confirm this current state of the index.

 

The key question is therefore, are these deleted index entries ever reused/removed, or are they forever “deadwood” that would require a periodic rebuild of the indexes to clean out ?

 

Answer coming soon …

Follow

Get every new post delivered to your Inbox.

Join 1,715 other followers