[jira] [Comment Edited] (LUCENE-8675) Divide Segment Search Amongst Multiple Threads

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Comment Edited] (LUCENE-8675) Divide Segment Search Amongst Multiple Threads

JIRA jira@apache.org

    [ https://issues.apache.org/jira/browse/LUCENE-8675?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16779287#comment-16779287 ]

Atri Sharma edited comment on LUCENE-8675 at 4/18/19 12:09 PM:
---------------------------------------------------------------

Here are the results of luceneutil (patched to generate P50 and P90 and to run concurrent searching within IndexSearcher. Patch is posted to luceneutil repo).

Adrien has a valid point about costly scorers not benefitting from this approach. Specifically, range queries can take a hit since BKD Tree's scorer is two phase and is expensive to construct, so doing them per portion of a segment would lead to increase in latency, as is evident from the increase in P90 latency in the above results. I am spending time to evaluate how to tackle this problem and will post any thoughts that I see as viable. These benchmarks are targeted to measure the changes in the "happy" path i.e. the targeted big index sizes and low QPS cases. Luceneutil was configured accordingly (low number of search threads, impacts turned off)

In summary, the queries scanning a higher amount of data and having higher read latencies tend to have the maximum improvement. Term queries and queries involving term queries on higher frequency terms get a reasonable latency reduction.

The following are P50 and P90 latencies calculated by Luceneutil. P50 Base is the P50 latency of the base, P50 Cmp is the P50 latency of the competitor (patched version), and the same for P90.

Note: The QPS jumps are not real. Since Luceneutil was congigured to run a single searcher thread, QPS jump is proportional to the latency drop for task.

Luceneutil results: [https://gist.github.com/atris/9a06d511fdfa9de1b48b47e09d5ab8d2]

I have attached the P50 and P90 latency graphs for high frequency phrase and term queries. It is apparent that queries with high frequency terms have sizeable improvements.

To address Adrien's point, I have some ideas to improve performance of BKD tree scorer for this case, will open a separate JIRA issue and link here.

[~jpountz] Are there any other concerns that you see here? Happy to address your feedback.

 

 


was (Author: atris):
Here are the results of luceneutil (patched to generate P50 and P90 and to run concurrent searching within IndexSearcher. Patch is posted to luceneutil repo).

Adrien has a valid point about costly scorers not benefitting from this approach. Specifically, range queries can take a hit since BKD Tree's scorer is two phase and is expensive to construct, so doing them per portion of a segment would lead to increase in latency, as is evident from the increase in P90 latency in the above results. I am spending time to evaluate how to tackle this problem and will post any thoughts that I see as viable. These benchmarks are targeted to measure the changes in the "happy" path i.e. the targeted big index sizes and low QPS cases. Luceneutil was configured accordingly (low number of search threads, impacts turned off)

In summary, the queries scanning a higher amount of data and having higher read latencies tend to have the maximum improvement. Term queries and queries involving term queries on higher frequency terms get a reasonable latency reduction.

The following are P50 and P90 latencies calculated by Luceneutil. P50 Base is the P50 latency of the base, P50 Cmp is the P50 latency of the competitor (patched version), and the same for P90.

Note: The QPS jumps are not real. Since Luceneutil was congigured to run a single searcher thread, QPS jump is proportional to the latency drop for task.

Luceneutil results:

{{||Task ('Wildcard', None)||P50 Base 9.993697||P50 Cmp 11.906981||Pct 19.1449070349||P90 Base 14.431318||P90 Cmp 13.953923|| Pct -3.3080485095}}
{{||Task ('HighTermDayOfYearSort', 'DayOfYear')||P50 Base 39.556908||P50 Cmp 44.389095||Pct 12.2157854198||P90 Base 62.421873||P90 Cmp 49.214184|| Pct -21.1587515165}}
{{||Task ('AndHighHigh', None)||P50 Base 3.814074||P50 Cmp 2.459326||Pct -35.5197093711||P90 Base 5.045984||P90 Cmp 7.932029|| Pct 57.1948900353}}
{{||Task ('OrHighHigh', None)||P50 Base 9.586193||P50 Cmp 5.846643||Pct -39.0097507947||P90 Base 14.978843||P90 Cmp 7.078967|| Pct -52.7402283341}}
{{||Task ('MedPhrase', None)||P50 Base 3.210464||P50 Cmp 2.276356||Pct -29.0957319565||P90 Base 4.217049||P90 Cmp 3.852337|| Pct -8.64851226533}}
{{||Task ('LowSpanNear', None)||P50 Base 11.247447||P50 Cmp 4.986828||Pct -55.6625783611||P90 Base 16.095342||P90 Cmp 6.121194|| Pct -61.9691585305}}
{{||Task ('Fuzzy2', None)||P50 Base 23.636902||P50 Cmp 20.959304||Pct -11.3280412128||P90 Base 112.5086||P90 Cmp 105.188025|| Pct -6.50668037821}}
{{||Task ('OrNotHighHigh', None)||P50 Base 4.225917||P50 Cmp 2.62127||Pct -37.9715692476||P90 Base 6.11225||P90 Cmp 8.525249|| Pct 39.4780809031}}
{{||Task ('OrHighNotLow', None)||P50 Base 4.015982||P50 Cmp 2.250697||Pct -43.956496817||P90 Base 10.636566||P90 Cmp 3.134868|| Pct -70.5274427856}}
{{||Task ('BrowseMonthSSDVFacets', None)||P50 Base 66.920633||P50 Cmp 66.986841||Pct 0.0989351072038||P90 Base 67.230757||P90 Cmp 76.011531|| Pct 13.0606502021}}
{{||Task ('Fuzzy1', None)||P50 Base 14.779783||P50 Cmp 12.559705||Pct -15.0210459788||P90 Base 46.329521||P90 Cmp 218.272906|| Pct 371.131367838}}
{{||Task ('HighSloppyPhrase', None)||P50 Base 21.362967||P50 Cmp 10.563982||Pct -50.5500242546||P90 Base 33.009649||P90 Cmp 15.74507|| Pct -52.3016133858}}
{{||Task ('OrNotHighMed', None)||P50 Base 2.032775||P50 Cmp 1.584332||Pct -22.0606314029||P90 Base 2.529475||P90 Cmp 2.044107|| Pct -19.1884877297}}
{{||Task ('LowPhrase', None)||P50 Base 4.937747||P50 Cmp 2.8876||Pct -41.5198875115||P90 Base 6.910574||P90 Cmp 5.159077|| Pct -25.345173932}}
{{||Task ('AndHighLow', None)||P50 Base 1.097696||P50 Cmp 1.416176||Pct 29.0134973617||P90 Base 3.426081||P90 Cmp 13.987273|| Pct 308.258678064}}
{{||Task ('LowTerm', None)||P50 Base 0.787595||P50 Cmp 1.038949||Pct 31.9141182968||P90 Base 1.12006||P90 Cmp 39.639455|| Pct 3439.04746174}}
{{||Task ('BrowseDayOfYearSSDVFacets', None)||P50 Base 80.006624||P50 Cmp 80.215023||Pct 0.260477182489||P90 Base 80.610476||P90 Cmp 81.187614|| Pct 0.71595905227}}
{{||Task ('Prefix3', None)||P50 Base 3.347358||P50 Cmp 3.219213||Pct -3.82824305019||P90 Base 6.716371||P90 Cmp 5.21174|| Pct -22.4024402464}}
{{||Task ('HighTermMonthSort', 'Month')||P50 Base 20.684075||P50 Cmp 19.601521||Pct -5.23375592092||P90 Base 21.341383||P90 Cmp 20.092673|| Pct -5.85112033274}}
{{||Task ('HighTerm', None)||P50 Base 2.991271||P50 Cmp 1.891199||Pct -36.7760727798||P90 Base 4.058212||P90 Cmp 2.320309|| Pct -42.8243522024}}
{{||Task Respell||P50 Base 17.33154||P50 Cmp 17.397468||Pct 0.38039320222||P90 Base 99.071728||P90 Cmp 66.75552|| Pct -32.6190010535}}
{{||Task ('MedTerm', None)||P50 Base 3.011125||P50 Cmp 1.793175||Pct -40.4483374154||P90 Base 4.206761||P90 Cmp 2.392798|| Pct -43.1201820118}}
{{||Task ('MedSloppyPhrase', None)||P50 Base 5.896878||P50 Cmp 3.304889||Pct -43.9552759952||P90 Base 8.044708||P90 Cmp 4.881775|| Pct -39.316939782}}
{{||Task ('HighSpanNear', None)||P50 Base 20.981466||P50 Cmp 9.533211||Pct -54.5636563241||P90 Base 28.98951||P90 Cmp 11.087743|| Pct -61.7525684291}}
{{||Task ('LowSloppyPhrase', None)||P50 Base 12.841091||P50 Cmp 6.075233||Pct -52.6891211969||P90 Base 18.539534||P90 Cmp 6.825001|| Pct -63.1867715769}}
{{||Task ('OrHighNotHigh', None)||P50 Base 11.822146||P50 Cmp 6.645646||Pct -43.786466518||P90 Base 17.02398||P90 Cmp 7.935497|| Pct -53.3863585366}}
{{||Task ('OrNotHighLow', None)||P50 Base 0.782455||P50 Cmp 1.06583||Pct 36.2161402253||P90 Base 1.668578||P90 Cmp 13.200645|| Pct 691.131430476}}
{{||Task ('MedSpanNear', None)||P50 Base 3.161032||P50 Cmp 2.154472||Pct -31.8427652741||P90 Base 5.386012||P90 Cmp 5.665401|| Pct 5.18730741781}}
{{||Task ('BrowseDateTaxoFacets', None)||P50 Base 444.971146||P50 Cmp 444.674024||Pct -0.066773318376||P90 Base 447.81169||P90 Cmp 445.950713|| Pct -0.415571330887}}
{{||Task ('HighPhrase', None)||P50 Base 7.464241||P50 Cmp 4.644244||Pct -37.7800904338||P90 Base 25.153245||P90 Cmp 7.548758|| Pct -69.9889298578}}
{{||Task ('OrHighLow', None)||P50 Base 6.344855||P50 Cmp 3.590218||Pct -43.4152868742||P90 Base 8.425453||P90 Cmp 15.578677|| Pct 84.9001709463}}
{{||Task ('BrowseDayOfYearTaxoFacets', None)||P50 Base 0.16655||P50 Cmp 0.184125||Pct 10.5523866707||P90 Base 0.207908||P90 Cmp 0.224575|| Pct 8.01652654059}}
{{||Task ('IntNRQ', None)||P50 Base 24.844282||P50 Cmp 12.870238||Pct -48.196377742||P90 Base 45.815197||P90 Cmp 57.190359|| Pct 24.8283598999}}
{{||Task ('BrowseMonthTaxoFacets', None)||P50 Base 0.16488||P50 Cmp 0.170045||Pct 3.13258127123||P90 Base 0.203625||P90 Cmp 0.200508|| Pct -1.53075506446}}
{{||Task ('AndHighMed', None)||P50 Base 2.109471||P50 Cmp 1.773399||Pct -15.9315771584||P90 Base 2.458244||P90 Cmp 3.943119|| Pct 60.4038899312}}
{{||Task ('OrHighNotMed', None)||P50 Base 3.580582||P50 Cmp 3.088177||Pct -13.7520939333||P90 Base 4.196391||P90 Cmp 4.16434|| Pct -0.763775348865}}
{{||Task PKLookup||P50 Base 9.248977||P50 Cmp 9.76835||Pct 5.61546428324||P90 Base 47.86882||P90 Cmp 10.705417|| Pct -77.6359287737}}
{{||Task ('OrHighMed', None)||P50 Base 9.072955||P50 Cmp 5.552202||Pct -38.8049207783||P90 Base 20.823925||P90 Cmp 7.961727|| Pct -61.7664441262}}


{{TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff}}
{{Wildcard 104.35 (8.5%) 84.83 (3.2%) -18.7% ( -28% - -7%)}}
{{AndHighLow 963.75 (8.6%) 827.96 (6.3%) -14.1% ( -26% - 0%)}}
{{OrNotHighLow 1249.76 (6.0%) 1081.18 (7.8%) -13.5% ( -25% - 0%)}}
{{LowTerm 1227.19 (8.0%) 1161.29 (7.0%) -5.4% ( -18% - 10%)}}
{{HighTermDayOfYearSort 24.32 (8.0%) 23.08 (4.8%) -5.1% ( -16% - 8%)}}
{{Prefix3 314.51 (10.1%) 299.39 (5.2%) -4.8% ( -18% - 11%)}}
{{BrowseDateTaxoFacets 2.24 (0.7%) 2.24 (0.6%) -0.1% ( -1% - 1%)}}
{{BrowseMonthSSDVFacets 14.50 (11.5%) 14.50 (11.5%) -0.0% ( -20% - 25%)}}
{{BrowseDayOfYearSSDVFacets 11.88 (13.0%) 11.89 (13.0%) 0.1% ( -22% - 29%)}}
{{BrowseMonthTaxoFacets 5907.02 (4.6%) 5946.48 (3.0%) 0.7% ( -6% - 8%)}}
{{BrowseDayOfYearTaxoFacets 5897.01 (6.4%) 5955.79 (5.2%) 1.0% ( -9% - 13%)}}
{{HighTermMonthSort 50.29 (2.6%) 50.98 (2.1%) 1.4% ( -3% - 6%)}}
{{Respell 59.67 (1.8%) 60.81 (5.8%) 1.9% ( -5% - 9%)}}
{{Fuzzy2 55.57 (9.9%) 57.60 (11.3%) 3.7% ( -15% - 27%)}}
{{PKLookup 97.44 (6.3%) 103.31 (2.6%) 6.0% ( -2% - 16%)}}
{{Fuzzy1 68.65 (7.9%) 80.73 (7.3%) 17.6% ( 2% - 35%)}}
{{AndHighMed 512.13 (4.4%) 633.26 (8.2%) 23.7% ( 10% - 37%)}}
{{OrHighNotMed 264.08 (4.4%) 339.89 (8.6%) 28.7% ( 15% - 43%)}}
{{OrNotHighMed 533.03 (4.1%) 711.16 (3.9%) 33.4% ( 24% - 43%)}}
{{MedPhrase 300.47 (3.4%) 459.87 (9.3%) 53.1% ( 38% - 68%)}}
{{HighTerm 342.15 (7.5%) 537.82 (4.7%) 57.2% ( 41% - 75%)}}
{{MedSpanNear 317.62 (3.2%) 503.45 (9.9%) 58.5% ( 43% - 74%)}}
{{OrNotHighHigh 246.01 (3.6%) 390.45 (4.8%) 58.7% ( 48% - 69%)}}
{{MedTerm 369.26 (7.9%) 589.39 (3.4%) 59.6% ( 44% - 76%)}}
{{OrHighNotLow 272.24 (10.0%) 452.12 (5.2%) 66.1% ( 46% - 90%)}}
{{AndHighHigh 259.71 (4.9%) 434.41 (6.5%) 67.3% ( 53% - 82%)}}
{{OrHighHigh 101.65 (10.4%) 175.05 (13.0%) 72.2% ( 44% - 106%)}}
{{HighPhrase 125.02 (5.0%) 218.79 (9.3%) 75.0% ( 57% - 93%)}}
{{LowPhrase 197.78 (4.1%) 347.76 (6.8%) 75.8% ( 62% - 90%)}}
{{MedSloppyPhrase 164.88 (5.6%) 296.28 (7.0%) 79.7% ( 63% - 97%)}}
{{OrHighMed 106.28 (8.5%) 191.96 (12.2%) 80.6% ( 55% - 110%)}}
{{OrHighLow 155.97 (6.4%) 281.71 (6.6%) 80.6% ( 63% - 100%)}}
{{OrHighNotHigh 83.27 (4.6%) 162.56 (9.2%) 95.2% ( 77% - 114%)}}
{{HighSpanNear 50.94 (2.0%) 103.13 (9.1%) 102.5% ( 89% - 115%)}}
{{LowSpanNear 95.27 (3.2%) 194.98 (5.6%) 104.7% ( 92% - 117%)}}
{{HighSloppyPhrase 44.70 (4.4%) 91.71 (6.9%) 105.2% ( 89% - 121%)}}
{{IntNRQ 37.26 (18.3%) 84.10 (4.8%) 125.7% ( 86% - 182%)}}
{{LowSloppyPhrase 70.70 (12.8%) 160.76 (6.8%) 127.4% ( 95% - 168%)}}

 

> Divide Segment Search Amongst Multiple Threads
> ----------------------------------------------
>
>                 Key: LUCENE-8675
>                 URL: https://issues.apache.org/jira/browse/LUCENE-8675
>             Project: Lucene - Core
>          Issue Type: Improvement
>          Components: core/search
>            Reporter: Atri Sharma
>            Priority: Major
>
> Segment search is a single threaded operation today, which can be a bottleneck for large analytical queries which index a lot of data and have complex queries which touch multiple segments (imagine a composite query with range query and filters on top). This ticket is for discussing the idea of splitting a single segment into multiple threads based on mutually exclusive document ID ranges.
> This will be a two phase effort, the first phase targeting queries returning all matching documents (collectors not terminating early). The second phase patch will introduce staged execution and will build on top of this patch.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]