BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
The following bug has been logged on the website:
Bug reference: 19705
Logged by: Ke
Email address: kehan5800@gmail.com
PostgreSQL version: 18.6
Operating system: Ubuntu 22.04.2 x86_64
Description:
Summary
-------
A single box value with a NaN coordinate, stored anywhere in a table, makes
a
BRIN box_inclusion_ops index stop returning rows that have nothing to do
with
it. The rows that disappear contain no NaN, and the queries that lose them
mention no NaN. There is no error and nothing unusual in the plan; the count
is
simply smaller than the heap says it should be.
The loss is one BRIN page range per NaN row. With the default
pages_per_range = 128 that is up to 128 pages of ordinary rows made
invisible
by one unrelated value.
Minimal case (fresh database, initdb defaults, nothing set but
enable_seqscan
to force the two plans to be compared):
CREATE TABLE b (v box);
INSERT INTO b SELECT box '(0,0),(1,1)' FROM generate_series(1, 1000);
INSERT INTO b VALUES (box '(NaN,NaN),(0,0)'); -- one row
CREATE INDEX bi ON b USING brin (v);
SELECT count(*) FROM b WHERE v && box '(-2,-2),(2,2)'; -- 1000
SET enable_seqscan = off;
SELECT count(*) FROM b WHERE v && box '(-2,-2),(2,2)'; -- 0
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) of the
second one:
Aggregate (actual rows=1.00 loops=1)
-> Bitmap Heap Scan on b (actual rows=0.00 loops=1)
Recheck Cond: (v && '(2,2),(-2,-2)'::box)
-> Bitmap Index Scan on bi (actual rows=0.00 loops=1)
Index Cond: (v && '(2,2),(-2,-2)'::box)
Index Searches: 1
Every strategy in the opclass behaves the same way on that table (seq scan
first, BRIN second):
v && box '(-2,-2),(2,2)' 1000 / 0
v @> point '(0,0)' 1000 / 0
v @> box '(0,0),(0,0)' 1000 / 0
v ~= box '(0,0),(1,1)' 1000 / 0
Deleting the NaN row and reindexing restores the correct answers.
What I expected
---------------
The same answer with and without the index. An index may hand back extra
rows
for the recheck above it to drop; it may not hand back fewer rows than the
predicate selects.
Why it happens
--------------
BRIN's inclusion framework summarises a page range with the union of the
values
on it and, at scan time, asks the strategy operator whether that summary
could
match the query, skipping the range if it could not. That is sound only
while
the summary is a true superset of the range's contents.
For box the two halves use different NaN conventions:
* The union, amproc 11 = boxes_bound_box() in
src/backend/utils/adt/geo_ops.c,
is computed with float8_max()/float8_min() from
src/include/utils/float.h.
Those follow the float8 convention, in which NaN is larger than
everything.
So a NaN corner propagates into the union and becomes its high corner.
* The consistent side, brin_inclusion_consistent() calling box_overlap(),
box_contain() and friends, is computed with the FPlt/FPle/FPgt/FPge
macros
in src/include/utils/geo_decls.h. Those are plain C comparisons with an
epsilon, under which every comparison with a NaN is false.
Put together, the union of one ordinary box and one NaN box is a box that
overlaps nothing -- not even the boxes it was built from:
SELECT bound_box(box '(0,0),(1,1)', box '(NaN,NaN),(0,0)') AS
u,
bound_box(box '(0,0),(1,1)', box '(NaN,NaN),(0,0)') @> box
'(0,0),(1,1)',
bound_box(box '(0,0),(1,1)', box '(NaN,NaN),(0,0)') && box
'(0,0),(1,1)';
u | ?column? | ?column?
----------------+----------+----------
(NaN,NaN),(0,0) | f | f
and that is exactly what gets stored as the range summary (pageinspect on
the
minimal case above):
SELECT blknum, value FROM brin_page_items(get_raw_page('bi', 2),
'bi'::regclass);
blknum | value
-------+-----------------------------
0 | {(NaN,NaN),(0,0) .. f .. f}
brin_inclusion_consistent() then correctly concludes that this summary
cannot
match the query and skips the range. The consistency function is doing its
job;
the summary is the lie.
The framework already has the escape hatch for values that cannot be merged
into a bounding value -- the INCLUSION_UNMERGEABLE flag, set when the
optional
support function PROCNUM_MERGEABLE (amproc 12) says two values cannot be
merged. A range marked unmergeable is always scanned. box_inclusion_ops does
not have that function:
opfname | amprocnum | amproc
----------------------+-----------+---------------------------
box_inclusion_ops | 11 | bound_box
box_inclusion_ops | 13 | box_contain
network_inclusion_ops | 11 | inet_merge
network_inclusion_ops | 12 | inet_same_family <-- the hatch
network_inclusion_ops | 13 | network_supeq
inet gets this right for the analogous case (an IPv6 address among IPv4
addresses, where no meaningful union exists) and box does not, which is why
inet is unaffected and box is not.
What else I measured
--------------------
* Not only the build path. Insert the NaN row after CREATE INDEX and let
brin_summarize_new_values() fold it into the summary: 4896 of 5000 rows
(pages_per_range = 1, so one page lost).
* Parallel index build: 382976 of 400000 rows.
* Order does not matter: NaN row first or last, same result.
* NaN specifically, not non-finite generally. The same table with
box '(Infinity,Infinity),(0,0)' instead returns 5001 of 5001. float8_max
/
float8_min and the FP* macros agree about infinities; they disagree only
about NaN.
* One NaN coordinate out of the four is enough.
* Realistic shape, 1,000,000 rows of box(point(g,g), point(g+1,g+1)) plus
one
NaN row, default pages_per_range = 128: 1 of 58 ranges is poisoned, and
a
query whose rows live in that range returns 0 where the heap has 102. At
this scale the wrong answer is plausible rather than obviously empty,
which
is what makes it worth reporting.
* Other BRIN opclasses on the same shape of data are fine: float8 minmax
with
a NaN among 3000 finite values returns 3000 = 3000 (it compares with
float8_lt/float8_gt, which know about NaN), and inet inclusion with a
::1
among 3000 IPv4 addresses returns 3000 = 3000 (amproc 12).
* The NaN row itself is also lost, not just its neighbours: v ~= box
'(NaN,NaN),(0,0)' finds it on a seq scan -- box_same routes through
float8_eq, where NaN = NaN is true -- and finds nothing through BRIN.
* The same disagreement is visible on GiST, at smaller blast radius: the
same 5001-row table loses roughly a leaf page's worth through a GiST
index
-- I have measured 4835, 4839, 4876 and 4897 of 5000 across four builds,
the exact figure depending on page packing -- and 5000 of 5000 through
SP-GiST. gistproc.c's rt_box_union() was already converted to
float8_max/float8_min by 1acf7572554, so GiST's union is NaN-propagating
in the same way, and it loses rows for the same reason: the search side
still uses the epsilon macros. I am reporting the BRIN case because
there
the unit of loss is a whole page range and because BRIN has the
ready-made
fix below, but the two are one defect.
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi,
I can reproduce this on master, and your analysis is right. bound_box()
lets the NaN into the range summary, and then every box operator says
the range cannot match.
You suggested adding a mergeable support function, like inet has. That
works, but it needs a new pg_amproc row, so it cannot go to the back
branches. The same code is in 14 and later.
0002 adds tests and is optional.
Thanks,
I can reproduce this on master, and your analysis is right. bound_box()
lets the NaN into the range summary, and then every box operator says
the range cannot match.
You suggested adding a mergeable support function, like inet has. That
works, but it needs a new pg_amproc row, so it cannot go to the back
branches. The same code is in 14 and later.
The attached 0001 fixes bound_box() instead. When an input coordinate is
NaN, the result is infinite on that side. The summary then matches any
query on that axis and the recheck does the rest. Only the NaN axis
becomes lossy, the other axis still prunes.
NaN, the result is infinite on that side. The summary then matches any
query on that axis and the recheck does the rest. Only the NaN axis
becomes lossy, the other axis still prunes.
Existing summaries that hold a NaN stay broken until REINDEX.
0002 adds tests and is optional.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi!
I think your fix is basically correct and comes in sync with previous
fix of this kind [0]
Your 0001 makes the BRIN symptom go away, including on the back branches.
A few observations and an alternative (your 0001 adjusted) I have been
working on (PFA)
On Tue, 22 Sept 2026 at 04:50, shihao zhong wrote:
>
> Hi,
>
> I can reproduce this on master, and your analysis is right. bound_box()
> lets the NaN into the range summary, and then every box operator says
> the range cannot match.
>
> You suggested adding a mergeable support function, like inet has. That
> works, but it needs a new pg_amproc row, so it cannot go to the back
> branches. The same code is in 14 and later.
Yes, but for HEAD it's OK and will be an idiomatic way to fix. So, we
can make different patches for HEAD and back branches, where the
back-branched version will miss pg_amproc fix (and misbehave on index
scan, but looks like we can live with that). Example:
CREATE TABLE b (v box);
INSERT INTO b SELECT box '(0,0),(1,1)' FROM generate_series(1, 1000);
INSERT INTO b VALUES (box '(NaN,NaN),(0,0)');
CREATE INDEX bi ON b USING brin (v);
SET enable_seqscan = off;
SELECT count(*) FROM b WHERE v && box '(-2,-2),(2,2)'; -- seq: 1000
SELECT count(*) FROM b WHERE v @> point '(0.5,0.5)'; -- seq: 1000
SELECT count(*) FROM b WHERE v ~= box '(0,0),(1,1)'; -- seq: 1000
SELECT count(*) FROM b WHERE v ~= box '(NaN,NaN),(0,0)'; -- seq:
1 (your v1 will return 0)
> The attached 0001 fixes bound_box() instead. When an input coordinate is
> NaN, the result is infinite on that side. The summary then matches any
> query on that axis and the recheck does the rest. Only the NaN axis
> becomes lossy, the other axis still prunes.
>
> Existing summaries that hold a NaN stay broken until REINDEX.
>
> 0002 adds tests and is optional.
>
> Thanks,
> Shihao
>
>
As the reporter already measured, GiST has the same defect, so 0002
fixes that too.
The GiST issue is in fallbackSplit(), gist_box_picksplit etc build the
groups union keys by copying the first entry
as-is `*leftBox = *box` and then growing the copy, so a NaN box placed
first in its group produces a NaN key. To fix this, there is a small
NaN-aware copy helper function. Also, adjustBoxnow uses two NaN-aware
helper functions, so they replace NaN with inf values too. This is
what makes the NaN keys not propagate to the root on the insert path.
Note that this efficiently means we will insert different tuples in
index (without NaNs but with Inf). See gist_page_items output for
reference.
GiST index failing test case is the same:
db2=#
CREATE TABLE b (v box);
INSERT INTO b SELECT box '(0,0),(1,1)' FROM generate_series(1, 1000);
INSERT INTO b VALUES (box '(NaN,NaN),(0,0)'); -- one row
CREATE TABLE
INSERT 0 1000
INSERT 0 1
db2=# CREATE INDEX bi ON b USING gist (v);
CREATE INDEX
db2=# select count(*) from b where v && box(point(1,1), point(4,4));
count
-------
835
(1 row)
db2=# drop index bi;
DROP INDEX
db2=# select count(*) from b where v && box(point(1,1), point(4,4));
count
-------
1000
(1 row)
before/after 0002 with pageinspect.
```
db2=# SELECT * FROM gist_page_items(get_raw_page('gist_nan_tbl_index',
0), 'gist_nan_tbl_index');
itemoffset | ctid | itemlen | dead | keys
------------+------------+---------+------+-----------------------------
1 | (1,65535) | 40 | f | (b)=("(82,82),(0,0)")
2 | (2,65535) | 40 | f | (b)=("(165,165),(83,83)")
3 | (3,65535) | 40 | f | (b)=("(NaN,NaN),(0,0)")
4 | (4,65535) | 40 | f | (b)=("(331,331),(249,249)")
5 | (5,65535) | 40 | f | (b)=("(414,414),(332,332)")
6 | (6,65535) | 40 | f | (b)=("(497,497),(415,415)")
7 | (7,65535) | 40 | f | (b)=("(580,580),(498,498)")
8 | (8,65535) | 40 | f | (b)=("(663,663),(581,581)")
9 | (9,65535) | 40 | f | (b)=("(746,746),(664,664)")
10 | (10,65535) | 40 | f | (b)=("(829,829),(747,747)")
11 | (11,65535) | 40 | f | (b)=("(912,912),(830,830)")
12 | (12,65535) | 40 | f | (b)=("(999,999),(913,913)")
```
```
reshke=# SELECT * FROM
gist_page_items(get_raw_page('gist_nan_tbl_index', 0),
'gist_nan_tbl_index');
itemoffset | ctid | itemlen | dead | keys
------------+------------+---------+------+-----------------------------------
1 | (1,65535) | 40 | f | (b)=("(Infinity,Infinity),(0,0)")
2 | (2,65535) | 40 | f | (b)=("(165,165),(83,83)")
3 | (3,65535) | 40 | f | (b)=("(248,248),(166,166)")
4 | (4,65535) | 40 | f | (b)=("(331,331),(249,249)")
5 | (5,65535) | 40 | f | (b)=("(414,414),(332,332)")
6 | (6,65535) | 40 | f | (b)=("(497,497),(415,415)")
7 | (7,65535) | 40 | f | (b)=("(580,580),(498,498)")
8 | (8,65535) | 40 | f | (b)=("(663,663),(581,581)")
9 | (9,65535) | 40 | f | (b)=("(746,746),(664,664)")
10 | (10,65535) | 40 | f | (b)=("(829,829),(747,747)")
11 | (11,65535) | 40 | f | (b)=("(912,912),(830,830)")
12 | (12,65535) | 40 | f | (b)=("(999,999),(913,913)")
(12 rows)
```
GiST indexes obviously need to be REINDEX-ed after that.
[0] https://github.com/postgres/postgres/commit/1acf7572554
--
Best regards,
Kirill Reshke
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
Andrey Borodin <x4mmm@yandex-team.ru>
Дата:
On 22 Sep 2026, Kirill Reshke wrote:
> Yes, but for HEAD it's OK and will be an idiomatic way to fix.
I found two false negatives with v2, on fresh indexes.
1. A BRIN range containing just one non-NULL NaN box never calls
box_mergeable(). brin_inclusion_add_value() copies the first value and
returns at "if (new)", leaving INCLUSION_UNMERGEABLE false:
CREATE TABLE b (v box);
INSERT INTO b VALUES ('(NaN,NaN),(0,0)');
CREATE INDEX bi ON b USING brin (v);
SET enable_seqscan = off;
SELECT * FROM b WHERE v ~= box '(NaN,NaN),(0,0)';
This returns no rows, versus one with a seq scan. Adding a finite box
to the range makes the NaN row findable. We need to cover the initial
value too, not just merges.
2. GiST still loses the NaN row for the same equality predicate. With
1000 finite boxes and one NaN box, I get one row via seq scan and none
via GiST. rtree_internal_consistent() implements RTSameStrategyNumber
using box_contain(), which rejects a NaN query even when the stored
bound is infinite.
Thank you!
Best regards, Andrey Borodin.
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi Andrey,
> I found two false negatives with v2, on fresh indexes.
Thanks, I reproduced both. v3 attached. 0001 is Kirill's v2 unchanged,
0002 fixes your cases, with tests that fail without it.
1. BRIN now asks the mergeable function about the first value too, by
merging it with itself. No change for inet.
2. GiST internal pages no longer prune ~= when the query has a NaN.
There is nothing safe to compare it with.
0002 also stops gist_box_union() from copying a NaN first entry.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
Kirill Reshke <reshkekirill@gmail.com>
Дата:
On Wed, 23 Sept 2026 at 08:43, shihao zhong wrote: > > Hi Andrey, > > I found two false negatives with v2, on fresh indexes. > > Thanks, I reproduced both. v3 attached. 0001 is Kirill's v2 unchanged, > 0002 fixes your cases, with tests that fail without it. > > 1. BRIN now asks the mergeable function about the first value too, by > merging it with itself. No change for inet. > > 2. GiST internal pages no longer prune ~= when the query has a NaN. > There is nothing safe to compare it with. > > 0002 also stops gist_box_union() from copying a NaN first entry. > > Thanks, > Shihao > Cool, thanks for v3. I think that addition to brin_inclusion_add_value is correct but looks like we need the same guard for brin_inclusion_consistent? Also, maybe it is worth making two patches here, one for BRIN and other for GiST for sake of simplicity. I also think that we can avoid rebuilding indexes after fix here, only lose selectivity on the poisoned subtrees. Looks like an internal key carrying a NaN should match every strategy. So, we can place new tuples with NaN -> inf substitution, while making tree search recurse in whole subtree in case of old (NaN) value. Does it sound? Also, we can make the master BRIN patch to not touch boxes_bound_box() at al. Only INCLUSION_UNMERGEABLE is sufficient. -- Best regards, Kirill Reshke
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi Kirill,
Agreed on all four. v4 attached, split into BRIN and GiST.
0001 is BRIN, master only. bound_box() is untouched. The consistent
function also scans a range whose union is not mergeable with itself,
so old NaN summaries work without REINDEX. Needs a catversion bump.
0002 is GiST, back to 14. Old internal keys with a NaN match every
search and get KNN distance zero. Without the distance part, KNN on old
indexes returned rows out of order. 0002 also fixes point ~= with a NaN
query, which lost rows even on a fresh index. The leaf check used
FPeq(), but point_eq() compares exactly when there is a NaN.
The .nocfbot file is BRIN for the back branches, against REL_18. It
needs no catalog change. Consistent scans a range whose union does not
contain itself, using the existing contains support function. A NaN box
fails that, and any sane union passes. Nothing on disk changes, so old
indexes work without REINDEX after a minor upgrade. The code applies to
14 and later, the test hunk needs a small rebase on 14 to 16. This check
would also work on master, if we want one fix everywhere.
I checked 0001 and 0002 with indexes built by unpatched master, then
pg_upgraded, no REINDEX. The back branch patch got the same check on
REL_18, with a minor upgrade.
Thanks,
Shihao
Agreed on all four. v4 attached, split into BRIN and GiST.
0001 is BRIN, master only. bound_box() is untouched. The consistent
function also scans a range whose union is not mergeable with itself,
so old NaN summaries work without REINDEX. Needs a catversion bump.
0002 is GiST, back to 14. Old internal keys with a NaN match every
search and get KNN distance zero. Without the distance part, KNN on old
indexes returned rows out of order. 0002 also fixes point ~= with a NaN
query, which lost rows even on a fresh index. The leaf check used
FPeq(), but point_eq() compares exactly when there is a NaN.
The .nocfbot file is BRIN for the back branches, against REL_18. It
needs no catalog change. Consistent scans a range whose union does not
contain itself, using the existing contains support function. A NaN box
fails that, and any sane union passes. Nothing on disk changes, so old
indexes work without REINDEX after a minor upgrade. The code applies to
14 and later, the test hunk needs a small rebase on 14 to 16. This check
would also work on master, if we want one fix everywhere.
I checked 0001 and 0002 with indexes built by unpatched master, then
pg_upgraded, no REINDEX. The back branch patch got the same check on
REL_18, with a minor upgrade.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
On Thu, 24 Sept 2026 at 07:44, shihao zhong wrote:
>
> Hi Kirill,
>
> Agreed on all four. v4 attached, split into BRIN and GiST.
>
> 0001 is BRIN, master only. bound_box() is untouched. The consistent
> function also scans a range whose union is not mergeable with itself,
> so old NaN summaries work without REINDEX. Needs a catversion bump.
>
> 0002 is GiST, back to 14. Old internal keys with a NaN match every
> search and get KNN distance zero. Without the distance part, KNN on old
> indexes returned rows out of order. 0002 also fixes point ~= with a NaN
> query, which lost rows even on a fresh index. The leaf check used
> FPeq(), but point_eq() compares exactly when there is a NaN.
>
> The .nocfbot file is BRIN for the back branches, against REL_18. It
> needs no catalog change. Consistent scans a range whose union does not
> contain itself, using the existing contains support function. A NaN box
> fails that, and any sane union passes. Nothing on disk changes, so old
> indexes work without REINDEX after a minor upgrade. The code applies to
> 14 and later, the test hunk needs a small rebase on 14 to 16. This check
> would also work on master, if we want one fix everywhere.
>
> I checked 0001 and 0002 with indexes built by unpatched master, then
> pg_upgraded, no REINDEX. The back branch patch got the same check on
> REL_18, with a minor upgrade.
>
> Thanks,
> Shihao
Hi! v4 good.
I have tested point fix for ~= and it survives an index built by the
old master binary. The REL_18 backport looks good to me.
I see your changes to KNN search:
```
* classification logic to work.
@@ -1465,9 +1552,13 @@ gist_point_distance(PG_FUNCTION_ARGS)
switch (strategyGroup)
{
case PointStrategyNumberGroup:
- distance = computeDistance(GIST_LEAF(entry),
- DatumGetBoxP(entry->key),
- PG_GETARG_POINT_P(1));
+ /* A NaN internal key tells us nothing, see box_has_nan() */
+ if (nan_internal_key(entry))
+ distance = 0.0;
+ else
+ distance = computeDistance(GIST_LEAF(entry),
+ DatumGetBoxP(entry->key),
+ PG_GETARG_POINT_P(1));
break;
default:
```
But I cannot reproduce any wrong results with unpatched binary for
KNN. Something that I tried:
CREATE TABLE knn (p point);
INSERT INTO knn SELECT point(0.001*i, 0.001*i)
FROM generate_series(1,1000) i;
INSERT INTO knn VALUES ('(NaN,NaN)');
INSERT INTO knn SELECT point(50+0.001*i, 50+0.001*i)
FROM generate_series(1,1000) i;
CREATE INDEX knn_idx ON knn USING gist (p);
SET enable_seqscan = off;
SELECT count(*) FROM (SELECT 1 FROM knn
ORDER BY p <-> point '(0,0)' LIMIT 2200) s; -- 2001
SELECT count(*) FROM (SELECT p <-> point '(0,0)' d FROM knn
ORDER BY p <-> point '(0,0)' LIMIT 2200) s
WHERE d::text = 'NaN'; -- 1
and this works without v4 (and with).
Another case (from regress tests):
```
reshke=# CREATE TABLE POINT_TBL(f1 point);
INSERT INTO POINT_TBL(f1) VALUES
('(0.0,0.0)'),
('(-10.0,0.0)'),
('(-3.0,4.0)'),
('(5.1, 34.5)'),
('(-5.0,-12.0)'),
('(1e-300,-1e-300)'), -- To underflow
('(1e+300,Inf)'), -- To overflow
('(Inf,1e+300)'), -- Transposed
(' ( Nan , NaN ) '),
('10.0,10.0');
-- We intentionally don't vacuum point_tbl here; geometry depends on that
reshke=#
SELECT * FROM point_tbl WHERE f1 <@ polygon
'(0,0),(0,100),(100,100),(50,50),(100,0),(0,0)';
f1
------------------
(1e-300,-1e-300)
(0,0)
(10,10)
(5.1,34.5)
(4 rows)
reshke=# set enable_seqscan to true;
SET
reshke=#
SELECT * FROM point_tbl WHERE f1 <@ polygon
'(0,0),(0,100),(100,100),(50,50),(100,0),(0,0)';
f1
------------------
(0,0)
(5.1,34.5)
(1e-300,-1e-300)
(NaN,NaN)
(10,10)
(5 rows)
```
So, v4 keeps point <@ polygon and point <@ circle losing NaN points
that the heap returns. I added simple NaN check to
CircleStrategyNumberGroup/PolygonStrategyNumberGroup cases.
So, attaching v4 as v5 (without changes) and v5-0003 for fix the latter issue
--
Best regards,
Kirill Reshke
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
shihao zhong <zhong950419@gmail.com>
Дата:
Hi Kirill,
> But I cannot reproduce any wrong results with unpatched binary for
> KNN.
It does fail on master. Your points lie on one line and the query is at
the origin, so the low corner is always the closest point of a box. Try
a grid:
CREATE TABLE knn (p point);
INSERT INTO knn SELECT point(x, y)
FROM generate_series(0, 99) x, generate_series(0, 99) y;
INSERT INTO knn VALUES ('(NaN,NaN)');
CREATE INDEX ON knn USING gist (p);
SET enable_seqscan = off;
SELECT p FROM knn ORDER BY p <-> point '(99,99)' LIMIT 1;
Master returns (92,99), v5 returns (99,99). With a NaN high corner,
computeDistance() falls to the vertex case and returns the distance to
the low corner. That is too big for a query point inside the box. The
new union code alone fixes fresh indexes. Without the distance hunk, an
index built by master still gives the same wrong answers.
> So, v4 keeps point <@ polygon and point <@ circle losing NaN points
> that the heap returns.
0003 looks right to me, it just needs pgindent. Your circle test passes
without the circle hunk though, its failure on master comes from 0002.
A NaN point only matches a circle when it also has an infinity and the
radius is infinite.
The root of the polygon case is point_inside(), which puts (NaN,NaN)
inside every polygon, even '((0,0))'. Changing that changes query
results, so I'd leave it for a separate master only patch.
Thanks,
Shihao
> But I cannot reproduce any wrong results with unpatched binary for
> KNN.
It does fail on master. Your points lie on one line and the query is at
the origin, so the low corner is always the closest point of a box. Try
a grid:
CREATE TABLE knn (p point);
INSERT INTO knn SELECT point(x, y)
FROM generate_series(0, 99) x, generate_series(0, 99) y;
INSERT INTO knn VALUES ('(NaN,NaN)');
CREATE INDEX ON knn USING gist (p);
SET enable_seqscan = off;
SELECT p FROM knn ORDER BY p <-> point '(99,99)' LIMIT 1;
Master returns (92,99), v5 returns (99,99). With a NaN high corner,
computeDistance() falls to the vertex case and returns the distance to
the low corner. That is too big for a query point inside the box. The
new union code alone fixes fresh indexes. Without the distance hunk, an
index built by master still gives the same wrong answers.
> So, v4 keeps point <@ polygon and point <@ circle losing NaN points
> that the heap returns.
0003 looks right to me, it just needs pgindent. Your circle test passes
without the circle hunk though, its failure on master comes from 0002.
A NaN point only matches a circle when it also has an infinity and the
radius is infinite.
The root of the polygon case is point_inside(), which puts (NaN,NaN)
inside every polygon, even '((0,0))'. Changing that changes query
results, so I'd leave it for a separate master only patch.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi,
Since the cases keep turning up one by one, I ran a differential check
of v5 (0001, 0002 and the NaN point check for polygon and circle) on
master and REL_18_STABLE. For every operator pg_amop lists for the
BRIN, GiST and SP-GiST box, point, polygon and circle opclasses, with
NaN rows first, last, alone and scattered, it compares a seq scan with
the index: count(*) for searches, the first 50 distances for ordering.
6769 checks per build, built without assertions.
BRIN: 79 mismatches without the patches, none with them, on master and
on REL_18. None either with indexes built by unpatched REL_18 and
searched after the minor upgrade.
GiST on master: 376 mismatches without the patches, 91 with them. Most of what
is left is ordering: the index scan fails with "inconsistent point
values" (with assertions, Assert(box->low.y <= box->high.y) fails in
computeDistance()), with and without v5, on both branches:
CREATE TABLE b (v box);
INSERT INTO b VALUES ('(1,NaN),(0,0)');
INSERT INTO b SELECT box(point(x, y), point(x + 1, y + 1))
FROM generate_series(0, 44) x, generate_series(0, 44) y;
CREATE INDEX ON b USING gist (v);
SET enable_seqscan = off;
SELECT v <-> point '(0.5,0.5)' FROM b
ORDER BY v <-> point '(0.5,0.5)' LIMIT 3;
The seq scan returns 0, 0.5, 0.5. Circle and polygon fail the same
way with a finite query point, and all four types with a NaN in the
query point. Which LIMIT reaches the NaN entry depends on where it
lands in the tree, so v5 changes which queries fail but not that they
do. Besides that, box ordering returns NaN distances before finite
ones, and polygon ordering also gets "index returned tuples in wrong
order", with finite query points as well. The rest is point <@
polygon with a NaN in the polygon, which you already set aside.
v5-0002 does not apply to REL_18 as is: gist_box_picksplit() uses
palloc_object(), which 18 does not have. With palloc(sizeof(BOX))
there it applies, and REL_18 gives the same counts as master.
Outside this thread: SP-GiST box_ops and poly_ops show similar ordering
and ~= mismatches, unchanged by v5. quad_point_ops fails CREATE
INDEX with NaN points with "getQuadrant: impossible case", the error of
bug #19597, although that report reaches it through rounding, not NaN.
I have not checked whether the patch there covers NaN too.
The counts, the full list and the scripts are attached.
Regards,
Manu
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
Hi Manu,
Thanks for the matrix.
> Most of what is left is ordering: the index scan fails with
> "inconsistent point values"
computeDistance() assumes low <= high and a query point without NaN.
So this doesn't need NaN rows. On a table with only finite values,
ORDER BY v <-> point '(1,NaN)' fails for all four GiST opclasses.
v6-0004 gives distance 0 to keys and query points with a NaN, as 0002
already does for internal keys. A box_ops leaf must be exact, and
index-only scans can't recheck, so it calls the operator instead.
With your script, GiST has 9 mismatches left on master, all point <@
polygon with a NaN vertex. GiST indexes built by unpatched master give
the same.
0001 to 0003 are v5. 0003 is Kirill's polygon and circle patch after
pgindent.
> palloc_object(), which 18 does not have
18 has it. The conflict comes from 1b105f9472b, which changed those
lines in 19.
> I have not checked whether the patch there covers NaN too.
It doesn't. The v2 there leaves NaN on the same error on purpose.
Regards,
Shihao
Thanks for the matrix.
> Most of what is left is ordering: the index scan fails with
> "inconsistent point values"
computeDistance() assumes low <= high and a query point without NaN.
So this doesn't need NaN rows. On a table with only finite values,
ORDER BY v <-> point '(1,NaN)' fails for all four GiST opclasses.
v6-0004 gives distance 0 to keys and query points with a NaN, as 0002
already does for internal keys. A box_ops leaf must be exact, and
index-only scans can't recheck, so it calls the operator instead.
With your script, GiST has 9 mismatches left on master, all point <@
polygon with a NaN vertex. GiST indexes built by unpatched master give
the same.
0001 to 0003 are v5. 0003 is Kirill's polygon and circle patch after
pgindent.
> palloc_object(), which 18 does not have
18 has it. The conflict comes from 1b105f9472b, which changed those
lines in 19.
> I have not checked whether the patch there covers NaN too.
It doesn't. The v2 there leaves NaN on the same error on purpose.
Regards,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
Manu <manuelreyesbravo@gmail.com>
Дата:
Hi Shihao,
I ran v6 (0001 through 0004) through the same differential matrix as
v5, on master (a5447a2deac) and REL_18_STABLE, built without
assertions. 6769 checks per build: seq scan versus index for every
operator the box, point, polygon and circle opclasses list, with NaN
rows first, last, alone and scattered.
> With your script, GiST has 9 mismatches left on master, all point <@
> polygon with a NaN vertex.
Confirmed. On master, v6 takes BRIN box_inclusion_ops from 79
mismatches to 0, GiST box_ops from 85 to 0, GiST circle_ops from 60 to
0, and GiST poly_ops from 71 to 0. GiST point_ops goes from 162 to 9,
and those 9 are exactly the point <@ polygon case with a NaN vertex in
the polygon: the seq scan returns about 2025 rows and the index 0. The
SP-GiST box_ops and poly_ops counts (10 and 28) are unchanged, as
expected; they are the separate matter from earlier in the thread.
> v6-0004 gives distance 0 to keys and query points with a NaN, as 0002
> already does for internal keys.
0004 also clears the KNN failure I reported. On master,
CREATE TABLE b (v box);
INSERT INTO b VALUES ('(1,NaN),(0,0)');
INSERT INTO b SELECT box(point(x, y), point(x + 1, y + 1))
FROM generate_series(0, 44) x, generate_series(0, 44) y;
CREATE INDEX ON b USING gist (v);
SET enable_seqscan = off;
SELECT v <-> point '(0.5,0.5)' FROM b
ORDER BY v <-> point '(0.5,0.5)' LIMIT 3;
fails the assertion box->low.y <= box->high.y in computeDistance() (and
raises "inconsistent point values" without assertions). With 0004 the
index returns 0, 0.5, 0.5, the same as the seq scan, with no assertion
and no error.
On REL_18 the BRIN backport (v6-REL_18-0001) also takes BRIN
box_inclusion_ops from 79 to 0. 0002 does not apply there, the
1b105f9472b context you mentioned, so I tested only the BRIN change on
that branch; the GiST counts stay at the master control numbers.
That leaves the point <@ polygon NaN-vertex case as the only mismatch
on master. I am happy to keep it out of scope for this set if you
would rather handle a NaN in the query polygon separately.
Regards,
Manu
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
shihao zhong <zhong950419@gmail.com>
Дата:
Hi Manu,
Thanks for running the whole matrix again.
> I am happy to keep it out of scope for this set if you
> would rather handle a NaN in the query polygon separately.
I'd keep it out. Nothing stored in the index is wrong here. The NaN is
in the query, and the heap answer is wrong too. With the gist.sql test
table, a 0 to 99 grid, the polygon '(0,0),(0,10),(10,10),(10,NaN)'
matches 1015 rows on a seq scan, far more than any 10 by 10 square can
hold. point_inside() doesn't handle NaN, so the fix belongs there, as a
master only behavior change. I'll start a separate thread for it.
Where each patch would go:
0001 BRIN, master only, it adds a pg_amproc row.
v6-REL_18-0001 BRIN without catalog changes, 14 to 18.
0002 to 0004 GiST, 14 to 18. They need a small rebase on 18 because
of 1b105f9472b, and a bit more on 14.
I think the set is ready for a committer to look at.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
shihao zhong <zhong950419@gmail.com>
Дата:
Hi Tomas and Heikki,
Adding you both, this touches BRIN and GiST. Here is the short version
so you don't have to read the whole thread.
One box with a NaN coordinate gets into a BRIN or GiST union key, and
no box operator is true against a NaN bound. So the whole range or
subtree holding that box disappears from index scans. KNN searches
with a NaN in a key or in the query point fail with "inconsistent
point values".
v6 from Sep 28 has four patches. 0001 fixes BRIN with a box_mergeable
support function, master only. 0002 fixes GiST union keys and the ~=
case. 0003 is Kirill's NaN point check for polygon and circle
searches, it also corrects a count in create_index.out where the index
scan has returned 4 and the seq scan 5. 0004 fixes GiST KNN. 0002 to
0004 go back to 14 with small rebases. For the back branches the BRIN
fix is v6-REL_18-0001, the scan checks whether the union contains
itself, no catalog change. That check would also do for master if you
would rather skip the catversion bump. Old indexes return correct
results without a REINDEX with either approach.
Manu compared seq scan with index scan for every operator of the box,
point, polygon and circle opclasses, 6769 checks on master. Every
mismatch goes to zero except point <@ polygon with a NaN vertex, which
is a heap bug in point_inside() and gets its own thread.
Thanks,
Shihao
Adding you both, this touches BRIN and GiST. Here is the short version
so you don't have to read the whole thread.
One box with a NaN coordinate gets into a BRIN or GiST union key, and
no box operator is true against a NaN bound. So the whole range or
subtree holding that box disappears from index scans. KNN searches
with a NaN in a key or in the query point fail with "inconsistent
point values".
v6 from Sep 28 has four patches. 0001 fixes BRIN with a box_mergeable
support function, master only. 0002 fixes GiST union keys and the ~=
case. 0003 is Kirill's NaN point check for polygon and circle
searches, it also corrects a count in create_index.out where the index
scan has returned 4 and the seq scan 5. 0004 fixes GiST KNN. 0002 to
0004 go back to 14 with small rebases. For the back branches the BRIN
fix is v6-REL_18-0001, the scan checks whether the union contains
itself, no catalog change. That check would also do for master if you
would rather skip the catversion bump. Old indexes return correct
results without a REINDEX with either approach.
Manu compared seq scan with index scan for every operator of the box,
point, polygon and circle opclasses, 6769 checks on master. Every
mismatch goes to zero except point <@ polygon with a NaN vertex, which
is a heap bug in point_inside() and gets its own thread.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
John Naylor <johncnaylorls@gmail.com>
Дата:
On Wed, Sep 30, 2026 at 12:30 PM shihao zhong wrote: > One box with a NaN coordinate gets into a BRIN or GiST union key, and > v6 from Sep 28 has four patches. 0001 fixes BRIN with a box_mergeable > support function, master only. 0002 fixes GiST union keys and the ~= > case. 0003 is Kirill's NaN point check for polygon and circle > searches, it also corrects a count in create_index.out where the index > scan has returned 4 and the seq scan 5. 0004 fixes GiST KNN. 0002 to > 0004 go back to 14 with small rebases. For the back branches the BRIN > fix is v6-REL_18-0001, the scan checks whether the union contains > itself, no catalog change. That check would also do for master if you > would rather skip the catversion bump. Old indexes return correct > results without a REINDEX with either approach. The following might be relevant as a different perspective: https://www.postgresql.org/message-id/1122078.1741378100@sss.pgh.pa.us -- John Naylor Amazon Web Services
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
shihao zhong <zhong950419@gmail.com>
Дата:
> The following might be relevant as a different perspective:
>
> https://www.postgresql.org/message-id/1122078.1741378100@sss.pgh.pa.us
Hi John,
Thanks. I don't think v6 conflicts with Tom's idea. Banning NaN
would reject input that works today, so it can't be back-patched. And
in master, NaN boxes already on disk stay there after pg_upgrade. So
the indexes need fixing either way.
If you want less code, I can drop 0004 and use the v6-REL_18-0001
check on master too. That leaves no catalog change.
Thanks,
Shihao
>
> https://www.postgresql.org/message-id/1122078.1741378100@sss.pgh.pa.us
Hi John,
Thanks. I don't think v6 conflicts with Tom's idea. Banning NaN
would reject input that works today, so it can't be back-patched. And
in master, NaN boxes already on disk stay there after pg_upgrade. So
the indexes need fixing either way.
If you want less code, I can drop 0004 and use the v6-REL_18-0001
check on master too. That leaves no catalog change.
Thanks,
Shihao
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
Greg Burd <greg@burd.me>
Дата:
On Wed, 30 Sep 2026 21:04:19 -0600, shihao zhong wrote:
> > The following might be relevant as a different perspective:
> >
> > https://www.postgresql.org/message-id/1122078.1741378100@sss.pgh.pa.us
>
> Hi John,
>
> Thanks. I don't think v6 conflicts with Tom's idea. Banning NaN
> would reject input that works today, so it can't be back-patched. And
> in master, NaN boxes already on disk stay there after pg_upgrade. So
> the indexes need fixing either way.
>
> If you want less code, I can drop 0004 and use the v6-REL_18-0001
> check on master too. That leaves no catalog change.
>
> Thanks,
> Shihao
Hey Shihao,
I happened onto this very issue myself when testing the other day. I
was testing a fix for this with an index-vs-sequential-scan check and
found two NaN/infinity cases it does not cover. Both are on master as
well, so I'm adding my voice here rather than as separate reports; they
may be in scope for this patch or may want their own. Your call.
1. Polygon containment. A polygon with NaN vertices is reported to
contain every point by a sequential scan, but no points by a GiST index:
CREATE TABLE t (g point);
INSERT INTO t VALUES ('(0,0)'), ('(5,5)');
CREATE INDEX ON t USING gist (g);
SET enable_indexscan = off; SET enable_bitmapscan = off;
SELECT count(*) FROM t WHERE g <@ polygon '((NaN,NaN))'; -- 2
SET enable_seqscan = off;
SELECT count(*) FROM t WHERE g <@ polygon '((NaN,NaN))'; -- 0
The sequential scan is the wrong side here: point_inside() builds a
crossing count from lseg_crossing(), and with NaN vertices every float
comparison is false, so it falls through and counts a crossing for each
edge, making any point "inside". box and circle give false for the same
inputs, and point '(NaN,NaN)' <@ an ordinary square also comes back
true. The GiST side (empty bbox -> no match) is the consistent answer.
2. KNN order. An ORDER BY ... <-> with an infinite query point over a
column that contains NaN points raises
ERROR: index returned tuples in wrong order
from the executor's reorder recheck, because the index distance order
and the recheck disagree for an infinite point against NaN keys.
Both reproduce on current master. I realize this patch is scoped to the
BRIN and GiST box cases from the original report; flag these as either
in or out of scope as you see fit.
best.
-greg
Re: BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows
От:
Manu <manuelreyesbravo@gmail.com>
Дата:
Hi Greg, shihao,
> 1. Polygon containment. A polygon with NaN vertices is reported to
> contain every point by a sequential scan, but no points by a GiST
> index
I traced this one in gdb on master. With a NaN coordinate every test
in lseg_crossing() is false, so it always falls through to the last
"return 2 * y_sign" (geo_ops.c:5669) and each edge adds -2 to
total_cross. point_inside() then reports the point inside. That
matches your reading: the seq scan is the side that is off, and the
index is the consistent one (box and circle also say false for the
same inputs).
point_inside() has six callers, so the same answer shows up in
point <@ polygon, polygon @> point, point <-> polygon (distance 0) and
point <@ closed path. It also depends on which coordinate is NaN:
point '(0.5,NaN)' is inside the unit square, point '(NaN,0.5)' is not.
> 2. KNN order. An ORDER BY ... <-> with an infinite query point over a
> column that contains NaN points raises
>
> ERROR: index returned tuples in wrong order
This turns out to be the same bug. That error comes only from the
reorder recheck (nodeIndexscan.c:319), and only opclasses whose
distance asks for a recheck reach it, so the column has to be a
polygon (GiST or SP-GiST poly_ops); GiST point_ops never rechecks.
In gdb the index returns NaN as the lower bound for the NaN key, the
recheck computes dist_ppoly(), which returns 0 because point_inside()
said "inside", and 0 < NaN raises the error. No infinite point is
needed:
CREATE TABLE p1 (g polygon);
INSERT INTO p1 VALUES ('((NaN,NaN))');
CREATE INDEX ON p1 USING gist (g);
SET enable_seqscan = off;
SELECT g <-> point '(10,10)' FROM p1 ORDER BY g <-> point '(10,10)';
The seq scan returns 0. With more rows and a query point near the
data, master stops earlier with "inconsistent point values" in
computeDistance(), which is likely why an infinite point was needed to
see it. It is also the polygon ordering failure from the v5 matrix.
shihao, v6-0004 fixes it for GiST: on v6 every GiST KNN query I tried
on polygon, box, circle and point columns matches the seq scan.
SP-GiST poly_ops still fails with v6: the same rows in an SP-GiST
index raise the error for (0.5,0.5), (1e308,1e308), (Infinity,0),
(-Infinity,-Infinity) and (Infinity,Infinity). The same failure
accounts for 25 of the 28 SP-GiST poly_ops mismatches the matrix still
showed with v6; the other 3 are ~=.
One data point on the expected output. On master, create_index.out
already shows the case 1 disagreement on point_tbl, which has a
(NaN,NaN) row: the seq scan count for
SELECT count(*) FROM point_tbl
WHERE f1 <@ polygon '(0,0),(0,100),(100,100),(50,50),(100,0),(0,0)';
is 5, and the GiST index-only scan of the same query is 4. The matrix
and gdb point to point_inside() as the side that is off, so the
GiST/SP-GiST answer (4) is the consistent one; v6-0003 brings the index
to match the seq scan (5) rather than the other way round. A small
guard in point_inside() makes both return 4.
As a direction, not a patch, I measured a guard at the top of
point_inside() that returns 0 ("not inside") when the point or any
polygon vertex has a NaN (about nine lines; I can send the diff).
On master alone it fixes both cases, SP-GiST included, and the scalar
operators above give false and NaN, the same as box and circle. On
top of v6 it takes the differential matrix (6769 checks, seq scan
versus index) from 47 mismatches to 13; the 13 left were already in
v6's 47 and are the SP-GiST box_ops ordering and ~= cases, unrelated.
There were no assertion failures with assertions enabled.
To be clear about what it is: a measurement prototype, with no test of
its own and no expected files updated. It does not replace v6-0004,
which is still needed for NaN internal keys ("inconsistent point
values" when the query point is near the data). make check changes in
geometry, create_index and, on v6, in 0003's new gist test (7602 rows
to 7599), all of them the "NaN is inside" answers that the expected
files record today. I can send the diff and the regression diffs if
they are useful.
That last point is the open question I would leave to you and the
committers: the change is user-visible, since today's answer is pinned
in the expected output, so it could be master only or back-patched
along with the rest of the set.
Regards,
Manu