1 2 Previous Next 17 Replies Latest reply: Feb 10, 2012 5:10 AM by Billy~Verreynne RSS

    bimtap conversion to rowid question

    AlleT
      I really can't figure out how oracle can convert bitmaps (in bitmap indexes) to rowid.

      Let's say there is a huge table T with a column C which has value 'V' for the Nth row and 'X' for all other rows.

      Let's say one issues the following query: SELECT * FROM T WHERE C='V'

      Oracle does not know how many rows are inside blocks, so how can it understand that the Nth row is in a certain block? Does it sample some blocks around the right one until it finds it?

      The algorythm of bitmap conversion to rowid is said to be internal but maybe someone has some clues about this.

      Thanks in advance
        • 1. Re: bimtap conversion to rowid question
          Tubby
          AlleT wrote:
          I really can't figure out how oracle can convert bitmaps (in bitmap indexes) to rowid.

          Let's say there is a huge table T with a column C which has value 'V' for the Nth row and 'X' for all other rows.

          Let's say one issues the following query: SELECT * FROM T WHERE C='V'

          Oracle does not know how many rows are inside blocks, so how can it understand that the Nth row is in a certain block? Does it sample some blocks around the right one until it finds it?

          The algorythm of bitmap conversion to rowid is said to be internal but maybe someone has some clues about this.

          Thanks in advance
          http://docs.oracle.com/cd/E11882_01/server.112/e25789/indexiot.htm#CNCPT1182

          "
          Each bit in the bitmap corresponds to a possible rowid. If the bit is set, then the row with the corresponding rowid contains the key value. A mapping function converts the bit position to an actual rowid, so the bitmap index provides the same functionality as a B-tree index although it uses a different internal representation.
          "
          • 2. Re: bimtap conversion to rowid question
            AlleT
            Ok, but my question is: how that function can do that? oracle does not know how many rows are inside a block so how can it convert a position to a rowid?

            Let's say you know you have to fetch the forth row: how do you know where that row is?

            Thanks
            • 3. Re: bimtap conversion to rowid question
              Tubby
              AlleT wrote:
              Ok, but my question is: how that function can do that? oracle does not know how many rows are inside a block so how can it convert a position to a rowid?
              Did you read the
              "
              Each bit in the bitmap corresponds to a possible rowid.
              "
              Part of the above quote? So ... why do you think oracle NEEDS to know how many rows are inside a block, how would that information be useful given the above quote?
              AlleT wrote:
              Let's say you know you have to fetch the forth row: how do you know where that row is?
              What is "the fourth row", and why do you think Oracle would care about that? There is no concept of randomly grabbing the nth row from a result set. If you needed a particular row you would specify so in your query ...

              Typically something like
              select <columns>
              from
              (
                 select <columns>, row_number() over (order by <something>) as rn
                 from <table>
                 where <conditions>
              )
              where rn <= 10
              So the inner query gets resolved and a row gets assigned a value by our analytic clause. The query needs to be resolved and the outputs ordered in order for our RN to be assigned.

              That's where (if appropriate) the bitmap index gets used, in determining the results of the inner query. The results are filtered (bitmap index access we'll say) and then the analytic clause is applied to the resultant result set.
              • 4. Re: bimtap conversion to rowid question
                rp0428
                >
                oracle does not know how many rows are inside a block
                >
                No - but Oracle does know the maximum number of rows that can be in a block - the Hakan factor.
                The Hakan factor is set to a fixed value when the table is created and can be modified after the
                table is created by
                alter table test minimize records_per_block;
                That will set the Hakan factor to a value representing the largest number of rows in any block in the table.

                You can easily force this to be any value you want:
                create table test(field number);
                insert into test values(1);
                commit;
                alter table test minimize records_per_block;
                After the above Oracle will not put more than 1 record into any block of the table.

                If you want to see what the Hakan factor is for a table use this query:
                select do.object_name, spare1
                from tab$, dba_objects do
                where do.object_id = tab$.obj#
                and do.owner = 'SCOTT'
                and do.object_name = 'EMP'
                
                EMP,736
                So as Tubby said Oracle reserves a bit for every possible rowid in each block in the range of ROWIDs.

                See the doc for the DBMS_ROWID package - http://docs.oracle.com/cd/B28359_01/appdev.111/b28419/d_rowid.htm

                Each ROWID for a standard hash table includes the file #, block# and row#. So the rowid START and END values combined
                with the max number of rows in a block tell Oracle how many bits to reserve to represent each block in the range.

                When the bitmap index is created Oracle sets the bits for non-existent rows to zero. This place holder bit will get set to one
                if that row in the block gets populated later and has the proper value.

                Since bitmap index entries have bits for rows that may not exist Oracle doesn't use bitmap indexes to count records.
                • 5. Re: bimtap conversion to rowid question
                  AlleT
                  thanks rp0428, you made me finally understand this thing! (I didn't manage to find any bit of docs about this mechanism).
                  • 6. Re: bimtap conversion to rowid question
                    Aman....
                    Excellent! Thanks a bunch for the explanation :) .

                    A small doubt! You said,
                    After the above Oracle will not put more than 1 record into any block of the table.
                    Is it that Oracle will not put any more than 1 record in the block of the table or it would now always believe that the highest number of records in a block are just one?


                    Aman....

                    Edited by: Aman.... on Feb 9, 2012 5:34 PM
                    • 7. Re: bimtap conversion to rowid question
                      Billy~Verreynne
                      rp0428 wrote:

                      Since bitmap index entries have bits for rows that may not exist Oracle doesn't use bitmap indexes to count records.
                      This is not exactly what I'm seeing - an execution plan for a select count(*) using a bitmap (and as the bitmap translates into very little I/O compared to b+tree indexes or the hash table, it is significantly faster option for counting rows in VLT's).
                      SQL> select /*+parallel(60) parallel_index(x,SI_XXXXXXXXX_XXXX,60)*/ count(*) from daily_xxxx x;
                      
                        COUNT(*)
                      ----------
                      1422302250
                      
                      Elapsed: 00:00:23.62
                      
                      Execution Plan
                      ----------------------------------------------------------
                      Plan hash value: 2191033651
                      
                      --------------------------------------------------------------------------------------------------------------------------------------------
                      | Id  | Operation                         | Name              | Rows  | Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |
                      --------------------------------------------------------------------------------------------------------------------------------------------
                      |   0 | SELECT STATEMENT                  |                   |     1 |  5652   (1)| 00:00:12 |       |       |        |      |            |
                      |   1 |  SORT AGGREGATE                   |                   |     1 |            |          |       |       |        |      |            |
                      |   2 |   PX COORDINATOR                  |                   |       |            |          |       |       |        |      |            |
                      |   3 |    PX SEND QC (RANDOM)            | :TQ10000          |     1 |            |          |       |       |  Q1,00 | P->S | QC (RAND)  |
                      |   4 |     SORT AGGREGATE                |                   |     1 |            |          |       |       |  Q1,00 | PCWP |            |
                      |   5 |      PX BLOCK ITERATOR            |                   |  1465M|  5652   (1)| 00:00:12 |     1 |    40 |  Q1,00 | PCWC |            |
                      |   6 |       BITMAP CONVERSION COUNT     |                   |  1465M|  5652   (1)| 00:00:12 |       |       |  Q1,00 | PCWP |            |
                      |   7 |        BITMAP INDEX FAST FULL SCAN| SI_XXXXXXXXX_XXXX |       |            |          |     1 |    40 |  Q1,00 | PCWP |            |
                      --------------------------------------------------------------------------------------------------------------------------------------------
                      
                      Note
                      -----
                         - Degree of Parallelism is 60 because of hint
                      
                      SQL> 
                      • 8. Re: bimtap conversion to rowid question
                        AlleT
                        Billy, your post may compromise the preceding explanation.

                        Can you post the code for creating the table and the bitmap index ?
                        • 9. Re: bimtap conversion to rowid question
                          rp0428
                          Thanks Billy for the example. Should have run one myself.

                          I posted a question about your results on Richard Foote's blog (http://richardfoote.wordpress.com/2011/07/05/bitmap-indexes-and-not-equal-holy-holy/#comment-53269) where he discusses bit-map index structures and why Oracle can't use a stand-alone bit-map index for a <> query.

                          This is the quote from that blog that I can't reconcile with the plan you show:
                          >
                          However, the value of a bit set to 0 can therefore potentially mean one of two things. It could mean that the row exists but doesn’t have the value represented by the index entry or it could mean that the row simply doesn’t exist at all. There is no way for Oracle to tell the difference between these two scenarios.
                          >
                          So if a bit can mean the row doesn't exist and you don't want to count non-existent rows in a 'count(*)' how does Oracle actually determine which bits are for rows that exist and count them?

                          The only explanation I can think of is that even though the table name isn't shown in the plan Oracle must be visiting every block header to determine which rows actually exist. Problem is that if it needed to do that there wouldn't be much point in using the index.
                          • 10. Re: bimtap conversion to rowid question
                            AlleT
                            Hi rp0428 if you think about it, if the column on which the index is built is NOT NULL oracle can scan the index counting only the 1 values and ignoring the 0 (which may refer to non-existing rows). So it can count the rows without accessing the table.

                            Do you agree ?
                            • 11. Re: bimtap conversion to rowid question
                              rp0428
                              No I don't agree but that means the answer is that Oracle is using all of the bitmap index entries since every existing row has to be accounted for in one of the entries. If you OR all of the entries together then the 1's mean that a row exists.

                              Good insight!
                              • 12. Re: bimtap conversion to rowid question
                                Billy~Verreynne
                                rp0428 wrote:
                                Thanks Billy for the example. Should have run one myself.
                                I have seen this specific behaviour consistently since 9i (or was it 8i?) - the CBO choosing a bitmap iindex when doing a row count, instead of using a B+tree index or FTS. Posted about it (posting called "+My database is too fast+") in comp.databases.oracle.server (cdos) back in 2003.

                                I have used this quite a few times through the years, and on different Oracle versions, on my larger tables to show just how fast a select count(*) can be and that it is not about the number of rows in the table, but the amount of I/O needed for doing the count.

                                When I ran it today I was expecting the CBO to choose a bitmap index on the VLT (same basic database that I had on 10.1 and 10.2). But this time I had to force it and force it to run in parallel. Which was a bit unexpected. Not the way the CBO behaved on such tables since 9i.
                                I posted a question about your results on Richard Foote's blog (http://richardfoote.wordpress.com/2011/07/05/bitmap-indexes-and-not-equal-holy-holy/#comment-53269) where he discusses bit-map index structures and why Oracle can't use a stand-alone bit-map index for a <> query.
                                That's a man that knows his indexes. ;-)

                                He was also a regular on cdos back then.
                                The only explanation I can think of is that even though the table name isn't shown in the plan Oracle must be visiting every block header to determine which rows actually exist. Problem is that if it needed to do that there wouldn't be much point in using the index.
                                Hmm.. to visit the block header means a full block read, right? If that's the case, this is not what I'm seeing as this counting of rows via a bitmap index has always been significantly faster and with seriously less I/O than a FTS.

                                Read Richard's response and it seems he's in agreement that the index alone suffices for counting all rows.
                                • 13. Re: bimtap conversion to rowid question
                                  Billy~Verreynne
                                  AlleT wrote:
                                  Billy, your post may compromise the preceding explanation.
                                  It will only strengthen the explanation and understanding of Oracle's internal workings. ;-)
                                  Can you post the code for creating the table and the bitmap index ?
                                  Standard hash table. Range partitioned (per day in this case). Several local partition bitmap indexes on it. Typical type of table one would expect in a data warehouse type system. Nothing special.

                                  And as I've mentioned, this behaviour is not new. I have seen and used this method for counting VLTs since 9i if not earlier. Makes for a great show.

                                  Once had Ingres kernel developers working in our offices (supporting a large Ingres database and trying to fix a serious low level bug). With me being the sole Oracle guy in the office (supporting the Oracle billing databases), talk invariable lead to "+whose is the biggest and best+".

                                  They kind of lost the argument after I pulled this select count on our production system on a table with several 100 million rows and it ran in something like 7 seconds or less - and they could not even get close to that performance with an Ingres table with a few 100 thousand rows. Of course, I did not tell them it was due to bitmap indexes. And parallel processing. And heating up the buffer cache first. Simply let them stew in loser's sauce.. :D
                                  • 14. Re: bimtap conversion to rowid question
                                    rp0428
                                    Aman - sorry to be late getting back to you but wanted to run a few more tests.

                                    I believe it is true that:
                                    >
                                    Oracle will not put any more than the Hakan factor number of records in the block of the table.
                                    >
                                    Had to reword you question and my answer based on further research and tests. See Martin Preiss comments at
                                    >
                                    http://richardfoote.wordpress.com/2011/07/19/bitmap-indexes-minimize-records_per_block-little-wonder/
                                    http://oracle-randolf.blogspot.com/2011/07/logical-io-evolution-part-1-baseline.html
                                    >
                                    It seems that SPARE1 holds a bit-encoded version of the Hakan factor and that maybe it can't be set to 1 but 2 works.
                                    Here is an example you can use to see the record and block counts go up and it even though 4 or 8 blocks get allocated at a time the math shows records per block is clearly being limited.
                                    Setup -
                                    drop table hakan
                                    /
                                    create table hakan as select 'ABCDE' char5 from dual
                                    /
                                    exec dbms_stats.gather_table_stats(ownname=>'SCOTT', tabname=>'HAKAN', estimate_percent=>null, cascade=>true, method_opt=>'FOR ALL COLUMNS SIZE 1')
                                    
                                    select table_name, num_rows, blocks, empty_blocks from user_tables where table_name = 'HAKAN'
                                    /
                                    alter table HAKAN minimize records_per_block
                                    /
                                    Now repeat the following and watch the block count after each run
                                    insert into HAKAN values ('ABCDE')
                                    /
                                    /
                                    exec dbms_stats.gather_table_stats(ownname=>'SCOTT', tabname=>'HAKAN', estimate_percent=>null, cascade=>true, method_opt=>'FOR ALL COLUMNS SIZE 1')
                                     
                                    select table_name, num_rows, blocks, empty_blocks from user_tables where table_name = 'HAKAN'
                                    /
                                    NOTE: - the duplicate / is intentional to insert two rows

                                    Foote seems to know his stuff and occasionallly has some hard-to-find things like block dumps. It's easy to see how the bitmap indexes are stored and he is sort of the 'myth buster' of things like using cardinality for bitmap index use determination, when is a table too small to index (woule believe not even a one block table?), and using separate tablespaces for tables and indexes.

                                    He uses pretty simple examples for his demos; a Tom Kyte approach for the internals.

                                    If Billy keeps hammerin' on me enough I'll eventually learn to run my own demos because I open my mouth and insert my size 13 feet into it! Hey - at least I don't bite down.
                                    1 2 Previous Next