10 Replies Latest reply: Feb 21, 2013 6:10 AM by rahulras RSS

    Bitmap vs Btree

    user10858330
      Hello,

      i'm little surprised while creating index. i have a partition table having 10784102 records in them. one of its column have 8558592 distinct values in them.
      which is equal to 80% of table data. therefore, cardinality of this column is very high so btree index is good for this situation.
      moreover there is no null value in the column as well. however, when i create btree index
      and do a simple select index does not scan. whereas when i create bitmap index on this column it scan index. here is my test case
      Btree index 
      explain plan for 
      select   SESS_SESSESSIONID  from REBE01S2_DG0 
      
      
      SELECT * FROM table(dbms_xplan.display);
      
      explain plan succeeded.
      PLAN_TABLE_OUTPUT                                                                                                                                                                                                                                                                                            
      ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 
      Plan hash value: 854853906                                                                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                                                                                   
      ----------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                           
      | Id  | Operation            | Name         | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |                                                                                                                                                                           
      ----------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                           
      |   0 | SELECT STATEMENT     |              |    10M|   287M|   103K  (1)| 00:24:07 |       |       |        |      |            |                                                                                                                                                                           
      |   1 |  PX COORDINATOR      |              |       |       |            |          |       |       |        |      |            |                                                                                                                                                                           
      |   2 |   PX SEND QC (RANDOM)| :TQ10000     |    10M|   287M|   103K  (1)| 00:24:07 |       |       |  Q1,00 | P->S | QC (RAND)  |                                                                                                                                                                           
      |   3 |    PX BLOCK ITERATOR |              |    10M|   287M|   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWC |            |                                                                                                                                                                           
      |   4 |     TABLE ACCESS FULL| REBE01S2_DG0 |    10M|   287M|   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                                                           
      ----------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                           
      
      11 rows selected
      
      *drop btree and create bitmap* 
      
      PLAN_TABLE_OUTPUT                                                                                                                                                                                                                                                                                            
      ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 
      Plan hash value: 1533847669                                                                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                                                                                   
      -----------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                        
      | Id  | Operation                       | Name                 | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |                                                                                                                                                        
      -----------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                        
      |   0 | SELECT STATEMENT                |                      |    10M|   287M|  7170   (1)| 00:01:41 |       |       |        |      |            |                                                                                                                                                        
      |   1 |  PX COORDINATOR                 |                      |       |       |            |          |       |       |        |      |            |                                                                                                                                                        
      |   2 |   PX SEND QC (RANDOM)           | :TQ10000             |    10M|   287M|  7170   (1)| 00:01:41 |       |       |  Q1,00 | P->S | QC (RAND)  |                                                                                                                                                        
      |   3 |    PX BLOCK ITERATOR            |                      |    10M|   287M|  7170   (1)| 00:01:41 |     1 |    15 |  Q1,00 | PCWC |            |                                                                                                                                                        
      |   4 |     BITMAP CONVERSION TO ROWIDS |                      |    10M|   287M|  7170   (1)| 00:01:41 |       |       |  Q1,00 | PCWP |            |                                                                                                                                                        
      |   5 |      BITMAP INDEX FAST FULL SCAN| MINDX_REBE01S2_DG0_0 |       |       |            |          |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                                        
      -----------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                        
      
      12 rows selected
      Both taking different time bitmap query return in 8 seconds whereas btree index take 2mints .
      Oracle Database 11g Enterprise Edition Release 11.2.0.3.0 - 64bit Production
      TNS for 64-bit Windows: Version 11.2.0.3.0 - Production
      Table and index both partition local. Range
        • 1. Re: Bitmap vs Btree
          JohnWatson
          You would need to declare the column NOT NULL before the b-tree index could be considered for use.
          --
          John Watson
          Oracle Certified Master DBA
          http://skillbuilders.com
          • 2. Re: Bitmap vs Btree
            Hemant K Chitale
            select SESS_SESSESSIONID from REBE01S2_DG0
            Please show the index definition. Is the index on the single column alone or is it a composite index.

            Your query is not requesting for a specific SESS_SESSESSIONID but for all the SESS_SESSESSIONID values -- all 10million. A B-tree could satisfy the query as an Index Fast Full Scan. However, it would still be large -- look at the LEAF_BLOCKS and BLEVEL statistics for the index. The Optimizer figures that a Full Table Scan (with parallelism enabled by default at the table or session level !!) is faster than reading the whole index.

            A Bitmap index is compressed and smaller than a B-Tree index. It is faster, still with parallelism enabled, to do an Index Fast Full Scan of the Bitmap index.

            You could remove parallelism degree on the table and compare the COST and Plans.
            You could query for a single SESS_SESSESSIONID or a small range of SESS_SESSESSIONID values and compare the COST and Plans.


            Hemant K Chitale
            • 3. Re: Bitmap vs Btree
              Jonathan Lewis
              user10858330 wrote:
              moreover there is no null value in the column as well. however, when i create btree index
              and do a simple select index does not scan. whereas when i create bitmap index on this column it scan index. here is my test case
              As John pointed out, the most obvious guess is that you haven't DECLARED the column to be not null, so the optimizer has to assume that there may be nulls - which means visiting the table in the case of the B-tree.

              If this isn't the case, then the first simple test is to add an /*+ index_ffs(alias (column_name)) */ hint to the query to see what the cost of the fast full scan on the b-tree index would be.

              Regards
              Jonathan Lewis
              • 4. Re: Bitmap vs Btree
                user10858330
                it is a single column index moreover when i use distinct with SESS_SESSESSIONID i should use index but i wouldn't here is the execution plan with distinct

                explain plan for
                select distinct SESS_SESSESSIONID from REBE01S2_DG0
                explain plan succeeded.
                PLAN_TABLE_OUTPUT                                                                                                                                                                                                                                                                                            
                ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 
                Plan hash value: 3888779724                                                                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                                                                                             
                ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                | Id  | Operation               | Name         | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |                                                                                                                                                                
                ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                |   0 | SELECT STATEMENT        |              |  8558K|   228M|       |   116K  (1)| 00:27:10 |       |       |        |      |            |                                                                                                                                                                
                |   1 |  PX COORDINATOR         |              |       |       |       |            |          |       |       |        |      |            |                                                                                                                                                                
                |   2 |   PX SEND QC (RANDOM)   | :TQ10001     |  8558K|   228M|       |   116K  (1)| 00:27:10 |       |       |  Q1,01 | P->S | QC (RAND)  |                                                                                                                                                                
                |   3 |    HASH UNIQUE          |              |  8558K|   228M|   371M|   116K  (1)| 00:27:10 |       |       |  Q1,01 | PCWP |            |                                                                                                                                                                
                |   4 |     PX RECEIVE          |              |    10M|   287M|       |   103K  (1)| 00:24:07 |       |       |  Q1,01 | PCWP |            |                                                                                                                                                                
                |   5 |      PX SEND HASH       | :TQ10000     |    10M|   287M|       |   103K  (1)| 00:24:07 |       |       |  Q1,00 | P->P | HASH       |                                                                                                                                                                
                |   6 |       PX BLOCK ITERATOR |              |    10M|   287M|       |   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWC |            |                                                                                                                                                                
                |   7 |        TABLE ACCESS FULL| REBE01S2_DG0 |    10M|   287M|       |   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                                                
                ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                
                14 rows selected
                • 5. Re: Bitmap vs Btree
                  user10858330
                  Hi Jonathan when i use hint strange plan is explain. Pleas have a look
                  select   /*+ index_FFS(REBE01S2_DG0(SESS_SESSESSIONID)) */ distinct  SESS_SESSESSIONID  from REBE01S2_DG0
                  PLAN_TABLE_OUTPUT                                                                                                                                                                                                                                                                                            
                  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 
                  Plan hash value: 3888779724                                                                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                                                                                               
                  ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                  | Id  | Operation               | Name         | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |                                                                                                                                                                
                  ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                  |   0 | SELECT STATEMENT        |              |  8558K|   228M|       |   116K  (1)| 00:27:10 |       |       |        |      |            |                                                                                                                                                                
                  |   1 |  PX COORDINATOR         |              |       |       |       |            |          |       |       |        |      |            |                                                                                                                                                                
                  |   2 |   PX SEND QC (RANDOM)   | :TQ10001     |  8558K|   228M|       |   116K  (1)| 00:27:10 |       |       |  Q1,01 | P->S | QC (RAND)  |                                                                                                                                                                
                  |   3 |    HASH UNIQUE          |              |  8558K|   228M|   371M|   116K  (1)| 00:27:10 |       |       |  Q1,01 | PCWP |            |                                                                                                                                                                
                  |   4 |     PX RECEIVE          |              |    10M|   287M|       |   103K  (1)| 00:24:07 |       |       |  Q1,01 | PCWP |            |                                                                                                                                                                
                  |   5 |      PX SEND HASH       | :TQ10000     |    10M|   287M|       |   103K  (1)| 00:24:07 |       |       |  Q1,00 | P->P | HASH       |                                                                                                                                                                
                  |   6 |       PX BLOCK ITERATOR |              |    10M|   287M|       |   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWC |            |                                                                                                                                                                
                  |   7 |        TABLE ACCESS FULL| REBE01S2_DG0 |    10M|   287M|       |   103K  (1)| 00:24:07 |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                                                
                  ---------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                
                  
                  14 rows selected
                  when i remove FFS from hint it use other column index
                  PLAN_TABLE_OUTPUT                                                                                                                                                                                                                                                                                            
                  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 
                  Plan hash value: 3694858448                                                                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                                                                                               
                  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                        
                  | Id  | Operation                               | Name                 | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |                                                                                                                                        
                  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                        
                  |   0 | SELECT STATEMENT                        |                      |  8558K|   228M|       |   539K  (1)| 02:05:47 |       |       |        |      |            |                                                                                                                                        
                  |   1 |  PX COORDINATOR                         |                      |       |       |       |            |          |       |       |        |      |            |                                                                                                                                        
                  |   2 |   PX SEND QC (RANDOM)                   | :TQ10001             |  8558K|   228M|       |   539K  (1)| 02:05:47 |       |       |  Q1,01 | P->S | QC (RAND)  |                                                                                                                                        
                  |   3 |    HASH UNIQUE                          |                      |  8558K|   228M|   371M|   539K  (1)| 02:05:47 |       |       |  Q1,01 | PCWP |            |                                                                                                                                        
                  |   4 |     PX RECEIVE                          |                      |    10M|   287M|       |   525K  (1)| 02:02:44 |       |       |  Q1,01 | PCWP |            |                                                                                                                                        
                  |   5 |      PX SEND HASH                       | :TQ10000             |    10M|   287M|       |   525K  (1)| 02:02:44 |       |       |  Q1,00 | P->P | HASH       |                                                                                                                                        
                  |   6 |       PX PARTITION RANGE ALL            |                      |    10M|   287M|       |   525K  (1)| 02:02:44 |     1 |    15 |  Q1,00 | PCWC |            |                                                                                                                                        
                  |   7 |        TABLE ACCESS BY LOCAL INDEX ROWID| REBE01S2_DG0         |    10M|   287M|       |   525K  (1)| 02:02:44 |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                        
                  |   8 |         BITMAP CONVERSION TO ROWIDS     |                      |       |       |       |            |          |       |       |  Q1,00 | PCWP |            |                                                                                                                                        
                  |   9 |          BITMAP INDEX FULL SCAN         | MINDX_REBE01S2_DG0_3 |       |       |       |            |          |     1 |    15 |  Q1,00 | PCWP |            |                                                                                                                                        
                  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                        
                  
                  16 rows selected
                  MINDX_REBE01S2_DG0_3 plz clarify this
                  • 6. Re: Bitmap vs Btree
                    user10858330
                    A Bitmap index is compressed and smaller than a B-Tree index. It is faster, still with parallelism enabled, to do an Index Fast Full Scan of the Bitmap index.
                    i have column ID in table which increment by 1 when i got new record in table. Suppose there is read only data no update and delete ever performed. what type of index is good for this ID column
                    Bitmap or Btree? and why it is always said Bitmap is good for low cardinality data. in my case, i decided column should have btree index becoz high cardinality of data. but CBO no going to use Btree. Not Null mention by john is new thing for me i will check and let you know does it impact or not
                    • 7. Re: Bitmap vs Btree
                      Hemant K Chitale
                      Do you really want to retrieve ALL (10million) values ? If the column is not defined as a NOT NULL column, the optimizer will assume that there may be one or more NULL values in that column in the table. These NULL values wouldn't appear in a BTree Index so Oracle cannot use the BTree index.
                      So, John suggests changing the column definition to a NOT NULL if it really does not contain any NULLs. That way, the optimizer will know that all 10million values are present in the index and can compare the cost of an Index Fast Full Scan with a Full Table Scan.
                      Alternatively, as I suggested, if your query is for a range of values in the column, the optimizer can choose to use the index because the range of values does not include a NULL.
                      I have column ID in table which increment by 1 when i got new record in table.
                      Use a BTree Index, not a Bitmap index.

                      Hemant K Chitale

                      Edited by: Hemant K Chitale on Feb 21, 2013 5:36 PM
                      • 8. Re: Bitmap vs Btree
                        Jonathan Lewis
                        user10858330 wrote:
                        Bitmap or Btree? and why it is always said ...
                        It's not ALWAYS said, it's loudly, commonly, and incorrectly said....
                        Here's some basic reading on the difference between btree and bitmap indexes, with a couple of forward links to further reading: http://jonathanlewis.wordpress.com/2009/12/23/btree-bitmap/

                        Regards
                        Jonathan Lewis
                        • 9. Re: Bitmap vs Btree
                          Jonathan Lewis
                          user10858330 wrote:
                          Hi Jonathan when i use hint strange plan is explain. Pleas have a look
                          The first plan you've shown is exactly as expected when sess_sesssessionid has not been declared as NOT NULL. I notice, though, that you've changed the query from the original.
                          select   /*+ index_FFS(REBE01S2_DG0(SESS_SESSESSIONID)) */ distinct  SESS_SESSESSIONID  from REBE01S2_DG0
                          when i remove FFS from hint it use other column index
                          MINDX_REBE01S2_DG0_3 plz clarify this
                          But in the previous post in response to Hemant, it didn't - this suggests that you're mixing up your experiments.
                          And you surely don't expect us to guess what's going on with the other index when you haven't even given us the definition of the index.

                          Since the column hasn't been declared NOT NULL there wasn't any point in trying the hint. Instead you could (for the purposes of investigating a point) run your query with the predicate "sess_sessessionid is not null".

                          Regards
                          Jonathan Lewis
                          • 10. Re: Bitmap vs Btree
                            rahulras
                            Is the stats up-to-date on that table? or rather, make sure there is no wrong stats on the table
                            E.g. you collected stats when table was empty (or very small), which set the stats to zerop rows (or very less rows), then you inserted 10M records and ran the query. Is something like that happening here?