Counting things at the speed of light with roaring bitmaps
summary
Counts faceting for a 100 million row table runs using pg_roaringbitmap bitmaps and PostgreSQL SQL, producing a 200 MB facets table of posting lists (some ~12 MB each) and answering facet intersections in about 80 ms after TOAST/materialization tuning. Implementation uses RB_BUILD_AGGREGATE, RB_AND_CARDINALITY, chunking by ~20 bits (~1M IDs per chunk) and a Delta table + periodic MERGE for updates; packaged as the pgfaceting extension on GitHub.
AI-written summary · about
chapters (15)
- 0:00Introduction to fast faceting
- 3:01Problem with naive faceting
- 6:31Speed of light memory access
- 9:49Bitmaps and inverted indexes
- 13:24Roaring bitmaps explained
- 18:24Postgres roaring bitmap extension
- 23:08Building faceting with roaring bitmaps
- 27:29TOAST performance issues
- 32:32Optimizing TOAST and updates
- 35:04Chunking for performance
- 37:38Delta tables for updates
- 38:46PG faceting extension demo
- 41:57Other uses for roaring bitmaps
- 43:23Graph algorithms with roaring bitmaps
- 44:27Q&A session
related talks
27mData indexing with RGB (Ruby, Graphs and Bitmaps)
31mMaking Data Dance
56mLightning Talks
26mData indexing with RGB (Ruby, Graphs and Bitmaps)
31mBiggish Data With Rails and Postgresql
21mAnalytics in Postgres –A decade in the making
27mBuilding a PostgreSQL data warehouse
34mAnalytics and AI with PostgreSQL - Mission Possible!