Roaring Bitmaps : Reducing Storage by 40X and query time by 89X

ยท

2 min read

Roaring Bitmaps : Reducing Storage by 40X and query time by 89X
Play this article

Problem Statement

There are 1 million Restaurants and 15 type of dishes, each restaurant can either be serviceable and available for dineout

Find restaurant IDs that are:

  • Serving pizza

  • Active

  • Offering dine-out

Restaurant Ids can range from 1 to 1 Billion

Approaches

  1. MySQL: Use normalized tables and SQL queries with joins.

  2. Redis Bitmaps: Utilize bitmaps for attributes and apply bitwise operations.

  3. Roaring Bitmaps: Similar to Redis but with compressed bitmaps.


MySql

Inserting 1 Million Restaurants where restaurant_id ranges from 1 to 1 Billion, to mimic the scenario where Data is in a sparse format

Let's first Insert a Million Restaurant records and around 8-9 Million Res. to Dish mappings

Querying the Data

SELECT r.restaurant_id
FROM restaurants r
JOIN dishes d ON r.restaurant_id = d.restaurant_id
WHERE d.dish_id = 7  -- Assuming 7 is the ID for pizza
AND r.status = TRUE
AND r.dine_out = TRUE;

Result :

Size of tables :

Here the query time is 610 ms

so storage of tables ~189 MB


Redis

Let's create 4 Redis Bitmaps :
- active_bitmap
- dineout_bitmap
- dish_1
- dish_7

and Set Random 1 million bits here

Querying

import redis
import time

# Connect to Redis
r = redis.Redis(host='localhost', port=6379, db=0)

# Record the start time
start_time = time.time()

# Execute the BITOP command
r.bitop('AND', 'result_bitmap', 'dish_7', 'active_bitmap', 'dineout_bitmap')

# Record the end time
end_time = time.time()

# Calculate and print the execution time
execution_time = end_time - start_time
print(f"The BITOP command took {execution_time} seconds to execute.")

Here the query time is 152ms

Single Redis Bitmap is 124MB

so storage of 3 Bitmaps ~372MB and 17 Bitmaps ~2.1GB


Roaring Bitmaps

Here the query time is just 7 ms

Single Roaring Bitmap is 0.35 Mb

so storage of 3 Bitmaps ~1.05 MB and 17 Bitmaps ~5.9 MB


Final Results

OperationMySqlRedis BitmapRoaring Bitmaps
Size189 MB124.98 MB -> Single Bitmap0.36 MB -> Single Bitmap
Query Time621 ms152 ms7 ms


Family Guy GIF - Family Guy Stewie - Discover & Share GIFs

ย