Repository navigation
Search query slow with filter #3775
Description
If the following are true then a search query on a QueryableIndex can be slower than expected.
- There is a filter
- The search dimension is high cardinality
- Many values of the search dimension match the query
This is because for QueryableIndex, the search query uses an index-based algorithm that does a bitmap intersection op for every value of the search dimension that matches the query before applying the filter. This can be more expensive than the cursor-based algorithm that applies the filter first, especially if the filter is very selective or if the search dimension is high cardinality.
Ideally the search query should use some heuristics to choose between the index-only vs. cursor-based algorithms, or at least provide a context flag to let you choose which one.
See also https://groups.google.com/d/topic/druid-user/gjhh3rfdrUw/discussion.
Activity
jihoonson commentedon Dec 15, 2016
Sounds interesting! I'm working on it.
b-slim commentedon Dec 15, 2016
@gianm not sure why we need some heuristics, i think if the query contains a filter we should apply the filters first.
gianm commentedon Dec 15, 2016
We always use the filter bitmap, the only question is do we intersect it with the bitmaps in the indexes of the search dimension (index-based algorithm), or do we use it to scan through the rows of the search dimension (cursor-based algorithm). Which one is faster would depend on the number of rows that match the filter and on the cardinality of the search dimensions.
stale commentedon Jun 21, 2019
This issue has been marked as stale due to 280 days of inactivity. It will be closed in 2 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.
stale commentedon Jul 5, 2019
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.