# Presentation: 421482

## Efficient Bitmap Indexes for Very Large Datasets

**John Wu**
**Ekow Otoo**
**Arie Shoshani**
**Lawrence Berkeley National Laboratory**

## Outline

**Introduction**
**Example application: high-energy physics data**
**Task: range queries on high-dimensional data**
**Approach: bitmap index**
**To make it work: **_**compression**_**, encoding, binning**
**New compression scheme**
**Best known scheme (BBC): CPU bound**
**Improve CPU efficiency: 10 X**
**Compressed bitmap index**
**Index size smaller than b-tree**
**Answer queries faster than b-tree, ...**
**Applying bitmaps for a feature tracking problem**

## Example I: High-energy Physics

| Selected attributes of STAR summary data (tags).
Actual size (January 2002): 20 million objects, 502 attributes |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| OID | Run | Event | NLb | tpc | Tracks | Particles | Vertex | qxb[2] | Energy |
| 0 | 1239029 | 2635 | 1341 | 909 | 1228 | 266 | .56 | -26.40 | 48 |
| 1 | 1239029 | 2636 | 1470 | 1243 | 1415 | 317 | .46 | -29.08 | 53 |
| 2 | 1239029 | 2637 | 1663 | 1285 | 1533 | 281 | .53 | -6.754 | 8 |

- Typical data processing steps:
- Collect raw data: collision events, ... (done once)
- Generate summary data (done once): 10-100 attributes per event
- Access data according to summary attributes (performed by many scientists):
**20001015<=Run & 200<Energy<300 ...**

## Range Queries on High-dimensional Data

**Typical query: partial range query**
**20001015<=Run & 200<Energy<300 ...**
**Characteristics of data**
**Large: millions or billions of records**
**High-dimensional: hundreds of attributes per object**
**Appends in batches**
**Most attributes are not categorical (integer, floating-point values)**
**Known solutions**
**Sequential scan**
**R-tree etc. are usually slower than sequential scan**
**Bitmap index is faster in some cases**

## Basic Bitmap Index

**Bitmap index is efficient for processing range queries on read-only data (P. O’Neil, 1987).**

## Features of Bitmap Index

**Main operations are bitwise logical operations and they are fast**
**Index sizes are small for categorical attributes with low cardinality**
**Each individual bitmap is small and frequently used ones can be cached in memory**
**Scientific datasets have mostly non-categorical attributes**
**Index size may be large**
**Query processing may be slow**

## Effective Bitmap Index

**To make bitmap index effective for scientific datasets:**
**Binning: reduce the number of bitmaps**
**Say 0 <= NLb < 4000, we can use 20 equal size bins [0,200)[200,400)[400,600)**
**Encoding: reduce the number of bitmaps or reduce the number of operations**
**Basic: equality encoding: generates on bitmap for each bin (shown above)**
**Other: range encoding, interval encoding, ...**
_**Compression**_**: reduce the size of each bitmap, may also speedup the logical operations**
**Find an efficient compression scheme to reduce query processing time**
**This talk only addresses the issue of compression**

## Efficient Compression Schemes

**Word-aligned Hybrid Code**

## Efficient Compression Schemes

**Best known compression scheme for bitmap indexes --- byte-aligned bitmap code (BBC)**
**Uses run-length encoding**
**Encode/decode bitmaps 8 bits (one byte) at a time**
**Compresses nearly as well as LZ77 (gzip)**
**Bitwise logical operations can be performed on compressed bitmaps directly**
**Operations are usually faster compared to other compression schemes, e.g., ExpGol, ...**
**Even faster than operating on uncompressed bitmaps in some cases**
**Used in ORACLE**

## Operations With BBC Is CPU Bound

**Operations With BBC Is CPU Bound**

- Bitwise logical operations on BBC compressed bitmaps are CPU bound
- Reduce CPU time

**CPU time is about 80% of total time on a system with 20 MB/s disk suite**
- Two independent implementations of BBC show similar behavior
- Operation measured: read two files from disk and perform one logical operation in memory

## Word-Aligned Hybrid Code

**Word-aligned hydride code (WAH)**
**Uses run-length encoding for long sequences of identical bits**
**Encode / decode bitmaps in word size chunks**
**Designed for minimal decoding to gain speed**

## Word-Aligned Hybrid Code

- 10000000000000000000011100000000000000000000000000000...................00000000000000000000000000000001111111111111111111111111

- 1023 bits

- Groups bits into 33 31-bit groups

- Encode each group using one word

- 31 bits

- 31*31 bits

- 31 bits

- 31 bits

- 31 bits

- ...

- 31 bits

- Merge neighboring groups with identical bits

## Information About the Test Setup

**Hardware and system**
**Sun enterprise 450 (Ultrasparc II 400MHz)**
**VARITAS volume manager (stripped disk) – measured IO speed 20 MB/s**
**Real application data from STAR**
**About 2.2 million records, 500 attributes**
**Synthetic data**
**100 million records, 10 attributes**
**Terms**
**Compression ratio: ratio of compressed bitmaps size and uncompressed bitmaps size **
**Time reported are wall clock time in seconds**

## Fraction of Time Spent in CPU

- On a 2 MB/s disk system

- On a 20 MB/s disk system

- Compared to two implementations of BBC,
- WAH spends smaller fraction of time in CPU

## Logical Operation Time

- Synthetic data
- 100 million records
**WAH is 2-20 times faster than BBC**

## Logical Operation Time

- STAR data
- 2.2 million records
**WAH is 2-60 times faster than BBC**

**Notes:**
Logical operation (on in-core bit vectors) times only

## Trade-off of Compression Schemes

## Performance of the Full Queries Using the Basic Bitmap Index

- Bitmap index setup:
- One bitmap per value (no bins)
- Equality encoding
- What is being measured
- Time – answering range queries (not individual logical operation):
- high cardinality attributes from STAR

## WAH index scales linearly with data size

**WAH index scales linearly ****with data size**

- STAR: 2.2 mil
- Combustion: 25
- Synthetic: 100

**Query processing time is proportional to index size**
** ******** ****1 sec ******** 100 MB**

**Range Queries over different datasets**

## Multi-attribute Range QueriesHigh Cardinality Attributes

- 2 attributes per query

- 5 attributes per query

**WAH compressed indexes are 10X faster than ORACLE, 5X faster than our BBC**
- P scan is scanning vertically projection of data table – the simplest option for processing partial range queries on high-dimensional data
- Queries on 12 most queried attributes, average cardinality 222,000

## Summary of Tests on STAR Data

|  |  |  | Exact answers |  | Approximate answers |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Indexing Method | Size
(X data) | Time (sec) | relative
to p scan | Time (sec) | relative
to p scan |
| Native vertical partition
(WAH) | P Scan | 0 | 0.57 | 1 |  |  |
|  | 20 bins | 0.18 | 0.11 | 5 | 0.01 | 60 |
|  | 50 bins | 0.43 | 0.07 | 8 | 0.01 | 60 |
|  | 100 bins | 0.90 | 0.05 | 11 | 0.01 | 60 |
|  | No bins | 1.65 | 0.05 | 11 |  |  |

- WAH
- vs.
- BBC

| ORACLE | Scan | 0 | 6.5 | 0.09 |
| --- | --- | --- | --- | --- |
|  | B-tree | 3.6 | 0.95 | 0.6 |
|  | Bitmap (no bins) | 0.98 | 0.66 | 0.86 |

**Our bitmap index can be 100 X faster than ORACLE:**
**10 X due to compression scheme, 10 X due to binning**

## Using Bitmaps for Feature Tracking

**Adopting Compressed Bitmaps to Operations Outside of the Bitmap Index**

## Example II: Combustion

**Example II: Combustion**

**Direct numerical simulation of auto-ignition process (solution of complex partial differential equations – data computed once but never modified)**
**A simple model has 12 variables per cell, a realistic model may have hundreds**
**Number of grid points: 2D 600 X 600 >>> 3D 1000 X 1000 X 1000**
**Time steps: 100 >>> 1000s**
**Data size: 1 GB >>> 10 TB**
**Task: ****identify features and track them across time steps**

## Tasks

**Cell identification**
**Identify cells with values satisfying specified conditions**
**Typically a partial range query, like, “600<temp<700 & HO****2****>10****-7****”**
**Region growing (feature identification)**
**Connect neighboring cells into connected regions**
**Feature tracking**
**Identify common cells in connected regions from different time steps**

## Basic Approach

**Cell identification**
**Scan data and perform comparisons**
**Solution is represented as a list of cell IDs**
**Region growing**
**For each cell in the above list, search all its neighbors**
**Each region is a list of cell IDs**
**Feature tracking**
**Sort cell IDs of each region and match cell IDs to identify common cells**
**Use bounding boxes to reduce unnecessary operations**

## Our Approach

**Cell identification**
**Vertically partition the data**
**Use bitmap index to speedup searches**
**Solutions are represented as compressed bitmaps**
**Region growing**
**Convert the compressed bitmaps into line segments**
**Connect neighboring line segments into regions**
**Convert each region into a compressed bitmap**
**Feature tracking**
**Use bitwise AND to identify common cells**
**Use bounding boxes to reduce unnecessary operations**

## Preliminary Performance Data

| Cell identification | Horizontal partition
75 seconds | Vertical partition
5 seconds | Bitmap index
0.1 seconds |
| --- | --- | --- | --- |
| Region growing | Point based algorithm
8 seconds |  | Line based algorithm
1.7 seconds |
| Feature tracking | Comparing cell Ids
10 seconds |  | Bitmap operations
0.2 seconds |
| Total time (sec) | 93 | 23 | 2.0 |

- 69 time steps, 600 X 600 grid, condition HO2>10-7

**Compressed bitmaps can be efficiently used for feature tracking**

## Summary

**The size of WAH compressed bitmap index is modest even in the worse case**
**For most high cardinality attributes with N records, the index size is about 2N words. Never more than 4N words**
**The WAH compressed index is efficient on attributes of any cardinality**
**On range queries, it is faster than uncompressed bitmap index (3X), BBC compressed index (2~20X), B+-tree index (20~200X), and scanning vertically partitioned table (4~50X)**
**Compressed bitmaps can also be efficiently used for feature tracking**

## Sizes of Compressed Bitmap Indexes

**10****8**** records**
- Test attribute: 1,2,3,...,1,2,3,...
- (worst case in terms of index size)

- B+-tree size
- (observed):
- 3~4 x 108 words

**WAH compressed index is not larger than B+-tree**

## Summary of Tests on STAR Data (I)

|  |  |  |  |  | Bitmap index |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  |  |  | B+-tree | P scan | Oracle | BBC | WAH |
| Low
cardinality
case |  | Size (MB) | 370 | 0 | 7 | 4 | 7 |
|  | Query processing
(seconds) | 1-attribute | 0.90 | 0.51 | 0.005 | 0.015 | 0.004 |
|  |  | 2-attribute | 2.10 | 0.56 | 0.024 | 0.026 | 0.006 |
|  |  | 5-attribute | 2.14 | 0.67 | 0.043 | 0.083 | 0.017 |
| High
cardinality
case |  | Size (MB) | 408 | 0 | 111 | 118 | 186 |
|  | Query processing
(seconds) | 1-attribute | 0.95 | 0.51 | 0.01 | 0.03 | 0.05 |
|  |  | 2-attribute | 2.15 | 0.56 | 0.39 | 0.17 | 0.04 |
|  |  | 5-attribute | 2.23 | 0.67 | 2.42 | 0.76 | 0.17 |

- Compressed bitmap index is more efficient for range queries than B+-tree or no index (p scan)
- A WAH compressed index uses more space than a BBC compressed index, but is more efficient

## Multi-attribute Range QueriesLow Cardinality Attributes

- 2 attributes per query

- 5 attributes per query

**WAH compressed indexes are faster than BBC compressed indexes (3X) and uncompressed indexes (3X)**
- Query box is the relative volume of the box formed by the query condition
- 12 lowest cardinality attributes of star, average attribute cardinality 26

## Total Effect of Compression and Encoding Schemes

**Bottom line on queries**
**Compression scheme determines efficiency of logical operations**
**Encoding scheme determines number of operations**
**Range & interval – only one logical operation over 2 bitmaps**
**Equality – many operations depending on number of bins**
**But, space may be a consideration**
**What is the trade-off?**

## Interval Encoding Is Better Overall(WAH Compression)

**Points on the **
**graphs represent:**
**10, 20, 30, 50, 100**
**Bins.**

**Average time for random range queries**

**Notes:**
Compressed Interval scheme uses 40% space compared to the uncompressed (U I)
It runs at about the same space given the same number of bins
If using the same amount of space, the compressed one is faster because there are less events to be scanned in the final filtering step

## Storing Bitmaps As Files Is Efficient

**BMI – store bitmaps in Objectivity**
**IBIS – store bitmaps in files**

**IBIS answers queries about 4 times faster than BMI using WAH**
**BMI with WAH is up to ten times faster than BMI with BBC**

- Joint work with Kurt Stockinger (CERN)