diff options
author | filipe oliveira <filipecosta.90@gmail.com> | 2022-11-24 16:09:56 +0000 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-11-24 18:09:56 +0200 |
commit | ae1de549006c1f15bade4969ba25932e3509f17a (patch) | |
tree | 7cb462149690e95efe363011f975c46d79698105 | |
parent | ca174e1d47a6bd9ae12868e0c577d98c177dee74 (diff) | |
download | redis-ae1de549006c1f15bade4969ba25932e3509f17a.tar.gz |
GEOSEARCH BYBOX: Reduce wastefull computation on geohashGetDistanceIfInRectangle and geohashGetDistance (#11535)
Optimize geohashGetDistanceIfInRectangle when there are many misses.
It calls 3x geohashGetDistance. The first 2 times we call them to produce intermediate results.
This PR focus on optimizing for those 2 intermediate results.
1 Reduce expensive computation on intermediate geohashGetDistance with same long
2 Avoid expensive lon_distance calculation if lat_distance fails beforehand
Co-authored-by: Oran Agra <oran@redislabs.com>
-rw-r--r-- | src/geohash_helper.c | 17 |
1 files changed, 13 insertions, 4 deletions
diff --git a/src/geohash_helper.c b/src/geohash_helper.c index a9224a1dd..a089c97c2 100644 --- a/src/geohash_helper.c +++ b/src/geohash_helper.c @@ -225,8 +225,12 @@ double geohashGetDistance(double lon1d, double lat1d, double lon2d, double lat2d lon2r = deg_rad(lon2d); u = sin((lat2r - lat1r) / 2); v = sin((lon2r - lon1r) / 2); - return 2.0 * EARTH_RADIUS_IN_METERS * - asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v)); + double a = u * u; + /* if v == 0 we can avoid doing expensive math */ + if (v != 0.0){ + a += cos(lat1r) * cos(lat2r) * v * v; + } + return 2.0 * EARTH_RADIUS_IN_METERS * asin(sqrt(a)); } int geohashGetDistanceIfInRadius(double x1, double y1, @@ -253,9 +257,14 @@ int geohashGetDistanceIfInRadiusWGS84(double x1, double y1, double x2, */ int geohashGetDistanceIfInRectangle(double width_m, double height_m, double x1, double y1, double x2, double y2, double *distance) { - double lon_distance = geohashGetDistance(x2, y2, x1, y2); + /* latitude distance is less expensive to compute than longitude distance + * so we check first for the latitude condition */ double lat_distance = geohashGetDistance(x2, y2, x2, y1); - if (lon_distance > width_m/2 || lat_distance > height_m/2) { + if (lat_distance > height_m/2) { + return 0; + } + double lon_distance = geohashGetDistance(x2, y2, x1, y2); + if (lon_distance > width_m/2) { return 0; } *distance = geohashGetDistance(x1, y1, x2, y2); |