[SERVER-20843] $geoIntersects performs poorly on polygons with lots of coordinates Created: 09/Oct/15 Updated: 28/Dec/23 |
|
| Status: | Backlog |
| Project: | Core Server |
| Component/s: | Geo |
| Affects Version/s: | 3.0.6 |
| Fix Version/s: | None |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | Casoa Makaso | Assignee: | Backlog - Query Integration |
| Resolution: | Unresolved | Votes: | 6 |
| Labels: | qi-geo, query-44-grooming | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Attachments: |
|
|||||||||||||||||||
| Issue Links: |
|
|||||||||||||||||||
| Assigned Teams: |
Query Integration
|
|||||||||||||||||||
| Operating System: | ALL | |||||||||||||||||||
| Steps To Reproduce: |
Import the attached database and run the query:
Delete the last document (id=56179fa25495b1184924b03e) and rerun the query. You'll see a marginal speedup, by just removing this one document. |
|||||||||||||||||||
| Participants: | ||||||||||||||||||||
| Case: | (copied to CRM) | |||||||||||||||||||
| Description |
|
Test Environment: Windows 10 x64, MongoDB 3.0.6 I have a very small database with 9999 Polygons (their coordinate consists of just 5 Points). Querying the set with geointersects (using a geosphere index) is fast, until I add one more polygon (which covers all others and has a large coordinate set > 130000 points). I'll add the mongoexport of my database. Explain without the last "huge" polygon:
Explain with the 10000ths large polygon:
|
| Comments |
| Comment by Beth Morgan [ 16/Sep/20 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
+1 We are experiencing this performance bottle neck on production...would be great to have this patched/fixed.... Â | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Rafael Acevedo [ 31/May/17 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
In my case, large polygons mean the ones that >50k vertices. They represent roughly 10% of all polygons in the DB(400k total), some of them being MultiPolygons. A single point-in-polygon query is taking 100ms on average, with no additional queries being executed at the same time. When there are multiple queries running in parallel, the average execution time increases to ~600ms or so.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Siyuan Zhou [ 30/May/17 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
racevedoo, thanks for reporting the issue. Although we don't have any plan to fix this issue in near future, could you please share more details about the performance in your case (e.g. how large/complex the polygons are) and (perhaps) the dataset and queries to help us understand your issue better and prioritize this ticket accordingly? The output of find(...).explain("executionStats") would be helpful as well. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Rafael Acevedo [ 24/May/17 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
+1 I'm having similar issues while querying for point-in-polygon with ~40k large polygons running mongo 3.2.9. Any updates on this issue? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Casoa Makaso [ 09/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
siyuan.zhou thanks for the response. Maybe I didn't explain our needs correctly. I attached a screenshot of a very abstract model of our polygons in the database. (Each colored border represents a polygon). The blue star is the position of a user (Lat/Lng) who requests information about his current place. (Kinda a reverse geocoding approach). Because we have only parts of the countries covered with counties/cities, we need to have huge polygons for the countries (ofc the world isn't needed currently). I don't see how we could solve this precomputed? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Siyuan Zhou [ 09/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
casoo, if the hierarchy is always world -> country -> county -> in your case, I still think it's possible to precompute the hierarchy in advance by computing a given city $within which country / county. Another easier solution would be to cache the hierarchy result for cities in a separate collection and reuse it whenever it's possible. GeoNear is more expensive than point-in-polygon check as it computes the distance to a polygon. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Casoa Makaso [ 07/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Let me add that I also tried it with a geoNear query (which returns the same results in our case as geoIntersects) {geo: { $near: {$geometry: {type: "Point", coordinates: [ 10.5891, 49.77997 ]}, $maxDistance: 1}}} but I did not see any improvements. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Casoa Makaso [ 03/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
siyuan.zhou, thanks for your fast response. I see that the workaround you describe makes completly sense, if I want to know which POI's are in which county/country. But our main use case is a different one (see the above query): 1) We have polygons describing the world/countries/counties/cities etc. 2) A user e.g. is located in 37.7576948,-122.4726194 (San Francisco) 3) He then wants to know which areas intersect with his coordinates 4) Therefore the query is: Give me all polygons that intersect with 37.7576948,-122.4726194 5) The result would be: "World", "USA", "San Francisco County", "San Francisco City" There is no way I know to precompute this e.g. in a string field. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Siyuan Zhou [ 02/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
casoo, thanks for providing the details about your use case. Point-in-polygon check is very computationally expensive for complex polygons. SERVER-21120 tracks future work to improve the performance on complex polygons. The complex polygon given above is "the world" or a country, I suppose? As a workaround, it gives a better performance to query the point's country once and store the country in a string field. Subsequent queries on the string field and simpler polygons (county, POI) can be very fast. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Casoa Makaso [ 02/Feb/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hello anonymous.user, I see some improvements with 3.2.0 (final now), but they don't give us the expected boost while running our queries. The above mentioned query with the large polygon included still takes ~80ms on my powerful dev machines (compared to 1ms for the query without the large polygon). I tested the case, where I added exact the same large polygon twice and the execution time doubles to 160ms. ramon.fernandez, basically we have polygons describing the world. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Ramon Fernandez Marina [ 09/Jan/16 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
camak, is there any additional information about your use case you can provide that may help us improve the performance of geospatial queries? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Kelsey Schubert [ 11/Nov/15 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hi camak, I've run the queries and confirmed the increase in execution time when the large polygon is included in the collection on 3.0.6 and in the master branch. However, on our master branch we have made substantial improvements to our geospatial queries. On my machine, with the large polygon included, 3.0.6 executed the query in 680 ms and master executed in the same query in 78 ms. Our master branch is at 3.2.0-rc2. I would recommend that you test whether this new version fits your needs. Please let us know a bit more about your use cases and whether 3.2.0-rc2 works for you. Kind regards, | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Casoa Makaso [ 10/Oct/15 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Just another note: I have an 2dsphere index on the geo field. Even if I add the document with id=56179fa25495b1184924b03e (which has > 130000 coordinates) to an empty collection and run the same query, I get the same slow query returns. The above output stats of ""executionTimeMillis" : NumberInt(87)", may not seem slow. But on our production servers which are not as powerful as my development machine I have query times above 1000ms, which makes it kinda unusable. |