apache / apache/lucene

Use a bit set to count long-tail of singleton FacetLabels? [LUCENE-10080]

Open
#11,118 12 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major module:facet type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.