Bitmap processing method

As the name implies, this method generates bitmaps that are used during access to the data space. The bitmap processing method is used to:

• Eliminate the random I/O that occurs on a data space when using an index in conjunction with the key position and/or index scan-key selection method.
• Allow multiple indexes to be used to access a particular table.

How the bitmap processing method works

In this method, the optimizer chooses one or more indexes to be used to aid in selecting rows from the data space. Temporary bitmaps are allocated (and initialized), one for each index. Each bitmap contains one bit for each row in the underlying data space. For each index, index scan-key positioning and index scan-key selection methods are used to apply selection criteria.

For each index entry selected, the bit associated with that row is set to '1' (i.e. turned on). The data space is not accessed. When the processing of the index is complete, the bitmap contains the information on which rows are to be selected from the underlying data space. This process is repeated for each index. If two or more indexes are used, the temporary bitmaps are logically ANDed and ORed together to obtain one resulting bitmap. Once the resulting bitmap is built, it is used to avoid mapping in rows from the data space unless they are selected by the query.

It is important to note that the indexes used to generate the bitmaps are not actually used to access the selected rows. For this reason, they are called tertiary indexes. Conversely, indexes used to access the final rows are called primary indexes. Primary indexes are used for ordering, grouping, joins, and for selection when no bitmap is used.

Where the method is used

The bitmap processing method is used in conjunction with primary access methods table scan, index scan-key selection, or index scan-key positioning. Bitmap processing, like parallel table prefetch and parallel table/index preload, does not actually select the rows from the data space; it assists the primary methods.

If the bitmap is used in conjunction with the table scan method, the bitmap initiates a skip-sequential processing. The table scan (and parallel table scan) uses the bitmap to "skip over" non-selected rows. This has several advantages:

• No CPU processing is used processing non-selected rows.
• I/O is minimized and the memory is not filled with the contents of the entire data space.

Example of a situation where the bitmap processing method is used in conjunction with the table scan method

The following example illustrates a query where the query optimizer chooses the bitmap processing method in conjunction with the table scan:

CREATE INDEX IX1 ON EMPLOYEE (WORKDEPT)
CREATE INDEX IX2 ON EMPLOYEE (SALARY)
 
DECLARE C1 CURSOR FOR
  SELECT * FROM EMPLOYEE
  WHERE WORKDEPT = 'E01' OR SALARY>50000
  OPTIMIZE FOR 99999 ROWS
 

OPNQRYF example:

OPNQRYF FILE((EMPLOYEE))
   QRYSLT('WORKDEPT *EQ ''E01'' *OR SALARY > 50000')

In this example, both indexes IX1 and IX2 are used. The database manager first generates a bitmap from the results of applying selection WORKDEPT = 'E01' against index IX1 (using index scan-key positioning). The database manager then generates a bitmap from the results of applying selection SALARY>50000 against index IX2 (again using index scan-key positioning).

Next, the database manager combines these two bitmaps into one bitmap using OR logic. Finally, a table scan is initiated. The table scan uses the bitmap to skip through the data space rows, retrieving only those selected by the bitmap.

This example also shows an additional capability provided with bitmap processing (use of an index for ANDed selection was already possible but bitmap processing now allows more than one index). When using bitmap processing, multiple index usage is possible with selections where OR is the major boolean operator.

The messages created by the PRTSQLINF command when used to describe this query would look like:

SQL4010  Table scan for table 1.
SQL4032  Index IX1 used for bitmap processing of table 1.
SQL4032  Index IX2 used for bitmap processing of table 1.
CPI4329  Arrival sequence access was used for file EMPLOYEE.
CPI4388  2 access path(s) used for bitmap processing of file EMPLOYEE.

Example of situation where bitmap processing is used in conjunction with the index scan-key positioning access method

If the bitmap is used in conjunction with either the index scan-key selection or index scan-key positioning method, it implies that the bitmap (generated from tertiary indexes) is being used to aid a primary index access. The following example illustrates a query where bitmap processing is used in conjunction with the index scan-key positioning for a primary index:

CREATE INDEX PIX ON EMPLOYEE (LASTNAME)
CREATE INDEX TIX1 ON EMPLOYEE (WORKDEPT)
CREATE INDEX TIX2 ON EMPLOYEE (SALARY)
 
DECLARE C1 CURSOR FOR
  SELECT * FROM EMPLOYEE
  WHERE WORKDEPT = 'E01' OR SALARY>50000
  ORDER BY LASTNAME

OPNQRYF example:

OPNQRYF FILE((EMPLOYEE))
   QRYSLT('WORKDEPT *EQ ''E01'' *OR SALARY > 50000')
   KEYFLD(LASTNAME)

In this example, indexes TIX1 and TIX2 are used in bitmap processing. The database manager first generates a bitmap from the results of applying selection WORKDEPT = 'E01' against index TIX1 (using index scan-key positioning). It then generates a bitmap from the results of applying selection SALARY>50000 against index TIX2 (again using index scan-key positioning).

The database manager then combines these two bitmaps into one bitmap using OR logic. An index scan-key selection method is initiated using (primary) index PIX. For each entry in index PIX, the bitmap is checked. If the entry is selected by the bitmap, then the data space row is retrieved and processed.

The messages created by the PRTSQLINF CL command, when used to describe this query, would look like:

SQL4008  Index PIX used for table 1.
SQL4032  Index TIX1 used for bitmap processing of table 1.
CPI4328  Access path of file PIX was used by query.
CPI4338  2 access path(s) used for bitmap processing of file EMPLOYEE.

Example of situation where bitmap processing is used in conjunction with join queries

Bitmap processing can be used for join queries, as well. Since bitmap processing is on a per table basis, each table of a join can independently use or not use bitmap processing

The following example illustrates a query where bitmap processing is used against the second table of a join query but not on the first table:

CREATE INDEX EPIX ON EMPLOYEE(EMPNO)
CREATE INDEX TIX1 ON EMPLOYEE(WORKDEPT)
CREATE INDEX TIX2 ON EMPLOYEE(SALARY)
DECLARE C1 CURSOR FOR
SELECT * FROM PROJECT, EMPLOYEE
WHERE RESEMP=EMPNO AND
(WORKDEPT='E01' OR SALARY>50000)
 

Using the OPNQRYF command:

OPNQRYF FILE((PROJECT) (EMPLOYEE)) FORMAT(RESULTFILE)
        JFLD((1/RESPEMP 2/EMPNO))
        QRYSLT('2/WORKDEPT=''E01'' *OR 2/SALARY>50000')
 

In this example, the optimizer decides that the join order is table PROJECT to table EMPLOYEE. Table scan is used on table PROJECT. For table EMPLOYEE, index EPIX is used to process the join (primary index). Indexes TIX1 and TIX2 are used in bitmap processing.

The database manager positions to the first row in table PROJECT. It then performs the join using index EPIX. Next, it generates a bitmap from the results of applying selection WORKDEPT='E01' against index TIX1 (using index scan-key positioning). It then generates a bitmap from the results of applying selection SALARY>50000 against index TIX2 (again using index scan-key positioning).

Next, the database manager combines these two bitmaps into one bitmap using OR logic. Finally, the entry that EPIX is currently positioned to is checked against the bitmap. The entry is either selected or rejected by the bitmap. If the entry is selected, the rows are retrieved from the underlying data space. Next, index EPIX is probed for the next join row. When an entry is found, it is compared against the bitmap and either selected or rejected. Note that the bitmap was generated only once (the first time it was needed) and is just reused after that.

The query optimizer debug messages put into the job log would look like:

CPI4327 File PROJECT processed in join position 1.
CPI4326 File EMPLOYEE processed in join position 2.
CPI4338 2 access path(s) used for bitmap processing of file EMPLOYEE.
 

Bitmap processing and composite key indexes

Bitmap processing alleviates some of the headache associated with having composite key indexes (multiple key columns in one index).

For example, given an SQL query:

DECLARE C1 CURSOR FOR
   SELECT * FROM EMPLOYEE
   WHERE WORKDEPT='D11' AND
   FIRSTNAME IN ('DAVID', 'BRUCE', 'WILLIAM')
 

Or the same query using the OPNQRYF command:

OPNQRYF FILE((EMPLOYEE))
  QRYSLT('WORKDEPT=''D11'' *AND
  FIRSTNME = %VALUES(''DAVID'' ''BRUCE'' ''WILLIAM'')')

An index with keys (WORKDEPT, FIRSTNAME) would be the best index to use to satisfy this query. However, two indexes, one with a key of WORKDEPT and the other with a key of FIRSTNME could be used in bitmap processing, with their resulting bitmaps ANDed together and table scan used to retrieve the result.

With the bitmap processing method, you can create several indexes, each with only one key column, and have the optimizer use them as general purpose indexes for many queries. You can avoid problems involved with trying to determine the best composite key indexes for all queries being performed against a table. Bitmap processing, in comparison to using a multiple key column index, allows more ease of use, but at some cost to performance. Keep in mind that you will always achieve the best performance by using composite key indexes.

Additional considerations for bitmap processing

Some additional points regarding bitmap processing:

• As long as the DB2 SMP feature is installed, you can use parallel processing whenever you use bitmap processing. in this case, the bitmap is built from the results of performing either parallel index scan-key positioning and/or parallel index scan-key selection on the tertiary index.
• Bitmaps are generated at the first row fetch (I/O). Therefore, the first row fetched may take longer to retrieve than subsequent rows.
• Bitmaps, by their nature, contain static selection. Once the bitmap is generated, it will not select any new or modified rows. Therefore, bitmap processing is used only when ALWCPYDTA(*OPTIMIZE) is specified.

  For example, suppose that an OPNQRYF statement specifying (QRYSLT('QUANTITY >5') is opened using bitmap processing and the first row is read. Through a separate database operation, all rows where QUANTITY is equal to 4 are updated so QUANTITY is equal to 10. Since the bitmap was already built (during the first row fetch from the OPNQRYF open identifier), these updated rows will not be retrieved on subsequent fetches through the OPNQRYF open identifier.

  The exception to this is if the query contains grouping or one or more aggregate functions (for example, SUM, COUNT, MIN, MAX), in which case static data is already being made.

• The query optimizer does not use bitmap processing for a query that is insert, update, or delete capable. For OPNQRYF, you must set the OPTION parameter to *INP and the SEQONLY parameter to *YES. There must not be any overrides to SEQONLY(*NO)).