Lucene Search within Search with BitSets

The Search within Search functionality is typically used when presenting results from an index in response to a user defined query. In addition to the search results returned to the user, we may want to show the user that he can drill down to get more focused search results for his query. So, for example, if the user searched for "cancer" on a medical search engine, in additions to pages that discuss cancer, we may want to show him how many occurences of "brain cancer", "lung cancer", etc, he can get from our index. These would be represented as a set of navigation links on the page. Clicking one of these links would spawn a fresh search with the augmented query term.

If you use Lucene, you will know that the popular ways of doing this is to either use a Boolean Query or search using a QueryFilter. A less popular, but incredibly powerful, way to count facet hits is to use BitSets returned by the QueryFilter. My ex-colleague Chris Hostetter refers to it in passing when announcing that CNET Category pages are powered by Lucene.

In this article, I present a Facet Hit counting class, which when passed in a reference to an IndexSearcher object, a reference to the base Lucene Query object, and a Map of facet names and their corresponding Query objects, returns a Map of facet names and their counts.

Caller code

The code for the caller would look something like this:

1 2 3 4 5 6 7 8 9 10 11 12

IndexSearcher searcher = new IndexSearcher("/path/to/index"); Query baseQuery = new TermQuery(new Term("body", "cancer")); Map<String,Query> subQueries = new HashMap<String,Query>(); subQueries.put("Lung Cancer", new TermQuery(new Term("body", "lung"))); subQueries.put("Brain Cancer", new TermQuery(new Term("body", "brain"))); subQueries.put("Skin Cancer", new TermQuery(new Term("body", "skin"))); ... BitSetFacetHitCounter facetHitCounter = new BitSetFacetHitCounter(); facetHitCounter.setSearcher(searcher); facetHitCounter.setBaseQuery(baseQuery); facetHitCounter.setSubQueries(subQueries); Map<String,Integer> counts = facetHitCounter.getFacetHitCounts();

The BitSetFacetHitCounter class

The code for the BitSetFacetHitCounter is shown below. The getFacetHitCounts() method creates the QueryFilter objects for the baseQuery and each of their subqueries and extracts their BitSets. Each bit in the BitSet corresponds to a Document in the index. If the bit is turned on, then the Document matched the query, else not. The intersection of the BitSets for the base query and the subquery is another BitSet, whose bits are turned on for those records where both the base query and the subquery are satisfied. In our example, the resulting BitSet will have only the bits for records containing "cancer" and "lung" turned on, so counting the 1's will give us the number of records for "lung cancer".

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

public class BitSetFacetHitCounter implements IFacetHitCounter { private Query baseQuery; private Map<String,Query> subQueries; private IndexSearcher searcher; public BitSetFacetHitCounter() { super(); } public void setBaseQuery(Query baseQuery) { this.baseQuery = baseQuery; } public void setSubQueries(Map<String,Query> subQueries) { this.subQueries = subQueries; } public void setSearcher(IndexSearcher searcher) { this.searcher = searcher; } public Map<String,Integer> getFacetHitCounts() throws Exception { Map<String,Integer> facetCounts = new HashMap<String,Integer>(); IndexReader reader = searcher.getIndexReader(); QueryFilter baseQueryFilter = new QueryFilter(baseQuery); BitSet baseBitSet = baseQueryFilter.bits(reader); for (String attribute : subQueries.keySet()) { QueryFilter filter = new QueryFilter(subQueries.get(attribute)); BitSet filterBitSet = filter.bits(reader); facetCounts.put(attribute, getFacetHitCount(baseBitSet, filterBitSet)); } return facetCounts; } private int getFacetHitCount(BitSet baseBitSet, BitSet filterBitSet) { filterBitSet.and(baseBitSet); return filterBitSet.cardinality(); } }

Alternate implementations

The other options for doing this are using BooleanQueries and searching with QueryFilters. The code for the getFacetHitCounts() method using these methods are also shown below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// using Boolean queries public Map<String,Integer> getFacetHitCounts() throws Exception { Map<String,Integer> facetCounts = new HashMap<String,Integer>(); for (String attribute : subQueries.keySet()) { BooleanQuery facetQuery = new BooleanQuery(); facetQuery.add(baseQuery, BooleanClause.Occur.MUST); facetQuery.add(subQueries.get(attribute), BooleanClause.Occur.MUST); Hits hits = searcher.search(facetQuery); facetCounts.put(attribute, hits.length()); } return facetCounts; } // using search with QueryFilters public Map<String, Integer> getFacetHitCounts() throws Exception { Map<String,Integer> facetCounts = new HashMap<String,Integer>(); for (String attribute : subQueries.keySet()) { QueryFilter filter = new QueryFilter(subQueries.get(attribute)); Hits hits = searcher.search(baseQuery, filter); facetCounts.put(attribute, hits.length()); } return facetCounts; }

Some performance numbers

I ran the same test case through all three implementations, working with 6 facets, in order to compare results. My experiments are not controlled, its simply tracking elapsed time using System.currentTimeMillis() in my JUnit test code, so your mileage may vary.

Implementation	Elapsed time (ms)
Bit Set implementation	40
Query Filter implementation	41
Boolean Query Implementation	50

As you can see, there does not seem to be much difference, performance-wise, between the three implementations. However, I am guessing that the BitSet approach will outperform the others as the invocations are increased. Also, both the QueryFilter and the BitSet approach will take advantage of QueryFilter caching within Lucene, which can be useful if you are not using external caching.