Roaringbitmap In Postgres
RoaringBitmap is a memory efficient, high performance compressed bitmap data structure. It is widely used in numerous big data and analytics softwares.
Ants Aasma discusses how RoaringBitmap was used to solve a very practical problem.
Ants Aasma: Counting things at the speed of light with roaring bitmaps (PGConf.EU 2023)
PostgreSQL Europe
Jan 9, 2024
Use-Case:
- Search through 100 million documents
- Need accurate results
- No false positives
- Response time to be less than 2 seconds 😄
| Solution | Time taken |
|---|---|
| Naive implementation - SQL query | ~ 32 seconds |
| RoaringBitmap based implementation :rocket: | < 1 second ! |
References
- pg_roaringbitmap: Chen Huajun’s extension providing RoaringBitmap in Postgres
- pgfaceting: PostgreSQL extension to quickly calculate facet counts using pg_roaringbitmap
- RoaringBitmap: Prof. Daniel Lemire’s original implementation of RoaringBitmap
- Ants Aasma