From 1b06614bfdf5d91703cfa3ef166691feb0b5dda4 Mon Sep 17 00:00:00 2001
From: Ewan Young <kdbase.hack@gmail.com>
Date: Tue, 7 Jul 2026 23:40:30 +0800
Subject: [PATCH v2] Reject ill-formed range bounds histograms in stats import
 functions

pg_restore_attribute_stats() and pg_restore_extended_stats() (and their
pg_set_*_stats() counterparts) stored a STATISTIC_KIND_BOUNDS_HISTOGRAM
verbatim, without checking the invariant that ANALYZE's
compute_range_stats() guarantees: the histogram must not contain any
empty range, and its lower and upper bounds must each appear in ascending
order.  The range and multirange selectivity estimators rely on this.  An
unsorted histogram makes calc_length_hist_frac() fail an assertion (or
compute a nonsensical, possibly negative, selectivity on a non-assert
build), and an empty range trips a "shouldn't happen" elog(ERROR), when
the planner later reads the imported statistics.  For instance, after
importing an unsorted bounds histogram, a query such as "WHERE r <@ ..."
crashes the backend during planning.

Validate the bounds histogram at import time and reject an ill-formed one
with a WARNING, like other inconsistent inputs.  The check lives in
stat_utils.c so that both the per-attribute and the extended-statistics
import paths, which can both load a bounds histogram, can share it.  It
covers both range- and multirange-typed columns, whose bounds histograms
are both arrays of ranges.

This is the same class of problem as commit f6e4ec0a705, which rejected
oversized MCV lists in pg_restore_extended_stats().
---
 src/backend/statistics/attribute_stats.c      |  3 +-
 src/backend/statistics/extended_stats_funcs.c |  2 +-
 src/backend/statistics/stat_utils.c           | 88 +++++++++++++++++++
 src/include/statistics/stat_utils.h           |  2 +
 src/test/regress/expected/stats_import.out    | 56 ++++++++++++
 src/test/regress/sql/stats_import.sql         | 34 +++++++
 6 files changed, 183 insertions(+), 2 deletions(-)

diff --git a/src/backend/statistics/attribute_stats.c b/src/backend/statistics/attribute_stats.c
index 1cc4d657231..cb0375374b2 100644
--- a/src/backend/statistics/attribute_stats.c
+++ b/src/backend/statistics/attribute_stats.c
@@ -488,7 +488,8 @@ attribute_statistics_update(FunctionCallInfo fcinfo)
 											atttypid, atttypmod,
 											&converted);
 
-		if (converted)
+		if (converted &&
+			stats_check_bounds_histogram(stavalues))
 		{
 			statatt_set_slot(values, nulls, replaces,
 							 STATISTIC_KIND_BOUNDS_HISTOGRAM,
diff --git a/src/backend/statistics/extended_stats_funcs.c b/src/backend/statistics/extended_stats_funcs.c
index a5dce8a2206..f66e2360df4 100644
--- a/src/backend/statistics/extended_stats_funcs.c
+++ b/src/backend/statistics/extended_stats_funcs.c
@@ -1491,7 +1491,7 @@ import_pg_statistic(Relation pgsd, JsonbContainer *cont,
 								  extexprargname[RANGE_BOUNDS_HISTOGRAM_ELEM],
 								  &val_ok);
 
-		if (val_ok)
+		if (val_ok && stats_check_bounds_histogram(stavalues))
 			statatt_set_slot(values, nulls, replaces,
 							 STATISTIC_KIND_BOUNDS_HISTOGRAM,
 							 InvalidOid, InvalidOid,
diff --git a/src/backend/statistics/stat_utils.c b/src/backend/statistics/stat_utils.c
index 0b190e88237..3369ac2f170 100644
--- a/src/backend/statistics/stat_utils.c
+++ b/src/backend/statistics/stat_utils.c
@@ -33,6 +33,7 @@
 #include "utils/array.h"
 #include "utils/builtins.h"
 #include "utils/lsyscache.h"
+#include "utils/rangetypes.h"
 #include "utils/rel.h"
 #include "utils/syscache.h"
 #include "utils/typcache.h"
@@ -742,3 +743,90 @@ statatt_init_empty_tuple(Oid reloid, int16 attnum, bool inherited,
 		nulls[Anum_pg_statistic_stacoll1 + slotnum - 1] = false;
 	}
 }
+
+/*
+ * Check that an imported bounds histogram (STATISTIC_KIND_BOUNDS_HISTOGRAM) is
+ * well-formed the way ANALYZE builds it in compute_range_stats(): it must not
+ * contain any empty range, and both its lower and its upper bounds must appear
+ * in non-decreasing order.  The range and multirange selectivity estimators
+ * rely on this: they split the histogram into separate lower- and upper-bound
+ * histograms and assume each is sorted (e.g. calc_length_hist_frac() Asserts
+ * that successive bound distances do not decrease, and the estimator throws an
+ * internal error if it finds an empty range).  Importing an unsorted or
+ * empty-containing histogram would therefore crash the backend, or produce
+ * nonsensical estimates on non-assert builds, when the histogram is later read
+ * by the planner.  Reject such input with a WARNING, like other inconsistent
+ * inputs.
+ *
+ * This is shared between the per-attribute (pg_restore_attribute_stats()) and
+ * the extended-statistics (pg_restore_extended_stats()) import paths, both of
+ * which can load a bounds histogram.
+ *
+ * For both range- and multirange-typed columns the histogram is an array of
+ * ranges, so we take the range type from the array's element type.
+ */
+bool
+stats_check_bounds_histogram(Datum arrayval)
+{
+	ArrayType  *arr = DatumGetArrayTypeP(arrayval);
+	Oid			rngtypid = ARR_ELEMTYPE(arr);
+	TypeCacheEntry *typcache;
+	int16		elmlen;
+	bool		elmbyval;
+	char		elmalign;
+	Datum	   *elems;
+	bool	   *nulls;
+	int			nelems;
+	RangeBound	prev_lower = {0};
+	RangeBound	prev_upper = {0};
+
+	typcache = lookup_type_cache(rngtypid, TYPECACHE_RANGE_INFO);
+
+	/*
+	 * The element type should always be a range type here, but be defensive:
+	 * if it isn't, the bounds histogram is never consulted by the range
+	 * estimator, so there is nothing to verify.
+	 */
+	if (typcache->rngelemtype == NULL)
+		return true;
+
+	get_typlenbyvalalign(rngtypid, &elmlen, &elmbyval, &elmalign);
+	deconstruct_array(arr, rngtypid, elmlen, elmbyval, elmalign,
+					  &elems, &nulls, &nelems);
+
+	for (int i = 0; i < nelems; i++)
+	{
+		RangeBound	lower,
+					upper;
+		bool		empty;
+
+		/* NULL elements are already rejected by statatt_build_stavalues() */
+		range_deserialize(typcache, DatumGetRangeTypeP(elems[i]),
+						  &lower, &upper, &empty);
+
+		if (empty)
+		{
+			ereport(WARNING,
+					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+					 errmsg("\"%s\" must not contain empty ranges",
+							"range_bounds_histogram")));
+			return false;
+		}
+
+		if (i > 0 &&
+			(range_cmp_bounds(typcache, &lower, &prev_lower) < 0 ||
+			 range_cmp_bounds(typcache, &upper, &prev_upper) < 0))
+		{
+			ereport(WARNING,
+					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+					 errmsg("\"%s\" must have its lower and upper bounds sorted in ascending order",
+							"range_bounds_histogram")));
+			return false;
+		}
+
+		prev_lower = lower;
+		prev_upper = upper;
+	}
+
+	return true;
+}
diff --git a/src/include/statistics/stat_utils.h b/src/include/statistics/stat_utils.h
index 74da7790579..9f617a0f42b 100644
--- a/src/include/statistics/stat_utils.h
+++ b/src/include/statistics/stat_utils.h
@@ -58,4 +58,6 @@ extern Datum statatt_build_stavalues(const char *staname, FmgrInfo *array_in, Da
 extern bool statatt_get_elem_type(Oid atttypid, char atttyptype,
 								  Oid *elemtypid, Oid *elem_eq_opr);
 
+extern bool stats_check_bounds_histogram(Datum arrayval);
+
 #endif							/* STATS_UTILS_H */
diff --git a/src/test/regress/expected/stats_import.out b/src/test/regress/expected/stats_import.out
index bfdff77afa7..d4e5247b22a 100644
--- a/src/test/regress/expected/stats_import.out
+++ b/src/test/regress/expected/stats_import.out
@@ -1187,6 +1187,34 @@ AND attname = 'arange';
  stats_import | test      | arange  | f         |      0.29 |         0 |          0 |                  |                   |                  |             |                   |                        |                      | {399,499,Infinity}     |              0.5 | {"[-1,1)","[0,4)","[1,4)","[1,100)"}
 (1 row)
 
+-- warn: range bounds histogram whose bounds are not sorted ascending
+SELECT pg_catalog.pg_restore_attribute_stats(
+    'schemaname', 'stats_import',
+    'relname', 'test',
+    'attname', 'arange',
+    'inherited', false::boolean,
+    'range_bounds_histogram', '{"[50,60)","[1,2)","[90,100)","[5,6)"}'::text
+    );
+WARNING:  "range_bounds_histogram" must have its lower and upper bounds sorted in ascending order
+ pg_restore_attribute_stats 
+----------------------------
+ f
+(1 row)
+
+-- warn: range bounds histogram containing an empty range
+SELECT pg_catalog.pg_restore_attribute_stats(
+    'schemaname', 'stats_import',
+    'relname', 'test',
+    'attname', 'arange',
+    'inherited', false::boolean,
+    'range_bounds_histogram', '{empty,"[1,2)","[3,4)"}'::text
+    );
+WARNING:  "range_bounds_histogram" must not contain empty ranges
+ pg_restore_attribute_stats 
+----------------------------
+ f
+(1 row)
+
 -- warn: cannot set most_common_elems for range type, rest ok
 SELECT pg_catalog.pg_restore_attribute_stats(
     'schemaname', 'stats_import',
@@ -2358,6 +2386,34 @@ HINT:  "range_length_histogram", "range_empty_frac", and "range_bounds_histogram
  f
 (1 row)
 
+-- warn: range bounds histogram whose bounds are not sorted ascending
+SELECT pg_catalog.pg_restore_extended_stats(
+  'schemaname', 'stats_import',
+  'relname', 'test_mr',
+  'statistics_schemaname', 'stats_import',
+  'statistics_name', 'test_mr_stat',
+  'inherited', false,
+  'exprs', '[{"range_length_histogram": "{10179,10189,10199}", "range_empty_frac": "0", "range_bounds_histogram": "{\"[50,60)\",\"[1,2)\",\"[90,100)\"}"}]'::jsonb);
+WARNING:  "range_bounds_histogram" must have its lower and upper bounds sorted in ascending order
+ pg_restore_extended_stats 
+---------------------------
+ f
+(1 row)
+
+-- warn: range bounds histogram containing an empty range
+SELECT pg_catalog.pg_restore_extended_stats(
+  'schemaname', 'stats_import',
+  'relname', 'test_mr',
+  'statistics_schemaname', 'stats_import',
+  'statistics_name', 'test_mr_stat',
+  'inherited', false,
+  'exprs', '[{"range_length_histogram": "{10179,10189,10199}", "range_empty_frac": "0", "range_bounds_histogram": "{empty,\"[1,2)\",\"[3,4)\"}"}]'::jsonb);
+WARNING:  "range_bounds_histogram" must not contain empty ranges
+ pg_restore_extended_stats 
+---------------------------
+ f
+(1 row)
+
 -- ok: multirange stats
 SELECT pg_catalog.pg_restore_extended_stats(
   'schemaname', 'stats_import',
diff --git a/src/test/regress/sql/stats_import.sql b/src/test/regress/sql/stats_import.sql
index 58140315efb..e54f04ad638 100644
--- a/src/test/regress/sql/stats_import.sql
+++ b/src/test/regress/sql/stats_import.sql
@@ -885,6 +885,24 @@ AND tablename = 'test'
 AND inherited = false
 AND attname = 'arange';
 
+-- warn: range bounds histogram whose bounds are not sorted ascending
+SELECT pg_catalog.pg_restore_attribute_stats(
+    'schemaname', 'stats_import',
+    'relname', 'test',
+    'attname', 'arange',
+    'inherited', false::boolean,
+    'range_bounds_histogram', '{"[50,60)","[1,2)","[90,100)","[5,6)"}'::text
+    );
+
+-- warn: range bounds histogram containing an empty range
+SELECT pg_catalog.pg_restore_attribute_stats(
+    'schemaname', 'stats_import',
+    'relname', 'test',
+    'attname', 'arange',
+    'inherited', false::boolean,
+    'range_bounds_histogram', '{empty,"[1,2)","[3,4)"}'::text
+    );
+
 -- warn: cannot set most_common_elems for range type, rest ok
 SELECT pg_catalog.pg_restore_attribute_stats(
     'schemaname', 'stats_import',
@@ -1696,6 +1714,22 @@ SELECT pg_catalog.pg_restore_extended_stats(
   'statistics_name', 'test_mr_stat',
   'inherited', false,
   'exprs', '[{"range_bounds_histogram": "{\"[1,10200)\"}", "range_length_histogram": "{10179}"}]'::jsonb);
+-- warn: range bounds histogram whose bounds are not sorted ascending
+SELECT pg_catalog.pg_restore_extended_stats(
+  'schemaname', 'stats_import',
+  'relname', 'test_mr',
+  'statistics_schemaname', 'stats_import',
+  'statistics_name', 'test_mr_stat',
+  'inherited', false,
+  'exprs', '[{"range_length_histogram": "{10179,10189,10199}", "range_empty_frac": "0", "range_bounds_histogram": "{\"[50,60)\",\"[1,2)\",\"[90,100)\"}"}]'::jsonb);
+-- warn: range bounds histogram containing an empty range
+SELECT pg_catalog.pg_restore_extended_stats(
+  'schemaname', 'stats_import',
+  'relname', 'test_mr',
+  'statistics_schemaname', 'stats_import',
+  'statistics_name', 'test_mr_stat',
+  'inherited', false,
+  'exprs', '[{"range_length_histogram": "{10179,10189,10199}", "range_empty_frac": "0", "range_bounds_histogram": "{empty,\"[1,2)\",\"[3,4)\"}"}]'::jsonb);
 
 -- ok: multirange stats
 SELECT pg_catalog.pg_restore_extended_stats(
-- 
2.47.3

