Grid Designer's Blog

Block Join Faceting: Implementation

2016-03-01T09:41:00.000-08:00

To view an updated version of this post click here

In previous post, we’ve been talking about business motivation behind support of structured documents in Solr/Lucene index and unique requirements to faceting engine which is created by such approach to modeling data. We introduced SOLR-5743 and now it is time to take a deep dive into implementation details.

First, let us recap how Solr deals with structured data. Solr supports search of hierarchical documents using Block Join Query (BJQ). Using this query requires special way of indexing documents. BJQ relies on special positioning of the documents in the index: all documents belonging to same hierarchy have to be indexed together, starting from child documents followed by their parent document. BJQ works as a bridge between levels of document hierarchy, e.g. it transforms matches on child documents to the matches on parent documents. When we search using BJQ, we provide a child query and a parent filter as a parameters. Child query represents what we are looking for among child documents, and parent filter tells BJQ how to distinguish parent documents from child documents in the index. For each matched child document, BJQ scans ahead in the index until it finds nearest parent document, which is sent into collector chain instead of child document. This trick of relying on relative document positioning in the index, or “index-time join”, is a secret behind high performance of BJQ.

Now, we are ready to look into faceting of BJQ results. We will use example of eCommerce catalog with Product-SKU parent-child relationship as modeling example.

Main idea is quite straightforward. We consider each hierarchy of matched documents separately. As we are using BJQ, each hierarchy is represented in the index as a document block, or DocSet Slice as we call it.

First, we calculate facets based on matched SKUs from our block. Then, we aggregate obtained SKU counts into Product-level facet counts increasing product level facet count by only 1 for every matched block, irrespective to number of matched SKUs within the block. For example, if we are searching by COLOR:Blue, even though two Blue SKU were found within a block, aggregated Product-level counts will be increased only by 1.

This solution is implemented inside BlockJoinFacetComponent which extends standard Solr SearchComponent. BlockJoinFacetComponent validates the query and injects special BlockJoinFacetCollector into Solr post-filter collectors chain. When BlockJoinFacetCollector is invoked, it receives a parent document, since the BlockJoinFacetComponent ensures that only ToParentBlockJoinQuery is allowed as a top level query.

Now, to adjust facet counts based on this parent, we need to identify the children documents which matched within the current block. To do that we request BlockJoinScorer to trackPendingChildHits() and to swapChildDocs(). Our next step is to calculate facets on the obtained doc slice. Initially, we just invoked standard faceting routine e.g. employed DocValuesFacet.getCounts() providing it DocSet representing matched child documents from current index block. Finally, facet counts calculated on slice, were aggregated into global ones counting multiple hits on the child documents as one hit on parent document.

We developed randomized test case BlockJoinFacetRandomTest to ensure functional correctness of this implementation. This test checks facet calculation with different combinations of Products, SKUs and random filters.

Also, BlockJoinFacetComponent was extended to work with Solr Cloud, and supplied with BlockJoinFacetDistribTest as well.

All looked good except one issue: faceting was relatively slow.

Profiling showed that utility DocValuesFacet.getCounts() was developed with assumption that it should be called only once for each particular field. However, with BlockJoinFacetComponent we invoked this method for each matched parent document. As a result, lots of work was unnecessary repeated many times, such as: determining field type, allocating in-memory objects, determining top and segment SortedSetDocValues, migration from segment facet counts to global ones. Thus, the first step of performance optimization was the introduction of BlockJoinFieldFacetAccumulator which is responsible for accumulating facet counts for particular field. It performs all mentioned tasks during initialization or switching to next index reader. Those improvements showed 25 x performance gain in local benchmarks.

Next improvement was inspired by Reverse Nested Aggregation Elastic Search solution. Suppose, we need to calculate facets for some DocValues field. For each segment we know SortedSetDocValues of this field, which contains unique values of this field. For each of those values, we need to track a facet count, where each term has corresponding long value positioned in the parallel array of facet counters. Here we use another trick to save memory and ensure CPU cache locality: each long value in our facet counter array combines aggregated (parent-level) facet count for particular term (highest 4 bytes) and position of most recently matched parent document which has a block with hit for this term (lowest 4 bytes).

When BlockJoinFieldFacetAccumulator is requested to update facet counts with particular parent document and an array of matched child documents, we:

iterate over matched children documents;
for each child document we identify terms contained in the document
for each term we find corresponding array entry long and check if its encoded parent position matches provided parent document. If it matches this mean that we have duplicated hit within same block, so we just ignore it and proceed with iteration over terms. If positions do not match, we have a first hit in a new block and and encoded long value is updated to increment facet value counter and update last seen parent position.

Thus, when all matched parent documents are processed, higher halves of the long values in accumulator array will contain required facet counts. This optimization delivered 2x performance boost.

Third optimization was suggested by Mikhail Khludnev. He proposed to calculate doc slice as an intersection of all matched child documents with all children of the current parent document. This approach is implemented as separate BlockJoinDocSetFacetComponent. On local benchmark it’s faster than BlockJoinFacetComponent by 40%, but we believe that exact circumstances in which one component is better than another require further analysis. We recommend to experiment with macro benchmarks using both implementations.

Components described in this blog post are committed into Solr codebase with SOLR-5743 in December 2015 and are available since Solr 5.5. Corresponding documentation is available at Solr Wiki . In order to utilize one of the BJQ faceting components, you need to configure them in solrconfig.xml and introduce appropriate search handlers, for example

<searchComponent name="blockJoinFacet"

class="org.apache.solr.search.join.BlockJoinFacetComponent"/>

<str name="shards.qt">blockJoinFacetRH</str>

</lst>

<str>blockJoinFacet</str>

</arr>

</requestHandler>

<searchComponent name="blockJoinDocSetFacet"

class="org.apache.solr.search.join.BlockJoinDocSetFacetComponent"/>

<requestHandler name="/blockJoinDocSetFacetRH"

class="org.apache.solr.handler.component.SearchHandler">

<str name="shards.qt">blockJoinDocSetFacetRH</str>

</lst>

<str>blockJoinDocSetFacet</str>

</arr>

</requestHandler>

Since only docValues fields could be used for BJQ faceting, you need to update corresponding fields configuration in schema.xml file, for example

<field name="COLOR_s" type="string" indexed="true"

stored="true" docValues="true"/>

<field name="SIZE_s" type="string" indexed="true"

stored="true" docValues="true"/>

Then, after indexing some set of hierarchical documents like

<doc>

<field name="type_s">parent</field>

<doc>

<field name="type_s">child</field>

</doc>

<doc>

<field name="type_s">child</field>

</doc>

you need to pass required ToParentBlockJoinQuery to the configured request handler and request calculating facets using child.facet.field parameter, for example:

http://localhost:8983/solr/collection1/blockJoinFacetRH?q={!parent+which%3D%22type_s%3Aparent%22}type_s%3Achild&wt=json&indent=true&facet=true&child.facet.field=COLOR_s&child.facet.field=SIZE_s

If everything is configured correctly, then Solr response should look like

{
"responseHeader":{
   "status":0,
   "QTime":82},
"response":{"numFound":1,"start":0,"docs":[
     {
       "id":"10",
       "type_s":["parent"],
       "BRAND_s":["Nike"],
       "_version_":1526159505694392320}]
},
"facet_counts":{
   "facet_queries":{},
   "facet_fields":{
     "COLOR_s":[
       "Blue",1,
       "Red",1],
     "SIZE_s":[
       "XL",1]},
   "facet_dates":{},
   "facet_ranges":{},
   "facet_intervals":{},
   "facet_heatmaps":{}}}

You may also consider an alternative way for calculating facets on hierarchical product structures. Solr JSON Facet API introduced by Yonik Seeley allows to solve the same task in a bit different way. This is a new and really powerful feature appeared in Solr 5.4. It provides very flexible way to control the facets to be calculated. Particularly, it’s possible to calculate facets on child documents with aggregation by unique _root_ field. For example, for request:

curl http://localhost:8983/solr/collection1/query -d 'q=(type_s:child)&rows=0&

json.facet={

colors:{

type : terms,

field : COLOR_s,

facet: {

productsCount: "unique(_root_)"

}

sizes:{

type : terms,

field : SIZE_s,

facet: {

productsCount: "unique(_root_)"

}

Solr returns response that contains expected counts (check productCount field):

"facets":{

"count":2,

"colors":{

"buckets":[{

"val":"Blue",

"count":1,

"productsCount":1},

{

"val":"Red",

"count":1,

"productsCount":1}]},

"sizes":{

"buckets":[{

"val":"XL",

"count":2,

"productsCount":1}]}}

This way has obvious advantages: it’s easier to programmatically control which facets are to be calculated, how they should be presented in response, include statistic, nested facet commands etc. The drawback here is that search query in above example, i.e. q=(type_s:child), yields child documents, while facets are calculated on parent ones. i.e. to present parent documents both in search results and in calculated facets, we need to execute 2 separate requests. Another reason to choose one of the BlockJoinFacetComponents is much better performance. On my local test data BlockJoinDocSetFacetComponent is about twice faster than JSON Facet API.

BlockJoinFacetComponent can be further improved by replacing iteration over matched child documents with bitwise operations over whole DocSets. Main idea here is to be able to obtain for each term a DocSet of matched parents with particular term in child documents. In this case, facet count of the term should correspond to the size of this DocSet.

Happy (block) faceting!

Block Join Faceting: Introduction

2016-02-27T17:01:00.000-08:00

To see an updated version of this post click here

Every software application is created to bring business value. Typically, software development process starts from understanding business requirements and creating a domain model. Such a model is very helpful in communication with business stakeholders and allows to clearly understand their needs and restrictions. Additionally, simple and flexible domain model is a strong basis for creating effective and extensible software architecture that meets customer’s requirements.

Normally, business modeling starts with identifying entities and relationships between them. Relationships could be association or composition, and have different cardinalities, e.g. one-to-one, one-to-many and many-to-many relationships. Relationships are so important, that they are first class citizens in the relational databases and majority of data related specifications and frameworks like JPA or Hibernate.

However, when we deal with search engines like Solr, we see that domain models readily supported by framework are quite simple. Each entity is represented as a document with some set of fields. That's it. It looks like Solr makes only basic steps in supporting all the variety of possible relationships between indexed documents, leaving the rest to application developer.

At the same time, for some business areas support of relationships is very important. In particular, such relationships introduce new challenges to the problem of facets calculation. As a example, lets consider e-commerce platforms where each Product in catalog has several so-called Stock Keeping Units (SKU). Each SKU defines a different flavor of the same item. Even though customers are purchasing SKUs, e.g. concrete flavor of the product, typical e-commerce business merchandizes in terms of the product.

Screenshot above is taken from one of the online retailers. As we can see, a dress could be in blue, pink or red colors, and for a blue color dress, only sizes XS and S are available. However, for merchandizer and for a customers it’s just a single product. So, when customer navigates the site, she should see all SKUs belonging to the same product as a single product. This means that for facet calculation, our facet counts should represent products, not SKUs. Thus, we need to find some approach to aggregate SKU-level facets into product ones.

Pretty common solution here is to propagate properties from SKU level to product level and produce single product document with multivalued fields aggregated from SKU. With this approach, our aggregated product will look as follows:

However, this approach creates possibility for false positive matches with regards to combinations of SKU-level fields. For example, if customer will filter by color ‘Blue’ and size ‘M’, Product_1 will be considered a valid match, even though there is no SKU in original catalog which is both 'Blue' and 'M'. This happens because when we are aggregating values from SKU level, we are loosing information about what value comes from what SKU. Even though this situation looks like an edge case, in real life application it can cause really bad customer experience. Imagine the situation when customer searched for particular item filtering by colors and sizes only to discover on checkout pages that there is no such item available in the catalog. This really frustrates customers and negatively impact customer loyalty. Not good for the business.

Getting back to technology, this means that we should carefully support catalog structure when searching and faceting products. The problem of searching structured data is already addressed in Solr with powerful, high performance and robust solution: Block Join Query. We wrote about this approach in this blog extensively.
However, problem of faceting structured data required further work. So, we created SOLR-5743 in February 2014 and worked on it ever since. Now, we are happy to report that first robust and high performance implementation is committed to trunk.
We will describe new BJQ faceting component and related algorythms in our next blog post. Stay tuned and happy faceting!

Block Join Faceting in Solr and other..

2016-01-20T11:21:00.000-08:00

To see an updated version of this post click here

I recently had a nice flight with onboard entertainment. It was quite well, but look at the film menu navigation! It definitely lacks an ability to nest different languages into the movie item and facet based on the movie languages. As a result, it wastes screen space and forces user to unnecessarily scroll titles again and again. Faceted navigation on nested items is one of our favorite topics when it comes to search experience.

It reminds me that block join facet functionality mentioned in earlier post was recently committed under SOLR-5743 and will be available since Solr 5.5. So, it can be found in snapshots of 5.5 and 6.0. Please check Solr Reference guide for the detailed description and sample request.

It’s worth to mention that this functionality is known as reverse nested aggregation in Elastic (Thanks to Andrey Kudryavtsev for the finding), and also it's can be achieved as unique(ID) aggregation in JSON Facets (this solution was suggested by Alessandro Benedetti). Nethertheless, I suppose dedicated components might be more convenient for users, but in future I prefer to merge them into JSON Facets framework.

Automatic Speech Recognition Services Comparison

2016-01-11T01:41:00.000-08:00

Automatic Speech Recognition Services Comparison

Introduction

“Ok Google, find me a red dress.” Your long-time customer has just been invited to an important party this evening and wants to make a good impression. She’s on her way to your store right now and can’t spend any time typing in searches while she drives. Instead of saying, “Ok, Google…” wouldn’t you rather she said, “Ok, MyFavoriteStore name?”

Both Apple and Google have done a good job educating users on the value and ease of voice-controlled features. So how mature is commercial speech recognition today? As Grid Dynamics has extensive experience in eCommerce and search solutions, we decided to take a look at the current speech recognition technologies available for voice search implementation. In this article we will share the results from our experiment - comparing the quality of different speech recognition providers.

Services

Before the Experiment was started, our team reviewed multiple providers of automatic speech recognition. We have used the following criteria for selection of the service to evaluate:

Unified, cross-platform interface. It means service availability via HTTP REST interface

Speech recognition quality “out of the box” without any tuning for particular customer

Free (or low price) for initial testing of service
Speech recognition provided as a SaaS

We compared the following services.

Google

Google

Google Speech API is not “production” ready.

Experimental status can change API at any time
No official API documentation or usage capabilities
Limitations of approximately 500 requests per day, per account
You need to join Chromium-dev mail group and generate appropriate key in Google developer console

Example of API usage:

curl -X POST \

--header 'Content-Type: audio/x-flac; rate=44100;' \

--data-binary @red_dress.flac \

'https://www.google.com/speech-api/v2/recognize?lang=en-us&key=<KEY>'

Nuance

Nuance speech recognition REST API features:

Registration is required
Account upgrade from Silver- to Gold-level offered for free
Usage limitations of 5,000 requests per day

Example of API usage:

curl -X POST \

--header "Content-Type: audio/x-wav;codec=pcm;bit=16;rate=16000" \

--header "Accept: application/xml" \

--header "Accept-Topic: Dictation" \

--data-binary @red_dress.wav \

"https://dictation.nuancemobility.net:443/NMDPAsrCmdServlet/dictation?appId=<APP_ID>&appKey=<APP_KEY>"

AT&T

AT&T speech recognition REST API features:

Registration is required
Required “Premium Access” payment is $99/year + Usage fees to access automatic speech recognition

AT&T REST API uses OAuth 2.0 for authorization
According to documentation usage limitations is 1 request per second

Example of API usage:

curl -X POST \

--header "Authorization: Bearer <TOKEN>" \

--header "Content-Type: audio/x-wav" \

--data-binary "@red_dress.wav" \

"https://api.att.com/speech/v3/speechToText"

WIT

WIT is more about NLP (Natural Language Processing) than about plain-speech recognition.

Main focus, besides speech recognition, is to parse out spoken phrases and extract valuable information (e.g., some voice command). The goal is to have the system “understand” voice. For example, play “Jingle Bells” when the user says, “Hi, robot! Please play me Christmas songs.”
Github account is all that is needed to access WIT REST API
No account usage limitation

Example of API usage:

curl -X POST \

--header "Authorization: Bearer <TOKEN>" \

--header "Content-Type: audio/wav" \

--data-binary "@red_dress.wav" \

"https://api.wit.ai/speech?v=20141022"

IBM Watson

IBM Speech recognition REST API features:

Public API was released to the public in early 2015

Registration in Bluemix is required
Usage limitations of 150,000 requests per month

Example of API usage:

curl -X POST \

--header "Content-Type: audio/flac" \

--user <USERNAME>:<PASSWORD> \

--data-binary "@red_dress.flac" \

"https://stream.watsonplatform.net/speech-to-text/api/v1/recognize"

Experiment

To compare quality of speech recognition, you first need a recorded voice. As we worked on voice search features for eCommerce, we recorded eCommerce-like search phrases. We used short phrases such as: brand names, colors, sizes, etc. Here’s a sample of the phases used - “red dress,” “Calvin Klein jeans” and “xl coat.” We leveraged over 3,000 different phrases for this experiment and compared different conditions like gender, age and background noise (I.e., with or without noise), as well as other criteria.

We used the following sequence for experiment purposes.

Delivered an audio file with recorded search phrases to external services
Received recognized text from automatic speech recognition service
Evaluated quality metrics of recognized text vs. actual search phrase

We used multiple quality metrics, such as:

Volume of exact recognized phrases

Simple, but a paramount quality metric
Larger number of exact recognized phrases, the better quality of speech recognition results

Word Error Rate (WER)

Minimum number of words edits (I.e., insertions, deletions or substitutions) required to change one phrase into the other
Normalized by phrase length (basically leveraging Levenshtein distance between two phrases working at the word level, instead of the phenomenal level)
Fewer number of required edits, which meant that the phrases are more like each other - offering the best quality of speech recognition

Comparison Results

The quality champion is Google. We didn’t reproduce the declared by Google 8% WER with our Grid Dynamics’ data, but the results are still impressive. Google achieved 73.3% of exact recognized phrases with a 15.8% WER.

Nuance came in second place by a large margin. In Nuance, 44.1% of the phrases were recognized perfectly and the WER was 39.7%. IBM (46.9.3% and 42.3% WER) came in third place. While AT&T and WIT had the exact same WER - 63.3%, with a small advantage in exact recognition by AT&T (32.8% vs 29.5%, WIT).

Word Error Rate (less is better):

Percentage of Exact Recognized Phrases (more is better):

Conclusion

Based on our test criteria of exact recognized phrases and word error rate, Google is by far the best solution out of the box. This is not surprising given their history of developing and proving voice search, but unfortunately - for now - it is not commercially available. Google’s quality, however, could be used as a benchmark for the commercially available products as many of them have tools and features for customizing search experience.

Exact phrase match and word error rate are only two issues to provide world-class voice search that your customers will soon expect. Additional challenges are speech recognition performance and recognizing eCommerce-specific terms. For instance, consider searches like brands, sizes, materials and, of course, long/complex phrase recognition (I.e., “Ok, MyFavoriteRetailer, find me a Ralph Lauren or Ann Taylor red cocktail dress, knee length and open back, in a size 9 that isn’t dry-clean only”).

But, we will discuss those challenges and our solutions in future articles.

Scoring Join Party in Solr 5.3

2015-08-23T14:21:00.000-07:00

New Solr release 5.3 brings two long awaited improvements in joins: SOLR-6234 and SOLR-5882. Join operation in Solr is as demanded as challenging. Well-known approaches are query-time {!join} and index-time block join {!parent}. Here I briefly describe the difference between two joins. Until Solr 5.3, both query parsers yield scoreless queries. Since Solr 5.3, a local parameter {!<join|parent> … score=<avg|max|min|none|total>}.. has been introduced in both query parsers. The value of score parameter defines how scores of subordinate query (“from” side query and “children” query) are aggregated into join query scores.

A Few Notes about Query-Time Join

Enabling score and even specifying {!join … score=none}.. picks the different algorithm - Lucene’s JoinUtil instead of the original Solr’s one that might have different performance. Also it can help you to use join query as Delete Query, which lead to ClassCastException before, see SOLR-6357. There is more subtle one, multiple values is supported only for “from” side (subordinate query), but not for “to” (result document). Thanks to Ryan Josal who brought this up.

Also note, that Lucene's join algorithm expect "from" field to be string docValues. If docValues is not enabled for “from” field, it will take some heap for uninverting. It is enough for "to" field to be just indexed, like with regular Solr's join.

Query-time join with scoring still supports cross-core join via “fromIndex” parameter, however, it works for Solr cores only, and support for SolrCloud collections arriving in Solr 5.4, follow-up SOLR-7775.

The Lab Time

Now let's index a few docs and experiment with join scoring. Note, for sake of simplicity this data work for both types of joins, I’ve never seen such blend in real life.

<update>
    <delete><query>*:*</query></delete>
    <add>
        <doc>
           <field name="id">1</field>
           <field name="type_s">product</field>
           <field name="name_s">expensive blue</field>
           <doc>
               <field name="id">sku1 of 1</field>
               <field name="color_s">Red</field>
               <field name="price_i">10</field>
               <field name="prod_id_s">1</field>
           </doc>
           <doc>
               <field name="id">sku 2 of 1</field>
               <field name="color_s">Blue</field>
               <field name="price_i">200</field>
               <field name="prod_id_s">1</field>
           </doc>
       </doc>

       <doc>
           <field name="id">2</field>
           <field name="type_s">product</field>
           <field name="name_s">expensive red</field>
           <doc>
            <field name="id">sku 1 of 2</field>
            <field name="color_s">Red</field>
            <field name="price_i">300</field>
            <field name="prod_id_s">2</field>
        </doc>
        <doc>
            <field name="id">sku 2 of 2</field>
            <field name="color_s">Blue</field>
            <field name="price_i">40</field>
            <field name="prod_id_s">2</field>
        </doc>
    </doc>

</add>
<commit/>
</update>

Here, both of products have red SKUs, let's sort products by color of SKU by price of SKU which matches the Red filter. To do that we need to use price_i field as a function query in subordinate query. Here we use Constant Score Query Syntax ^= to ignore score from the filtering (Red) clause.

http://localhost:8983/solr/techproducts/select?q={!join from=prod_id_s to=id score=max}+color_s:Red^=0 {!func}price_i&wt=json&indent=true&fl=score,*,[docid]

{
  "response": {
    "numFound": 2,
    "start": 0,
    "maxScore": 300,
    "docs": [
      {
        "id": "2",
        "type_s": "product",
        "name_s": "expensive red",
        "score": 300
      },
      {
        "id": "1",
        "type_s": "product",
        "name_s": "expensive blue",
        "score": 10
      }
    ]
  }
}

Filtering Blue SKUs flips the products ordering:

http://localhost:8983/solr/techproducts/select?q={!join from=prod_id_s to=id score=max}+color_s:Blue^=0 {!func}price_i&wt=json&indent=true&fl=score,*,[docid]

{
  "numFound": 2,
  "start": 0,
  "maxScore": 200,
  "docs": [
    {
      "id": "1",
      "type_s": "product",
      "name_s": "expensive blue",
      "score": 200
    },
    {
      "id": "2",
      "type_s": "product",
      "name_s": "expensive red",
      "score": 40
    }
  ]
}

As I said, the data works with index-time join, so following query will yield the same result: http://localhost:8983/solr/techproducts/select?q={!parent which=type_s:product score=max}+color_s:Red^=0 {!func}price_i&wt=json&indent=true&fl=score,*,[docid]

Near Real-Time boosting

Another challenge is to be able to update document order in real-time, eg sort by stock units, update price or rating etc. Straightforward approach is to use Atomic Updates, however internally it loads all stored fields of the updated documents, fully reindexes it, then commits and flushes all caches. It sounds like “Far Real-Time”, isn’t it? My irony doesn’t mean I know an ideal solution, as this problem is a way complex per se.

Here is ~~a better~~ another idea: if the document has many field and thus expensive for update, let’s put all frequently updated fields into separate core! Let’s create a separate core for small stock unit documents linked to SKU documents in main core:

<update>
    <delete><query>*:*</query></delete>
    <add>

        <doc>
           <field name="id">sku1 of 1</field>
           <field name="units_i">777</field>
       </doc>
       <doc>
           <field name="id">sku 2 of 1</field>
           <field name="units_i">88</field>
       </doc>

       <doc>
           <field name="id">sku 1 of 2</field>
           <field name="units_i">99</field>
       </doc>
       <doc>
           <field name="id">sku 2 of 2</field>
           <field name="units_i">66</field>
       </doc>
   </add>
   <commit/>
</update>

Now we can run functional query on this core, obtaining number of units available, and then pass it into main core with query-time cross-core join. Then, these scores passed again when join SKUs to products.

http://localhost:8983/solr/techproducts/select?q={!parent which=type_s:product score=max}+color_s:Red^=0 {!join from=id to=id fromIndex=stocks score=max}{!func}units_i&wt=json&indent=true&fl=score,*,[docid]

We see how it bumps up particular product which has SKU which is passing the filter with high amount available.

{
  "numFound": 2,
  "start": 0,
  "maxScore": 777,
  "docs": [
    {
      "id": "1",
      "type_s": "product",
      "name_s": "expensive blue",
      "score": 777
    },
    {
      "id": "2",
      "type_s": "product",
      "name_s": "expensive red",
      "score": 99
    }
  ]
}

Now, lets drop stock amount for sku 1 of 1:

<update>
    <add>
        <doc>
           <field name="id">sku1 of 1</field>
           <field name="units_i">7</field>
       </doc>
   </add>
   <commit/>
</update>

You see, here we don’t use Atomic Updates, thus fields might not be stored. After update, the product which has been almost sold out goes down:

{
  "numFound": 2,
  "start": 0,
  "maxScore": 99,
  "docs": [
    {
      "id": "2",
      "type_s": "product",
      "name_s": "expensive red",
      "score": 99
    },
    {
      "id": "1",
      "type_s": "product",
      "name_s": "expensive blue",
      "score": 7
    }
  ]
}

Note, if you would like to approach query-time cross-join for real-time boosting, make sure you check performance on early stages of evaluation. Query-time join might be not fast enough for large indices. Also, index-time join can’t help here, because it’s strictly intra-core. One promising challenger is Global Ordinals Join, even though ordinals map doesn’t span across cores, but only through segments of the single index. The question is: is it really a blocker?

That is it. I hope it brings you a few ideas how join scoring might be used in you application! Let us know how it worked out.

How to import structured data into Solr

2015-07-06T15:16:00.000-07:00

This post summarizes our experience around data ingestion in Search. Almost any search project begins with feeding search engine by existing data. Here we are mostly focusing on old good relational databases as data source. I don’t even hesitate what to to type: SQL database, or not-NoSQL DB?. Needless to say most of these considerations are applicable to any other data sources like files, web services, NoSQL DBs and distributed file systems.

Solr Data Import Handler - DIH

Let me come out at first, I’m a big fan of Data Import Handler. It’s as handy as any other ETL tool - you don’t need to write Java code calling SolrJ and debug SQL query results in IDE. With DIH you are jungling with configs and copy-paste queries and play with the queries and data right in the SolrAdmin. So, DIH is perfect for fast prototyping, but what about running it in production? There are couple of issues here (add yours):

lack of concurrency - single thread processing keeps hardware idle and takes a lot of time to complete;
lack of performant join (look further).

We will check these points below, however, we have an evidence that DIH is used for really huge deployments. So, despite of these limitations many people run DIH in production. To solve the concurrency problem, we can logically shard data using specially crafted queries and launch per-shard imports in parallel. Join performance problem is solved by persistent caches, which presumably makes join operation faster, yet I am skeptical about this approach.

Now let’s look at some practical questions.

Indexing Blocks by DIH

We are known as Block Join proponents, and as such, want to index blocks in DIH. That’s made possible in 5.1 and enabled by specifying child=”true” in the child (2nd level and more) entity.

Nested Entities (data join) in DIH

Now, lets come back to joining entities in DIH. As it’s perfectly described in SOLR-2382 referred above: “Using SqlEntityProcessor with Child Entities can cause an "n+1 select” problem”. This term reminds my earlier challenges in IT. Thus, it can’t process any considerable amount of data in a reasonable time.

You may ask why don’t just ask RDBMS to join entities and process joined result set in DIH. Well, it’s possible if both tables reside in the same DB, however, you should remember about cartesian product problem which can happen if you join two or more child entities.

Recommended approach in this case is to cache one side of the relation on heap with hashmap, and when heap is exceeded (the only case I care) it’s suggested to put data off-heap in BDB files.

Merge Join in DIH

It turns out ETL community is aware of this problem and had solution recipe for ages - external merge join. For example a gain between naive N+1 subqueries to merge join for hundred of millions records is the speedup from several hours to several minutes. It’s worth to mention that we meet the same algorithm - merging sorted sequences over and over again in search engines implementation.

Here is the good news: starting from 5.0 merge join is available for any EntityProcessor in DIH by specifying join=”zipper” in child entity. Sure you need to sort both inputs, thankfully that’s done by RDBMS’ indices quite well. Interesting to see how Kettle ETL reminds about it every time when merge join configuration is amended. DIH doesn’t bother you with such pop-up, but throws an exception if inbound streams are not ordered.

You can also process many-to-many relations, but it requires join and sort in RDBMS, that’s usually fine.

It’s time to talk about threads and concurrent processing. Before this, let’s make a note that merge join algorithm is not easily parallelizable, thus “hash join” (lookup in cached data) is more suitable for multithreaded processing.

Multithreading

There are no threads in DIH. Sic. We have usual pitfall of producer-consumer with the sequential processing - everyone waits its’ counterpart:

What we have in DIH

What we want to have

Just a note, the same problem we have if run DIH with SolrCloud, in this case DIH feeds Solr one document by one synchronously, and blocks until every document is sent to shard leader by DistributingUpdateProcessor.

Okay, enough about problems, let’s talk about opportunities. We can parallelize outbound flow (consumer):

if DIH sent updates via ConcurrentUpdateSolrClient or CloudSolrClient, it would unblock producer from consumer, giving the opportunity to fully utilize Solr machines for indexing. However, this is not possible with current DIH design, but we have a great attempt to breakthrough - SOLR-7188. Heads up! It would be a great win, letting us to run DIH as a real ETL tool.
there is another patch adds threads on UpdateRequestProcessors layer - SOLR-3585 you can think about it as a server side ConcurrentUpdateSolrClient. Despite we have a positive feedback from the production usage, I’ve changed my mind since its’ contribution and don’t consider it as an architecturally wise approach. I suppose it’s a client’s duty (i.e. ETL) to provide the proper level of concurrent load and throttling. Nevertheless, you can use it if you are in the trouble, for example if you have some legacy script posting files into Solr http endpoint.

We can also think how to prefetch data in JdbcDataSource in background thread that avoids blocking producer. I must have such patch somewhere, let me know if you need one.

Another ETL tool: Kettle

I also played with a couple of open source ETL tools, I choose Kettle as an example. It has many useful facilities built-in and you can definitely use it as a tool box for data ingestion.

However, we are keen in the particular problem - building Solr XMLs. The difficulty which I've faced is the limitations of flat relational tuples (call it rows or records). However, what we need is to have at least three levels of nesting like here - parent-child-attributes. One of the possible workarounds is to use XML DOM as a data structure, however it can not be transferred between transformation steps as-is, and needs to be converted into string, concatenated and parsed again and again something like we have here.

I've found XML Join is not well scalable, it rather works like in-memory XPath database, it's great, but not what I need.

One of the possible solutions is to introduce DOM XML as a first class datatype in Kettle, and let some steps to process it as-is.
UPD: here is a prototype https://github.com/griddynamics/xml-dom-kettle-etl-plugin

Stay tuned, we will present such a proof-of-concept soon. Don't hesitate to share your vision, experience and findings.

Lucene SIMD Codec benchmark and future steps

2015-06-16T18:51:00.000-07:00

We are happy to share results of our Lucene SIMD research announced earlier.

Ivan integrated https://github.com/lemire/simdcomp as Lucene Codec and we could observe 18% gain on standard Lucene benchmark. Here are the fork, deck, recording from BerlinBuzzwords.

Tech notes

The prototype is limited to postings (IndexOptions.DOCS), so far it doesn’t support freqs, positions, payloads. Thus, full idf-tf scoring is not possible so far.

The heap problem

Currently, the bottleneck of the search performance is the scoring heap. Heap is hard for vectorization, and even hard to compute with regular instructions. Thus, benchmark retrieves only top 10 docs to limit efforts for managing heap.

Here is a profiler snapshot for the default Lucene code, decoding takes more than collecting.

This is hotspots with the SIMD codec, note that collecting is prevailing now and ForUtil takes relatively smaller time for decoding.

Edge cases

There are few special code paths which bypass generic FOR decoding which make it harder to observe vectorization gain. Very dense stopwords postings are encoded as a sequence of increasing numbers with by just specifying length of the sequence (see ForUtil.ALL_VALUES_EQUAL). Thus, we excluded stopwords from the benchmark to better observe the gain in FOR decoding.

Another edge case is shortening postings on high segmentation. FOR compression is applied on blocks, and remaining tail is encoded by vInt. Thus, to observe the gain in FOR decoding, we merge segments to the single one.

Due to the same reason, rare terms with short postings list is not a good use case to show a gain.

Further Plans

Here are some directions which we consider:

provide codec and benchmark as a separate modules;
apply SIMD codec for DocValues and Norms - it should improve generic sorting, scoring and faceting. Because ordinals in DocValues are not increasing like postings, https://github.com/lemire/FastPFor should be incorporated;
complete codec for supporting frequencies, offsets and positions to make it fully functional;
presumably, SIMD facet component might get some gain from vectorization, however decoding ordinals might not be the biggest problem in faceting, like it’s described here;
execute binary operations like intersections on compressed data with SIMD instructions https://github.com/lemire/SIMDCompressionAndIntersection;
native code might access mmapped index files without boundary checks or copying to heap arrays;
implementing roaring bitmaps might help with dense postings;

Which of of those directions are relevant your challenges? Leave a comment below!

Here are still questions to clarify:

will critical natives work for Java 9 and further?
couldn’t it happen that vectorization heuristic by JIT makes explicit SIMD codec redundant?

We’d like to thank all people who contributed their researches and let us to conduct ours.

Who is who in Big Data

2015-06-01T14:05:00.000-07:00

Well, this post is not about persons or companies, but brief overview of what is BigData and Big Data stack technologies, so don't be confused with the title.

It's a good starting point to explore Big Data and understand what is what, pros and cons and of every technology and how they can be combined.

Enjoy!

http://sotnikdv.github.io/bigdata/2015/05/31/who-is-who-in-bigdata.html

Spark and ZooKeeper: fault-tolerant job manager out of the box

2015-03-18T11:11:00.001-07:00

Problem definition

Imagine that you’ve been using some RDBMS for last ten years, and there’s millions of records inside, moreover the information keeps flowing every minute. And one day you needed to organize some complex information retrieval process on this data with a full-fledge enterprise search engine like Apache Solr. In order to do this you need to develop some ETL process that will be able to convert your data to internal Solr documents. You obviously want to distribute it and make fault-tolerant (you don’t want to lose even a row of information). And the last requirement, that makes everything more interesting - you want zero support burden. Everything should come out of the box! Too difficult? Absolutely not! Let’s see how to nail it with Solr, Spark and Zookeeper binded together.

Why Spark? It is distributed, it doesn’t force you to use MapReduce programming model (like Hadoop does), and finally, it has a failover mechanism backed by Zookeeper.

So, we introduced our toolbox, now it’s time to make it work. Let’s start with Solr and Zookeeper. Historically, Solr was just an universal search engine built on top of Apache Lucene, but starting from 4.x version it comes with distributed search support aka SolrCloud, which provides additional failure resilience, delegating cluster management to Zookeeper. Spark can also use Zookeeper for failure recovery in cluster mode.

Preparation

First, let’s prepare a simple application that will emulate our long running data import task. We’ll submit this application to Spark and try to simulate node/process failure, while it sends simple documents to Solr. Our goal is to ensure that there’s no document loss due to any failures.

Spark applications are just Java archives containing all project dependencies. Documentation recommends to use either sbt or Maven project management tools with appropriate plugins:

We’ll make our application with Maven. In order to do this we need to add a dependency to SolrJ (http://mvnrepository.com/artifact/org.apache.solr/solr-solrj) and put a dummy class with a simple code like this:

package com.example;

import org.apache.solr.client.solrj.SolrServer;

import org.apache.solr.client.solrj.impl.HttpSolrServer;

import org.apache.solr.common.SolrInputDocument;

import java.util.ArrayList;

import java.util.List;

public class Executor {

public static void main(String[] args) {

String solrServerURL = "http://localhost:8983/solr";

int offset = 0;

int delay = 1;

for (String arg : args) {

if (arg.startsWith("offset=")) {

// This offset is needed to avoid sending several documents with the

// same id. In spite of the fact that Solr can handle such documents,

// we don't want to have any intersections. If we run 4 tasks like this

// one, then we need check if all 4000 documents are indexed.

offset = Integer.parseInt(arg.split("=")[1]);

} else if (arg.startsWith("delay")) {

delay = Integer.parseInt(arg.split("=")[1]);

} else if (arg.startsWith("solr_server")) {

solrServerURL = arg.split("=")[1];

}

SolrServer solrServer = new HttpSolrServer(solrServerURL);

List<SolrInputDocument> docs = new ArrayList<SolrInputDocument>();

for (int i = 1; i <= offset + 1000; i ++) {

SolrInputDocument document = new SolrInputDocument();

document.addField("docid", String.valueOf(i));

docs.add(document);

// Add documents to Solr by batches with a size equal to 100

try {

if (i % 100 == 0) {

solrServer.add(docs);

docs = new ArrayList<SolrInputDocument>();

}

} catch (Exception e) {

// TODO: Proper exception handling

}

// Artificial delay to prolongate total time

try {

Thread.sleep(delay);

} catch (InterruptedException e) {

// Nothing to do

}

// Finally commit documents and free resources

try {

solrServer.commit();

} catch (Exception e) {

// TODO: Proper exception handling

} finally {

solrServer.shutdown();

}

This code generates Solr input documents with the only field “id”, and sends them to server using Java client called SolrJ. The “id” field must be unique in the context of Solr index, and nevertheless it is not exceptional situation for Solr to handle two documents with the same id, we need to count every document sent to server to ensure that no document is lost. Fine, let’s build it, and now we have our “uber” JAR with all dependencies.

SolrCloud deployment

Next step. Now we are going to download and unpack SolrCloud distributive. Downloads are located on the page http://lucene.apache.org/solr/downloads.html. I took 4.10.2 version. We’ll be using embedded example in our how-to, let’s clone its folder to make four independent workspaces:

my_device:~ Root$ cd ~/solr-4.10.2/
my_device:solr-4.10.2 Root$ cp -r example example2
my_device:solr-4.10.2 Root$ cp -r example exampleB
my_device:solr-4.10.2 Root$ cp -r example example2B

Ok, now deploy first instance:

my_device:example Root$ export SOLR_INSTANCE=~/solr-4.10.2/example
my_device:example Root$ java -Djetty.port=8983 -Djetty.home=$SOLR_INSTANCE -Dsolr.solr.home=$SOLR_INSTANCE/solr -Dbootstrap_confdir=$SOLR_INSTANCE/solr/collection1/conf -Dcollection.configName=myconf -DzkRun -DzkHost=localhost:9983,localhost:8574,localhost:9900,localhost:9500 -DnumShards=2 -jar $SOLR_INSTANCE/start.jar

And continue deploying, changing jetty.port (8983, 7574, 8900, 8500) and SOLR_INSTANCE (example, example2, exampleB, example2B) parameters accordingly. You can send all these commands to background using “&” appendix or run them separately in four consoles. Here:

jetty.port, jetty.home - Solr from example uses Jetty embedded server under the hood, so we just need to specify right port to bind on and working folder
solr.solr.home - home directory for all Solr files (properties, index files and so on)
bootstrap_confdir - initial boot configuration, that will be uploaded to ZooKeeper
collection.configName - sets a name for ZooKeeper configuration
zkRun - tells to run embedded ZooKeeper
zkHost - specifies all nodes eligible to host ZooKeeper

When everything is done, we’ll get two shards and two replicas SolrCloud. Also we told Solr to run embedded ZooKeeper and upload its configuration there. You can check Solr state, cloud details and ZooKeeper data by going to Solr admin page located by the link http://localhost:port/solr (pic. 1 and 2).

Pic. 1 – SolrCloud graph

Pic. 2 – Zookeeper tree

Spark deployment

Now, it’s Spark turn. Spark can be downloaded from https://spark.apache.org/downloads.html. There are several pre-built versions available for download for your convenience. When it’s done, unpack an archive and clone it - one instance will became a leader or master node, second one will became spare or standby node. Let’s name these folders accordingly:

my_device:~ Root$ tar -xzvf spark-1.1.1-bin-hadoop2.4.tgz
my_device:~ Root$ mv spark-1.1.1-bin-hadoop2.4 spark-leader

my_device:~ Root$ cp spark-leader spark-standby

Alright, then we need to configure our Spark nodes. In order to do this, copy or rename existing template:

my_device:~ Root$ cd spark-leader/conf
my_device:~ Root$ cp spark-env.sh.template spark-env.sh

And reduce it’s content to:

export SPARK_MASTER_IP="localhost"

export SPARK_MASTER_PORT=1101

export SPARK_DAEMON_JAVA_OPTS="-Dspark.deploy.recoveryMode=ZOOKEEPER -Dspark.deploy.zookeeper.url=localhost:9983,localhost:8574,localhost:9900,localhost:9500"

export SPARK_PID_DIR="/tmp/spark-leader"

export SPARK_MASTER_WEBUI_PORT=6661

export SPARK_WORKER_PORT=1102

export SPARK_WORKER_MEMORY=512m

export SPARK_LOCAL_DIRS="./data"

export SPARK_WORKER_DIR="./work"

What is this all about? Well, every option is described in the original template, we’ll only pay an attention to the following variables:

SPARK_DAEMON_JAVA_OPTS - we told Spark to use Zookeeper for recovery and pointed to Zookeeper cluster
SPARK_PID_DIR - there’s a dir where Spark will keep process ids, we will need it in order to simulate node failure

Do the same for the spare node:

export SPARK_MASTER_IP="localhost"

export SPARK_MASTER_PORT=2101

export SPARK_DAEMON_JAVA_OPTS="-Dspark.deploy.recoveryMode=ZOOKEEPER -Dspark.deploy.zookeeper.url=localhost:9983,localhost:8574,localhost:9900,localhost:9500"

export SPARK_PID_DIR="/tmp/spark-standby"

export SPARK_MASTER_WEBUI_PORT=7661

export SPARK_WORKER_PORT=2102

export SPARK_WORKER_MEMORY=512m

export SPARK_LOCAL_DIRS="./data"

export SPARK_WORKER_DIR="./work"

That’s all, now it’s time to deploy Spark cluster. I wrote a simple bash script to achieve this goal:

#!/bin/bash

rm -rf /tmp/spark-leader

rm -rf /tmp/spark-standby

bash spark-leader/sbin/start-master.sh

bash spark-standby/sbin/start-master.sh

SPARK_WORKER_INSTANCES=4

SPARK_WORKER_WEBUI_PORT=8661

for ((i=0; i<$SPARK_WORKER_INSTANCES; i++)); do

bash spark-leader/sbin/start-slave.sh $(( $i + 1 )) spark://localhost:1101 --webui-port $(( $SPARK_WORKER_WEBUI_PORT + $i ))

done

This script first cleans tmp directories, then runs two master nodes and finally starts four worker nodes. What are these master and worker nodes? Worker nodes are executors, they can only run assigned tasks, and master nodes are Spark coordinators, they orchestrate Spark cluster and assign tasks to available workers. If everything is fine, in a minute after the script is run we’ll be able to see following page by addressing to http://locahost:6661:

Pic. 3 – Spark master web UI

In the picture 3 we can see Spark master with four connected worker nodes. If we go to another node (http://localhost:7661), we’ll see similar screen, but without any worker nodes connected (that's because we sent them to spark://localhost:1101).

Testing

So, we deployed Solr, Zookeeper and Spark clusters, and we have an assembled application, let’s submit it and experiment with failover!

my_device:~ Root$ spark-leader/bin/spark-submit --class com.example.Executor --master spark://localhost:1101 --deploy-mode cluster --supervise --executor-memory 512m --total-executor-cores 4 path-to-application.jar offset=0 solr_server=http://localhost:8983/solr &

What do these command mean? First of all, we use spark-submit script to submit our tasks. Second, we point to an executable class within our jar. Further we tell Spark how to submit the tasks (or drivers in terminology of Spark):

--deploy-mode cluster – from documentation “Whether to deploy your driver on the worker nodes (cluster) or locally as an external client (client) (default: client)”
--supervise – specify this flag to make sure that the driver is automatically restarted if it fails with non-zero exit code. This’s exactly what we’re looking for – in case if Spark worker node is terminated, Spark cluster will just restart it on any free worker node.

What about the rest of the arguments? Well, one of them is obviously just path to our jar. And the others two are arguments that are sent to our executable class. Solr server url is an endpoint where to send Solr documents. And the last one – offset – we need it, as it was told, to avoid sending several documents with the same id.

Run this command four times increasing offset by thousand. If everything is fine, we’ll get four completed tasks and four thousand documents in Solr (see pictures 4 and 5).

Pic. 4 – finished drivers in Spark master web UI

Pic. 5 – Match all query in Solr web UI

What next? Remember we introduced “delay” command line argument in our code? We need it now to manipulate total execution time causing some artificial processing delay. During the first run we minimized it to default 1 ms, because we needed this run only to collect our control data. During the second run we’ll extend this value up to 180 ms (total execution time will be at least 3 minutes) - this will give us enough time to simulate node failure. In the end we’ll compare control data with test data. But first we need to find out leader node PID:

my_device:~ Root$ cd /tmp/spark-leader

my_device:~ Root$ cat spark-Root-org.apache.spark.deploy.master.Master-1.pid

38073

my_device:~ Root$

Ok, this number – 38073 – is our leader node PID. And let’s find out our worker nodes ids:

my_device:~ Root$ jps

38145 Master

38073 Master

38016 start.jar

38014 start.jar

38015 start.jar

38865 Jps

38013 start.jar

38385 Worker

38325 Worker

38265 Worker

38205 Worker

my_device:~ Root$

We’ll choose one of the workers as well as leader node and terminate them, but first we need to purge Solr and run our modified submit commands (again, four times):

my_device:~ Root$ curl http://localhost:8983/solr/update --data '<delete><query>*:*</query></delete>' -H 'Content-type:text/xml; charset=utf-8'

my_device:~ Root$ curl http://localhost:8983/solr/update --data '<commit/>' -H 'Content-type:text/xml; charset=utf-8'

Ready? Lets simulate nodes failure:

my_device:~ Root$ kill -9 38385

my_device:~ Root$ kill -9 38073

If we’re fast enough, we can see how Spark failover mechanism works – all we need is to track changes on our standby node web UI (http://localhost:7661). Usually it takes about a half of a minute to see any updates. Expected behaviour is that no submitted task will lost if the worker is down (pic. 6), spare node will change its status from STANDBY to ALIVE (it becomes leader node) if current leader node is terminated, and no orphan worker will left – they all become connected to new leader (pic. 7):

Pic. 6 – Driver relaunching

Pic. 7 – Spark recovery process on spare master node

Finally, when all drivers become completed, we need to go back to Solr and check that all match query returns the same result as we seen (pic. 5) – 4000 documents.

Okay, seems our problem is solved - we simulated long-run distributed task, we randomly terminated executing applications and we saw entire recovery process which ensured that we haven’t lost any data. We didn’t have to write any special code to achieve this level of resiliency and job recovery. So, Spark can be used as a resilient job manager for long running data importing tasks.

Proposing SIMD codec for Lucene

2015-02-01T12:45:00.006-08:00

This post is inspired by a whitepaper. Hence, if you wish to save your time you can just read it instead of this post. However, let me try to express the context around.

First, lets recollect the basics. Search engines are based on inverted index (or wiki) data structure which is essentially a mapping from a term to its posting list - a sorted sequence of documents where this particular term occurs.

The search request execution has several stages. Usually, the three of the most time consuming are:

term dictionary lookup, which resolves posting list position for the given query terms;
reading posting list from the storage, whether it’s a disk or a memory;
applying query logic and ranking results.

This post aims the second item - reading posting list, which is in fact decompression. You may wonder why to waste efforts on decompression, giving that storage cost is miserable nowadays. The answer is that system bus becomes a bottleneck when the huge index data is moved to CPU for processing. Hence, compression allows to trade CPU clocks for bus throughput.

Giving significant academia attention to this problem (eg check the best paper at ECIR’14), we’ve tried to measure which part of the search time is spent on decompression. We’ve slightly modified Lucene wiki search benchmark. It searches for 10K most frequent terms in 2.9M docs index. We’ve compared current Lucene codec with DOCS_ONLY mode that indexes only document numbers with the postings loaded into heap via FixedBitSetCachingWrapperFilter. The benchmark shows nearly 20% performance gain with heap bitsets. It does not seem like vast majority of the time, that might have two explanations: the benchmark is incorrect; or Lucene made a good progress toward fast decompression already.

The later seems happen in 4.x where bit variable codec, which can stores just a few bit per document, replaced the older byte variable ones, which stores at least a byte per document. From another benchmark we have an evidence two-time performance gain of the former one. Nevertheless, we consider 20% as a maximum gain achievable by optimizing the decompression algorithm.

The idea of the paper referred in the beginning is to apply SIMD operations for decompression. Let me omit the explanation about it. We just can say that it is known as MMX, SSE2, SSE3 and it’s definitely nearly as cool as CUDA, you know. We are going to approach The SIMDComp library as Lucene codec and report a simple benchmark. The most difficult part is to make a fast call from Java to native SIMD code. We have an idea how to do that, which was found by one hacker from ok.ru used to be principal HotSpot developer. Here is the description of the finding in Russian and translation.

From the codec benchmarks, which we’ve done so far we expect two times gain from approaching existing SIMD decoder. Thus, we expect only 10% overall improvement for Lucene wiki benchmark. It doesn’t sound like a true performance breakthrough, but we consider it as first step on the promising field, because further SIMD can be possibly approached for other CPU consuming operations like faceting, aggregations, intersections, etc. So, let us know if you know VC who is hungry for something like this, or if you aware about pitfalls which we are going to hit.

Numeric Range Queries in Lucene/Solr

2014-10-15T17:33:00.001-07:00

I bet that almost every e-commerce site has price-range filters which help user to filter search results by price. Of course, ranges could be used not only as filters but also as a part of query. Most of us are familiar with range queries in Lucene/Solr but only few people know about internal optimizations for numeric ranges.

In this post we will unveil the main algorithm for numeric range queries and also take a brief look at some tricks made in Lucene/Solr to make numeric ranges fast and efficient. From a historical point of view the idea of an algorithm came from PANGAEA® Framework for Metadata Portals and original publications made by Uwe Schindler.

Algorithm

In Solr, following algorithm is used for trie based fields, such as solr.TrieIntField, solr.TrieFloatField, etc...

Let's start from explanation of the main idea of NumericRangeQuery which is based on trie representation of numerics. For simplicity, lets stick with decimal number system for the first example.

Index time

On the diagram there are term values themselves in the lowermost row and some term values in the upper rows: each upper level is an integer quotient of division of lower row by ten, let's call them lower precision values. Let's assume that we index all numbers from lowermost row(original term values) with all their quotients.

To make it more clear we need to look at posting lists:
value -> document ids
421 -> [1]
423 -> [2]
445 -> [3]
446 -> [3]
448 -> [4]
521 -> [5]
522 -> [7]
632 -> [5]
633 -> [6]
634 -> [7]
641 -> [5]
642 -> [6]
644 -> [7]

and for quotients
42 -> [1, 2]
44 -> [3, 4]
52 -> [5, 7]
63 -> [5, 6]
64 -> [5, 6 , 7]
4 -> [1, 2, 3, 4]
5 -> [5, 7]
6 -> [5, 6, 7]

In other words we group/aggregate posting lists by lower precision values during index time.

Search time

Lets assume we want to find all records with term values between “423” and “642”. Naive algorithm here would be to expand the range to separate values: 423 OR 445 OR ... 641 OR 642 (Note: I omitted values which were not indexed to simplify description). But as we use special type of field, instead of selecting all terms in lowermost row, query is optimized to only match on labelled term values (elements with gray fill on the diagram) with lower precision, where applicable. It is enough to select “5” to match all records starting with “5” (“521”, “522”) or “44” for “445”, “446”, “448”. Query is therefore simplified to match all records containing the following terms: “423”, “44”, “5”, “63”, “641”, or “642”.

So, instead of doing search by every value in the requested range, algorithm uses grouped values wherever possible.

Under the hood

Now, once we get the main idea of the algorithm we can proceed with Solr internals and switch to binary. Warning! This part can be tricky if you've never spent several days debugging Solr and Lucene guts.

Index time

During index time all terms for value and its quotients are need to be produced. Solr index flow is as simple as: DirectUpdateHandler->IndexWriter#updateDocuments->DocumentWriter->DocumentConsumer#processDocument(fieldInfos)->DocFieldProcessor->DocFieldProcessorPerField->DocInverterPerField

So, for incoming document we get all its fields and process values of each field by DocInverterPerField. Basically it gets a token stream (Lucene's TokenStreams are explained by Mike McCandles) which produces the sequence of tokens to be indexed for a document's fields.

Here is a sequence diagram where you could see that for numeric field types the NumericTokenStream is created:

The NumericTokenStream is where half of magic happens. Values it produces depends on actual field type (TrieIntField, TrieLongField, etc) and precision step configured for field. The precision step parameter will be explained later. In the upcoming example we will stick with TrieIntField and precision step equal to 1.

Now, let's look at an example which shows us which tokens are produced by NumericTokenStream for some value.

In our case the value would be 11, here is its binary representation:

00000000

00001011

And this is how it is indexed(@see rawValue row):

The second thing which you may have noticed is "shift" which increases by precision step value for each next token. So, the values are 11, 10, 8, 8, 0, 0 and a scrollbar. What are binary representation for these values? Here they are:

00001011

00001010

00001000

00000000

Et cetera.. Note that I showed you only the first byte, in general for integer we have 4 bytes. 11 is quite small number, so if we had a bigger number we would end up with 32 different tokens being produced.

All these tokens are indexed including the value itself. Now to get the second half of magic and put pieces together we need to look at the search time.

Search time

The search starts from a http request with some parameters. For example, for default configuration we have something like: http://localhost:8983/solr/collection1/query=price:[3 TO 12]. QueryParser parses the query to produce a Query object. Here is a sequence diagram:

Again we have FieldType here which creates a query. TrieIntField creates a NumericRangeQuery.

And here comes another half of magic.

NumericRangeQuery extends MultiTermQuery. The latter one is an abstract Query that matches documents containing a subset of terms provided by a FilteredTermEnum enumeration. This query cannot be used directly(abstract); you must subclass it and define getEnum(Terms) to provide a FilteredTermEnum that iterates through the terms to be matched. NumericRangeQuery returns an instance of NumericRangeTermEnum for enumerating all terms that match the sub-ranges for trie range queries.

Underneath it uses utility class method NumericUtils.splitXXXRange() to calculate values to be matched. We won't explain the algorithm here because it requires a separate blog post itself (it is briefly covered in the first useful link in the end of the post), but we will look at our last example one more time to find labelled term values for it:

We had value=11 and precisionStep=1, but as you may remember we had 11, 10, 8, 8, 0, 0, 0.. lower precision values for it. But if you look to decimal picture you will notice that each upper level is a lower level divided by 10, right? So, here you have the same: if you divide the 11 by 2 you will get 5 as integer quoitient and if you multiply 5 back, you will get 10. I know, it sounds tricky but it's really just the same as we had in decimal example, oh, binary system is so uncomfortable..

There is one reasonable question to ask here. How to differ 1 from lowermost level and 1 from an upper level? Here is the answer: during indexation the value is encoded and first byte of encoded value is the shift which is unique across trie levels. So, in index it could look something like that (just a speculation):
shift value
0 3
0 12
2 1
2 2

As a bonus of such encoding, the values became ordered by trie level, 3 and 12 go first and then 1 and 2. And that's what NumericRangeTermEnum does. It enumerates terms/values in such an order.

Actually it's not the end of the story and after you get a FilteredEnum for MultiTermQuery it needs to be somehow converted to a real Query because MultiTermQuery just throws UnsupportedOperationException on createWeight(..) method which means that MultiTermQuery shouldn't be used as a real query. And here comes another story about different rewrite methods. If you want you could dig into javadoc for org.apache.lucene.search.MultiTermQuery.RewriteMethod. I want to simply mention two main rewrite methods and their general idea.

BOOLEAN_QUERY_REWRITE

Collect terms (TermCollector) by using #getTermsEnum(...)
For each term create TermQuery
return BooleanQuery with all Term queries as leafs

FILTER_REWRITE

Get termsEnum by using #getTermsEnum(...)
Create FixedBitSet
Get DocsEnum for each term
Iterate over docs and bitSet.set(docid);
return ConstantScoreQuery over filter (bitSet)

That's all I wanted to tell you here.

Precision step

I promised to tell you more about precision step. Actually precision step just determines the size of a shift, consequently:

It defines how much values to index for each original value
Smaller precision step means less number of terms to match, which optimizes query speed but more terms to seek in index (because of additional terms)
Higher precision step means more number of terms to match, reducing the effect of optimization, if precision step is equal to a type size then nothing is optimized and no additional terms in index are present.
You can index with a lower precision step value and test search speed using a multiple of the original step value. Ideal step can be found only by testing

Performance

According to NumericRangeQuery javadoc:
Opteron64 machine, Java 1.5, 8 bit precision step
500k docs index
TermRangeQuery in BooleanRewriteMode took about 30-40 seconds
TermRangeQuery in FilterRewriteMode took about 5 seconds
NumericRangeQuery took < 100ms

Useful links

Here are some useful links for curious readers:
http://www.slideshare.net/VadimKirilchuk/numeric-rangequeries
http://lucene.apache.org/core/4_0_0/core/org/apache/lucene/search/NumericRangeQuery.html
http://invertedindex.blogspot.com/2009/11/numeric-range-queries-comparison.html

Thanks

Alternative approach to spell correction: character histograms

2014-04-02T17:23:00.000-07:00

Intro

Spell correction (a.k.a. “fuzzy matching”) is a comprehensive feature which is a “must-have” for any modern search engine. In Solr/Lucene, spell correction feature is implemented with SpellChecker class inside org.apache.lucene.search.spell.* package. The implementation details will lead you to N-gram based matching model, which is pretty fast technique for most situations. Lucene 4.0 introduced fast FuzzyQuery, which is built on a top of FSA and offers better performance, while having limitations in supported accuracy range. Here we discuss yet another approach to spell correction, which may be useful in some cases and offer our benchmarks.

Problem statement

Assuming that we have some corpus of documents indexed, spell correction problem can be viewed as a task to find a number of “similar” phrases in the index for a given input phrase:

String[] suggestSimilar(String word, int numSug, float accuracy)

Where:

word - a concrete given input phrase;
numSug - number of suggestions to produce;
accuracy - metric describing how “far” can be our suggestions from original input phrase. Most commonly, distance between phrases is measured with Levenshtein distance, and our “accuracy is tied with it with the following equation”: maxEditDist = (1-accuracy)*word.length());

Approach

Brute force approach to solution of our problem would be to iterate through all phrases in index, calculating Levenshtein distance with input phrase and collecting numSug phrases with smallest distance. Unfortunately, Levenshtein distance is quite expensive operation and it is impractical to invoke for every phrase in the dictionary. So, we need to be cleverer than that. One way of optimization is to build a statistics for our phrases at index time which would allow to quickly filter only those phrases which can potentially have sufficiently small Levenshtein distance with input phrase. This is exactly what is happening with N-gram model and alternative algorithm we are discussing here follows same idea

Character Histograms and Spell Correction

This curious approach was inspired by Leo Polovets on this Quora conversation. Our goal, as it was stated above, to filter out those phrases from our dictionary, which are guaranteed to don’t pass accuracy restriction. We should find such filter which will leave only ~1% of candidate phrases in the dictionary, for which we have to actually calculate Levenshtein distance. Let’s buckle up and dig into details.

What it character histograms

Character histogram is a simple way of creating a general statistics about character distribution in a given word or a phrase.

For instance, character histograms for “burberry watches” can be viewed as:

How can we use histograms to compare two phrases

It is easy to see that there is no direct connection between Levenstein distance and character histogram. For example, for two phrases “step” and “pets” character histograms would be the same: so histograms doesn’t account for character ordering. However, we still can get important information about their Levenstein distance by using their character distribution.

Distance between our histograms can be calculated with Manhattan distance. Key insight of the algorithm is that lower boundary of Levenstein distance depends on Manhattan distance between our histograms:

when character is inserted or deleted, histogram distance will be exactly 1
when character is substituted, histogram distance can be both 0 (if new character falls in same bucket) and 2 (new character falls in a different bucket).

To support this uncertainty we can safely say that LD >= MD/ 2

Well, lower boundary of Levenstein distance as half of Manhattan distance is good, but we should be able to push it up a little bit! Indeed, it is obvious that Levenstein distance is larger that difference between phrase lengths (String distance, SD). We can try to combine both lower bounds into single lower bound. We only have to remember that inserts and deletions are accounted by both metrics, thus we have to divide by two to receive accurate lower boundary:

LD >= (MD+SD)/2

Lets consider our example: Manhattan distance between our histogram is 3. To transform “baboon” into “balloon”, we need to delete one “b” and add two “l” in our histograms. It looks like that Levenstein distance is greater than or equal to 3. As histograms ignore character order, we can say that real distance can be greater than 3. However, in our sample there is a possible 2-edit (not 3-edit) sequence: “baboon” (edit: “b” -> “l”) -> “baloon” (insert: “l”) -> “balloon”. Thus, some “delete”+”insert” operations bundle can be substituted by single “substitute” operation. Taking into account string length difference SD=|6-7|=1, we receive true lower boundary (3+1)/2=2

So, if our spell correction accuracy requires Levenstein distance =1, we shouldn’t even bother to calculate Levenstein distance between baboon and balloon, it is guaranteed to be at least 2.

So the main conclusion here is:

we can obtain a lower bound for the Levenstein distance between input phrase and suggest candidate from a dictionary using character histograms;
we can filter out suggest candidate if a lower bound for LD doesn’t satisfy accuracy restriction.

All we need to do now is to have ridiculously fast ways to calculate and compare character histograms.

How can we encode histograms

For encoding let’s assume that each character is already represented as an ASCII code.

We want to map character histograms into 64 bits (using Java notation) for obvious performacne reasons:

long encode(String word)

Internals:

64 bits are be divided into 16 buckets;
Each bucket is a number from 0 to 15 (4 bits);
For each character from histogram:

take an ASCII code modulo 16 - this will be bucket number
put/add character frequency to the specified bucket;

Conditions:

It can happen that one bucket will be holding frequencies for more than characters, i.e. bucket collisions;
It can happen that the character frequency will be more, that 15. In this case, as we are storing in a bucket a number modulo 16, we can sustain information losses.

In sake of performance, we are accepting those risks (in production, ensure that your phrases are short enough). This situation is similar to that of Bloom filter, where we accept possibility of false negative matches.

Example: “banana”

char	ASCII	bucket number = ASCII % 16
b	98	2
a	97	1
n	110	14
a	97	1
n	110	14
a	97	1

Thus, “Banana” will be encoded into the following 64 bit sequence:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0000001100010000000000000000000000000000000000000000000000100000

Implementation Details

In the index-time we can pre-calculate all histograms for the whole dictionary. Basically for the list of dictionary phrases we will construct the list of histograms (long[] in Java notation) of the same size.

At the query time we will calculate the histogram of the input phrase and will iterate through this array calculating histogram difference and obtaining lower boundary for Levenstein difference. We will collect only those phrases, which has acceptable lower bound for the LD. After that, we will calculate actual Levenstein distance only for our candidates.

We have (naive and unoptimized) implementation using Java and Lucene 4.5.0. All sources you can find on my github page: https://github.com/pvasilyev/pet-project-spellcheck

Benchmark Results

Benchmark results were obtained using http://openjdk.java.net/projects/code-tools/jmh/ micro-benchmark harness.

Those benchmarks utilized:

MacBook Air, Mac OS 10.9;
8 GB, 1600 MHz, DDR-3 RAM;
2 GHz Intel Core i7, Ivy-Bridge;
JMH test against 1 thread both for Lucene spell check engine (SpellChecker) and new spell check engine (current approach).

Input dataset: dictionary with some e-commerce data (brand names, categories, etc.) ranging from 1K up to 200K entries.

Input queries: there was pre-generated list of queries with various typos (from 1 to 6 - depending on the query phrase length)

Results can be found in a graph:

Conclusions and further directions

As you can see, even naive implementation of this approach provides significant performance boost over Lucene’s for small dictionaries. However, scalability of this implementation is poor and it starting to lose to Lucene at near 25K dictionary size. Current implementation can be improved both by pure code optimization and by improved algorithm of histogram filtration. This can be achieved by building additional data structures at index time to improve “neighbour” histogram search performance. Some advanced techniques like BK-trees can prove handy.

Stay tuned!

Segmented Filter Cache in Solr

2014-01-03T10:32:00.000-08:00

To view an updated version of this post click here

Intro

Let’s continue exploring block-join query parser in Solr. Today we’ll look at some sort of an accidental finding. What do you think, which query this parser yields if you omit query string eg. q={!parent which='type_s:parent'}? It might not seems obvious, but it yields the same parent filter (type_s:parent) from perSegFilter cache. Initial intention for this code branch was to expose parents bitset to users who want to reuse it as Solr’s filter query. It turns out that it can solve a filter cache regeneration issue and make Solr more NRT-friendly (Near Real Time).

Let’s start from caching basis. If you specify fq=SIZE:XL in request params, Solr will create on-heap bitset on top of all segments and will use it as a filter in a very efficient manner. However, when you perform commit (no matter hard or soft) this bitset gets scratched and you are facing with slowdown, either at commit time, when filter bitsets are regenerated, or at query time, when unlucky ‘cold’ requests have to regenerate those bitsets. Such pauses make Solr not really NRT- friendly. If you are dealing with such commit pauses and/or have to commit frequently, read on, otherwise you can consider it as quite untypical Solr use case.

NRT-filters

To get rid of these pauses try to rewrite fq=SIZE:XL to fq={!parent which='SIZE:XL'}. Also, make sure that perSegFilter has proper size and has NoOpRegenerator specified. Now filters shouldn’t slowdown searches on commit nor commits themselves. If you wish further explanation, please comment below and I’ll elaborate.

To check that it works as expected, look at cache entries by enabling cache introspection. That’s what you should see in perSegFilter dropdown in SolrAdmin:

item_SIZE:XL: FixedBitSetCachingWrapperFilter(QueryWrapperFilter(SIZE:XL))

Make sure that there is no hit in filterCache while you experiment with those filters.

It’s worth to mention that intersecting such filters (when you specify several fqs) is not so efficient at comparison to plain Solr’s fq-s, which use bitwise AND on eight-byte words.

One more drawback of this hack is the memory-wasteful plain bitsets (like Solr’s fq-s), rather than more compact one.

OR Filters

One of the question which regularly hits the mailing list is about disjunction of cached filters i.e. if fq=SIZE:L and fq=SIZE:M are cached as two separate cache entries, can’t we reuse these bitsets in disjunction filter fq=SIZE:L OR SIZE:M and avoid caching it separately? Yes, we can! fq={!cache=false}{!parent which='SIZE:L'} OR {!parent which='SIZE:M'}.

In addition to cache introspection mentioned in previous paragraph, you can check that you do it right by placing this string to q= param and requesting debugQuery=true, in this case you should see something like this

{!cache=false}{!cache=false}ConstantScore(FixedBitSetCachingWrapperFilter(QueryWrapperFilter(SIZE:L))) {!cache=false}ConstantScore(FixedBitSetCachingWrapperFilter(QueryWrapperFilter(SIZE:M)))

Here you can see non-cached disjunction of two filters cached in perSegFilters. Last two notes from the previous paragraph (about inefficient combining and storing) are applicable here as well.

Filters 2.0

Pay attention that all this dance around filters is about using a heap to cache postings list. Providing that most times a postings list file is mmaped in according to the great advice, how much is sense in it? The reason for caching is the postings on-disk format, which is CPU-intensive while decoding on reading. This format also stores some scoring necessary data like tf which is not needed for filtering; also Solr’s filters use bitwise operation for intersection that gets some gain usually. Thus, we can think about a specialized bitset codec as a future of filters. There is a modest prototype of this approach.

NRT-Facets

What else still made Solr not NRT-friendly? Right, UnInvertedFields! What you can do with them? If you count facet on single value fields, you can use Lucene’s FieldCache by facet.method=fcs. if you deal with multivalue fields you can specify docValues for them that triggers alternative faceting engine. DocValues facets use heap data structure (OrdinalMap) that leads to pauses similar to those, which are caused by UnInvertedField, however, they should be much shorter.

The most NRT-faceting with sidecar taxonomy index is implemented in Lucene Facets Framework, but it’s still far from Solr.

The last note is that NRT doesn’t mean better throughput in general, it just tries to achieve a more predictable latency (which doesn’t mean decreasing average latency).

That’s it for today, folks.

Trust noone, watch the profiler!

Grandchildren and Siblings with Block Join

2013-12-14T21:26:00.000-08:00

To view an updated version of this post click here
The last post about block-join query parser in Solr got many comments and questions, so I decided to consider a few more complicated cases.

Lets take Solr 4.5 or above and index the data. Now the data structure is a bit more complex, so it worth a diagram:

As you can see, this hierarchical structure is similar to entity-relationship models from RDBMS world. We name those nested entities “scopes”.

Once data is indexed, use q=*:*&wt=csv&rows=100 to see how documents are aligned in blocks.

Grandchildren search

Lets consider a search for t-shirt product (parent) which has particular SKU (child) which has sufficient inventory available in particular storage. We model a storage as a child of SKU scope, and grandchild of Product scope.

Here is a search for t-shirts which have sufficient inventory (>10) of Blue XL SKUs in CA

q={!parent which=type_s:product}+COLOR_s:Blue +SIZE_s:XL +{!parent which=type_s:sku v='+QTY_i:[10 TO *] +STATE_s:CA'}

here comes the trick mentioned by David Smiley - when child query contains a space you need to wrap it into {!... v=’..’} local parameter, or extract into separate request parameter and refer to it by {!... v=$ref}...&ref=...&.

You can see that crossmatch is excluded - this query returns products 20 and 30. You can remove either QTY_i filter or COLOR_s, which brings product 10 into results.

Needless to say that possible nesting depth is unlimited. One more interesting observation about block join that it provides blazingly fast transitive closure on parent-child relationship: you can search for grandchildren and deeper descendants directly, omitting queries for intermediate scopes.

Sibling Scopes

Vendor and SKU scopes share same parent Product, and are not nested in each other.

Let’s search for t-shirts which are made by Vendor Bob and cost between $20 and $25. Here local parameter reference is necessary:

q=+{!parent which=type_s:product v=$skuq} +{!parent which=type_s:product v=$vendorq}&skuq=+COLOR_s:Blue +SIZE_s:XL +{!parent which=type_s:sku v='+QTY_i:[10 TO *] +STATE_s:CA'}&vendorq=+NAME_s:Bob +PRICE_i:[20 TO 25]

As you can see, it returns only product 20, and if you relax query eg. choose Alice or accept more expensive t-shirts, product 30 appears. Works like relational calculus!

Minor usability issue

It was raised in the mailing list thread. It seems like to-child block join queries are not user friendly enough, especially for those queries which violate orthogonality between parent filter and child query. We follow up SOLR-5553.

P.S.

Stay tuned! I’ll post about one easter egg unexpected breakthrough in Solr soon.

Solr block-join support

2013-09-05T22:23:00.000-07:00

To view an updated version of this post click here

Introduction

As you may already know block join support has been committed into Solr and will be available starting from 4.5. Here Solr catches up with ElasticSearch. Let me omit explanation and refer to these two great articles, and also mention my modest benchmark.

I performed some experiments with 4.5-SNAPSHOT obtained from NightlyBuilds and want to share my experience.

One preparation step is necessary (however it might be already there): make sure you have _root_ field in schema.xml and perSegFilter in solrconfig.xml.

Indexing

SolrInputDocument has new methods getChildDocuments()/addChildDocument() for nesting child documents into a parent document. XML and Javabin formats are now capable to transfer them. JSON support is ongoing.

Start from indexing a few t-shirts, which is a sample product-SKU hierarchy, by post.jar.

To check how blocks is laid out run match-all query with csv output. You see that parent document is placed right after children.

It is worth to be aware about implicit _root_ field which works as block identifier, all children documents obtain _root_ value from the parent’s uniqueKey field. It’s used for overwriting whole block on update.

Searching

Let’s assume we have a query matching our Red-XL children documents (SKUs aka UPCs):

q=+COLOR_s:Red +SIZE_s:XL. It returns children with ids 11 and 31.

Now let’s join from children to parent by calling special “parent” query parser.

q={!parent which='type_s:parent'}+COLOR_s:Red +SIZE_s:XL that returns parents 10 and 30, as expected.

Local parameter ‘which’ provides a filter which distinguishes parent documents from children ones. Keep in mind two important things about it:

it should not match any children documents;
it should always match all parent documents.

Pay attention that block join avoids cross-match problem - it doesn’t capture parent 20 which is a candidate for potential false positive match, as it has Red and XL SKU’s but doesn’t have SKU which is _both_ Red and XL.

This {!parent} query can be combined with any other query and filter. For example we can constrain results by brand.

q=+BRAND_s:Nike +_query_:"{!parent which=type_s:parent}+COLOR_s:Red +SIZE_s:XL"

same can be achieved by employing filter query:

q={!parent which=type_s:parent}+COLOR_s:Red +SIZE_s:XL&fq=BRAND_s:Puma

Don’t try to constraint children by filter queries, it doesn’t work, because filter queries explicitly constraint {!parent} query.

There is a “reverse” query parser for searching children documents by parent filter.

{!child of=type_s:parent}BRAND_s:Puma returns SKUs belongs to the single Puma product.

Note that even as local parameter name changed, it has the same meaning, namely supplies a parent filter.

If you are not familiar with nested queries and local parameters check the short intro.
The last but not least - it works for distributed search too!

Caveat

You always need to be quite accurate with updating blocks. They always need to be updated as whole. Let me show you one unlucky example. Let’s remove parent and left children in the index.

At first, It seems like everything still works. Children 11 and 12 are left in the index, but ToParentBlockJoinQuery somehow detects it and q={!parent which='type_s:parent'}+COLOR_s:Red +SIZE_s:XL correctly returns parent 30. However after <optimize/> is executed, deleted parent document is purged from the index and all of the sudden children 11 and 12 start to be considered as if they belong to parent 20! The same query q={!parent which='type_s:parent'}+COLOR_s:Red +SIZE_s:XL now returns 20 and 30 which is wrong! I’m afraid there are few other similar cases of wrong behavior. As a reliable workaround I suggest to send explicit deletes by query with implicit field _root_. I hope this caveat will be fixed in future.

Further Directions

Here is a few further desirable features in random order.

Faceting

Facet component for block indexes is quite useful in eCommerce. The trickiest thing is to count SKU field values and aggregate them into product counts like it was described at the earlier posts. Upd. https://issues.apache.org/jira/browse/SOLR-5743 has the patch.

FilterCache

Now there is no way to use filter query (fq=) or their combination in a child query, so it needs to read index every time, instead of intersecting bitsets from the heap. Upd. however, you can use the suggestion from next post.

Schema

Now an application should be aware about relations between documents while it indexes and searches. However, it might be much more convenient if search engine provides “flat” navigation model to a front-end. Front-end just refines search results by color and search engine figures out itself which documents to filter and which one to join.

Scoring Mode

ToParentBlockJoinQuery supports a few modes of score calculations. {!parent} parser has None mode hardcoded. Contributions are welcome! Upd: patch SOLR-5882

Group Collecting

There is nothing similar to collecting groups in FileldCollapsing. Upd. [child] doctransformer is delivered! Here is the related ticket.

UPD: DataImportHandler will be able to index children docs at 5.x. see SOLR-5147
UPD: SolrJ support for nesting children documents is provided via SolrInputDocument.getChildDocuments()

Have a good join!

Block Join Query Performs

2012-08-23T10:10:00.003-07:00

As join support is highly demanded feature, especially in eCommerce, I repeated Erick’s benchmark with proposed block join support for Solr, and want to share my observations.

Definitions

For this post and in future let’s distinguish Join and Block Join. Most technical details are covered in Martijn talk.

Data

I have a single segment 55Gb index with 27 M docs - about a million parent documents, each having five children. I ran worst case from Eric’s benchmark, where join field has many unique values. It’s a worst case for Join, but not for BlockJoin.

Tools and Procedure

I used Solr Meter with slightly modified RandomExecutor, which tries to keep specified rate of queries per time period. I prefer this constant throughput model, rather than virtual user’s model. Solr-Meter allows gently ramp up load and empirically find the saturation point. It provides several useful statistics and charts.

Also I attached iostat traces to show system load during tests.

I have 2.4 GHz Core i5 laptop with 8G RAM and good old 5400 rpm HDD onboard.

Query Result Cache and Filter Cache has been disabled, Document Cache was enabled and shows hit ratio about 0.5. See more about these Solr bolts and nuts.

My goal is to find maximum throughput, which doesn’t impact search latency.

Join

A queries look like

q=text_all:(patient OR autumn OR helen)&fl=id,score&sort=score desc&fq={!join from=join_id to=id}acl:[1303 TO 1309]

I did several measurements, but decided to post this particular histogram (caveat, it’s not a timeline). You can see that join almost never runs for less than a second, and CPU saturates with 100 requests per minute. Adding more queries harms latency.

From iostat trace you can see that there is no I/O activity, all index is cached in RAM via memory mapped files magic. I’ll tell about it later.

BlockJoin

I sen the same queries with block join.

q=text_all:(patient OR autumn OR helen)&fl=id,score&sort=score desc&fq={!parent which=kind:body}acl:[1303 TO 1309]

Here are latency timeline and statistics.

You see it! Search now takes a few tens of milliseconds and survives with 6K request per minute (100 qps). And you can notice plenty of free CPU!

Culprit

We can check where Join spends so much CPU by simple jstack:

java.lang.Thread.State: RUNNABLE

at o.a.l.codecs.BlockTreeTermsReader$FieldReader$SegmentTermsEnum.docFreq(BlockTreeTermsReader.java:2098)

at o.a.s.search.JoinQuery$JoinQueryWeight.getDocSet(JoinQParserPlugin.java:338)

I/O exercises

You can notice that the last screenshot was taken with zero I/O rate. How could it be? I ran two tests to understand how cache index files impacts performance. You can consider it as lab exersize for the great lecture Use Lucene’s MMapDirectory on 64bit platforms, please!

First of all, let’s explain how 55G index can ever be cached in just 8G RAM. You should know that not all files in your index are equally valuable (it other words - tune your schema wisely). In my index frq file is 7.7G and tim file is 427M only, and it’s almost all what’s needed for these queries. Of course, a file which stores primary key values is also read, but it doesn’t seem significant.

Here is search latency timeline taken after flushing filesystem cache with 50 threads configured in servlet container. Right after flush search takes more than 7 seconds.

This timeline shows how search time decreases while cache gets warmed, but it’s taken with 4 thread limit in servlet container. All searches are sub-second. Although four threads server isn’t able to reach 6K requests per minute due to “idle” limit, it speedups much faster than 50 thread server with I/O bottleneck.

I/O numbers say that we hit HDD limit. My “lab machine” usually shows 100-200 tps (I/O transactions per second), but I saw even 300 once. First and third columns: KB/t - kilobytes per transaction and MB/s - IO throughput shows how efficiently it reads. To get peak numbers run cat * >/dev/null in folder with your index files, and check iostat while it sequentially reads.

One more interesting observation is related to KB/t. My first tests showed really slow search and low I/O utilization about 4 KB/t. I was really upset until realized that on my OS, which is not Linux,FSDirectory chooses NIOFSDirectory. After I explicitly specified MMapDirectory, in according to Uwe advice, cache magic starts working for me, and I’ve got the great result above.

To block or not to block (join)?

From my point of view BlockJoin is the most efficient way to do the join operation, but it doesn’t mean you need to get rid of your solution based on the other one (slow) Join. The room for Join is frequent children updates, and small indexes, of course.

Happy (block) joining!

Ignoring test failures at CI

2012-05-23T13:30:00.000-07:00

Problem

Today, I want to talk about one obvious issue which occurs when your code and tests are written by the different people and you have a properly established CI process. In this scenario, tests appear in VCS first, because without a test the code can’t be committed, but this test breaks the build. Obviously, test author skips it or disables it from CI test suite until this functionality is actually implemented. I believe that this is not the best practice, because it leads to a lot of wasted efforts from both dev and QA teams. Let’s look at what’s going on in typical project team:

Commit

Developer checks out the disabled test for his new feature from VCS, runs it, and checks that the code is ready. Now he’s able to commit the code. He does it, but unfortunately makes two usual mistakes: he performs one-line-improvement right before commit without full test run (of course, what can possibly go wrong?); and he forgets to commit one property file. Doesn’t it happen to you? Really?

Test

Then he pings the test’s author, - Hey! I’ve done it. Check your test pls. Tester needs to run a private build to verify that all code changes have been committed, and then enables the test for CI. If tester skips the private build phase, which can include pulling snapshot or build and creating deployment, you’ll have CI failure without genuine code issue.

What it should be

Just free tester from the unnecessary private build and testing cycle. Let CI work for you. Don’t skip test from CI suite, let it run and fail without impacting the build status. Tester sets the expectation for functionality, and let developers reach it, without a necessity to verify an uncommitted code.

Tooling

JUnit has only one workaround - assumeTrue, which allows to mark failed test as skipped. To introduce a fancier way you need to write your Runner.
UPD: there is @Rule feature gives the simple solution. Thanks to the thread!

TeamCity has nice looking “mute” feature. Nice work, JetBrains!

TestNG has something along these lines. It works fine, but surefire doesn’t support it doesn’t support it.

JBehave has ignoreFailureInView property, but it belongs to whole suite not for paticular test.

Credits

I realized that some time ago but decide to post after found the same concern in the mail thread.

Highlights from our OpenStack-specific blog

2011-10-25T10:28:00.000-07:00

A few highlights from our OpenStack blog:

How our RHEL port is built and tested, using Gear + Mock

Setting up VPN for projects with CloudPipe

Using SSH keys with novaclient

Improving novaclient CLI: boot a server with specific SSH key

Also, for those who do not follow our OpenStack blog closely, OpenStack Diablo release is out for both RHEL and CentOS (version 6, as usual). Sources are available as well.

Solr Experience: search parent-child relations. Part III

2011-10-03T01:16:00.001-07:00

In the previous posts (part I and part II) I presented challenges in searching parent-child relations by Solr, a couple of workarounds and handsome final solution - SpanQueries.

In this post I will describe the infrastructure for SpanQueries we’ve built inside Solr . It includes indexing, query parsing (creating SpanQueries), caching filter queries, faceting and sorting.

Indexing

Fist of all I should say that we use SolrJ - embedded Solr server, and this section is about adding documents into Solr by its’ Java API only.

If you put a collection of values into SolrInputDocument.addField(“field”, values) with termPositions=”true” in schema.xml, Solr will interpret them as several different terms for one field and for each value it sets position to 0.

The straightforward approach is adding all values as one text string (e. g. “red blue green”) and using analyzer (StandardAnalyzer works fine), which adds proper term positions into the index. In this case, if we want to index several numbers, we have to add them as one string, e. g. “123.45 42.15 98.27”. It’s not useful, so we implemented field types for String, Integer, Double and Float. They create Field instance with special TokenStream, which uses List as a source and saves positions (indexes in List).

Parsing SpanQueries

By default Solr uses LuceneQParser plugin to parse user queries and create Lucene Queries. We created a wrapper for it - SpanQParserPlugin - which transforms regular BooleanQueries and TermQueries into SpanQueries. Then we registered it in solrconfig.xml:
    <queryParser name="span" class="com.griddynamics.solr.spans.SpanQParserPlugin"/>

This plugin transforms BooleanQuery with AND clause into SpanNearQuery(...) and BooleanQuery with OR clause into SpanOrQuery.
As result the query ”fq={!span tag=spanFQ}+color:Red +size:XL” is parsed into:
SpanNearQuery(
    SpanTermQuery("color", "Red”),
    FieldMaskingSpanQuery(
              SpanTermQuery("size", "XL"),
              “color”
    ), -1, false
)

Here {!span} is defType local param. It says to Solr to use SpanQParserPlugin and spanFQ is a tag we will use for faceting later.
Please be informed that there are a couple of better ways to extend query parsing.

Filter queries caching

Solr caches docSets (materialized FilterQuery results, which are intersected on searching) and docLists (ranked query results that store document lists). But they are not enough for us, because for faceting we need spans, which passed the filter.

We’ve created SpanQueryFilterCache for this - it’s similar to SpanFilterResult but uses primitives and arrays instead wrappers and collections. It stores spans which were found by SpanQuery in the user cache provided by Solr. To get spans we call SpanQueryFilterCache.getSpans(spanQuery, solrIndexSearcher) that initializes the cache lazily and gets spans by spanQuery key.

Faceting

I suppose it’s the most interesting part of this article.
Standard field faceting mechanism calculates counts of documents that contain field value. It doesn’t fit for us, because we need to count facets on the matched spans only (parts of a document).

To count span facets we made a special component SpanFacetComponent, which is activated with the parameter span.facet.field.

The query for searching Red sweaters and count facets for size and color fields looks like this:

q={!span tag=spanFQ}+color:Red&facet=true&span.facet.field={!by=spanFQ aggOp=unique}color&span.facet.field={!by=spanFQ aggOp=unique}size

And we have a Product, which passes the filter:

Only two of its’ Items pass the filter and must be counted for faceting. The tag “spanFQ” (see above) gets SpanQuery instance and uses SpanQueryFilterCache to enumerate matched spans. It works for color and size fields, because span doesn’t have a field and we can count size facet by spans matched by color filter. For counting facets we need field values on matched spans. We get from the use forward view of data - UnInvertedSpans (it’s allusion to UnInvertedField; it stores mapping {(docId, spanNum) -> {termNum}}).

We have two Items, which passed the filter, but we have a constraint that a single document increases facet count for a value only once i.e. document gives a set of values (not a bag) for facet counts. The match above gives {Red,XL,XXL}. To determine which span should be counted we use aggOp (aggregation operation) parameter that can be one of three values:

unique - each unique value increases facet count;
first - only first span value increases facet count;
last - only last span value increases facet count.

The last two operations are used for calculating min/max price (here we use natural ordering enforced during indexing, instead honest query time min/max). It’s worth to implement min/max operations also.

Sorting

Our Product can have several prices. To sort by price we need to use different values depending on sorting direction: for ascending - min price, for descending - max price.
The solution is store prices aligned by positions and SpanQueries to get a price values for sorting. During indexing we put prices in the Product document in ascending order. In query time we use SpanQuery and UnInvertedSpans to get spans with prices and then our MultiValueFieldComparatorSource uses value from first (on asc) or last (on desc) span for sorting. For example, our query with additional price filter and sorting by price field will be:

q={!span tag=spanFQ}+color:Red

&fq={!span tag=priceFQ}+price:[5 TO 15]

&sort.field={!bySpanFQ=priceFQ}price ASC

Conclusion

That’s all. We hope our experience and ideas will help someone to resolve his or her issues about parent-child relations. In future we want to try storing two or more terms for one field in one position - by this way we want to handle the same issues with multi-valued field.
We also work on deeper understanding of the problem and building a powerful model of nested documents on inverted lists. One of the last findings is that ‘false positive matching on multi-value fields’ is well-known Fan Trap in ER-modelling.

There is a considerable alternative approach LUCENE-3171. It’s a little bit raw at the moment, but the idea is promising.

Solr Experience: search parent-child relations. Part II

2011-07-27T23:32:00.001-07:00

In the previous post I presented an e-Commerce site that sells sweaters. I showed how we tried to implement Faceted Navigation with Solr, found the problem with the multi-valued field for searching parent-child relations. I also proposed a workaround that solves the problem but that is far from perfect.

In this post I’ll describe the ultimate solution - SpanQueries.

SpanQuery

SpanQueries are purposed for proximity search, which considers terms’ positions inside text. Lucene can index terms’ positions in addition to terms. For example, “crazy cat and crazy dog” gives us the following inverted index:

Word “and” is excluded as stop word.

SpanQuery considers that terms’ positions during searching. Span - is a term position range or tuple that contains document ID and start and end positions. A term can have several spans per document. There is a basement method SpanQuery.getSpans(...), which returns iterator for matched documents and spans.

SpanQuery - is an abstract class, there are several its descendants. You can find their description in the post in the Lucid Imagination blog and "Lucene In Action" book.

We are interested in three of them:

SpanTermQuery - finds all spans by the term;
SpanNearQuery - combines several SpanQueries considering the distance between matched spans;
FieldMaskingSpanQuery - masks SpanQuery by one field as query by another field.

Now let’s take a look at how do we use this SpanQueries to search parent-child relations.

Parent-child relations with SpanQueries

We index Products in a way when attributes of each Item are located on the same position:

Combining the SpanTermQueries with FiledMaskingSpanQuery and putting them inside SpanNearQuery allows searching the intersections of the terms' positions, and properly find the Product, which contains the specified Item (color:Red and size:XL):
SpanNearQuery(
    SpanTermQuery("color", "Red”),
    FieldMaskingSpanQuery(
               SpanTermQuery("size", "XL"),
               “color”
    ), -1, false
)

This query returns the only documents, which have color:Red and size:XL at the same position i.e. belonging to the same Item:

The third product (Style&co.) is not returned, because its' terms "Red" and "XL" are located in different positions.

We've got what we want out-of-the box. But there is another problem: Solr doesn't have any infrastructure for supporting SpanQueries. In the next post I will tell about how do we bring SpanQueries into the Solr, including interesting issues of caching, faceting and sorting.

P. S.: recently we found the similar approach had been proposed and ongoing work in Lucene core (see LUCENE-2454, LUCENE-3133, LUCENE-3171). Looking forward for incorporating this feature in Solr.

Spring Nested - Part III

2011-07-02T11:26:00.000-07:00

In the previous posts I, II I told you how we came up with our own Service Locator framework based on Spring. Frankly speaking, a root application context creates child application contexts and keeps a services registry, where the child contexts advertise and look up service beans by names. Today I will tell you about two vital features.

Handling Web Requests

We use Spring MVC to expose platform services via Web. To handle Web requests WAR should has handlers or controllers declared in Spring application context. In our platform all business logic resides in component contexts aka child contexts. Therefore, a component developer declares request handlers and controllers in component context, but Spring MVC’s DispatcherServlet looks for request handlers in the root context only. So, we need to pass the request to these controller/handler beans declared in the target child context. We went through three approaches below one by one:

the first was really explicit: child contexts publish their Web request handlers to the service registry. Root context contains a special request handlers, every of which delegates a request to a handler obtained from service registry by the specified name. So, we had to amend the root config xml when a new web handler appears in any component;
then, we introduced the handler mapping registry in the root context. Child contexts have factory beans register the child request handlers in that registry. Thus, the registry can handle a request by looking up a child handler by an URL and delegating request to it. That’s better than the first approach because we don’t need to update the root config xml on introducing a new request handler. But it was too far from non-invasive approach, i.e. we had to consider these declarations when add a new handler;
the final approach is completely implicit: root context has the same child handler mapping registry (url -> handler), but it’s populated automatically during scanning the child contexts for handler/controller beans. Then, this mapping registry handles requests by delegating them to particular child handlers found by an url. As result, component developer doesn’t care about the framework when he delivers a new Web request handler.

In contrast to Spring DM way we have a single WAR with the single DispatcherServlet contains the several Web components.

Component Initialization and Dependencies

It’s the most feature I am proud of. To instantiate all child contexts we need to know a correct initialization sequence - which child context goes after which. Initially we relied on the list of config XMLs explicitly provided in the root context. Then, we found problems with this straightforward approach, e.g.

absence or fail of one export breaks the related lookup;
a looked up bean (which is actually a proxy) can be accessed before its’ context initialization.

We decided to implement Dependency Analyzer that verifies dependencies across child contexts before any child context initialization.

How have we done it? We rejected the idea of parsing Spring context XMLs to analyze dependencies, just because we had two XML formats already. Spring has quite extensible and elegant design: BeanDefinitionReader parses XML and passes BeanDefinitions to BeanDefinitionRegistry. For default flow BeanDefinitionRegistry is an ApplicationContext, which creates singleton bean instances etc. But we can run this routine against a fake one: SimpleBeanDefinitionRegistry that just keeps bean definitions in a map . Then analyzer can iterate through bean definitions, recognize exports and lookups, verify it, raise concerns and/or arrange initialization order. Here is the list of rules which analyzer enforces now:

verifies that an every bean class is exist in classpath;
warns unnecessary exports (without any lookup);
prohibits imports without a matching export;
prohibit dependency cycles between contexts (a but allows to resolve them manually in “god mode”);
orders child context initialization considering exports before to imports;
finds a minimal list of the components which are required for running the given sub-set of services (transitively finds the dependent contexts);
skips the dependent contexts after a some context initialization failure;
outputs the derived component dependencies graph into debug log in Graph Viz format.

Some of these features just spot the trivial errors and reduce the number of log lines to look through. Remaining features provide a flexible and robust container for our platform.

Finally I’d like to spot a significant difference between Spring DM and Spring Nested. Spring DM has an asynchronous ad-hoc initialization which is too complex and inconvenient sometimes. Spring Nested proposes a single thread deterministic initialization. It’s rigid enough - prohibits cycles, but flexible - you code against services, don’t care about a component initialization sequence. And it’s developer friendly: you shouldn't change you Spring habits much; troubleshooting is easy as possible with the reduced logs and the preliminary checks.

If you accept some simplifications, which has been made in Spring Nested design this framework can help you with your large Spring application.

The Real Life Application

Here is the modules dependencies graph of our application that is built with Spring Nested. This graph is derived from the services references by the dependency analyzer and logged in Graph Viz text format on startup.

I smudged the component names at this picture just to avoid NDA aspects.

Further Plans

We want to open its’ source. Please let us know if you are interested in it or leave a valuable feedback and ideas.

This framework is available on https://github.com/griddynamics/banshun

Solr Experience: search parent-child relations. Part I

2011-06-06T07:15:00.000-07:00

Typical e-Commerce sites provide a catalog of products with filtration (or search by criteria). We implement such catalog with Solr search server based on Apache Lucene library.

A catalog entries usually have parent-child relations and search must consider these relations. Unfortunately Solr documents are flat and some straightforward approaches e.g. several indexes, denormalization have been rejected because of efficiency and implementation efforts.

In this post I describe the problem and some possible approaches.

E-Commerce site

Product is the model of any goods which are sold on the site. A product has attributes like Brand, Occasion etc. You can’t buy a Product, you can buy an Item - a concrete instance of the Product, which has such attributes like Color, Size, Length, etc. Also every Item shares Product’s attributes.

For example, if you search "Nizza Hi" on www.shopadidas.com site, you see different sneakers of the single model ("Men's Originals Nizza Hi Shoes"). They have different colors, therefore they are Items. Then search the same on Macys.com - you see the only pair of sneakers. If you look to its' page, you see that there are several colors available. The Macys.com search result contains Product, not Items.

Let's have a site, where we sell sweaters with different colors and sizes (Items). There are three brands and each brand is presented as separate Product. The list of all available Items:

Alfani:
- Red - XL
- Red - XXL
- Blue - XL
- Green - L
- Green - XXL
Calvin Klein:
- Red - XL
- Blue - M
- Blue - L
- Green - M
- Green - XL
Style&co.:
- Red - M
- Blue - XXL
- Blue - XL
- Green - S

To provide a better usability we need to show three Products instead of twelve Items, and allow to filter them by color and size i.e. to provide Faceted Navigation.

For example, a client need Red shoes with XL size. Therefore, the site must show Products that contain Items with color:Red and size:XL only:

Alfani:
- Red - XL
- Red - XXL
- Blue - XL
- Green - L
- Green - XXL
Calvin Klein:
- Red - XL
- Blue - M
- Blue - L
- Green - M
- Green - XL
Style&co.:
- Red - M
- Blue - XXL
- Blue - XL
- Green - S

I’ve highlighted with bold font Items and Products passed the filter. The third Product (Style&co.) doesn’t match the filter. Although it has Items with Red color and XL size, but it doesn’t contain any Item with both Red color and XL size we are looking for.

Attemt #1: Two indexes

The first intention is using Solr as database: to create separate indexes for Items and Products. Thus we can get the result with two Solr-queries:

find all Items passed the filter;
find all Products that contain Items we got on the previous step.

The logic seems working, but further investigation has shown two problems:

Pagination - usually we want to show not the whole result, but only 10, 30, 50, or 100 Products. But it's very expensive to query all Items (number of them can be huge) and than pass them inside the second query for getting first N Products;
Faceting - we have to write a lot of custom code around Solr to calculate all facet counts from the result of the first query. Also the first query result must contain product ID, which is expensive.

Thus this approach was rejected.

Attempt #2: Denormalization

Denormalization is creating the only index for Items. It's similar to the previous approach, but there are two differences:

productID field is not stored field, because we need it only for querying;
Faceting requires custom code too, but it can be placed inside Solr within own Components. They use Solr/Lucine internal data structures and much faster than post-processing the result.

There is another problem - result collapsing. We need Products as final result, not Items. Solr’s FiledCollapsing can be used for this but it has a little bit different purpose. We ended up with our own collapser.

Thid approach is not flexible: small requirements changes impact the codebase a lot.
We've got that the document granularity should match the search result.

Attempt #3: Item Attributes' Promotion

Then we came back to the Product index. The question was how to index Items inside Product documents with keeping their identity for filtering. Here we come to the attributes’ promotion approach: item’s attributes (sub-documents) are promoted into the multi-value document fields.
But doing it straightforward we met the false positive multi-value field match problem. Let's look to Lucene documents:

I highlighted with bold font the result for query color:Red and size:XL. The third Product “Style&co.” is presented in the result table, but it must be filtered out (see our example above), because it doesn’t contain any Items with both Red color and XL size we are looking for.

After we realized this problem, we moved to...

Attempt #4: Term Encoding

The solution was quite brave - we solved it with an accurate term encoding. We introduced a composite terms for keeping an Item identity. For example:

Alfani:

Red - XL : RedXL
Red - XXL : RedXXL
Blue - XL : BlueXL
Green - L : GreenL
Green - XXL : GreenXXL

As result you can find a document by an item attributes combination and avoid a false match for absent items like RedXL. We also had to generate all subsets of attribute values. Thus the full list of generated terms for our example looks like:

Red, XL, RedXL, XXL, RedXXL, Blue, BlueXL, Green, L, GreenL, GreenXXL.

The findability is solved (because Style&co. doesn't have term RedXL, which we are looking for), but we still needed a proper faceting. Honestly speaking we faceted such composite fields with Tokenizer and HashMap (a kind of brute force).

We knew that this approach is far from perfect due to performance and scalability issues and the complex processing in query time. That's why we continued to find a more robust approach.

Part I: Conclusion

Keep in mind that the described issue takes place with almost any case, when your search result contains the documents with any form of hierarchy. We actually met two instances of that:

product document has an item sub-documents (which is not presented as a separate documents itself);
product documents are grouped by another documents reside in the index;
document has associations with another entity encoded by a term (it seems like relation sub-document).

In the next part I will introduce the silver bullet - SpanQueries.

Understanding GC pauses in JVM, HotSpot's CMS collector.

2011-06-02T19:09:00.000-07:00

(previous artictle "Understanding GC pauses in JVM, HotSpot's minor GC")

Concurrent Mark Sweep (CMS) is one of HotSpot JVM low pause garbage collectors. CMS can do most of its work for reclaiming memory concurrently with application (without stopping it). But still it requires few stop-the-world pauses to make its work. This article will explain nature of these pauses and how to minimize them.

Basics of concurrent mark sweep

HotSpot’s CMS is a generational collector, it means that heap is separated into young and old (tenured) space and these spaces are collected independently. For young space collection usual HotSpot’s copy collector is use (see previous article about HotSpot’s young space collector). Concurrent Mark Sweep is used only to collect old space. To enable of using CMS collector you have to specify –XX:+UseConcMarkSweepGC in JVM’s command line.

CMS collection cycle has following phases:

Initial mark – this is stop-the-world phase while CMS is collecting root references.
Concurrent mark – this phase is done concurrently with application, garbage collector traverses though object graph in old space marking live objects.
Concurrent pre clean – this is another concurrent phase, basically it is another mark phase which will try to account references changed during previous mark phase. Main reason for this phase is reduce time of stop-the-world remark phase.
Remark – once concurrent mark is finished, garbage collector need one more stop-the-world pause to account references which have been changed during concurrent mark phase.
Concurrent sweep – garbage collector will scan through whole old space and reclaim space occupied by unreachable objects.
Concurrent reset – after CMS cycle is finished, some structures have to be reset before next cycle can start.

Unlike most other garbage collectors, CMS does not do compaction of heap space. Instead of moving objects to make unoccupied space continuous, CMS keeps lists of all fragments of free memory. This way CMS is avoiding cost associated with relocating of live objects (and relocating of objects is expensive operation which require stop-the-world pause), but as down size of this heap space is prone to fragmentation. To minimize risk of fragmentation CMS is doing statistical analysis of object’s sizes and have separate free lists for objects of different sizes.

Length of CMS pauses

CMS itself has only two pauses, but your application will also experience pauses of young space collector which is working in conjunction with CMS. See previous article about pauses of young space collector.

Initial mark

During initial mark CMS should collect all root references to start marking of old space. This includes:

References from thread stacks,
References from young space.

References from stacks are usually collected very quickly (less than 1ms), but time to collect references from young space depends on size of objects in young space. Normally initial mark starts right after young space collection, so Eden space is empty and only live objects are in one of survivor space. Survivor space is usually small and initial mark after young space collection often takes less than millisecond. But if initial mark is started when Eden is full it may take quite long (usually longer than young space collection itself).

Once CMS collection is triggered, JVM may wait some time for young collection to happen before it will start initial marking. JVM configuration option –XX:CMSWaitDuration= can be used to set how long CMS will wait for young space collection before start of initial marking. If you want to avoid long initial marking pauses, you should configure this time to be longer than typical period of young collections in your application.

Remark

Most of marking is done in parallel with application, but it may not be accurate because application may modify object graph during marking. When concurrent marking is finished; garbage collector should stop application and repeat marking to be sure that all reachable objects marked as alive. But collector doesn’t have to traverse through whole object graph; it should traverse only reference modified since start of marking (actually since start pre clean phase). Card table (see card marking write barrier) is used to identify modified portions of memory in old space, but thread stacks and young space should be scanned once again.

Usually most time of remark phase is spent of scanning young space. This time will be much shorter if we collect garbage in young space before starting of remark. We can instruct JVM to always force young space collection before CMS remark. Use JVM parameter –XX:+CMSScavengeBeforeRemark to enable this option.

Even is young space is empty, remark phase still have to scan through modified references in old space, this usually takes time close to normal young collection pause (due scanning of old space done during young collection is similar to scanning required for remark).

When CMS collection starts?

Unlike stop-the-world old space collectors, CMS collection cycle should start before old space become full. CMS collection is triggered when amount of free memory in old space falls below certain threshold (this threshold can be chosen by JVM based of runtime statistics or set via parameters) and actual start of CMS collection cycle may be delayed until next young collection.

Normally objects are allocated in old space only during young space collection (which may promote some objects to old space). So CMS cycle usually starts right after young space collection, which is good because init mark pause will be very small.

But in certain cases object may be allocated directly in old space and CMS cycle could start while Eden has lots of objects. In this case initial mark can be 10-100 times slower which is bad. Usually this is happening due to allocation of very large objects (few megabyte arrays). To avoid these long pauses you should configure reasonable –XX:CMSWaitDuration.

Configuring fixed threshold for CMS start

You can set fixed threshold for olds space occupation for triggering CMS cycle by using JVM options ‑XX:+UseCMSInitiatingOccupancyOnly ‑XX:CMSInitiatingOccupancyFraction=70 (this will force CMS cycle to start when more than 70% of old space is used).

Explicitly invoking CMS cycle

You can also configure JVM to start CMS cycle by invocation of System.gc() by ‑XX:+ExplicitGCInvokesConcurrent command line option.

Full GC with CMS

If CMS cannot free enough in old space, JVM may fallback to compacting collector. Compacting collector will force stop-the-world pause so it can be considered emergency case. Normally you would like to avoid full GC and long stop-the-world pause associated with it. Full GC may happen either if CMS is not fast enough for dealing with garbage (or collection cycle has been started too late) or due to fragmentation of old space (there is no large enough continuous space for object to be allocated). Also it is possible that you just didn’t give JVM enough memory and after full GC it will through OutOfMemoryExpection anyway.

Permanent generation collection

One of reasons why CMS may end up in full GC is garbage in permanent space. By default CMS does not reclaim unused space in permanent space. If your application is using multiple class loaders and/or reflection you may need to enable collecting of garbage in permanent space. JVM option ‑XX:+CMSClassUnloadingEnabled will allow CMS collector to clean permanent space. Remember that objects in permanent space may have references to normal old space thus even if permanent space is not full itself, references from perm to old space may keep some dead objects unreachable for CMS if class unloading is not enabled.

Utilizing multiple cores

CMS has multiple phases. Some of them are concurrent; others are stop-the-world pauses but may be executed in parallel to compressed application freeze time.

‑XX:+CMSConcurrentMTEnabled – allows CMS to use multiple cores for concurrent phase.

‑XX:+ConcGCThreads= – specifies number of thread for concurrent phases.

‑XX:+ParallelGCThreads= – specifies number of thread for parallel work during stop-the-world pauses (by default it equals to number of physical cores).

‑XX:+UseParNewGC – instructs JVM to use parallel collector for young space collections in conjunction with CMS.

Comming soon:

Tuning CMS collector for large IMDG storage nodes

Understanding GC pauses in JVM, HotSpot's minor GC.

2011-06-01T03:04:00.000-07:00

Stop-the-world pauses of JVM due to the work of garbage collector are known foes of java-based applications. HotSpot JVM has a set of very advanced and tunable garbage collectors, but to find optimal configuration it is very important to understand an exact mechanics of garbage collection algorithms. This article is first of the series explaining how exactly GC spends our precious CPU cycles during stop-the-world pauses. An algorithm for young space garbage collection in HotSpot is explained in this post.

Structure of heap
Most of modern GCs are generational. That means that java heap memory is separated into few "spaces". Spaces are usually distinguished by “age” of resident objects. Objects are allocated in young space, then eventually copied to old (or tenured) space, if they survive long enough. This principle is based on hypothesis that most object “die young”, i.e. majority of objects become garbage shortly after being allocated. All HotSpot garbage collectors separate memory into 5 spaces (though for G1 collector spaces may be not continuous).

• Eden are space there objects are allocated,
• Survivor spaces are used to receive object during young (or minor GC),
• Tenured space is for long lived objects,
• Permanent space is for JVM own objects (like classes and JITed code), it is behaves just like tenured space so we will ignore it for rest of article.
Eden and 2 survivor spaces together are called young space.

HotSpot GC algorithms overview

HotSpot JVM is implementing few algorithms for GC which are combined in few possible GC profiles.

• Serial generational collector (-XX:+UseSerialGC).

• Parallel for young space, serial for old space generational collector (-XX:+UseParallelGC).

• Parallel young and old space generational collector (-XX:+UseParallelOldGC).

• Concurrent mark sweep with serial young space collector (-XX:+UseConcMarkSweepGC

–XX:-UseParNewGC).

• Concurrent mark sweep with parallel young space collector (-XX:+UseConcMarkSweepGC
–XX:+UseParNewGC).

• G1 garbage collector (-XX:+UseG1GC).

All profiles except G1 are using almost same young space collection algorithms (with serial vs parallel variations).

Write barrier

Key point of generational GC is what it does need to collect entire heap each time, but just portion of it (e.g. young space). But to achieve this JVM have to implement special machinery called “write barrier”. There 2 types of write barriers implemented in HotSpot: dirty cards and snapshot-at-the-beginning (SATB). SATB write barrier is used in G1 algorithms (which is not covered in this article). All other algorithms are using dirty cards.

Dirty cards write barrier

Principle of dirty card write-barrier is very simple. Each time when program modifies reference in memory, it should mark modified memory page as dirty. There is a special card table in JVM and each 512 byte page of memory has associated byte in card table.

Young space collection algorithm

Almost all new objects (there are few exception when new object can be allocated directly in old space) are allocated in Eden space. To be more effective HotSpot is using thread local allocation blocks (TLAB) for allocation of new objects, but TLAB themselves are allocated in Eden. Once Eden becomes full minor GC is triggered. Goal of minor GC is to clear fresh garbage in Eden space. Copy-collection algorithm is used (live objects are copied to another space, and then whole space is marked as free memory). But before start collecting live objects, JVM should find all root references. Root references for minor GC are references from stack and all references from old space.

Normally collection of all reference from old space will require scanning through all objects in old space. That is why we need write-barrier. All objects in young space have been created (or relocated) since last reset of write-barrier, so non-dirty pages cannot have references into young space. This means we can scan only objects in dirty pages.

Once initial reference set is collected, dirty cards are reset and JVM starts coping of live objects from Eden and one of survivor spaces into other survivor space. JVM only need to spend time on live objects. Relocating of object also requires updating of references pointing to it.

Finally we have Eden and one survivor space clean (and ready for allocation) and one survivor space filled with objects.

Object promotion

If object is not cleared during young GC it will be eventually copied (promoted) to old space. Promotion occurs in following situations:

• -XX:+AlwaysTenure makes JVM to promote objects directly to old space instead of survivor space (survivor spaces are not used in this case).

• once survivor space is full, all remaining live object are relocated directly to old space.

• If object has survived certain number of young space collections, it will be promoted to old space (required number of collections can be adjusted using –XX:MaxTenuringThreshold option and
–XX:TargetSurvivorRatio JVM options).

Allocation of new objects in old space

It would be beneficial if we could possibly allocate long lived objects directly in old space. Unfortunately there is no way to instruct JVM to do this for particular object. But there are few cases when object can be allocated directly in old space.

• Option -XX:PretenureSizeThreshold=n instructs JVM what all objects larger than n bytes should be allocated directly in old space (though if object size fits TLAB, JVM will allocate it in TLAB and thus young space, so you should also limit TLAB size).

• If object is larger than size of Eden space it also will be allocated in old space.

Unlike application objects, system objects are always allocated by JVM directly in permanent space.

Parallel execution

Most of task during young space collection can be done in parallel. If there are several CPUs available, JVM can utilize them to compress duration of stop-the-world pause during collection. Number of threads can be configured in HotSpot JVM by –XX:ParallelGCTreads=n parameter. By default JVM will choose number of thread by number of available CPU. As expected, serial version of collector will ignore this parameter because it can use only one CPU. Using parallel collection reduces time of stop-the-world pause by factor close to number of physical cores.

Measuring stop-the-world pause for young collection

Young space collection happens during stop-the-world pause (all non-GC-related threads in JVM are suspended). Wall clock time of stop-the-world pause is very important factor for applications (especially applications requiring fast response time). Parallel execution affects wall clock time of pause but not work effort to be done.

Let’s summarize components of young GC pause. Total pause time can be written as:

T_young = T_{stack_scan} + T_{card_scan} + T_old__scan+ T_copy ; there T_young is total time of young GC pause, T_{stack_scan} is time to scan root in stacks, T_old__scan is time to scan roots in old space and T_copy is time to copy live objects (1).

Thread stack are usually very small, so major factors affecting time of young GC is T_old__scan and T_copy.

Another important parameter is frequency of young GC. Period between young collections is mainly determined by application allocation rate (bytes per second) and size of Eden space.

P_young = S_eden / R_alloc; there P_young is period between young GC, S_eden is size of Eden and R_alloc is rate of memory allocations (bytes per second) (2).

T_{stack_scan}– can be considered application specific constant.
T_{card_scan}– is proportional to size of old space. Literally, JVM have to check single byte of table for each 512 bytes of heap (e.g. 8G of heap -> 16m to scan).

T_old__scan – is proportional to number of dirty cards in old space at the moment of young GC. If we assume that references to young space are distributed randomly in old space, then we can provide following formula for time of old space scanning.

; there S_old is size of old space and D, k_card and n_card are coefficients specific for application (3).

T_copy– is proportional to number of live objects in heap. We can approximate it by formula:

There k_copyis effort to copy object, R_{long_live} is rate of allocation of long lived objects, k_survive = R_{long_live}/ R_alloc(k_survive usually very small), and k_tenure is a coefficient to approximate aging of object in young space before tenuring (k_tenure ≥ 1) (4).

Now we can analyze how various JVM options may affect time and frequency of young GC.

Size of old space. Size of old space is affecting T_{card_scan} and T_{old_scan} part of young GC pause time according to formulas above. So we as we are increasing size of old space (read total heap size) time of young GC pauses will grow and it can be helped. After certain size of heap (usually 4-8 Gb) time of young collection is dominated by T_{card_scan} (technically T_copy can be even greater than T_{card_scan}, bur it usually can be controlled by tuning of GC options).

HotSpot JVM options: -Xmx=n, -Xms=n

Size of Eden space. Period between young GC is proportional to size of Eden. T_copy is also proportional to size of eden but in practice k_survive can be so small that for some applications we can forget about Tcopy. Unfortunately time between young GC will also affect coefficient D in equation (4). Though dependency between D and P_young is very application specific, increasing P_young will increase D and as a consequence T_{scan_old}.

HotSpot JVM options: -XX:NewSize=n, -XX:MaxNewSize=n

Size of survivor space. Size of survivor space puts hard limit of how much objects can stay in young space between collections. Changing size of survivor space may affect k_tenure(or mat not, e.g. if k_tenureis already 1).

HotSpot JVM options: -XX:SurviorRatio=n

Max tenuring threshold and target survivor ratio. These two JVM options also allow artificially adjust k_tenure.

HotSpot JVM options: -XX:TargetSurviorRatio=n, -XX:MaxTenuringThreshold=n , -XX:+AlwaysTenure, -XX:+NeverTenure

Pretenuring threshold. For some applications using pretenuring threshold could reduce k_survive due to allocation of long lived object directly in old space.

HotSpot JVM options: -XX:PretenureThreshold=n

(Next article "Understanding GC pauses in JVM, HotSpot's CMS collector.")

Comming soon:

Tuning CMS collector for large IMDG storage nodes

Running 200 VM instances on OpenStack Compute

2011-05-31T02:18:00.000-07:00

Introduction

OpenStack Compute is an exciting piece of software. It is open, it is evolving rapidly and the community is terrific. However, as with any software that is new to the market, there’s little understanding and hard data on its performance. It’s scalability, for instance, is something that is only known through anecdotes around the watercooler. This post tells a story of a “baby cloud” running in one of our labs.

Our goal is to see how much we can stretch the software until it rips. In this installment, we’ll start with a very basic test — launching 200 virtual machines in parallel.

Setup and first steps

The test stand consists of three blades (two X5570 and 48G RAM each). All blades are diskless and SAN-backed. The exact hardware configuration is not relevant, since performance of individual VMs is not relevant for this kind of test.

Test image that was used for test is a stripped installation of RHEL 5.6, packed using QCOW2 (153Mb).

All the tests were performed using KVM-based RHEL 6.0 version of OpenStack Compute.

Here is our /etc/nova/nova.conf for cloud controller node:

We used the following script to run the VMs:

We started with a trunk build 1058 of OpenStack Compute.

First try

After firing up the script for the first time, we noticed that 3-5% of all machines were not coming up — that is, showing as down when listing instances. This was not completely unexpected, yet still discouraging. Having ten machines out of two hundred failing on the spot is not a good thing.

The investigation showed that connections to Rabbit are frequently timing out. Turned out that we stumbled upon a known bug in the eventlet library: socket connects are incorrectly reported as timed out. Patch to eventlet and improvements in RPC code helped us to eliminate the Rabbit timeout issue and bring down the error rate significantly. Kudos to Chris Behrens and Soren Hansen for the solution.

Second try

The error rate went down, but it was still above zero. Looked like we’ve stumbled on a race condition. Logs showed traces of exceptions about releasing locks. It turned out that the problem was in synchronization while creating VLANs. Simply adding a lock on the VLAN creation (bzr1097) made the problem go away — kudos to Vish Ishaya.

Third try

Now all instances show up as running, but are they actually usable?

“Usable” may mean many things, depending on how thorough you are. We have some pretty sophisticated test suites that can verify if a cloud instance is healthy for most practical purposes. But in this case, a simple ping of the VMs from outside to see if they respond was sufficiently informative.

The result was somewhat unexpected and bizarre: we could ping only 150 instances on network while API was indicating that all 200 were running. Run 150 instances… all 150 are responding. 180… 150 are responding. 151… again only 150 are responding. Looked like we stumbled on some sort of a limit.

Investigation showed that the problem is in dnsmasq, which has default DHCP lease cap at 150. Took some time to figure this one out, but very straightforward to fix — bzr1100.

Finally, the two hundred nodes were able to run without a hitch. Here’s one for the team!

Some random data

For those who want more data, here go a couple pretty graphs.

We ran two different configurations — one with two compute nodes, another with three (the third one being co-located with CC).

Fig 1. Two compute nodes, dedicated cloud controller.Total startup time: 12 minutes 6 seconds.

Fig 2. Three compute nodes, co-located cloud controller.

Total startup time: 8 minutes 20 seconds.

Though this is hardly conclusive, co-locating cloud controller with one of the compute nodes is not necessary a bad idea, at least from the performance standpoint.

Some random observations

Final success rate is 100%, reproducible;
Most of startup time is spent injecting SSH keys through libguestfs;
To run one hundred VMs per host from the same image, only 24Gb of RAM and 3.4GB in /var/lib/nova is needed. Thanks to KSM and QCOW2!

Next steps

Obviously, we are not settling on two hundred VMs run in parallel. This is still very much a work-in-progress and we’re raising the bar higher every time. Stay tuned for the next report from the trenches.

P.S.

By the time this post was written, we were able to go past 400 VMs. The team is working around another race condition as we speak.

Grid Designer's Blog

Block Join Faceting: Implementation

To view an updated version of this post click here

Block Join Faceting: Introduction

Block Join Faceting in Solr and other..

Automatic Speech Recognition Services Comparison

Automatic Speech Recognition Services Comparison

Introduction

Scoring Join Party in Solr 5.3

A Few Notes about Query-Time Join

The Lab Time

Near Real-Time boosting

How to import structured data into Solr

Solr Data Import Handler - DIH

Indexing Blocks by DIH

Nested Entities (data join) in DIH

Merge Join in DIH

Multithreading

Another ETL tool: Kettle

Lucene SIMD Codec benchmark and future steps

Tech notes

The heap problem

Edge cases

Further Plans

Who is who in Big Data

Spark and ZooKeeper: fault-tolerant job manager out of the box

Proposing SIMD codec for Lucene

Numeric Range Queries in Lucene/Solr

Algorithm

Index time

Search time

Under the hood

Index time

Search time

Precision step

Performance

According to NumericRangeQuery javadoc: Opteron64 machine, Java 1.5, 8 bit precision step 500k docs index TermRangeQuery in BooleanRewriteMode took about 30-40 seconds TermRangeQuery in FilterRewriteMode took about 5 seconds NumericRangeQuery took < 100ms

Useful links

Alternative approach to spell correction: character histograms

Intro

Problem statement

Approach

Character Histograms and Spell Correction

What it character histograms

How can we use histograms to compare two phrases

How can we encode histograms

Implementation Details

Benchmark Results

Conclusions and further directions

Segmented Filter Cache in Solr

To view an updated version of this post click here

Intro

NRT-filters

OR Filters

Filters 2.0

NRT-Facets

Grandchildren and Siblings with Block Join

Grandchildren search

Sibling Scopes

Minor usability issue

P.S.

Solr block-join support

To view an updated version of this post click here

Introduction

Indexing

Searching

Caveat

Further Directions

Faceting

FilterCache

Schema

Scoring Mode

Group Collecting

Block Join Query Performs

Definitions

Data

Tools and Procedure

Join

BlockJoin

Culprit

According to NumericRangeQuery javadoc:
Opteron64 machine, Java 1.5, 8 bit precision step
500k docs index
TermRangeQuery in BooleanRewriteMode took about 30-40 seconds
TermRangeQuery in FilterRewriteMode took about 5 seconds
NumericRangeQuery took < 100ms