You are viewing a plain text version of this content. The canonical link for it is here.
Posted to solr-dev@lucene.apache.org by Yonik Seeley <yo...@apache.org> on 2006/09/20 23:21:34 UTC

big faceting speedup for single valued fields

I implemented the FieldCache implementation for faceted browsing on a
field that is not tokenized (integer, sint, string, etc) and not
multiValued, so there is a max of one token per document.

Before optimization:  10.03 seconds (filtercache not large enough to
hold all possible vals)
After optimization:  0.02 seconds   (500 times faster!)
Cool eh?

The base query matched 166,000 documents out of 25 million.
I faceted on author, which I assume there are many of, but I don't
have exact numbers.


This isn't the last word on faceted optimizations, there are other
common cases that may be optimized, but don't expect results anywhere
near this again ;-)

Here's the changes I'll commit shortly unless there are objections
(sorry about the false-changes... I think it must be trailing
whitespace that my IDE stripped of or something... I'll try to fix
that for the future)

Index: src/java/org/apache/solr/schema/FieldType.java
===================================================================
--- src/java/org/apache/solr/schema/FieldType.java	(revision 443015)
+++ src/java/org/apache/solr/schema/FieldType.java	(working copy)
@@ -57,7 +57,7 @@
   int properties;

   /** Returns true if fields of this type should be tokenized */
-  protected boolean isTokenized() {
+  public boolean isTokenized() {
     return (properties & TOKENIZED) != 0;
   }

Index: src/java/org/apache/solr/request/SimpleFacets.java
===================================================================
--- src/java/org/apache/solr/request/SimpleFacets.java	(revision 443015)
+++ src/java/org/apache/solr/request/SimpleFacets.java	(working copy)
@@ -20,23 +20,20 @@
 import org.apache.lucene.index.TermEnum;
 import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.queryParser.ParseException;
-import org.apache.lucene.queryParser.QueryParser;
 import org.apache.lucene.search.*;
 import org.apache.solr.core.SolrCore;
 import org.apache.solr.core.SolrException;
 import org.apache.solr.request.SolrParams;
-import org.apache.solr.request.SolrQueryRequest;
-import org.apache.solr.request.SolrQueryResponse;
-import org.apache.solr.request.DefaultSolrParams;
 import org.apache.solr.schema.IndexSchema;
 import org.apache.solr.schema.FieldType;
+import org.apache.solr.schema.SchemaField;
+import org.apache.solr.schema.BoolField;
 import org.apache.solr.search.*;
 import org.apache.solr.util.NamedList;
 import org.apache.solr.util.BoundedTreeSet;

 import java.io.IOException;
 import java.util.*;
-import java.util.logging.Level;

 /**
  * A class that generates simple Facet information for a request.
@@ -52,15 +49,16 @@
   protected SolrParams params;
   /** Searcher to use for all calculations */
   protected SolrIndexSearcher searcher;
-
-  public SimpleFacets(SolrIndexSearcher searcher,
-                      DocSet docs,
+
+
+  public SimpleFacets(SolrIndexSearcher searcher,
+                      DocSet docs,
                       SolrParams params) {
     this.searcher = searcher;
     this.docs = docs;
     this.params = params;
   }
-
+
   /**
    * Looks at various Params to determing if any simple Facet Constraint count
    * computations are desired.
@@ -73,7 +71,7 @@
   public NamedList getFacetCounts() {

     // if someone called this method, benefit of the doubt: assume true
-    if (!params.getBool(params.FACET,true))
+    if (!params.getBool(params.FACET,true))
       return null;

     NamedList res = new NamedList();
@@ -82,7 +80,7 @@
       res.add("facet_queries", getFacetQueryCounts());

       res.add("facet_fields", getFacetFieldCounts());
-
+
     } catch (Exception e) {
       SolrException.logOnce(SolrCore.log, "Exception during facet counts", e);
       res.add("exception", SolrException.toStr(e));
@@ -97,7 +95,7 @@
    * @see SolrParams#FACET_QUERY
    */
   public NamedList getFacetQueryCounts() throws IOException,ParseException {
-
+
     NamedList res = new NamedList();

     /* Ignore SolrParams.DF - could have init param facet.query assuming
@@ -106,7 +104,7 @@
      * explicit.
      */
     SolrQueryParser qp = new SolrQueryParser(searcher.getSchema(),null);
-
+
     String[] facetQs = params.getParams(SolrParams.FACET_QUERY);
     if (null != facetQs && 0 != facetQs.length) {
       for (String q : facetQs) {
@@ -125,22 +123,33 @@
    * @see #getFacetFieldMissingCount
    * @see #getFacetTermEnumCounts
    */
-  public NamedList getFacetFieldCounts()
-    throws IOException {
-
+  public NamedList getFacetFieldCounts()
+          throws IOException {
+
     NamedList res = new NamedList();
     String[] facetFs = params.getParams(SolrParams.FACET_FIELD);
-    if (null != facetFs && 0 != facetFs.length) {
-
+    if (null != facetFs) {
       for (String f : facetFs) {
+        NamedList counts=null;
+        SchemaField sf = searcher.getSchema().getField(f);
+        FieldType ft = sf.getType();

-        NamedList counts = getFacetTermEnumCounts(f);
-
-        if (params.getFieldBool(f, params.FACET_MISSING, false))
-          counts.add(null, getFacetFieldMissingCount(f));
-
+        int limit = params.getFieldInt(f, params.FACET_LIMIT, 100);
+        boolean zeros = params.getFieldBool(f, params.FACET_ZEROS, true);
+        boolean missing = params.getFieldBool(f, params.FACET_MISSING, false);
+
+
+        if (sf.multiValued() || ft.isTokenized() || ft instanceof BoolField) {
+          counts = getFacetTermEnumCounts(f,limit,zeros);
+          if (missing) {
+            counts.add(null, getFacetFieldMissingCount(f));
+          }
+        } else {
+          // TODO: future logic could use filters instead of the fieldcache if
+          // the number of terms in the field is small enough.
+          counts = getFieldCacheCounts(f, limit, zeros, missing);
+        }
         res.add(f, counts);
-
       }
     }
     return res;
@@ -160,6 +169,63 @@
     return docs.andNotSize(hasVal);
   }

+
+  NamedList getFieldCacheCounts(String fieldName, int limit, boolean
zeros, boolean missing) throws IOException {
+    // TODO: If the number of terms is high compared to docs.size(),
and zeros==false,
+    //  we should use an alternate strategy to avoid
+    //  1) creating another huge int[] for the counts
+    //  2) looping over that huge int[] looking for the rare non-zeros.
+    //
+    // Yet another variation: if docs.size() is small and termvectors
are stored,
+    // then use them instead of the FieldCache.
+    //
+
+    FieldCache.StringIndex si =
FieldCache.DEFAULT.getStringIndex(searcher.getReader(), fieldName);
+    int[] count = new int[si.lookup.length];
+    DocIterator iter = docs.iterator();
+    while (iter.hasNext()) {
+      count[si.order[iter.nextDoc()]]++;
+    }
+
+    FieldType ft = searcher.getSchema().getFieldType(fieldName);
+    NamedList res = new NamedList();
+
+    // IDEA: we could also maintain a count of "other"... everything
that fell outside
+    // of the top 'N'
+
+    BoundedTreeSet<CountPair<String,Integer>> queue=null;
+
+    if (limit>=0) {
+      // TODO: compare performance of BoundedTreeSet compare against
priority queue?
+      queue = new BoundedTreeSet<CountPair<String,Integer>>(limit);
+    }
+
+    int min=-1;  // the smallest value in the top 'N' values
+    for (int i=1; i<count.length; i++) {
+      int c = count[i];
+      if (c==0 && !zeros) continue;
+      if (limit<0) {
+        res.add(ft.indexedToReadable(si.lookup[i]), c);
+      } else if (c>min) {
+        // NOTE: we use c>min rather than c>=min as an optimization
because we are going in
+        // index order, so we already know that the keys are ordered.
 This can be very
+        // important if a lot of the counts are repeated (like zero
counts would be).
+        queue.add(new
CountPair<String,Integer>(ft.indexedToReadable(si.lookup[i]), c));
+        if (queue.size()>=limit) min=queue.last().val;
+      }
+    }
+
+    if (limit>=0) {
+      for (CountPair<String,Integer> p : queue) {
+        res.add(p.key, p.val);
+      }
+    }
+
+
+    if (missing) res.add(null, count[0]);
+    return res;
+  }
+
   /**
    * Returns a list of terms in the specified field along with the
    * corrisponding count of documents in the set that match that constraint.
@@ -167,50 +233,46 @@
    * @see SolrParams#FACET_LIMIT
    * @see SolrParams#FACET_ZEROS
    */
-  public NamedList getFacetTermEnumCounts(String fieldName)
+  public NamedList getFacetTermEnumCounts(String fieldName, int
limit, boolean zeros)
     throws IOException {
-
+
     /* :TODO: potential optimization...
-     * cache the Terms with the highest docFreq and try them first
-     * don't enum if we get our max from them
-     */
-
+    * cache the Terms with the highest docFreq and try them first
+    * don't enum if we get our max from them
+    */
+
     IndexSchema schema = searcher.getSchema();
     IndexReader r = searcher.getReader();
     FieldType ft = schema.getFieldType(fieldName);

-    Set<CountPair<String,Integer>> counts
+    Set<CountPair<String,Integer>> counts
       = new HashSet<CountPair<String,Integer>>();

-    int limit = params.getFieldInt(fieldName, params.FACET_LIMIT, 100);
     if (0 <= limit) {
       counts = new BoundedTreeSet<CountPair<String,Integer>>(limit);
     }

-    boolean zeros = params.getFieldBool(fieldName, params.FACET_ZEROS, true);
-
     TermEnum te = r.terms(new Term(fieldName,""));
     do {
       Term t = te.term();

-      if (null == t || ! t.field().equals(fieldName))
+      if (null == t || ! t.field().equals(fieldName))
         break;

       if (0 < te.docFreq()) { /* all docs may be deleted */
         int count = searcher.numDocs(new TermQuery(t),
                                      docs);

-        /* :TODO: is indexedToReadable correct? */
-        if (zeros || 0 < count)
+        if (zeros || 0 < count)
           counts.add(new CountPair<String,Integer>
-                     (ft.indexedToReadable(t.text()), count));
+                     (t.text(), count));

       }
     } while (te.next());

     NamedList res = new NamedList();
     for (CountPair<String,Integer> p : counts) {
-      res.add(p.key, p.val);
+      res.add(ft.indexedToReadable(p.key), p.val);
     }
     return res;
   }
@@ -220,7 +282,7 @@
    * <b>higher</b> vals come before lower vals.
    * In case of tie vals, then <b>lower</b> keys come before higher keys.
    */
-  public static class CountPair<K extends Comparable<? super K>, V
extends Comparable<? super V>>
+  public static class CountPair<K extends Comparable<? super K>, V
extends Comparable<? super V>>
     implements Comparable<CountPair<K,V>> {

     public CountPair(K k, V v) {
@@ -232,7 +294,7 @@
       return key.hashCode() ^ val.hashCode();
     }
     public boolean equals(Object o) {
-      return (o instanceof CountPair)
+      return (o instanceof CountPair)
         && (0 == this.compareTo((CountPair<K,V>) o));
     }
     public int compareTo(CountPair<K,V> o) {

Property changes on: src/java/org/apache/solr/request/SimpleFacets.java
___________________________________________________________________
Name: svn:eol-style
   + native



-Yonik

Re: big faceting speedup for single valued fields

Posted by Yonik Seeley <yo...@apache.org>.
On 9/21/06, Chris Hostetter <ho...@fucit.org> wrote:
>
> : I'll try to update my patch to pull out a getFieldFacets method that
> : encapsulates parameter parsing and the decision of what faceting
> : strategy to call... that way soneone could add their own method and
> : override getFieldFacets() to call it in certain cases.  I'm not sure
> : it's really a realistic use-case though.
>
> I see your point ... i guess i tend to think that fragile base class
> issues can be reduced by clearly documented pre/post conditions but yor
> probably right ... this code is new enough and will probably fluctuate
> enough over time that trying to anticipate all the use cases in advance is
> asking for trouble, so structuring it as a toolkit of utilities is a
> better idea then as a base class.

It's checked in.  Feel free to change things... I'm not married to the
specific static/non-static/name of methods.  Better to get what I have
out there so others can edit it also (esp since it's still in flux...
we won't be breaking anything by changing it now).

-Yonik

Re: big faceting speedup for single valued fields

Posted by Chris Hostetter <ho...@fucit.org>.
: I'll try to update my patch to pull out a getFieldFacets method that
: encapsulates parameter parsing and the decision of what faceting
: strategy to call... that way soneone could add their own method and
: override getFieldFacets() to call it in certain cases.  I'm not sure
: it's really a realistic use-case though.

I see your point ... i guess i tend to think that fragile base class
issues can be reduced by clearly documented pre/post conditions but yor
probably right ... this code is new enough and will probably fluctuate
enough over time that trying to anticipate all the use cases in advance is
asking for trouble, so structuring it as a toolkit of utilities is a
better idea then as a base class.



-Hoss


Re: big faceting speedup for single valued fields

Posted by Yonik Seeley <yo...@apache.org>.
On 9/20/06, Chris Hostetter <ho...@fucit.org> wrote:
> They can still choose to compose a SimpleFacets instance and
> treat it as a collection of utilities, but i'd like to make sure
> subclasses that only override a small piece of the functionality are easy
> to write.

"override a small piece" is overly generic.  Base classes need to be
designed carefully and *specifically* for allowing certain methods to
be overridden. If you just export your current implementation and say
"overidde any piece you want", you end up with a big mess in the
future.

Let's say someone did want to do facets slightly different, and they
override   getFacetTermEnumCounts.  Now I come along and add a
different strategy (getFieldCacheCounts) and now their class is broken
because they relied on getFacetTermEnumCounts always being called.

http://en.wikipedia.org/wiki/Fragile_base_class

I would not expect a client to override getFieldCacheCounts or
getFacetTermEnumCounts.  I *could* see someone calling specific
implementations though...

We need use-cases to intelligently evaluate what the internal API
should look like.
I could see a custom query handler doing conditional faceting based on
previous results:

f = Faceting.getFieldCacheCounts(base_doc_set, "foo",10,false,false)
if (f.getValue(0) > 100) {
  // OK, the first value is big... let's further split it by field "bar"
  DocSet newDocSet = base_doc_set.intersection(doc_set_for_top_term)
  f2 = Faceting.getFieldTermEnumCounts(newDocSet, "bar",10,false,false)
} else {
   // too few values, try faceting on a different field
  f = Faceting.getFieldCacheCounts(base_doc_set, "baz",25,false,false)
}


I'll try to update my patch to pull out a getFieldFacets method that
encapsulates parameter parsing and the decision of what faceting
strategy to call... that way soneone could add their own method and
override getFieldFacets() to call it in certain cases.  I'm not sure
it's really a realistic use-case though.


-Yonik

Re: big faceting speedup for single valued fields

Posted by Chris Hostetter <ho...@fucit.org>.
: Depends on what one things the "entry" point should be, or the unit of re-use.
: If someone is implementing their own custom handler, they may very
: well be doing param parsing differently.  The lowest level routines

but the bueaty of hte SolrParam class is that it isn't inheriently tied
to request params .. a custom request handler that wants it's own way of
determing the faceting behavior could construct an arbitrary
MapSolrParams for use in the constructor to SimpleFacets.

: should perhaps even be static and have everything passed into them
: (searcher, field, options).  I'm flexible though :-)

i avoided statics because it makes it hard to future code to customize
*some* of the behavior ... ie: right now a client could subclass
SimpleFacets and override just the getFacetFieldCounts to include an
optimization like the one you provided, and still leverage both the "lower
level methods like getFacetTermEnumCounts and getFacetFieldMissingCount
from within their new version, as well as trusting that the "higher" level
getFacetCounts will call their version of getFacetFieldCounts.

If any of those methods had been static, custom client code would need to
cut/past a lot of the "glue" again.

: I haven't thought much about it, and I don't know what you had in
: mind... but would someone really override methods of SimpleFacets?  It
: seems more likely that they would use it more as a library resource,
: calling methods to do different things as needed, and that can easily
: be done with composition rather than inheritance.

If everything is static, then they *have* to use it as a library resource
and all of hte glue methods (like getFacetCounts) have to be rewritten,
and custom clients don't get to take advantage of future additions as
easily.  They can still choose to compose a SimpleFacets instance and
treat it as a collection of utilities, but i'd like to make sure
subclasses that only override a small piece of the functionality are easy
to write.


(we kind of have hte same problem with the request handlers right now:
with all of hte funcionality directly in handleRequest, it's hard for
people to subclass it and override a small bit of functionality without
cuting/pasting a lot of code ... which is one of the reasons i added the
StandardRequestHandler.getFacetInfo method, even though all the real work
is in SimpleFacets -- if developers want all of hte behavior of
StandardRequestHanlder, but have their own more complex Faceting system
they want to use, they can write a 3 line subclass and still benefit from
any future additions to StandardRequestHandler.


-Hoss


Re: big faceting speedup for single valued fields

Posted by Yonik Seeley <yo...@apache.org>.
On 9/20/06, Chris Hostetter <ho...@fucit.org> wrote:
> one thing confuses me: why the boolean params for missing/zero in the
> method declarations for getFieldCacheCounts and getFieldTermEnumCounts ?

I envision multiple ways of getting facet counts, with the most
efficient being called based on heuristics, cached term information,
etc...  putting param parsing into each of these methods doesn't seem
right.

Notice how the new method I added is package protected... I'm not yet
sure at what level the public API should be.

> ... for getFieldTermEnumCounts i was pulling that info from the protected
> member variable "params" to keep the method signatures simple for when the
> day comes that we want the behavior to be driven by additional params

Depends on what one things the "entry" point should be, or the unit of re-use.
If someone is implementing their own custom handler, they may very
well be doing param parsing differently.  The lowest level routines
should perhaps even be static and have everything passed into them
(searcher, field, options).  I'm flexible though :-)

> (i expect there will be custom subclasses to SimpleFacets in the future
> reusing these methods, and i'd hate to keep adding method params that make
> it hard for those subclasses)

I haven't thought much about it, and I don't know what you had in
mind... but would someone really override methods of SimpleFacets?  It
seems more likely that they would use it more as a library resource,
calling methods to do different things as needed, and that can easily
be done with composition rather than inheritance.

-Yonik

Re: big faceting speedup for single valued fields

Posted by Chris Hostetter <ho...@fucit.org>.
: Here's the changes I'll commit shortly unless there are objections
: (sorry about the false-changes... I think it must be trailing

one thing confuses me: why the boolean params for missing/zero in the
method declarations for getFieldCacheCounts and getFieldTermEnumCounts ?
... for getFieldTermEnumCounts i was pulling that info from the protected
member variable "params" to keep the method signatures simple for when the
day comes that we want the behavior to be driven by additional params
(i expect there will be custom subclasses to SimpleFacets in the future
reusing these methods, and i'd hate to keep adding method params that make
it hard for those subclasses)



-Hoss