{"id":5978,"date":"2011-09-12T09:00:03","date_gmt":"2011-09-12T07:00:03","guid":{"rendered":"http:\/\/blog.orange11.nl\/?p=5978"},"modified":"2011-09-12T09:00:03","modified_gmt":"2011-09-12T07:00:03","slug":"hotspotting-lucene-with-query-specialization","status":"publish","type":"post","link":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/","title":{"rendered":"Hotspotting Lucene With Query Specialization"},"content":{"rendered":"

Most Java developers probably take the technology behind HotspotTM<\/span><\/sup><\/span><\/a>\u00a0<\/sup><\/span><\/a> for granted and assume it\u2019s best suited to optimize their code. \u00a0While they might know that choosing the best implementation of List will have a\u00a0 big impact on their program\u2019s performance, they probably shy away from worrying about the cost of virtual method calls, believing Hotspot knows best.<\/p>\n

With most applications and in most situations this belief is well-founded and what I\u2019m going to discuss is not trying to change the world view on Hotspot or encourage people to \u2018optimize prematurely\u2019. Rather, I want to explore the how we might aid Hotspot to produce the most optimal code for executing Lucene Querys and in the process increase query performance by over 100%.<\/div>\n

Red Hot <\/span>FunctionQuery Execution<\/h1>\n

One of the most popular Querys in Apache Solr<\/a> and Lucene<\/a> is FunctionQuery, which applies a function<\/em> (known as a ValueSource) to every<\/em> document in the index, returning the result of the function as the document\u2019s score. \u00a0Rarely in Lucene\u2019s Querys is logic applied to every document since Querys are responsible for matching (finding a relevant subset of documents) as well as scoring. Consequently, scoring logic is usually only applied to the matched subset. FunctionQuerys are not focused on matching, instead they manipulate the scores of documents in extensible ways.<\/p>\n

To understand the problems this might cause, imagine you have an index with 100 million documents containing two fields which you wish to sum together and use as document scores. Even though the logic required to implement this is very simple, the fact that it will be executed 100 million times for every<\/em> query means that it will glow hot – red hot<\/span>.<\/p>\n

\n

As mentioned, FunctionQuery is designed to be extensible. It accepts implementations of ValueSource of which there are many in Lucene\u2019s codebase. One such abstract implementation is MultiFloatFunction, itself accepting a list of ValueSources. MultiFloatFunction computes its function result by applying the logic implemented in the method func() to each of the results taken from its ValueSources. SumFloatFunction, a concrete implementation of MultiFloatFunction, adds sum logic to func().<\/p>\n

The following UML class diagram illustrates the hierarchy of ValueSource classes necessary to add the values of two integer fields together.<\/p>\n

\n
\n
<\/div>\n
\"\"<\/a><\/div>\n
<\/div>\n
\n
\n

Note, FieldValueSourceis a ValueSource implementation that returns the value of a field for a document. IntFieldValueSource assumes the value is an integer.<\/p>\n

Although this seems convoluted already, in practice this example is not too bad. The code boils down to two values being read from two different arrays and added together. However, if you wanted to add two field values together and then multiply the result by a third field value, you would need to add another MultiFloatFunction implementation (ProductFloatFunction) and another IntFieldSource. \u00a0Suddenly we have a large stack of objects with many layers of virtual calls that must be executed per document per<\/em> Query just to execute the formula (A + B) * C.<\/p>\n<\/div>\n

Specialized FunctionQuerys<\/h1>\n
\n

In a simple benchmark, I indexed 100,000 documents containing random integer values for 3 fields. \u00a0I then assembled the ValueSource required to execute A + B and computed the time required to execute 100,000 FunctionQuerys using the ValueSource. The result, on my underpowered laptop, was an average execution time of 3ms – not bad, not bad at all. However when I repeated the same test, this time using the ValueSource for (A + B) * C, the execution time jumped up to 25ms per query – still not bad, especially given the benchmarks were not on a dedicated server.<\/p>\n

However, I wondered if part of the increase in cost were the extra levels of virtual method calls that needed to be made. To test this, I created a simple interface called Function (shown below) and created an implementation of FunctionQuery which used Functions instead of
\nValueSources.<\/p>\n

\npublic interface Function {\nfloat f(int doc);\nvoid setNextReader(IndexReader indexReader) throws IOException;\n}\n<\/pre>\n
I then created an implement to support the formula (A + B) * C as follows:<\/p>\n
\npublic final class ABCFunction {\nprivate final int[] aVals, bVals, cVals;\npublic float f(int doc) { return (aVals[doc] + bVals[doc]) * cVals[doc]; }\npublic void setNextReader(IndexReader indexReader) throws IOException {\n\/\/ load arrays from FieldCache\n}\n}\n<\/pre>\n
Executed against the same index, the time per FunctionQuery dropped to just 13ms – a huge improvement.<\/p>\n
Whats the difference? Well the above implementation does not use object composition. The only virtual method call executed is that from FunctionQuery to the Function implementation. Even though the logic is the same as that executed using the ValueSources (3 values loaded from arrays, arithmetic applied), Hotspot is able to execute the simplified code with fewer method invocations much quicker.<\/p>\n<\/div>\n
\n
\n
\n
\n
Extensibility and Performance<\/h1>\n
While hopefully you are impressed by the performance improvement, you\u2019re also probably thinking \u201cWell that\u2019s great Chris, but this is not extensible or reusable\u201d and you would be right. \u00a0ValueSource\u2019s composition architecture allows us to quickly assemble a wide variety of functions while hiding away much of the complexity (some ValueSources are very complex). \u00a0They also lend themselves to be easy created while parsing a query string.<\/p>\n
Yet it could be argued that the above code illustrates that if your search application uses a small set of known functions regularly, there is a considerable performance benefit to be gained by providing specialised implementations. \u00a0From my experience, most Solr applications use only a couple of functions, primarily composed of the rudimentary arithmetic variety.<\/p>\n
ASTs and Executables<\/h1>\n
While toying with ValueSource and comparing it against my own ABCFunction, I couldn\u2019t help but notice the similarity between ValueSources and ASTs, and ABCFunction and Java Bytecode. When compiling source code, most compilers create an Abstract Syntax Tree (AST) representation of the code. \u00a0ASTs are a very close representation of the original source code, but use typed objects and composition, instead of text, to represent code statements. The following is a UML diagram showing the AST javac builds to represent the statement int a = 10:<\/div>\n
\"\"<\/div>\n
<\/div>\n
\n
\n
Having constructed an AST and after applying some optimizations, most compilers then generate the executable form of the source code. For Javac, this is Java Bytecode.<\/p>\n
An assembled ValueSource is very much like an AST. It describes the function that is to be executed and as mentioned, can be very easily constructed during query string parsing. But like an AST, it perhaps isn\u2019t the most efficient form for execution. \u00a0Instead, it needs to optimized (for a future article), and then converted to an optimal execution format. ABCFunction can be seen as an example of such a format.<\/p>\n
So how do we get from ValueSource to our optimal Function implementation?
\nWell, we could generate source code and use Javac to compile it for us, or we could generate bytecode ourselves, or we could even generate native code. However we do it, we are creating the foundations for a Query Compiler<\/em>.<\/p>\n<\/div>\n
Query Compilation and Beyond<\/h1>\n
Hopefully I\u2019ve tickled your interest in how we might go about using code specialisation to increase the performance of Hotspot\u2019s executions of Query code. In a future article, I will extend my explorations to the execution of all Lucene\u2019s Querys and explain in more detail how we might go about building a Query Compiler for Lucene.<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Most Java developers probably take the technology behind HotspotTM\u00a0 for granted and assume it\u2019s best suited to optimize their code. \u00a0While they might know that choosing the best implementation of List will have a\u00a0 big impact on their program\u2019s performance, they probably shy away from worrying about the cost of virtual method calls, believing Hotspot […]<\/p>\n","protected":false},"author":24,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","footnotes":""},"categories":[10],"tags":[35,17],"class_list":["post-5978","post","type-post","status-publish","format-standard","hentry","category-development","tag-lucene","tag-search"],"acf":[],"yoast_head":"\nHotspotting Lucene With Query Specialization - Trifork Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hotspotting Lucene With Query Specialization - Trifork Blog\" \/>\n<meta property=\"og:description\" content=\"Most Java developers probably take the technology behind HotspotTM\u00a0 for granted and assume it\u2019s best suited to optimize their code. \u00a0While they might know that choosing the best implementation of List will have a\u00a0 big impact on their program\u2019s performance, they probably shy away from worrying about the cost of virtual method calls, believing Hotspot […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/\" \/>\n<meta property=\"og:site_name\" content=\"Trifork Blog\" \/>\n<meta property=\"article:published_time\" content=\"2011-09-12T07:00:03+00:00\" \/>\n<meta name=\"author\" content=\"Chris Male\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Chris Male\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/\",\"url\":\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/\",\"name\":\"Hotspotting Lucene With Query Specialization - Trifork Blog\",\"isPartOf\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#website\"},\"datePublished\":\"2011-09-12T07:00:03+00:00\",\"author\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/63ca100399079ec6e98e2b4365298806\"},\"breadcrumb\":{\"@id\":\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/trifork.nl\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Hotspotting Lucene With Query Specialization\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/trifork.nl\/blog\/#website\",\"url\":\"https:\/\/trifork.nl\/blog\/\",\"name\":\"Trifork Blog\",\"description\":\"Keep updated on the technical solutions Trifork is working on!\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/trifork.nl\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/63ca100399079ec6e98e2b4365298806\",\"name\":\"Chris Male\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/8bbf7706dc08d42eaf11f2b18add0721?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/8bbf7706dc08d42eaf11f2b18add0721?s=96&d=mm&r=g\",\"caption\":\"Chris Male\"},\"url\":\"https:\/\/trifork.nl\/blog\/author\/chris\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hotspotting Lucene With Query Specialization - Trifork Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/","og_locale":"en_US","og_type":"article","og_title":"Hotspotting Lucene With Query Specialization - Trifork Blog","og_description":"Most Java developers probably take the technology behind HotspotTM\u00a0 for granted and assume it\u2019s best suited to optimize their code. \u00a0While they might know that choosing the best implementation of List will have a\u00a0 big impact on their program\u2019s performance, they probably shy away from worrying about the cost of virtual method calls, believing Hotspot […]","og_url":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/","og_site_name":"Trifork Blog","article_published_time":"2011-09-12T07:00:03+00:00","author":"Chris Male","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Chris Male","Est. reading time":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/","url":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/","name":"Hotspotting Lucene With Query Specialization - Trifork Blog","isPartOf":{"@id":"https:\/\/trifork.nl\/blog\/#website"},"datePublished":"2011-09-12T07:00:03+00:00","author":{"@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/63ca100399079ec6e98e2b4365298806"},"breadcrumb":{"@id":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/trifork.nl\/blog\/hotspotting-lucene-with-query-specialization\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/trifork.nl\/blog\/"},{"@type":"ListItem","position":2,"name":"Hotspotting Lucene With Query Specialization"}]},{"@type":"WebSite","@id":"https:\/\/trifork.nl\/blog\/#website","url":"https:\/\/trifork.nl\/blog\/","name":"Trifork Blog","description":"Keep updated on the technical solutions Trifork is working on!","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/trifork.nl\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/63ca100399079ec6e98e2b4365298806","name":"Chris Male","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/8bbf7706dc08d42eaf11f2b18add0721?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8bbf7706dc08d42eaf11f2b18add0721?s=96&d=mm&r=g","caption":"Chris Male"},"url":"https:\/\/trifork.nl\/blog\/author\/chris\/"}]}},"_links":{"self":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/5978","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/users\/24"}],"replies":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/comments?post=5978"}],"version-history":[{"count":0,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/5978\/revisions"}],"wp:attachment":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/media?parent=5978"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/categories?post=5978"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/tags?post=5978"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}