You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ho...@apache.org on 2016/03/21 01:43:51 UTC
[29/50] lucene-solr:jira/SOLR-445: LUCENE-7105: Optimize
LatLonPoint.newDistanceQuery
LUCENE-7105: Optimize LatLonPoint.newDistanceQuery
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/870baafc
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/870baafc
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/870baafc
Branch: refs/heads/jira/SOLR-445
Commit: 870baafc82b0853349db55b7886a6f31b54a69d5
Parents: 3ba7456
Author: Robert Muir <rm...@apache.org>
Authored: Tue Mar 15 11:17:52 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Tue Mar 15 11:18:15 2016 -0400
----------------------------------------------------------------------
lucene/CHANGES.txt | 2 +
.../document/LatLonPointDistanceQuery.java | 88 ++++++++++++++++----
2 files changed, 75 insertions(+), 15 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/870baafc/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 59cd092..3b4f507 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -21,6 +21,8 @@ Optimizations
* LUCENE-7099: LatLonPoint's newDistanceQuery supports two-phase
iteration. (Robert Muir)
+* LUCENE-7105: Optimize LatLonPoint's newDistanceQuery. (Robert Muir)
+
* LUCENE-7097: IntroSorter now recurses to 2 * log_2(count) quicksort
stack depth before switching to heapsort (Adrien Grand, Mike McCandless)
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/870baafc/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 3f86f1e..e8c7c08 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java
@@ -41,7 +41,9 @@ import org.apache.lucene.spatial.util.GeoUtils;
import org.apache.lucene.util.BitSet;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.SparseFixedBitSet;
+import org.apache.lucene.util.StringHelper;
/**
* Distance query for {@link LatLonPoint}.
@@ -74,16 +76,41 @@ final class LatLonPointDistanceQuery extends Query {
@Override
public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
GeoRect box = GeoUtils.circleToBBox(longitude, latitude, radiusMeters);
- final GeoRect box1;
- final GeoRect box2;
+ // create bounding box(es) for the distance range
+ // these are pre-encoded with LatLonPoint's encoding
+ final byte minLat[] = new byte[Integer.BYTES];
+ final byte maxLat[] = new byte[Integer.BYTES];
+ final byte minLon[] = new byte[Integer.BYTES];
+ final byte maxLon[] = new byte[Integer.BYTES];
+ // second set of longitude ranges to check (for cross-dateline case)
+ final byte minLon2[] = new byte[Integer.BYTES];
+
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLatitude(box.minLat), minLat, 0);
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLatitude(box.maxLat), maxLat, 0);
// crosses dateline: split
if (box.crossesDateline()) {
- box1 = new GeoRect(-180.0, box.maxLon, box.minLat, box.maxLat);
- box2 = new GeoRect(box.minLon, 180.0, box.minLat, box.maxLat);
+ // box1
+ NumericUtils.intToSortableBytes(Integer.MIN_VALUE, minLon, 0);
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLongitude(box.maxLon), maxLon, 0);
+ // box2
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLongitude(box.minLon), minLon2, 0);
+ } else {
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLongitude(box.minLon), minLon, 0);
+ NumericUtils.intToSortableBytes(LatLonPoint.encodeLongitude(box.maxLon), maxLon, 0);
+ // disable box2
+ NumericUtils.intToSortableBytes(Integer.MAX_VALUE, minLon2, 0);
+ }
+
+ // compute a maximum partial haversin: unless our box is crazy, we can use this bound
+ // to reject edge cases faster in matches()
+ final double minPartialDistance;
+ if (box.maxLon - longitude < 90 && longitude - box.minLon < 90) {
+ minPartialDistance = Math.max(LatLonPointDistanceComparator.haversin1(latitude, longitude, latitude, box.maxLon),
+ LatLonPointDistanceComparator.haversin1(latitude, longitude, box.maxLat, longitude));
+ assert LatLonPointDistanceComparator.haversin2(minPartialDistance) >= radiusMeters;
} else {
- box1 = box;
- box2 = null;
+ minPartialDistance = Double.POSITIVE_INFINITY;
}
return new ConstantScoreWeight(this) {
@@ -128,6 +155,22 @@ final class LatLonPointDistanceQuery extends Query {
@Override
public void visit(int docID, byte[] packedValue) {
+ // we bounds check individual values, as subtrees may cross, but we are being sent the values anyway:
+ // this reduces the amount of docvalues fetches (improves approximation)
+
+ if (StringHelper.compare(Integer.BYTES, packedValue, 0, maxLat, 0) > 0 ||
+ StringHelper.compare(Integer.BYTES, packedValue, 0, minLat, 0) < 0) {
+ // latitude out of bounding box range
+ return;
+ }
+
+ if ((StringHelper.compare(Integer.BYTES, packedValue, Integer.BYTES, maxLon, 0) > 0 ||
+ StringHelper.compare(Integer.BYTES, packedValue, Integer.BYTES, minLon, 0) < 0)
+ && StringHelper.compare(Integer.BYTES, packedValue, Integer.BYTES, minLon2, 0) < 0) {
+ // longitude out of bounding box range
+ return;
+ }
+
result.add(docID);
}
@@ -137,18 +180,25 @@ final class LatLonPointDistanceQuery extends Query {
// 3. recurse naively.
@Override
public Relation compare(byte[] minPackedValue, byte[] maxPackedValue) {
- double latMin = LatLonPoint.decodeLatitude(minPackedValue, 0);
- double lonMin = LatLonPoint.decodeLongitude(minPackedValue, Integer.BYTES);
- double latMax = LatLonPoint.decodeLatitude(maxPackedValue, 0);
- double lonMax = LatLonPoint.decodeLongitude(maxPackedValue, Integer.BYTES);
-
- if (latMax < box1.minLat || latMin > box1.maxLat) {
+ if (StringHelper.compare(Integer.BYTES, minPackedValue, 0, maxLat, 0) > 0 ||
+ StringHelper.compare(Integer.BYTES, maxPackedValue, 0, minLat, 0) < 0) {
// latitude out of bounding box range
return Relation.CELL_OUTSIDE_QUERY;
- } else if ((lonMax < box1.minLon || lonMin > box1.maxLon) && (box2 == null || lonMax < box2.minLon)) {
+ }
+
+ if ((StringHelper.compare(Integer.BYTES, minPackedValue, Integer.BYTES, maxLon, 0) > 0 ||
+ StringHelper.compare(Integer.BYTES, maxPackedValue, Integer.BYTES, minLon, 0) < 0)
+ && StringHelper.compare(Integer.BYTES, maxPackedValue, Integer.BYTES, minLon2, 0) < 0) {
// longitude out of bounding box range
return Relation.CELL_OUTSIDE_QUERY;
- } else if (lonMax - longitude < 90 && longitude - lonMin < 90 &&
+ }
+
+ double latMin = LatLonPoint.decodeLatitude(minPackedValue, 0);
+ double lonMin = LatLonPoint.decodeLongitude(minPackedValue, Integer.BYTES);
+ double latMax = LatLonPoint.decodeLatitude(maxPackedValue, 0);
+ double lonMax = LatLonPoint.decodeLongitude(maxPackedValue, Integer.BYTES);
+
+ if (lonMax - longitude < 90 && longitude - lonMin < 90 &&
GeoDistanceUtils.haversin(latitude, longitude, latMin, lonMin) <= radiusMeters &&
GeoDistanceUtils.haversin(latitude, longitude, latMin, lonMax) <= radiusMeters &&
GeoDistanceUtils.haversin(latitude, longitude, latMax, lonMin) <= radiusMeters &&
@@ -183,7 +233,15 @@ final class LatLonPointDistanceQuery extends Query {
long encoded = docValues.valueAt(i);
double docLatitude = LatLonPoint.decodeLatitude((int)(encoded >> 32));
double docLongitude = LatLonPoint.decodeLongitude((int)(encoded & 0xFFFFFFFF));
- if (GeoDistanceUtils.haversin(latitude, longitude, docLatitude, docLongitude) <= radiusMeters) {
+
+ // first check the partial distance, if its more than that, it can't be <= radiusMeters
+ double h1 = LatLonPointDistanceComparator.haversin1(latitude, longitude, docLatitude, docLongitude);
+ if (h1 > minPartialDistance) {
+ continue;
+ }
+
+ // fully confirm with part 2:
+ if (LatLonPointDistanceComparator.haversin2(h1) <= radiusMeters) {
return true;
}
}