Repository navigation
Bloom filters for dimensions and dimension filters #4494
Description
This suggestion is to have a bloom filter for the dimension values so a missing dimension value doesn't even need to scan through the dimension values to determine there is a miss.
Such a filter would be checked whenever there is a filter on a dimension value applied. This will probably not work for extraction dimensions.
Activity
[-]Bloom filters for dimensions[/-][+]Bloom filters for dimensions and dimension filters[/+]cheddar commentedon Jul 20, 2017
It's likely important to verify how much performance gain this gives. From what we've looked at, the lookup in the
GenericIndexedis actually pretty fast, so it would be interesting to know how much time is actually saved by this.Also, for our own purposes, when we've looked at the queries that will sometimes match zero rows on segments, it seems like it might be more important to "fail fast" and not process subsequent filters when one of the filters returns an always-false response.
gianm commentedon Jul 20, 2017
Is that the same thing as #3676?
drcrallen commentedon Jul 21, 2017
That could make a lot of sense: would it look something like combining operations for bitmaps passing in getters or factories so they don't have to make them if the early ones would cause the later to never need to materialize?
cheddar commentedon Jul 21, 2017
@gianm awesome, yes, hadn't realized that was done.
In that case, then my only real comment here is that we should verify the performance gain from using the bloomfilter, especially on columns that have dictionaries. Other systems get nice speed gains because the predicate check is a lot more expensive. In our case, it will save a lookup in a dictionary which might be expensive, but also might not be any more expensive than the seeks we expect to do for each of the bloom filter hash functions. Anyway, bloomfilters might be a win and also might not. For columns without dictionaries, they would definitely be a win though.
github-actions commentedon Jun 2, 2023
This issue has been marked as stale due to 280 days of inactivity.
It will be closed in 4 weeks if no further activity occurs. If this issue is still
relevant, please simply write any comment. Even if closed, you can still revive the
issue at any time or discuss it on the dev@druid.apache.org list.
Thank you for your contributions.
github-actions commentedon Jun 30, 2023
This issue has been closed due to lack of activity. If you think that
is incorrect, or the issue requires additional review, you can revive the issue at
any time.