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 2019/10/04 05:13:40 UTC
[lucene-solr] branch master updated: LUCENE-8860: add additional
leaf node level optimizations in LatLonShapeBoundingBoxQuery. (#844)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/master by this push:
new d4ab808 LUCENE-8860: add additional leaf node level optimizations in LatLonShapeBoundingBoxQuery. (#844)
d4ab808 is described below
commit d4ab808a8ab8c58a9ddbc7d4f108df7f1f4c0b51
Author: Igor Motov <ig...@motovs.org>
AuthorDate: Fri Oct 4 01:13:34 2019 -0400
LUCENE-8860: add additional leaf node level optimizations in LatLonShapeBoundingBoxQuery. (#844)
---
lucene/CHANGES.txt | 3 +
.../document/LatLonShapeBoundingBoxQuery.java | 3 +
.../lucene/document/XYShapeBoundingBoxQuery.java | 3 +
.../java/org/apache/lucene/geo/Rectangle2D.java | 77 ++++++++++++++++++++--
.../org/apache/lucene/geo/TestRectangle2D.java | 58 +++++++++++++++-
5 files changed, 136 insertions(+), 8 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 5bfec58..5883abf 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -154,6 +154,9 @@ the total hits is not requested.
* LUCENE-8755: spatial-extras quad and packed quad prefix trees now index points faster.
(Chongchen Chen, David Smiley)
+* LUCENE-8860: add additional leaf node level optimizations in LatLonShapeBoundingBoxQuery.
+ (Igor Motov via Ignacio Vera)
+
* LUCENE-8968: Improve performance of WITHIN and DISJOINT queries for Shape queries by
doing just one pass whenever possible. (Ignacio Vera)
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
index 9f7f326..aa1f93d 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -42,6 +42,9 @@ final class LatLonShapeBoundingBoxQuery extends ShapeQuery {
@Override
protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ if (queryRelation == QueryRelation.INTERSECTS || queryRelation == QueryRelation.DISJOINT) {
+ return rectangle2D.intersectRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ }
return rectangle2D.relateRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
}
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
index dd809e4..4a9e465 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/XYShapeBoundingBoxQuery.java
@@ -41,6 +41,9 @@ public class XYShapeBoundingBoxQuery extends ShapeQuery {
@Override
protected PointValues.Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ if (queryRelation == QueryRelation.INTERSECTS || queryRelation == QueryRelation.DISJOINT) {
+ return rectangle2D.intersectRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ }
return rectangle2D.relateRangeBBox(minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
}
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
index c200537..b3fdf0e 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Rectangle2D.java
@@ -105,16 +105,28 @@ public class Rectangle2D {
return bboxContainsPoint(x, y, this.minX, this.maxX, this.minY, this.maxY);
}
- /** compare this to a provided rangle bounding box **/
+ /** compare this to a provided range bounding box **/
public Relation relateRangeBBox(int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
- Relation eastRelation = compareBBoxToRangeBBox(this.bbox, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ Relation eastRelation = compareBBoxToRangeBBox(this.bbox,
+ minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
if (this.crossesDateline() && eastRelation == Relation.CELL_OUTSIDE_QUERY) {
return compareBBoxToRangeBBox(this.west, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
}
return eastRelation;
}
+ /** intersects this to a provided range bounding box **/
+ public Relation intersectRangeBBox(int minXOffset, int minYOffset, byte[] minTriangle,
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ Relation eastRelation = intersectBBoxWithRangeBBox(this.bbox,
+ minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ if (this.crossesDateline() && eastRelation == Relation.CELL_OUTSIDE_QUERY) {
+ return intersectBBoxWithRangeBBox(this.west, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle);
+ }
+ return eastRelation;
+ }
+
/** Checks if the rectangle intersects the provided triangle **/
public boolean intersectsTriangle(int aX, int aY, int bX, int bY, int cX, int cY) {
// 1. query contains any triangle points
@@ -165,15 +177,14 @@ public class Rectangle2D {
return bboxContainsTriangle(ax, ay, bx, by, cx, cy, minX, maxX, minY, maxY);
}
- /** static utility method to compare a bbox with a range of triangles (just the bbox of the triangle collection) */
+ /**
+ * static utility method to compare a bbox with a range of triangles (just the bbox of the triangle collection)
+ **/
private static Relation compareBBoxToRangeBBox(final byte[] bbox,
int minXOffset, int minYOffset, byte[] minTriangle,
int maxXOffset, int maxYOffset, byte[] maxTriangle) {
// check bounding box (DISJOINT)
- if (Arrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) > 0 ||
- Arrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, BYTES, 2 * BYTES) < 0 ||
- Arrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) > 0 ||
- Arrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 0, BYTES) < 0) {
+ if (disjoint(bbox, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle)) {
return Relation.CELL_OUTSIDE_QUERY;
}
@@ -183,10 +194,62 @@ public class Rectangle2D {
Arrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0) {
return Relation.CELL_INSIDE_QUERY;
}
+
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ /**
+ * static utility method to compare a bbox with a range of triangles (just the bbox of the triangle collection)
+ * for intersection
+ **/
+ private static Relation intersectBBoxWithRangeBBox(final byte[] bbox,
+ int minXOffset, int minYOffset, byte[] minTriangle,
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ // check bounding box (DISJOINT)
+ if (disjoint(bbox, minXOffset, minYOffset, minTriangle, maxXOffset, maxYOffset, maxTriangle)) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+
+ if (Arrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, BYTES, 2 * BYTES) >= 0 &&
+ Arrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 0, BYTES) >= 0 ) {
+ if (Arrays.compareUnsigned(maxTriangle, minXOffset, minXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) <= 0 &&
+ Arrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ if (Arrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) <= 0 &&
+ Arrays.compareUnsigned(maxTriangle, minYOffset, minYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ }
+
+ if (Arrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) <= 0 &&
+ Arrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) <= 0 ) {
+ if (Arrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, BYTES, 2 * BYTES) >= 0 &&
+ Arrays.compareUnsigned(minTriangle, maxYOffset, maxYOffset + BYTES, bbox, 0, BYTES) >= 0) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ if (Arrays.compareUnsigned(minTriangle, maxXOffset, maxXOffset + BYTES, bbox, BYTES, 2 * BYTES) >= 0 &&
+ Arrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 0, BYTES) >= 0) {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ }
+
return Relation.CELL_CROSSES_QUERY;
}
/**
+ * static utility method to check a bbox is disjoint with a range of triangles
+ **/
+ private static boolean disjoint(final byte[] bbox,
+ int minXOffset, int minYOffset, byte[] minTriangle,
+ int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+ return Arrays.compareUnsigned(minTriangle, minXOffset, minXOffset + BYTES, bbox, 3 * BYTES, 4 * BYTES) > 0 ||
+ Arrays.compareUnsigned(maxTriangle, maxXOffset, maxXOffset + BYTES, bbox, BYTES, 2 * BYTES) < 0 ||
+ Arrays.compareUnsigned(minTriangle, minYOffset, minYOffset + BYTES, bbox, 2 * BYTES, 3 * BYTES) > 0 ||
+ Arrays.compareUnsigned(maxTriangle, maxYOffset, maxYOffset + BYTES, bbox, 0, BYTES) < 0;
+ }
+
+ /**
* encodes a bounding box into the provided byte array
*/
private static void encode(final int minX, final int maxX, final int minY, final int maxY, byte[] b) {
diff --git a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
index ef90c33..787a2a5 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/geo/TestRectangle2D.java
@@ -87,7 +87,13 @@ public class TestRectangle2D extends LuceneTestCase {
NumericUtils.intToSortableBytes(tMaxY, triangle, 2 * BYTES);
NumericUtils.intToSortableBytes(tMaxX, triangle, 3 * BYTES);
- PointValues.Relation r = rectangle2D.relateRangeBBox(BYTES, 0, triangle, 3 * BYTES, 2 * BYTES, triangle);
+ PointValues.Relation r;
+ if (random().nextBoolean()) {
+ r = rectangle2D.relateRangeBBox(BYTES, 0, triangle, 3 * BYTES, 2 * BYTES, triangle);
+ } else {
+ r = rectangle2D.intersectRangeBBox(BYTES, 0, triangle, 3 * BYTES, 2 * BYTES, triangle);
+ }
+
if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
assertFalse(rectangle2D.intersectsTriangle(ax, ay, bx, by , cx, cy));
assertFalse(rectangle2D.containsTriangle(ax, ay, bx, by , cx, cy));
@@ -97,4 +103,54 @@ public class TestRectangle2D extends LuceneTestCase {
}
}
}
+
+ public void testIntersectOptimization() {
+ byte[] minTriangle = box(0, 0, 10, 5);
+ byte[] maxTriangle = box(20, 10, 30, 15);
+
+ Rectangle2D rectangle2D = Rectangle2D.create(new Rectangle(-0.1, 30.1, -0.1, 15.1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+
+ rectangle2D = Rectangle2D.create(new Rectangle(-0.1, 30.1, -0.1, 10.1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+
+ rectangle2D = Rectangle2D.create(new Rectangle(-0.1, 30.1, 4.9, 15.1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+
+ rectangle2D = Rectangle2D.create(new Rectangle(-0.1, 20.1, -0.1, 15.1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+
+ rectangle2D = Rectangle2D.create(new Rectangle(9.9, 30.1, -0.1, 15.1));
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+
+ rectangle2D = Rectangle2D.create(new Rectangle(5, 25, 3, 13));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.intersectRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY,
+ rectangle2D.relateRangeBBox(BYTES, 0, minTriangle, 3 * BYTES, 2 * BYTES, maxTriangle));
+ }
+
+ private byte[] box(int minY, int minX, int maxY, int maxX) {
+ byte[] bytes = new byte[4 * BYTES];
+ NumericUtils.intToSortableBytes(GeoEncodingUtils.encodeLatitude(minY), bytes, 0); // min y
+ NumericUtils.intToSortableBytes(GeoEncodingUtils.encodeLongitude(minX), bytes, BYTES); // min x
+ NumericUtils.intToSortableBytes(GeoEncodingUtils.encodeLatitude(maxY), bytes, 2 * BYTES); // max y
+ NumericUtils.intToSortableBytes(GeoEncodingUtils.encodeLongitude(maxX), bytes, 3 * BYTES); // max x
+ return bytes;
+ }
}