Skip to content

geo/geomfn: add point in polygon optimization to st_intersects#62193

Merged
craig[bot] merged 1 commit intocockroachdb:masterfrom
andyyang890:optimize_st_intersects
Mar 23, 2021
Merged

geo/geomfn: add point in polygon optimization to st_intersects#62193
craig[bot] merged 1 commit intocockroachdb:masterfrom
andyyang890:optimize_st_intersects

Conversation

@andyyang890
Copy link
Copy Markdown
Collaborator

@andyyang890 andyyang890 commented Mar 18, 2021 •
edited
Loading

This patch improves the performance of st_intersects for the
common use case of testing whether a (multi)polygon and a
(multi)point intersect.

Release note: None

@andyyang890 andyyang890 requested a review from otan March 18, 2021 04:27
@cockroach-teamcity
Copy link
Copy Markdown
Member

cockroach-teamcity commented Mar 18, 2021

This change is Reviewable

@andyyang890
Copy link
Copy Markdown
Collaborator Author

andyyang890 commented Mar 18, 2021

In my local testing, this improved the performance of the benchmark query from https://blog.cleverelephant.ca/2018/09/postgis-external-storage.html from ~55s to ~17s.

@otan
Copy link
Copy Markdown
Contributor

otan commented Mar 18, 2021

In my local testing, this improved the performance of the benchmark query from https://blog.cleverelephant.ca/2018/09/postgis-external-storage.html from ~55s to ~17s.

nice! do you have a profile of where time is being spent now?

@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch from bca0f43 to 14af793 Compare March 19, 2021 00:20
@andyyang890
Copy link
Copy Markdown
Collaborator Author

andyyang890 commented Mar 19, 2021

In my local testing, this improved the performance of the benchmark query from https://blog.cleverelephant.ca/2018/09/postgis-external-storage.html from ~55s to ~17s.

nice! do you have a profile of where time is being spent now?

https://share.polarsignals.com/f694a64/

@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch from 14af793 to 0303a71 Compare March 19, 2021 01:00
@andyyang890 andyyang890 marked this pull request as ready for review March 19, 2021 01:01
otan
otan approved these changes Mar 19, 2021
View reviewed changes
Copy link
Copy Markdown
Contributor

@otan otan left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i would see if you can make the same optimisations for st_contains and st_within

@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch from 0303a71 to ad5f4d5 Compare March 19, 2021 20:13
@andyyang890 andyyang890 requested a review from otan March 19, 2021 20:13
@andyyang890
Copy link
Copy Markdown
Collaborator Author

andyyang890 commented Mar 19, 2021

i would see if you can make the same optimisations for st_contains and st_within

I used the same baseline query but changed the function to ST_Contains and ST_Within and the performance of both improves from ~55s to ~12s.

Profile for ST_Contains: https://share.polarsignals.com/7a3ba6f/

@andyyang890 andyyang890 changed the title geo/geomfn: add point in polygon optimization to st_intersects geo/geomfn: add point in polygon optimization to a few binary predicates Mar 19, 2021
@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch 5 times, most recently from dea6356 to b13a30b Compare March 20, 2021 00:43
otan
otan suggested changes Mar 21, 2021
View reviewed changes
Copy link
Copy Markdown
Contributor

@otan otan left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice.

I've added a few comments to things I've noticed which could improve performance which I missed in the earlier PR.

You should probably have merged that intersects one first and then did this on top, to break up the work a bit! It's okay to break this stuff up and take care of perfection separately. This PR got more difficult factoring in Contains and WIthin and as a result requires cognitive load on top of the first PR to review. Ah well.

@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch from b13a30b to 2bbcf05 Compare March 23, 2021 00:32
@blathers-crl blathers-crl bot requested a review from otan March 23, 2021 00:32
@andyyang890 andyyang890 changed the title geo/geomfn: add point in polygon optimization to a few binary predicates geo/geomfn: add point in polygon optimization to st_intersects Mar 23, 2021
otan
otan approved these changes Mar 23, 2021
View reviewed changes
geo/geomfn: add point in polygon optimization to st_intersects
0b5b1ad 
This patch improves the performance of st_intersects for the
common use case of testing whether a (multi)polygon and a
(multi)point intersect.

Release note: None
@andyyang890 andyyang890 force-pushed the optimize_st_intersects branch from 2bbcf05 to 0b5b1ad Compare March 23, 2021 00:51
@andyyang890
Copy link
Copy Markdown
Collaborator Author

andyyang890 commented Mar 23, 2021 •
edited
Loading

Having PointKindAndPolygonKind return values instead of pointers and removing the extra conversion to and from geo.Geometry seems to have improved the performance further to ~10s.

Profile: https://share.polarsignals.com/ec7ae37/

@andyyang890
Copy link
Copy Markdown
Collaborator Author

andyyang890 commented Mar 23, 2021

bors r=otan

@craig
Copy link
Copy Markdown
Contributor

craig bot commented Mar 23, 2021

Build failed (retrying...):

@craig
Copy link
Copy Markdown
Contributor

craig bot commented Mar 23, 2021

Build failed (retrying...):

@craig
Copy link
Copy Markdown
Contributor

craig bot commented Mar 23, 2021

Build succeeded:

@craig craig bot merged commit 46620dd into cockroachdb:master Mar 23, 2021
@andyyang890 andyyang890 deleted the optimize_st_intersects branch March 23, 2021 22:09
@otan otan mentioned this pull request Apr 18, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@otan otan otan approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@andyyang890 @cockroach-teamcity @otan