From e2a4d02baa80bfd8257530e200a8793d0898366f Mon Sep 17 00:00:00 2001
From: Paul Ramsey <pramsey@cleverelephant.ca>
Date: Wed, 13 Dec 2017 20:51:36 +0000
Subject: [PATCH] _postgis_index_extent() for extent from index

git-svn-id: http://svn.osgeo.org/postgis/trunk@16151 b70326c6-7e19-0410-871a-916f4a2858ee
---
 NEWS                             |   1 +
 libpgcommon/gserialized_gist.h   |   5 ++
 postgis/gserialized_estimate.c   |   6 +-
 postgis/gserialized_gist_2d.c    | 114 +++++++++++++++++++++++--------
 postgis/gserialized_gist_nd.c    |   7 +-
 regress/estimatedextent.sql      |  39 +++++++----
 regress/estimatedextent_expected |  12 ++++
 7 files changed, 138 insertions(+), 46 deletions(-)

diff --git a/NEWS b/NEWS
index ecac7ba04..65a298a02 100644
--- a/NEWS
+++ b/NEWS
@@ -6,6 +6,7 @@ PostGIS 2.5.0
   - #3564, ST_LineInterpolatePoints (Dan Baston)
   - #3896, PostGIS_Extensions_Upgrade()
   - #3913, Upgrade when creating extension from unpackaged (Sandro Santilli)
+  - #2256, _postgis_index_extent() for extent from index (Paul Ramsey)
 
 * Breaking Changes *
   - #3885, version number removed from address_standardize lib file
diff --git a/libpgcommon/gserialized_gist.h b/libpgcommon/gserialized_gist.h
index 67d3f2e01..8ebf6bfe3 100644
--- a/libpgcommon/gserialized_gist.h
+++ b/libpgcommon/gserialized_gist.h
@@ -66,6 +66,8 @@ GIDX* gidx_new(int ndims) ;
 /* Increase the size of a GIDX */
 void gidx_expand(GIDX *a, float d);
 
+/* Note empty GIDX */
+bool gidx_is_unknown(const GIDX *a);
 
 /* Generate human readable form for GIDX. */
 char* gidx_to_string(GIDX *a) ;
@@ -99,6 +101,9 @@ GIDX* gidx_copy(GIDX *b);
 /* Grow the first argument to contain the second */
 void gidx_merge(GIDX **b_union, GIDX *b_new);
 
+/* Note empty BOX2DF */
+bool box2df_is_empty(const BOX2DF *a);
+
 /* Fill in a gbox from a GIDX */
 void gbox_from_gidx(GIDX *a, GBOX *gbox, int flags);
 
diff --git a/postgis/gserialized_estimate.c b/postgis/gserialized_estimate.c
index b475a8b01..ad9a42ac1 100644
--- a/postgis/gserialized_estimate.c
+++ b/postgis/gserialized_estimate.c
@@ -2327,7 +2327,7 @@ Datum gserialized_estimated_extent(PG_FUNCTION_ARGS)
 		PG_RETURN_NULL();
 	}
 
-#if 0
+#if 1
 	/* Read the extent from the head of the spatial index, if there is one */
 	idx_oid = table_get_spatial_index(tbl_oid, col, &key_type);
 	if (!idx_oid)
@@ -2525,11 +2525,15 @@ spatial_index_read_extent(Oid idx_oid, int key_type)
 
 	if (key_type == STATISTIC_SLOT_2D && bounds_2df)
 	{
+		if (box2df_is_empty(bounds_2df))
+			return NULL;
 		gbox = gbox_new(0);
 		box2df_to_gbox_p(bounds_2df, gbox);
 	}
 	else if (key_type == STATISTIC_SLOT_ND && bounds_gidx)
 	{
+		if (gidx_is_unknown(bounds_gidx))
+			return NULL;
 		gbox = gbox_new(0);
 		gbox_from_gidx(bounds_gidx, gbox, 0);
 	}
diff --git a/postgis/gserialized_gist_2d.c b/postgis/gserialized_gist_2d.c
index 634c95982..103d95e74 100644
--- a/postgis/gserialized_gist_2d.c
+++ b/postgis/gserialized_gist_2d.c
@@ -153,7 +153,32 @@ BOX2DF* box2df_copy(BOX2DF *b)
 	return c;
 }
 
+inline bool box2df_is_empty(const BOX2DF *a)
+{
+	if (isnan(a->xmin))
+		return true;
+	else
+		return false;
+}
+
+static inline void box2df_set_empty(BOX2DF *a)
+{
+	a->xmin = a->xmax = a->ymin = a->ymax = NAN;
+	return;
+}
 
+static inline void box2df_set_finite(BOX2DF *a)
+{
+	if ( ! isfinite(a->xmax) )
+		a->xmax = FLT_MAX;
+	if ( ! isfinite(a->ymax) )
+		a->ymax = FLT_MAX;
+	if ( ! isfinite(a->ymin) )
+		a->ymin = -1*FLT_MAX;
+	if ( ! isfinite(a->xmin) )
+		a->xmin = -1*FLT_MAX;
+	return;
+}
 
 /* Enlarge b_union to contain b_new. If b_new contains more
    dimensions than b_union, expand b_union to contain those dimensions. */
@@ -202,7 +227,7 @@ static float box2df_size(const BOX2DF *a)
 {
 	float result;
 
-	if ( a == NULL )
+	if ( a == NULL || box2df_is_empty(a) )
 		return (float)0.0;
 
 	if ( (a->xmax <= a->xmin) || (a->ymax <= a->ymin) )
@@ -219,7 +244,7 @@ static float box2df_size(const BOX2DF *a)
 
 static float box2df_edge(const BOX2DF *a)
 {
-	if ( a == NULL )
+	if ( a == NULL || box2df_is_empty(a) )
 		return (float)0.0;
 
 	return ((a->xmax) - (a->xmin)) + ((a->ymax) - (a->ymin));
@@ -237,10 +262,10 @@ static float box2df_union_size(const BOX2DF *a, const BOX2DF *b)
 		return 0.0;
 	}
 
-	if ( a == NULL )
+	if ( a == NULL || box2df_is_empty(a) )
 		return box2df_size(b);
 
-	if ( b == NULL )
+	if ( b == NULL || box2df_is_empty(b) )
 		return box2df_size(a);
 
 	result = ((double)Max(a->xmax,b->xmax) - (double)Min(a->xmin,b->xmin)) *
@@ -264,10 +289,10 @@ static float box2df_union_edge(const BOX2DF *a, const BOX2DF *b)
 		return 0.0;
 	}
 
-	if ( a == NULL )
+	if ( a == NULL || box2df_is_empty(a) )
 		return box2df_edge(b);
 
-	if ( b == NULL )
+	if ( b == NULL || box2df_is_empty(b) )
 		return box2df_edge(a);
 
 	result = (Max(a->xmax,b->xmax) - Min(a->xmin,b->xmin)) +
@@ -308,6 +333,10 @@ static inline void box2df_validate(BOX2DF *b)
 {
 	float tmp;
 	POSTGIS_DEBUGF(5,"validating box2df (%s)", box2df_to_string(b));
+
+	if ( box2df_is_empty(b) )
+		return;
+
 	if ( b->xmax < b->xmin )
 	{
 		tmp = b->xmin;
@@ -325,7 +354,8 @@ static inline void box2df_validate(BOX2DF *b)
 
 static bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	if ( (a->xmin > b->xmax) || (b->xmin > a->xmax) ||
 	     (a->ymin > b->ymax) || (b->ymin > a->ymax) )
@@ -338,7 +368,12 @@ static bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
 
 bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b )
+		return false;
+
+	/* All things can contain EMPTY (except EMPTY) */
+	if ( box2df_is_empty(b) && ! box2df_is_empty(a) )
+		return true;
 
 	if ( (a->xmin > b->xmin) || (a->xmax < b->xmax) ||
 	     (a->ymin > b->ymin) || (a->ymax < b->ymax) )
@@ -351,7 +386,12 @@ bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b )
+		return false;
+
+	/* EMPTY is within all other things (except EMPTY) */
+	if ( box2df_is_empty(a) && ! box2df_is_empty(b) )
+		return true;
 
 	POSTGIS_DEBUG(5, "entered function");
 	return box2df_contains(b,a);
@@ -359,25 +399,24 @@ static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( a &&  b ) {
-		if ( (a->xmin != b->xmin) || (a->xmax != b->xmax) ||
-		     (a->ymin != b->ymin) || (a->ymax != b->ymax) )
-		{
-			return false;
-		}
+	if ( !a && !b )
 		return true;
-	} else if ( a || b ) {
-		/* one empty, one not */
+	else if ( !a || !b )
 		return false;
-	} else {
-		/* both empty */
+	else if ( box2df_is_empty(a) && box2df_is_empty(b) )
 		return true;
-	}
+	else if ( box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
+	else if ((a->xmin == b->xmin) && (a->xmax == b->xmax) && (a->ymin == b->ymin) && (a->ymax == b->ymax))
+		return true;
+	else
+		return false;
 }
 
 static bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.xmax <= b.xmax */
 	return a->xmax <= b->xmax;
@@ -385,7 +424,8 @@ static bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_left(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.xmax < b.xmin */
 	return a->xmax < b->xmin;
@@ -393,7 +433,8 @@ static bool box2df_left(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_right(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.xmin > b.xmax */
 	return a->xmin > b->xmax;
@@ -401,7 +442,8 @@ static bool box2df_right(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.xmin >= b.xmin */
 	return a->xmin >= b->xmin;
@@ -409,7 +451,8 @@ static bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.ymax <= b.ymax */
 	return a->ymax <= b->ymax;
@@ -417,7 +460,8 @@ static bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_below(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.ymax < b.ymin */
 	return a->ymax < b->ymin;
@@ -425,7 +469,8 @@ static bool box2df_below(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_above(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.ymin > b.ymax */
 	return a->ymin > b->ymax;
@@ -433,7 +478,8 @@ static bool box2df_above(const BOX2DF *a, const BOX2DF *b)
 
 static bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
 {
-	if ( ! a || ! b ) return false; /* TODO: might be smarter for EMPTY */
+	if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
+		return false;
 
 	/* a.ymin >= b.ymin */
 	return a->ymin >= b->ymin;
@@ -955,8 +1001,12 @@ Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
 	/* Is the bounding box valid (non-empty, non-infinite)? If not, return input uncompressed. */
 	if ( result == LW_FAILURE )
 	{
+		box2df_set_empty(&bbox_out);
+		gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
+		              entry_in->rel, entry_in->page, entry_in->offset, false);
+
 		POSTGIS_DEBUG(4, "[GIST] empty geometry!");
-		PG_RETURN_POINTER(entry_in);
+		PG_RETURN_POINTER(entry_out);
 	}
 
 	POSTGIS_DEBUGF(4, "[GIST] got entry_in->key: %s", box2df_to_string(&bbox_out));
@@ -965,8 +1015,12 @@ Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
 	if ( ! isfinite(bbox_out.xmax) || ! isfinite(bbox_out.xmin) ||
 	     ! isfinite(bbox_out.ymax) || ! isfinite(bbox_out.ymin) )
 	{
+		box2df_set_finite(&bbox_out);
+		gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
+		              entry_in->rel, entry_in->page, entry_in->offset, false);
+
 		POSTGIS_DEBUG(4, "[GIST] infinite geometry!");
-		PG_RETURN_POINTER(entry_in);
+		PG_RETURN_POINTER(entry_out);
 	}
 
 	/* Enure bounding box has minimums below maximums. */
diff --git a/postgis/gserialized_gist_nd.c b/postgis/gserialized_gist_nd.c
index 3f988f5e1..039854d9a 100644
--- a/postgis/gserialized_gist_nd.c
+++ b/postgis/gserialized_gist_nd.c
@@ -154,7 +154,7 @@ static inline void gidx_validate(GIDX *b)
 /* An "unknown" GIDX is used to represent the bounds of an EMPTY
    geometry or other-wise unindexable geometry (like one with NaN
    or Inf bounds) */
-static inline bool gidx_is_unknown(const GIDX *a)
+inline bool gidx_is_unknown(const GIDX *a)
 {
 	size_t size = VARSIZE(a) - VARHDRSZ;
 	/* "unknown" gidx objects have a too-small size of one float */
@@ -168,6 +168,11 @@ static inline void gidx_set_unknown(GIDX *a)
 	SET_VARSIZE(a, VARHDRSZ);
 }
 
+static inline void gidx_set_finite(GIDX *a)
+{
+	SET_VARSIZE(a, VARHDRSZ);
+}
+
 /* Enlarge b_union to contain b_new. If b_new contains more
    dimensions than b_union, expand b_union to contain those dimensions. */
 void gidx_merge(GIDX **b_union, GIDX *b_new)
diff --git a/regress/estimatedextent.sql b/regress/estimatedextent.sql
index d237b55c3..93c549a83 100644
--- a/regress/estimatedextent.sql
+++ b/regress/estimatedextent.sql
@@ -187,18 +187,29 @@ round(st_ymin(e.e)::numeric, 2), round(st_ymax(e.e)::numeric, 2) from e;
 
 drop table p cascade;
 
-
--- create table test (id serial primary key, geom1 geometry, geom2 geometry);
--- create index test_x1 on test using gist (geom1);
--- create index test_x2 on test using gist (geom2);
--- select _postgis_gserialized_index_extent('test', 'geom1');
--- select _postgis_gserialized_index_extent('test', 'geom2');
--- insert into test (geom1, geom2) select NULL, NULL;
--- insert into test (geom1, geom2) select 'POINT EMPTY', 'LINESTRING EMPTY';
--- insert into test (geom1, geom2) select 'POINT EMPTY', 'LINESTRING EMPTY';
--- select _postgis_gserialized_index_extent('test', 'geom1');
--- select _postgis_gserialized_index_extent('test', 'geom2');
--- insert into test (geom1, geom2) select st_makepoint(s, s), st_makepoint(2*s, 2*s) from generate_series(-100,100) s;
--- select _postgis_gserialized_index_extent('test', 'geom1');
--- select _postgis_gserialized_index_extent('test', 'geom2');
+--
+-- Index assisted extent generation
+--
+create table test (id serial primary key, geom1 geometry, geom2 geometry);
+create index test_x1 on test using gist (geom1);
+create index test_x2 on test using gist (geom2);
+select '1.a null', _postgis_index_extent('test', 'geom1');
+select '1.b null', _postgis_index_extent('test', 'geom2');
+insert into test (geom1, geom2) select NULL, NULL;
+insert into test (geom1, geom2) select 'POINT EMPTY', 'LINESTRING EMPTY';
+select '2.a null', _postgis_index_extent('test', 'geom1');
+select '2.b null', _postgis_index_extent('test', 'geom2');
+insert into test (geom1, geom2) select 'POINT EMPTY', 'LINESTRING EMPTY' from generate_series(0,1024);
+select '3.a null', _postgis_index_extent('test', 'geom1');
+select '3.b null', _postgis_index_extent('test', 'geom2');
+insert into test (geom1, geom2) select st_makepoint(s, s), st_makepoint(2*s, 2*s) from generate_series(-100,100) s;
+select '4.a box',_postgis_index_extent('test', 'geom1');
+select '4.b box',_postgis_index_extent('test', 'geom2');
+delete from test;
+select '5.a bad-box',_postgis_index_extent('test', 'geom1');
+select '5.b bad-box',_postgis_index_extent('test', 'geom2');
+vacuum full test;
+select '6.a null', _postgis_index_extent('test', 'geom1');
+select '6.b null', _postgis_index_extent('test', 'geom2');
+drop table test cascade;
 
diff --git a/regress/estimatedextent_expected b/regress/estimatedextent_expected
index f51bedb61..5eb2f1516 100644
--- a/regress/estimatedextent_expected
+++ b/regress/estimatedextent_expected
@@ -39,3 +39,15 @@ WARNING:  stats for "p.g" do not exist
 #3391.19|0.00|1.00|0.00|1.00
 #3391.20|0.00|1.00|0.00|1.00
 NOTICE:  drop cascades to 2 other objects
+1.a null|
+1.b null|
+2.a null|
+2.b null|
+3.a null|
+3.b null|
+4.a box|BOX(-100 -100,100 100)
+4.b box|BOX(-200 -200,200 200)
+5.a bad-box|BOX(-100 -100,100 100)
+5.b bad-box|BOX(-200 -200,200 200)
+6.a null|
+6.b null|
-- 
2.40.0