3 ms·
I'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 do
by marginalia_nu 4y ago
I'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.
- jaffee 4y agoGenerally 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.
- JustG 4y agoDisk 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).
- quadrature 4y agoThey're benchmarking the bitmap operations like AND,OR etc. These operations benefit a lot from vectorization.