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

[Paul Ramsey]

Good job looking that up... so maybe it was shared-dimensions when I
put it down and my recollection isn't actually faulty. Sandro, do you
remember the use case that led you to implement infinite expansion?

On Mon, Jul 30, 2018 at 7:16 AM, Esteban Zimanyi <ezimanyi at ulb.ac.be> wrote:
> According to PostGIS' ChangeLog file Sandro was the last person working on
> the &&& operator
>
> ---------------------------------------------------------------
> 2015-02-20 17:27  Sandro Santilli <strk at kbt.io>
>
> * [r13250] libpgcommon/gserialized_gist.c,
>   libpgcommon/gserialized_gist.h, postgis/gserialized_gist_nd.c,
>   regress/operators.sql, regress/operators_expected: Fix
>   dimensionality confusion in &&& operator (#3045)
>
>   Also enforce the concept that missing dimensions are infinite,
>   thus always intersecting present dimensions.
>   See
>   http://lists.osgeo.org/pipermail/postgis-devel/2015-February/024759.html
> ---------------------------------------------------------------
>
>
> On Mon, Jul 30, 2018 at 3:47 PM, Esteban Zimanyi <ezimanyi at ulb.ac.be> wrote:
>>
>> 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
>>
>>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel