You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2025/01/16 06:54:35 UTC

(lucene) branch branch_10x updated: Implement IntersectVisitor#visit(IntsRef) whenever it makes sense (#14138)

This is an automated email from the ASF dual-hosted git repository.

ivera pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_10x by this push:
     new 264f75cef13 Implement IntersectVisitor#visit(IntsRef) whenever it makes sense (#14138)
264f75cef13 is described below

commit 264f75cef13d18b775fe6f176a7c77dc14ebdd86
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Thu Jan 16 07:52:43 2025 +0100

    Implement IntersectVisitor#visit(IntsRef) whenever it makes sense (#14138)
    
    Implement IntersectVisitor#visit(IntsRef) in many of the current implementations and add
    BulkAdder#add(IntsRef) method. They should provide better performance due to less virtual
    method calls and more efficient bulk processing.
---
 lucene/CHANGES.txt                                 |  4 ++
 .../lucene/document/LatLonPointDistanceQuery.java  | 14 +++++++
 .../lucene/document/LongDistanceFeatureQuery.java  | 16 ++++++++
 .../apache/lucene/document/RangeFieldQuery.java    | 10 ++++-
 .../org/apache/lucene/document/SpatialQuery.java   | 44 ++++++++++++++++++++
 .../lucene/document/XYPointInGeometryQuery.java    |  6 +++
 .../org/apache/lucene/search/PointRangeQuery.java  |  4 +-
 .../org/apache/lucene/util/DocIdSetBuilder.java    | 48 +++++++++++++---------
 .../java/org/apache/lucene/util/bkd/BKDReader.java | 14 +++++++
 .../apache/lucene/util/TestDocIdSetBuilder.java    | 19 ++++++---
 .../spatial3d/PointInShapeIntersectVisitor.java    |  6 +++
 11 files changed, 154 insertions(+), 31 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index c1c8fa32e5c..716c437eb79 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -29,6 +29,10 @@ Improvements
 
 * GITHUB#14113: Remove unnecessary ByteArrayDataInput allocations from `Lucene90DocValuesProducer$TermsDict.decompressBlock`. (Ankit Jain)
 
+* GITHUB#14138: Implement IntersectVisitor#visit(IntsRef) in  many of the current implementations and add
+  BulkAdder#add(IntsRef) method. They should provide better performance due to less virtual method calls and
+  more efficient bulk processing. (Ignacio Vera)
+
 Optimizations
 ---------------------
 
diff --git a/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java b/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
index 7f5f8cf6290..9cebb8e7301 100644
--- a/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -44,6 +44,7 @@ import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.BitSetIterator;
 import org.apache.lucene.util.DocIdSetBuilder;
 import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.NumericUtils;
 
 /** Distance query for {@link LatLonPoint}. */
@@ -233,6 +234,11 @@ final class LatLonPointDistanceQuery extends Query {
             adder.add(docID);
           }
 
+          @Override
+          public void visit(IntsRef ref) {
+            adder.add(ref);
+          }
+
           @Override
           public void visit(DocIdSetIterator iterator) throws IOException {
             adder.add(iterator);
@@ -269,6 +275,14 @@ final class LatLonPointDistanceQuery extends Query {
             cost[0]--;
           }
 
+          @Override
+          public void visit(IntsRef ref) {
+            for (int i = 0; i < ref.length; i++) {
+              result.clear(ref.ints[ref.offset + i]);
+            }
+            cost[0] = -ref.length;
+          }
+
           @Override
           public void visit(DocIdSetIterator iterator) throws IOException {
             result.andNot(iterator);
diff --git a/lucene/core/src/java/org/apache/lucene/document/LongDistanceFeatureQuery.java b/lucene/core/src/java/org/apache/lucene/document/LongDistanceFeatureQuery.java
index c675136ca80..788ded4909b 100644
--- a/lucene/core/src/java/org/apache/lucene/document/LongDistanceFeatureQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/LongDistanceFeatureQuery.java
@@ -35,6 +35,7 @@ import org.apache.lucene.search.Scorer;
 import org.apache.lucene.search.ScorerSupplier;
 import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.NumericUtils;
 
 final class LongDistanceFeatureQuery extends Query {
@@ -405,6 +406,21 @@ final class LongDistanceFeatureQuery extends Query {
               adder.add(docID);
             }
 
+            @Override
+            public void visit(DocIdSetIterator iterator) throws IOException {
+              int docID;
+              while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+                visit(docID);
+              }
+            }
+
+            @Override
+            public void visit(IntsRef ref) {
+              for (int i = 0; i < ref.length; ++i) {
+                visit(ref.ints[ref.offset + i]);
+              }
+            }
+
             @Override
             public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
               long minDocValue = NumericUtils.sortableBytesToLong(minPackedValue, 0);
diff --git a/lucene/core/src/java/org/apache/lucene/document/RangeFieldQuery.java b/lucene/core/src/java/org/apache/lucene/document/RangeFieldQuery.java
index f5747c0f8bd..8248441f3cd 100644
--- a/lucene/core/src/java/org/apache/lucene/document/RangeFieldQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/RangeFieldQuery.java
@@ -38,6 +38,7 @@ import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.ArrayUtil.ByteArrayComparator;
 import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.IntsRef;
 
 /**
  * Query class for searching {@code RangeField} types by a defined {@link Relation}.
@@ -401,7 +402,12 @@ public abstract class RangeFieldQuery extends Query {
           }
 
           @Override
-          public void visit(int docID) throws IOException {
+          public void visit(IntsRef ref) {
+            adder.add(ref);
+          }
+
+          @Override
+          public void visit(int docID) {
             adder.add(docID);
           }
 
@@ -411,7 +417,7 @@ public abstract class RangeFieldQuery extends Query {
           }
 
           @Override
-          public void visit(int docID, byte[] leaf) throws IOException {
+          public void visit(int docID, byte[] leaf) {
             if (queryType.matches(ranges, leaf, numDims, bytesPerDim, comparator)) {
               visit(docID);
             }
diff --git a/lucene/core/src/java/org/apache/lucene/document/SpatialQuery.java b/lucene/core/src/java/org/apache/lucene/document/SpatialQuery.java
index 811591d9a1c..cc233f89948 100644
--- a/lucene/core/src/java/org/apache/lucene/document/SpatialQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/SpatialQuery.java
@@ -49,6 +49,7 @@ import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.BitSetIterator;
 import org.apache.lucene.util.DocIdSetBuilder;
 import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IntsRef;
 
 /**
  * Base query class for all spatial geometries: {@link LatLonShape}, {@link LatLonPoint} and {@link
@@ -445,6 +446,11 @@ abstract class SpatialQuery extends Query {
         adder.add(iterator);
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        adder.add(ref);
+      }
+
       @Override
       public void visit(int docID, byte[] t) {
         if (leafPredicate.test(t)) {
@@ -489,6 +495,14 @@ abstract class SpatialQuery extends Query {
         cost[0] += iterator.cost();
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        for (int i = 0; i < ref.length; i++) {
+          result.set(ref.ints[ref.offset + i]);
+        }
+        cost[0] += ref.length;
+      }
+
       @Override
       public void visit(int docID, byte[] t) {
         if (result.get(docID) == false) {
@@ -532,6 +546,14 @@ abstract class SpatialQuery extends Query {
         cost[0]++;
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        for (int i = 0; i < ref.length; i++) {
+          result.set(ref.ints[ref.offset + i]);
+        }
+        cost[0] += ref.length;
+      }
+
       @Override
       public void visit(DocIdSetIterator iterator) throws IOException {
         result.or(iterator);
@@ -589,6 +611,13 @@ abstract class SpatialQuery extends Query {
         excluded.or(iterator);
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        for (int i = 0; i < ref.length; i++) {
+          visit(ref.ints[ref.offset + i]);
+        }
+      }
+
       @Override
       public void visit(int docID, byte[] t) {
         if (excluded.get(docID) == false) {
@@ -643,6 +672,14 @@ abstract class SpatialQuery extends Query {
         cost[0]--;
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        for (int i = 0; i < ref.length; i++) {
+          result.clear(ref.ints[ref.offset + i]);
+        }
+        cost[0] -= ref.length;
+      }
+
       @Override
       public void visit(DocIdSetIterator iterator) throws IOException {
         result.andNot(iterator);
@@ -693,6 +730,13 @@ abstract class SpatialQuery extends Query {
         result.andNot(iterator);
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        for (int i = 0; i < ref.length; i++) {
+          visit(ref.ints[ref.offset + i]);
+        }
+      }
+
       @Override
       public void visit(int docID, byte[] packedTriangle) {
         // NO-OP
diff --git a/lucene/core/src/java/org/apache/lucene/document/XYPointInGeometryQuery.java b/lucene/core/src/java/org/apache/lucene/document/XYPointInGeometryQuery.java
index 47b6abb46c2..833d9c9209c 100644
--- a/lucene/core/src/java/org/apache/lucene/document/XYPointInGeometryQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/XYPointInGeometryQuery.java
@@ -38,6 +38,7 @@ import org.apache.lucene.search.Scorer;
 import org.apache.lucene.search.ScorerSupplier;
 import org.apache.lucene.search.Weight;
 import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.IntsRef;
 
 /**
  * Finds all previously indexed points that fall within the specified XY geometries.
@@ -90,6 +91,11 @@ final class XYPointInGeometryQuery extends Query {
         adder.add(iterator);
       }
 
+      @Override
+      public void visit(IntsRef ref) {
+        adder.add(ref);
+      }
+
       @Override
       public void visit(int docID, byte[] packedValue) {
         double x = XYEncodingUtils.decode(packedValue, 0);
diff --git a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
index 1b6d6869c19..e5d956e8d1e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
@@ -188,9 +188,7 @@ public abstract class PointRangeQuery extends Query {
 
           @Override
           public void visit(IntsRef ref) {
-            for (int i = ref.offset; i < ref.offset + ref.length; i++) {
-              adder.add(ref.ints[i]);
-            }
+            adder.add(ref);
           }
 
           @Override
diff --git a/lucene/core/src/java/org/apache/lucene/util/DocIdSetBuilder.java b/lucene/core/src/java/org/apache/lucene/util/DocIdSetBuilder.java
index 28128af05f6..159cef02567 100644
--- a/lucene/core/src/java/org/apache/lucene/util/DocIdSetBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/DocIdSetBuilder.java
@@ -41,29 +41,28 @@ public final class DocIdSetBuilder {
    *
    * @see DocIdSetBuilder#grow
    */
-  public abstract static class BulkAdder {
-    public abstract void add(int doc);
+  public sealed interface BulkAdder permits FixedBitSetAdder, BufferAdder {
+    void add(int doc);
 
-    public void add(DocIdSetIterator iterator) throws IOException {
-      int docID;
-      while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
-        add(docID);
-      }
-    }
-  }
+    void add(IntsRef docs);
 
-  private static class FixedBitSetAdder extends BulkAdder {
-    final FixedBitSet bitSet;
+    void add(DocIdSetIterator iterator) throws IOException;
+  }
 
-    FixedBitSetAdder(FixedBitSet bitSet) {
-      this.bitSet = bitSet;
-    }
+  private record FixedBitSetAdder(FixedBitSet bitSet) implements BulkAdder {
 
     @Override
     public void add(int doc) {
       bitSet.set(doc);
     }
 
+    @Override
+    public void add(IntsRef docs) {
+      for (int i = 0; i < docs.length; i++) {
+        bitSet.set(docs.ints[docs.offset + i]);
+      }
+    }
+
     @Override
     public void add(DocIdSetIterator iterator) throws IOException {
       bitSet.or(iterator);
@@ -85,17 +84,26 @@ public final class DocIdSetBuilder {
     }
   }
 
-  private static class BufferAdder extends BulkAdder {
-    final Buffer buffer;
-
-    BufferAdder(Buffer buffer) {
-      this.buffer = buffer;
-    }
+  private record BufferAdder(Buffer buffer) implements BulkAdder {
 
     @Override
     public void add(int doc) {
       buffer.array[buffer.length++] = doc;
     }
+
+    @Override
+    public void add(IntsRef docs) {
+      System.arraycopy(docs.ints, docs.offset, buffer.array, buffer.length, docs.length);
+      buffer.length += docs.length;
+    }
+
+    @Override
+    public void add(DocIdSetIterator iterator) throws IOException {
+      int docID;
+      while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+        add(docID);
+      }
+    }
   }
 
   private final int maxDoc;
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
index 0efcc2ef465..a90c79a8c80 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
@@ -24,6 +24,7 @@ import org.apache.lucene.search.DocIdSetIterator;
 import org.apache.lucene.store.IndexInput;
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.MathUtil;
 
 /**
@@ -146,6 +147,19 @@ public class BKDReader extends PointValues {
             count[0]++;
           }
 
+          @Override
+          public void visit(DocIdSetIterator iterator) throws IOException {
+            int docID;
+            while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+              visit(docID);
+            }
+          }
+
+          @Override
+          public void visit(IntsRef ref) {
+            count[0] += ref.length;
+          }
+
           @Override
           public void visit(int docID, byte[] packedValue) {
             throw new AssertionError();
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestDocIdSetBuilder.java b/lucene/core/src/test/org/apache/lucene/util/TestDocIdSetBuilder.java
index 88dbf24e2d1..1d9079a203f 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestDocIdSetBuilder.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestDocIdSetBuilder.java
@@ -130,13 +130,20 @@ public class TestDocIdSetBuilder extends LuceneTestCase {
       for (j = 0; j < array.length; ) {
         final int l = TestUtil.nextInt(random(), 1, array.length - j);
         DocIdSetBuilder.BulkAdder adder = null;
-        for (int k = 0, budget = 0; k < l; ++k) {
-          if (budget == 0 || rarely()) {
-            budget = TestUtil.nextInt(random(), 1, l - k + 5);
-            adder = builder.grow(budget);
+        if (usually()) {
+          for (int k = 0, budget = 0; k < l; ++k) {
+            if (budget == 0 || rarely()) {
+              budget = TestUtil.nextInt(random(), 1, l - k + 5);
+              adder = builder.grow(budget);
+            }
+            adder.add(array[j++]);
+            budget--;
           }
-          adder.add(array[j++]);
-          budget--;
+        } else {
+          IntsRef intsRef = new IntsRef(array, j, l);
+          adder = builder.grow(l);
+          adder.add(intsRef);
+          j += l;
         }
       }
 
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
index 8883fef2240..9b990b08e47 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/PointInShapeIntersectVisitor.java
@@ -27,6 +27,7 @@ import org.apache.lucene.spatial3d.geom.GeoShape;
 import org.apache.lucene.spatial3d.geom.PlanetModel.DocValueEncoder;
 import org.apache.lucene.spatial3d.geom.XYZBounds;
 import org.apache.lucene.util.DocIdSetBuilder;
+import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.NumericUtils;
 
 class PointInShapeIntersectVisitor implements IntersectVisitor {
@@ -67,6 +68,11 @@ class PointInShapeIntersectVisitor implements IntersectVisitor {
     adder.add(iterator);
   }
 
+  @Override
+  public void visit(IntsRef ref) throws IOException {
+    adder.add(ref);
+  }
+
   @Override
   public void visit(int docID, byte[] packedValue) {
     assert packedValue.length == 12;