You Asked

Greetings,

How does the data structure of a compound index in Oracle look like? I'm wondering how Oracle is able to use a "skip scan" by using the second entry in a compound index? I know that the first field uses a b-tree structure, but I am unsure how the second field is stored.

I started to think about this recently since I have been supporting MongoDB. In MongoDB, it is not able to use a compound index if the prefix field isn't part of the query.

I've added the following as optional information to show a little bit about how Mongo stores a compound index and to show why Mongo can't use the secondary field of a compound index because the value of the second field is just concatenated into the value of the first field.

For instance, in Mongo, if we have the following data:

"test" has these four docs/records:
{ x: 1, y: 2 }
{ x: 2, y: 3 }
{ x: 2, y: 1 }
{ x: 1, y: 4 }

Next, we create a compound index:
db.test.createIndex({x: 1, y: 1})

Then we search for records that have x=2 and y >= infinity and get explain plan:

Mongo reports that only two index leaf keys were read. This means that Mongo stores entries in the b-tree leaf as: (field1:field2)

Thanks for your help,

John

and Chris said...

All columns are part of the B-tree in Oracle Database's compound indexes. The entries are sorted by the first column, then the second column, and so on.

e.g.: for an index on ( C1, C2 ), entries look something like:

C1, C2, location
1,abc,rowid
1,def,rowid
1,ghi,rowid
1,jlk,rowid
2,abc,rowid
2,def,rowid
2,ghi,rowid
2,jlk,rowid

If the first column has few unique values, the database can do a skip scan when you search on only the second. Conceptually this searches the index once for each value in the leading column.

The docs discuss this in more detail https://docs.oracle.com/en/database/oracle/oracle-database/23/tgsql/optimizer-access-paths.html#GUID-21258F63-7506-4019-9FB4-323E9D2DE087

Rating

(4 ratings)

Comments

John Cantu, February 10, 2025 - 11:17 pm UTC

Thank you, Chris.

If I execute, select * from Where c1=1 and c2='jlk', will Oracle have to read these four index entries:

1,abc
1,def
1,ghi
1,jlk

BTW: In Mongo, it will report that it only had to read one index key which I take it to mean, just needs to compare against: "1, jlk"

February 11, 2025 - 1:24 pm UTC

Oracle Database only needs to read one entry in this case too.

Mind Blowing!

John Cantu, February 12, 2025 - 7:25 am UTC

Thank you, Chris!

Wow, so the number of index entries read when just considering a query on qualifiers C1 & C2 will be exactly the same whether index is created as ( C1, C2 ) or ( C2, C1 )!

February 12, 2025 - 8:56 am UTC

Correct. This is the point of indexes - to only access items that match your search!

surprised that Oracle doesn't have to access additional index key to find the requested one

John Cantu, February 12, 2025 - 3:05 pm UTC

Chris, so if the following entries exist in an index leaf block, how is it able to find "1,jlk" without reading "1,abc", "1,def" & "1,ghi"? I thought that Oracle had to scan the leaf block sequentially.

Entries in one index leaf block:
C1, C2, location
1,abc,rowid
1,def,rowid
1,ghi,rowid
1,jlk,rowid
2,abc,rowid
2,def,rowid
2,ghi,rowid
2,jlk,rowid

February 13, 2025 - 1:43 pm UTC

I guess I oversimplified.

The smallest unit of data access in Oracle Database is the block. When accessing an index entry (or table row), the database will fetch the block containing it - this includes everything else in the block.

So if all the entries are in one block as in your example, you're right the database will have to scan through the preceding entries.

However, the effect of this is trivial and not worth worrying about. Most of the work is in getting a read consistent view of the block. The database will only read index blocks matching your search*.

* When searching a non-unique index, the database has to check the next entry too. This is because there could be many entries matching your search. So it only stops searching when it finds an entry that doesn't match your search. In your example, this would be "2,abc".

If "1,jlk" happens to be the last entry in the block, the database will read the next block to ensure there are no further matches.

Tie it back to Mongo's explain plan reporting that they only had to read two index leaf blocks

John Cantu, February 15, 2025 - 4:51 pm UTC

RRight, Chris, I understand it is a drop in the bucket to perform those compares in the block. I am focused on those details because I want to be to compare Oracle's approach versus Mongo's.

I am going to simplify this scenario by removing the compound index piece. If I perform the following in Mongo:

db.test.insertMany([{x:1},{x:2},{x:2},{x:1},{x:9},{x:8])
db.test.createIndex({x:1})
db.test.find({x:2})

My educated guess is that Mongo and Oracle both have to compare 5 index leaf entries. It will not read x:9 since it will know that after reading x:8.

However, Mongo's explain plan states that it only had to read "2 index keys examined." It seems impossible for Mongo to only have to "examine 2 index keys," don't you agree? Is Mongo lying? Oracle has to perform 5 index compares while Mongo only has to perform 2?

FYI: Here is what Mongo claims:

Query Performance Summary

- 2 documents returned
- 2 documents examined
- 0 ms execution time
- Is not sorted in memory
2 index keys examined
Query used the following index: x

February 17, 2025 - 5:07 pm UTC

I don't know enough about Mongo to comment on it; I suggest finding Mongo experts and asking them if you need precise details on how this works in that database.

Oracle has to perform 5 index compares

No it doesn't!

The default index structure in Oracle Database is a B-Tree. This is an ordered data structure. So the entries in the index will be in this sequence - regardless of which order you inserted them or how they're physically stored in the table:

1, 1, 2, 2, 8, 9.

So in this case Oracle Database has to read index entries 2, 2, 8. It might also access 1, 1 if they happen to be in the same block. If that's the only data in the table by default everything will fit in one block so the database will report one consistent get.

For example, here both queries report one get (Buffers = 1) for the index range scan despite the first only returning rows = 2 and the other reading all the entries in the index:

create table t ( c1 int, c2 varchar2(100) default rpad ( 'stuff', 100, 'f' ) );

insert into t ( c1 )
values ( 1 ), ( 2 ), ( 2 ), ( 1 ), ( 8 ), ( 9 );

create index i on t ( c1 ) ;

exec dbms_stats.gather_table_stats ( user, 't' );
alter session set statistics_level = all;
set serveroutput off

select * from t
where  c1 = 2;

select * from dbms_xplan.display_cursor ( format => 'IOSTATS' ) ;

------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |      |      1 |        |      2 |00:00:00.01 |       2 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T    |      1 |      2 |      2 |00:00:00.01 |       2 |
|*  2 |   INDEX RANGE SCAN                  | I    |      1 |      2 |      2 |00:00:00.01 |       1 |
------------------------------------------------------------------------------------------------------

select * from t
where  c1 >= 1;

select * from dbms_xplan.display_cursor ( format => 'IOSTATS' ) ;

------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |      |      1 |        |      6 |00:00:00.01 |       2 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T    |      1 |      6 |      6 |00:00:00.01 |       2 |
|*  2 |   INDEX RANGE SCAN                  | I    |      1 |      6 |      6 |00:00:00.01 |       1 |
------------------------------------------------------------------------------------------------------

If we recreate the index with pctfree 99 this reserves lots of space in each block, so each leaf will only contain one entry.

Rerun the queries and you'll find

- c1 = 2 does 4 gets; 1 for the root block + three for the leaves 2, 2, 8
- c1 >= 1 does 7 gets; 1 for the root block + one get for each of the six rows

drop index i;
create index i on t ( c1 ) pctfree 99;

select * from t
where  c1 = 2;

---------------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
---------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |      |      1 |        |      2 |00:00:00.01 |       5 |     12 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T    |      1 |      2 |      2 |00:00:00.01 |       5 |     12 |
|*  2 |   INDEX RANGE SCAN                  | I    |      1 |      2 |      2 |00:00:00.01 |       4 |     12 |
---------------------------------------------------------------------------------------------------------------

select * from dbms_xplan.display_cursor ( format => 'IOSTATS' ) ;

select /*+ index ( t ( c1 ) ) */* from t
where  c1 >= 1;

select * from dbms_xplan.display_cursor ( format => 'IOSTATS' ) ;

------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |      |      1 |        |      6 |00:00:00.01 |       8 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T    |      1 |      6 |      6 |00:00:00.01 |       8 |
|*  2 |   INDEX RANGE SCAN                  | I    |      1 |      6 |      6 |00:00:00.01 |       7 |
------------------------------------------------------------------------------------------------------

Oracle Database doesn't have an "index keys examined" metric that I know of. I don't think you can compare this Mongo metric directly to the work in Oracle Database.

More to Explore

Performance

Get all the information about database performance in the Database Performance guide.

Breadcrumb

Question and Answer