NaN range lengths and 1e100-row estimates

Ruohang Feng (Vonng@PGSTY) · rh@vonng.com · 17 October 2026 · Patch proposed on pgsql-bugs, not committed

ANALYZE stores the result of the range subtype's subdiff function as the length of each range. For numeric that is NaN for some valid ranges, such as [1,NaN) and [Infinity,Infinity]. Once a NaN is in the length histogram, <@ and @> can get a NaN selectivity, and clamp_row_est() turns it into an estimate of 1e100 rows. Query results are correct, but plans built on these estimates can be very slow. No statistics import is involved: ordinary data and ANALYZE (or autovacuum) are enough.

Affected

<@ and @> on numrange; on nummultirange with a multirange, and @> with a range; float8-based range types. The code is from 9.3 (59d0bf9dca).

Effect

1e100-row estimates; in the join below, 2,000,000 index probes instead of 151, about 4 s instead of 65 ms.

Fix

get_len_position() returns 0.5 when either bin boundary is NaN, in the range and multirange code. One check with a comment in each file; histograms without NaN entries are not affected.

Tested

14, 18, 19rc1 and master on Linux x86_64; 18, 19 and master on macOS aarch64. Assertions enabled.

Reproducer

In a fresh database:

CREATE TABLE nan_len (id int PRIMARY KEY, r numrange);
INSERT INTO nan_len SELECT g, numrange(g, g + (g % 97) + 1)
  FROM generate_series(1, 1000) g;
INSERT INTO nan_len SELECT 1000 + g, numrange(g, 'NaN')
  FROM generate_series(1, 20) g;
ANALYZE nan_len;

EXPLAIN ANALYZE SELECT * FROM nan_len WHERE r <@ numrange(0, 200);
EXPLAIN ANALYZE SELECT * FROM nan_len WHERE r @> numrange(500, 510);

First plan line of each query on unpatched 19rc1; 14, 18 and master print the same estimates. EXPLAIN prints the row count in full, shortened here:

Seq Scan on nan_len  (cost=0.00..19.75 rows=1e100 width=19) (actual time=0.570..1.037 rows=151.00 loops=1)
Seq Scan on nan_len  (cost=0.00..19.75 rows=1e100 width=19) (actual time=0.216..0.396 rows=60.00 loops=1)

The table has 1,020 rows. The length histogram ANALYZE built ends in …, 95, 96, 97, NaN, NaN}.

Other inputs

Estimates before and after the patch, with the same data. The numbers are the same on 18, 19rc1 and master. The fixtures are in the appendix.

[Infinity,Infinity] is a nonempty range whose bounds are the value Infinity, not unbounded, so ANALYZE calls subdiff and gets Infinity − Infinity = NaN. An unbounded range such as numrange(g, NULL) gets the length Infinity without calling subdiff, and does not trigger the problem. The multirange <@ range estimate is too high without NaN being involved, and the patch does not change it.

Plan impact

Join the table from the reproducer to a 2M-row table with an index on the join key:

-- Run after the reproducer.  Creates two million rows.
CREATE TABLE fact (dim_id int, payload text);
INSERT INTO fact SELECT (g % 1020) + 1, repeat('x', 50)
  FROM generate_series(1, 2000000) g;
CREATE INDEX ON fact (dim_id);
VACUUM ANALYZE fact;

SET max_parallel_workers_per_gather = 0;
EXPLAIN ANALYZE
SELECT count(*) FROM nan_len d JOIN fact f ON f.dim_id = d.id
WHERE d.r <@ numrange(0, 200);

Unpatched (abridged, 19rc1):

Aggregate  (actual rows=1.00 loops=1)
  ->  Nested Loop  (rows=1e100) (actual rows=296110.00 loops=1)
        ->  Index Only Scan using fact_dim_id_idx on fact f  (rows=2000000) (actual rows=2000000.00 loops=1)
        ->  Index Scan using nan_len_pkey on nan_len d  (rows=1e100) (actual rows=0.15 loops=2000000)
Execution Time: 3980.020 ms

Patched, same data and statistics:

Aggregate  (actual rows=1.00 loops=1)
  ->  Nested Loop  (rows=329412) (actual rows=296110.00 loops=1)
        ->  Seq Scan on nan_len d  (rows=168) (actual rows=151.00 loops=1)
        ->  Index Only Scan using fact_dim_id_idx on fact f  (rows=1961) (actual rows=1960.99 loops=151)
Execution Time: 61.025 ms

Single runs, assert-enabled builds, max_parallel_workers_per_gather = 0. Both plans return the same count, 296110. The timings show the size of the effect on one machine; they are not a comparison between versions or platforms.

Cause

1. compute_range_stats() (rangetypes_typanalyze.c) stores subdiff(upper, lower) as the length of each bounded range, without checking it. numrange_subdiff() returns NaN for a NaN bound and for Infinity − Infinity. The built-in integer, date and timestamp range types cannot produce NaN.
2. The lengths are sorted with float8_qsort_cmp(), which uses plain C comparisons and so reports “greater” whenever either argument is NaN. That is not a consistent order, and NaN entries can end up anywhere in the array. Most land at the end, and the last element is always kept in the histogram.
3. length_hist_bsearch() returns the last entry less than the searched length. NaN < x is false, so it can stop on a bin whose upper boundary is NaN.
4. get_len_position() interpolates in that bin:

   if (!isinf(hist1) && !isinf(hist2))
   {
       if (isinf(value))
           return 0.5;
   
       return 1.0 - (hist2 - value) / (hist2 - hist1);    /* NaN */
   }

   calc_length_hist_frac() then returns NaN, and so does the selectivity of <@ and @>.
5. CLAMP_PROBABILITY() tests p < 0.0 and p > 1.0, both false for NaN, so NaN passes. So does the range check in restriction_selectivity().
6. clamp_row_est() maps a NaN row count to MAXIMUM_ROWCOUNT, 1e100.

Commit 652686a334 (2020, bug #16122, back-patched to all branches then supported) made get_position() and get_distance() punt on NaN from subdiff for the bounds histogram. The length histogram side never got the same treatment.

Fix

The production code change, identical in rangetypes_selfuncs.c and multirangetypes_selfuncs.c:

 static double
 get_len_position(double value, double hist1, double hist2)
 {
+	/*+	 * ANALYZE stores whatever the subtype's subdiff function returns as the+	 * range length, and that can be NaN for valid ranges, such as numeric+	 * ranges with a NaN bound or [Infinity,Infinity].  We can't interpolate+	 * in a bin with a NaN boundary, so just assume the middle.+	 */+	if (isnan(hist1) || isnan(hist2))+		return 0.5;+ 	if (!isinf(hist1) && !isinf(hist2))
 	{
 		/*

The patch also adds a regression test to rangetypes.sql. It builds a numrange table with NaN-bound and [Infinity,Infinity] rows and a nummultirange copy, checks that the length histogram contains NaN, and checks that four <@/@> estimates do not exceed the row count. All four estimate checks fail without the C change.

Why this is enough

• It is the only place that can see a NaN. get_len_position() is where calc_length_hist_frac() does arithmetic on histogram entries. Its other use of them is the loop over the bins, which compares bin_upper < length2; that comparison is false for NaN, so the loop stops at a NaN entry. The lower boundary of the first bin is never NaN, because the binary search only stops on an entry that compared less than the searched length. It can be NaN in the last bin, when the search falls before the first entry and the histogram starts with NaN. Hence both boundaries are checked.
• Nothing else can become NaN. Without the NaN entries, an ANALYZE-built histogram is still sorted. sort_template.h compares elements only with the pivot during partitioning, and with a neighbour during insertion sort. A non-NaN pivot places the non-NaN values on the correct side; a NaN pivot sends everything else to one side; insertion sort never moves a value past a smaller non-NaN one. A sorted histogram cannot produce Infinity − Infinity or a zero-width bin in this code.
• Measured. On 60 ANALYZE-built tables (numrange, nummultirange and a float8 range; NaN rows, [Infinity,Infinity] rows and unbounded rows; statistics targets 10 to 300; NaN entries at the start, in the middle and at the end of the histogram), 229 of 720 <@ and @> estimates were 1e100 without the patch and none with it. On 19rc1, a more defensive variant that also clamps the interpolated position and the final fraction gave the same estimate for all 720 queries.

What does not change

• Histograms without NaN entries. The new branch is never taken. 400 random <@, @> and && queries over int4range, numrange, daterange, tstzrange, int4multirange and int4range with unbounded values gave identical estimates with and without the patch.
• Existing statistics. Nothing in the catalog changes, and no new ANALYZE is needed. The before/after numbers in this report come from the same data directory, started first with the unpatched and then with the patched binary; a hash of the fixtures' pg_stats rows was identical.
• ANALYZE, sorting and statistics import. These are untouched. The patch handles histograms as ANALYZE builds them; it does not try to validate length histograms supplied by hand through pg_restore_attribute_stats().

0.5 is a fallback, not an estimate of the true position. Apart from the 229 cases that went from 1e100 to a finite value, 62 estimates changed that had been finite but were still computed from NaN intermediate values. 52 of these moved closer to the actual row count and 10 moved further away.

Testing

Linux: gcc 13.3, --enable-cassert --enable-debug, core suite via installcheck-parallel. macOS: Apple clang 21.0.0, assertions enabled, make check, run with an earlier revision of this patch that has the same code change and different comments and tests. No assertion failures anywhere.
¹ C change only; the test's context differs in 14–16, and it reads pg_stats.range_length_histogram, which exists from 17, so on 14 the same checks were run against pg_statistic.
² Six estimate checks of the earlier test revision. The macOS builds gave the same estimates as Linux for the reproducer and for the fixtures they covered.

The C part of the patch applies without changes to REL_14_STABLE through master.

Patch

v1, against master 45fc51fcbf. Attached to the pgsql-bugs report.

From 1e0c07b24591c96f80c0a8e9f99bdd83d628402f Mon Sep 17 00:00:00 2001
From: Ruohang Feng <rh@vonng.com>
Date: Sat, 17 Oct 2026 23:41:40 +0800
Subject: [PATCH v1] Avoid NaN estimates from NaN entries in range length
 histograms
 
ANALYZE stores the result of the range subtype's subdiff function as
the length of each range, and that can be NaN for valid ranges: numeric
returns NaN for a NaN bound and for Infinity minus Infinity, so for
example [1,NaN) and [Infinity,Infinity] get a NaN length.  If such an
entry becomes a boundary of the length histogram bin that
calc_length_hist_frac() interpolates in, get_len_position() returns
NaN, and so does the selectivity of <@ and @>.  CLAMP_PROBABILITY()
lets NaN through, and clamp_row_est() turns it into a 1e100 row
estimate, which can lead to very poor plans.
 
Make get_len_position() return 0.5 when either bin boundary is NaN,
much like get_position() punts on an indeterminate position in the
bounds histogram since 652686a334.  Nothing changes for histograms
without NaN entries.  The multirange code has a copy of the same
function and gets the same fix.
---
 .../utils/adt/multirangetypes_selfuncs.c      |  9 +++
 src/backend/utils/adt/rangetypes_selfuncs.c   |  9 +++
 src/test/regress/expected/rangetypes.out      | 63 +++++++++++++++++++
 src/test/regress/sql/rangetypes.sql           | 39 ++++++++++++
 4 files changed, 120 insertions(+)
 
diff --git a/src/backend/utils/adt/multirangetypes_selfuncs.c b/src/backend/utils/adt/multirangetypes_selfuncs.c
index 533111445e..136e6a3bc3 100644
--- a/src/backend/utils/adt/multirangetypes_selfuncs.c
+++ b/src/backend/utils/adt/multirangetypes_selfuncs.c
@@ -872,6 +872,15 @@ get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound
 static double
 get_len_position(double value, double hist1, double hist2)
 {
+	/*+	 * ANALYZE stores whatever the subtype's subdiff function returns as the+	 * range length, and that can be NaN for valid ranges, such as numeric+	 * ranges with a NaN bound or [Infinity,Infinity].  We can't interpolate+	 * in a bin with a NaN boundary, so just assume the middle.+	 */+	if (isnan(hist1) || isnan(hist2))+		return 0.5;+ 	if (!isinf(hist1) && !isinf(hist2))
 	{
 		/*
diff --git a/src/backend/utils/adt/rangetypes_selfuncs.c b/src/backend/utils/adt/rangetypes_selfuncs.c
index 75f1e7567d..11e5e09cc2 100644
--- a/src/backend/utils/adt/rangetypes_selfuncs.c
+++ b/src/backend/utils/adt/rangetypes_selfuncs.c
@@ -761,6 +761,15 @@ get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound
 static double
 get_len_position(double value, double hist1, double hist2)
 {
+	/*+	 * ANALYZE stores whatever the subtype's subdiff function returns as the+	 * range length, and that can be NaN for valid ranges, such as numeric+	 * ranges with a NaN bound or [Infinity,Infinity].  We can't interpolate+	 * in a bin with a NaN boundary, so just assume the middle.+	 */+	if (isnan(hist1) || isnan(hist2))+		return 0.5;+ 	if (!isinf(hist1) && !isinf(hist2))
 	{
 		/*
diff --git a/src/test/regress/expected/rangetypes.out b/src/test/regress/expected/rangetypes.out
index fb1bb30b7e..dd360e0f9f 100644
--- a/src/test/regress/expected/rangetypes.out
+++ b/src/test/regress/expected/rangetypes.out
@@ -2048,3 +2048,66 @@ select * from text_support_test where t <@ textrange_supp('a', 'd');
 
 drop table text_support_test;
 drop type textrange_supp;
+--+-- ANALYZE stores NaN as the length of ranges whose subdiff is NaN, such as+-- numeric ranges with a NaN bound or [Infinity,Infinity].  Check that NaN+-- entries in the length histogram don't produce bogus row estimates.+--+create function range_explain_rows(query text) returns float8+language plpgsql as+$$+declare+  plan json;+begin+  execute 'explain (format json) ' || query into plan;+  return (plan->0->'Plan'->>'Plan Rows')::float8;+end;+$$;+create table numrange_nan_len (nr numrange);+alter table numrange_nan_len alter column nr set statistics 100;+insert into numrange_nan_len+  select numrange(g, g + (g % 97) + 1) from generate_series(1, 1000) g;+insert into numrange_nan_len+  select numrange(g, 'NaN') from generate_series(1, 10) g;+insert into numrange_nan_len+  select '[Infinity,Infinity]' from generate_series(1, 10);+analyze numrange_nan_len;+select count(*) > 0 as has_nan+  from pg_stats, unnest(range_length_histogram::text::float8[]) v+  where schemaname = current_schema() and tablename = 'numrange_nan_len'+    and v = 'NaN'::float8;+ has_nan +---------+ t+(1 row)++select range_explain_rows('select * from numrange_nan_len where nr <@ numrange(0, 200)') <= 1020 as sane;+ sane +------+ t+(1 row)++select range_explain_rows('select * from numrange_nan_len where nr @> numrange(500, 510)') <= 1020 as sane;+ sane +------+ t+(1 row)++create table nummultirange_nan_len (nmr nummultirange);+alter table nummultirange_nan_len alter column nmr set statistics 100;+insert into nummultirange_nan_len select nummultirange(nr) from numrange_nan_len;+analyze nummultirange_nan_len;+select range_explain_rows('select * from nummultirange_nan_len where nmr <@ nummultirange(numrange(0, 200))') <= 1020 as sane;+ sane +------+ t+(1 row)++select range_explain_rows('select * from nummultirange_nan_len where nmr @> nummultirange(numrange(500, 510))') <= 1020 as sane;+ sane +------+ t+(1 row)++drop table numrange_nan_len, nummultirange_nan_len;+drop function range_explain_rows(text);diff --git a/src/test/regress/sql/rangetypes.sql b/src/test/regress/sql/rangetypes.sql
index e4062c3e6a..c5e0d8b21a 100644
--- a/src/test/regress/sql/rangetypes.sql
+++ b/src/test/regress/sql/rangetypes.sql
@@ -722,3 +722,42 @@ select * from text_support_test where t <@ textrange_supp('a', 'd');
 drop table text_support_test;
 
 drop type textrange_supp;
++--+-- ANALYZE stores NaN as the length of ranges whose subdiff is NaN, such as+-- numeric ranges with a NaN bound or [Infinity,Infinity].  Check that NaN+-- entries in the length histogram don't produce bogus row estimates.+--+create function range_explain_rows(query text) returns float8+language plpgsql as+$$+declare+  plan json;+begin+  execute 'explain (format json) ' || query into plan;+  return (plan->0->'Plan'->>'Plan Rows')::float8;+end;+$$;+create table numrange_nan_len (nr numrange);+alter table numrange_nan_len alter column nr set statistics 100;+insert into numrange_nan_len+  select numrange(g, g + (g % 97) + 1) from generate_series(1, 1000) g;+insert into numrange_nan_len+  select numrange(g, 'NaN') from generate_series(1, 10) g;+insert into numrange_nan_len+  select '[Infinity,Infinity]' from generate_series(1, 10);+analyze numrange_nan_len;+select count(*) > 0 as has_nan+  from pg_stats, unnest(range_length_histogram::text::float8[]) v+  where schemaname = current_schema() and tablename = 'numrange_nan_len'+    and v = 'NaN'::float8;+select range_explain_rows('select * from numrange_nan_len where nr <@ numrange(0, 200)') <= 1020 as sane;+select range_explain_rows('select * from numrange_nan_len where nr @> numrange(500, 510)') <= 1020 as sane;+create table nummultirange_nan_len (nmr nummultirange);+alter table nummultirange_nan_len alter column nmr set statistics 100;+insert into nummultirange_nan_len select nummultirange(nr) from numrange_nan_len;+analyze nummultirange_nan_len;+select range_explain_rows('select * from nummultirange_nan_len where nmr <@ nummultirange(numrange(0, 200))') <= 1020 as sane;+select range_explain_rows('select * from nummultirange_nan_len where nmr @> nummultirange(numrange(500, 510))') <= 1020 as sane;+drop table numrange_nan_len, nummultirange_nan_len;+drop function range_explain_rows(text); 
base-commit: 45fc51fcbf4534ea2f6f85e36f8155dbd5ba9851
-- 
2.43.0

-- Run after the reproducer, in the same database.
CREATE TABLE nm AS SELECT nummultirange(r) AS r FROM nan_len;
ANALYZE nm;

CREATE TABLE numeric_inf AS
  SELECT numrange(g, g + (g % 97) + 1) AS r FROM generate_series(1, 1000) g;
INSERT INTO numeric_inf
  SELECT '[Infinity,Infinity]'::numrange FROM generate_series(1, 20);
ANALYZE numeric_inf;

CREATE TYPE floatrange AS RANGE (subtype = float8, subtype_diff = float8mi);
CREATE TABLE float_inf AS
  SELECT floatrange(g, g + (g % 13) + 1) AS r FROM generate_series(1, 500) g;
INSERT INTO float_inf
  SELECT '[Infinity,Infinity]'::floatrange FROM generate_series(1, 20);
ANALYZE float_inf;

CREATE TABLE numeric_unbounded AS
  SELECT numrange(g, g + (g % 97) + 1) AS r FROM generate_series(1, 1000) g;
INSERT INTO numeric_unbounded
  SELECT numrange(g, NULL) FROM generate_series(1, 20) g;
ANALYZE numeric_unbounded;

CREATE TABLE numeric_large AS
  SELECT numrange(g::numeric * 1e304, (g + (g % 97) + 1)::numeric * 1e304) AS r
  FROM generate_series(1, 1000) g;
ANALYZE numeric_large;

EXPLAIN ANALYZE SELECT * FROM nm WHERE r <@ nummultirange(numrange(0, 200));
EXPLAIN ANALYZE SELECT * FROM nm WHERE r @> nummultirange(numrange(500, 510));
EXPLAIN ANALYZE SELECT * FROM nm WHERE r @> numrange(500, 510);
EXPLAIN ANALYZE SELECT * FROM numeric_inf WHERE r <@ numrange(0, 200);
EXPLAIN ANALYZE SELECT * FROM numeric_inf WHERE r @> numrange(500, 510);
EXPLAIN ANALYZE SELECT * FROM float_inf WHERE r <@ floatrange(0, 100);
EXPLAIN ANALYZE SELECT * FROM float_inf WHERE r @> floatrange(200, 201);
EXPLAIN ANALYZE SELECT * FROM nm WHERE r <@ numrange(0, 200);
EXPLAIN ANALYZE SELECT * FROM numeric_unbounded WHERE r <@ numrange(0, 200);
EXPLAIN ANALYZE SELECT * FROM numeric_large WHERE r <@ numrange(0, 2e306);
EXPLAIN ANALYZE SELECT * FROM numeric_large WHERE r @> numrange(5e306, 5.1e306);

References

• 59d0bf9dca, Add cost estimation of range @> and <@ operators (9.3)
• 652686a334, Fix edge-case crashes and misestimation in range containment selectivity (2020)
• BUG #16122 on pgsql-bugs
• Numeric types: NaN and Infinity in numeric
• Range types: infinite (unbounded) ranges and defining new range types