Add selectivity estimate?

[msdemlei]

I'm still regularly struggling with abysimal query plans when q3c functions are in queries; disabling seqscans helps a bit of course, but it certainly is not an suboptimal and has unwelcome side effects in general.

Now the support functions Laurenz Albe reports on on https://www.cybertec-postgresql.com/en/optimizer-support-functions/ would seem to be helpful here; I would guess that giving q3c_join a selectivity of (roughly) match_radius**2/4 pi (so: circle area over sphere area) would already greatly improve the query plans (even acknowledging that star density varies by orders of magnitude over the sky).

Do you have plans to add support functions? Do you see major obstacles to at least a very rough implementation that would assume evenly distributed objects?

[segasai]

Yes, I've been watching this topic for a long while and this is the reason I've implemented the selectivity function for parts of q3c_join (check here

q3c/q3c.c

Line 136 in 0254998

Datum pgq3c_seljoin(PG_FUNCTION_ARGS)

). The problem is that the q3c_ functions are SQL inlined and the underlying clauses that are executed are q3c_ang2ipix()<XX and q3c_ang2ipix()>YY. So the only way to have selectivity for this is to make custom type and operator which as far as I am aware would not allow the bitmap index scan.
So basically I don't know of a way of making it work. I would really want though. If you can demonstrate the approach that would work, I'll gladly help/accept it. But to my knowledge without going into new types/operators/operator classes it impossible and even with that I'm not sure.

[segasai]

Looking at the https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=74dfe58a5927b22c744b29534e67bfdd203ac028 patch, it seems it only supports conditions like
select * from where myfunction()
If there was a way to support
select * from where myfunction()<X or
select * from where myfunction() between X and Y

That would do the job, because writing those selectivities would be easy.

[msdemlei]

On Wed, Feb 10, 2021 at 06:58:20AM -0800, Sergey Koposov wrote: Yes, I've been watching this topic for a long while and this is the reason I've implemented the selectivity function for parts of q3c_join (check here https://github.com/segasai/q3c/blob/0254998c3a6084e53a4f6d4bd07552eabd453aaf/q3c.c#L136 ). The problem is that the q3c_ functions are SQL inlined and the underlying clauses that are executed are q3c_ang2ipix()<XX and q3c_ang2ipix()>YY. So the only way to have selectivity for this is to make custom type and operator which as far as I am aware would not allow the bitmap index scan.

So, the trouble is that either (a) we can provide selectivity estimates to q3c_join(ra1, dec1, ra2, dec2, radius) but then lose the ability to have index scans, defeating the whole purpose, or (b) we keep letting postgres inline things and then lose the ability to provide selectivity estimates? Ouch. Since @laurenz has written the nice blog post: Perhaps he can point at a route to escape from this conundrum?

[segasai]

(a) we can provide selectivity estimates to q3c_join(ra1, dec1, ra2,
dec2, radius) but then lose the ability to have index scans,
defeating the whole purpose, or
(b) we keep letting postgres inline things and then lose the ability
to provide selectivity estimates?

That's my understanding, but I've been also looking at the git commits of those support functions, and maybe there is something there that provides support for func()<value queries or provides a way to specify index strategy given a function call, but I am not sure. There isn't a lot of documentation there.. I was thinking previously writing an email pgsql-hackers asking about it, but haven't had time. (if @laurenz can help, that'd be great).
Realistically we need PG

to be able to execute

( func(a,b) between X and Y)  or 
( func(a,b) between X and Y)  or 
( func(a,b) between X and Y)  

queries with user-provided selectivity for between operator.
Alternatively I'm okay to introduce a user defined operator instead of "between". Something like
func(a,b) @@ ( X, Y)
if the usage of the operator will essentially lead
to the same query as above.

[laurenz]

Hm. Can't you inline a function, and the inlined expression contains a function with a support function?
I didn't look at this special case though.

[segasai]

Yes, that's idea. But I don't know if the support functions for function F can provide selectivity for queries like this
where (F(a,b)> X and F(a,b)<Y) or ( F(a,b)>Z and F(a,b)<K)
because our current functions are inlined like that

q3c/scripts/q3c--2.0.0.sql

Line 204 in 0254998

SELECT (((q3c_ang2ipix($3,$4)>=(q3c_nearby_it($1,$2,$5,0))) AND (q3c_ang2ipix($3,$4)<=(q3c_nearby_it($1,$2,$5,1))))

[laurenz]

After looking at what q3c_join does, it seems indeed to be a perfect candidate for a support function.

You would do away with the inlined SQL function and use a support function in its place, see PostGIS' postgis_index_supportfn.

The support function would make the optimizer run an index scan instead of or as a filter before executing the function.

[segasai]

Thank you for the pointer @laurenz , I'll take a look there.

[gshennessy]

I've never understood why in q3c--2.0.0.sql the routine q3c_join tests for a range of values against q3c_nearby_it with four cases but q3c_radial_query tests for 200 cases. Is that number related to the number of polygons that can be tested for, or is that a coincidence? Is this documented anywhere?

[segasai]

The reason is that the radial query is mostly designed for large circle queries, so making a more precise approximation to a circle by going deeper in the quad-tree can save significant I/O. For the q3c_join, the main use case was thought to have a pretty small x-match radius, therefore it is less crucial to have a good quad-tree approximation to a circle, as likely stuff will be sitting on the same disk block anyway.

That's the original reasoning (I think). Whether in practice q3c_radial_query going deep is that beneficial is not 100% obvious (but for sure for a query near the galactic plane in say gaia q3c_radial_query with just 4 squares would run significantly longer)

[gshennessy]

Might we be over thinking this? I'm also struggling with the issue plans not using the q3c index when I (as a human) think they should. Rather than dealing with anything complicated, perhaps simply dealing with a SupportRequestSelectivity call to allow the planner to make better row estimates would help.

I don't know if people can see the plan at https://explain.dalibo.com/plan/RMS
I try to match a 526 star landolt table with a 747million star allwise catalog.
The bitmab index scan is estimated as 43 billion rows, ending up over estimated by 8 million.
The 43 billion row estimate is 526*747Million/9, which is what postgres assumes as a default selectivity.
if we have q3c_seljoin set a selectivity as theta squared divided by 41252 i woudl think we would be fine.

Thoughts?

[segasai]

That's exactly what seljoin does

q3c/q3c.c

Line 168 in 1290e00

ratio = 3.14 * rad * rad / 41252.; /* pi*r^2/whole_sky_area */

But I attach that selectivity to a special operator see https://github.com/segasai/q3c/blob/master/scripts/q3c--2.0.0.sql
not the q3c_ang2pix> <= conditions. If someone helps me with how to attach SupportRequestSelectivity stuff to q3c_join, that'd be appreciated. It would take me probably few days to figure this out and I don't have that time now.

I also looked recently at a way of using the int8range types to replace the q3c_ang2ipix()> <= conditions
https://www.mail-archive.com/pgsql-general@lists.postgresql.org/msg30615.html
with the hope of better estimates, but it looks PG is still missing some functionality there for it to be useful.

[gshennessy]

I started a thread on https://dba.stackexchange.com/questions/312526/in-postgresql-13-how-do-i-ensure-a-supportrequestselectivity-is-made where I show a first attempt at a selectivity operator, but my function isn't
called with SupportRequestSelectivity, only SupportRequestSimplify. I've also posted the same information
to pgsql-hackers. I'll keep you in touch in case there is progress on this issue.