[ https://issues.apache.org/jira/browse/LUCENE-4198?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrien Grand updated LUCENE-4198: --------------------------------- Attachment: LUCENE-4198.patch I have taken another approach. Issue with {{setMinCompetitiveScore}} is that it usually cannot be efficiently leveraged to speed up eg. conjunctions. So I went with implementing ideas from the block-max WAND (BMW) paper (http://engineering.nyu.edu/~suel/papers/bmw.pdf): the patch introduces a new {{ImpactsEnum}} which extends {{PostingsEnum}} and introduces two APIs instead of {{setMinCompetitiveScore}}: - {{int advanceShallow(int target)}} to get scoring information for documents that start at {{target}}. The benefit compared to {{advance}} is that it only advances the skip list reader, which is much cheaper: no decoding is happening. - {{float getMaxScore(int upTo)}} wich gives information about scores for doc ids between the last target to {{advanceShallow}} and {{upTo}}, both included. Currently only TermScorer leverages this, but the benefit is that we could add these APIs to Scorer as well in a follow-up issue so that WANDScorer and ConjunctionScorer could leverage them. I built a prototype already to make sure that there is an actual speedup for some queries, but I'm leaving it to a follow-up issue as indexing impacts is already challenging on its own. One thing that it made me change though is that the new patch also stores all impacts on the first level, which is written every 128 documents. This seemed important for conjunctions, since the maximum score on a given block is not always reached, on the contrary to term queries since they match all documents in the block. It makes it more important to have good bounds of the score with conjunctions than it is with term queries. The disk overhead is still acceptable to me: the wikimedium10 index is only 1.4% larger overall, and postings alone (the .doc file) is only 3.1% larger. Here are the benchmark results: {noformat} TaskQPS baseline StdDev QPS patch StdDev Pct diff AndHighLow 1128.91 (3.5%) 875.48 (2.3%) -22.4% ( -27% - -17%) AndHighMed 409.67 (2.0%) 331.98 (1.7%) -19.0% ( -22% - -15%) OrHighMed 264.99 (3.5%) 229.15 (3.0%) -13.5% ( -19% - -7%) OrHighLow 111.47 (4.5%) 98.00 (3.2%) -12.1% ( -18% - -4%) OrHighHigh 34.88 (4.2%) 31.69 (4.0%) -9.1% ( -16% - -1%) OrNotHighLow 1373.74 (5.2%) 1291.72 (4.1%) -6.0% ( -14% - 3%) LowPhrase 78.14 (1.6%) 75.28 (1.2%) -3.7% ( -6% - 0%) MedPhrase 47.49 (1.6%) 45.92 (1.2%) -3.3% ( -5% - 0%) LowSloppyPhrase 208.43 (2.8%) 202.37 (2.7%) -2.9% ( -8% - 2%) Fuzzy1 300.99 (7.7%) 292.78 (8.0%) -2.7% ( -17% - 13%) LowSpanNear 62.73 (1.4%) 61.09 (1.3%) -2.6% ( -5% - 0%) Fuzzy2 188.37 (7.9%) 184.16 (6.7%) -2.2% ( -15% - 13%) MedSpanNear 57.41 (1.8%) 56.17 (1.5%) -2.2% ( -5% - 1%) MedSloppyPhrase 23.21 (2.3%) 22.73 (2.3%) -2.1% ( -6% - 2%) HighPhrase 48.75 (3.2%) 47.80 (3.6%) -1.9% ( -8% - 4%) HighSpanNear 40.04 (2.9%) 39.35 (2.7%) -1.7% ( -7% - 4%) HighTermMonthSort 228.21 (8.4%) 224.66 (7.9%) -1.6% ( -16% - 16%) HighSloppyPhrase 25.96 (2.8%) 25.61 (3.0%) -1.4% ( -6% - 4%) Respell 284.85 (3.7%) 282.42 (4.0%) -0.9% ( -8% - 7%) IntNRQ 18.87 (5.3%) 18.86 (6.8%) -0.1% ( -11% - 12%) Wildcard 85.50 (5.0%) 86.79 (4.0%) 1.5% ( -7% - 11%) Prefix3 137.41 (6.5%) 141.61 (4.9%) 3.1% ( -7% - 15%) HighTermDayOfYearSort 116.58 (6.3%) 121.38 (7.2%) 4.1% ( -8% - 18%) AndHighHigh 37.64 (1.5%) 118.12 (6.7%) 213.8% ( 202% - 225%) LowTerm 909.13 (2.2%) 3379.38 (11.2%) 271.7% ( 252% - 291%) OrNotHighMed 196.21 (1.7%) 1509.92 (28.9%) 669.6% ( 627% - 712%) MedTerm 305.82 (1.7%) 2897.01 (42.5%) 847.3% ( 789% - 907%) HighTerm 108.94 (1.7%) 1191.54 (61.3%) 993.8% ( 915% - 1075%) OrHighNotMed 81.83 (0.5%) 1082.94 (63.2%) 1223.5% (1153% - 1294%) OrHighNotHigh 63.16 (0.7%) 995.35 (72.0%) 1475.8% (1393% - 1559%) OrHighNotLow 34.53 (0.9%) 557.35 (94.8%) 1514.1% (1406% - 1623%) OrNotHighHigh 51.95 (0.9%) 943.81 (73.7%) 1716.6% (1626% - 1808%) {noformat} Results are a bit less good than previously for two reasons: - The new API doesn't allow term queries to skip more than one block (128 docs) at a time. But I think the perspective of speeding up boolean queries too makes it a good trade-off, especially given that this is already quite a significant speed up for term queries. - The new implementation is more complex since it also (optionally) gives access to positions, offsets and payloads. I did not specialize the case that only frequencies are requested (hopefully this won't be necessary). Information about positions could be useful in the future to speed up phrase queries. I wouldn't worry too much about the slowdown for some boolean queries. First the most affected queries are queries that are already quite fast. Plus I hope that follow-ups will allow us to get some performance back. > Allow codecs to index term impacts > ---------------------------------- > > Key: LUCENE-4198 > URL: https://issues.apache.org/jira/browse/LUCENE-4198 > Project: Lucene - Core > Issue Type: Sub-task > Components: core/index > Reporter: Robert Muir > Attachments: LUCENE-4198.patch, LUCENE-4198.patch, LUCENE-4198.patch, > LUCENE-4198.patch, LUCENE-4198_flush.patch > > > Subtask of LUCENE-4100. > Thats an example of something similar to impact indexing (though, his > implementation currently stores a max for the entire term, the problem is the > same). > We can imagine other similar algorithms too: I think the codec API should be > able to support these. > Currently it really doesnt: Stefan worked around the problem by providing a > tool to 'rewrite' your index, he passes the IndexReader and Similarity to it. > But it would be better if we fixed the codec API. > One problem is that the Postings writer needs to have access to the > Similarity. Another problem is that it needs access to the term and > collection statistics up front, rather than after the fact. > This might have some cost (hopefully minimal), so I'm thinking to experiment > in a branch with these changes and see if we can make it work well. -- This message was sent by Atlassian JIRA (v6.4.14#64029) --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org