You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "slow-J (via GitHub)" <gi...@apache.org> on 2026/06/17 16:03:15 UTC
[PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
slow-J opened a new pull request, #16268:
URL: https://github.com/apache/lucene/pull/16268
Resolves https://github.com/apache/lucene/issues/16249
Rest TK
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3481864108
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
> Does the latest commit also include the interval-tracking rewind change?
Yes.
> Unwrapping adds a little bit of complexity, but if it improves performance, I think we should keep it.
I'll setup and run a benchmark now just to see the perf diff due to the unwrapping.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3444797113
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
I think skipper can stil improve performance for this case, as we can still cache ordinal, it is just that in this case we have to always call longValues.advanceExact(doc). If it returns true - we return cached ordinal (and avoid reading long value as well as binary search elementary interval), otherwise return false
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3487383485
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Sounds good to me, let's separate these two changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3459587398
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Hmm looking at the new benchmark results, there is an improvement in the ID tasks, which do not have a doc-values skip index. This is due to a change in the latest commit.
id is a single-valued field, but in `main`, fromLongField never unwraps to a single-valued source, always picking the multi-valued leaf cutter even when the field is single-valued.
We now route single-valued segments to the single-valued cutter instead. The new create(String field, …) keeps the field name, which lets createLeafCutter inspect each segment during search and pick the right cutter.
I have kept this in this PR but its slightly increasing the scope.
@epotyom let me know what you think about this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3482200089
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Ran: ` python3 -u src/python/localrun.py -s rangeFacetsWikimediumAll -b lucene_baseline -c lucene_candidate -iterations 30 -warmups 20 2>&1 | tee "$BASE/run9-onlyunwrapping-timing.txt"`
Heres the result.
## Latency (ms) — aggregated across all iterations
| Task | P50 B | P50 C | Diff | P90 B | P90 C | Diff | P99 B | P99 C | Diff | P999 B | P999 C | Diff | P100 B | P100 C | Diff |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| BrowseIDOvlpRangeFacets | 946.928 | 820.170 | -13.4% | 1279.722 | 1178.839 | -7.9% | 1509.599 | 3489.425 | +131.1% | 1579.256 | 10588.392 | +570.5% | 1647.232 | 10662.196 | +547.3% |
| BrowseIDRangeFacets | 410.635 | 296.512 | -27.8% | 630.174 | 670.131 | +6.3% | 869.641 | 866.369 | -0.4% | 931.130 | 8681.360 | +832.3% | 1008.106 | 9240.540 | +816.6% |
| BrowseLastModOvlpRangeFacets | 381.116 | 365.262 | -4.2% | 577.681 | 639.843 | +10.8% | 866.191 | 2046.696 | +136.3% | 1028.218 | 10214.331 | +893.4% | 1029.600 | 10234.017 | +894.0% |
| BrowseLastModRangeFacets | 324.172 | 317.631 | -2.0% | 526.130 | 634.818 | +20.7% | 808.836 | 884.852 | +9.4% | 851.734 | 9413.995 | +1005.3% | 887.375 | 9912.493 | +1017.1% |
| MedTermIDOvlpRangeFacets | 213.936 | 181.524 | -15.1% | 433.905 | 437.942 | +0.9% | 603.100 | 702.917 | +16.6% | 679.574 | 838.447 | +23.4% | 761.983 | 848.642 | +11.4% |
| MedTermIDRangeFacets | 211.334 | 171.214 | -19.0% | 519.706 | 555.351 | +6.9% | 735.139 | 713.797 | -2.9% | 834.724 | 836.369 | +0.2% | 840.486 | 843.231 | +0.3% |
| MedTermLastModOvlpRangeFacets | 176.353 | 173.086 | -1.9% | 486.851 | 537.847 | +10.5% | 712.630 | 719.706 | +1.0% | 830.068 | 832.742 | +0.3% | 842.260 | 840.165 | -0.2% |
| MedTermLastModRangeFacets | 188.926 | 182.942 | -3.2% | 487.783 | 553.020 | +13.4% | 731.373 | 718.764 | -1.7% | 830.363 | 832.185 | +0.2% | 841.503 | 834.076 | -0.9% |
## QPS
| Task | QPS baseline | StdDev | QPS modified | StdDev | Pct diff | p-value |
|---|---|---|---|---|---|---|
| BrowseLastModRangeFacets | 3.26 | (5.8%) | 3.34 | (8.1%) | 2.6% (-10% - 17%) | 0.155 |
| BrowseLastModOvlpRangeFacets | 2.75 | (5.1%) | 2.85 | (6.2%) | 3.6% (-7% - 15%) | 0.015 |
| MedTermLastModRangeFacets | 5.58 | (7.9%) | 5.80 | (8.6%) | 3.8% (-11% - 22%) | 0.072 |
| MedTermLastModOvlpRangeFacets | 5.89 | (6.9%) | 6.13 | (8.2%) | 4.1% (-10% - 20%) | 0.035 |
| MedTermIDOvlpRangeFacets | 4.94 | (6.3%) | 5.68 | (6.6%) | 15.0% (1% - 29%) | 0.000 |
| MedTermIDRangeFacets | 5.19 | (9.9%) | 6.17 | (7.1%) | 18.7% (1% - 39%) | 0.000 |
| BrowseIDOvlpRangeFacets | 1.12 | (7.4%) | 1.33 | (11.9%) | 19.1% (0% - 41%) | 0.000 |
| BrowseIDRangeFacets | 2.52 | (4.5%) | 3.60 | (12.0%) | 42.7% (25% - 61%) | 0.000 |
Mainly impacts the ID tasks which do not have a skipper.
But it does seem to cause a worrying latency regression at high percentile latency (p90 and onward).
Hmm, @epotyom what do you think? Since it is not related to the skipper change, I am partial towards removing the unwrapping and retesting performance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3534182234
##########
lucene/CHANGES.txt:
##########
@@ -325,6 +325,8 @@ Optimizations
* GITHUB#16352: Better cost() estimation for SkipBlockRangeIterator. (Alan Woodward)
+* GITHUB#16268: Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter. (Jakub Slowinski)
Review Comment:
up to you - but maybe worth mentioning all applied optimisations (use skipper, unwrap multi valued in some cases, ~~reuse~~ rewind tracker)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3519975101
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -124,6 +152,39 @@ public static LongRangeFacetCutter create(
*/
abstract List<InclusiveRange> buildElementaryIntervals();
+ /**
+ * Returns the {@link DocValuesSkipper} for {@link #skipField} in this segment. Null when: no skip
+ * field is configured, the field has no skip index, or some doc in this segment has more than one
+ * value.
+ */
+ final DocValuesSkipper maybeSkipper(LeafReaderContext context) throws IOException {
+ if (skipField == null) {
+ return null;
+ }
+ SortedNumericDocValues sortedNumeric = DocValues.getSortedNumeric(context.reader(), skipField);
+ if (DocValues.unwrapSingleton(sortedNumeric) == null) {
+ return null;
+ }
+ return context.reader().getDocValuesSkipper(skipField);
+ }
+
+ /** Single-valued {@link LongValues} for {@link #skipField} in this segment. */
+ final LongValues skipFieldValues(LeafReaderContext context) throws IOException {
+ NumericDocValues values =
+ DocValues.unwrapSingleton(DocValues.getSortedNumeric(context.reader(), skipField));
Review Comment:
Will do that in next commit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3459206290
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Took me some time to publish the changes as I managed to initially introduce a regression into range facets without skip lists, I done a small refactor while fixing that.
I am getting much better performance after implementing your suggestions, I will update the benchmark results in the top level comment.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3491400091
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Removed the unwrapping in latest commit, will edit the main benchmark in PR description with new numbers.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3519761465
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -42,6 +47,10 @@ public abstract class LongRangeFacetCutter implements FacetCutter {
// TODO: refactor - weird that we have both multi and single here.
final LongValuesSource singleValues;
+
+ // Field name whose skip index is used on the single-valued path, or null when faceting a source.
+ final String skipField;
Review Comment:
Sure!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3476643944
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Interesting, nice catch!
> This is due to a change in the latest commit.
Does the latest commit also include the interval-tracking `rewind` change? If so, could you please run benchmarks for the unwrapping change only?
Unwrapping adds a little bit of complexity, but if it improves performance, I think we should keep it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3519746228
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -124,6 +152,39 @@ public static LongRangeFacetCutter create(
*/
abstract List<InclusiveRange> buildElementaryIntervals();
+ /**
+ * Returns the {@link DocValuesSkipper} for {@link #skipField} in this segment. Null when: no skip
+ * field is configured, the field has no skip index, or some doc in this segment has more than one
+ * value.
+ */
+ final DocValuesSkipper maybeSkipper(LeafReaderContext context) throws IOException {
+ if (skipField == null) {
+ return null;
+ }
+ SortedNumericDocValues sortedNumeric = DocValues.getSortedNumeric(context.reader(), skipField);
+ if (DocValues.unwrapSingleton(sortedNumeric) == null) {
+ return null;
+ }
+ return context.reader().getDocValuesSkipper(skipField);
+ }
+
+ /** Single-valued {@link LongValues} for {@link #skipField} in this segment. */
+ final LongValues skipFieldValues(LeafReaderContext context) throws IOException {
Review Comment:
There is less of an uplift in the multivalued, compared to single valued.
│ MedTermLastModMultiOvlpRangeFacets │ 3.49 │ 3.95 │ +13.2% │ 0.000 │
│ BrowseLastModMultiRangeFacets │ 1.78 │ 1.85 │ +3.8% │ 0.006 │
│ BrowseLastModMultiOvlpRangeFacets │ 1.12 │ 1.15 │ +2.8% │ 0.056 │
│ MedTermLastModMultiRangeFacets │ 4.51 │ 4.49 │ −0.3% │ 0.849 │
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5764005651
@stefanvodita I tested it again, this time ran different ids in separate tests to give them separate JVMs.
Setup: 33.3M docs, sorted by lastMod_skipper. Three long fields get faceted: lastMod_skipper (single-valued, has a skip index), lastMod_multi_skipper (multi-valued, has skip index), id (no skip index). 126 tasks across those three fields.
Run 1 - all three fields, 126 tasks
| Task | baseline QPS | StdDev | patched QPS | StdDev | Pct diff | p-value |
|---|---:|---:|---:|---:|---:|---:|
| BrowseLastModMultiRangeFacets | 0.41 | 1.9% | 0.37 | 0.8% | −10.1% (−12% – −7%) | 0.000 |
| BrowseIDRangeFacets | 0.58 | 1.6% | 0.53 | 1.3% | −9.2% (−11% – −6%) | 0.000 |
| BrowseLastModMultiOvlpRangeFacets | 0.24 | 1.3% | 0.22 | 0.8% | −5.5% (−7% – −3%) | 0.000 |
| BrowseIDOvlpRangeFacets | 0.28 | 1.3% | 0.27 | 0.9% | −4.8% (−6% – −2%) | 0.000 |
| MedTermIDOvlpRangeFacets | 3.04 | 2.4% | 2.98 | 1.2% | −2.0% (−5% – 1%) | 0.000 |
| MedTermLastModMultiOvlpRangeFacets | 2.39 | 5.2% | 2.36 | 1.3% | −1.1% (−7% – 5%) | 0.036 |
| MedTermIDRangeFacets | 6.35 | 6.6% | 6.34 | 1.8% | −0.2% (−8% – 8%) | 0.821 |
| MedTermLastModMultiRangeFacets | 3.56 | 9.1% | 3.57 | 1.6% | 0.2% (−9% – 12%) | 0.825 |
| MedTermLastModRangeFacets | 3.62 | 6.2% | 5.11 | 2.5% | 41.3% (30% – 53%) | 0.000 |
| BrowseLastModRangeFacets | 0.53 | 1.7% | 0.84 | 2.5% | 57.8% (52% – 63%) | 0.000 |
| MedTermLastModOvlpRangeFacets | 4.13 | 2.2% | 7.42 | 2.9% | 79.5% (72% – 86%) | 0.000 |
| BrowseLastModOvlpRangeFacets | 0.28 | 1.3% | 0.67 | 3.9% | 138.0% (131% – 145%) | 0.000 |
Run 2 - id only, 42 tasks, same index
| Task | baseline QPS | StdDev | patched QPS | StdDev | Pct diff | p-value |
|---|---:|---:|---:|---:|---:|---:|
| MedTermIDRangeFacets | 6.53 | 7.3% | 6.17 | 9.3% | −5.4% (−20% – 12%) | 0.000 |
| MedTermIDOvlpRangeFacets | 4.15 | 4.1% | 4.00 | 5.2% | −3.6% (−12% – 5%) | 0.000 |
| BrowseIDRangeFacets | 0.69 | 3.1% | 0.68 | 2.8% | −2.1% (−7% – 3%) | 0.000 |
| BrowseIDOvlpRangeFacets | 0.30 | 1.4% | 0.30 | 0.9% | −1.1% (−3% – 1%) | 0.000 |
Run 3 - multi-valued only, 84 tasks, fresh index
| Task | baseline QPS | StdDev | patched QPS | StdDev | Pct diff | p-value |
|---|---:|---:|---:|---:|---:|---:|
| MedTermLastModMultiOvlpRangeFacets | 1.89 | 2.2% | 1.96 | 2.3% | 3.5% (0% – 8%) | 0.000 |
| BrowseLastModMultiOvlpRangeFacets | 0.21 | 2.7% | 0.22 | 2.9% | 3.7% (−1% – 9%) | 0.000 |
| MedTermLastModMultiRangeFacets | 3.74 | 3.0% | 3.89 | 3.3% | 3.8% (−2% – 10%) | 0.000 |
| BrowseLastModMultiRangeFacets | 0.34 | 4.2% | 0.36 | 4.4% | 5.5% (−2% – 14%) | 0.000 |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-4743432231
I reran benchmarks, this time correctly using localrun, and updated the results in https://github.com/apache/lucene/pull/16268#issue-4684961710
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5548113321
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov merged PR #16268:
URL: https://github.com/apache/lucene/pull/16268
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3481864108
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
> Does the latest commit also include the interval-tracking rewind change?
Yes, it has all three changes: non-dense fast path, rewind reuse, and unwrapping.
> Unwrapping adds a little bit of complexity, but if it improves performance, I think we should keep it.
I'll setup and run a benchmark now just to see the perf diff due to the unwrapping.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5358339796
Fixed merge conflict in changes.txt since this has gotten stale.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5713650422
> Cool idea and nice improvement! Do we know why BrowseIDOvlpRangeFacets QPS went down?
Trying to drill into this, ID tasks (MedTermIDRangeFacets, MedTermIDOvlpRangeFacets, BrowseIDOvlpRangeFacets, BrowseIDRangeFacets) have no skip index in the tested index.
Running a new benchmark testing this branch as candidate and this branch less this commit as baseline.
I see that lastMod_multi_skipper seems to have a regression while single value looks good.
Maybe my testing setup is wrong as its been a few weeks since I ran this last. Will dig into this more.
| Task | Field | Pct diff | ±1σ span | p |
| --- | --- | ---: | :---: | ---: |
| BrowseLastModOvlpRangeFacets | `lastMod_skipper` | +138.0% | [+131%, +145%] | 0.000 |
| MedTermLastModOvlpRangeFacets | `lastMod_skipper` | +79.5% | [+72%, +86%] | 0.000 |
| BrowseLastModRangeFacets | `lastMod_skipper` | +57.8% | [+52%, +63%] | 0.000 |
| MedTermLastModRangeFacets | `lastMod_skipper` | +41.3% | [+30%, +53%] | 0.000 |
| MedTermLastModMultiRangeFacets | `lastMod_multi_skipper` | +0.2% | [−9%, +12%] | 0.825 |
| MedTermIDRangeFacets | `id` | −0.2% | [−8%, +8%] | 0.821 |
| MedTermLastModMultiOvlpRangeFacets | `lastMod_multi_skipper` | −1.1% | [−7%, +5%] | 0.036 |
| MedTermIDOvlpRangeFacets | `id` | −2.0% | [−5%, +1%] | 0.000 |
| BrowseIDOvlpRangeFacets | `id` | −4.8% | [−6%, −2%] | 0.000 |
| BrowseLastModMultiOvlpRangeFacets | `lastMod_multi_skipper` | −5.5% | [−7%, −3%] | 0.000 |
| BrowseIDRangeFacets | `id` | −9.2% | [−11%, −6%] | 0.000 |
| BrowseLastModMultiRangeFacets | `lastMod_multi_skipper` | −10.1% | [−12%, −7%] | 0.000 |
About regression in ID, it is not impacted by this code, so maybe its an issue with JIT? Trying to run some more tests.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3496536235
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -124,6 +152,39 @@ public static LongRangeFacetCutter create(
*/
abstract List<InclusiveRange> buildElementaryIntervals();
+ /**
+ * Returns the {@link DocValuesSkipper} for {@link #skipField} in this segment. Null when: no skip
+ * field is configured, the field has no skip index, or some doc in this segment has more than one
+ * value.
+ */
+ final DocValuesSkipper maybeSkipper(LeafReaderContext context) throws IOException {
+ if (skipField == null) {
+ return null;
+ }
+ SortedNumericDocValues sortedNumeric = DocValues.getSortedNumeric(context.reader(), skipField);
+ if (DocValues.unwrapSingleton(sortedNumeric) == null) {
+ return null;
+ }
+ return context.reader().getDocValuesSkipper(skipField);
+ }
+
+ /** Single-valued {@link LongValues} for {@link #skipField} in this segment. */
+ final LongValues skipFieldValues(LeafReaderContext context) throws IOException {
Review Comment:
Is this method a part of the single value unwrapping logic that we want to remove for now?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3497838500
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -124,6 +152,39 @@ public static LongRangeFacetCutter create(
*/
abstract List<InclusiveRange> buildElementaryIntervals();
+ /**
+ * Returns the {@link DocValuesSkipper} for {@link #skipField} in this segment. Null when: no skip
+ * field is configured, the field has no skip index, or some doc in this segment has more than one
+ * value.
+ */
+ final DocValuesSkipper maybeSkipper(LeafReaderContext context) throws IOException {
+ if (skipField == null) {
+ return null;
+ }
+ SortedNumericDocValues sortedNumeric = DocValues.getSortedNumeric(context.reader(), skipField);
+ if (DocValues.unwrapSingleton(sortedNumeric) == null) {
+ return null;
+ }
+ return context.reader().getDocValuesSkipper(skipField);
+ }
+
+ /** Single-valued {@link LongValues} for {@link #skipField} in this segment. */
+ final LongValues skipFieldValues(LeafReaderContext context) throws IOException {
Review Comment:
Nope, this is part of the core skipper path.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3444819290
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -252,21 +313,48 @@ abstract static class LongRangeSingleValuedLeafFacetCutter implements LeafFacetC
IntervalTracker requestedIntervalTracker;
+ // Skip index for the faceted field, or null when disabled.
+ private final DocValuesSkipper skipper;
+
+ // Cached decision from advanceSkipper, valid for every doc up to (and including) upToInclusive:
+ // when upToSameInterval is true, all those docs map to elementary interval upToIntervalOrd.
+ private int upToInclusive = -1;
+ private boolean upToSameInterval;
+ private int upToIntervalOrd;
+
LongRangeSingleValuedLeafFacetCutter(LongValues longValues, long[] boundaries, int[] pos) {
+ this(longValues, boundaries, pos, null);
+ }
+
+ LongRangeSingleValuedLeafFacetCutter(
+ LongValues longValues, long[] boundaries, int[] pos, DocValuesSkipper skipper) {
this.longValues = longValues;
this.boundaries = boundaries;
this.pos = pos;
+ this.skipper = skipper;
}
@Override
public boolean advanceExact(int doc) throws IOException {
- if (longValues.advanceExact(doc) == false) {
+ if (skipper != null && doc > upToInclusive) {
+ advanceSkipper(doc);
+ }
+
+ int intervalOrd;
+ if (upToSameInterval) {
+ // We are inside a dense skip block that maps entirely to one elementary interval, so reuse
+ // the cached ordinal and skip the per-doc value lookup and binary search.
+ intervalOrd = upToIntervalOrd;
+ } else if (longValues.advanceExact(doc)) {
+ intervalOrd = processValue(longValues.longValue());
+ } else {
return false;
}
+
if (requestedIntervalTracker != null) {
Review Comment:
Do we also want to reuse requestedIntervalTracker if intervalOrd is the same for the previous doc?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3459206290
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Took me some time to publish the changes as I managed to initially introduce a regression into range facets without skip lists, I done a small refactor while fixing that.
I am getting much better performance after implementing your suggestions, I will update the benchmark results in the top level comment.
Edit: updated benchmark results.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3444797113
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
I think skipper can stil improve performance for this case, as we can still cache ordinal, it is just that in this case we have to always call longValues.advanceExact(doc). If it returns true - we return cached ordinal, otherwise return false
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5053084576
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3535860897
##########
lucene/CHANGES.txt:
##########
@@ -325,6 +325,8 @@ Optimizations
* GITHUB#16352: Better cost() estimation for SkipBlockRangeIterator. (Alan Woodward)
+* GITHUB#16268: Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter. (Jakub Slowinski)
Review Comment:
Thanks for the review Egor, will change the entry now while resolving the changes conflicts.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on PR #16268:
URL: https://github.com/apache/lucene/pull/16268#issuecomment-5670574346
Cool idea and nice improvement! Do we know why `BrowseIDOvlpRangeFacets` QPS went down?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "epotyom (via GitHub)" <gi...@apache.org>.
epotyom commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3534182234
##########
lucene/CHANGES.txt:
##########
@@ -325,6 +325,8 @@ Optimizations
* GITHUB#16352: Better cost() estimation for SkipBlockRangeIterator. (Alan Woodward)
+* GITHUB#16268: Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter. (Jakub Slowinski)
Review Comment:
up to you - but maybe worth mentioning all applied optimisations (use skipper, unwrap multi valued in some cases, reuse tracker)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3459206290
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Took me some time to publish the changes as I managed to initially introduce a regression into range facets without skipper, I done a small refactor while fixing that.
I am getting much better performance after implementing your suggestions, I will update the benchmark results in the top level comment.
Edit: updated benchmark results.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3519762788
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -124,6 +152,39 @@ public static LongRangeFacetCutter create(
*/
abstract List<InclusiveRange> buildElementaryIntervals();
+ /**
+ * Returns the {@link DocValuesSkipper} for {@link #skipField} in this segment. Null when: no skip
+ * field is configured, the field has no skip index, or some doc in this segment has more than one
+ * value.
+ */
+ final DocValuesSkipper maybeSkipper(LeafReaderContext context) throws IOException {
+ if (skipField == null) {
+ return null;
+ }
+ SortedNumericDocValues sortedNumeric = DocValues.getSortedNumeric(context.reader(), skipField);
+ if (DocValues.unwrapSingleton(sortedNumeric) == null) {
+ return null;
+ }
+ return context.reader().getDocValuesSkipper(skipField);
+ }
+
+ /** Single-valued {@link LongValues} for {@link #skipField} in this segment. */
+ final LongValues skipFieldValues(LeafReaderContext context) throws IOException {
Review Comment:
Will do alongside `fieldName`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3452975112
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -252,21 +313,48 @@ abstract static class LongRangeSingleValuedLeafFacetCutter implements LeafFacetC
IntervalTracker requestedIntervalTracker;
+ // Skip index for the faceted field, or null when disabled.
+ private final DocValuesSkipper skipper;
+
+ // Cached decision from advanceSkipper, valid for every doc up to (and including) upToInclusive:
+ // when upToSameInterval is true, all those docs map to elementary interval upToIntervalOrd.
+ private int upToInclusive = -1;
+ private boolean upToSameInterval;
+ private int upToIntervalOrd;
+
LongRangeSingleValuedLeafFacetCutter(LongValues longValues, long[] boundaries, int[] pos) {
+ this(longValues, boundaries, pos, null);
+ }
+
+ LongRangeSingleValuedLeafFacetCutter(
+ LongValues longValues, long[] boundaries, int[] pos, DocValuesSkipper skipper) {
this.longValues = longValues;
this.boundaries = boundaries;
this.pos = pos;
+ this.skipper = skipper;
}
@Override
public boolean advanceExact(int doc) throws IOException {
- if (longValues.advanceExact(doc) == false) {
+ if (skipper != null && doc > upToInclusive) {
+ advanceSkipper(doc);
+ }
+
+ int intervalOrd;
+ if (upToSameInterval) {
+ // We are inside a dense skip block that maps entirely to one elementary interval, so reuse
+ // the cached ordinal and skip the per-doc value lookup and binary search.
+ intervalOrd = upToIntervalOrd;
+ } else if (longValues.advanceExact(doc)) {
+ intervalOrd = processValue(longValues.longValue());
+ } else {
return false;
}
+
if (requestedIntervalTracker != null) {
Review Comment:
Good idea, will try to do this!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Use the doc-values skip index to skip per-doc value lookups in LongRangeFacetCutter [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16268:
URL: https://github.com/apache/lucene/pull/16268#discussion_r3452984774
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/cutters/ranges/LongRangeFacetCutter.java:
##########
@@ -275,6 +363,40 @@ public boolean advanceExact(int doc) throws IOException {
return true;
}
+ /** Mirrors {@code HistogramCollector#advanceSkipper}. */
+ private void advanceSkipper(int doc) throws IOException {
+ if (doc > skipper.maxDocID(0)) {
+ skipper.advance(doc);
+ }
+ upToSameInterval = false;
+
+ if (skipper.minDocID(0) > doc) {
+ // Corner case which happens if doc doesn't have a value and is between two intervals of the
+ // skip index. Fall back to per-doc lookups until the next block.
+ upToInclusive = skipper.minDocID(0) - 1;
+ return;
+ }
+
+ upToInclusive = skipper.maxDocID(0);
+ // Now find the highest level where all docs have a value and map to the same interval.
+ for (int level = 0; level < skipper.numLevels(); ++level) {
+ int totalDocsAtLevel = skipper.maxDocID(level) - skipper.minDocID(level) + 1;
+ if (skipper.docCount(level) != totalDocsAtLevel) {
+ // Some docs at this level have no value, so we can't resolve the whole block at once.
Review Comment:
Thanks for the review Egor! Good point!
I'll try to address these 2 comments and run new benchmarks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org