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

[Esteban Zimanyi]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20180730/814a7c69/attachment.html>