Saturday May 10, 2008
Otis asked about Minion performance and how it compares to Lucene.
We did some performance comparisons a while ago, and it probably deserves a full post. Part of the problem with performance comparisons is that it's hard to get the same conditions for both systems.
I think it would be a good idea for all of the open source engines to get together, find a nice open document collection (the Apache mailing list archives and their associated searches?) and build a nice set of regression tests and some pooled relevance sets so that we can test retrieval performance without having to rely on the TREC data.
At any rate, we used Lucene 2.0 and a build of Minion to build an indexer for email messages. We used these to build indexes of 1.1 million email messages. We then ran a bunch of queries against the index. The messages and queries were taken from an archive of about 5 million messages that we provide internally. We ran the queries serially and in parallel up to 32 threads on a couple of Sun x64 and Niagara boxes.
The practical upshot was that the Minion indexer was substantially faster than the Lucene indexer (at the cost of more memory used) and the queries were comparable in similar conditions. Of course, indexing speed probably isn't that big a deal in most situations.
Our "standard" config Lucene did a lot better than our default Minion config, which is totally understandable, since Minion was doing a lot more work (e.g., doing query term expansion, processing the case sensitive postings and searching all the fields). When we feed Lucene our expanded terms, and both engines are doing straightforward boolean AND, the difference in query times is about 10% in Lucene's favor. This sounds like a lot, but we're talking about 35ms vs 39ms.
I have no doubt that we could go in and massage the query evaluator (or come up with a more efficient postings format, or ...) to get that 10% back and I'm sure that the Lucene folks could go in and get another 10%, lather, rinse, repeat.
With respect to global IDF, we store a separate dictionary containing global term statistics, so when we're doing weighting, we're using the statistics for the collection as a whole. We actually try to be fairly careful about the term statistics, especially for things like document categorization.
As for distributed search, Minion is like Lucene in that it's a simple indexing and retrieval library. We're working on distributing the search as part of Aura, but I can't really comment on the performance there yet as it's still pretty early days. I will say that it was pretty pleasingly fast on a 7 million document index distributed into 16 pieces — fast enough that I thought it was broken when we ran the first queries. I'll let you know how it goes when we have 100 million or a billion docs :-)
Thursday May 08, 2008
Although I did attend the The Harvard of the North!
I gave a talk at Harvard early in April on the history of search at Sun. If you're interested you can watch the video. I'm the big dude up at the front there. Also, you get a few thrilling seconds of Jim Waldo close to the start.
I go into a bit of background on the early work that formed the foundation for our engine, and some of the stuff that's going into Minion and Aura.
Thursday May 08, 2008
The query languages for the two engines provide the usual suite of boolean operators with their usual interpretations. One difference is that, in Lucene, the NOT operator must be used in opposition to a term, it can not appear on its own. That is, the query: NOT dog is not valid. Only queries like cat NOT dog are valid. In Minion, NOT is a fully general operator that can be applied to any subexpression in a query.
As we've mentioned in previous installments, Minion provides a number of query operators that Lucene does not, most of which are aimed at modifying the case behavior or variant behavior when looking up query terms in a dictionary.
Minion provides a full suite of proximity operators, all of which are based on the Sun Labs Relaxation Ranking Passage Retrieval algorithm. This allows for compatibility of scoring between (for example) NEAR, PHRASE, and PASSAGE queries. Minion's query evaluator allows you to do some pretty cool things, like finding phrases that are near each other.
Lucene provides PHRASE and NEAR operators in its query language, but there is no indication of how the nearness of terms will affect the score assigned to a document. Recent versions of Lucene have introduced the notion of query spans, which are document, start position, and end position tuples. These spans can be used to implement any number of proximity operators, although they must be used programatically (i.e., they are not part of the query language.) They seem similar in intent to the work done at Waterloo on Multitext.
Minion is designed to provide any number of query languages that can be selected per-query. We have developed a Lucene query parser that handles the Lucene query language as well as parsers for our own query language and a "Web" query language.
One thing that Lucene has that Minion doesn't (and we want!) is an API for constructing queries programatically. This is really useful, especially in situations where you want to build queries from input from a user interface. If the users are entering full strings (e.g., for substring matches in an email subject), if you want to build a query for Minion, then you need to build a string containing whatever query operators are appropriate. Of course, you need to make sure that the query you build is syntactically valid so that the query parser doesn't choke on it.
Lucene provides an API that you can use to construct queries, essentially it allows you to build the structure that the query parser would generate (not exactly, but you get the idea!). You could do this in Minion, but it would be extremely unpleasant to do so. I expect that we'll be adding a programmatic query API in the relatively near future.
As far as document ranking goes, if I understand correctly, both Minion and Lucene use a variation of the standard TFIDF weighting function, and both allow for users of the system to implement any particular weighting function that they like (e.g., I'm pretty sure there's a BM25 implementation for Lucene).
I would expect that the ranking differences that you would see between Minion and Lucene on a given query on a given document collection would probably be due more to how the respective engines are configured (e.g., was stemming or morphological expansion used?), rather than any fundamental differences in the performance of the engines.
Wednesday May 07, 2008
Jeff and I gave our talk at JavaOne today. I'll post a link to the audio and slides once it's up.
The big news today is that the source for Minion is now available at java.net.
This is pretty exiciting for us. If you're interested in trying Minion, please do download the source, join the project and the mailing lists, read the getting started docs, and give it a go!
Minion's under active development, and we'll be working on documentation and tutorials as we go, so stay tuned.
Saturday May 03, 2008
Back in the good old days, most search engines stemmed the terms being indexed.
The idea was that removing the suffixes on a word would save space (since you need to store fewer terms in the dictionary and store fewer postings), and it would allow the users to type in any variant of a particular term. The engine would stem the query terms before looking them up in the dictionary, resulting in the engine returning the documents for all variants of the term.
The problem with this approach is that it makes it impossible to search for a variant in exactly the way specified by the user. So, for example, you couldn't search for the surname woods without also getting hits for the singular wood.
By default, both Minion and Lucene store the word forms encountered in the documents in the index, rather than storing (for example) stemmed forms. The difference between the engines is that Minion provides for searching across term variants at query time. By default, Minion
searches for all known morphological variations of the query terms. We generate the variations using a lightweight morphological framework that uses a set of rules similar to the set used by stemmers. The interesting thing about this is that the lightweight morphology is generative, so that given a term we can produce a set of terms that we should try to lookup in the dictionary.
The lightweight morphology tends to overgenerate, but it overgenerates in a lot of the same ways that people tend to. The good thing is that if it generates something that's not really an English word (e.g., I've seen it generate happiless from happiness) then the dictionary lookup will fail and it won't impact the query results.
We currently have lightweight morphological analyzers for English, Spanish, and German (and one for French that we haven't integrated yet!)
This behavior can be modified with the use of the EXACT query operator. Additionally, Minion provides a language-independent stemmer that can be selected at query time using the STEM operator.
By default, Lucene only searches for the form provided in the query, so, for example, a query for dog will exclude documents that only include the plural form dogs. Lucene can be configured to stem the terms as they are added to the index and then stem the query terms, but this leads to the problem described above.
A solution to this is to use the lightweight morphological analyzer to generate the variants and then modify a query to look for any of the variants. In fact, we did this in some of our evaluations of Lucene.
Wednesday Apr 30, 2008
One of the big differences between Minion and Lucene is how they treat case. By default, Lucene's indexing is case insensitive. That is, terms extracted from documents are converted to lower case before being added to the index. The same transformation is performed on query terms, so in its default configuration, you can't ask for documents that have a particular term in a particular case. For example, if you're searching for my last name, Green, you're going to get lots of occurrences of the color green.
In fact, you can make a case sensitive index in Lucene by removing this behavior, but then you can only query for the particular case. So, if you run a query for dog, you won't get the occurrences of Dog that come at the start of a sentence.
While Minion could be configured to have either of these behaviors, by default Minion builds a case sensitive. Terms extracted from documents are stored in the case in which they appeared in the document as well as all lower case.
By default the query behavior is:
- Given a term in all lower case or all upper case, search for the term in any case
- Given a term in mixed case, search for the term in that case.
This behavior can be modified by the use of the CASE operator, which indicates that a term should be looked up in the provided case. You can also configure Minion to do case insensitive lookups no matter what the case of the terms provided in the query.
The above rules also apply to relational operators applied against saved string fields.
All of this case sensitive behavior is supported by a couple of dictionary entry types that support postings for the case sensitive and case insensitive versions of a term. This allows us to do the case insensitive queries nearly as quickly as the case sensitive ones.
Obviously, this requires extra index space to store the duplicated postings, but if you want to constrain the size of the index you can configure the engine to act like Lucene does. Minion provides a default configuration that has this behavior.
Monday Apr 28, 2008
Mark Chu-Carroll at Good Math, Bad Math has a post today describing how a heap works.
Anyways, heaps are a ferociously useful data structure, especially in a search engine. Minion uses heaps in two crucial places.
The first is in the results fetching code. The problem we need to solve is: given a set of documents with associated scores, how do we choose the n documents with the highest scores? The answer is to make a heap with n elements that's organized by the score, with the lowest score at the root of the heap. When considering a document, if the document has a score greater than the score at the root of the heap, we remove the root of the heap and add the new document, since it has a higher score than the document from the top n with the lowest score.
Doing this saves a lot of the comparisons that you would generate sorting a million document return set to find the top 10 documents.
The other crucial place that we use a heap is when merging dictionaries. To merge n dictionaries, we make a heap of iterators for the dictionaries organized by the term from the dictionary that's at the head of the iterator. For a given term, you can poll the heap to get all of the iterators (and therefore all of the dictionaries) that contain that term and combine the information into the new dictionary.
We use heaps in a lot of other places too. In Minion, we use the java.util.PriorityQueue class for our heap, and Netbeans says that we have 90 usages of the PriorityQueue class!
Interesting fact: Mark is a Googler, so I expect he knows how heaps are used in search engines, and it turns out that I knew his wife when I was a grad student.
Monday Apr 28, 2008
Paul's been posting freakomendations, which are "unusual recommendations" (that's a bit of an understatement given your examples, Paul!)
John Scalzi posted that Amazon's recommender suggested that he might like The Last Colony, a book he wrote!
This is not necessarily a freakomendation, because it seems pretty likely that John would read books that the people who read The Last Colony had read, and by that measure the Amazon recommender worked pretty well. But, as you can see from the comments for that postings, doing things like this calls the quality of all of the recommendations into question. This is probably unfair to Amazon's recommender, but that's what you're (which is to say "we're") up against when building recommender systems.
Saturday Apr 26, 2008
Both Minion and Lucene model a document as a number of field/value pairs. Both engines provide ways to index and query the contents of fields, but they differ quite a bit in how the fields may be queried. Because fields are so fundamental to both engines' document models, there's a lot to say about the engines' similarities and differences.
Indexed Fields
Both engines allow for field values to be tokenized and the resulting tokens to be placed into the index for later querying. For example, if the title of a document is Dog bites man, the tokens dog, bites, and man will be placed into the dictionary and searches for these terms will return this document.
One main difference between the engines is that Lucene considers a field in a document to be a "sub-document" to a much greater degree than Minion. When a term occurs in a particular field, Lucene will index it only as part of that field. In our example above, an entry like title:dog will be placed into the dictionary for the term dog. Terms that are not in any defined field will be placed into a default body field.
When querying in Lucene, you can use a query term like title:dog to find documents that have dog in the title field. Terms that do not specify a field are searched for only in the body. In Minion, all of the information associated with the term dog is stored in the dictionary entry for dog. Thus a simple query for dog will find dog in any field of the document. The Minion query language provides a CONTAINS operator that can be used to restrict a query to a particular field.
The advantage for Lucene here is that searches for terms in a particular field will most likely be faster than in Minion, because only a simple postings list must be traversed. In Minion, finding a term in a particular field requires decoding field information in the postings list for the term. The advantage for Minion is that search for a term in all of the fields in a document will most likely be faster than in Lucene, because in that case a single dictionary lookup and postings list traversal is all that is necessary.
Lucene provides an extension class that searches across all fields for a particular term, but it has the (somewhat strange, IMHO) requirement that the term must occur in all fields in a document for it to satisfy the query. Clearly, the Minion behavior could be emulated in Lucene using a disjunction of terms in all of the known fields, but as far as we can tell, this is not done.
Saved Fields
Both engines provide for saving field values as they appear in the documents so that they may be retrieved and displayed to the user at query time. Both offer three "standard" types for their saved fields: String, Date, and Long. Minion additionally offers a Double saved field type.
Minion stores saved field values in a dictionary per field and the names of the entries in the dictionaries are the saved values, and the postings associated with the entries contain the documents that contain that particular field value. This has the advantage that common field values do not take up as much space in the index and it allows for fast computation of common relational queries (such as classification = fast.)
As with all of the dictionaries in a Minion index, the entries in the dictionaries and the associated postings are compressed to save space. Longs, Dates, and Doubles are all stored as 64-bit quantities. This allows us to store any valid Java Long or Double. It also provides for full millisecond resolution for all saved dates, but this full resolution requires some finesse at querying time when a query uses a day-resolution date. Additionally, Minion sometimes encounters difficulty when indexing is done in a different time zone than retrieval.
Lucene stores saved fields in a compressed format, but it uses a string representation for all saved data. In the case of numbers, they are stored using a base 36 representation that allows them to be sorted lexicographically and come out in the correct numerical order. Dates are stored using a variable resolution that is selected at indexing time. As with numbers, they are stored using a representation that allows them to be sorted lexicographically. This resolution selection gets around Minion's day-resolution and time zone problems, but it does mean that dates in the source material may not be represented with the resolution that someone querying the index will require (e.g., if you choose a day-level resolution at indexing time, then you can't query for documents from a particular hour).
Both Minion and Lucene provide relational operators for their saved fields. Lucene offers a range operator for saved field values, which can be used to select documents that have a saved field value in the given range (including or excluding endpoints). Wildcards can be used in the range operator to get something like a substring operator. Lucene doesn't offer a single ended range, but this can be emulated using terms that are known to be less than the smallest term in the index or greater than the largest term (of course, it's up to the application to provide for this capability!)
I must admit to some confusion about how indexed and saved fields interact with tokenization for these range queries. It appears as though one can only use a range operator with a particular word indexed out of a saved field value and not on the saved field values directly. As far as I can tell, the distinction between the saved, tokenized, and indexed attributes is stronger in Minion than it is in Lucene. As with all Lucene searches, these range operators are case insensitive.
Minion offers standard relational operators (e.g., <=, >=, =, etc.) with some support in the query parser for combining operators for the same field into a range. Minion also supports a != operator, which Lucene does not. These operators are available for any saved field type. Minion also offers operators like STARTS, ENDS, SUBSTRING, and MATCHES for string fields. In Minion, relational queries for string fields can be case sensitive or insensitive.
Friday Apr 25, 2008
Jeff and I proposed a talk about Minion for this year's JavaOne. We were accepted as an alternate, but we just got word yesterday that we've been given a slot on the program. It's TS-5027: The Minion Search Engine: Search, Text Similarity And Tag Gardening, which is at 10:50 on Wednesday.
Quoting from the abstract:
Minion is a capable full text search engine that provides integrated boolean, relational and proximity querying. Because Minion was developed as a research engine, it is designed to be highly configurable at runtime so that the user can decide which features and capabilities he needs for a particular job.
In this talk, we'll provide a quick tour of Minion's features as well as feature and performance comparison of Minion and Lucene, a popular open source search engine. We'll show you how to use Minion's API to define what your documents are and how to perform indexing and querying on those documents. We'll use the task of tag gardening to show you how to use the API to perform document similarity and classification operations as well as word sense disambiguation.
People who like the Aura talk also liked the Minion talk! (That's a recommender joke!)
<crickets>
OK. Anyways, if you do come to the talk, please stop by and say hello!
Thursday Apr 24, 2008
A commenter asked if I had any advice about when someone should choose Minion instead of Lucene. When we started the open source process for Minion we took some time to figure out exactly what distinguished Minion from Lucene. We're not by any means Lucene experts, so if we're incorrect in any of our assessments, please let me know. None of what I'm going to say is meant to disparage Lucene: it's a good engine with a great community of developers and users. In an alternate world where Sun opened up a bit earlier, I would have been working on Lucene from the get-go, rather than starting from scratch.
In a fundamental way, the engines are very similar: documents are modeled as a number of field/value pairs, they use inverted files and compressed postings to store their indices, they provide similar query capabilities and they are both extendable. Where the engines differ is in the default capabilities that they provide.
Over the next few days, I'll provide a series of posts explaining what I think the distinguishing characteristics of Minion are, starting with how they treat fields.
Thursday Apr 24, 2008
When we started working on Minion, we decided to take a philosophy that we call EIDAP: Everything Is Dictionary And Postings.
The previous version of the engine had a number of issues (the queries were slower than I would have liked, for example), and while figuring out what needed to be fixed, it was clear that there were several places in the engine where I had developed a sorta-dictionary that had entries that used kinda-postings to store information. This, of course, led to a lot of code duplication with the utterly expected (and annoying) failure mode of having to debug and fix the same problem (or, even worse, similar problems) multiple times.
So, I decided that in Minion (although it wasn't called that yet) we would use the dictionary and postings paradigm wherever we could. This turned out to be a lot of places.
So here's how it works: a dictionary has entries. Each entry has a name and some associated information. Most of the entries encode information about the number of IDs associated with the entry, the size of the postings associated with the entry and the offset (or offsets) in a postings file where those entries might be found, but there's a general mechanism that a particular entry type can use to encode more information, if necessary.
The postings encode information about the IDs that are relevant to that entry. This information may just be the IDs or it might include frequency information or information about the fields in which the entry occurred and the positions where the entry occurred.
If this all sounds a bit generic, that's because it is pretty generic. We use this paradigm for pretty much everything in the engine (remember: EIDAP!) The entry types, the names of the entries, the postings types, and where the postings are written is all configurable at runtime.
Perhaps some concrete examples will help. By default, the "main" dictionary for a partition contains entries whose names are strings. The name of the entry is a term from a document. The postings associated with an entry contain the IDs of the documents that contain that term, the fields in which the term occurs in each document and the positions where the term occurs in each document.
The document dictionary contains entries whose names are strings. The name of an entry is the unique key for a document. The postings associated with an entry contain the IDs of the terms that the document contains and the frequencies of the terms in the document. There may be multiple postings per document, one per vectored field.
A saved field of type INTEGER has a dictionary whose names are integers. The names are the saved values. The postings associated with the entry contain the IDs of the documents that have that value in the field. You can imagine what the dictionaries are like for the other saved types.
We use bigram dictionaries to speed up wildcard processing for querying. A wildcard dictionary has entries whose names are character bigrams. These bigrams are extracted from the terms in an associated dictionary. The postings associated with a bigram entry contain the IDs of the terms containing the bigrams.
A single partition in the index might have more than a dozen dictionaries and associated sets of postings.
Where the EIDAP philosophy really pays off for us is when partitions are merged, which happens all the time in a live index. In the previous version, there were about four different places where we needed to implement merges (come to think of it, they were pretty much the four places that correspond to the examples above!), which meant that debugging a partition merge meant fixing the bug in one place and then looking in all the other places to figure out if the same bug was evident. When everything is a dictionary, a partition merge boils down to merging all of the dictionaries in the partitions, which means we only need to have merge code for dictionaries.
The code for merging dictionaries is fewer than 200 lines, including comments. Admittedly, we use a couple of support classes to do the merge (they're shared with the code that writes the dictionaries in the first place), but the resulting code size is substantially smaller than it was pre-EIDAP.
Wednesday Apr 23, 2008
Paul blogged today about using the search engine to implement a persistent set of strings. He called it abusing the search engine, but it was so simple to do that it seems like more of a use than an abuse, IMHO.
One of Minion's strengths is that it offers a fairly small "public" API that is supposed to offer all of the functionality that you need for indexing and searching documents. Paul's persistent set uses an interface called SimpleIndexer that, as the name suggests, provides a simple way to index documents.
Recall that a document in Minion is just a bunch of fields, so to index using a SimpleIndexer you just do something like:
SearchEngine e = SearchEngineFactory.getSearchEngine(indexDir);
SimpleIndexer si = e.getSimpleIndexer();
to get the a search engine and the simple indexer. Then for each document you want to index you can say:
si.startDocument(key);
si.addField(field1, value1);
si.addField(field2, value2);
...
si.endDocument();
when you're done you need to tell the engine that you're done with the simple indexer so that any information that's accumulated in memory can be flushed to disk:
si.finish();
Don't worry about "indexing too much" with a simple indexer. The engine will flush data to the disk when the heap starts to fill. Also, don't forget to close the engine when you're done with all your indexing:
e.close();
As it stands right now, if you forget to call finish some of the data that you've indexed might be discarded. This is the kind of infelicity that I'm hoping to fix over the next little while. Paul was complaining about having to remember to close the engine yesterday, so we'll probably make that a little easier to deal with as well.
Generally speaking, when Paul complains about the engine I listen. His (constructive!) criticism is the reason that we have SimpleIndexer in the first place.
There are a couple of other ways of indexing documents, but the SimpleIndexer is a remarkably powerful way to index a whole host of things (blogs, email, databases, etc.)
Monday Apr 21, 2008
I'm about to start posting about the internals of Minion. The problem is that it's hard to find a place to start. That is, I'm trying to describe a single part without having to describe all the parts.
In writing a first post about Minion, I find myself making blank blog entries for the things that I need to get to later. So far there are about a dozen. I will attempt in this post to set up some basic terminology that should forgo (I hope!) some confusion. Still, if you encounter something that you don't understand or doesn't make sense, say so in the comments and I'll try to clarify.
Minion indexes documents. Each document is expected to have a unique key. The application doing the indexing is in charge of deciding what the keys are and making sure that distinct documents have distinct keys. A document is composed of fields and values. Although we say that a document is a map from field names to field values, it's actually a multimap. A single field can have multiple values.
Fields can have attributes that specify how the field should be treated during indexing and affect what kind of queries can be asked about the field. The attributes are:
- Tokenized
- The text in the field will be broken into tokens using our universal tokenizer
- Indexed
- The tokens in the field will be added as terms to the main dictionary. When querying, you can query for terms in a particular field.
- Vectored
- The terms in the field will be added to a document vector for this field. These document vectors can be used in document similarity computations as well as classification and clustering operations.
- Saved
- An exact copy of the data in the field is stored in the index. Saved fields must have a type associated with them. We currently support string, numeric (64 bit) and date fields. This data can be queried using parametric query operators (e.g., <, substring) and retrieved for display for a particular search result
Fields can have any combination of these attributes.
Minion indexes documents until a (configurable, of course!) memory limit is reached. At this point an index partition is dumped to the disk. A partition consists of a number of files. When enough partitions of a given size have been dumped to the disk, the partitions are merged into a larger partition. A Minion index that's been in use for quite a while will typically have a couple of large partitions and several smaller partitions (think of a pyramid with the big partitions at the top.)
This approach will be familiar to anyone who has used Lucene.
All indexing is updating in Minion, so if an application indexes a document with a key that already exists in the index, the old information will be removed and the new information will be returned for queries that match the document.
A Minion index can safely be opened, indexed into, and queried by multiple Java threads and multiple Java processes. Minion periodically accesses the index to make sure that it has the most up-to-date set of partitions for querying.
Saturday Apr 19, 2008
I just created a java.net project for Minion. Minion is the name that we (which is to say, Jeff) came up with for the open sourcing of the Sun Labs search engine. The engine we're open sourcing is a substantial revision of the engine that ships with the Portal Server and Web Server.
In the simplest terms, Minion provides an API for indexing and searching documents. Minion has a pretty liberal interpretation of what a document is: a document is a map from field names to field values. If you want to index data, you just have to figure out what the fields are that you want indexed and how they should be treated by the engine. The indexer takes a document as a java.util.Map and adds it to the index. This simple model turns out to be fairly useful for a pretty wide range of things.
As far as querying goes, Minion provides ranked boolean, proximity, and parametric query operators. In addition to the query opertions, Minion provides document similarity operations as well as automatic document classification and document clustering capabilities.
Once the project's officially approved (and we clean things up a wee bit) we'll be putting the source code into the java.net repository.
For the next little while, I'll be blogging about the engine in general as well as the extremely specific.
When it comes to indexing speed, the current versi...
What Daniel said :)
Do you recall what p...
I figured that things would have changed, since th...
svn co lucene/java/trunk/contrib/benchmark and hav...
OK, I'll put that on the list of things to do.
Hi Stephen
I have contacted you via LinkedIn regar...