Fix geo search bounding box check causing missing results by qetu3790 · Pull Request #10018 · redis/redis

qetu3790 · 2021-12-28T08:02:01Z

Consider the following example:

geoadd k1 -0.15307903289794921875 85 n1 0.3515625 85.00019260486917005437 n2.
geodist k1 n1 n2 returns "4891.9380"
but GEORADIUSBYMEMBER k1 n1 4891.94 m only returns n1.
n2 is in the boundingbox but out of search areas.So we let search areas contain boundingbox to get n2.

Consider the following example: 1. geoadd k1 -0.15307903289794921875 85 n1 0.3515625 85.00019260486917005437 n2. 2. geodist k1 n1 n2 returns "4891.9380" 3. but GEORADIUSBYMEMBER k1 n1 4891.94 m only returns n1. n2 is in the boundingbox but out of search areas.So we let search areas contain boundingbox to get n2.

yangbodong22011 · 2021-12-28T12:49:42Z

Hi, @qetu3790 I think the current result is within the normal error range (Currently I cannot calculate the distance error of Redis GEO, and the document does not mention it).

127.0.0.1:6379> GEORADIUSBYMEMBER k1 n1 4891.96 m
1) "n1"
2) "n2"
127.0.0.1:6379>

qetu3790 · 2021-12-29T01:49:24Z

The larger the search radius, the greater the error. See the other two examples:

127.0.0.1:6379>` geoadd k1 -4.95211958885192871094 85 n1 11.25 85.0511 n2
(integer) 0
127.0.0.1:6379> geodist k1 n1 n2
"155848.3353"
127.0.0.1:6379> GEORADIUSBYMEMBER k1 n1 156544 m
"n1"

127.0.0.1:6379> geoadd k1 -45 65.50900022111811438208 n1 90 85.0511 n2
(integer) 0
127.0.0.1:6379> geodist k1 n1 n2
"3136004.8437"
127.0.0.1:6379> GEORADIUSBYMEMBER k1 n1 5009431 m
"n1"

By the way, I wonder if the geo commands are designed to be used only for small search radius. And what are the boundaries?

oranagra · 2021-12-30T16:23:50Z

@yangbodong22011 isn't this because of the bent trapezoid issue we realized in #8094?
in which case, isn't the proposed fix correct?

oranagra · 2021-12-30T16:27:15Z

actually, it was here: #8445

qetu3790 · 2021-12-31T04:49:00Z

In most cases, the fix cat let search areas contain boundingbox. Although sometims it can't(see the following example), we can also prove the search areas contain all points within the search radius.

The example:

GEOADD k1 -1 65.9 n2

GEORADIUSBYMEMBER k1 n2 1252357.8 m

In this example, the east edge of search areas is also smaller than the ease edge of boundingbox when we have modifed the code.

We don't want to decrease more steps, because this can let us compare more points. It's enough as long as search areas contain all points within the search radius.

The fix can also solve another problem: crossing pole problem.

The crossing pole problem example:

127.0.0.1:6379> geoadd k1 45 65 n1 -135 85.05 n2
(integer) 0
127.0.0.1:6379> geodist k1 n1 n2
"3331227.6970"
127.0.0.1:6379> GEORADIUSBYMEMBER k1 n1 5009431 m
"n1"

yangbodong22011 · 2021-12-31T07:17:23Z

@qetu3790
Redis uses GEOHASH, the higher the latitude, the greater the error. The maximum latitude range specified in Redis is

/* Limits from EPSG:900913 / EPSG:3785 / OSGEO:41001 */
#define GEO_LAT_MIN -85.05112878
#define GEO_LAT_MAX 85.05112878
#define GEO_LONG_MIN -180
#define GEO_LONG_MAX 180

Going back to the question, in the case you constructed, it is true that the steps cannot be reduced due to errors (but note that reducing the steps will mean that we search for more elements in the Zset, resulting in lower efficiency). This is also my opinion Your PR concerns.

yangbodong22011 · 2021-12-31T07:23:48Z

@yangbodong22011 isn't this because of the bent trapezoid issue we realized in #8094? in which case, isn't the proposed fix correct?

no, trapezoid is only used to exclude the search areas that are useless.

yangbodong22011 · 2021-12-31T07:26:17Z

@qetu3790 Merging this PR will solve the case you mentioned earlier, but the impact is that when users search for high latitude points (like your test case), you may need to traverse more elements in Zset, right?

If I understand correctly, I think I can accept this PR. @qetu3790

qetu3790 · 2021-12-31T10:22:43Z

Yes. In order to get right results, we have to do so. And I've tried not to decrease steps too much. @yangbodong22011

src/geohash_helper.c

Co-authored-by: Binbin <[email protected]>

qetu3790 · 2022-01-02T09:03:22Z

@qetu3790 Redis uses GEOHASH, the higher the latitude, the greater the error. The maximum latitude range specified in Redis is
/* Limits from EPSG:900913 / EPSG:3785 / OSGEO:41001 */
#define GEO_LAT_MIN -85.05112878
#define GEO_LAT_MAX 85.05112878
#define GEO_LONG_MIN -180
#define GEO_LONG_MAX 180
Going back to the question, in the case you constructed, it is true that the steps cannot be reduced due to errors (but note that reducing the steps will mean that we search for more elements in the Zset, resulting in lower efficiency). This is also my opinion Your PR concerns.

When the latitude is not too high, we still have a large error. Example:

127.0.0.1:6379> geoadd k1 -45 65.50900022111811438208 n1 90 70 n2
(integer) 0
127.0.0.1:6379> geodist k1 n1 n2
"4558542.3356"
127.0.0.1:6379> GEORADIUSBYMEMBER k1 n1 5009431 m
"n1"

src/geohash_helper.c

yangbodong22011 · 2022-01-03T03:17:37Z

@qetu3790 Can you add several tests you provide to `tests/unit/geo.tcl' ?

geoadd k1 -0.15307903289794921875 85 n1 0.3515625 85.00019260486917005437 n2.
geoadd k1 -4.95211958885192871094 85 n1 11.25 85.0511 n2
geoadd k1 -45 65.50900022111811438208 n1 90 85.0511 n2

yangbodong22011 · 2022-01-05T01:47:45Z

@qetu3790 Merging this PR will solve the case you mentioned earlier, but the impact is that when users search for high latitude points (like your test case), you may need to traverse more elements in Zset, right?

If I understand correctly, I think I can accept this PR. @qetu3790

@oranagra please have a look when you have time, merging this PR will make some case search results more accurate. The impact is that these cases will search for more elements in Zset, "correctness is greater than efficiency", so I agree with this PR merger.

oranagra

@yangbodong22011 isn't this because of the bent trapezoid issue we realized in #8445? in which case, isn't the proposed fix correct?

no, trapezoid is only used to exclude the search areas that are useless.

This is exactly the trapezoid problem.
the old code used to compare the "horizontal" and "vertical" distance from the point (longitude,latitude), to the lon min/max and lat min/max of north, south, east, and west.

i.e. the horizontal distance was computed only at the center of that box.
from longitude,latitude to east.longitude.max,latitude and to west.longitude.min,latitude.
along a single latitude (the center).

the new code uses the min/max values computed by geohashBoundingBox which has this diagram:

 *    \-----------------/          --------               \-----------------/
 *     \               /         /          \              \               /
 *      \  (long,lat) /         / (long,lat) \              \  (long,lat) /
 *       \           /         /              \             /             \
 *         ---------          /----------------\           /---------------\
 *  Northern Hemisphere       Southern Hemisphere         Around the equator

clearly the central latitude is wrong to use.
instead geohashBoundingBox uses the top / bottom latitudes.

yangbodong22011 · 2022-02-21T06:50:33Z

@oranagra Yes, agree and thank you for your explanation.

Consider the following example: 1. geoadd k1 -0.15307903289794921875 85 n1 0.3515625 85.00019260486917005437 n2. 2. geodist k1 n1 n2 returns "4891.9380" 3. but GEORADIUSBYMEMBER k1 n1 4891.94 m only returns n1. n2 is in the boundingbox but out of search areas.So we let search areas contain boundingbox to get n2. Co-authored-by: Binbin <[email protected]> (cherry picked from commit b2d393b)

qetu3790 changed the title ~~Let search areas contain boundingbox.~~ [GEO]Let search areas contain boundingbox. Dec 28, 2021

oranagra requested a review from yangbodong22011 December 28, 2021 10:25

enjoy-binbin reviewed Jan 1, 2022

View reviewed changes

src/geohash_helper.c Outdated Show resolved Hide resolved

Update src/geohash_helper.c

a2ee92a

Co-authored-by: Binbin <[email protected]>

yangbodong22011 reviewed Jan 3, 2022

View reviewed changes

src/geohash_helper.c Outdated Show resolved Hide resolved

qetu3790 added 3 commits January 4, 2022 21:26

Update geo.tcl

5213242

Update geo.tcl

16db260

Update geo.tcl

2f76133

yangbodong22011 approved these changes Jan 5, 2022

View reviewed changes

zuiderkwast added the state:to-be-merged The PR should be merged soon, even if not yet ready, this is used so that it won't be forgotten label Jan 14, 2022

oranagra approved these changes Feb 20, 2022

View reviewed changes

minor white space cleanup

b6bfec7

oranagra added the release-notes indication that this issue needs to be mentioned in the release notes label Feb 20, 2022

oranagra changed the title ~~[GEO]Let search areas contain boundingbox.~~ Fix geo search bounding box check causing missing results Feb 21, 2022

oranagra merged commit b2d393b into redis:unstable Feb 21, 2022

oranagra mentioned this pull request Feb 28, 2022

Release 7.0 RC2 #10355

Merged

This was referenced Apr 27, 2022

Redis 6.2.7 #10653

Closed

Redis 6.2.7 #10654

Merged

Conversation

qetu3790 commented Dec 28, 2021

Uh oh!

yangbodong22011 commented Dec 28, 2021

Uh oh!

qetu3790 commented Dec 29, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oranagra commented Dec 30, 2021

Uh oh!

oranagra commented Dec 30, 2021

Uh oh!

qetu3790 commented Dec 31, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

yangbodong22011 commented Dec 31, 2021

Uh oh!

yangbodong22011 commented Dec 31, 2021

Uh oh!

yangbodong22011 commented Dec 31, 2021

Uh oh!

qetu3790 commented Dec 31, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

qetu3790 commented Jan 2, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

yangbodong22011 commented Jan 3, 2022

Uh oh!

yangbodong22011 commented Jan 5, 2022

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

yangbodong22011 commented Feb 21, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

qetu3790 commented Dec 29, 2021 •

edited

Loading

qetu3790 commented Dec 31, 2021 •

edited

Loading

qetu3790 commented Dec 31, 2021 •

edited

Loading

qetu3790 commented Jan 2, 2022 •

edited

Loading