Infrastructure at your Service

Oracle Team

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

Oracle Team
Oracle Team