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

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

iverase commented on pull request #687:
URL: https://github.com/apache/lucene/pull/687#issuecomment-1053981720


   I like this idea but I agree with Adrien that the API change does not look right. More over, I don't think we need to add it to PointValues as this is something specific for Index sorting and it won't apply in all situation. I think it makes little sense when we use the kd-tree as an effective r-tree like in range fields.
   
   I think it is possible to add a specific implementation on `IndexSortSortedNumericDocValuesRangeQuery` that does not require on an API change. I came up with this implementation, something closer to that should work?
   
   ```
     /**
      * Returns the first document whose packed value is greater than or equal 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) 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 (comparator.compare(packedValue, offset, testPackedValue, 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())) {
             // 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) == false) {
                         doc[0] = docID;
                     }
                 }
   
                 @Override
                 public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
                     return Relation.CELL_CROSSES_QUERY;
                 }
             });
             assert doc[0] != -1;
             return doc[0];
         }
     }
   ```
   
   
   


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