Home

Getting Started

Utilities

Indexing

Omnidex

Development

Tutorials

Quick Links

 

OMNIDEX Indexing

Indexing Options

 

Well-Behaved IDs

Comparison

 

Indexing Options

ASK Indexes

MDK Indexes

Composite Indexes

Bitmap Indexes

Excluded Words

Translation Tables

Special Characters

 

Bitmap Indexes

Bitmap indexing is an indexing option which stores index pointers as a bitmap rather than a B-tree, providing efficient indexing for "low cardinality" data (small numbers of unique values).

Bitmap indexes are used on low cardinality data of less than 30 unique values with well behaved Omnidex IDs. Ideal for Data Warehouse applications that do not need real time indexing.

The following example shows a table with "well-behaved" IDs. One bit is assigned to each ID in the table. The bitmap index is installed on the state field.

State

ID

CO

1

CA

2

CO

3

 

ID

Bitmap Index

1

1

2

0

3

1


The next example is "ill-behaved" because the maximum value of the IDs (3,000,000) greatly exceeds the row count of the table. A bitmap index will create a bit for every possible value between 1 and the maximum value of the IDs in the table. In this example, there are 3,000,000 bits in the index for 3 records.

State

ID

CO

1,000,000

CA

2,000,000

CO

3,000,000

 

ID

Bitmap Index

1

0

2

0

3

0

4- 999,999

0

1,000,000

1

1,000,001 -
2,999,999

0

3,000,000

1

 

 

 

Well-Behaved IDs

A bitmap index will be created for each unique value in the column installed with the ;BM option, and each bitmap index will contain a bit for each row in the table. Therefore, the table must have a well-behaved rowid to efficiently utilize bitmap indexing.

A well-behaved id must:

  • be a 32-bit integer.
  • be sequentially ascending from 1.
  • have a maximum value within 20% of the table's row count. This percentage decreases as the cardinality increases.
Databases with well-behaved rowids
  • Flat files, RMS fixed length sequential files, and RMS relative files all have well-behaved rowids because the TRR option is REQUIRED.
  • TurboImage/XL children have well-behaved rowids.
  • Any database that is using a Redefined Rowid, where the redefined rowid is mostly sequentially ascending from 1, has well-behaved rowids.
Databases with ill-behaved rowids
  • Oracle uses a 13-byte rowid which must be mapped into a $RECNO using a TIDMAP. Oracle 8i uses 16-byte rowids.
  • Informix uses a 4-byte rowid but is not sequentially ascending. Rowids may also be duplicated.
  • C-ISAM uses a 4-byte rowid but is not sequentially ascending.
  • ODBC standardized interface does not support rowids. This includes Microsoft SQL Server.
  • RMS Index Files do not have well-behaved rowids.

 

Well-Behaved vs Ill-Behaved IDs

The following comparison demonstrates bitmap indexing for well-behaved ids versus ill-behaved ids.

The first example is "well-behaved" because the ids are sequentially ascending from one.

Well-behaved ids
Bitmap Index for "CA"
Bitmap Index for "CO"

Data

ID

ID

Index

ID

Index

CA

2

1

0

1

1

CO

1

2

1

2

0

CO

3

3

0

3

1

Ill-Behaved

The next example is "ill-behaved" because the maximum value of the IDs (3,000,000) greatly exceeds the row count of the table. A bitmap index will create a bit for every possible value between 1 and the maximum value of the IDs in the table. In this example, there are 3,000,000 bits in the index for 3 records.

Ill-behaved ids
Bitmap Index for "CA"
Bitmap Index for "CO"

Data

ID

ID

Index

ID

Index

CA

2,000,000

1

0

1

1

CO

1,000,000

2

0

2

0

CO

3,000,000

3

0

3

1

 

 

 

 

4
...
1,999,999

0

4
...
999,999

0

 

 

2,000,000

1

1,000,000

1

 

 

 

 

2,000,001
...
3,000,000

0

1,000,001
...
2,999,999

0

 

 

 

 

3,000,000

1

 

Top