Infrastructure at your Service

Franck Pachot

Covering indexes in Oracle, and branch size

By April 13, 2018 Oracle No Comments

By Franck Pachot

.
A covering index is an index that contains all the columns required by your query, so that you don’t have to do a TABLE ACCESS BY INDEX ROWID, which is the major cost of an index range scan. You don’t need any special feature to do that in Oracle. Just add the required columns at the end of the index. In the execution plan you will see the columns used as index keys for the range scan displayed in ‘access’ predicates, and the further filtering done on the remaining columns with ‘filter’ predicates. The ‘projection’ shows the columns that are returned in the rowset result.
However you may have seen that SQL Server has a special ‘INCLUDE’ keyword to separate those non-key columns added only for filtering or projection but not for access. What does it bring that Oracle doesn’t have?

An index entry is composed of a key and data associated to the key. The index is sorted on the key. The data for each key have no special order, like in a heap table. The idea of the SQL Server INCLUDE keyword is to separate the columns belonging to the key and the columns belonging to the data. It is not mandatory. You can add all columns to the key but depending on the implementation, the benefit can be:

  • some data types may not be allowed in the key but allowed as data
  • sorting the data when not required may be a performance overhead
  • there can be limitations on the size of the key
  • having a larger key may require more space in the branches
  • adding sorted columns may change the clustering factor

In Oracle, there are very few data types that cannot be indexed (like LONG). The limitation on the size of the key may come into play for large 12c Extended Datatypes. You can substring them, but that defeats the goal of covering indexes. I see two reasons why ‘INCLUDE’ indexes can be useful. The first reason is about the clustering factor. The second about sorting the whole index entry and referencing it from the branches. I’ll detail those reasons later, but first here is an example.


SQL> create table DEMO (UNIQU ,RANGE ,RANDOM_TEXT ,CONSTANT_TEXT ) as select rownum UNIQU , mod(rownum,4) RANGE , dbms_random.string('u',80) RANDOM_TEXT , lpad('x',80,'x') CONSTANT_TEXT from xmltable('1 to 100000');
Table DEMO created.
SQL> commit;
Commit complete.

This table has an all-distinct-values column UNIQ, a few-distinct-values on (RANGE) and I’ll use them for the key. And I’ve two columns I’ll add as additional column for covering queries: one is with lot of distinct values (RANDOM_TEXT) and the other has few distinct values (CONSTANT_TEXT).
The first rows look like this:


SQL> select * from DEMO order by ROWID fetch first 5 rows only;
  UNIQU   RANGE RANDOM_TEXT                                                                        CONSTANT_TEXT
  -----   ----- --------------------------------------------------------------------------------   --------------------------------------------------------------------------------
      1       1 XCFNWCRCFBEPJPSHREUVVVTBUCCXLZMRPJPNQDTHWYRZRUORBPDOBCIRFHLICETULTCZTMPOCMUNQITV   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
      2       2 XUSPNDOMPQKOIRCVDDTVYAGKRDGIXOSVUNMRAQLSRQGYKOFEXRQMCPXPYZYKRHHKDXGIINOUUAUJOLOO   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
      3       3 ZBCVFTDSRUFIUTSIWOOOBWIRMEFUXNWLADAPUPFNPVYDLPQTOUZVXJKMGIPCGZESXFXOIYVMKNSMMZKB   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
      4       0 VOIRCXFVSRVZQRZDRLQRHZWNGQJAAWJXWXJKRCJVPWYDJSZLJIOEWAMCFSRCUPSPPEKITJYHHOUQSVYQ   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
      5       1 UUSAMEVRWNLPGCUVMJWVVPDAENRYKIWWMIHTUJSZRQASMTYOVQNCGZGZIJZWNSOJVSIBMMUEAXOHJCOA   xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

I’m adding indexes fo access on RANGE as the index key, with only the key, or covering the random or constant text:


SQL> create index DEMO_RANGE                   on DEMO(RANGE)               pctfree 50;
Index DEMO_RANGE created.
SQL> create index DEMO_RANGE_COVERING_RANDOM   on DEMO(RANGE,RANDOM_TEXT)   pctfree 50;
Index DEMO_RANGE_COVERING_RANDOM created.
SQL> create index DEMO_RANGE_COVERING_CONSTANT on DEMO(RANGE,CONSTANT_TEXT) pctfree 50;
Index DEMO_RANGE_COVERING_CONSTANT created.

An additional one adding the unique column in-between:


SQL> create index DEMO_RANGE_COVERING_WITH_PK  on DEMO(RANGE,UNIQU,CONSTANT_TEXT) pctfree 50;
Index DEMO_RANGE_COVERING_WITH_PK created.

And now for access with the unique column as a key:


SQL> create index DEMO_UNIQU_COVERING_RANDOM   on DEMO(UNIQU,RANDOM_TEXT)   pctfree 50;
Index DEMO_UNIQU_COVERING_RANDOM created.
SQL> create index DEMO_UNIQU_COVERING_CONSTANT on DEMO(UNIQU,CONSTANT_TEXT) pctfree 50;
Index DEMO_UNIQU_COVERING_CONSTANT created.

Here are some interesting stats:


SQL> exec dbms_stats.gather_table_stats(user,'DEMO');
PL/SQL procedure successfully completed.
SQL> select index_name,blevel,leaf_blocks,num_rows,clustering_factor from user_indexes where table_name='DEMO' order by 2,3;
INDEX_NAME                       BLEVEL   LEAF_BLOCKS   NUM_ROWS   CLUSTERING_FACTOR
-------------------------------- ------   -----------   --------   -----------------
DEMO_RANGE                            1           353     100000                9757
DEMO_RANGE_COVERING_RANDOM            2          2440     100000               99967
DEMO_RANGE_COVERING_CONSTANT          2          2440     100000                9757
DEMO_UNIQU_COVERING_RANDOM            2          2500     100000                2440
DEMO_UNIQU_COVERING_CONSTANT          2          2500     100000                2440
DEMO_RANGE_COVERING_WITH_PK           2          2565     100000                9757
6 rows selected.

Leaf size

About the size, the covering indexes have approximately the same number of leaf blocks because the included column (RANDOM_TEXT or CONSTANT_TEXT) has the same size (80 bytes). Of course, the non-covering index is smaller (but will need table access to query additional column). The key on UNIQU is slightly larger than the one on RANGE because the numbers go higher. The index with 3 columns is the largest.

Clustering factor

About the clustering factor, there’s one outlier here which deserves an explanation. But before that, you must understand that this higher clustering factor is not important for a query using the covering index, such as a SELECT RANDOM_TEXT WHERE RANGE=0, because in that case you don’t read the table. However for some queries you may cover only the filter predicates and go to the table for projection.
But the big problem is that when you add a column to an index to address a specific query, you don’t want to risk a side effect on another query, and changing the clustering factor is a risk here. One solution is to keep the old non-covering index (DEMO_RANGE) but then the side effect is on DML overhead.

To understand the change in clustering factor we must go deeper on Oracle index key and data implementation. The ‘data’ part exists in Oracle indexes even when not specified explicitely with an INCLUDE clause. The ROWID is the data part. An index entry associates a key (the indexed columns) with a pointer to the table row (the ROWID). At least, this is for UNIQUE indexes where each key is unique.

Non-unique indexes are a special case. Actually, Oracle implements only unique key indexes. When the indexed columns are not unique, the ROWID is stored on the key part of the index entry, and there is no data part. You should read Richard Foote, Differences between Unique and Non-Unique Indexes for detailed explanation.

Branch size

The previous statistics displayed only the number of branch level, which was the same, but we can have more detail about the branch size with an ANALYZE INDEX.

The non-covering index has only one branch block, the root, which references all the 353 leaf blocks containing the 100000 entries, with an average of 5479/352=15 bytes per branch entry:


SQL> analyze index DEMO_RANGE validate structure offline;
Index DEMO_RANGE analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       2      384       353       1375000       352         1          5479               25000       2830616      1380479         49          25000                12502.5                 19             1375000             353

The covering index with lot of distinct values for the non-key columns has more branch blocks, with an average of 34623/2439=14 bytes per branch entry:


SQL> analyze index DEMO_RANGE_COVERING_RANDOM validate structure offline;
Index DEMO_RANGE_COVERING_RANDOM analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       3     2560      2440       9475000      2439         6         34623                   1      19558408      9509623         49              1                      4                  2             9475000            2440

Here the number of branches is higher only because there are more leaves (as we have more columns), but not because of the size in the branch entries, which are even smaller. They are smaller because the branch does not have to store the full value of all columns in order to identify one leaf block. Then, only the first bytes are needed and not the full 80 bytes of them.

The covering index with few of distinct values for the non-key columns has a lot more branch blocks, with an average of 234755/2439=96 bytes per branch entry:


SQL> analyze index DEMO_RANGE_COVERING_CONSTANT validate structure offline;
Index DEMO_RANGE_COVERING_CONSTANT analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
 
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       3     2560      2440       9475000      2439        31        234755               25000      19759108      9709755         50          25000                12503.5                 86             9475000            2440

So, here the size of the branch blocks is higher because we have multiple leaves blocks with the value of COVERING_CONSTANT the second column is not sufficient to identify only one leaf block. The full 80 bytes must be stored, and the rowid in addition to it.

When the indexed column has only unique values, there is no need to store more in the branches (not the additional columns, not the rowid) and only 12 bytes are needed here on average:


SQL> analyze index DEMO_UNIQU_COVERING_RANDOM validate structure offline;
Index DEMO_UNIQU_COVERING_RANDOM analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
 
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       3     2560      2500       9688892      2499         5         29737                   1      20030140      9718629         49              1                      4                  0             9688892            2500

As the second column is not needed, the size of branch is the same whether we use RANDOM_TEXT or CONSTANT_TEXT:


SQL> analyze index DEMO_UNIQU_COVERING_CONSTANT validate structure offline;
Index DEMO_UNIQU_COVERING_CONSTANT analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
 
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       3     2560      2500       9688892      2499         5         29737                   1      20030140      9718629         49              1                      4                  0             9688892            2500

Now, the last one is my workaround for the higher size when adding a column that do not have a lot of distinct values: just add a column before with more distinct values. Here I use the UNIQU one, but you probably have one that can be useful for your queries.


SQL> analyze index DEMO_RANGE_COVERING_WITH_PK validate structure offline;
Index DEMO_RANGE_COVERING_WITH_PK analyzed.
SQL> select  height,blocks,lf_blks,lf_rows_len,br_rows,br_blks,br_rows_len,most_repeated_key,btree_space,used_space,pct_used,rows_per_key,blks_gets_per_access,opt_cmpr_pctsave,lf_uncmp_rows_len,lf_uncmp_blks from index_stats
 
  HEIGHT   BLOCKS   LF_BLKS   LF_ROWS_LEN   BR_ROWS   BR_BLKS   BR_ROWS_LEN   MOST_REPEATED_KEY   BTREE_SPACE   USED_SPACE   PCT_USED   ROWS_PER_KEY   BLKS_GETS_PER_ACCESS   OPT_CMPR_PCTSAVE   LF_UNCMP_ROWS_LEN   LF_UNCMP_BLKS
  ------   ------   -------   -----------   -------   -------   -----------   -----------------   -----------   ----------   --------   ------------   --------------------   ----------------   -----------------   -------------
       3     2688      2565       9963892      2564         6         37456                   1      20557908     10001348         49              1                      4                  2             9963892            2565

Now you get the idea. When creating an index, or adding columns for covering index, and you have the choice of column order, then try to have their first bytes selective enough so that the branch needs only a small substring to identify each leaf block (or lower level branches).

Block dumps

If you want to see the details about the branch length, here are some info from block dumps. I got them with the following:


SQL> column value new_value tracefile
SQL> select value from v$diag_info where name='Default Trace File';
VALUE
/u01/app/oracle/diag/rdbms/cdb1/CDB1/trace/CDB1_ora_6799.trc
SQL> exec for i in (select header_file, header_block from dba_segments where owner='DEMO' and segment_name='DEMO_RANGE') loop execute immediate 'alter system dump datafile '||i.header_file||' block '||(i.header_block+1); end loop;
PL/SQL procedure successfully completed.
SQL> host tail -20  &tracefile

Here is the last branch entry for the root block of DEMO_RANGE where the first column is not very selective and then the rowid is required in the branch:


row#351[3279] dba: 113261807=0x6c03cef
col 0; len 2; (2):  c1 04
col 1; len 6; (6):  07 00 05 7b 00 25

Here is the last branch entry for the root block of DEMO_RANGE_COVERING_RANDOM where instead of the rowid the 3 first bytes of the RANDOM_TEXT column are sufficient:


row#3[8006] dba: 113263037=0x6c041bd
col 0; len 2; (2):  c1 04
col 1; len 3; (3):  53 51 52
col 2; TERM

Here is the last branch entry for the root block of DEMO_RANGE_COVERING_CONSTANT where the full 80 bytes of CONSTANT_TEXT are not even sufficient, and the ROWID is needed as a 3rd column:


row#28[5316] dba: 117444566=0x7000fd6
col 0; len 2; (2):  c1 04
col 1; len 80; (80):
 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78
 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78
 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78
 78 78 78 78 78
col 2; len 6; (6):  07 00 05 43 00 25

Here is the last branch entry for the root block of DEMO_UNIQU_COVERING_CONSTANT where the first column is sufficient:


row#2[8026] dba: 117447160=0x70019f8
col 0; len 4; (4):  c3 09 0d 04
col 1; TERM

So what?

We probably don’t need a feature like SQL Server INCLUDE indexes in most of the cases. However, this may require thinking about the order of columns, mainly:

  • ensure that selective columns appear as early as possible (without compromising the index access efficiency of course) in order to lower the bytes required to address branches and leaves
  • when adding columns, try to add first a column that will keep the clustering factor you had with the rowid, such as a date of insert

Added 14-APR-2018

The conclusion above was only focused at columns added for covering indexes (I wrote it after reading wrong things in this stackoverflow thread), and it is not a general statement about putting selective columns first, which is a common misconception. Columns like this CONSTANT_TEXT (which is an extreme case of non-selective) can have a better index compression (Enterprise Edition feature) when in front. Read this tread, answers and links from Richard Foote: https://twitter.com/OracleSK/status/984906294879539200

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Franck Pachot
Franck Pachot

Principal Consultant / Database Evangelist