Bitmap Indexes in Go: Search Speed (2019)
1–10 of 40 posts
Re: Bitmap Indexes in Go: Search Speed (2019)
#2Bitmaps can also be used for computing funnels:
https://vikramoberoi.com/using-bitmaps-to-run-interactive-re...
Re: Bitmap Indexes in Go: Search Speed (2019)
#3Looks like Pilosa mentioned in the article is now called FeatureBase and all the new activity is happening at https://github.com/FeatureBaseDB/featurebase
Re: Bitmap Indexes in Go: Search Speed (2019)
#4Looks like Pilosa mentioned in the article is now called FeatureBase and all the new activity is happening at https://github.com/FeatureBaseDB/featurebase
Yes. Molecula, the company behind Pilosa, has rebranded itself to FeatureBase. It's offering both a managed cloud/serverless option and a downloadable Open Source build for implementing binary indexes. Both ARM and Intel versions are available (but not for Windows, yet). I just joined the team and am working on some interesting demos for machine learning applications.
While FeatureBase is great for doing analytics on massive data sets, it's also well suited for being used as a model's feature store, for both training and inference.
We have a Discord here, if anyone is interested: https://discord.com/invite/bSBYjDbUUb?utm_campaign=FeatureBa...
Re: Bitmap Indexes in Go: Search Speed (2019)
#5Very approachable introduction to this data structure.
The assembly implementation, though, reminded me of the stone soup story. Where a stranger is boiling a rock in a pot of water, and the townspeople intrigued by the idea of stone soup bring various ingredients to add to it and everyone is shocked that "stone soup" could taste so good.
The "Go" implementation ends up being pretty much all assembly by the end, in an article supposedly about a fast bitmap index implementation written in Go.
Re: Bitmap Indexes in Go: Search Speed (2019)
#6Very approachable introduction to this data structure. The assembly implementation, though, reminded me of the stone soup story. Where a stranger is boiling a rock in a pot of water, and the townspeople intrigued by the idea of stone soup bring various ingredients to add to it and everyone is shocked that "stone soup" could taste so good. The "Go" implementation ends up being pretty much all assembly by the end, in a…
Going off-topic, a typical Portuguese soup actually, worth a visit to a "Loja das Sopas" in a nearby shopping mall when in Portugal.
Re: Bitmap Indexes in Go: Search Speed (2019)
#7I'm not sure I follow what it is they're benchmarking (although I struggle reading text that has too many images so I may be confused as to what they're even doing).
I'd expect the bottleneck in a database index to be your disk or RAM access patterns. It seems very counterintuitive to see a real-world speed-up from SIMD if that is the case. The fact that they're seeing one in the benchmark would suggest maybe the benchmark isn't entirely capturing the right thing.
Re: Bitmap Indexes in Go: Search Speed (2019)
#8Bitmaps can also be used for computing funnels: https://vikramoberoi.com/using-bitmaps-to-run-interactive-re...
I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.
Re: Bitmap Indexes in Go: Search Speed (2019)
#9I'm not sure I follow what it is they're benchmarking (although I struggle reading text that has too many images so I may be confused as to what they're even doing). I'd expect the bottleneck in a database index to be your disk or RAM access patterns. It seems very counterintuitive to see a real-world speed-up from SIMD if that is the case. The fact that they're seeing one in the benchmark would suggest maybe the ben…
Generally speaking, the nice thing about bitmap indexes is that you're able to access the data in a very granular way. If you have a WHERE clause that's calling out specific values, you only access the data which is pertinent to those values within a column, you don't have to scan the whole column. This is simply due to the structure of a bitmap index where you have a separate bitmap for each value in the domain of a column.
Furthermore, access patterns for bitmaps tend to be very linear and cache/prefetch friendly.
I think it's very feasible that adding SIMD could result in a real-world speedup in an otherwise well-optimized in-memory system. I agree if you need to go to disk, that will likely dominate the overall performance of a single query, but it may still be overall more efficient which can still help in a multi-user situation.
Re: Bitmap Indexes in Go: Search Speed (2019)
#10I'm not sure I follow what it is they're benchmarking (although I struggle reading text that has too many images so I may be confused as to what they're even doing). I'd expect the bottleneck in a database index to be your disk or RAM access patterns. It seems very counterintuitive to see a real-world speed-up from SIMD if that is the case. The fact that they're seeing one in the benchmark would suggest maybe the ben…
Disk and Memory can both be bottle necks, however with compression on Roaring bitmaps you typically keep your entire index in memory and compute in a compressed state, avoiding slow disk. You do in fact become CPU bound on queries, even intelligent multi-threading, and CPU efficiency comes into play (especially so as a bitmap begins expanding across several shards).