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  |
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  |
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.
|
|
|
|
Goto Forum:
Current Time: Thu Apr 25 08:27:43 CDT 2024
|
] 
Blog
Search
Help
Members
Register
Login
Home
