Translation for PostGIS && operator

[bjornharrtell]

The PostGIS && operator allows to do indexed search without secondary geometric intersection filter. This can be desired for some types of data (fx. very detailed geometries) and when the secondary filtering is desired to be done at some other place.

AFAIK I can't see any way to translate a linq expression to use the operator though, because there nothing equivalent in NTS I suppose?

It looks like DbFunctions has an extension for the "Distance" operator <-> with DistanceKnn so perhaps that is the way to support the && too with a function named for example IntersectsBbox?

I've made an attempt to implement at #3484 but it's not working as expected yet.

[roji]

The && operator seems like an intersection operation, which doesn't seem related to distance (DistanceKnn, <->). We already support ST_Intersects, which seems quite similar (though && seems to intersect the bounding boxes) - is that maybe what you're looking for?

For providing a translation specifically for &&, I'd maybe check with the NetTopologySuite folks first if they have a .NET API which corresponds to this, or at least whether there's an API to get the bounding box of a geometry; if the latter exists, then && could be expressed as an intersection operation over the two bounding boxes of the input geometries.

[bjornharrtell]

I didn't mean to say intersects was functionally similar to distance, just that the implementation of EF.Functions.DistanceKnn is kind of similar (as it exposes the <-> operator via DbFunction extension) to how && operator could be exposed.

I intentionally want to use the && operator instead of ST_Intersects to avoid the secondary geometric intersection calculation that occurs with ST_Intersects.

There is API in NTS to get the bounding box (https://nettopologysuite.github.io/NetTopologySuite/api/NetTopologySuite.Geometries.Geometry.html#NetTopologySuite_Geometries_Geometry_EnvelopeInternal) but it may be problematic due to #1313 (the box2d type in PostGIS isn't serialisable and seems "internal" or close to it).

[bjornharrtell]

@roji I have some hope that my argumentation above can persuade? 🙂 The PR is in working order AFAIK.

[roji]

@bjornharrtell sorry, there is a lot going on at the moment, expect delayed responses in general.

I'm noticing in your test that the client-side validation uses EnvelopeInternal.Intersects:

        await AssertQuery(
            async,
            ss => ss.Set<PolygonEntity>().Select(e => new { e.Id, IntersectsBbox = (bool?)EF.Functions.IntersectsBbox(e.Polygon, polygon) }),
            ss => ss.Set<PolygonEntity>().Select(e => new { e.Id, IntersectsBbox = (e.Polygon == null ? (bool?)null : e.Polygon.EnvelopeInternal.Intersects(polygon.EnvelopeInternal)) }),

Does NTS's EnvelopeInternal.Intersects() indeed perfectly match the PostgreSQL && operator? If it does (I'm relying on you to make sure), then it does seem like we should translate that rather than introducing a new IntersectsBbox stub...

#1313 and box2d not being serializable isn't a problem here - we're not trying to read or write the envelope, merely identify a pattern in the user's query tree (Intersects() method call over EnvelopeInternal property call), and translate that to &&.

However, implementing this is unfortunately a bit complicated: since it's not a simple method call, a method translator can't be used; this requires more low-level matching - see NpgsqlSqlTranslatingExpressionVisitor.VisitMethod. Further, there's currently no way fo a plugin (such as the NetTopologySuite one) to add such a complex translation - all that's supported is simple method and member translators. So to do this, we'd have to implement the translation in the provider itself (in NpgsqlSqlTranslatingExpressionVisitor.VisitMethod), and use string-based matching to avoid taking a reference on NTS.

So here's what I propose: if you can confirm that EnvelopeInternal.Intersects() is a 100% accurate way to represent the PG && operation, I'll go ahead and implement that translation - sounds good?

[omaristalis]

I'm very keen to see this go in, if all is well. Using ST_Intersects takes 10x longer than && and a GIST index in my query.

[bjornharrtell]

@roji your suggestion seemed good to me initially, but since you made it clear it's on me to prove it's equivalent I've done some research and talked to PostGIS people and the short answer, unfortunately, is that EnvelopeInternal.Intersects() while functionally same is not 100% equivalent/exact with the && operator in PostGIS. When numbers go into float single vs double precision land, PostGIS will give false positives.

The short version of why is that PostGIS in most cases represents bbox internally (and in spatial index) with single (4-byte) floats as an acceptable approximate for historical and performance reasons.

Explanation in SQL, select 'point(1 1.00000001)'::geometry && 'point(1 1)'::geometry will return true because their 4-bytes float bboxes are overlapping. Doing the same in NTS and EnvelopeInternal.Intersects() will return false.

I would suggest a custom IntersectsBbox is the better option to go with here due to this fact. If you agree, I will try to add an appropriate explanation in the docs for the function.

That said, I would't be 100% against still going with EnvelopeInternal.Intersects() and a warning about the precision / false positives risk in the docs instead.

[bjornharrtell]

@roji a little gentle reminder of this one. :)

[Pieeer1]

This would be a valuable addition in my mind, currently have to run this in manual SQL instead of an ideal scenario. IE:

        var query = _mapContext.Set<Line>()
            .Where(l => l.LineString.Overlaps(PostGisExtensions.TileEnvelope(z, x, y, Constants.DefaultSRID3857Bounds, 0.0f)))
            .Select(l => l.LineString.AsMvtGeometry(PostGisExtensions.TileEnvelope(z, x, y, Constants.DefaultSRID3857Bounds, 0.0f), 4096, 64, true))
            .ToQueryString();

Creates the folllowing:

-- @__z_0='7'
-- @__x_1='22'
-- @__y_2='51'
SELECT ST_AsMVTGeom(l.geom, ST_TileEnvelope(@__z_0, @__x_1, @__y_2, GEOMETRY 'SRID=3857;LINESTRING (-20037508.342789 -20037508.342789, 20037508.342789 20037508.342789)', 0), 4096, 64, TRUE)
FROM dbo.lines AS l
WHERE ST_Overlaps(l.geom, ST_TileEnvelope(@__z_0, @__x_1, @__y_2, GEOMETRY 'SRID=3857;LINESTRING (-20037508.342789 -20037508.342789, 20037508.342789 20037508.342789)', 0))

where I would hope for

SELECT ST_AsMVTGeom(l.geom, ST_TileEnvelope(7, 22, 51, GEOMETRY 'LINESTRING (-20037508.342789 -20037508.342789, 20037508.342789 20037508.342789)', 0), 4096, 64, TRUE)
FROM dbo.lines AS l
WHERE l.geom && ST_TileEnvelope(7, 22, 51, GEOMETRY 'LINESTRING (-20037508.342789 -20037508.342789, 20037508.342789 20037508.342789)', 64.0 / 4096)

[bjornharrtell]

I feel this is an important improvement/fix so I'll try to nudge for attention @roji, I hope that is ok.

[JarrodOsborne]

Bump. This would be a huge improvement.

[roji]

@bjornharrtell sorry for not answering here for so long.

It seems like you've done the research here, what you say seems reasonable. So if you want rebase #3484 on top of latest main (it currently targets hotfix/9.0.5), I'm good to merge this for 11.0. Let me know.