BUG #19705: One NaN box makes a BRIN box_inclusion_ops index omit unrelated rows

Started by PG Bug reporting form1 day ago1 messagesbugs

noreply@postgresql.org

1 day ago

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:

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.