[postgis-devel] Fwd: Why n-D indexes (based on GIDX) only support the &&& operator ?
Esteban Zimanyi
ezimanyi at ulb.ac.be
Mon Jul 30 07:16:20 PDT 2018
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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20180730/d5613033/attachment-0001.html>
More information about the postgis-devel
mailing list