MurmurHash3 for Java

Background

I needed a really good hash function for the distributed indexing we’re implementing for Solr. Since it will be used for partitioning documents, it needed to be really high quality (well distributed) since we don’t want uneven shards. It also needs to be cross-platform, so a client could calculate this hash value themselves if desired, to predict which node has a given document.

MurmurHash3

MurmurHash3 is one of the top favorite new hash function these days, being both really fast and of high quality. Unfortunately it’s written in C++, and a quick google did not yield any suitable high quality port. So I took 15 minutes (it’s small!) to port the 32 bit version, since it should be faster than the other versions for small keys like document ids. It works in 32 bit chunks and produces a 32 bit hash – more than enough for partitioning documents by hash code.

MurmurHash3-java

It would be nice to prevent others from having to do the same thing. Since stuff like this is small enough, I simply put it under the public domain and uploaded to github. This way anyone can just copy the file or the function into their project and avoid extra dependencies and license hassles.

Here’s the code, copy away!

Solr’s Realtime Get

Solr took another step toward increasing it’s NoSQL datastore capabilities, with the addition of realtime get.

Background

As readers probably know, Lucene/Solr search works off of point-in-time snapshots of the index. After changes have been made to the index, a commit (or a new Near Real Time softCommit) needs to be done before those changes are visible. Even with Solr’s new NRT (Near Real Time) capabilities, it’s probably not advisable to reopen the searcher more than once a second. However there are some use cases that require the absolute latest version of a document, as opposed to just a very recent version. This is where Solr’s new realtime get comes to the rescue, where the latest version of a document can be retrieved without reopening the searcher and risk disrupting other normal search traffic.

The Realtime-Get API

The realtime get handler is registered at the /get URL. As an example, a request like
http://localhost:8983/solr/get?id=SOLR1000&fl=id,name&wt=json
returns a response like

{"doc":{"id":"SOLR1000","name":"Solr, the Enterprise Search Server"}}

Notice that the optional fl (field list) parameter works as normal, allowing you to select the fields you want returned.

There’s also a realtime get component that can be inserted into any request handler, including the standard request handler.

How it works

The realtime get feature uses transaction logging to keep track of uncommitted updates to the index.  When a get request for a document is received, this log is checked first and retrieved from there if found.  If it’s not found, then the latest opened searcher is used to retrieve the document.  Checking the log is super fast, and IO reads from the log are fully concurrent for maximum scalability.

Try it out

Download a recent nightly build of Solr 4.0-dev and follow the Quick Start guide  on the Solr wiki.  Feedback on the solr-user mailing list is always appreciated!

Solr relevancy function queries

Lucene’s default ranking function uses factors such as tf, idf, and norm to help calculate relevancy scores.
Solr has now exposed these factors as function queries.

• docfreq(field,term) returns the number of documents that contain the term in the field.
• termfreq(field,term) returns the number of times the term appears in the field for that document.
• idf(field,term) returns the inverse document frequency for the given term, using the Similarity for the field.
• tf(field,term) returns the term frequency factor for the given term, using the Similarity for the field.
• norm(field) returns the “norm” stored in the index, the product of the index time boost and then length normalization factor.
• maxdoc() returns the number of documents in the index, including those that are marked as deleted but have not yet been purged.
• numdocs() returns the number of documents in the index, not including those that are marked as deleted but have not yet been purged.

We can use these new functions to develop and test custom ranking functions!  For example, if we wanted simple tf*idf for a given term, we could issue the following function query (if you have solr’s example server running with exampledocs indexed, just click on the following link):

http://localhost:8983/solr/select/?fl=score,id&defType=func&q=mul(tf(text,memory),idf(text,memory))

To avoid repeating the term we are using (text,memory) we can pull the field and term out into other query parameters:

http://localhost:8983/solr/select/?fl=score,id&defType=func&q=mul(tf($f,$t),idf($f,$t))&f=text&t=memory

Utilizing Solr’s new ability to sort by arbitrary function queries, we could now sort a query by the number of times a specific term appears in each document.  The following query searches for documents matching “DDR”, but then sorts by the number of times “memory” appears in the text field.

http://localhost:8983/solr/select/?fl=score,id&q=DDR&sort=termfreq(text,memory) desc

We could also utilize the “norm” function to sort by the longest field first.  This assumes there were no index time boosts and thus the norm is just the standard length normalization factor.

http://localhost:8983/solr/select/?fl=score,id&q=DDR&sort=norm(text) asc

Given Solr’s plethora of function queries (including the new spatial queries that return distance between points), the possibilities are almost endless.  To try this out,  you’ll need a recent nightly build of Solr 4.0-dev, or LucidWorks Enterprise, our commercial version of Solr.

Solr Result Grouping / Field Collapsing Improvements

I previously introduced Solr’s Result Grouping, also called Field Collapsing, that limits the number of documents shown for each “group”, normally defined as the unique values in a field or function query.

Since then, there have been a number of bug fixes, performance improvements, and feature enhancements. You’ll need a recent nightly build of Solr 4.0-dev, or the newly released LucidWorks Enterprise v1.6, our commercial version of Solr.

Feature Enhancements

One improvement is the ability to group by query via the group.query parameter. This functionality is very similar to facet.query, except that it retrieves the top documents that match the query, not just the count. This has many potential uses, including always getting the top documents for specific groups, or defining custom groups such has price ranges.

Another useful capability is the addition of the group.main parameter. Setting this to true causes the results of the first grouping command to be used as the main result list in a flattened response format that legacy clients will be able to handle.

For example, the grouped response format normally returns highly structured results under “grouped”.
…&q=solr+memory&group=true&group.field=manu_exact


 "grouped":{
  "manu_exact":{
   "matches":6,
   "groups":[{
     "groupValue":"Apache Software Foundation",
     "doclist":{"numFound":1,"start":0,"docs":[
       {
        "id":"SOLR1000",
        "name":"Solr, the Enterprise Search Server",
        "manu":"Apache Software Foundation"}]
     }},
    {
     "groupValue":"Corsair Microsystems Inc.",
     "doclist":{"numFound":2,"start":0,"docs":[
       {
        "id":"VS1GB400C3",
        "name":"CORSAIR ValueSelect 1GB 184-Pin DDR SDRAM Unbuffered DDR 400 (PC 3200) System Memory - Retail",
        "manu":"Corsair Microsystems Inc."}]
     }},
[...]


If we add group.main=true to the request, then we get back a much more familiar looking response (i.e. it looks like a normal non-grouped response):
…&q=solr+memory&group=true&group.field=manu_exact&group.main=true


 "response":{"numFound":6,"start":0,"docs":[
   {
    "id":"SOLR1000",
    "name":"Solr, the Enterprise Search Server",
    "manu":"Apache Software Foundation"},
   {
    "id":"VS1GB400C3",
    "name":"CORSAIR ValueSelect 1GB 184-Pin DDR SDRAM Unbuffered DDR 400 (PC 3200) System Memory - Retail",
    "manu":"Corsair Microsystems Inc."},


One can also use the group.format=simple parameter to select this simplified flattened response within the normal “grouped” section of the response.

Other recent enhancements include support for debugging explain, highlighting, faceting, and the ability to handle missing values in the grouping field by treating all documents without a value as being in the “null” group.

Performance Enhancements

There have been a number of performance enhancements, including an improvement to the short circuiting logic… cutting off low ranking documents earlier in the process. This important optimization resulted in a speedup of about 9x for collapsing on certain fields!

Collapsing on string fields was further optimized with specialized code that worked on ord values instead of the string values. This doubled the performance yet again!

Please see the Solr Wiki for further documentation on all of result grouping’s capabilities and parameters.

Indexing JSON in Solr 3.1

Solr has been able to produce JSON results for a long time, by adding wt=json to any query. A new capability has recently been added to allow indexing in JSON, as well as issuing other update commands such as deletes and commits.

All of the functionality that was available through XML update commands can now be given in JSON.
For example, you can index a document like so:


$ curl http://localhost:8983/solr/update/json -H 'Content-type:application/json' -d '
{
  "add": {
    "doc": {
      "id" : "ISBN:978-0641723445",
      "title" : "The Lightning Thief"
      "author" : "Rick Riordan",
      "series_t" : "Percy Jackson and the Olympians",
      "cat" : ["book","hardcover"],
      "genre_s" : "fantasy",
      "pages_i" : 384
      "price" : 12.50,
      "inStock" : true,
      "popularity" : 10
    }
  }
}'


Of course, if you want the doc to be visible, you must do a commit. This could have been done by adding a commit=true parameter to the URL in the previous command, or we could have added a commit command within the JSON itself. This time we’ll issue a separate commit command.


curl "http://localhost:8983/solr/update/json?commit=true"


And now, we can query the Solr index and verify the document has been correctly added (requesting the results in JSON of course!)

http://localhost:8983/solr/select?wt=json&indent=true&q=title:lightning

There’s more documentation on the Solr Wiki.
To use this functionality, you’ll need to use LucidWorks Enterprise (our commercial version of Solr), or a recent Solr 3.1-dev or 4.0-dev nightly build.

Solr Result Grouping / Field Collapsing

Result Grouping, also called Field Collapsing, has been committed to Solr!
This functionality limits the number of documents for each “group”, usually defined by the unique values in a field (just like field faceting).

You can think of it like faceted search, except instead of just getting a count, you get the top documents for that constraint or category. There are tons of potential use cases:

• For web search, only show 1 or 2 results for a given website by collapsing on a site field.
• For email search, only show 1 or 2 results for a given email thread
• For e-commerce, show the top 3 products for each store category (i.e. “electronics”, “housewares”)
• Hiding duplicate documents at query time.

In addition to being able to group by the values of a field, you can also group by the values of a function query. Given that geo search works as a function query, this also opens up possibilities for showing top query matches within 1 mile, between 1 and 2 miles, etc.

Just like faceting, we’ll be adding new functionality and making continual improvements.
Result Grouping is documented on the Solr Wiki, and you will need a recent
nightly build of Solr 4.0-dev to try it out (just make sure it’s dated after this post).

CSV output for Solr

Solr has been able to slurp in CSV for quite some time, and now I’ve finally got around to adding the ability to output query results in CSV also. The output format matches what the CSV loader can slurp.

Adding a simple wt=csv to a query request will cause the docs to be written in a CSV format that can be loaded into something like Excel.

http://localhost:8983/solr/select?q=ipod&fl=id,cat,name,popularity,price,score&wt=csv

id,cat,name,popularity,price,score
IW-02,"electronics,connector",iPod & iPod Mini USB 2.0 Cable,1,11.5,0.98867977
F8V7067-APL-KIT,"electronics,connector",Belkin Mobile Power Cord for iPod w/ Dock,1,19.95,0.6523595
MA147LL/A,"electronics,music",Apple 60 GB iPod with Video Playback Black,10,399.0,0.2446348

CSV formats tend to vary, so there are a number of parameters that allow you to customize the output. For example setting csv.escape=\ and csv.separator=%09 (a URL-encoded tab character) will use a tab separator and backslash escaping to match the default CSV format that MySQL uses.

http://localhost:8983/solr/select?q=ipod&fl=score,id&wt=csv&csv.escape=\&csv.separator=%09

score	id
0.98867977	IW-02
0.6523595	F8V7067-APL-KIT
0.2446348	MA147LL/A

The CSVResponseWriter is documented on the Solr Wiki, but you will need a recent
nightly build (Solr 3.1-dev or Solr 4.0-dev) to try it out.

Ranges over Functions in Solr 1.4

Solr 1.4 contains a new feature that allows range queries or range filters over arbitrary functions.  It’s implemented as a standard Solr QParser plugin, and thus easily available for use any place that accepts the standard Solr Query Syntax by specifying the frange query type.  Here’s an example of a filter specifying the lower and upper bounds for a function:

fq={!frange l=0 u=2.2}log(sum(user_ranking,editor_ranking))

The other interesting use for frange is to trade off memory for speed when doing range queries on any type of single-valued field.  For example, one can use frange on a string field provided that there is only one value per field, and that numeric functions are avoided.

For example, here is a filter that only allows authors between martin and rowling, specified using a standard range query:
fq=author_last_name:[martin TO rowling]

And the same filter using a function range query (frange):
fq={!frange l=martin u=rowling}author_last_name

This can lead to significant performance improvements for range queries with many terms between the endpoints, at the cost of memory to hold the un-inverted form of the field in memory (i.e. a FieldCache entry – same as would be used for sorting). If the field in question is already being used for sorting or other function queries, there won’t be any additional memory overhead.

The following chart shows the results of a test of frange queries vs standard range queries on a string field with 200,000 unique values. For example, frange was 14 times faster when executing a range query / range filter that covered 20% of the terms in the field. For narrower ranges that matched less than 5% of the values, the traditional range query performed better.

Percent of terms covered	Fastest implementation	Speedup (how many times faster)
100%	frange	43.32
20%	frange	14.25
10%	frange	8.07
5%	frange	1.337
1%	normal range query	3.59

Of course, Solr 1.4 also contains the new TrieRange functionality that will generally have the best time/space profile for range queries over numeric fields.

Filtered query performance increases for Solr 1.4

One of the many performance improvements in the upcoming Solr 1.4 release involves improved filtering performance. Solr 1.4 filters are both faster (anywhere from 30% to 80% faster to calculate intersections, depending on configuration), take less memory (40% smaller), and are more efficiently applied to the query during a search.

In previous Solr releases, filters were applied after the main query and thus had little impact on overall query performance. Filters are now checked in parallel with the query, resulting in greater speedups the fewer documents that match the filters.

Example: Adding a filter that matched 10% of a large index resulted in a 300% performance increase for a dismax query consisting of three words on a single field with proximity boost.

Related issues:

https://issues.apache.org/jira/browse/SOLR-1169

https://issues.apache.org/jira/browse/SOLR-1179

Solr scalability improvements

With CPU cores constantly increasing, there has been some major work done in Lucene/Solr to increase the scalability under multi-threaded load.

Read-only IndexReaders

One bottleneck was synchronization around the checking of deleted docs in a Lucene IndexReader.  Since another thread could delete a document at any time, the IndexReader.isDeleted() call was synchronized.  It’s a very quick call, simply checking if a bit is set in a BitVector, but the problem was that it can be called millions of times in the process of satisfying a single query. The Read-only IndexReader feature allowed for the removal of this synchronization by prohibiting deletion.

Use of NIO to read index files

The standard method for Lucene to read index files is via Java’s RandomAccessFile.  Reading a part of the file involves two calls, a seek() to position the file pointer followed by a read() to get the data.  For multiple threads to share the same RandomAccessFile instance, this obviously involves synchronization to avoid one thread changing the file pointer before another thread gets to read at the file position it set.   If the data to be read isn’t in the operating system cache, it’s even worse news… the synchronization causes all other reads to block while the data is retrieved from disk, even if some of those reads could have been quickly satisified.

The preferred solution would be to have a method on RandomAccessFile that accepted an offset to read from.  This could easily be implemented by the JVM via a pread() system call.  But since Sun has not provided this functionality, we need to use something else.  NIO’s FileChannel does have the type of method we are looking for:  FileChannel.read(ByteBuffer dst, long position)

Solr now uses the non-synchronizing NIO method of reading index files (via Lucene’s NIOFSDirectory) by default if you are on a non-Windows platform.  Windows systems default to the older method since it turns out to be faster than the new method – the reason being a long standing “bug” in Java that still synchronizes internally even when using FileChannel.read().

Non blocking caches

Solr’s standard LRU cache implementation use a synchronized LinkedHashMap.  A single cache could be checked hundreds or thousands of times during the course of a single request that involves faceting.  A non-blocking ConcurrentLRUCache was developed as an alternative implementation, and is now the default for Solr’s filter cache.  One user indicated that this has doubled their query throughput under ideal circumstances.

Where to find this scalability goodness?

Solr 1.3 has read-only IndexReaders, but for the other scalability improvements, including the improved faceting, you’ll have to grab a nightly Solr build.