NotificationsYou must be signed in to change notification settings
Fork15
Star22

Selectivity estimators for <@(spoint, scircle) and spoint_dwithin(spoint, spoint, float8)#80

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Jump to bottom

Merged

vitcpp merged 1 commit intopostgrespro:masterfromcybertec-postgresql:selectivity

Oct 20, 2023

Merged

Selectivity estimators for <@(spoint, scircle) and spoint_dwithin(spoint, spoint, float8)#80

vitcpp merged 1 commit intopostgrespro:masterfromcybertec-postgresql:selectivity

Oct 20, 2023

Conversation

Copy link

Contributor

df7cb commentedOct 6, 2023

This implements restriction selectivity estimation for the <@ @> !<@ !@>
family of operators on spoint and scircle. The selectivity is estimated
to be (area of sphere circle) / (4 pi).

Queries likeselect * from sky where sky.star <@ scircle(const, radius)
will be able to properly estimate if using an index is appropriate
depending on the size of radius.

Secondly, a function spoint_dwithin(p1 spoint, p2 spoint, radius float8)
is added that effectively returnsp1 <-> p2 <= radius. But other than
this two-operator expression, it has GIST index support so the optimizer
can rewrite it to eitherp1 <@ scircle(p2, radius) orp2 <@ scircle(p1, radius), i.e. it is symmetric in the first two arguments.

This allows efficient matching queries without the user having to encode
the join ordering in the query.

On PostgreSQL 10/11, the spoint_dwithin function is created, but without
the GIST support since that only appeared in PG12.

The file expected/selectivity_1.out is used on PG10/11; it has <@
flipped around to @> in some plans.

Copy link

Contributor

esabol commentedOct 6, 2023

This is an awesome contribution! Thank you!

esabol reviewed

Oct 6, 2023

View reviewed changes

MakefileShow resolvedHide resolved

Copy link

ContributorAuthor

df7cb commentedOct 7, 2023 via email

Am 6. Oktober 2023 21:41:54 MESZ schrieb Ed Sabol ***@***.***>:

@esabol commented on this pull request.> @@ -241,8 +248,11 @@ pg_sphere--1.2.3--1.3.0.sql: pgs_brin.sql.in pg_sphere--1.3.0--1.3.1.sql: cat ***@***.*** > $@-pg_sphere--1.3.1--1.3.2.sql:-cat ***@***.*** > $@+ifeq ($(has_support_functions),y)+pg_sphere--1.3.1--1.3.2.sql: pgs_gist_support.sql.in+endif+pg_sphere--1.3.1--1.3.2.sql: pgs_circle_sel.sql.in+cat ***@***.*** $^ > $@I'm not sure, but I wonder if lines 251-255 should be the following instead?```ifeq ($(has_support_functions),y)pg_sphere--1.3.1--1.3.2.sql: pgs_gist_support.sql.in pgs_circle_sel.sql.inelsepg_sphere--1.3.1--1.3.2.sql: pgs_circle_sel.sql.inendifcat ***@***.*** $^ > $@```--Reply to this email directly or view it on GitHub:#80 (review)You are receiving this because you authored the thread.Message ID: ***@***.***>

It does works that way, $^ collects all dependencies.

esabol approved these changes

Oct 12, 2023

View reviewed changes

esabol suggested changes

Oct 12, 2023

View reviewed changes

Copy link

Contributor

esabol left a comment

Choose a reason for hiding this comment

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

Actually, could you make a couple minor tweaks to the documentation changes? Thanks!

doc/functions.sgm OutdatedShow resolvedHide resolved

vitcpp reviewed

Oct 12, 2023

View reviewed changes

src/point.c Outdated

		float8within = PG_GETARG_FLOAT8(2);
		float8dist = spoint_dist(p1, p2);

		PG_RETURN_BOOL(dist <= within);

Copy link

Contributor

vitcppOct 11, 2023

Choose a reason for hiding this comment

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

I guess, FPle should be used instead of direct comparison. pgSphere calculations are executed with EPSILON = 1E-9. When we compare two distances, all the numbers less than 1E-9 should be treated as zeroes, I think. There is the example: spoint_in_circle() function, where FPle is used. I would also propose to add some tests for this function, if it can be done.

Copy link

ContributorAuthor

df7cbOct 12, 2023

Choose a reason for hiding this comment

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

Ack, will change that (likely later, not now).

Copy link

Contributor

vitcppOct 13, 2023

Choose a reason for hiding this comment

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

Sure, thank you! No hurry.

Copy link

ContributorAuthor

df7cbOct 16, 2023

Choose a reason for hiding this comment

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

Implemented in89dc41d.

src/pgs_util.hShow resolvedHide resolved

MakefileShow resolvedHide resolved

src/circle_sel.cShow resolvedHide resolved

esabol reviewed

Oct 14, 2023

View reviewed changes

expected/index.outShow resolvedHide resolved

Alena0704 reviewed

Oct 16, 2023

View reviewed changes

src/circle_sel.cShow resolvedHide resolved

pgs_circle_sel.sql.inShow resolvedHide resolved

src/circle_sel.cShow resolvedHide resolved

src/gist_support.cShow resolvedHide resolved

df7cb force-pushed theselectivity branch from89dc41d toc9e410fCompare

October 16, 2023 13:33

esabol approved these changes

Oct 16, 2023

View reviewed changes

esabol suggested changes

Oct 16, 2023

View reviewed changes

doc/functions.sgm OutdatedShow resolvedHide resolved

esabol approved these changes

Oct 18, 2023

View reviewed changes

Copy link

Contributor

esabol commentedOct 18, 2023

In case anyone is interested in comparing selectivity estimators, similar efforts are in progress over in the q3c repo as well:

segasai/q3c#30
https://github.com/segasai/q3c/pull/35/files

df7cb force-pushed theselectivity branch froma4b600f to8ed421eCompare

October 18, 2023 11:56

Copy link

ContributorAuthor

df7cb commentedOct 18, 2023

Rebased.

vitcpp requested changes

Oct 19, 2023

View reviewed changes

Copy link

Contributor

vitcpp left a comment

Choose a reason for hiding this comment

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

Just one trivial change. Thank you!

src/point.c OutdatedShow resolvedHide resolved

src/circle_sel.cShow resolvedHide resolved

Implement restriction selectivity estimators for <@(spoint, scircle)

65217de

This implements restriction selectivity estimation for the <@ @> !<@ !@>family of operators on spoint and scircle. The selectivity is estimatedto be (area of sphere circle) / (4 pi).Queries like `select * from sky where sky.star <@ scircle(const, radius)`will be able to properly estimate if using an index is appropriatedepending on the size of radius.Secondly, a function spoint_dwithin(p1 spoint, p2 spoint, radius float8)is added that effectively returns `p1 <-> p2 <= radius`. But other thanthis two-operator expression, it has GIST index support so the optimizercan rewrite it to either `p1 <@ scircle(p2, radius)` or `p2 <@scircle(p1, radius)`, i.e. it is symmetric in the first two arguments.This allows efficient matching queries without the user having to encodethe join ordering in the query.On PostgreSQL 10/11, the spoint_dwithin function is created, but withoutthe GIST support since that only appeared in PG12.The file expected/selectivity_1.out is used on PG10/11; it has <@flipped around to @> in some plans.

df7cb force-pushed theselectivity branch from8ed421e to65217deCompare

October 19, 2023 11:28

vitcpp approved these changes

Oct 19, 2023

View reviewed changes

Alena0704 approved these changes

Oct 20, 2023

View reviewed changes