You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2017/01/30 10:20:49 UTC
[4/6] lucene-solr:branch_6x: LUCENE-7661: Speed up for
LatLonPointInPolygonQuery by pre-computing the relation of the polygon with a
grid.
LUCENE-7661: Speed up for LatLonPointInPolygonQuery by pre-computing the relation of the polygon with a grid.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/d2051e3f
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/d2051e3f
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/d2051e3f
Branch: refs/heads/branch_6x
Commit: d2051e3f9d4edeb5d6c74f71684c14596453b4a2
Parents: 9e98100
Author: Adrien Grand <jp...@gmail.com>
Authored: Mon Jan 30 09:44:48 2017 +0100
Committer: Adrien Grand <jp...@gmail.com>
Committed: Mon Jan 30 11:16:31 2017 +0100
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/geo/GeoEncodingUtils.java | 145 +++++++++++++++----
.../document/LatLonDocValuesDistanceQuery.java | 2 +-
.../document/LatLonPointDistanceQuery.java | 2 +-
.../document/LatLonPointInPolygonQuery.java | 6 +-
5 files changed, 128 insertions(+), 30 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d2051e3f/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index cd77115..1bc5046 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -70,6 +70,9 @@ Optimizations
* LUCENE-7656: Speed up for LatLonPointDistanceQuery by computing distances even
less often. (Adrien Grand)
+* LUCENE-7661: Speed up for LatLonPointInPolygonQuery by pre-computing the
+ relation of the polygon with a grid. (Adrien Grand)
+
Build
* LUCENE-7651: Fix Javadocs build for Java 8u121 by injecting "Google Code
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d2051e3f/lucene/core/src/java/org/apache/lucene/geo/GeoEncodingUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoEncodingUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoEncodingUtils.java
index cc75fbf..663cb2e 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoEncodingUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoEncodingUtils.java
@@ -27,6 +27,8 @@ import static org.apache.lucene.geo.GeoUtils.MIN_LAT_INCL;
import static org.apache.lucene.geo.GeoUtils.checkLatitude;
import static org.apache.lucene.geo.GeoUtils.checkLongitude;
+import java.util.function.Function;
+
/**
* reusable geopoint encoding methods
*
@@ -158,11 +160,48 @@ public final class GeoEncodingUtils {
* @lucene.internal */
public static DistancePredicate createDistancePredicate(double lat, double lon, double radiusMeters) {
final Rectangle boundingBox = Rectangle.fromPointDistance(lat, lon, radiusMeters);
+ final double axisLat = Rectangle.axisLat(lat, radiusMeters);
+ final double distanceSortKey = GeoUtils.distanceQuerySortKey(radiusMeters);
+ final Function<Rectangle, Relation> boxToRelation = box -> GeoUtils.relate(
+ box.minLat, box.maxLat, box.minLon, box.maxLon, lat, lon, distanceSortKey, axisLat);
+ final Grid subBoxes = createSubBoxes(boundingBox, boxToRelation);
+
+ return new DistancePredicate(
+ subBoxes.latShift, subBoxes.lonShift,
+ subBoxes.latBase, subBoxes.lonBase,
+ subBoxes.maxLatDelta, subBoxes.maxLonDelta,
+ subBoxes.relations,
+ lat, lon, distanceSortKey);
+ }
+
+ /** Create a predicate that checks whether points are within a polygon.
+ * It works the same way as {@link #createDistancePredicate}.
+ * @lucene.internal */
+ public static PolygonPredicate createPolygonPredicate(Polygon[] polygons, Polygon2D tree) {
+ final Rectangle boundingBox = Rectangle.fromPolygon(polygons);
+ final Function<Rectangle, Relation> boxToRelation = box -> tree.relate(
+ box.minLat, box.maxLat, box.minLon, box.maxLon);
+ final Grid subBoxes = createSubBoxes(boundingBox, boxToRelation);
+
+ return new PolygonPredicate(
+ subBoxes.latShift, subBoxes.lonShift,
+ subBoxes.latBase, subBoxes.lonBase,
+ subBoxes.maxLatDelta, subBoxes.maxLonDelta,
+ subBoxes.relations,
+ tree);
+ }
+
+ private static Grid createSubBoxes(Rectangle boundingBox, Function<Rectangle, Relation> boxToRelation) {
final int minLat = encodeLatitudeCeil(boundingBox.minLat);
final int maxLat = encodeLatitude(boundingBox.maxLat);
final int minLon = encodeLongitudeCeil(boundingBox.minLon);
final int maxLon = encodeLongitude(boundingBox.maxLon);
+ if (maxLat < minLat || (boundingBox.crossesDateline() == false && maxLon < minLon)) {
+ // the box cannot match any quantized point
+ return new Grid(1, 1, 0, 0, 0, 0, new byte[0]);
+ }
+
final int latShift, lonShift;
final int latBase, lonBase;
final int maxLatDelta, maxLonDelta;
@@ -186,8 +225,6 @@ public final class GeoEncodingUtils {
assert maxLonDelta > 0;
}
- final double axisLat = Rectangle.axisLat(lat, radiusMeters);
- final double distanceSortKey = GeoUtils.distanceQuerySortKey(radiusMeters);
final byte[] relations = new byte[maxLatDelta * maxLonDelta];
for (int i = 0; i < maxLatDelta; ++i) {
for (int j = 0; j < maxLonDelta; ++j) {
@@ -196,55 +233,54 @@ public final class GeoEncodingUtils {
final int boxMaxLat = boxMinLat + (1 << latShift) - 1;
final int boxMaxLon = boxMinLon + (1 << lonShift) - 1;
- relations[i * maxLonDelta + j] = (byte) GeoUtils.relate(
+ relations[i * maxLonDelta + j] = (byte) boxToRelation.apply(new Rectangle(
decodeLatitude(boxMinLat), decodeLatitude(boxMaxLat),
- decodeLongitude(boxMinLon), decodeLongitude(boxMaxLon),
- lat, lon, distanceSortKey, axisLat).ordinal();
+ decodeLongitude(boxMinLon), decodeLongitude(boxMaxLon))).ordinal();
}
}
- return new DistancePredicate(
+ return new Grid(
latShift, lonShift,
latBase, lonBase,
maxLatDelta, maxLonDelta,
- relations,
- lat, lon, distanceSortKey);
+ relations);
}
/** Compute the minimum shift value so that
* {@code (b>>>shift)-(a>>>shift)} is less that {@code ARITY}. */
private static int computeShift(long a, long b) {
- assert a < b;
+ assert a <= b;
// We enforce a shift of at least 1 so that when we work with unsigned ints
// by doing (lat - MIN_VALUE), the result of the shift (lat - MIN_VALUE) >>> shift
// can be used for comparisons without particular care: the sign bit has
// been cleared so comparisons work the same for signed and unsigned ints
for (int shift = 1; ; ++shift) {
final long delta = (b >>> shift) - (a >>> shift);
- if (delta >= 0 && delta < DistancePredicate.ARITY) {
+ if (delta >= 0 && delta < Grid.ARITY) {
return shift;
}
}
}
- /** A predicate that checks whether a given point is within a distance of another point. */
- public static class DistancePredicate {
-
- private static final int ARITY = 64;
+ private static class Grid {
+ static final int ARITY = 64;
- private final int latShift, lonShift;
- private final int latBase, lonBase;
- private final int maxLatDelta, maxLonDelta;
- private final byte[] relations;
- private final double lat, lon;
- private final double distanceKey;
+ final int latShift, lonShift;
+ final int latBase, lonBase;
+ final int maxLatDelta, maxLonDelta;
+ final byte[] relations;
- private DistancePredicate(
+ private Grid(
int latShift, int lonShift,
int latBase, int lonBase,
int maxLatDelta, int maxLonDelta,
- byte[] relations,
- double lat, double lon, double distanceKey) {
+ byte[] relations) {
+ if (latShift < 1 || latShift > 31) {
+ throw new IllegalArgumentException();
+ }
+ if (lonShift < 1 || lonShift > 31) {
+ throw new IllegalArgumentException();
+ }
this.latShift = latShift;
this.lonShift = lonShift;
this.latBase = latBase;
@@ -252,6 +288,22 @@ public final class GeoEncodingUtils {
this.maxLatDelta = maxLatDelta;
this.maxLonDelta = maxLonDelta;
this.relations = relations;
+ }
+ }
+
+ /** A predicate that checks whether a given point is within a distance of another point. */
+ public static class DistancePredicate extends Grid {
+
+ private final double lat, lon;
+ private final double distanceKey;
+
+ private DistancePredicate(
+ int latShift, int lonShift,
+ int latBase, int lonBase,
+ int maxLatDelta, int maxLonDelta,
+ byte[] relations,
+ double lat, double lon, double distanceKey) {
+ super(latShift, lonShift, latBase, lonBase, maxLatDelta, maxLonDelta, relations);
this.lat = lat;
this.lon = lon;
this.distanceKey = distanceKey;
@@ -259,16 +311,17 @@ public final class GeoEncodingUtils {
/** Check whether the given point is within a distance of another point.
* NOTE: this operates directly on the encoded representation of points. */
- public boolean apply(int lat, int lon) {
+ public boolean test(int lat, int lon) {
final int lat2 = ((lat - Integer.MIN_VALUE) >>> latShift);
if (lat2 < latBase || lat2 >= latBase + maxLatDelta) {
return false;
}
int lon2 = ((lon - Integer.MIN_VALUE) >>> lonShift);
if (lon2 < lonBase) { // wrap
- lon2 += 1L << (32 - lonShift);
- assert lon2 >= lonBase;
+ lon2 += 1 << (32 - lonShift);
}
+ assert Integer.toUnsignedLong(lon2) >= lonBase;
+ assert lon2 - lonBase >= 0;
if (lon2 - lonBase >= maxLonDelta) {
return false;
}
@@ -284,4 +337,44 @@ public final class GeoEncodingUtils {
}
}
+ /** A predicate that checks whether a given point is within a polygon. */
+ public static class PolygonPredicate extends Grid {
+
+ private final Polygon2D tree;
+
+ private PolygonPredicate(
+ int latShift, int lonShift,
+ int latBase, int lonBase,
+ int maxLatDelta, int maxLonDelta,
+ byte[] relations,
+ Polygon2D tree) {
+ super(latShift, lonShift, latBase, lonBase, maxLatDelta, maxLonDelta, relations);
+ this.tree = tree;
+ }
+
+ /** Check whether the given point is within the considered polygon.
+ * NOTE: this operates directly on the encoded representation of points. */
+ public boolean test(int lat, int lon) {
+ final int lat2 = ((lat - Integer.MIN_VALUE) >>> latShift);
+ if (lat2 < latBase || lat2 >= latBase + maxLatDelta) {
+ return false;
+ }
+ int lon2 = ((lon - Integer.MIN_VALUE) >>> lonShift);
+ if (lon2 < lonBase) { // wrap
+ lon2 += 1 << (32 - lonShift);
+ }
+ assert Integer.toUnsignedLong(lon2) >= lonBase;
+ assert lon2 - lonBase >= 0;
+ if (lon2 - lonBase >= maxLonDelta) {
+ return false;
+ }
+
+ final int relation = relations[(lat2 - latBase) * maxLonDelta + (lon2 - lonBase)];
+ if (relation == Relation.CELL_CROSSES_QUERY.ordinal()) {
+ return tree.contains(decodeLatitude(lat), decodeLongitude(lon));
+ } else {
+ return relation == Relation.CELL_INSIDE_QUERY.ordinal();
+ }
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d2051e3f/lucene/sandbox/src/java/org/apache/lucene/document/LatLonDocValuesDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonDocValuesDistanceQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonDocValuesDistanceQuery.java
index 6febedc..df40eef 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonDocValuesDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonDocValuesDistanceQuery.java
@@ -113,7 +113,7 @@ final class LatLonDocValuesDistanceQuery extends Query {
final long value = values.valueAt(i);
final int lat = (int) (value >>> 32);
final int lon = (int) (value & 0xFFFFFFFF);
- if (distancePredicate.apply(lat, lon)) {
+ if (distancePredicate.test(lat, lon)) {
return true;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d2051e3f/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
index 421858d..6028086 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -164,7 +164,7 @@ final class LatLonPointDistanceQuery extends Query {
int docLatitude = NumericUtils.sortableBytesToInt(packedValue, 0);
int docLongitude = NumericUtils.sortableBytesToInt(packedValue, Integer.BYTES);
- if (distancePredicate.apply(docLatitude, docLongitude)) {
+ if (distancePredicate.test(docLatitude, docLongitude)) {
adder.add(docID);
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d2051e3f/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
index 8db8296..4609d35 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointInPolygonQuery.java
@@ -35,6 +35,7 @@ import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.StringHelper;
+import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.geo.Polygon2D;
@@ -92,6 +93,7 @@ final class LatLonPointInPolygonQuery extends Query {
NumericUtils.intToSortableBytes(encodeLongitude(box.maxLon), maxLon, 0);
final Polygon2D tree = Polygon2D.create(polygons);
+ final GeoEncodingUtils.PolygonPredicate polygonPredicate = GeoEncodingUtils.createPolygonPredicate(polygons, tree);
return new ConstantScoreWeight(this) {
@@ -130,8 +132,8 @@ final class LatLonPointInPolygonQuery extends Query {
@Override
public void visit(int docID, byte[] packedValue) {
- if (tree.contains(decodeLatitude(packedValue, 0),
- decodeLongitude(packedValue, Integer.BYTES))) {
+ if (polygonPredicate.test(NumericUtils.sortableBytesToInt(packedValue, 0),
+ NumericUtils.sortableBytesToInt(packedValue, Integer.BYTES))) {
adder.add(docID);
}
}