GoSuda

Vibrant Bitmap

By snowmerak views ...

What Is a Bitmap?

The bitmap discussed here is a type of index. If you came in thinking about graphics, you may go back.

Basic Concept

A bitmap is a form of indexing technique in databases. It represents the values of a particular column as an element or form of a bit array or vector, where each bit indicates whether a specific value of that column exists. Therefore, the most basic form assigns a bit index to each row and expresses the presence or absence with 0 and 1.

For example, suppose there is a table with a sex column. Suppose this table has 5 rows, and the values of the sex column are as follows:

  1. Male
  2. Female
  3. Male
  4. Female
  5. Other

In this case, the bitmap index for the sex column can be expressed as follows:

  • Male: 10100
  • Female: 01010
  • Other: 00001

So Where Is It Actually Used?

Many people probably think that it is not merely for representing this. To make proper use of a bitmap index, let us consider the following case.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Suppose this table has 1,000,000 rows. Then suppose we execute the following query.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

This query finds rows where both the active and sex columns are TRUE. Then, the fastest way to find rows satisfying the condition that both columns are TRUE would be to use the bitwise AND operation.

  • Suppose the bitmap index for the active column, a 1,000,000-bit array 1100110011..., is pre-indexed,
  • and the bitmap index for the sex column, a 1,000,000-bit array 1010101010..., is pre-indexed.

Then, by performing a bitwise AND operation on the two bitmap indexes, we can quickly find the rows where both columns are TRUE. Because it is a simple bit operation, the result can be obtained much faster than with other index scans.

Trade-offs

Bitmap indexes can be very efficient, but they have several trade-offs. There are many other drawbacks, but for now we will only point out one.

Namely, bitmap indexes are better suited to low cardinality (that is, columns with a small number of possible values). Using a bitmap index on a high-cardinality column can make the bitmap very large.

If a bitmap index is used on a high-cardinality column, a separate bitmap must be created for each distinct value, so it may require a lot of storage space. For example, if a column has 1,000,000 distinct values, 1,000,000 bitmaps must be created, which can be very inefficient.

So What Do We Do

To replace the bitmaps arising from high cardinality, we can use something called Roaring Bitmap. Roaring Bitmap has several characteristics, but its greatest underlying philosophy and feature is dynamically selecting the most suitable storage method according to data density to maximize both compression ratio and computation speed.

Basic Concept of Roaring Bitmap

Two-Level Indexing

Roaring Bitmap goes through the following two steps to store a single integer. Although it is called two-level indexing, you can simply think of it as a two-dimensional array.

  • Extracting the upper 16 bits: The upper 16 bits of the integer are extracted and used as an index. Among a two-dimensional array with a total length of 65536, this becomes the index of the outer array. This array stores the address of the container described later.
  • Extracting the lower 16 bits: The lower 16 bits of the integer are extracted and used as the position within the container.

Container

This container corresponds to the inner array of the two-dimensional array, as analogized just now. However, unlike the outer array for the upper 16 bits, the internal structure of this container varies depending on how much data it holds. Roaring Bitmap supports the following three types of containers.

  • Array Container: This container is used when the amount of data stored inside is small. Specifically, it is used when storing 4096 or fewer elements. This container is implemented simply as a sorted integer array. Elements can be found by performing a binary search.
  • Bitmap Container: This container is used when the amount of data stored inside is large. Specifically, it is used when storing more than 4096 elements. This container is implemented as a bitmap of 65536 bits (8192 bytes). Each bit indicates whether the integer at that position exists.
  • Run Container: This container is used to store continuous integer ranges. For example, it is efficient for storing consecutive integers such as 1, 2, 3, 4, 5. This container is implemented as a list of (start value, length) pairs. What if everything is present? It simply means that all values from beginning to end exist, so only (0, 65536) needs to be stored.

This approach allows Roaring Bitmap to use memory very efficiently and provide optimal performance across various data densities.

Features of Roaring Bitmap

Basic Features

Roaring Bitmap provides the following basic features.

  • Insertion: Adds a new integer to the bitmap. During this process, an appropriate container can be selected, or containers can be converted as needed.
  • Deletion: Removes an existing integer from the bitmap. Even in this process, appropriate handling is performed according to the state of the container.
  • Search: Checks whether a specific integer exists in the bitmap. This process is performed very quickly.

Set Operations

Roaring Bitmap also supports the following set operations.

  • Union: Creates a new bitmap containing all elements of both bitmaps.
  • Intersection: Creates a new bitmap containing only the elements that exist in both bitmaps.
  • Symmetric Difference: Creates a new bitmap containing elements that exist in only one of the two bitmaps.

These operations are optimized according to the container types of the bitmaps and are performed very quickly.

In the Go Language

In the Go language, Roaring Bitmap can be easily used through the github.com/RoaringBitmap/roaring package. This package provides all the features of Roaring Bitmap and is optimized to suit the characteristics of Go.

Installation

1go get github.com/RoaringBitmap/roaring/v2

Usage Example

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Initialize with 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialize with 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Add 5
14	b2.Add(10) // Add 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmap operations modify the original, so use a clone
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Other major features not shown in the example above include:

  • Contains(x uint32) bool: Checks whether a specific value exists in the bitmap
  • GetCardinality() uint64: Returns the number of elements contained in the bitmap
  • Rank(x uint32) uint64: Returns the number of elements less than or equal to a specific value
  • ToBytes() ([]byte, error): Serializes the bitmap into a byte slice
  • FromBytes(data []byte) error: Restores the bitmap from a byte slice
  • Clone() *Bitmap: Creates a copy of the bitmap
  • Clear(): Resets the bitmap
  • NextValue(x uint32) int64: Returns the next element greater than or equal to x
  • PreviousValue(x uint32) int64: Returns the previous element less than or equal to x
  • Maximum() uint32: Returns the largest element in the bitmap
  • Minimum() uint32: Returns the smallest element in the bitmap

These are the available features. For more details, please refer to the official documentation.

For reference, the roaring package also includes a package that supports uint64 in addition to uint32. It provides nearly the same interface, so it can be used as a direct replacement.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Initialize with 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialize with 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Add 5
14	b2.Add(10) // Add 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmap operations modify the original, so use a clone
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusion

Roaring Bitmap is a powerful tool for efficiently storing and manipulating sets of integers with high cardinality. By using the github.com/RoaringBitmap/roaring package in Go, all the features of Roaring Bitmap can be easily utilized. Through its various container types and optimized operations, this package maximizes memory usage and performance. Roaring Bitmap can be applied to efficient data processing in many fields, including database indexing, log analysis, and statistical computation.

Roaring Bitmap is especially high-performing on large-scale datasets and can be useful in a wide range of applications. Combined with the concise and efficient syntax of Go, Roaring Bitmap offers developers a powerful tool. Going forward, along with the development of Roaring Bitmap, more features and optimizations are expected.

Why did I do this? I did it for indexing by each tag and fast union operations in a time series database.