"For query-time, we found that reading an extra bit for every event adds around 10ns to the reading of data. This is close to a 2% increase in the query time be

"For query-time, we found that reading an extra bit for every event adds around 10ns to the reading of data. This is close to a 2% increase in the query time because of the additional column." This seems somewhat more expensive than I would've expected. Given your estimates of duplicate probability, the bitset should compress to essentially nothing, so IO is probably not the issue unless you're not compressing it. Are you doing a virtual function call or something here?