jump to navigation

Best Method To Select One Row From Small Table – Solution (Revolution 1) September 7, 2011

Posted by Richard Foote in Oracle Indexes, Small Indexes.
4 comments

OK, time for some answers, although of course regular readers of this blog will already know the answer :)

When selecting one row from the small table as in the quiz in my previous post, the correct order is as follows:

1) PK access of an Index Organized Table.

This option only requires just the 1 consistent get (as the IOT only consists of just 1 block) and this consistent get is a “cheaper” consistent get examination, which in turn only requires the 1 latch. So 1 consistent get and 1 latch. For more info on this, see: http://richardfoote.wordpress.com/2009/05/27/indexes-and-small-tables-part-vii-cluster-one/.

2) Use of Unique Index With a Heap Table.

This option only requires 2 consistent gets (one to read the index leaf block and one to read the table block). There can only be a maximum of one row when a single equality predicate is specified as the index is Unique, which means that 2 consistent gets is the maximum necessary (there may only be the 1 consistent get if there are either no rows to be returned or if all required columns can be found in the index). Additionally, because the index is Unique, both consistent gets are the cheaper, 1 latch consistent get examinations. So that’s 2 consistent gets and 2 latches. For more information, see: http://richardfoote.wordpress.com/2009/05/13/indexes-and-small-tables-part-v-its-no-game/.

3) Use of Non-Unique Index With a Heap Table

This option requires at most 3 consistent gets (one to read the leaf block, one to access the table and possibly one more to perform an additional fetch operation and checking the leaf block again in case of more rows, possibly necessary as the index is Non-Unique and there could be more than one row that matches an equality predicate). Unfortunately, as the index is Non-Unique, the consistent gets are the full-blown consistent gets which requires the buffer block to be pinned/unpinned via 2 latch calls. If the last value is specified, then the additional fetch may be unnecessary and if the index contains all the necessary columns, then just 1 consistent get would be necessary. But in the example provided, we’re looking at typically 3 consistent gets and 6 latches. For more information, see: http://richardfoote.wordpress.com/2009/05/05/indexes-and-small-tables-part-iv-treefingers/.

4) Use of a Full Table Scan

This option requires as a minimum 4 consistent gets (as Oracle needs to not only access the one block containing the 42 rows, but additionally the table segment header multiple times in order to determine the extent map, segment HWM etc.). These additional consistent gets are not generally an issue as these overheads are negligible for a typical FTS of a typical table. But in this example, with a tiny table, these consistent gets makes the difference. Note also that all 4 consistent gets require the block to be pinned/unpinned and so require 2 latch gets each. So that’s 4 consistent gets and 8 latches, minimum, even if all the rows can fit in 1 table block. On its own, no big deal, but if this small lookup table is accessed 10,000 times a minute, that’s potentially a lot of extra CPU and contention when performing a FTS over the above options. For more info, see: http://richardfoote.wordpress.com/2009/04/16/indexes-on-small-tables-part-i-one-of-the-few/ and the other articles on Indexes on Small Tables.

To those that got it right, well done. To those that didn’t, hopefully you’ve learnt something useful.

The moral of the story, no table is too small to potentially benefit from an index, even if the table is only one block in size :)

New question and discussion tomorrow.

Best Method To Select One Row From Small Table Quiz (Each Small Candle) September 5, 2011

Posted by Richard Foote in Oracle Indexes, Quiz, Small Indexes.
22 comments

Assume you have a tiny little table with just 42 rows (naturally) that all fit in one table block. Order the following options in order of “efficiency” (most efficient option first) when accessing just one of these rows:

1) Full Table Scan of Heap Table

2) PK access of an Index Organised Table

3) Index access of Heap Table via a Unique Index

4) Index access of Heap Table via a Non-Unique Index

If you think any of the options are the same, then you can order them as follows (example only):

1) Option 1

2) Option 2

2) Option 3

4) Option 4

Answer in the next few days …

UPDATE: just to clarify based on comments already made.

Yes, any index must visit the table as there are required columns within the table that are not stored in the index (this is implied by the above options). The table has only ever contained 42 rows and the are no additional table blocks below the table HWM (not that this really makes a difference to the answer). To keep it simple, the column being queried has a NOT NULL constraint (although it doesn’t really matter, except for when you want to put a PK constraint on it such as with the IOT option).

Indexes And Small tables Part VII (Cluster One) May 27, 2009

Posted by Richard Foote in Index Organized Tables, Oracle Indexes, Small Indexes.
14 comments

OK, almost getting to the end here ;)

As discussed previously, despite popular opinion, an index can be just that little bit more efficient than a FTS when accessing very small tables, even if  all rows in the table exist in the one table block. And a small efficiency multiplied by a large number can potentially add up and make a noticeable difference.

As we’ve seen, a unique index on such a small table accessing a specific row of interest need only perform one consistent read on the index block and one consistent read on the table block for a grand total of 2 consistent reads, with both consistent gets being the cheaper examinations variety. Not bad,  not too bad at all and somewhat cheaper than an equivalent FTS.

However, as I hinted and as many of you have already commented, we can go one step further still in reducing the overheads of such queries on small tables by potentially storing all the columns in the one, non-heap table structure.

One option is to create an Index Organized Table (IOT), storing all columns within a single index structure and thereby eliminating the need to visit a table segment at all.

Following on from the previous demo, let’s recreate the table as an IOT and populate it with the same data:

SQL> drop table small;
 
Table dropped.
 
SQL> create table small (id number primary key, name varchar2(10)) organization index;
 
Table created.
 
SQL> insert into small select rownum, ‘BOWIE’ from dual connect by level <=100;
 
100 rows created.
 
SQL> commit;
 
Commit complete.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>’SMALL’, method_opt=>’FOR ALL COLUMNS SIZE 1′);
 
PL/SQL procedure successfully completed.

 

If we now run our query again:

 

SQL> select * from small where id = 42;

 
        ID NAME
---------- ----------
        42 BOWIE
 
Execution Plan
------------------------------------------
|Id|Operation         |Name              |
------------------------------------------
| 0|SELECT STATEMENT  |                  |
|*1| INDEX UNIQUE SCAN|SYS_IOT_TOP_68376 |
------------------------------------------

Statistics
-------------------------------------------
  0  recursive calls
  0  db block gets
  1  consistent gets
  0  physical reads
  0  redo size
465  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

 

We notice that we have now reduced the number of consistent gets down to just one.

Not only is it just one consistent get but if we look at the type of consistent get by running the following query in another session before/after our SELECT above:

SQL> select name, value from v$sesstat s, v$statname n where s.statistic#=n.statistic# and sid = 141 and name like ‘consistent gets%';
 

NAME                           VALUE
----------------------------- ------
consistent gets                32842
consistent gets - examination   6694

 

SQL> select name, value from v$sesstat s, v$statname n where s.statistic#=n.statistic# and sid = 141 and name like ‘consistent gets%';

 
NAME                           VALUE
----------------------------- ------
consistent gets                32843 (+1)
consistent gets - examination   6695 (+1)

 

We also notice that it’s the cheaper, one latch consistent gets examination.

So we’ve now reduced our overheads down to just one consistent get and just the one latch get as well. It doesn’t really get much cheaper than that.

IOT are one of those under used options in Oracle that really should be considered used a lot more than they are. Yes they can be problematic when used inappropriately (especially if you need to create several secondary indexes) but for scenarios such as this they can be very useful.

I plan to discuss the advantages and disadvantages of IOT in future posts.

 

Another posssible option to improve things in our little demo is to create a Hash Cluster (as commented by Piet):

SQL> create cluster small_cluster (id number) size 100 single table hashkeys 200;
 
Cluster created.
 
SQL> create table small_tab (id number, name varchar2(100)) cluster small_cluster(id);
 
Table created.
 
SQL> insert into small_tab select rownum, ‘BOWIE’ from dual connect by level <=100;
 
100 rows created.
 
SQL> commit;
 
Commit complete.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>’SMALL_TAB’, estimate_percent=>null, method_opt=>’FOR ALL COLUMNS SIZE 1′);
 
PL/SQL procedure successfully completed.
 
SQL> select * from small_tab where id = 42; 

  ID NAME
---- ----------
  42 BOWIE

Execution Plan
---------------------------------------
| Id  | Operation         | Name      |
---------------------------------------
|   0 | SELECT STATEMENT  |           |
|*  1 |  TABLE ACCESS HASH| SMALL_TAB |
---------------------------------------

Statistics
-------------------------------------------
  0  recursive calls
  0  db block gets
  1  consistent gets
  0  physical reads
  0  redo size
465  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

 

Note again we have got our consistent gets down to just one as Oracle can simply determine the correct hash key based on the specified ID value and go directly to the table block containing the row of interest. Note however, this will not be a consistent get – examination, but the more expensive 2 latch and pin the block variety.

However, if you now create a unique index on the ID column:

SQL> create unique index small_tab_i on small_tab(id);

Index created.

And re-run the query:

SQL> select * from small_tab where id = 42; 

  ID NAME
---- ----------
  42 BOWIE

Execution Plan
---------------------------------------
| Id  | Operation         | Name      |
---------------------------------------
|   0 | SELECT STATEMENT  |           |
|*  1 |  TABLE ACCESS HASH| SMALL_TAB |
---------------------------------------

Statistics
-------------------------------------------
  0  recursive calls
  0  db block gets
  1  consistent gets
  0  physical reads
  0  redo size
465  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

 

Oracle will still use the hash to determine the location of the row of interest but because it now knows it will only retrieve the one row, will do so with only a consistent get – examination.  Back to one consistent get and only one latch get as well.

Again, clusters and all their various types and forms will be discussed in future blog entries.

Perhaps our good old familar heap table might not always be the best and most efficient option when creating these small tables (or even larger tables for that matter).

But for now the key message from this series is that any table, no matter how small can potentially benefit from being indexed. There really is no such thing as a table that’s too small to benefit from an index.Yes the difference might be small and of no real consequence but then again for larger database environments the overall savings might all add up and surprise. Note that the associated costs of having such indexes are also likely to be relatively small so perhaps it might just be worthwhile indexing those small tables after all ;)

Indexes And Small Tables Part VI (Loaded) May 19, 2009

Posted by Richard Foote in Constraints, Oracle Indexes, Small Indexes, Unique Indexes.
9 comments

Thanks to comments by PdV, I need yet another Part before I can look at completing this series ;)

OK, we’ve reached the stage in Part V of accessing this small, one block table with a Unique Index. This has reduced the number of consistent gets to 2, with both consistent get operations being the “pinless”, one latch consistent get examinations.

We basically need one consistent get to read the index and the other consistent get to read the row from the table block.

Not bad.

However, if we could somehow just store all the columns of interest within the index structure, we could potentially do even better because then we wouldn’t need to visit the table segment at all. A single consistent get from the index and bingo, we can retrieve all the required data directly from the index.

Overloading an index in this way is actually quite a common tuning trick. Simply add additional columns within the select list so that all the required columns can be found within the index, thereby elliminating the need to access the table at all and so potentially improve performance.

However, when it comes to overloading a unique index designed to specifically police a PK or Unique constraint we have a slight problem. Oracle will not allow a unique constraint to be policed by a unique index that does not have the same column list. It’s not a problem for a non-unique index (providing the leading columns match the constraint columns), but it’s an issue for a unique index.

Therefore, in our little example, we can’t simply create a single concatenated unique index on both the ID and NAME columns and use it to police a unique constraint on just the ID column. We must either use a unique index on the ID column or use a non-unique index on both the ID and NAME columns. If we want to create a unique index on both the ID and NAME columns, we would need to create an additional index on the ID column to police the PK on the ID column or change our business rules to make both the ID and NAME the PK (which is not likely something we would want to do). Note also by doing creating 2 unique indexes, we would effectively be storing the ID column in three separate places, within the table, within the ID index and also within the ID and NAME index. Again, not something we’re likely going to want to do.

To illustrate the point, drop any existing indexes on the SMALL table. If we attempt to create a unique index on both the ID and NAME columns while making the ID column only the PK, Oracle is going to complain:

SQL> alter table small add primary key(id) using index (create unique index small_uk_i on small(id, name));
alter table small add primary key(id) using index (create unique index small_uk_i on small(id, name))
*
ERROR at line 1:
ORA-14196: Specified index cannot be used to enforce the constraint.try and cr

If we create a unique index first on both the ID and NAME columns:

SQL> create unique index small_uk_i on small(id, name);

Index created.

And then hope Oracle will simply use this index to police a PK constraint on just the ID column, we’ll be sadly disappointed as Oracle will actually created another unique index on the ID column behind the scenes:

SQL> alter table small add primary key(id);

Table altered.

SQL> select c.index_name, c.column_name from user_indexes i, user_ind_columns cwhere i.index_name = c.index_name and i.table_name = c.table_name and i.table_name = ‘SMALL';

INDEX_NAME   COLUMN_NAME
------------ ------------
SMALL_UK_I   ID
SMALL_UK_I   NAME
SYS_C009759  ID

 

The CBO will of course potentially look at using our SMALL_UK_I concatenated unique index to perform the select statement of our demo, but the efficiency results are not quite what we’re after:

SQL> select id, name from small where id = 42;

        ID NAME
---------- -----
        42 BOWIE
-----------------------------------
|Id| Operation        | Name      |
-----------------------------------
| 0| SELECT STATEMENT |           |
|*1|  INDEX RANGE SCAN| SMALL_UK_I|
-----------------------------------
Statistics
-------------------------------------------
  0  recursive calls
  0  db block gets
  2  consistent gets
  0  physical reads
  0  redo size
465  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

 

We first note Oracle is indeed using the concatenated, unique SMALL_UK_I index as it can retrieve all the necessary data from the query directly from the index.

However, also note the CBO is performing an index range scan, not a unique scan as only a portion of the index (the ID) is specified in the WHERE clause. Oracle doesn’t pick up the fact the select operation is actually unique as not all columns within the SMALL_UK_I unique index used by the CBO are specified in the WHERE clause. This despite the fact the ID is actually the defined PK of the table.

Therefore, Oracle is still performing 2 consistent get operations as there may be more rows to retrieve after performing the first fetch within the SQL*PLUS session. Also, if we examined the types of consistent reads being performed, we would note that neither of them are consistent get – examinations.

So we’re really not that far ahead of just using the unique index on the ID column as we did in Part V of this series. We still require 2 consistent gets (although neither of them are now examinations) and we’re having to store the ID in three separate locations for our trouble, rather than two.

Wouldn’t it be nice if we could have a PK index on just the ID column, but somehow add the NAME column (or any other columns of interest) to the index structure so that we only need to visit the index structure, thereby storing the ID in only the one index. Then we could potentially access the data with just one consistent get and with it being a unique index, it would be a consistent get examination requiring only the one latch access.

Hell, wouldn’t it be nice if we didn’t even bother with the table segment at all as all queries of interest would never actually need to access and use the table segment anyways, thereby storing the PK in possibly just the one location.

Such a solution has of course been possible for a long time …

;)

Indexes And Small Tables Part V (It’s No Game) May 13, 2009

Posted by Richard Foote in Index Internals, Oracle Indexes, Small Indexes, Unique Indexes.
12 comments

So far in our little example, we’ve looked at how accessing a row of a one block table via a FTS required 4 consistent gets while accessing this same table via a Non-unique index reduced the consistent gets down to 3.

Time to take the next step and improve the efficiency yet further of accessing this small one block table.

We’re now going to replace the Non-unique index with a Unique Index instead. We can obviously do this because the values on the indexed ID column are indeed unique.

Now it’s always a good idea of course to document these table business rules (such as a column being unique) inside the database, however it’s somewhat alarming just how many application just don’t this. I’ve also previously discussed how a PK or Unique constraint can actually be policed via a Non-Unique index so there are many reasons why a small table might not have an associated Unique index.

Not least of course the incorrect perception that an index is not going to be much use on a small table anyways …

So let’s now replace the Non-Unique index with a Unique index instead:

SQL> drop index small_id_i;

Index dropped.

SQL> alter table small add primary key (id) using index (create unique index small_id_i on small(id));

Table altered.

 
OK, so now we have our Unique index in place. Let’s now run the same query again to see how our consistent gets related statistics might change:

 
SQL> select * from small where id = 42;

 

        ID NAME
---------- -----
        42 BOWIE

--------------------------------------------
|Id |Operation                  |Name      |
--------------------------------------------
|  1|TABLE ACCESS BY INDEX ROWID|SMALL     |
|* 2| INDEX UNIQUE SCAN         |SMALL_ID_I|
--------------------------------------------

Statistics
--------------------------------------------
  0  recursive calls
  0  db block gets
  2  consistent gets
  0  physical reads
  0  redo size
465  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

 

We notice our first significant change. The number of consistent gets has reduced further down to just 2.

Why ?

Because with a Unique index, there can only be a maximum of 1 row returned. It’s simply not possible to return 2 or more rows.

Therefore, when selecting this one row, Oracle doesn’t have to perform the second fetch operation to confirm there are indeed no more rows to return. The first fetch will either return the one row of interest or none at all when resolving an equality predicate. That’s it, there are no other possibilities. We return the row of interest by simply accessing the index block (1 consistent get) followed by the table block (the second consistent get).

As we have previously, if we look at the actual consistent gets statistics of interest by running the following query in another session before/after the select statement:

SQL> SELECT n.name, s.value FROM v$sesstat s, v$statname n WHERE s.statistic# =n.statistic# AND s.sid = 141 AND n.name LIKE ‘consistent%';

NAME                           VALUE
------------------------------ -----
consistent gets                31236
consistent gets - examination   5084

 
And again afterwards ..

 
SQL> SELECT n.name, s.value FROM v$sesstat s, v$statname n WHERE s.statistic# =n.statistic# AND s.sid = 141 AND n.name LIKE ‘consistent%';

NAME                           VALUE
------------------------------ -----
consistent gets                31238 (+2)
consistent gets - examination   5086 (+2)

We notice we have indeed only performed the 2 consistent gets. But we also notice another significant difference, that being both consistent gets are now the “cheaper” consistent gets – examination.

This means that the latches required to now perform this select statement via the Unique index is just 2, down from 6 for the Non-unique index and 8 from the FTS.

Generally during a consistent get, Oracle needs to grab the cache buffers chain latch so it can pin the specific block in memory and then grab the latch again so that it can subsequently unpin the block once it’s finished processing the block. Each of these accesses to the latch and the subsequently pin/unpinning of the block requires CPU and is a possible source of contention within the database.

For some operations that only require a very very quick “read and get out of there” type operation and/or on blocks that are unlikely to change within a given point of time, Oracle uses a cheaper consistent get operation which doesn’t actually require the block to be pinned. There’s no point in pinning the block as it’s only going to be read and accessed for a short time (shorter than might otherwise be required when processing a block in memory) and the block is unlikely to change anyways.

So for these operations, Oracle uses a cheaper consistent get called a consistent gets – examination. These consistent gets examinations only need grab the cache buffers chain latch before quickly reading the block and releasing the latch once the read operation is complete. Therefore it only needs to grab and release the cache buffer chains latch the once without having to pin/unpin the block, which means less CPU and less latch contention overall.

Now this isn’t particularly well documented. Often discussions mention reads of undo blocks as being candidates for consistent gets examinations as these reads are likely to be both relatively quick and a specific undo block is unlikely to change as only one transaction can actually update an undo block at a given time.

Getting back to indexes, reads of index root blocks are another candidate mentioned as again a read of an index root block is going to be very quick and an index root block is unlikely to change at a given point of time.

However, what is not well documented at all is the fact that any block accessed during an index Unique Scan is accessed via a consistent get – examination, including the consistent get associated with reading the table block as well. This is because again, any such read operation is going to be relatively quick as the most that ever needs to be read is the one index related entry and the one table row.

The net result is that now accessing a row from a small table via a Unique index requires only 2 latch accesses vs. the initial FTS example which required 8 latch gets as none of the FTS consistent gets are examinations.

Now you might say that these are all very small numbers, that 4 consistent reads isn’t that much, that 8 latches isn’t really that huge a number and reducing 8 latches down to 2 latches isn’t really going to be that noticeable. Yes it is effectively a 75% reduction but it’s a 75% reduction of not very much.

And if you’re discussing a single read of a single small lookup table you would likely be right.

But what if the small table is accessed frequently by the application, perhaps many 1,000s of times per minute. What if you have many such small tables, often used in small join operations by your OLTP applications. What if you have large numbers of users in a large application with many many such small table accesses. This effectively 75% saving can potentially become very significant, both in terms of the reduction in CPU load and also in the reduction of latch contention, which in turn can further reduce CPU loads.

A small improvement multiplied by a large amount can indeed make a difference …

However, I have one more step to go yet in further improving the efficiency of these small table lookups via an index.

One which can reduce the overall overheads by yet another 50% …

Indexes And Small Tables Part IV (Treefingers) May 5, 2009

Posted by Richard Foote in Index Block Splits, Index Internals, Oracle Indexes, Root Index Block, Small Indexes.
17 comments

As I asked in my previous post, the key question when comparing the associated costs of accessing a small table via a Full Table Scan (FTS) vs. an index scan is why does Oracle visit the segment header during a FTS but not during an index scan ?

The answer all comes down to understanding why Oracle must visit the table segment header during a FTS and how Oracle can avoid visiting the index segment header during an index scan.

Oracle must visit the table segment header during a FTS because it contains vital information necessary to perform the FTS, namely the extent map and the High Water Mark (HWM) associated with the table. Even with a table that only contains 1 data block worth of rows as in the SMALL table in my examples, Oracle has no way of automatically determining there’s actually only just the one block worth of data. It has to somehow look that up and determine exactly what table blocks Oracle needs to access during the FTS operation and the table segment header contains this necessary meta data. During “most” FTS operations, which are generally speaking larger, “expensive” operations, these accesses to the table segment header constitute a relatively small overhead. However, for FTS operations on “small” tables, accessing the table segment header can actually be a significant proportion of the overall associated costs.

During an index scan operation, there’s nothing of interest within the index segment header. The critical index block, the index block by which all index scans must start is the root block of the index (except Fast Full Index Scans which are basically the FTS equivalent for indexes). There’s no need to access the index segment header because it’s the root block that actually contains all the necessary information by which to start the index scan operation. The root blocks contains the pointers to subsequent index blocks (be it a branch or leaf blocks) that Oracle needs to follow in order to find the index entry of interest. The key to starting an index scan therefore is in determining the location of the index root block.

But how can Oracle determine the location of the index root block ?

Well Oracle implements a little “trick”, a golden rule with regard to indexes that doesn’t change regardless of the Oracle version, regardless of the O/S version, regardless of the type of tablespace or tablespace option of the index and regardless of how the index is created or grows and block splits over time.

The index root block is always, always, always the block immediately after the index segment header.

Always.

Therefore, when the Oracle code issues the associated function calls to perform an index scan, the first index block that Oracle assesses is the index segment header plus an offset of 1. Whereas a FTS accesses the table segment header, an index scan accesses the index segment block id plus 1.

With a tiny index that only has a level of 0 (or height of 1), note there is not “root” block as such as all the index entries can fit within one index leaf block. However, this block, this one and only leaf block within the index structure is also always the block immediately after the index segment header.

Always.

When we add more index entries into this one and only leaf block, we’ll eventually reach a point when it’s full and Oracle must perform an index block split operation. Oracle will then allocate 2 new blocks to the index. Assuming a 50-50 block split, one of these new blocks is assigned the lower 1/2 of all the current index entry values and the other new block is assigned the other upper 1/2 of the current index entry values. The original index leaf block content is then cleaned out and reassigned with just relative block address pointers and value boundaries associated with the 2 new leaf blocks.

The original index leaf block has been “reborn” as the root block of the index.

It’s quite easy to demonstrate how the original index block in a level 0 index or the root block of an index never changes and is always the block that follows the index segment header.

First, just create a little table and associated index:

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

Table created.

SQL> INSERT INTO same_root VALUES (1, ‘The Thin White Duke’);

1 row created.

SQL> COMMIT;

Commit complete.

SQL> CREATE INDEX same_root_i ON same_root(name);

Index created.

If we dump the block immediately following the index segment header, we can confirm it’s our index block of interest, containing our one and only index entry:

SQL> select header_file, header_block from dba_segments where segment_name=’SAME_ROOT_I';

HEADER_FILE HEADER_BLOCK
----------- ------------
          5       107441

SQL> alter system dump datafile 5 block 107442;

System altered.

Following is an extract of the index block dump:

Leaf block dump
===============
header address 98959964=0x5e6025c
kdxcolev 0
KDXCOLEV Flags = – – -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 8007=0x1f47
kdxcoavs 7969
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8007] flag: ——, lock: 0, len=29
col 0; len 19; (19):  54 68 65 20 54 68 69 6e 20 57 68 69 74 65 20 44 75 6b 65
col 1; len 6; (6):  01 41 a3 aa 00 00
—– end of leaf block dump —–

Note that it is indeed our one and only index leaf block.

If we now take a treedump of the index:

SQL> SELECT object_id FROM dba_objects where object_name = ‘SAME_ROOT_I';

 OBJECT_ID
----------
     67721

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

Session altered.

 

Following is the treedump output:

—– begin tree dump
leaf: 0x141a3b2 21078962(0: nrow: 1 rrow: 1)
—– end tree dump

We note that the relative block address of our one and only index leaf block is 21078962.

If we now add a whole bunch of new rows to the table so that the leaf block can no longer hold all the index entries, thereby forcing the index to block split and grow:

SQL> insert into same_root select rownum+1, ‘David Bowie’ from dual connect by level <=100000;

100000 rows created.

SQL> commit;

Commit complete.

And now take a block dump of the same index block:

SQL> alter system dump datafile 5 block 107442;

System altered.

Branch block dump
=================
header address 98959940=0x5e60244
kdxcolev 2
KDXCOLEV Flags = – – -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 2
kdxconro 2
kdxcofbo 32=0x20
kdxcofeo 8016=0x1f50
kdxcoavs 7984
kdxbrlmc 21238606=0x144134e
kdxbrsno 1
kdxbrbksz 8060
kdxbr2urrc 0
row#0[8038] dba: 21238607=0x144134f
col 0; len 11; (11):  44 61 76 69 64 20 42 6f 77 69 65
col 1; len 5; (5):  01 41 be 5f 01
row#1[8016] dba: 21238769=0x14413f1
col 0; len 11; (11):  44 61 76 69 64 20 42 6f 77 69 65
col 1; len 5; (5):  01 44 12 ba 01
—– end of branch block dump —–

We notice that the block is no longer a leaf block but has changed itself into an index branch block.

But not just any branch block. If we now take a new treedump:

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

Session altered.

branch: 0x141a3b2 21078962(0: nrow: 3, level: 2)
   branch: 0x144134e 21238606 (-1: nrow: 161, level: 1)
      leaf: 0x141a3b3 21078963 (-1: nrow: 179 rrow: 179)
      leaf: 0x141a3b4 21078964 (0: nrow: 179 rrow: 179)
      leaf: 0x141a3b5 21078965 (1: nrow: 179 rrow: 179)
      leaf: 0x141a3b6 21078966 (2: nrow: 179 rrow: 179)
      leaf: 0x141a3b7 21078967 (3: nrow: 179 rrow: 179)

….

The above partial listing of the treedump clearly shows that the index has grown from a level 0 index to a level 2 index and that the root block is the very same index block as the original leaf block listed as it has the same relative block address as before (21078962).

Indeed the original leaf block is now the index root block which is still the same block that immediately follows the index segment header.

Because Oracle doesn’t have to visit the index segment header and can simply directly access the block following the index segment header as this block is always the first index block of interest when performing an index scan, the index scan has that little advantage over the FTS. And it’s this little advantage that can give the index scan the edge over a FTS, even if we’re potentially accessing data from a very small table.

And you can’t get much smaller than a table that has all it’s rows in the one table block.

So far though, the example I’ve shown has been a “normal”, everyday, non-unique index that has a 1 consistent get advantage over the FTS when accessing a row of interest. I’ll next discuss how indexes can having an even bigger edge and more significant advantage over a FTS of a tiny table,  than just the 1 consistent get …

Indexes On Small Tables Part III (Another Brick In The Wall Part III) April 29, 2009

Posted by Richard Foote in Non-Unique Indexes, Oracle Indexes, Small Indexes.
11 comments

So far, in Part I and Part II of this little series, we’ve looked at how Oracle performs a Full Table Scan (FTS) when accessing a small table. With very small tables, Oracle needs to still access the table segment header and perform a number of fetch operations, even if the table is as small as you can get with all the rows in the table residing in one table block and even if we’re only interested in accessing the one row. In the little example we went through, Oracle still needs to access 2 distinct table blocks and perform 4 consistent get operations to read this one row of interest.

OK, let’s now finally introduce an index into the discussion.  To begin with, we’ll just create a standard, Non-Unique index on the ID column.

SQL> create index small_id_i on small(id);

Index created.

Now surely, there would be no real benefit in creating such an index on such a tiny table. This would be a separate index segment from the existing table segment so that if Oracle were to ever use the index to retrieve rows, it would need to visit both the index and table segments.

How can that possibly be more efficient than reading directly from the only table block in the table segment that contains rows ?

Well, let’s see what happens:

SQL> select * from small where id = 42;

        ID NAME
---------- -----
        42 BOWIE

--------------------------------------------
|Id|Operation                   |Name      |
--------------------------------------------
| 0|SELECT STATEMENT            |          |
| 1| TABLE ACCESS BY INDEX ROWID|SMALL     |
|*2|  INDEX RANGE SCAN          |SMALL_ID_I|
--------------------------------------------

Statistics
-------------------------------------------
  0  recursive calls
  0  db block gets
  3  consistent gets
  0  physical reads
  0  redo size
465  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

Well, we notice 2 very interesting points.

Firstly, the CBO does indeed decide to use the index, even though the table is so tiny.

Secondly, we notice that the actual number of consistent gets has actually reduced from 4 with the FTS down to just 3.  The index scan does indeed require less consistent gets than the equivalent FTS.

If we look at the consistent get stats via another session before and after the SELECT staement as we did in Part I, we can again confirm only 3 consistent gets were necessary:

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 LIKE ‘consistent%’;

NAME                            VALUE
----------------------------- -------
consistent gets                   110
consistent gets - examination      25

And again after the SELECT on the small table:

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 LIKE ‘consistent%’;

 
NAME                            VALUE
----------------------------- -------
consistent gets                   113 (+3)
consistent gets - examination      25

The consistent gets indeed increased by 3 rather than 4 but again as in the FTS example, none of these consistent gets were the cheaper “consistent gets – examination” (to be discussed later).

But why did the index scan only require 3 consistent gets ? Again, by flushing the buffer cache and tracing the session, we get the necessary information to answer the question:

SQL> alter system flush buffer_cache;

System altered.

SQL> exec dbms_monitor.session_trace_enable(waits=> true);

PL/SQL procedure successfully completed.

SQL> select * from small where id = 42;

        ID NAME
---------- -----
        42 BOWIE

SQL> exec dbms_monitor.session_trace_disable();

PL/SQL procedure successfully completed.

If we now look at an example trace file:
=====================
PARSING IN CURSOR #2 len=33 dep=0 uid=88 oct=3 lid=88 tim=24452815463 hv=2225904586 ad=’23bdd320′ sqlid=’7pjs08q2at6ya’
select * from small where id = 42
END OF STMT
PARSE #2:c=0,e=7613,p=0,cr=0,cu=0,mis=1,r=0,dep=0,og=1,tim=24452815457
EXEC #2:c=0,e=42,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=1,tim=24452815593
WAIT #2: nam=’SQL*Net message to client’ ela= 5 driver id=1111838976 #bytes=1 p3=0 obj#=12446 tim=24452815631
WAIT #2: nam=’db file sequential read’ ela= 17035 file#=7 block#=118026 blocks=1 obj#=99587 tim=24452832933
WAIT #2: nam=’db file sequential read’ ela= 5592 file#=7 block#=117898 blocks=1 obj#=99586 tim=24452838643

FETCH #2:c=0,e=23057,p=2,cr=2,cu=0,mis=0,r=1,dep=0,og=1,tim=24452838728
WAIT #2: nam=’SQL*Net message from client’ ela= 394 driver id=1111838976 #bytes=1 p3=0 obj#=99586 tim=24452839197
FETCH #2:c=0,e=22,p=0,cr=1,cu=0,mis=0,r=0,dep=0,og=1,tim=24452839275
STAT #2 id=1 cnt=1 pid=0 pos=1 obj=99586 op=’TABLE ACCESS BY INDEX ROWID SMALL (cr=3 pr=2 pw=2 time=0 us cost=2 size=9 card=1)’
STAT #2 id=2 cnt=1 pid=1 pos=1 obj=99587 op=’INDEX RANGE SCAN SMALL_ID_I (cr=2 pr=1 pw=1 time=0 us cost=1 size=0 card=1)’
WAIT #2: nam=’SQL*Net message to client’ ela= 3 driver id=1111838976 #bytes=1 p3=0 obj#=99586 tim=24452839399

The critical part here is the first “db file sequential read” wait event. By looking at the obj#=99587, we can determine this refers to the SMALL_ID_I index segment. By looking at the associated file#=7 block#=118026, a block dump reveals this to be the index leaf block containing the index row entries. Notice how we do not actually access the index segment header at all prior to accessing the leaf block of the index.

The following “db file sequential read” wait event on obj#=99586 corresponds to the table segment and file#=7 blockblock#=117898 corresponds to the table block containing the rows. So the first FETCH uses 2 consistent reads (cr=2) to return the first (and in this case only) row of interest (r=1) by first reading the index leaf block and then reading the table data block containing the row of interest.

Oracle then performs another FETCH to read the leaf block again to determine whether there are any other rows of interest (cr=1) of which there are none (r=0).

There is no PK or Unique constraint on the ID column in table and the index is Non-Unique so there is no possible way for Oracle to know there is indeed only one row of interest hence why Oracle needs to again visit the leaf block just in case there are multiple rows that have an ID = 42.

So that’s our 3 consistent gets, 1 to read the leaf block, 1 to read the table block and 1 to again read the index block again due to a SQL*PLUS quirk to perform a secondary fetch operation for non-unique scans as the first fetch only checks and fetches for one row.

Now in our specific example, that’s a saving of 1 consistent get and effectively 2 latch gets by using the Non-Unique index vs. performing the FTS on this effectively 1 block table. The savings would of course be more substantial if the small table had more than just the one data block containing rows.

Now you might well say, is it really worth the effort, what’s 1 consistent get in the grand scheme of things. Well, that’s 1 consistent get each and every time such a query needs to access this specific table. And this is just one table, you may have many such lookup tables in your databases. In heavily used applications, such lookup tables can potentially be accessed many millions of times per hour. Now all this can add up to potentially many millions of reduced consistent gets, many millions of reduced latch requests, which all in turn can add up to considerable CPU savings as well as the significantly reduced contention issues, increasing the general scalability of your applications.

And as we’ll see, we can actually do a lot better than saving just 1 consistent get by using an index to access such small tables …

However, the key question at this point is why doesn’t Oracle have to visit the index segment header as it does with the table segment during a FTS and how does Oracle know where to find the index block it needs ?

That will be answered in the next instalment coming soon …

Indexes On Small Tables Part II (The Mysteries) April 24, 2009

Posted by Richard Foote in Oracle Indexes, Small Indexes.
14 comments

I’m a bit pushed for time at the moment but I thought I might quickly just expand a little on the observations in Part I of this no doubt soon to be epic series (there’s at least another 3 parts to come) !!

In Part I we saw how even with a tiny table that consists of just one block containing 100 rows of application data, Oracle requires 4 consistent get operations to retrieve just the one row via a Full Table Scan (FTS). This surprises some folks as they expect Oracle to perhaps only need the 1 or maybe 2 consistent gets to access this one block containing application related row data.

If we were to flush the buffer cache before running the SELECT statement and trace the associated session, the resultant trace file shows how Oracle needs to first visit the Segment Header of the table before it can read the actual table block containing the row of interest. Oracle needs to read the table segment header in order to determine what blocks need to be accessed to begin the FTS operation. In this specific case, there’s only the one data block but Oracle also has to check to ensure there indeed are no more blocks it needs to visit. Oracle also has to perform another fetch operation to confirm there are indeed no more rows it needs to return after it fetches the first (and in this case only) row.

The following should help to show what’s going on during the FTS of our little 100 row table where all 100 rows nicely resides in the one data block.

We first flush the buffer cache in order to force Oracle to perform physical I/Os (note the following example was run on 11.1.0.6).

SQL> alter system flush buffer_cache;

System altered.

 

Next, we trace our session …

SQL> exec dbms_monitor.session_trace_enable(waits=> true);

PL/SQL procedure successfully completed.

 

Before running the SELECT statement that returns our one row of interest …

SQL> select * from small where id = 42;

 
        ID NAME
---------- -----
        42 BOWIE

 

SQL> exec dbms_monitor.session_trace_disable();

 

If we look at an example trace file:

=====================
PARSING IN CURSOR #19 len=33 dep=0 uid=88 oct=3 lid=88 tim=24079367090 hv=2225904586 ad=’23bdd320′ sqlid=’7pjs08q2at6ya’
select * from small where id = 42
END OF STMT
PARSE #19:c=0,e=18142,p=0,cr=0,cu=0,mis=1,r=0,dep=0,og=1,tim=24079367080
EXEC #19:c=0,e=35,p=0,cr=0,cu=0,mis=0,r=0,dep=0,og=1,tim=24079367262
WAIT #19: nam=’SQL*Net message to client’ ela= 5 driver id=1111838976 #bytes=1 p3=0 obj#=62986 tim=24079367301
WAIT #19: nam=’db file sequential read’ ela= 16020 file#=7 block#=117897blocks=1 obj#=99586 tim=24079383391
WAIT #19: nam=’db file sequential read’ ela= 16820 file#=7 block#=117898blocks=1 obj#=99586 tim=24079416967
FETCH #19:c=15625,e=49760,p=2,cr=3,cu=0,mis=0,r=1,dep=0,og=1,tim=24079417101

WAIT #19: nam=’SQL*Net message from client’ ela= 445 driver id=1111838976 #bytes=1 p3=0 obj#=99586 tim=24079417615
FETCH #19:c=0,e=27,p=0,cr=1,cu=0,mis=0,r=0,dep=0,og=1,tim=24079417699
STAT #19 id=1 cnt=1 pid=0 pos=1 obj=99586 op=’TABLE ACCESS FULL SMALL (cr=4 pr=2 pw=2 time=0 us cost=2 size=9 card=1)’
WAIT #19: nam=’SQL*Net message to client’ ela= 6 driver id=1111838976 #bytes=1 p3=0 obj#=99586 tim=24079439168

 

Notice how the first highlighted wait event performs a ‘db file sequential read’ to first  access the segment header as denoted by file#=7 block#=117897 in order to determine which blocks need to be read during the FTS operation. You can easily confirm the file# and block # corresponds to the table segment header by querying DBA_SEGMENTS.

This is then immediately followed by another ‘db file sequential read’ wait event to access the only data block of interest as denoted by file#=7 block#=117898. Notice how this block is simply the block that follows the segment header, as all 100 rows were inserted at one time by the one transaction. Note this is the only data block in the table that contains rows and is the only table block that needs to be accessed during the FTS operation.

Notice how the first FETCH operation resulted in 3 consistent gets (cr=3), 2 consistent gets that correspond to the 2 physical I/O waits events already identified plus an extra consistent read to confirm there were no more table blocks of interest.  This FETCH returns the first and (in this case) only row of interest (r=1).

A second FETCH was required resulting in an additional consistent get (cr=1) to confirm to the client that there are indeed no more rows of interest to be returned after the first row was fetched (r=0). We might know there’s only one row but Oracle doesn’t until it performs this second fetch.

Note BTW that if the query returned no rows at all, this second fetch would not have been required as the first empty fetch would have confirmed to Oracle there were no more rows to come. The total CR count would have been just 3 in this case (but would still have been bettered by an index if present).

This is a small lookup table and we’re generally interested in just the one row. As discussed in Part 1 and now expanded upon here, a FTS requires at least 4 CR behind the scenes when retrieving just the one row of interest, even if the table is tiny and can potentially store all its rows in just the one data block.

You can’t really get a table smaller than one block and yet as we’ll see, an index can beat the 4 CR overhead of reading a row from this tiny table via a FTS.

Next installment coming soon … :)

Indexes On Small Tables Part I (One Of The Few) April 16, 2009

Posted by Richard Foote in Oracle Indexes, Small Indexes.
26 comments

A common question I get asked is when is a table too small to benefit from being indexed.

If a table only has a few blocks for example, which could all be potentially read via a single multiblock read operation, surely there’s no benefit in indexing such a table (except perhaps to police an associated PK constraint). It must take at least 2 Logical I/O (LIO) operations to read data from the table via an index, at least one LIO to read an index block and at least one LIO to read the associated table block referenced by the ROWID in the index. If a Full Table Scan (FTS) can be effectively performed via a single multiblock read operation, hence reading the entire table with just one LIO , surely an index will always be a more expensive option and so ultimately useless with such small tables.

Well not necessarily …

The first thing to point out is that generally speaking, a Full Table Scan is a relatively expensive operation. Tables can be big, really really big, consisting of potentially many many 1,000s of data blocks, potentially requiring many 1,000s of multiblock read operations to be performed. Therefore, generally speaking, if we’re going to perform a relatively expensive FTS, we’re not going to be too concerned if we use an extra I/O or two, as we potentially have to perform 1,000s of I/Os anyways. A shortcut here or there is not going to generally make much of a difference one way or the other.

Note also that with a FTS being this relatively expensive operation, we’re not likely to generally speaking want to perform 1,000s of such FTS operations every minute within our databases. Generally speaking, a FTS is a much less common event than an Index Range Scan operation and so we wouldn’t take advantage of any possible short cuts here or there very often.

However, generally speaking, an index scan is a relatively inexpensive operation, potentially consisting of just a few LIO operations. We may have an index that has a blevel of say 2 (height of 3) and we may typically only want to select a row or two. That would therefore consist of just 3 LIOs of read the index related blocks (the index root block, an index branch block and an index leaf block) plus an I/O or two to read a row or two from the table. It’s potentially just a handful of blocks, just a few little LIOs but if we could somehow save an I/O or two in the process, this could in fact make a huge difference to the relative costs of the Index Range Scan.

Note also that with an Index Range Scan being this relatively inexpensive operation, we’re quite like to generally speaking want to perform lots and lots of such Index operations each and every minute in our databases. Generally speaking, an Index Range scan is a very very common event and so any short cut here or there can be extremely useful and significant and be taken advantage of frequently within the database.

So a FTS has a tendency to be relatively expensive and is not performed anywhere near as as frequently as Index Range Scan operations which have a tendency to be relatively inexpensive. Generally speaking of course.

But Oracle takes this generalisation very much to heart in how it goes about processing these operations.

The next point to make is that if a table has just a few rows and say consists of  just the one data block below its High Water Mark (HWM), it doesn’t necessarily mean we only need just the one I/O operation to read the entire table. For example, how does Oracle know there’s just one block worth of data ? How does Oracle know where to actually physically locate this one block worth of data ? How does Oracle know that once its read this block, there aren’t any other data blocks of interest ?

The answer is that it can’t without referencing data dictionary objects and without accessing the table segment header where the extent map is located. Even for a tiny table with only a handful of rows that can reside in only the one table block, it therefore requires more than just the one consistent get operation to read data from the table via a FTS. However, as a FTS is usually a relatively expensive operation, these few little consistent reads here and there to determine the actual number of blocks in the table and the actual location of these blocks is generally going to be a relatively trivial overhead. Oracle though doesn’t differentiate between a small and a larger table when it comes to a FTS, so these extra few consistent reads can potentially be a significant overhead for FTS operations on smaller tables.

As an example, let’s create a little table and see what consistent gets are required to read it via a FTS …

Let’s begin by creating a small table that consists of just 100 little rows.

SQL> CREATE TABLE small AS SELECT rownum id, ‘BOWIE’ name FROM dual CONNECT BY LEVEL <= 100;

Table created.

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

PL/SQL procedure successfully completed.

SQL> SELECT blocks from user_tables WHERE table_name=’SMALL';

    BLOCKS
----------
         1

Note that this table consists of just the one data block below the HWM. A table can’t really get much smaller that one block.

Let’s now select just one row from this table. Note we haven’t created an index at this point so Oracle has no choice but to read this one row via a FTS.

SQL> SELECT * FROM small WHERE id = 42;

        ID NAME
---------- -----
        42 BOWIE

 

Execution Plan
------------------------------------------
|Id  | Operation         | Name  | Rows  |
------------------------------------------
|  0 | SELECT STATEMENT  |       |     1 |
|* 1 |  TABLE ACCESS FULL| SMALL |     1 |
------------------------------------------
Statistics
--------------------------------------------
  0  recursive calls
  0  db block gets
  4  consistent gets
  0  physical reads
  0  redo size
465  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

 

Note to read just this one row from this one block table, we have actually performed 4 consistent gets operations. Not 1 consistent get, but 4 consistent gets …

Let’s look at the actual type of consistent gets, by running the following statement in another session before and after executing the above SELECT statement (note SID 134 refers to the session SID that ran the above SELECT statement) :

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 LIKE ‘consistent%';

NAME                           VALUE
----------------------------- ------
consistent gets               275851
consistent gets - examination  70901

Note the above figures were the session consistent gets before the SELECT statement and the following consistent gets statistics are after the SELECT statement was executed. 

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 LIKE ‘consistent%';

NAME                           VALUE
----------------------------- ------
consistent gets               275855 (+4)
consistent gets - examination  70901 (0)

Note that yes indeed, there were 4 consistent gets performed and that none of the consistent gets were the “cheaper” consistent gets examinations. Therefore, the 4 consistent gets used in performing the FTS of the one block table required 4 x 2 = 8 latches.

Now 4 consistent reads to perform a FTS isn’t too bad, even for this little table and 8 latches isn’t exactly a huge number.

However, as we’ll see next, an index on this tiny one block table can do so much better …

Follow

Get every new post delivered to your Inbox.

Join 1,918 other followers