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-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
