Home » RDBMS Server » Performance Tuning » CBO estimates Bitmap Index retrieval at 100 times Btree cost.
CBO estimates Bitmap Index retrieval at 100 times Btree cost. [message #108949] Sun, 20 February 2005 09:39 Go to next message
John Hammond
Messages: 2
Registered: February 2005
Junior Member
The actual problem we have is that the bitmap indexes we have defined are not being used
when they should be. I have investigated further and found the reason to be that the CBO
is saying that the 'index rowid table access' for a bitmap is estimated at (typically) 100
times the cost of retrieval for a btree. This is clearly rediculous and running the query
proves this as the bitmap access is roughly the same actual cost as the btree.

I want to point out various possibilities that I have explored.

1. Statistics have been collected. The example uses stats at table, index and column level
to prove that they do not make a difference.
2. The data is skewed which affects performance. My example deliberately chooses a uniform
distribution of the search key.
3. The clustering of the data affects performance making index retrieval ineffective. My
example deliberately has perfect data clustering (all rows with the same search key are
next to eachother).
4. Multiblock read count means superior io for tablescans, so the CBO is deliberately
avoiding use of indexes. The question is not tablescan v bitmap index, but btree v bitmap
index. I have given our system statistics on multiblock reads only so the example can be
reproduced.

This code was run on VMS ORACLE 9.2.0.5 and should be reproducable on any oracle system
that supports bitmap indexes.

Part 1 Example Table and Index Creation
=======================================

A table is created with 500,000 rows. 2 identical columns are defined having values
between 1 and 500. Values that are the same are clustered together in the file, making the
column a good candidate for an index..

SQL> set autotrace off
SQL> CREATE TABLE t1
2 NOLOGGING
3 AS
4 SELECT
5 ROWNUM ID,
6 TRUNC(ROWNUM/1000)+1 btree_col,
7 TRUNC(ROWNUM/1000)+1 bitmap_col,
8 RPAD('x',80) padding
9 FROM all_objects ao1, all_objects ao2
10 WHERE ROWNUM <= 500000;

Table created.

The table is analysed to ensure the cbo (cost based optimizer) comes into play and indexes
are built on the identical columns, one btree the other bitmap.

SQL> analyze table t1 compute statistics;

Table analyzed.

SQL> create index t1_btree on t1(btree_col);

Index created.

SQL> create bitmap index t1_bitmap on t1(bitmap_col);

Index created.

SQL> spool off

Part 2 Index retrieval costed with Table stats only and Actual Costs of Retrieval
=================================================================================

We now use the CBO to cost 2 very simple queries to retrieve values. The hints are
used to ensure that the CBO is used, and the index is chosen, in case the cost of a
tablescan read is very cheap in relation to an index read. On our system (see later) the
cost of a tablescan block read is approximately 1/4 of an index driven block read.

Through the Btree the estimated cost is 4.

SQL> set autotrace traceonly explain
SQL> SELECT /*+ choose index(t1_btree,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE btree_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=4 Card=1 Bytes
=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=4 Card=998 B
ytes=6986)

3 2 INDEX (RANGE SCAN) OF 'T1_BTREE' (NON-UNIQUE) (Cost=2
Card=998)

Through the Bitmap index the estimated cost is a staggering 320 80 TIMES THE BTREE ESTIMATE!

SQL> SELECT /*+ choose index(t1_bitmap,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE bitmap_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=320 Card=1 Byt
es=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=320 Card=998
Bytes=6986)

3 2 BITMAP CONVERSION (TO ROWIDS)
4 3 BITMAP INDEX (SINGLE VALUE) OF 'T1_BITMAP'

Lets now look at the actual cost of these queries. Both run very quickly and have been
run twice to show the effect of caching. The crucial figure that the CBO has been trying
to estimate is the number of consistent gets.

For the btree retrieval actual cost is 18 consistent gets.

SQL> set autotrace on stat
SQL> SELECT /*+ choose index(t1_btree,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE btree_col = 1;

MAX(ID)
----------
999

Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
18 consistent gets
3 physical reads
0 redo size
307 bytes sent via SQL*Net to client
426 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed

SQL> SELECT /*+ choose index(t1_btree,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE btree_col = 1;

MAX(ID)
----------
999

Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
18 consistent gets
0 physical reads
0 redo size
307 bytes sent via SQL*Net to client
426 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed

For the bitmap retrieval the actual cost is actually 16 consistent gets ONE TWENTIETH
OF THE CBO ESTIMATE. (and actually less than the btree retrieval).

SQL> SELECT /*+ choose index(t1_bitmap,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE bitmap_col = 1;

MAX(ID)
----------
999

Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
16 consistent gets
1 physical reads
0 redo size
307 bytes sent via SQL*Net to client
426 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed

SQL> SELECT /*+ choose index(t1_bitmap,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE bitmap_col = 1;

MAX(ID)
----------
999

Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
16 consistent gets
0 physical reads
0 redo size
307 bytes sent via SQL*Net to client
426 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed

SQL> spool off
Part 3 - The effect of Index Statistics on Cost Estimates
=========================================================

We Analyze both indexes

SQL> analyze index t1_btree compute statistics
2 ;

Index analyzed.

SQL> analyze index t1_bitmap compute statistics;

Index analyzed.

The bitmap index analysis has some statistics that are clearly unusual. It is saying that
only one data block has to be read in order to retrieve all the values for a particular
search key. This is clearly rediculous when you compare it with the sensible btree value.

These stats would tend to make bitmap retrieval more favourable. In fact the CBO completely
ignores stats generated on the bitmap index. I tried setting the values to the sensible ones
for the btree using DBMS_STATS.set_index_stats, but that made no difference.

SQL> SELECT ui.index_name, ui.avg_data_blocks_per_key, ui.num_rows
2 FROM user_indexes ui
3 WHERE ui.index_name LIKE 'T1%';

INDEX_NAME AVG_DATA_BLOCKS_PER_KEY NUM_ROWS
------------------------------ ----------------------- ----------
T1_BITMAP 1 501
T1_BTREE 13 500000

Here we can see the btree cost estimate has become closer to the true estimate thanks to
the index stats.

SQL> set autotrace traceonly explain
SQL> /* Formatted on 2005/02/19 17:13 (Formatter Plus v4.8.5) */
SQL> SELECT /*+ choose index(t1_btree,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE btree_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=20 Card=1 Byte
s=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=20 Card=998
Bytes=6986)

3 2 INDEX (RANGE SCAN) OF 'T1_BTREE' (NON-UNIQUE) (Cost=6
Card=998)

The estimated cost of Bitmap is UNAFFECTED BY INDEX STATS.

SQL> SELECT /*+ choose index(t1_bitmap,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE bitmap_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=320 Card=1 Byt
es=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=320 Card=998
Bytes=6986)

3 2 BITMAP CONVERSION (TO ROWIDS)
4 3 BITMAP INDEX (SINGLE VALUE) OF 'T1_BITMAP'

Part 4: The effect of histogram analysis on cost estimate
=========================================================

This should not have an effect because the data is deliberately uniformly distributed, and
indeed this is the case.

I have investigated where the data is skewed and the CBO does modify estimates for both
btree and bitmaps. It is very good at estimating the number of records retrieved and
generally takes its previous estimate for the average number of records retrieved and
adjusts it roughly in proportion.

SQL> analyze table t1 compute statistics for columns btree_col, bitmap_col size 250 ;

Table analyzed.

SQL> SELECT /*+ choose index(t1_btree,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE btree_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=20 Card=1 Byte
s=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=20 Card=1000
Bytes=7000)

3 2 INDEX (RANGE SCAN) OF 'T1_BTREE' (NON-UNIQUE) (Cost=6
Card=1000)

SQL> SELECT /*+ choose index(t1_bitmap,t1) */
2 MAX (ID)
3 FROM t1
4 WHERE bitmap_col = 1;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=HINT: CHOOSE (Cost=320 Card=1 Byt
es=7)

1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (BY INDEX ROWID) OF 'T1' (Cost=320 Card=100
0 Bytes=7000)

3 2 BITMAP CONVERSION (TO ROWIDS)
4 3 BITMAP INDEX (SINGLE VALUE) OF 'T1_BITMAP'

SQL> spool off
Part 5 - System Parameters and Statistics
=========================================

I have done my best to list the parameters and statistics on our system. If you require
other information, I will be happy to oblige.

SQL> select name, value, isdefault from v$parameter order by name ;

NAME
----------------------------------------------------------------
VALUE
--------------------------------------------------------------------------------
ISDEFAULT
---------
O7_DICTIONARY_ACCESSIBILITY
FALSE
TRUE

active_instance_count

TRUE

aq_tm_processes
0
TRUE

archive_lag_target
0
TRUE

audit_sys_operations
FALSE
TRUE

audit_trail
NONE
TRUE

background_core_dump
partial
TRUE

background_dump_dest
$1$DGA1:[[ORACLE9I.V920.admin.CHARTL.bdump]]
FALSE

backup_tape_io_slaves
FALSE
TRUE

bitmap_merge_area_size
4096000
FALSE

blank_trimming
FALSE
TRUE

buffer_pool_keep

TRUE

buffer_pool_recycle

TRUE

circuits
0
TRUE

cluster_database
FALSE
TRUE

cluster_database_instances
1
TRUE

cluster_interconnects

TRUE

commit_point_strength
1
TRUE

compatible
9.2.0.5
FALSE

control_file_record_keep_time
7
TRUE

control_files
DISK$FASTRAID:[[ORACLE9I.V920.admin.CHARTL]]ORA_CONTROL1.CON, DISK$FASTRAID:[[ORACL
E9I.V920.admin.CHARTL]]ORA_CONTROL2.CON
FALSE

core_dump_dest
$1$DGA1:[[ORACLE9I.V920.admin.CHARTL.cdump]]
FALSE

cpu_count
4
TRUE

create_bitmap_area_size
4096000
FALSE

cursor_sharing
EXACT
TRUE

cursor_space_for_time
FALSE
TRUE

db_16k_cache_size
0
TRUE

db_2k_cache_size
0
TRUE

db_32k_cache_size
0
TRUE

db_4k_cache_size
0
TRUE

db_8k_cache_size
0
TRUE

db_block_buffers
300000
FALSE

db_block_checking
FALSE
TRUE

db_block_checksum
TRUE
TRUE

db_block_size
8192
FALSE

db_cache_advice
OFF
TRUE

db_cache_size
0
TRUE

db_create_file_dest

TRUE

db_create_online_log_dest_1

TRUE

db_create_online_log_dest_2

TRUE

db_create_online_log_dest_3

TRUE

db_create_online_log_dest_4

TRUE

db_create_online_log_dest_5

TRUE

db_domain

TRUE

db_file_multiblock_read_count
64
FALSE

db_file_name_convert

TRUE

db_files
1500
FALSE

db_keep_cache_size
0
TRUE

db_name
CHARTL
FALSE

db_recycle_cache_size
0
TRUE

db_writer_processes
4
FALSE

dblink_encrypt_login
FALSE
TRUE

dbwr_io_slaves
0
TRUE

dg_broker_config_file1
ORA_DB:dr1@.dat
TRUE

dg_broker_config_file2
ORA_DB:dr2@.dat
TRUE

dg_broker_start
FALSE
TRUE

disk_asynch_io
FALSE
FALSE

dispatchers

TRUE

distributed_lock_timeout
60
TRUE

dml_locks
60000
FALSE

drs_start
FALSE
TRUE

enqueue_resources
60000
FALSE

event

TRUE

fal_client

TRUE

fal_server

TRUE

fast_start_io_target
0
TRUE

fast_start_mttr_target
0
TRUE

fast_start_parallel_rollback
LOW
TRUE

file_mapping
FALSE
TRUE

filesystemio_options
asynch
TRUE

fixed_date

TRUE

gc_files_to_locks

TRUE

global_context_pool_size

TRUE

global_names
FALSE
FALSE

hash_area_size
16384000
FALSE

hash_join_enabled
TRUE
TRUE

hi_shared_memory_address
0
TRUE

hs_autoregister
TRUE
TRUE

ifile

TRUE

instance_groups

TRUE

instance_name
CHARTL
FALSE

instance_number
0
TRUE

java_max_sessionspace_size
0
TRUE

java_pool_size
33554432
FALSE

java_soft_sessionspace_limit
0
TRUE

job_queue_processes
10
FALSE

large_pool_size
16777216
FALSE

license_max_sessions
0
TRUE

license_max_users
0
TRUE

license_sessions_warning
0
TRUE

local_listener

TRUE

lock_name_space

TRUE

lock_sga
FALSE
TRUE

log_archive_dest

TRUE

log_archive_dest_1

TRUE

log_archive_dest_10

TRUE

log_archive_dest_2

TRUE

log_archive_dest_3

TRUE

log_archive_dest_4

TRUE

log_archive_dest_5

TRUE

log_archive_dest_6

TRUE

log_archive_dest_7

TRUE

log_archive_dest_8

TRUE

log_archive_dest_9

TRUE

log_archive_dest_state_1
enable
TRUE

log_archive_dest_state_10
enable
TRUE

log_archive_dest_state_2
enable
TRUE

log_archive_dest_state_3
enable
TRUE

log_archive_dest_state_4
enable
TRUE

log_archive_dest_state_5
enable
TRUE

log_archive_dest_state_6
enable
TRUE

log_archive_dest_state_7
enable
TRUE

log_archive_dest_state_8
enable
TRUE

log_archive_dest_state_9
enable
TRUE

log_archive_duplex_dest

TRUE

log_archive_format
ARCH%T_%S.ARC
TRUE

log_archive_max_processes
2
TRUE

log_archive_min_succeed_dest
1
TRUE

log_archive_start
FALSE
TRUE

log_archive_trace
0
TRUE

log_buffer
2048000
FALSE

log_checkpoint_interval
10000
FALSE

log_checkpoint_timeout
1800
TRUE

log_checkpoints_to_alert
FALSE
TRUE

log_file_name_convert

TRUE

log_parallelism
1
TRUE

logmnr_max_persistent_sessions
1
TRUE

max_commit_propagation_delay
700
TRUE

max_dispatchers
5
TRUE

max_dump_file_size
10240
FALSE

max_enabled_roles
30
TRUE

max_rollback_segments
30
TRUE

max_shared_servers
20
TRUE

mts_circuits
0
TRUE

mts_dispatchers

TRUE

mts_listener_address

TRUE

mts_max_dispatchers
5
TRUE

mts_max_servers
20
TRUE

mts_multiple_listeners
FALSE
TRUE

mts_servers
0
TRUE

mts_service
CHARTL
TRUE

mts_sessions
0
TRUE

object_cache_max_size_percent
10
TRUE

object_cache_optimal_size
102400
TRUE

olap_page_pool_size
33554432
TRUE

open_cursors
800
FALSE

open_links
4
TRUE

open_links_per_instance
4
TRUE

optimizer_dynamic_sampling
1
TRUE

optimizer_features_enable
9.2.0
TRUE

optimizer_index_caching
0
TRUE

optimizer_index_cost_adj
100
TRUE

optimizer_max_permutations
2000
TRUE

optimizer_mode
CHOOSE
TRUE

oracle_trace_collection_name
oracle8
TRUE

oracle_trace_collection_path
ORA_RDBMS_LOG
TRUE

oracle_trace_collection_size
5242880
TRUE

oracle_trace_enable
FALSE
TRUE

oracle_trace_facility_name
oracle8
TRUE

oracle_trace_facility_path
ORA_RDBMS_ADMIN
TRUE

os_authent_prefix
OPS$
TRUE

os_roles
FALSE
TRUE

parallel_adaptive_multi_user
FALSE
TRUE

parallel_automatic_tuning
FALSE
FALSE

parallel_execution_message_size
2152
TRUE

parallel_instance_group

TRUE

parallel_max_servers
0
FALSE

parallel_min_percent
0
TRUE

parallel_min_servers
0
FALSE

parallel_server
FALSE
TRUE

parallel_server_instances
1
TRUE

parallel_threads_per_cpu
2
TRUE

partition_view_enabled
FALSE
TRUE

pga_aggregate_target
0
TRUE

plsql_compiler_flags
INTERPRETED
TRUE

plsql_native_c_compiler

TRUE

plsql_native_library_dir

TRUE

plsql_native_library_subdir_count
0
TRUE

plsql_native_linker

TRUE

plsql_native_make_file_name

TRUE

plsql_native_make_utility

TRUE

plsql_v2_compatibility
FALSE
TRUE

pre_page_sga
FALSE
TRUE

processes
350
FALSE

query_rewrite_enabled
false
TRUE

query_rewrite_integrity
enforced
TRUE

rdbms_server_dn

TRUE

read_only_open_delayed
FALSE
TRUE

recovery_parallelism
0
TRUE

remote_archive_enable
true
TRUE

remote_dependencies_mode
TIMESTAMP
TRUE

remote_listener

TRUE

remote_login_passwordfile
EXCLUSIVE
FALSE

remote_os_authent
FALSE
TRUE

remote_os_roles
FALSE
TRUE

replication_dependency_tracking
TRUE
TRUE

resource_limit
FALSE
TRUE

resource_manager_plan

TRUE

rollback_segments

TRUE

row_locking
always
TRUE

serial_reuse
DISABLE
TRUE

serializable
FALSE
TRUE

service_names
CHARTL
TRUE

session_cached_cursors
0
TRUE

session_max_open_files
10
TRUE

sessions
390
TRUE

sga_max_size
3030961192
TRUE

shadow_core_dump
partial
TRUE

shared_memory_address
0
TRUE

shared_pool_reserved_size
17616076
TRUE

shared_pool_size
352321536
FALSE

shared_server_sessions
0
TRUE

shared_servers
0
TRUE

sort_area_retained_size
4096000
FALSE

sort_area_size
4096000
FALSE

spfile

TRUE

sql92_security
FALSE
TRUE

sql_trace
FALSE
TRUE

sql_version
NATIVE
TRUE

standby_archive_dest
ORA_ARCHIVE:
TRUE

standby_file_management
MANUAL
TRUE

star_transformation_enabled
FALSE
TRUE

statistics_level
TYPICAL
TRUE

tape_asynch_io
TRUE
TRUE

thread
0
TRUE

timed_os_statistics
0
TRUE

timed_statistics
TRUE
FALSE

trace_enabled
TRUE
TRUE

tracefile_identifier

TRUE

transaction_auditing
TRUE
TRUE

transactions
400
FALSE

transactions_per_rollback_segment
20
FALSE

undo_management
MANUAL
TRUE

undo_retention
900
TRUE

undo_suppress_errors
FALSE
TRUE

undo_tablespace

TRUE

use_indirect_data_buffers
FALSE
TRUE

user_dump_dest
$1$DGA1:[[ORACLE9I.V920.admin.CHARTL.udump]]
FALSE

utl_file_dir
$1$DGA3:[[CHARTDIST]], TONY_1, TONY_2:, CHART_DIST:, *
FALSE

vlm_backing_storage_file
FALSE
TRUE

vlm_sga_base_address
0xfffffef000000000
FALSE

workarea_size_policy
MANUAL
TRUE

SQL> select * from sys.aux_stats$ where sname = 'SYSSTATS_MAIN';

SNAME PNAME PVAL1
------------------------------ ------------------------------ ----------
PVAL2
--------------------------------------------------------------------------------
SYSSTATS_MAIN CPUSPEED 4598

SYSSTATS_MAIN MAXTHR -1

SYSSTATS_MAIN MBRC 10

SYSSTATS_MAIN MREADTIM 9.708

SYSSTATS_MAIN SLAVETHR -1

SYSSTATS_MAIN SREADTIM 4.121

6 rows selected.

SQL> spool off
Re: CBO estimates Bitmap Index retrieval at 100 times Btree cost. [message #109009 is a reply to message #108949] Mon, 21 February 2005 02:39 Go to previous message
John Hammond
Messages: 2
Registered: February 2005
Junior Member
Replies to Points Raised so far
===============================

1. Cost estimate is not measuring consistent gets

Cost estimate is approximately number of logical reads (consistent gets in this case). There is
a CPU element, but in this io based example it is negligible. The optimizer does not know the

effect of caching so in effect assumes the worst case that each logical read results in a physical

read.

2. The two queries are not identical.

The two queries are identical in all respects bar the point in question: one is using a btree and
the other a bitmap.

3. The hints are not the best I could use.

I have made a syntax mistake in that the hints should be INDEX(t1 t1_btree) etc (got the order

reversed). Sorry about that. However the CBO shows it has done what I intended it to in the
output explaining its plan.

The index_combine hint has been suggested as a better hint for bitmap indexes and certainly it is
recommended by Oracle. This is much appreciated and I will use it in future. However I used the
hint and got the same CBO cost on the bitmap retrieval.

4. I should be using DBMS_STATS instead of ANALYZE.

I have tried this to see if it makes any difference. DBMS_STATS calculates exactly the same stats
as ANALYZE and there is no difference in the results. I used ANALYZE because more people are
familiar with it. DBMS_STATS is recommended by Oracle because it is more efficient, as it performs
the same tasks as ANALYZE but in parallel.

5. The search key in my bitmap index has 501 distinct values and is not of low enough cardinality
to be a bitmap index.

The bitmap index works fine with 501 distinct values (it outperforms the btree in the query, even
though the CBO estimates it at 80 times slower).

The point is what is low cardinality? 2 values? 100 values? I would refer anyone interested in this

point to Jonathan Lewis' excellent article on this matter.
http://www.dbazine.com/jlewis3.shtml

6. I should investigate using 10053 event.

Good point! I shall be making this my next investigation.
Previous Topic: same statement reparsing again.Pl help
Next Topic: Does DML on Global temp table generates REDO
Goto Forum:
  


Current Time: Wed Feb 28 04:29:13 CST 2024