Zoekindex Lucene verder geoptimaliseerd

Meresco, onze library van search en retrieval software, gebruikt Lucene voor de zoekindex. Lucene is ontwikkeld in Java; onze code is geschreven in Python. Python biedt verschillende mogelijkheden om deze Java code te gebruiken. De open source Software Foundation Apache biedt de mogelijkheid de Java code beschikbaar te maken binnen Python. Dit kan met PyLucene (http://lucene.apache.org/pylucene/).

Opvallend

Tot voor kort maakte we alleen maar gebruik van PyLucene om onze indexen aan te spreken. Op onze software draait continu een monitoring systeem, dat ons inzicht geeft in performance. We merkten steeds vaker dat er geheugen ‘kwijt’ was. Een ander opvallend fenomeen was dat het nodig werd de indexen eens in de zoveel tijd te herstarten, omdat deze anders ‘Out of memory’ gingen. Duidelijk: er was iets aan de hand, en we doken erin. Ondanks veel memory profiling en het bekijken van heap-dumps, die laten zien waaruit het gebruikte geheugen was opgebouwd, kwamen we niet tot een bevredigende conclusie waarom de garbage collector zijn werkt niet goed deed. Java objecten, waarvan wij zagen dat die wel konden worden opgeruimd, werden níet opgeruimd.

Zagen wij iets over het hoofd? Hadden we echt een geheugenlek? Of had de garbage collector te veel te doen om dit binnen de gewenste tijden op te kunnen ruimen?

Aankijken

Ondertussen bleven onze indexen groeien, alsook het aantal queries aan de indexen. Tot we uiteindelijk voor sommige indexen meerdere keren per dag een ‘out of memory error’-melding kregen. Om wat ruimte te scheppen, zetten we het automatisch bijwerken van de indexen daarom uit, en voerden we die handmatig uit op rustige momenten van de dag. Dit gaf voorlopig ruimte, maar dat is geen duurzame oplossing. Tijd voor actie dus.

Actie

Wij hebben een tijdje gebruik gemaakt van het open source enterprise search platform Solr, dat in Java is geschreven. Solr maakt gebruik van de zoekindex-functionaliteit van Lucene, en biedt een http-service aan om queries te stellen. Wat zou er gebeuren als wij ook deze strategie zouden volgen? We zouden Lucene in Java gaan draaien, de ‘native’ taal. Het combineren van garbage in Python en Java komt dan niet meer voor en lost eventuele problemen die we daarmee hebben op. We waren ook heel benieuwd wat er met de performance zou gebeuren.

We schreven onze eigen code om naar Java, bovenop Lucene, en plaatsten er een http-service voor. Na een aantal dagen Java code schrijven, met in het achterhoofd dat het ons zowiezo zou helpen bij het vinden van een oplossing, lukte het ons om weer een werkende versie te krijgen.

Performance testen

De code installeerden we op een acceptatie server met veel data. De eerste testresultaten waren erg bemoedigend. Ze gaven aan dat de indexen zelfs meer dan dubbel zo snel waren geworden. Dat was een beter resultaat dan we verwacht hadden. Maar de grote vraag: is ons geheugenprobleem opgelost, was nog niet beantwoord. We lieten daarom een duurtest los op de oplossing. We bestookten het systeem urenlang met een continue load, waarvan we wisten dat het oude systeem daar al snel onder zou bezwijken. En jawel: er kwamen geen geheugenproblemen meer voor.

Gemiddelde responstijden voor en na release op 16 december

Gemiddelde responstijden voor en na release (op 16 december 2015)

In de roos

Het leek er sterk op dat we ons probleem opgelost hadden. Ons vermoeden dat het in puur Java beter zou moeten gaan, klopte. Als klap op de vuurpijl kregen we er ook nog een enorme performance verbetering bij.

Uiteindelijk hebben we deze aanpak een tijdje laten meedraaien op de acceptatie-omgeving om er zeker van te zijn dat de werking probleemloos was. Intussen is het alweer een tijdje gereleased naar een productie omgeving, waar het nu vlekkeloos draait.

 

A Faster Join for Solr/Lucene

Reducing Index Maintenance Costs with Join.

The previous post introduced the reasons why we want blazingly fast join functionality in Lucene: reduction of index maintenance costs.

This post details how we improved the speed of Lucene’s Query-Time Join a thousandfold.  We achieved this by looking at usage patterns instead of looking at the technology. Lucene’s default Join is a truly Lucene way of performing Joins between arbitrary terms in arbitrary fields in two indexes. Our Join more or less turns a Lucene index into a relational table and provides Join functionality as you would expect from a relational database.  That might sound restrictive to Lucene-adepts, but it offers unprecedented possibilities.

Keys, keys, keys

Lucene joins indexes based on terms. Our first observation is that these terms in fact play the role of keys. In database-lingo you would call them primary or foreign keys. Nowadays, most people use either UUIDs or URIs to identify things, but these are hard to deal with: they occupy much space, are expensive to compare and do not compress well.  Data management software internally always translates long, text based identifiers to small integers. (As a matter of fact, Lucene also uses them and calls them docid and ord.) Our Join implementation is based on such small monotonically increasing numbers and we call them keys.

Multiple Values

The second observation is that lucene supports join on fields that contain multiple values for one document.  But key cells in databases always contain exactly one value for each row.  If you need multiple values, you’d create a separate table containing multiple entries containing the same (foreign) key and then… join it.  Since join is a database concept after all, we might want to consider to be consequent and use single valued fields exclusively. If we need multiple values, we’ll create a separate index and then… join it!  So in our Join implementation, every document in a Lucene index gets one and only one (non-unique though) key.   This is not restricting you as long as you are prepared to adapt your data model.  Read on.

Performance

The performance gain of using small integers over strings is tremendous.  Small integers use significantly less memory and can be fetched, stored and compared with a single machine instruction. Having only single values (one key) per field per document means they can be organized efficiently in one-dimensional arrays or bitsets.  Much research in the domain of Information Retrieval deals with fast storage and intersection of these arrays and bitsets, and much of the research results are available in Lucene! It works marvelous with our keys.

Translate Identifiers to Single Valued Keys

So how do we go about translating string identifiers to numeric keys?  The implementation of this is downright easy in Lucene if you use the new Taxonomy functionality.  The taxonomy is a proper dictionary, mapping every term onto a small number: the key.  Lucene can store this key very efficiently using the relatively new NumericDocValuesField feature. During indexing, we use it like this to store a key in field key (pseudo-code):

TaxonomyWriter keysDict = new DirectoryTaxonomyWriter(...);
Document doc = new Document();
long key = keyDict.addCategory(new CategoryPath());
doc.add(new NumericDocValuesField("key", key));
indexWriter_A.addDocument(doc);

It is essential that one uses the same TaxonomyWriter for every index so that identifiers in all indexes get mapped onto the same keys.

(A completely different way of creating keys is using another database’s key generation mechanism.  Virtuoso for example exposes its IRI_TO_ID and ID_TO_IRI functions.  Using these to obtain keys gives the opportunity to Join between Lucene and Virtuoso.  Expect a blog about that!)

Create Single Valued Keys

The problem of having single valued keys may require changes to the data model. In our case we had the denormalized form in one index:

id:<uri_1>  title:"The Hobbit"  location:<loc_1>,<loc_2>, ...

We split this into two indexes:

id:<uri_1>  title:"The Hobbit"

and:

id:<uri_1>  location:<loc_1>
id:<uri_1>  location:<loc_2>

Querying

Now we have two or more indexes in which the terms we wish to use for joining are replaced by keys.  We can now join these indexes during queries by specifying which fields to use for joining. To keep things simple, we assume that one index A simply filters the results from another index B.  In practise things are (much) more complicated; too complicated for a blog.

Expressing Join

For join to really work well, we will need a query language that supports join. The query language built into Lucene offers no support for this, but luckily we can do without.  There is another language that does support joins and that is the language consisting of Java classes centered around Query, Filter and Collector.

Collecting Terms… eh Keys

The first step is to collect the keys for the terms we want to match between indexes. This step is straight forward (if you leave out caching and all the devious Java markup, it is just two lines of useful code.).  We created a Collector that for each hit, looks up the key and stores it into a bitset.  It needs to know the name of the field containing the key. Use it as follows:

KeyCollector keyCollector = new KeyCollector("key");
indexSearcher_A.search(<query_a>, keyCollector);

Filtering Terms… eh Keys

The second step is to ask the KeyCollector for a KeyFilter to be used in another index. The filter is also not too complicated if you leave out caching and Java markup. It needs to know the name of the field containing the key.  Use it as follows:

KeyFilter keyFilter = keyCollector.getFilter("otherKey");
TopDocs results = indexSearcher_B.search(<query_b>, keyFilter);

Done. Now the results in index B are filtered based on a query on index A.  And it is fast, blazingly fast, thanks to Lucene’s excellent DocValues and Collector APIs.

But it needs to be faster, even more

Although this duo of KeyCollector and KeyFilter improve the speed of Lucene’s built-in Join with a factor 50 or so, it is not fast enough.  It would get the raw processing time for our 8-second query down to 160 ms, but that is still too much. You’ll need to add all kinds of post-processing to this 160 ms and then you’ll end up way to close to 1s. Any raw processing time not substantially under 100 ms makes me personally very nervous. It would require many machines to deal with the loads we have.

Caching

With caching, we can get the processing times down by a factor 20, leaving a mere 8 ms. That yields a total 1000-fold speedup compared to where we started.

How that is achieved might be the subject of the next blog. But you might peek at Meresco’s Lucene code at GitHub.

Conclusion

By making some observations about the nature of joins and by making a firm decision to follow the relational interpretation of join and by assuming that anything is still possible by adapting your data model, we managed to speed up joins 1000-fold.

The result is completely orthogonal to other Lucene functionality such as faceting, sorting, scoring, filtering, etc. All intermediate steps and results are in the hands of the programmer.

The results are about to go in production (March) on a Dutch national library search engine, joining 12.000.000+ titles with 25.000.000+ holdings. The contribution of join to the query response times are deep down on the list of bottlenecks: a few ms.

Reducing Index Maintenance Costs with Query-Time Join for Solr/Lucene

Index Maintenance: Cheaper and Better

Last year Seecr has been on a quest to make maintenance of large integrated search engines easier, cheaper and at the same time better.

We achieved that goal by reorganizing the indexing process and applying a technique called Late Integration.  We created an exciting extension for the Solr/Lucene search engine to make that possible.

In a series of blogs, we will present the problem, the solution and the code. This completes our previous series of blogs about the Open Index: Late IntegrationQuery Resolving and how to find relevant indexes.

Relations and Denormalization

Traditionally (that is, during the last decade), integrated search meant collecting data from various sources and integrating it in an central search engine. This approach works well but runs into problems when the data sets become larger and more divers. And what finally kills this approach is the presence of 1:n relations between data sets.

Traditional databases and triple stores deal with relations explicitly and provide query languages (SQL and SPARQL) that incorporate the notion of relations. With Lucene, the predominant approach is to de-normalize the data in order to create one big index. This denormalization is what becomes the bottleneck when the index grows.

Denormalizing: The Problem

Suppose you have a corporate catalogue of product descriptions and each local branch maintains a database, linking to this central catalogue, adding information about the local stock, price, promotions, reservation, et cetera.  Providing Solr/Lucene-based search functionality spanning both the central catalogue as well as the local database would require both data sources to be de-normalized.  Doing so runs into a few problems:

  1. The 1-N nature of the relationship yields an explosion of data. That’s the nature of denormalization. The most prominent example I know of is the travel agency that maintained one index with over 109 trips, resulting from heavy denormalizing destinations, hotels, dates, lengths and features like dog admittance and smoking rooms.
  2. Both sources have their own update cycle (life cycle). Some data might be constantly updated, for example room availability, while other data is rather stable, such as room descriptions. Feeding both into the same update cycle often limits the update rate of more volatile data.
  3. Both sources require their own specific expertise. The extraction of the data out of its original environment poses a problem: away from the experts that know it by heart and into the centrally managed domain of the generalists.

It would be so much nicer to have separate indexes: one for the corporate catalogue and one for the local stock.  Each update in local stock would require just one simple update in the stock index, just as one item update in the catalogue requires only one update in the catalogue index. So, an catalogue item update need not to go through the denormalize process, avoiding the forced update of all local stock related to this item.

Having separate indexes makes it almost trivial to differentiate the calculation of fields (tokenization, ranking, normalization etc) per index. Also, the update rate can vary easily between indexes, simply because they are independent.

If we only could join the indexes during query time…

Relations in Lucene: Join

If we could bring the notion of relations to Lucene, and we are able to efficiently query along relations, we could avoid denormalization, making the indexing process easier while at the same time creating opportunities to have more specialized indexing when needed.

What is Join?

The idea of joins stems from relational databases (RDBMS) and the structured query language (SQL).  The main idea is to normalize the data into separate tables, and to re-combine these tables during queries. Queries express relations between those tables and data is recombined based on the relations.  This is called joining.

The same idea is present in RDF triple stores. The Sparql query language allows queries to span multiple relations between concepts. The actual join however is much more natural: it happens implicitly because of the notion of everything being a relation, even individual properties.

Lucene Join

Coincidentally, last years, Solr/Lucene has seen the addition of functionality for joining. This allows one to indicate a specific field in one index, and one specific field in another index, and Lucene would then join documents from both indexes if and when they contain the same value in the indicated fields. But since it is not fast enough, we had to rethink and redesign it for us to work. We needed it to be as fast as any other query in Lucene. So we made it that way.

Speed?

In Solr/Lucene a special utility helps an application programmer to create a query that under the hood collects terms in one index and filters on these terms in another. Using this utility (JoinUtil.createJoinQuery) we run a typical query on our indexes: one containing 12,000,000+ book titles and one containing 25,000,000+ individual books held by libraries in the Netherlands.  The question is: for a certain selection, which books are present at a certain library or group of libraries?

This query took 8679 ms to execute.

Regardless of hardware, this is too much. Way too much, as each and every query will come with such a filter.  We need it down to 8 ms. That is our target.

A 1000 times faster

The reasons Lucene’s Join is not fast enough lays in the generic nature of it’s approach. It works on terms: strings of random length. It builds sets of terms and makes intersections or unions of them.  However, for computers, dealing with strings is expensive. They take a lot of memory, and comparison is slow, especially if almost every string is an URI, with long common prefixes. Secondly, the intersections and unions are made by scanning the terms of an index, which is a slow process.

But Lucene is open source, is rather well though-about, and has healthy discussions between experts.  So we started reading and we improved the speed of joining by doing the following:

  1. Translate terms (strings) into numbers. This will speed up the creation of sets as well as taking the intersection.
  2. Closely follow the Lucene segmenting architecture to exploit caching per segment on a lowest possible level.

We set out to do so and learned a lot about Lucene and joining algorithms!

Results

We were very surprised by the results: joining has become so fast, it is now a non-issue for us. This means we can use it whenever we decide that maintaining a separate index is beneficial, without worrying about the performance loss of queries.

Exactly how we did it will be the subject of a following, more technical, blog post.

In the next post, we will outline our approach, with real working code, and show how join can be combined orthogonally with other Lucene functionality. At the end, we will contribute this code to the marvellous Lucene-community.

Autocomplete met Solr

Autocomplete is een functie die al langere tijd beschikbaar is in de systemen die met Meresco gebouwd worden, maar bij Seecr en haar opdrachtgever Kennisnet bestond de behoefte aan een duidelijk overzicht van de verschillende methodes voor een autocomplete functie.

Meresco levert die functies via Solr. Op de Meresco blog analyseert Hendrik vier methodes van autocomplete die door Solr 4.0 worden aangeboden.

Autocomplete met Solr (Dutch)

Autocomplete is een functie die al langere tijd beschikbaar is in de systemen die met Meresco gebouwd worden, maar bij Seecr en haar opdrachtgever Kennisnet bestond de behoefte aan een duidelijk overzicht van de verschillende methodes voor een autocomplete functie.

Meresco levert die functies via Solr. Hieronder analyseren we vier methodes van autocomplete die door Solr 4.0 worden aangeboden op basis van de volgende criteria.

De methode:

  1. geeft aanvulling op velden met één waarde (bijvoorbeeld: datum=01052013) of met meerdere waarden (bijvoorbeeld: tags=leuk, spannend).
  2. kan achteraan , maar ook vooraan of middenin aanvullen: “auto”, “mobiel” en “autobiel” leveren “automobiel” op.
  3. geeft aanvullingen binnen een zoekresultaat (bijvoorbeeld: aanvulling binnen het resultaat van de vorige zoekvraag) of op de gehele index.
  4. geeft (exacte) aantallen voor de te verwachten resultaten.
  5. kan snel aanvullen uit een lijst met zeer veel verschillende waarden (>100.000).
  6. werkt op een standaard index, of op een apart te bouwen index.

De vier methodes voor autocomplete in Solr (en Meresco) werken op basis van:

  1. De Facet-functie
  2. Alle Termen in de Index
  3. De Suggester Component
  4. Een N-Grammen Index

De Facet-functie
Met behulp van de standaard facet-functie kunnen alleen achteraan aanvullingen gegenereerd worden. Dit werkt erg efficiënt, ook binnen zoekresultaten. Het mooie er van is dat bij elke term het te verwachten aantal resultaten getoond kan worden. Met erg veel termen wordt het echter wel trager.

Voordelen:
–       Geeft aanvullingen in velden met meerdere waarden.
–       Geeft aanvullingen binnen een zoekresultaat.
–       Geeft exacte aantallen voor de te verwachten resultaten.
–       Te gebruiken met een standaard index.

Nadelen:
–       Kan alleen achteraan aanvullen.
–       Wordt minder snel bij zeer veel verschillende waarden.

Alle Termen in de Index
Deze methode geeft aanvullingen op basis van alle geïndexeerde waarden in een index. Het ondersteunt aanvullen achteraan, vooraan en middenin. Maar alleen achteraan werkt snel, ook bij zeer veel waarden in de index.

Voordelen:
–       Geeft aanvullingen in velden met meerdere waarden.
–       Kan achteraan, vooraan en middenin aanvullen.
–       Te gebruiken met een standaard index.
–       Werkt efficiënt met zeer veel verschillende waarden.

Nadelen:
–       Vooraan en middenin aanvullen werkt niet efficiënt.
–       Alleen een benadering van het aantal te verwachten resultaten.
–       Kan geen aanvullingen geven binnen een zoekresultaat.

De Suggester Component
Via de Suggester component kan een aanvulling gedaan worden door het aan te vullen woord te zien als woord waarvoor spellingscontrole gedaan moet worden. Dit werkt efficiënt voor aanvulling achteraan, vooraan en middenin door middel van een speciale index. Het mooie van deze oplossing is dat er verschillende algoritmen kunnen worden gekozen om de aanvulling te produceren.

Voordelen:
–       Geeft aanvullingen in velden met meerdere waarden.
–       Kan achteraan, vooraan en middenin aanvullen.
–       Werkt efficiënt met zeer veel verschillende waarden.

Nadelen:
–       Kan geen aanvullingen geven binnen een zoekresultaat.
–       Geen informatie over het aantal te verwachten resultaten.
–       Er moet een speciale index (tree) voor onderhouden worden.

Een N-Grammen Index
Deze oplossing wijkt sterk af van de andere. De aanvullingen gaan op basis van een query op een speciale index van delen van woorden. Het woord “snel” wordt hierin geïndexeerd als “sn”, “ne” en “el”. Omdat dit een normale zoekopdracht is, geeft dit geen aanvullingen terug, maar moet dit gecombineerd worden met de facet-functie of het ophalen van opgeslagen waarden. Het mooie aan deze oplossing is dat het gemakkelijk uitgebreid kan worden met speciale spellingcheckers of fonetische suggesties.

Voordelen:
– Kan achteraan, vooraan en middenin aanvullen.
– Geeft exacte aantallen voor de te verwachten resultaten in combinatie met de facet-functie.
– Werkt binnen een zoekresultaat.
– Werkt efficiënt met zeer veel verschillende termen.

Nadelen:
– Niet geschikt voor velden met meerdere waarden.
– Er moet een speciale n-gram index voor worden opgebouwd.

Samenvatting
In onderstaande tabel worden de voor en nadelen naast elkaar gezet. Daaruit is duidelijk op te maken dat de verschillende methodes heel verschillend scoren op onze criteria.

  Facet-functie Termen Suggester N-Grammen
Meerdere waarden per veld

+

+

+

Achteraan

Vooraan

Middenin

+

+

+/-

+/-

+

+

+

+

+

+

Binnen een zoekresultaat

+

+

Exacte aantallen

+

+

Veel verschillende waarden

+

+

+

Index

standaard

standaard

tree

n-gram

Conclusie
Uit de resultaten komt naar voren dat voor een bepaalde toepassing een specifieke methode beter werkt dan andere. In twee gevallen is er ook een speciale index nodig om het goed, en efficiënt, te laten werken. Het kiezen van de juiste autocomplete methode is daarom dus een zaak van grondige analyse van de wensen.