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

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