[GitHub] [lucene] iverase commented on a change in pull request #687: LUCENE-10425：speed up IndexSortSortedNumericDocValuesRangeQuery#BoundedDocSetIdIterator construction using bkd binary search

[GitBox <gi...@apache.org>]

iverase commented on a change in pull request #687:
URL: https://github.com/apache/lucene/pull/687#discussion_r815921747



##########
File path: lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java
##########
@@ -181,12 +189,143 @@ public int count(LeafReaderContext context) throws IOException {
     };
   }
 
+  /**
+   * Returns the first document whose packed value is greater than or equal (if allowEqual is true) to the provided packed value
+   * or -1 if all packed values are smaller than the provided one,
+   */
+  public final int nextDoc(PointValues values, byte[] packedValue, boolean allowEqual) throws IOException {
+      final int numIndexDimensions = values.getNumIndexDimensions();
+      final int bytesPerDim = values.getBytesPerDimension();
+      final ByteArrayComparator comparator = ArrayUtil.getUnsignedComparator(bytesPerDim);
+      final Predicate<byte[]> biggerThan = testPackedValue -> {
+          for (int dim = 0; dim < numIndexDimensions; dim++) {
+              final int offset = dim * bytesPerDim;
+              if (allowEqual) {
+                  if (comparator.compare(testPackedValue, offset, packedValue, offset) < 0) {
+                      return false;
+                  }
+              } else {
+                  if (comparator.compare(testPackedValue, offset, packedValue, offset) <= 0) {
+                      return false;
+                  }
+              }
+          }
+          return true;
+      };
+      return nextDoc(values.getPointTree(), biggerThan);
+  }
+
+  private int nextDoc(PointValues.PointTree pointTree, Predicate<byte[]> biggerThan) throws IOException {
+      if (biggerThan.test(pointTree.getMaxPackedValue()) == false) {
+          // doc is before us
+          return -1;
+      } else if (pointTree.moveToChild()) {
+          // navigate down
+          do {
+              final int doc = nextDoc(pointTree, biggerThan);
+              if (doc != -1) {
+                  return doc;
+              }
+          } while (pointTree.moveToSibling());
+          pointTree.moveToParent();
+          return -1;
+      } else {
+          // doc is in this leaf
+          final int[] doc = { -1 };
+          pointTree.visitDocValues(new IntersectVisitor() {
+              @Override
+              public void visit(int docID) {
+                  throw new AssertionError("Invalid call to visit(docID)");
+              }
+
+              @Override
+              public void visit(int docID, byte[] packedValue) {
+                  if (doc[0] == -1 && biggerThan.test(packedValue)) {
+                      doc[0] = docID;
+                  }
+              }
+
+              @Override
+              public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
+                  return Relation.CELL_CROSSES_QUERY;
+              }
+          });
+          return doc[0];
+      }
+  }
+
+  private boolean matchAll(PointValues points, byte[] queryLowerPoint, byte[] queryUpperPoint) throws IOException {
+      final ByteArrayComparator comparator = ArrayUtil.getUnsignedComparator(points.getBytesPerDimension());
+      for (int dim = 0; dim < points.getNumDimensions(); dim++) {
+          int offset = dim * points.getBytesPerDimension();
+          if (comparator.compare(points.getMinPackedValue(), offset, queryUpperPoint, offset) > 0) {
+              return false;
+          }
+          if (comparator.compare(points.getMaxPackedValue(), offset, queryLowerPoint, offset) < 0) {
+              return false;
+          }
+          if (comparator.compare(points.getMinPackedValue(), offset, queryLowerPoint, offset) < 0
+              || comparator.compare(points.getMaxPackedValue(), offset, queryUpperPoint, offset) > 0) {
+              return false;
+          }
+      }
+      return true;
+  }
+
+  private BoundedDocSetIdIterator getDocIdSetIteratorOrNullFromBkd(LeafReaderContext context, DocIdSetIterator delegate)
+      throws IOException {
+      Sort indexSort = context.reader().getMetaData().getSort();
+      if (indexSort != null
+          && indexSort.getSort().length > 0
+          && indexSort.getSort()[0].getField().equals(field)
+          && !indexSort.getSort()[0].getReverse()) {

Review comment:
       We prefer to explicitly equal to false than to use the `!` operator for readability.
   

##########
File path: lucene/sandbox/src/java/org/apache/lucene/sandbox/search/IndexSortSortedNumericDocValuesRangeQuery.java
##########
@@ -308,8 +449,10 @@ public int advance(int target) throws IOException {
       if (target < firstDoc) {
         target = firstDoc;
       }
-
-      int result = delegate.advance(target);
+      int result = target;
+      if(!allDocExist) {

Review comment:
       We prefer to explicitly equal to false than to use the `!` operator for readability.

##########
File path: lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestIndexSortSortedNumericDocValuesRangeQuery.java
##########
@@ -483,6 +483,65 @@ public void testCount() throws IOException {
     dir.close();
   }
 
+  public void testCountWithBkd() throws IOException {

Review comment:
       I think we should add a stronger random test case to cover as many cases as possible?




-- 
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