Bitmap Inverted Index in Apache Pinot

In modern data processing systems, fast query performance is crucial, especially when handling large datasets. One of the key ways to achieve fast filtering and retrieval of data is by using indexes. Apache Pinot, a distributed columnar store designed for real-time analytics, uses several types of indexes to enhance query speed. One of the most effective types of indexes is the Bitmap Inverted Index.

 

What is a Bitmap Inverted Index?

A Bitmap Inverted Index is an efficient data structure used to index a column with low cardinality. It stores a bitmap (or list of document IDs) for each unique value in a column. Instead of storing a separate record for each row, a bitmap or list of row IDs is used to identify which rows contain the specific value. This enables extremely fast lookups when filtering data.

 

Unlike traditional row-based indexes, where each index entry maps to specific values, a bitmap index maps each unique value to a list of documents (rows) where the value occurs.

 

How Does Bitmap Inverted Index Work?

Let's consider a simple dataset of documents with a Category and Price column.

 

Document ID	Category	Price
d1	Electronics	1000
d2	Furniture	700
d3	Electronics	1200
d4	Clothing	500

 

Now, the Bitmap Inverted Index for the Category and Price columns would look like this:

 

Category Column Index:

Category	Document IDs
Electronics	d1, d3
Furniture	d2
Clothing	d4

 

Price Column Index:

Price	Document IDs
1000	d1
700	d2
1200	d3
500	d4

 

How Queries Work with Bitmap Inverted Index?

When a query is executed, Apache Pinot can quickly access the Bitmap Inverted Index to filter documents.

 

For example:

 

Query 1: Find documents with Category = 'Electronics'

SELECT * FROM Documents WHERE Category = 'Electronics';

How Pinot Retrieves Data?

·      Looks up the Category = 'Electronics' entry in the index, which maps to d1, d3.

·      Retrieves documents d1 and d3 directly.

 

Query 2: Find documents with Price = 700

SELECT * FROM Documents WHERE Price = 700;

How Pinot Retrieves Data?

·      Looks up the Price = 700 entry in the index, which maps to d2.

·      Retrieves document d2 directly.

 

Advantages of Bitmap Inverted Index

·      Efficient for Low Cardinality Columns: Bitmap indexes are particularly useful when columns contain a limited number of unique values (such as Category, Price, etc.).

·      Fast Filtering: Bitmap indexes allow for quick filtering by directly referencing document IDs where the value exists.

·      Space Efficient: Instead of storing values repeatedly, the index stores only the document IDs where the value appears. This leads to smaller storage requirements.

·      Multi-condition Queries: Bitmap indexes can easily combine results from multiple conditions (using logical operations like AND, OR), making them excellent for complex filtering.

 

When to Use Bitmap Inverted Index?

·      Low Cardinality Columns: When a column has a small number of unique values (e.g., Category, Gender, Region), Bitmap Inverted Index can be highly efficient.

·      Frequent Filters: If certain columns are frequently used for filtering in queries, such as in analytics dashboards, using a Bitmap Inverted Index will greatly improve performance.

·      Real-time Analytics: Bitmap Inverted Indexes are ideal for real-time analytics systems where quick response times are essential, especially for filtering large volumes of data.

 

 

In summary, Bitmap Inverted Indexes in Apache Pinot offer a powerful way to optimize query performance, especially for columns with low cardinality. By mapping unique values to document IDs, Bitmap Inverted Indexes allow fast, space-efficient filtering that can greatly enhance the performance of real-time analytical queries.

 

 

 

Previous                                                    Next                                                    Home