UPDATE 30 March 2016
I've come to realise that there are some mistakes and inaccuracies in this post [see this post for more details], so I've edited this post and corrected what I can. Rather than leave behind incorrect claims, I've replaced them by the corrected text, so hopefully now this post no longer has its previous faults.
ORIGINAL POST:
Many people consider a Full Table Scan (FTS) in a query execution plan to be a bad thing - reading every record from a table to find only those records the query needs. This is indicated by a "
TABLE ACCESS FULL"
in an execution plan. But is it really all that bad? Is it actually
sometimes the right tool for the job? Can a Full Table Scan sometimes
have a lower cost than using an Index?My view is that the Oracle Optimizer will only choose a FTS under the following two conditions:
- There is no other possible access method to get the needed data from the table
- No other access method is currently available, but another access method might be a lower cost if it was available
- A FTS is a lower cost (and so should be faster) than all other possible access methods
- The FTS is the "best" access method of all available and the Optimizer is correct to use it
TABLE ACCESS FULL"
in an execution plan you should not jump to the conclusion that this is
wrong and "needs to be fixed", because maybe it is correct and it is
indeed the best access method for that particular step of the query
operation. If you have concerns about the FTS then you need to double
check things to find out whether it is the right thing for the Optimizer
to be choosing, or whether a better access method would reduce the
execution cost. Jumping to the wrong conclusion can lead you down a
dead end when trying to improve a query's performance.So when you see a Full Table Scan in an execution plan you should check the query and all other relevant factors to see if a FTS is indeed the "best" access method to get that data because it has the lowest cost. Don't assume that the Optimizer is wrong - normally it isn't. It is just as likely to be your query that is affecting the execution plan chosen.
Calculating the Cutover Point
The actual percentage or fraction of rows in the table that is the cutover point between the Optimizer using a Full Table Scan or an available Index is itself mainly dependent on the average number of rows stored per data block. The other main factor is the value being used by the Optimizer for Multi-Block Read Count (MBRC), which is part of the System Statistics stored in the database. It is possible to calculate this cutover point yourself on a given table to see when a FTS really is cheaper and when an Index might help.For a specific query involving an equality filter on a column, the other factor is what fraction of the data rows in the table have the same value stored in them. Oracle maintains this as a statistic on each column named "Density". By comparing the Density value for a column against the fraction of rows in the table needed by the query, you can see whether a FTS would be cheaper or not for a filter on that column. Remember that a percentage is just a fractional decimal value multiplied by 100 - so a Density of 0.0025 means 0.25%.
First the value used for MBRC (Multi-Block Read Count). This is stored in the
AUX_STAT$ table owned by SYS.
Its value only gets set when you gather system statistics. If set,
then that particular value is used. If not set then a default value of 8
is used (note that it seems to ignore the value of the initialization
parameter db_file_multiblock_read_count). The Optimizer also uses the values for MREADTIM and SREADTIM (Multi-block read time and Single block read time) also in the AUX_STAT$ table. Again, if these have not been set then it will use a default formula to derive them from the values for IOSEEKTIM and IOTFRSPEED.To try and keep this explanation short we can jump to the following formulae used when you have not gathered system statistics.
SREADTIM = IOSEEKTIM + (DB_BLOCK_SIZE / IOTFRSPEED)
MREADTIM = IOSEEKTIM + (MBRC * DB_BLOCK_SIZE / IOTFRSPEED)
MBRC (8), IOSEEKTIM (10) and IOTFRSPEED (4096) and a DB_BLOCK_SIZE of 8192 (8 KB) you get an SREADTIM value of 12 milliseconds, and a MREADTIM value of 26 milliseconds.When a Full Table Scan occurs the Optimizer knows that it will be doing multi-block reads. However, it needs to cast or convert the cost of these reads into units of single block reads. This is because all other I/O costs are in terms of single block reads internal to the Optimizer. And the "cost" of a multi-block read is not the same as the "cost" of a single block read - a multi-block read should take longer given the greater number of blocks being transferred.
Instead of dividing the number of blocks in the table by the full
MBRC value, it "adjusts" this value by the ratio of SREADTIM to MREADTIM, and then uses this value in the cost calculation. The cost of a FTS would then be calculated as (note the brackets):
FTS Cost = #Blocks in Table / (MBRC * SREADTIM / MREADTIM)
FTS Cost = (#Blocks in Table * MREADTIM) / (MBRC * SREADTIM)
- Number of Rows in the table -
NUM_ROWSinUSER_TABLESorUSER_TAB_STATISTICS - Number of Blocks used for the table -
BLOCKSinUSER_TABLESorUSER_TAB_STATISTICS - Density of the column -
DENSITYinUSER_TAB_COLSorUSER_TAB_COL_STATISTICS
Density > (BLOCKS * MREADTIM) / (MBRC * SREADTIM * NUM_ROWS)
Conclusions
Although a Full Table Scan can seem a "brute force" approach to finding some matching records in a table, it can sometimes be the better way of doing it though. It depends on several factors including how many rows you want back from the table, the number of blocks for the table, and the Clustering Factor of any indexes.It is possible that for even low percentages of data being retrieved from a table that a Full Table Scan can be the cheapest and best access method. Trying to force the Optimizer into using another access method in this circumstance is a waste of time, because all other access methods will be more expensive. The only exception might be another Full Scan type access, such as an Index Full Scan. But even then the gains (reduction in cost) will only be marginal i.e. not a full order of magnitude less.
When you see a FTS in a query execution plan you should check many things including, but not limited to, the number of rows in the table, the number of blocks used for the table, the Clustering Factor for each possible index, and the estimated row count for the filters being used. If the estimate is correct then a FTS is the lowest cost access method and the Optimizer is right to choose it. You should also check if your query is correct, or if there is something wrong with the filter conditions in it.
Tests
Lets show whether this holds true with some tests. There is quite a lot of output here, but I want to provide everything so that anyone else can reproduce these tests on their own systems.Database version - 12.1.0.2.0
Operating System - Oracle Linux 7.2
Scan Test table - 10 million rows, with columns of different repeated values:
drop table scantest ;
--
prompt Loading data ....
create table scantest
tablespace testdata
as
select r pkid
, 1 one -- a constant, which forces actual data row access
, mod (r, 10) pct10 -- 10 values = 10% of data in table
, mod (r, 20) pct5 -- 20 values = 5% of data in table
, mod (r, 50) pct2 -- 50 values = 2% of data in table
, mod (r, 100) pct1 -- 100 values = 1% of data in table
, mod (r, 200) pct05 -- 200 values = 0.5% of data in table
, mod (r, 500) pct02 -- 500 values = 0.2% of data in table
, mod (r, 1000) pct01 -- 1,000 values = 0.1% of data in table
, mod (r, 2000) pct005 -- 2,000 values = 0.05% of data in table
, mod (r, 5000) pct002 -- 5,000 values = 0.02% of data in table
, mod (r, 10000) pct001 -- 10,000 values = 0.01% of data in table
, mod (r, 20000) pct0005 -- 20,000 values = 0.005% of data in table
, mod (r, 50000) pct0002 -- 50,000 values = 0.002% of data in table
from (select rownum r
from (select rownum r from dual connect by level <= 1000) a,
(select rownum r from dual connect by level <= 1000) b,
(select rownum r from dual connect by level <= 1000) c
where rownum <= 10000000) ;
--
prompt Gathering Statistics ....
exec dbms_stats.gather_table_stats ('JOHN', 'SCANTEST')
--
prompt Creating Indexes ....
create unique index ix_scan_pkid on scantest (pkid) ;
create index ix_scan_pct2 on scantest (pct2) ;
create index ix_scan_pct1 on scantest (pct1) ;
create index ix_scan_pct05 on scantest (pct05) ;
create index ix_scan_pct02 on scantest (pct02) ;
create index ix_scan_pct01 on scantest (pct01) ;
TABLE STATISTICS
Table %F IT In Ext Next Ext %I
------------------------------ --- --- ---------------- ---------------- ---
SCANTEST 10 1 65,536 1,048,576
Avg Spc
Num Rows Blocks E Blocks Free/Blk Chains Avg Row Len
------------ ------------ -------- --------- ------ -----------
10,000,000 80,951 0 .00 0 53.000
Table Num Extents Blocks Avg Blocks
------------------------------ ------------ ------------ ------------
SCANTEST 151 81,920 543
Leaf Distinct Clustering
Index Height Blocks Keys Factor
-------------------- -------- -------- ---------------- ----------------
IX_SCAN_PKID 3 22,132 10,000,000 80,528
IX_SCAN_PCT2 3 19,503 50 4,026,368
IX_SCAN_PCT1 3 19,518 100 8,052,718
IX_SCAN_PCT05 3 20,212 200 10,000,000
IX_SCAN_PCT02 3 20,629 500 10,000,000
IX_SCAN_PCT01 3 20,768 1,000 10,000,000
Full Table Scan cost is calculated as follows:
FTS Cost = (BLOCKS * MREADTIM) / (MBRC * SREADTIM)
MREADTIM and SREADTIM are not set, and the others have default values in the system statistics in AUX_STAT$ (IOSEEKTIM = 10, IOTFRSPEED = 4096), so using the formula from before this gives SREADTIM of 12 ms and MREADTIM of 26 ms.Plugging these values into the previous formula gives about 22,000 as the cost for the FTS:
(80951 * 26) / (8 * 12) = 2104726 / 96 = 21,924.23
Density > (BLOCKS * MREADTIM) / (MBRC * SREADTIM * NUM_ROWS)
Density > (80,951 * 26) / (8 * 12 * 10,000,000) = 0.002192 or 0.22% approximately
Having calculated the FTS cost at about 22,000 we can also calculate the expected Index Scan costs, and see whether they do drop below the FTS cost under 0.22% of the data in the table.
An Index Scan cost has 2 components:
Index Access Cost = Levels + (Leaf Blocks * Filter Factor)
Data Access Cost = Clustering Factor * Filter Factor
For all indexes the number of Levels is 3 and the number of Leaf Blocks is about 20,500. Yes, it does vary but it is not significantly different for the tests we are doing here. Also from index PCT05 onwards the Clustering Factor is always 10 million i.e. it is not clustered and it is the row count in the table.
| Column Name | % of Rows returned | Fraction of Rows | Index Cost | Data Cost | Total Cost |
|---|---|---|---|---|---|
| pct1 | 1% | 0.01 | 3 + (20,500 * 0.01) = 3 + 205 = 208 | 8,000,000 * 0.01 = 80,000 | 80,208 |
| pct05 | 0.5% | 0.005 | 3 + (20,500 * 0.005) = 3 + 102.5 = 105.5 | 10M * 0.005 = 50,000 | 50,106 |
| pct02 | 0.2% | 0.002 | 3 + (20,500 * 0.002) = 3 + 41 = 44 | 10M * 0.002 = 20,000 | 20,044 |
| pct01 | 0.1% | 0.001 | 3 + 20.5 = 23.5 | 10M * 0.001 = 10,000 | 10,024 |
Our calculations confirm that the expected cost of an Index Scan should drop below that of a Full Table Scan when less than 0.22% of the data in the table is being selected.
Does this bear out in practise? Will Oracle switch from a Full Table Scan to an Index Scan when the fraction of rows requested drops below 0.0022? Lets see.
Note: The buffer cache and shared pool were flushed from a SYSDBA session before each query execution, so the buffer cache was empty in each case. And we are only interested in the I/O statistics from the query execution - other statistics such as Redo and SQL*Net bytes sent are not relevant and have been removed.
Query 1:
set autotrace on statistics
--
select sum (one) from scantest where pct2 = 1 ;
SUM(ONE)
----------
200000
Statistics
----------------------------------------------------------
80704 consistent gets
80541 physical reads
2 SQL*Net roundtrips to/from client
6 sorts (memory)
0 sorts (disk)
1 rows processed
dbms_xplan.display_cursor for the SQL_ID):select sum (one) from scantest where pct2 = 1
Plan hash value: 1745049784
-------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 22028 (100)| |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
|* 2 | TABLE ACCESS FULL| SCANTEST | 200K| 1171K| 22028 (1)| 00:00:01 |
-------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter("PCT2"=1)
- 2% of 10 million rows is 200 thousand, which the Optimizer has correctly estimated.
- Full table scan cost is 22,028. This is very close to my own estimate of about 22,000. The missing cost component would be for CPU work to filter each row.
- 80,541 physical reads occurred, which is very close to the 80,951 blocks reported in the table.
Query 2:
Repeat this with a lower percentage column - pct05
select sum (one) from scantest where pct05 = 1 ;
SUM(ONE)
----------
50000
1 row selected.
Statistics
----------------------------------------------------------
80704 consistent gets
80541 physical reads
2 SQL*Net roundtrips to/from client
6 sorts (memory)
0 sorts (disk)
1 rows processed
select sum (one) from scantest where pct05 = 1
Plan hash value: 1745049784
-------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 22040 (100)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
|* 2 | TABLE ACCESS FULL| SCANTEST | 50000 | 341K| 22040 (1)| 00:00:01 |
-------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter("PCT05"=1)
- Rows estimate is now 50,000, as expected
- Full table scan cost is slightly different for some unknown reason, but still about 22,000.
- Same number of physical reads occurred - 80,541.
Query 3:
Continue down to the next lower percentage column - pct02
select sum (one) from scantest where pct02 = 1 ;
SUM(ONE)
----------
20000
1 row selected.
Statistics
----------------------------------------------------------
20212 consistent gets
20060 physical reads
2 SQL*Net roundtrips to/from client
6 sorts (memory)
0 sorts (disk)
1 rows processed
select sum (one) from scantest where pct02 = 1
Plan hash value: 3458310886
------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 20049 (100)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
| 2 | TABLE ACCESS BY INDEX ROWID BATCHED| SCANTEST | 20000 | 136K| 20049 (1)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | IX_SCAN_PCT02 | 20000 | | 44 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("PCT02"=1)
- Now 0.2% of data in this table, which is low enough that an Index Scan should be cheaper
- Index cost is indeed lower than a Full Table Scan, as expected - 20,049 versus 22,040
- Index cost is very close to our own calculation of 20,044 - again CPU cost is the difference
- Only 20,060 physical reads now - Index branch blocks + Leaf blocks + Data rows
Query 4:
Repeat this with a lower percentage column - pct01
select sum (one) from scantest where pct01 = 1 ;
SUM(ONE)
----------
10000
1 row selected.
Statistics
----------------------------------------------------------
10192 consistent gets
10038 physical reads
2 SQL*Net roundtrips to/from client
6 sorts (memory)
0 sorts (disk)
1 rows processed
select sum (one) from scantest where pct01 = 1
Plan hash value: 1707962624
------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 10025 (100)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
| 2 | TABLE ACCESS BY INDEX ROWID BATCHED| SCANTEST | 10000 | 70000 | 10025 (1)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | IX_SCAN_PCT01 | 10000 | | 23 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("PCT01"=1)
- Index cost is halved because row count is halved - 10,025 versus 10,024 calculated
- Only 10,038 physical reads now - Index branch blocks + Leaf blocks + Data rows
Query 5:
If we force the use of an index for the query on the PCT05 column using a hint we get the following:
select /*+ index (scantest (pct05)) */ sum (one) from scantest where pct05 = 1 ;
SUM(ONE)
----------
50000
Statistics
----------------------------------------------------------
50271 consistent gets
50133 physical reads
2 SQL*Net roundtrips to/from client
6 sorts (memory)
0 sorts (disk)
1 rows processed
select /*+ index (scantest (pct05)) */ sum (one) from scantest where pct05 = 1
Plan hash value: 3145193111
------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 50116 (100)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
| 2 | TABLE ACCESS BY INDEX ROWID BATCHED| SCANTEST | 50000 | 341K| 50116 (1)| 00:00:02 |
|* 3 | INDEX RANGE SCAN | IX_SCAN_PCT05 | 50000 | | 104 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("PCT05"=1)
No comments:
Post a Comment