Return-Path: X-Original-To: apmail-lucene-commits-archive@www.apache.org Delivered-To: apmail-lucene-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id B793D19AD9 for ; Mon, 21 Mar 2016 00:43:27 +0000 (UTC) Received: (qmail 51695 invoked by uid 500); 21 Mar 2016 00:43:24 -0000 Mailing-List: contact commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@lucene.apache.org Delivered-To: mailing list commits@lucene.apache.org Received: (qmail 51053 invoked by uid 99); 21 Mar 2016 00:43:24 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 21 Mar 2016 00:43:24 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id F1D4EE00FF; Mon, 21 Mar 2016 00:43:23 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: hossman@apache.org To: commits@lucene.apache.org Date: Mon, 21 Mar 2016 00:43:42 -0000 Message-Id: In-Reply-To: <76f0c69bbd3442feb68bc131603ceb4c@git.apache.org> References: <76f0c69bbd3442feb68bc131603ceb4c@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [20/50] lucene-solr:jira/SOLR-445: LUCENE-7103: further optimize LatLonPoint.newDistanceSort LUCENE-7103: further optimize LatLonPoint.newDistanceSort Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/1660b563 Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/1660b563 Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/1660b563 Branch: refs/heads/jira/SOLR-445 Commit: 1660b5630aec516fb7365e8cb5c0a8a2bfd14d2f Parents: 0f949c8 Author: Robert Muir Authored: Mon Mar 14 16:25:31 2016 -0400 Committer: Robert Muir Committed: Mon Mar 14 16:25:31 2016 -0400 ---------------------------------------------------------------------- .../document/LatLonPointDistanceComparator.java | 41 ++++++++++++++++---- .../lucene/document/TestBigIntegerPoint.java | 4 +- .../lucene/document/TestInetAddressPoint.java | 4 +- .../apache/lucene/document/TestLatLonPoint.java | 2 +- .../document/TestLatLonPointDistanceQuery.java | 4 +- .../document/TestLatLonPointDistanceSort.java | 28 +++++++++++-- 6 files changed, 64 insertions(+), 19 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java index 86c9134..ef4c3f3 100644 --- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java +++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java @@ -26,9 +26,10 @@ import org.apache.lucene.index.SortedNumericDocValues; import org.apache.lucene.search.FieldComparator; import org.apache.lucene.search.LeafFieldComparator; import org.apache.lucene.search.Scorer; -import org.apache.lucene.spatial.util.GeoDistanceUtils; +import org.apache.lucene.spatial.util.GeoProjectionUtils; import org.apache.lucene.spatial.util.GeoRect; import org.apache.lucene.spatial.util.GeoUtils; +import org.apache.lucene.util.SloppyMath; /** * Compares documents by distance from an origin point @@ -96,7 +97,7 @@ class LatLonPointDistanceComparator extends FieldComparator implements L crossesDateLine = false; } else { assert Double.isFinite(bottom); - GeoRect box = GeoUtils.circleToBBox(longitude, latitude, bottom); + GeoRect box = GeoUtils.circleToBBox(longitude, latitude, haversin2(bottom)); // pre-encode our box to our integer encoding, so we don't have to decode // to double values for uncompetitive hits. This has some cost! int minLatEncoded = LatLonPoint.encodeLatitude(box.minLat); @@ -166,7 +167,7 @@ class LatLonPointDistanceComparator extends FieldComparator implements L if (outsideBox == false) { double docLatitude = LatLonPoint.decodeLatitude(latitudeBits); double docLongitude = LatLonPoint.decodeLongitude(longitudeBits); - minValue = Math.min(minValue, GeoDistanceUtils.haversin(latitude, longitude, docLatitude, docLongitude)); + minValue = Math.min(minValue, haversin1(latitude, longitude, docLatitude, docLongitude)); } } return Double.compare(bottom, minValue); @@ -174,7 +175,7 @@ class LatLonPointDistanceComparator extends FieldComparator implements L @Override public void copy(int slot, int doc) throws IOException { - values[slot] = distance(doc); + values[slot] = sortKey(doc); } @Override @@ -190,17 +191,17 @@ class LatLonPointDistanceComparator extends FieldComparator implements L @Override public Double value(int slot) { - return Double.valueOf(values[slot]); + return Double.valueOf(haversin2(values[slot])); } @Override public int compareTop(int doc) throws IOException { - return Double.compare(topValue, distance(doc)); + return Double.compare(topValue, haversin2(sortKey(doc))); } // TODO: optimize for single-valued case? // TODO: do all kinds of other optimizations! - double distance(int doc) { + double sortKey(int doc) { currentDocs.setDocument(doc); int numValues = currentDocs.count(); @@ -213,8 +214,32 @@ class LatLonPointDistanceComparator extends FieldComparator implements L long encoded = currentDocs.valueAt(i); double docLatitude = LatLonPoint.decodeLatitude((int)(encoded >> 32)); double docLongitude = LatLonPoint.decodeLongitude((int)(encoded & 0xFFFFFFFF)); - minValue = Math.min(minValue, GeoDistanceUtils.haversin(latitude, longitude, docLatitude, docLongitude)); + minValue = Math.min(minValue, haversin1(latitude, longitude, docLatitude, docLongitude)); } return minValue; } + + // sort by first part of the haversin computation. note that this value is meaningless to the user. + // invoke haversin2() to "complete" the calculation and get a distance in meters. + static double haversin1(double lat1, double lon1, double lat2, double lon2) { + double dLat = SloppyMath.TO_RADIANS * (lat2 - lat1); + double dLon = SloppyMath.TO_RADIANS * (lon2 - lon1); + lat1 = SloppyMath.TO_RADIANS * (lat1); + lat2 = SloppyMath.TO_RADIANS * (lat2); + + final double sinDLatO2 = SloppyMath.sin(dLat / 2); + final double sinDLonO2 = SloppyMath.sin(dLon / 2); + + return sinDLatO2*sinDLatO2 + sinDLonO2 * sinDLonO2 * SloppyMath.cos(lat1) * SloppyMath.cos(lat2); + } + + // second half of the haversin calculation, used to convert results from haversin1 (used internally + // for sorting) for display purposes. + static double haversin2(double partial) { + if (Double.isInfinite(partial)) { + return partial; + } + double c = 2 * SloppyMath.asin(Math.sqrt(partial)); + return (GeoProjectionUtils.SEMIMAJOR_AXIS * c); + } } http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java index 8f38bcd..a7a1295 100644 --- a/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java +++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java @@ -41,7 +41,7 @@ public class TestBigIntegerPoint extends LuceneTestCase { // search and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(BigIntegerPoint.newExactQuery("field", large))); assertEquals(1, searcher.count(BigIntegerPoint.newRangeQuery("field", large.subtract(BigInteger.ONE), large.add(BigInteger.ONE)))); assertEquals(1, searcher.count(BigIntegerPoint.newSetQuery("field", large))); @@ -66,7 +66,7 @@ public class TestBigIntegerPoint extends LuceneTestCase { // search and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(BigIntegerPoint.newExactQuery("field", negative))); assertEquals(1, searcher.count(BigIntegerPoint.newRangeQuery("field", negative.subtract(BigInteger.ONE), negative.add(BigInteger.ONE)))); http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java index c91b52b..b0e7107 100644 --- a/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java +++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java @@ -41,7 +41,7 @@ public class TestInetAddressPoint extends LuceneTestCase { // search and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(InetAddressPoint.newExactQuery("field", address))); assertEquals(1, searcher.count(InetAddressPoint.newPrefixQuery("field", address, 24))); assertEquals(1, searcher.count(InetAddressPoint.newRangeQuery("field", InetAddress.getByName("1.2.3.3"), InetAddress.getByName("1.2.3.5")))); @@ -68,7 +68,7 @@ public class TestInetAddressPoint extends LuceneTestCase { // search and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(InetAddressPoint.newExactQuery("field", address))); assertEquals(1, searcher.count(InetAddressPoint.newPrefixQuery("field", address, 64))); assertEquals(1, searcher.count(InetAddressPoint.newRangeQuery("field", InetAddress.getByName("fec0::f66c"), InetAddress.getByName("fec0::f66e")))); http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java index d180d58..ff4af12 100644 --- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java +++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java @@ -39,7 +39,7 @@ public class TestLatLonPoint extends LuceneTestCase { // search and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(LatLonPoint.newBoxQuery("field", 18, 19, -66, -65))); reader.close(); http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java index fa95710..c69791c 100644 --- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java +++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java @@ -55,7 +55,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase { // search within 50km and verify we found our doc IndexReader reader = writer.getReader(); - IndexSearcher searcher = newSearcher(reader, false); + IndexSearcher searcher = newSearcher(reader); assertEquals(1, searcher.count(LatLonPoint.newDistanceQuery("field", 18, -65, 50_000))); reader.close(); @@ -148,7 +148,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase { writer.addDocument(doc); } IndexReader reader = writer.getReader(); - IndexSearcher searcher = new IndexSearcher(reader); + IndexSearcher searcher = newSearcher(reader); for (int i = 0; i < numQueries; i++) { double lat = -90 + 180.0 * random().nextDouble(); http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1660b563/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java ---------------------------------------------------------------------- diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java index a776b3f..7df956f 100644 --- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java +++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java @@ -54,7 +54,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase { iw.addDocument(doc); IndexReader reader = iw.getReader(); - IndexSearcher searcher = new IndexSearcher(reader); + IndexSearcher searcher = newSearcher(reader); iw.close(); Sort sort = new Sort(LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731)); @@ -91,7 +91,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase { iw.addDocument(doc); IndexReader reader = iw.getReader(); - IndexSearcher searcher = new IndexSearcher(reader); + IndexSearcher searcher = newSearcher(reader); iw.close(); Sort sort = new Sort(LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731)); @@ -128,7 +128,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase { iw.addDocument(doc); IndexReader reader = iw.getReader(); - IndexSearcher searcher = new IndexSearcher(reader); + IndexSearcher searcher = newSearcher(reader); iw.close(); SortField sortField = LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731); @@ -234,7 +234,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase { writer.addDocument(doc); } IndexReader reader = writer.getReader(); - IndexSearcher searcher = new IndexSearcher(reader); + IndexSearcher searcher = newSearcher(reader); for (int i = 0; i < numQueries; i++) { double lat = -90 + 180.0 * random().nextDouble(); @@ -289,4 +289,24 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase { writer.close(); dir.close(); } + + /** Test this method sorts the same way as real haversin */ + public void testPartialHaversin() { + for (int i = 0; i < 100000; i++) { + double centerLat = -90 + 180.0 * random().nextDouble(); + double centerLon = -180 + 360.0 * random().nextDouble(); + + double lat1 = -90 + 180.0 * random().nextDouble(); + double lon1 = -180 + 360.0 * random().nextDouble(); + + double lat2 = -90 + 180.0 * random().nextDouble(); + double lon2 = -180 + 360.0 * random().nextDouble(); + + int expected = Integer.signum(Double.compare(GeoDistanceUtils.haversin(centerLat, centerLon, lat1, lon1), + GeoDistanceUtils.haversin(centerLat, centerLon, lat2, lon2))); + int actual = Integer.signum(Double.compare(LatLonPointDistanceComparator.haversin1(centerLat, centerLon, lat1, lon1), + LatLonPointDistanceComparator.haversin1(centerLat, centerLon, lat2, lon2))); + assertEquals(expected, actual); + } + } }