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

[Paul Ramsey]

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