Use a bit set to count long-tail of singleton FacetLabels? [LUCENE-10080]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
I was talking about this with @rmuir about #11008, and he had a neat idea for more efficient facet counting.
Today we accumulate counts directly in an HPPC native int/int map, or a non-sparse `int[]` (if enough hits match the query).
But it is likely that many of these facet counts are singletons (occur only once in each query). To be more space efficient, we could wrap a bit set around the map or `int[]`. The first time we see an ordinal, we set its bit. The second and subsequent times, we increment the count as we do today.
If we use a non-sparse bitset (e.g. `FixedBitSet`) that will add some non-sparse heap cost O(maxDoc) for each segment, but if there are enough ordinals to count, that can be a win over just the HPPC native int map for some cases?
Maybe this could be an intermediate implementation, since we already cover the "very low hit count" (use HPPC int/int map) and "very high hit count" (using `int[]`) today?
Also, this bit set would be able to quickly iterate over the sorted ordinals, which might be helpful if we move the three big `int[]` into numeric doc values?
---
Migrated from [LUCENE-10080](https://issues.apache.org/jira/browse/LUCENE-10080) by Michael McCandless (@mikemccand), updated Oct 04 2021
Contributor guide
Research direction
Start by locating Lucene's facet-counting implementation and reading the existing HPPC int/int map and non-sparse int[] paths described in the issue. The issue does not name files or tests; completion would require settling the bit-set design, integrating it with the current counting strategies, and demonstrating that the intended space or iteration benefits are achieved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100