[postgis-devel] Fwd: Why n-D indexes (based on GIDX) only support the &&& operator ?

[Esteban Zimanyi]

 The implementation I suggested is fully compatible with the current &&&
semantics (and thus no backward compatibility issues) but generalizes to
the three new operators that are currently commented out.

On Mon, Jul 30, 2018 at 3:32 PM, Paul Ramsey <pramsey at cleverelephant.ca>
wrote:

> I'm sure I initially implemented with just "relevant dimensions" and
> then switch, but I cannot for the life of my remember *why*. I know
> that changing the semantics of the &&& index are either a "no, never"
> thing, or a "only a 3.0" thing, so it might involves another operator
> or opclass for backwards compatibility reasons.
>
> P
>
> On Mon, Jul 30, 2018 at 2:41 AM, Esteban Zimanyi <ezimanyi at ulb.ac.be>
> wrote:
> >
> > As a follow-up to my question, in mobility applications we often need to
> > compare geometries of mixed dimensions. Suppose that we have 2D
> geometries
> > representing, e.g., provinces, and 3D trajectories of moving objects
> (e.g.,
> > cars) where the temporal features are encoded in the M dimension. We
> would
> > need queries such as the following ones
> >
> > -- Spatial-only query
> > SELECT * FROM Trips WHERE Trip &&& geometry 'Polygon((0 0,0 1,1 1,1 0,0
> > 0))';
> > -- Temporal-only query
> > SELECT * FROM Trips WHERE Trip &&& tsrange '[2001-01-01, 2001-01-05)';
> > -- Spatiotemporal query
> > SELECT * FROM Trips WHERE Trip &&& geometry 'LINESTRING M (0 0
> 978307200,1 1
> > 978393600,1 1 978652800)'
> >
> > where the last geometry is equivalent to '[Point(0 0)@2001-01-01, Point(1
> > 1)@2001-01-02, Point(1 1)@2001-01-05)'. The above approach can be
> > generalized when we have 4D trajectories of flying objects (e.g., drones
> or
> > planes) with both Z and M. Notice that in such scenarios the four
> operators
> > &&& (overlaps), ~ (contains), @ (within), and ~= (equals) would be useful
> > and index support for these operators is essential.
> >
> > The current approach followed in PostGIS is to extend the missing
> dimensions
> > of the arguments of the index predicate with a default value  +-infinity.
> > However, this approach only works for the overlaps and within operators.
> > When the missing dimensions are extended with +-infinity, the other
> > operators equals and contains will always evaluate to false, giving a
> wrong
> > result.
> >
> > An easy way to cope with this issue is to **only** compare the common
> > dimensions of the left and right arguments, ignoring the missing
> dimensions.
> > This requires minor changes in three functions of the file
> > gserialized_gist_nd.c
> >
> > /*
> > ** Overlapping GIDX box test.
> > **
> > ** Box(A) Overlaps Box(B) IFF for every common dimension d of both
> operands:
> > **   min(A,d) <= max(B,d) && max(A,d) => min(B,d)
> > **
> > ** Any missing dimension is ignored. Empty boxes never overlap.
> > */
> > bool gidx_overlaps(GIDX *a, GIDX *b)
> > {
> > int i, dims_a, dims_b;
> >
> > POSTGIS_DEBUG(5, "entered function");
> >
> > if ( (a == NULL) || (b == NULL) ) return false;
> >
> > if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
> > return false;
> >
> > dims_a = GIDX_NDIMS(a);
> > dims_b = GIDX_NDIMS(b);
> > /* For all common dimensions min(a) > max(b) and min(b) > max(a) */
> > for ( i = 0; i < Min(dims_a, dims_b); i++ )
> > {
> > /* If the missing dimension was not padded with -+FLT_MAX */
> > if ( GIDX_GET_MAX(a,i) != FLT_MAX && GIDX_GET_MAX(b,i) != FLT_MAX )
> > if ( GIDX_GET_MIN(a,i) > GIDX_GET_MAX(b,i) )
> > return false;
> > if ( GIDX_GET_MIN(b,i) > GIDX_GET_MAX(a,i) )
> > return false;
> > }
> >
> > return true;
> > }
> >
> > /*
> > ** Containment GIDX test.
> > **
> > ** Box(A) CONTAINS Box(B) IFF for every common dimension d of both
> operands:
> > **  (pt(A)LL < pt(B)LL) && (pt(A)UR > pt(B)UR)
> > **
> > ** Any missing dimension is ignored.
> > */
> > bool gidx_contains(GIDX *a, GIDX *b)
> > {
> > int i, dims_a, dims_b;
> >
> > POSTGIS_DEBUG(5, "entered function");
> >
> > if ( (a == NULL) || (b == NULL) ) return false;
> >
> > if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
> > return false;
> >
> > dims_a = GIDX_NDIMS(a);
> > dims_b = GIDX_NDIMS(b);
> >
> > /* For all common dimensions min(a) > min(b) and max(a) < max(b) */
> > for (i = 0; i < Min(dims_a, dims_b); i++)
> > {
> > /* If the missing dimension was not padded with -+FLT_MAX */
> > if ( GIDX_GET_MAX(a,i) != FLT_MAX && GIDX_GET_MAX(b,i) != FLT_MAX )
> > if ( GIDX_GET_MIN(a,i) > GIDX_GET_MIN(b,i) )
> > return false;
> > if ( GIDX_GET_MAX(a,i) < GIDX_GET_MAX(b,i) )
> > return false;
> > }
> >
> > return true;
> > }
> >
> > /*
> > ** Equality GIDX test.
> > **
> > ** Box(A) EQUALS Box(B) IFF for every common dimension d of both
> operands:
> > **   (pt(A)LL == pt(B)LL) && (pt(A)UR == pt(B)UR)
> > **
> > ** Any missing dimension is ignored.
> > */
> > bool gidx_equals(GIDX *a, GIDX *b)
> > {
> > uint32_t i;
> > int dims_a, dims_b;
> >
> > POSTGIS_DEBUG(5, "entered function");
> >
> > if ( (a == NULL) && (b == NULL) ) return true;
> > if ( (a == NULL) || (b == NULL) ) return false;
> >
> > if ( gidx_is_unknown(a) && gidx_is_unknown(b) )
> > return true;
> >
> > if ( gidx_is_unknown(a) || gidx_is_unknown(b) )
> > return false;
> >
> > dims_a = GIDX_NDIMS(a);
> > dims_b = GIDX_NDIMS(b);
> >
> > /* For all common dimensions min(a) == min(b), max(a) == max(b) */
> > for (i = 0; i < Min(dims_a, dims_b); i++)
> > {
> > /* If the missing dimension was not padded with -+FLT_MAX */
> > if ( GIDX_GET_MAX(a,i) != FLT_MAX && GIDX_GET_MAX(b,i) != FLT_MAX )
> > if ( GIDX_GET_MIN(a,i) != GIDX_GET_MIN(b,i) )
> > return false;
> > if ( GIDX_GET_MAX(a,i) != GIDX_GET_MAX(b,i) )
> > return false;
> > }
> > return true;
> > }
> >
> > I have tested this approach and works perfectly. I can prepare a PR with
> the
> > patches and the regression tests.
> >
> >
> >
> > _______________________________________________
> > postgis-devel mailing list
> > postgis-devel at lists.osgeo.org
> > https://lists.osgeo.org/mailman/listinfo/postgis-devel
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20180730/7c670ee6/attachment.html>