You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jainankitk (via GitHub)" <gi...@apache.org> on 2025/04/04 07:04:45 UTC
[PR] Adding logic for collecting Histogram efficiently using Point Trees [lucene]
jainankitk opened a new pull request, #14439:
URL: https://github.com/apache/lucene/pull/14439
### Description
This PR adds multi range traversal logic to collect the histogram on numeric field indexed as pointValues for MATCH_ALL cases. Even for non-match all cases like `PointRangeQuery`, if the query field == histogram field, this logic can be used. For the later, need to supply the `PointRangeQuery` bounds for building the appropriate `Ranges` to be collected.
One of the key assumptions is absence of any deleted documents. Maybe going forward (especially if the deleted documents percentage is low), we can consider correcting the collected `Ranges` by subtracting for deleted documents. Although if I remember correctly, getting histogram field values for just deleted documents was non-trivial task!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2056783050
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +63,31 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (context.reader().hasDeletions() == false
+ && weight.count(context) == context.reader().maxDoc()) {
Review Comment:
I would check weight against `null`, applications may have collectors that don't set a weight.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +63,31 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (context.reader().hasDeletions() == false
Review Comment:
You don't need this check, Weight#count already accounts for deletions.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.NumericUtils;
+
+class PointTreeBulkCollector {
+ private static Function<byte[], Long> bytesToLong(int numBytes) {
+ if (numBytes == Long.BYTES) {
+ // Used by LongPoint, DoublePoint
+ return a -> NumericUtils.sortableBytesToLong(a, 0);
+ } else if (numBytes == Integer.BYTES) {
+ // Used by IntPoint, FloatPoint, LatLonPoint, LatLonShape
+ return a -> (long) NumericUtils.sortableBytesToInt(a, 0);
+ }
+
+ return null;
+ }
+
+ static boolean canCollectEfficiently(final PointValues pointValues, final long bucketWidth)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size() for this optimization
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong = bytesToLong(pointValues.getBytesPerDimension());
+ if (byteToLong == null) {
+ return false;
+ }
+
+ long leafMinBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMinPackedValue()), bucketWidth);
+ long leafMaxBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMaxPackedValue()), bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
Review Comment:
Sounds good to me.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054837202
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
Review Comment:
There are other files in sandbox with experimental tags, so maybe better safe then sorry? I guess it's easy to forget to add those when moving a piece of code out of sandbox.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2050117622
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +59,22 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point range query for MATCH_ALL cases
+ final PointValues pointValues = context.reader().getPointValues(field);
+ if (query instanceof MatchAllDocsQuery && !context.reader().hasDeletions()) {
Review Comment:
Yes, I will open follow-up once we are close to merging this PR. I will keep this conversation open, until the issue is created
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2059224354
##########
lucene/CHANGES.txt:
##########
@@ -78,6 +78,8 @@ Optimizations
---------------------
* GITHUB#14418: Quick exit on filter query matching no docs when rewriting knn query. (Pan Guixin)
+* GITHUB#14439: Efficient Histogram Collection using multi range traversal over PointTrees
Review Comment:
ah, my bad. Fixed!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2049533078
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
Review Comment:
Do we need explicit `@lucene.experimental` even for classes within sandbox? As per my understanding, everything sandbox is experimental by default?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2822536135
> Interesting idea! I like that you integrated it transparently into the collector, so that users can benefit from it out of the box.
Thanks @jpountz for the review. Had some challenges with the integration initially, but `seWeight` method was pretty useful!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2049741831
##########
lucene/sandbox/src/test/org/apache/lucene/sandbox/facet/plain/histograms/TestHistogramCollectorManager.java:
##########
@@ -115,6 +117,38 @@ public void testSkipIndexWithSortAndLowInterval() throws IOException {
.setCodec(TestUtil.alwaysDocValuesFormat(new Lucene90DocValuesFormat(3))));
}
+ public void testMultiRangePointTreeCollector() throws IOException {
Review Comment:
Okay, ran the test and few times and I understand what the error is.
```
java.lang.AssertionError: expected:<[1=>978, 3=>1004, 4=>1000, 2=>1022, 0=>996]> but was:<[4=>5000, 1=>4890, 2=>5110, 3=>5020, 0=>4980]>
```
The actual values are 5 times of the expected. Essentially, the logic efficiently collects values for entire segment and in case of intra-segment concurrency, it ends up collecting 5 times. I am wondering if the collectors can be aware of intra-segment concurrency, and not use the optimized path when it is enabled?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054988914
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
+ }
+
+ BucketManager collector =
+ new BucketManager(
+ collectorCounts,
+ minValue,
+ bucketWidth,
+ a -> getLongFromByte(byteToLong, a),
+ maxBuckets);
+ PointValues.IntersectVisitor visitor = getIntersectVisitor(collector);
+ try {
+ intersectWithRanges(visitor, pointValues.getPointTree(), collector);
+ } catch (CollectionTerminatedException _) {
+ // Early terminate since no more range to collect
+ }
+ collector.finalizePreviousBucket(null);
+
+ return true;
+ }
+
+ private static void intersectWithRanges(
+ PointValues.IntersectVisitor visitor,
+ PointValues.PointTree pointTree,
+ BucketManager collector)
+ throws IOException {
+ PointValues.Relation r =
+ visitor.compare(pointTree.getMinPackedValue(), pointTree.getMaxPackedValue());
+
+ switch (r) {
+ case CELL_INSIDE_QUERY:
+ collector.countNode((int) pointTree.size());
+ break;
+ case CELL_CROSSES_QUERY:
+ if (pointTree.moveToChild()) {
+ do {
+ intersectWithRanges(visitor, pointTree, collector);
+ } while (pointTree.moveToSibling());
+ pointTree.moveToParent();
+ } else {
+ pointTree.visitDocValues(visitor);
+ }
+ break;
+ case CELL_OUTSIDE_QUERY:
+ }
+ }
+
+ private static long getLongFromByte(Function<byte[], Long> f, byte[] packedValue) {
+ // TODO: Read long correctly instead of downcasting to int
+ return f.apply(packedValue).intValue();
+ }
+
+ private static PointValues.IntersectVisitor getIntersectVisitor(BucketManager collector) {
+ return new PointValues.IntersectVisitor() {
+ @Override
+ public void visit(int docID) {
+ // this branch should be unreachable
+ throw new UnsupportedOperationException(
+ "This IntersectVisitor does not perform any actions on a "
+ + "docID="
+ + docID
+ + " node being visited");
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) throws IOException {
+ if (!collector.withinUpperBound(packedValue)) {
+ collector.finalizePreviousBucket(packedValue);
+ }
+
+ if (collector.withinRange(packedValue)) {
+ collector.count();
+ }
+ }
+
+ @Override
+ public void visit(DocIdSetIterator iterator, byte[] packedValue) throws IOException {
+ if (!collector.withinUpperBound(packedValue)) {
+ collector.finalizePreviousBucket(packedValue);
+ }
+
+ if (collector.withinRange(packedValue)) {
+ for (int doc = iterator.nextDoc(); doc != NO_MORE_DOCS; doc = iterator.nextDoc()) {
+ collector.count();
+ }
+ }
+ }
+
+ @Override
+ public PointValues.Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ // try to find the first range that may collect values from this cell
+ if (!collector.withinUpperBound(minPackedValue)) {
+ collector.finalizePreviousBucket(minPackedValue);
+ }
+
+ // Not possible to have the CELL_OUTSIDE_QUERY, as bucket lower bound is updated
+ // while finalizing the previous bucket
+ if (collector.withinRange(minPackedValue) && collector.withinRange(maxPackedValue)) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+ };
+ }
+
+ private static class BucketManager {
+ private final LongIntHashMap collectorCounts;
+ private int counter = 0;
+ private long startValue;
+ private long endValue;
+ private int nonZeroBuckets = 0;
+ private int maxBuckets;
+ private Function<byte[], Long> byteToLong;
+ private long bucketWidth;
+
+ public BucketManager(
+ LongIntHashMap collectorCounts,
+ long minValue,
+ long bucketWidth,
+ Function<byte[], Long> byteToLong,
+ int maxBuckets) {
+ this.collectorCounts = collectorCounts;
+ this.bucketWidth = bucketWidth;
+ this.startValue = Math.floorDiv(minValue, bucketWidth) * bucketWidth;
+ this.endValue = startValue + bucketWidth;
+ this.byteToLong = byteToLong;
+ this.maxBuckets = maxBuckets;
+ }
+
+ private void count() {
+ counter++;
+ }
+
+ private void countNode(int count) {
+ counter += count;
+ }
+
+ private void finalizePreviousBucket(byte[] packedValue) {
+ // TODO: Can counter ever be 0?
Review Comment:
I think this specific TODO, we can leave for now. More like a safety guard. I will try to add unit test in future to validate this, and remove if not needed
Others TODOs were important and have been addressed
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2794700870
I didn't mean to imply that the two solutions are the same, apologies if that's how it came across.
> Need some inputs from the community on how it can be plugged correctly into the HistogramCollector
Let me know if this doesn't answer the question @jainankitk, maybe you'd already gone through this and you were looking for a different answer.
I think you could start in `HistogramCollector.getLeafCollector` ([code](https://github.com/apache/lucene/blob/4957766fcee52c534d786e3948fadf6d36c9779f/lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java#L50)). Right now we throw an exception if the field we're using isn't doc values ([code](https://github.com/apache/lucene/blob/4957766fcee52c534d786e3948fadf6d36c9779f/lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java#L59)). You'd need a new branch for the case you want to implement and a new `LeafCollector`, similar to the ones already in the file. Having that would make it easier to think through the next steps.
At a higher level, I'm curious if you had a use-case in mind.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2794969733
> I didn't mean to imply that the two solutions are the same, apologies if that's how it came across.
Not at all. Even I was initially confused with skipper logic, only after spending some time realized this approach is slightly different. So, thanks for reiterating the question.
> I think you could start in HistogramCollector.getLeafCollector ([code](https://github.com/apache/lucene/blob/4957766fcee52c534d786e3948fadf6d36c9779f/lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java#L50)). Right now we throw an exception if the field we're using isn't doc values ([code](https://github.com/apache/lucene/blob/4957766fcee52c534d786e3948fadf6d36c9779f/lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java#L59)).
Currently, `Collector` doesn't need to be aware of the `Query` itself. They are designed to collect individual docId or using `DocIdStream` from the scorer. But this `CustomCollector`, does not need the scorer to provide documents, but can `BulkCollect` documents, assuming `MATCH_ALL` or `PointRangeQuery` (where `PointRangeQuery.field == histogram.field`). Otherwise, it should fallback to traditional methods for collecting matching documents.
> At a higher level, I'm curious if you had a use-case in mind.
This optimization can be applied to following use cases:
* Number of sale based on the price range (0-50, 50-100, 100-250,.....)
* Number of visits on website for each day in a month
Just as a data point, this change helped us improve date histogram latency from 5168 ms to 160 ms (~32x!!) for big5 workload in OpenSearch
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2824226140
This is a nice optimization, using points (if the user indexed them) to carefully optimize counting of ranges.
> @stefanvodita - Thanks for a prompt review. Addressed most of the review comments. Adding JMH benchmark instead of the not so useful performance test added earlier. The benchark results demonstrate significant increase in throughput with increasing # documents and bucket width (lesser buckets mean less low level traversal in point range tree and more documents collected in bulk):
Oooh those JMH benchy results are nice! Though, it's dangerous testing only on random data -- you can draw random conclusions/results. But it's better than no benchmark! Maybe we should add histogram faceting benchy to Lucene's nightly 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
Re: [PR] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita merged PR #14439:
URL: https://github.com/apache/lucene/pull/14439
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054894167
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +65,30 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (query instanceof MatchAllDocsQuery && context.reader().hasDeletions() == false) {
Review Comment:
Yes we can, but I am anyway planning to address `PointRangeQuery` case more generically as fast followup - https://github.com/apache/lucene/issues/14535. Also with intra-segment search, `leafCollector` can be called multiple times, so I want to ensure that in cases we don't use this optimization has minimal overhead. I am assuming `weight.count(context)` will have some overhead?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054858596
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/HistogramCollectorBenchmark.java:
##########
@@ -0,0 +1,130 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.Comparator;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Stream;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.LongPoint;
+import org.apache.lucene.document.NumericDocValuesField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.sandbox.facet.plain.histograms.HistogramCollectorManager;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.MatchAllDocsQuery;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.MMapDirectory;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Warmup;
+
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.SECONDS)
+@Fork(value = 1, warmups = 1)
+@Warmup(iterations = 1, time = 1)
+@Measurement(iterations = 3, time = 3)
+public class HistogramCollectorBenchmark {
Review Comment:
I like this benchmark!
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
Review Comment:
I could be misunderstanding, so please bear with me. Let's say a user only has `PointValues` indexed and no `DocValues` and they try to use the histogram. Would they be able to do that even if their data doesn't fit the efficiency condition above?
##########
lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java:
##########
@@ -801,4 +802,16 @@ public static int compareUnsigned4(byte[] a, int aOffset, byte[] b, int bOffset)
return Integer.compareUnsigned(
(int) BitUtil.VH_BE_INT.get(a, aOffset), (int) BitUtil.VH_BE_INT.get(b, bOffset));
}
+
+ public static Function<byte[], Long> getValue(int numBytes) {
Review Comment:
I'm happy with how it is now. Thank you!
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
Review Comment:
Let me be more specific. I'm questioning if the `Expected numeric field, but got doc-value type` exception we used to throw still makes sense now or needs to be adjusted since we now have another case for `PointValues` which must have not worked out to reach the exception.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054996584
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
Review Comment:
Ah, not really. As explained in other, we can discuss that as part of https://github.com/apache/lucene/issues/14536?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2059125314
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
Review Comment:
I see your point and I'm happy to have a follow-up issue if necessary for this and the related comment below.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2810960212
I have updated the PR, and the code flow is like below now:
* `HistogramCollector` overrides the `setWeight` for accessing the underlying `Query`
* To keep things simple, just optimizing for `MATCH_ALL_DOCS` query and no deleted documents for now
* Optimized path is enabled only if `pointTree` is built for the field
* There are few other conditions for optimized path being enabled. Being conservative for now, and fallback to original.
* Add small unit test to verify working as expected
Will add few more unit tests, once I get some feedback on the code changes. Can also include small performance unit test that demonstrates, pointTree based collection is faster than the docValues based collector.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2049535183
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
Review Comment:
The user does not need to get anything. We will just skip the optimized path and fall back to the original execution plan
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2050147491
##########
lucene/sandbox/src/test/org/apache/lucene/sandbox/facet/plain/histograms/TestHistogramCollectorManager.java:
##########
@@ -115,6 +117,38 @@ public void testSkipIndexWithSortAndLowInterval() throws IOException {
.setCodec(TestUtil.alwaysDocValuesFormat(new Lucene90DocValuesFormat(3))));
}
+ public void testMultiRangePointTreeCollector() throws IOException {
Review Comment:
Okay, I have added logic for collecting only for one of the partitions if intra-segment concurrency is enabled. Ran the test 50k times after that without any failures:
```
> Task :lucene:core:testClasses
> Task :lucene:core:test
> Task :lucene:core:wipeTaskTemp
> Task :lucene:sandbox:test
:lucene:sandbox:test (SUCCESS): 50000 test(s)
> Task :lucene:sandbox:wipeTaskTemp
The slowest suites (exceeding 1s) during this run:
580.41s TestHistogramCollectorManager (:lucene:sandbox)
BUILD SUCCESSFUL in 9m 58s
246 actionable tasks: 181 executed, 65 up-to-date
```
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2049534867
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
Review Comment:
The user does not need to get anything. We will just skip the optimized path and fall back to the original execution plan
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2056150570
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +65,30 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (query instanceof MatchAllDocsQuery && context.reader().hasDeletions() == false) {
Review Comment:
I'ml not sure if we're talking about the same case. You seem to be talking about the case when the histogram is computed on the same field as the range query. I was referring to the case when a query is not a `MatchAllDocsQuery` but still fully matches a segment, e.g. a `TermQuery` on a stop word like `a` or a wide `PointRangeQuery` (not necessarily on the same field as the histogram).
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054889522
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +59,22 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point range query for MATCH_ALL cases
+ final PointValues pointValues = context.reader().getPointValues(field);
+ if (query instanceof MatchAllDocsQuery && !context.reader().hasDeletions()) {
Review Comment:
https://github.com/apache/lucene/issues/14535
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2056830312
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +63,31 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (context.reader().hasDeletions() == false
Review Comment:
Ah, nice!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2050115412
##########
lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java:
##########
@@ -801,4 +802,16 @@ public static int compareUnsigned4(byte[] a, int aOffset, byte[] b, int bOffset)
return Integer.compareUnsigned(
(int) BitUtil.VH_BE_INT.get(a, aOffset), (int) BitUtil.VH_BE_INT.get(b, bOffset));
}
+
+ public static Function<byte[], Long> getValue(int numBytes) {
Review Comment:
Thanks for suggesting `NumericUtils`. I wasn't aware of the `NumericUtils#sortableBytesToLong`, exactly what I needed to flip the sign bit correctly!
```
// Flip the sign bit back
v ^= 0x8000000000000000L;
```
I have removed this method from `ArrayUtil` and added in `PointTreeBulkCollector`. Please let me know if you still see any concerns
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2048509305
##########
lucene/sandbox/src/test/org/apache/lucene/sandbox/facet/plain/histograms/TestHistogramCollectorManager.java:
##########
@@ -115,6 +117,38 @@ public void testSkipIndexWithSortAndLowInterval() throws IOException {
.setCodec(TestUtil.alwaysDocValuesFormat(new Lucene90DocValuesFormat(3))));
}
+ public void testMultiRangePointTreeCollector() throws IOException {
Review Comment:
Let's run this test more? I've checked it out and seen it both pass and fail.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
Review Comment:
Should we only call this once?
##########
lucene/sandbox/src/test/org/apache/lucene/sandbox/facet/plain/histograms/TestHistogramCollectorManager.java:
##########
@@ -115,6 +117,38 @@ public void testSkipIndexWithSortAndLowInterval() throws IOException {
.setCodec(TestUtil.alwaysDocValuesFormat(new Lucene90DocValuesFormat(3))));
}
+ public void testMultiRangePointTreeCollector() throws IOException {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig());
+
+ long[] values = new long[5000];
+
+ for (int i = 0; i < values.length; i++) {
+ values[i] = RandomizedTest.between(0, 5000); // Generates a random integer
Review Comment:
Let's use `random()` inherited from `LuceneTestCase` to ensure failures are reproducible.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
Review Comment:
Similar question as above. What will the user get in this case?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +59,22 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point range query for MATCH_ALL cases
+ final PointValues pointValues = context.reader().getPointValues(field);
+ if (query instanceof MatchAllDocsQuery && !context.reader().hasDeletions()) {
Review Comment:
Maybe we should open a follow-up issue if we want to expand to other use cases.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
Review Comment:
Would users get exceptions that make sense in all the failure cases listed here?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
Review Comment:
Can we add `@lucene.experimental` tags for all the public APIs we're introducing or changing?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong =
+ ArrayUtil.getValue(pointValues.getBytesPerDimension());
+ final long minValue = getLongFromByte(byteToLong, pointValues.getMinPackedValue());
+ final long maxValue = getLongFromByte(byteToLong, pointValues.getMaxPackedValue());
+ long leafMinBucket = Math.floorDiv(minValue, bucketWidth);
+ long leafMaxBucket = Math.floorDiv(maxValue, bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
+ return false;
+ }
+
+ BucketManager collector =
+ new BucketManager(
+ collectorCounts,
+ minValue,
+ bucketWidth,
+ a -> getLongFromByte(byteToLong, a),
+ maxBuckets);
+ PointValues.IntersectVisitor visitor = getIntersectVisitor(collector);
+ try {
+ intersectWithRanges(visitor, pointValues.getPointTree(), collector);
+ } catch (CollectionTerminatedException _) {
+ // Early terminate since no more range to collect
+ }
+ collector.finalizePreviousBucket(null);
+
+ return true;
+ }
+
+ private static void intersectWithRanges(
+ PointValues.IntersectVisitor visitor,
+ PointValues.PointTree pointTree,
+ BucketManager collector)
+ throws IOException {
+ PointValues.Relation r =
+ visitor.compare(pointTree.getMinPackedValue(), pointTree.getMaxPackedValue());
+
+ switch (r) {
+ case CELL_INSIDE_QUERY:
+ collector.countNode((int) pointTree.size());
+ break;
+ case CELL_CROSSES_QUERY:
+ if (pointTree.moveToChild()) {
+ do {
+ intersectWithRanges(visitor, pointTree, collector);
+ } while (pointTree.moveToSibling());
+ pointTree.moveToParent();
+ } else {
+ pointTree.visitDocValues(visitor);
+ }
+ break;
+ case CELL_OUTSIDE_QUERY:
+ }
+ }
+
+ private static long getLongFromByte(Function<byte[], Long> f, byte[] packedValue) {
+ // TODO: Read long correctly instead of downcasting to int
+ return f.apply(packedValue).intValue();
+ }
+
+ private static PointValues.IntersectVisitor getIntersectVisitor(BucketManager collector) {
+ return new PointValues.IntersectVisitor() {
+ @Override
+ public void visit(int docID) {
+ // this branch should be unreachable
+ throw new UnsupportedOperationException(
+ "This IntersectVisitor does not perform any actions on a "
+ + "docID="
+ + docID
+ + " node being visited");
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) throws IOException {
+ if (!collector.withinUpperBound(packedValue)) {
+ collector.finalizePreviousBucket(packedValue);
+ }
+
+ if (collector.withinRange(packedValue)) {
+ collector.count();
+ }
+ }
+
+ @Override
+ public void visit(DocIdSetIterator iterator, byte[] packedValue) throws IOException {
+ if (!collector.withinUpperBound(packedValue)) {
+ collector.finalizePreviousBucket(packedValue);
+ }
+
+ if (collector.withinRange(packedValue)) {
+ for (int doc = iterator.nextDoc(); doc != NO_MORE_DOCS; doc = iterator.nextDoc()) {
+ collector.count();
+ }
+ }
+ }
+
+ @Override
+ public PointValues.Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+ // try to find the first range that may collect values from this cell
+ if (!collector.withinUpperBound(minPackedValue)) {
+ collector.finalizePreviousBucket(minPackedValue);
+ }
+
+ // Not possible to have the CELL_OUTSIDE_QUERY, as bucket lower bound is updated
+ // while finalizing the previous bucket
+ if (collector.withinRange(minPackedValue) && collector.withinRange(maxPackedValue)) {
+ return PointValues.Relation.CELL_INSIDE_QUERY;
+ }
+ return PointValues.Relation.CELL_CROSSES_QUERY;
+ }
+ };
+ }
+
+ private static class BucketManager {
+ private final LongIntHashMap collectorCounts;
+ private int counter = 0;
+ private long startValue;
+ private long endValue;
+ private int nonZeroBuckets = 0;
+ private int maxBuckets;
+ private Function<byte[], Long> byteToLong;
+ private long bucketWidth;
+
+ public BucketManager(
+ LongIntHashMap collectorCounts,
+ long minValue,
+ long bucketWidth,
+ Function<byte[], Long> byteToLong,
+ int maxBuckets) {
+ this.collectorCounts = collectorCounts;
+ this.bucketWidth = bucketWidth;
+ this.startValue = Math.floorDiv(minValue, bucketWidth) * bucketWidth;
+ this.endValue = startValue + bucketWidth;
+ this.byteToLong = byteToLong;
+ this.maxBuckets = maxBuckets;
+ }
+
+ private void count() {
+ counter++;
+ }
+
+ private void countNode(int count) {
+ counter += count;
+ }
+
+ private void finalizePreviousBucket(byte[] packedValue) {
+ // TODO: Can counter ever be 0?
Review Comment:
Commenting so I don't forget to check that the various TODOs are resolved in a future revision.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +59,22 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point range query for MATCH_ALL cases
+ final PointValues pointValues = context.reader().getPointValues(field);
+ if (query instanceof MatchAllDocsQuery && !context.reader().hasDeletions()) {
Review Comment:
Let's stick to the convention that we don't negate using `!`.
##########
lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java:
##########
@@ -801,4 +802,16 @@ public static int compareUnsigned4(byte[] a, int aOffset, byte[] b, int bOffset)
return Integer.compareUnsigned(
(int) BitUtil.VH_BE_INT.get(a, aOffset), (int) BitUtil.VH_BE_INT.get(b, bOffset));
}
+
+ public static Function<byte[], Long> getValue(int numBytes) {
Review Comment:
Is this generic enough that we should define it in a utils file? Even if it is generic enough, is this the right file? Maybe `NumericUtils` would be better?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054847302
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.NumericUtils;
+
+class PointTreeBulkCollector {
+ private static Function<byte[], Long> bytesToLong(int numBytes) {
+ if (numBytes == Long.BYTES) {
+ // Used by LongPoint, DoublePoint
+ return a -> NumericUtils.sortableBytesToLong(a, 0);
+ } else if (numBytes == Integer.BYTES) {
+ // Used by IntPoint, FloatPoint, LatLonPoint, LatLonShape
+ return a -> (long) NumericUtils.sortableBytesToInt(a, 0);
+ }
+
+ return null;
+ }
+
+ static boolean canCollectEfficiently(final PointValues pointValues, final long bucketWidth)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size() for this optimization
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong = bytesToLong(pointValues.getBytesPerDimension());
+ if (byteToLong == null) {
+ return false;
+ }
+
+ long leafMinBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMinPackedValue()), bucketWidth);
+ long leafMaxBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMaxPackedValue()), bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
Review Comment:
I imagine that 512 is the size of leaves with the default codec. It's a bit annoying to rely on a codec parameter. I'm tempted to replace it with a simpler heuristic like the collector does, something like `leafMaxBucket - leafMinBucket <= 1024`.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +65,30 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (query instanceof MatchAllDocsQuery && context.reader().hasDeletions() == false) {
Review Comment:
Maybe replace this condition with `weight.count(context) == context.reader().maxDoc()` to make it a bit more generic, e.g. it could be a range query that happens to fully match the segment.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.NumericUtils;
+
+class PointTreeBulkCollector {
+ private static Function<byte[], Long> bytesToLong(int numBytes) {
+ if (numBytes == Long.BYTES) {
+ // Used by LongPoint, DoublePoint
+ return a -> NumericUtils.sortableBytesToLong(a, 0);
+ } else if (numBytes == Integer.BYTES) {
+ // Used by IntPoint, FloatPoint, LatLonPoint, LatLonShape
+ return a -> (long) NumericUtils.sortableBytesToInt(a, 0);
+ }
+
+ return null;
+ }
+
+ static boolean canCollectEfficiently(final PointValues pointValues, final long bucketWidth)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size() for this optimization
Review Comment:
I think so, the collector makes sure to count each doc only once, including docs that have two values that fall into the same bucket.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054876160
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.NumericUtils;
+
+class PointTreeBulkCollector {
+ private static Function<byte[], Long> bytesToLong(int numBytes) {
+ if (numBytes == Long.BYTES) {
+ // Used by LongPoint, DoublePoint
+ return a -> NumericUtils.sortableBytesToLong(a, 0);
+ } else if (numBytes == Integer.BYTES) {
+ // Used by IntPoint, FloatPoint, LatLonPoint, LatLonShape
+ return a -> (long) NumericUtils.sortableBytesToInt(a, 0);
+ }
+
+ return null;
+ }
+
+ static boolean canCollectEfficiently(final PointValues pointValues, final long bucketWidth)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size() for this optimization
Review Comment:
Ah, thats a good point! I was thinking of cases, when two values are across two buckets, but two values falling in same bucket makes the condition obvious
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054906523
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.NumericUtils;
+
+class PointTreeBulkCollector {
+ private static Function<byte[], Long> bytesToLong(int numBytes) {
+ if (numBytes == Long.BYTES) {
+ // Used by LongPoint, DoublePoint
+ return a -> NumericUtils.sortableBytesToLong(a, 0);
+ } else if (numBytes == Integer.BYTES) {
+ // Used by IntPoint, FloatPoint, LatLonPoint, LatLonShape
+ return a -> (long) NumericUtils.sortableBytesToInt(a, 0);
+ }
+
+ return null;
+ }
+
+ static boolean canCollectEfficiently(final PointValues pointValues, final long bucketWidth)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size() for this optimization
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()) {
+ return false;
+ }
+
+ final Function<byte[], Long> byteToLong = bytesToLong(pointValues.getBytesPerDimension());
+ if (byteToLong == null) {
+ return false;
+ }
+
+ long leafMinBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMinPackedValue()), bucketWidth);
+ long leafMaxBucket =
+ Math.floorDiv(byteToLong.apply(pointValues.getMaxPackedValue()), bucketWidth);
+
+ // We want that # leaf nodes is more than # buckets so that we can completely skip over
+ // some of the leaf nodes. Higher this ratio, more efficient it is than naive approach!
+ if ((pointValues.size() / 512) < (leafMaxBucket - leafMinBucket)) {
Review Comment:
> I imagine that 512 is the size of leaves with the default codec. It's a bit annoying to rely on a codec parameter. I'm tempted to replace it with a simpler heuristic like the collector does, something like leafMaxBucket - leafMinBucket <= 1024.
While I share your annoyance of relying on codec parameter, `leafMaxBucket - leafMinBucket <= 1024` works for prior case as it uses dense array that is just function of this. But here, if we collect billion documents, even ` leafMaxBucket - leafMinBucket <= 10^5` is fairly reasonable. Maybe we can use something more generic and reasonable like 1000 instead of sticking exactly to the codec parameter?
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054995845
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
+ static boolean collect(
+ final PointValues pointValues,
+ final long bucketWidth,
+ final LongIntHashMap collectorCounts,
+ final int maxBuckets)
+ throws IOException {
+ // TODO: Do we really need pointValues.getDocCount() == pointValues.size()
+ if (pointValues == null
+ || pointValues.getNumDimensions() != 1
+ || pointValues.getDocCount() != pointValues.size()
+ || ArrayUtil.getValue(pointValues.getBytesPerDimension()) == null) {
+ return false;
Review Comment:
I think we can keep this for now as is. The way to read it is, it works same as before including exceptions and everything. There is possibly optimized path if pointValues are indexed. I have created another issue for tackling this specific scenario - https://github.com/apache/lucene/issues/14536. Might need some more changes or slightly different approach to `PointTreeBulkCollector`
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2054986918
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/PointTreeBulkCollector.java:
##########
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.facet.plain.histograms;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.function.Function;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.internal.hppc.LongIntHashMap;
+import org.apache.lucene.search.CollectionTerminatedException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.ArrayUtil;
+
+class PointTreeBulkCollector {
Review Comment:
> There are other files in sandbox with experimental tags, so maybe better safe then sorry?
Yup, adding the tag!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2825127094
> Oooh those JMH benchy results are nice! Though, it's dangerous testing only on random data -- you can draw random conclusions/results. But it's better than no benchmark! Maybe we should add histogram faceting benchy to Lucene's nightly benchmarks?
Thanks @mikemccand for the feedback. Having histogram faceting benchmark in Lucene's nightly will be great! Created issue https://github.com/mikemccand/luceneutil/issues/375 for following up on 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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2819914834
@stefanvodita - Thanks for a prompt review. Addressed most of the review comments. Adding JMH benchmark instead of the not so useful performance test added earlier. The benchark results demonstrate significant increase in throughput with increasing # documents and bucket width (lesser buckets mean less low level traversal in point range tree and more documents collected in bulk):
```
Benchmark (bucketWidth) (docCount) (pointEnabled) Mode Cnt Score Error Units
HistogramCollectorBenchmark.collectHistogram 5000 500000 true thrpt 3 2114.002 ± 46.852 ops/s
HistogramCollectorBenchmark.collectHistogram 5000 500000 false thrpt 3 1236.532 ± 724.312 ops/s
HistogramCollectorBenchmark.collectHistogram 5000 5000000 true thrpt 3 220.636 ± 17.688 ops/s
HistogramCollectorBenchmark.collectHistogram 5000 5000000 false thrpt 3 147.054 ± 37.055 ops/s
HistogramCollectorBenchmark.collectHistogram 25000 500000 true thrpt 3 9788.181 ± 4388.445 ops/s
HistogramCollectorBenchmark.collectHistogram 25000 500000 false thrpt 3 1227.537 ± 21.222 ops/s
HistogramCollectorBenchmark.collectHistogram 25000 5000000 true thrpt 3 856.278 ± 840.625 ops/s
HistogramCollectorBenchmark.collectHistogram 25000 5000000 false thrpt 3 145.322 ± 86.603 ops/s
```
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2784239065
@stefanvodita / @jpountz - Would love to get your thoughts on this optimization, and how we can leverage it in Lucene. In a nutshell, it solves the below problem:
Given a sorted non-overlapping set of intervals (Histogram buckets could be an example), it collects the matching documents count in single travel of `PointsTree` index, by skipping over the `leafBlocks` completely unless the values in `leafBlock` overlap with more than one interval. This ensures that the `# leafBlocks` actually traversed is bounded by the `# buckets` and remaining `leafBlocks` are collected in bulk. Hence it can very efficiently collect the doc counts, especially when the `# documents / # buckets` is pretty high.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "stefanvodita (via GitHub)" <gi...@apache.org>.
stefanvodita commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2059130450
##########
lucene/CHANGES.txt:
##########
@@ -78,6 +78,8 @@ Optimizations
---------------------
* GITHUB#14418: Quick exit on filter query matching no docs when rewriting knn query. (Pan Guixin)
+* GITHUB#14439: Efficient Histogram Collection using multi range traversal over PointTrees
Review Comment:
You should add your name too!
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2814740258
Addressed most of the review comments. Ran small performance benchmark to see the difference, and we can see some even with small number of documents:
Bulk time is new approach, and skip index time is the existing
With 100k docs, and 5k bucketWidth
```
1> Bulk time was : 10593417 vs skip index time : 12941417
1> Bulk time was : 1006750 vs skip index time : 3241959
1> Bulk time was : 770916 vs skip index time : 4690875
1> Bulk time was : 870917 vs skip index time : 2621291
1> Bulk time was : 754709 vs skip index time : 3175500
1> Bulk time was : 1389750 vs skip index time : 2557125
1> Bulk time was : 788125 vs skip index time : 4633541
1> Bulk time was : 767125 vs skip index time : 5078917
1> Bulk time was : 727208 vs skip index time : 6333083
1> Bulk time was : 755250 vs skip index time : 3179917
```
With 250k documents, and 10k bucketWidth:
```
1> Bulk time was : 14125250 vs skip index time : 20235666
1> Bulk time was : 915583 vs skip index time : 15929834
1> Bulk time was : 886959 vs skip index time : 15842375
1> Bulk time was : 904667 vs skip index time : 10911500
1> Bulk time was : 801959 vs skip index time : 10846750
1> Bulk time was : 844834 vs skip index time : 14980917
1> Bulk time was : 855209 vs skip index time : 5865500
1> Bulk time was : 804334 vs skip index time : 15966667
1> Bulk time was : 805042 vs skip index time : 11613791
1> Bulk time was : 830958 vs skip index time : 11036833
```
As we can see the difference is bit more pronounced with increasing number of documents and wide enough bucketWidth.
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2056686537
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +65,30 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (query instanceof MatchAllDocsQuery && context.reader().hasDeletions() == false) {
Review Comment:
Oh yeah, that's a good point! Hadn't thought about queries on other fields. Changed
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on code in PR #14439:
URL: https://github.com/apache/lucene/pull/14439#discussion_r2056834941
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/facet/plain/histograms/HistogramCollector.java:
##########
@@ -53,11 +63,31 @@ public LeafCollector getLeafCollector(LeafReaderContext context) throws IOExcept
// The segment has no values, nothing to do.
throw new CollectionTerminatedException();
}
+
+ // We can use multi range traversal logic to collect the histogram on numeric
+ // field indexed as point for MATCH_ALL cases. In future, this can be extended
+ // for Point Range Query cases as well
+ if (context.reader().hasDeletions() == false
+ && weight.count(context) == context.reader().maxDoc()) {
Review Comment:
Added `null` check
--
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] Logic for collecting Histogram efficiently using Point Trees [lucene]
Posted by "jainankitk (via GitHub)" <gi...@apache.org>.
jainankitk commented on PR #14439:
URL: https://github.com/apache/lucene/pull/14439#issuecomment-2791267186
> Sorry, I only had a quick look. Is the opimisation here analogous to the one `HistogramLeafCollector` does with the skipper?
No, this approach is different from the skipper as it leverages `PointValues` instead of `DocValues` for computing the buckets
--
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