[ https://issues.apache.org/jira/browse/LUCENE-10633?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17571807#comment-17571807 ]
Adrien Grand commented on LUCENE-10633: --------------------------------------- The PR is ready for review now if someone is interested in having a look. I made an improvement for the very sparse case, so that after collecting {{numHits}} matches, the collector would tell the query to only look at documents that have a value for the sort field. One assumption that this change makes is that terms are encoded exactly the same way in the terms index and in the doc-values terms dictionary. I think it's a fine assumption, but wanted to make it explicit because this optimization will lead to runtime errors if this assumption isn't met. This is the same assumption that we are already making today when sorting numeric fields and using the points index to dynamically prune irrelevant hits. I ran luceneutil again to verify performance is still good: {noformat} TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value HighSloppyPhrase 11.46 (4.3%) 11.19 (5.3%) -2.4% ( -11% - 7%) 0.120 Prefix3 53.30 (16.7%) 52.06 (16.8%) -2.3% ( -30% - 37%) 0.659 BrowseDateSSDVFacets 5.23 (11.1%) 5.13 (13.5%) -1.9% ( -23% - 25%) 0.632 BrowseDayOfYearSSDVFacets 20.33 (7.6%) 19.96 (8.6%) -1.9% ( -16% - 15%) 0.470 BrowseMonthTaxoFacets 28.62 (12.0%) 28.11 (7.8%) -1.8% ( -19% - 20%) 0.582 OrHighNotLow 1357.76 (6.3%) 1334.12 (4.8%) -1.7% ( -12% - 9%) 0.325 OrHighNotMed 1568.25 (4.3%) 1541.21 (4.8%) -1.7% ( -10% - 7%) 0.232 MedTerm 2422.95 (5.2%) 2381.38 (4.6%) -1.7% ( -10% - 8%) 0.269 HighTerm 1736.81 (6.5%) 1710.26 (5.6%) -1.5% ( -12% - 11%) 0.426 MedSloppyPhrase 62.45 (3.4%) 61.59 (4.1%) -1.4% ( -8% - 6%) 0.249 OrNotHighHigh 931.81 (5.4%) 919.74 (4.4%) -1.3% ( -10% - 8%) 0.403 OrHighHigh 58.41 (5.3%) 57.65 (4.1%) -1.3% ( -10% - 8%) 0.388 OrNotHighMed 1179.51 (3.0%) 1168.53 (3.2%) -0.9% ( -6% - 5%) 0.338 BrowseRandomLabelSSDVFacets 14.52 (1.9%) 14.40 (1.9%) -0.8% ( -4% - 3%) 0.186 LowTerm 1589.67 (3.6%) 1579.95 (4.6%) -0.6% ( -8% - 7%) 0.642 MedTermDayTaxoFacets 52.00 (4.3%) 51.70 (4.3%) -0.6% ( -8% - 8%) 0.672 OrHighNotHigh 1008.27 (5.9%) 1002.78 (5.1%) -0.5% ( -10% - 11%) 0.756 LowIntervalsOrdered 11.03 (4.8%) 10.98 (4.4%) -0.5% ( -9% - 9%) 0.724 OrHighMedDayTaxoFacets 22.72 (3.5%) 22.64 (3.1%) -0.4% ( -6% - 6%) 0.718 OrHighLow 899.20 (3.3%) 896.35 (3.0%) -0.3% ( -6% - 6%) 0.750 MedIntervalsOrdered 43.37 (3.6%) 43.25 (3.7%) -0.3% ( -7% - 7%) 0.799 HighIntervalsOrdered 24.44 (5.3%) 24.37 (5.5%) -0.3% ( -10% - 11%) 0.864 OrNotHighLow 1448.52 (4.0%) 1446.40 (3.5%) -0.1% ( -7% - 7%) 0.901 LowSpanNear 85.70 (2.4%) 85.59 (2.2%) -0.1% ( -4% - 4%) 0.851 AndHighLow 1043.29 (5.2%) 1042.26 (3.9%) -0.1% ( -8% - 9%) 0.946 PKLookup 236.83 (1.4%) 236.69 (2.2%) -0.1% ( -3% - 3%) 0.919 HighTermTitleBDVSort 25.03 (3.5%) 25.02 (2.6%) -0.0% ( -5% - 6%) 0.977 Wildcard 156.78 (1.9%) 156.93 (1.8%) 0.1% ( -3% - 3%) 0.877 MedSpanNear 214.11 (4.2%) 214.32 (2.9%) 0.1% ( -6% - 7%) 0.929 Fuzzy1 118.50 (1.2%) 118.67 (0.9%) 0.1% ( -1% - 2%) 0.664 Respell 59.34 (1.0%) 59.43 (0.8%) 0.1% ( -1% - 2%) 0.630 Fuzzy2 115.77 (1.1%) 116.01 (1.1%) 0.2% ( -1% - 2%) 0.549 LowSloppyPhrase 89.17 (2.6%) 89.38 (2.6%) 0.2% ( -4% - 5%) 0.771 HighSpanNear 31.18 (4.1%) 31.28 (3.2%) 0.3% ( -6% - 8%) 0.769 OrHighMed 252.02 (3.5%) 252.99 (2.5%) 0.4% ( -5% - 6%) 0.692 AndHighMedDayTaxoFacets 151.31 (2.5%) 152.01 (1.9%) 0.5% ( -3% - 5%) 0.511 HighPhrase 369.49 (3.8%) 371.89 (3.3%) 0.6% ( -6% - 8%) 0.564 LowPhrase 61.86 (3.6%) 62.30 (2.6%) 0.7% ( -5% - 7%) 0.475 AndHighMed 227.16 (4.6%) 228.89 (5.3%) 0.8% ( -8% - 11%) 0.626 TermDTSort 826.30 (2.0%) 833.64 (1.7%) 0.9% ( -2% - 4%) 0.139 AndHighHighDayTaxoFacets 24.63 (3.5%) 24.89 (4.2%) 1.0% ( -6% - 9%) 0.400 MedPhrase 123.13 (3.4%) 124.49 (2.5%) 1.1% ( -4% - 7%) 0.243 IntNRQ 128.88 (4.9%) 130.32 (3.6%) 1.1% ( -7% - 10%) 0.410 HighTermDayOfYearSort 1443.98 (2.1%) 1461.31 (2.0%) 1.2% ( -2% - 5%) 0.063 AndHighHigh 73.59 (4.1%) 74.62 (5.5%) 1.4% ( -7% - 11%) 0.363 BrowseRandomLabelTaxoFacets 35.66 (11.8%) 36.30 (6.0%) 1.8% ( -14% - 22%) 0.544 BrowseDayOfYearTaxoFacets 44.76 (13.7%) 45.89 (4.5%) 2.5% ( -13% - 24%) 0.434 BrowseDateTaxoFacets 43.26 (13.4%) 44.53 (4.8%) 2.9% ( -13% - 24%) 0.354 BrowseMonthSSDVFacets 21.46 (6.7%) 22.22 (10.8%) 3.6% ( -13% - 22%) 0.212 HighTermTitleSort 115.84 (9.7%) 544.03 (15.6%) 369.6% ( 313% - 437%) 0.000 HighTermMonthSort 153.92 (9.5%) 3899.90 (100.4%) 2433.8% (2122% - 2810%) 0.000 {noformat} If you wonder why the speedup for HighTermTitleSort is lower now, this is because the tasks file for wikimedium10m didn't include queries that sort on the title field previously, so I added one query on the HighTerm that had the highest document frequency. Now wikimedium10m has sorting tasks for all HighTerms, including some that have a significantly lower document frequency (which is why the baseline is also faster compared to the previous run, fewer hits to sort), and this optimization works better with queries that have lots of matches. For queries that don't match many documents on sort fields that have a high cardinality, this optimization may even make queries a bit slower. Here's the performance difference for one of the low-frequency terms (`fantasy`): {noformat} TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value LowTermTitleSort 434.21 (7.0%) 427.76 (8.0%) -1.5% ( -15% - 14%) 0.534 LowTermMonthSort 770.08 (5.9%) 1300.48 (21.2%) 68.9% ( 39% - 102%) 0.000 {noformat} In general I think it's a good trade-off: the slower queries are getting faster, and queries that are already fast may get just a little bit slower. > Dynamic pruning for queries sorted by SORTED(_SET) field > -------------------------------------------------------- > > Key: LUCENE-10633 > URL: https://issues.apache.org/jira/browse/LUCENE-10633 > Project: Lucene - Core > Issue Type: Improvement > Reporter: Adrien Grand > Priority: Minor > Time Spent: 10m > Remaining Estimate: 0h > > LUCENE-9280 introduced the ability to dynamically prune non-competitive hits > when sorting by a numeric field, by leveraging the points index to skip > documents that do not compare better than the top of the priority queue > maintained by the field comparator. > However queries sorted by a SORTED(_SET) field still look at all hits, which > is disappointing. Could we leverage the terms index to skip hits? -- This message was sent by Atlassian Jira (v8.20.10#820010) --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org