BUG #19597: getQuadrant: impossible case is reachable

Hi,

On Sun, 2 Aug 2026 at 23:42, PG Bug reporting form <noreply@postgresql.org>
wrote:

The following bug has been logged on the website:

Bug reference: 19597
Logged by: Michael Malis
Email address: malis@pgrust.com
PostgreSQL version: 18.3
Operating system: Debian 18.3-1.pgdg13+1
Description:

getQuadrant has four arms covering the quadrants and an elog(ERROR,
"getQuadrant: impossible case") fallthrough. The arms are exhaustive only
if
the above/below/horizontal predicates are exhaustive. They are not: the
three comparisons are written in three algebraically different forms, and
near a power-of-two boundary — where the gap between adjacent doubles
doubles — adding EPSILON rounds up on one side and vanishes on the other. A
point can then be neither above, below, nor level with the centroid, and
the
"impossible" branch executes.

Reproducer (runnable against stock PostgreSQL 18.3)
---------------------------------------------------
CREATE TABLE gq(p point);
-- 4000 identical points: their mean (the quad centroid) is exactly
this
value,
-- which is nextafter(2^34, -inf)
INSERT INTO gq SELECT point('17179869183.999998','17179869183.999998')
FROM generate_series(1,4000);
CREATE INDEX gqx ON gq USING spgist(p);
-- probe at 2^34, one representable step away
INSERT INTO gq SELECT point('17179869184.0','17179869184.0')
FROM generate_series(1,400);
ERROR: getQuadrant: impossible case

The identical-point fill is what forces the computed centroid onto the
chosen value — spg_quad_picksplit uses the mean of the split set, so the
centroid cannot simply be inserted.

Expected vs. actual
-------------------
- Expected: the insert succeeds, or fails with a meaningful user-facing
error. A branch labelled "impossible case" should not be reachable from
well-formed finite input.
- Actual: ERROR: getQuadrant: impossible case. The backend survives (this
is
a catchable error, not a crash), but the index operation fails and the
message is an internal invariant leaking to the user.

Mechanism, with file:line into the 18.3 source
----------------------------------------------
src/backend/access/spgist/spgquadtreeproc.c, getQuadrant (function at 55):
57: if ((SPTEST(point_above, tst, centroid) || SPTEST(point_horiz,
tst,
centroid)) && ...
63: if (SPTEST(point_below, tst, centroid) && ...
68: if ((SPTEST(point_below, tst, centroid) || SPTEST(point_horiz,
tst,
centroid)) && ...
73: if (SPTEST(point_above, tst, centroid) && SPTEST(point_left, tst,
centroid))
77: elog(ERROR, "getQuadrant: impossible case");

point_above/point_below/point_horiz reduce to FPgt/FPlt/FPeq on the y
coordinate. src/include/utils/geo_decls.h:
41: #define EPSILON 1.0E-06
47: FPeq(A,B) { return A == B || fabs(A - B) <= EPSILON; }
59: FPlt(A,B) { return A + EPSILON < B; }
71: FPgt(A,B) { return A > B + EPSILON; }

FPeq tests the rounded difference; FPlt and FPgt test rounded sums. Over
exact reals these partition the line; in floating point they do not. Just
below 2^34 the spacing between doubles is 2^-19 ≈ 1.907e-6 (> EPSILON, so
adding EPSILON rounds up a step); just above it is 2^-18 ≈ 3.815e-6 (>
2·EPSILON, so adding EPSILON rounds back down). For a = 2^34, b =
nextafter(2^34, -inf) all three are false — verified on 18.3's own
arithmetic:

expression value
----------- --------------------------------------------
a - b 1.9073486328125e-06 (> EPSILON ⇒ FPeq false)
a > b + eps false (b + eps rounds up to exactly a)
a + eps < b false (a + eps rounds back to a)

With the y trichotomy failing, no arm matches regardless of the x result,
and line 77 executes.

Thanks for the detailed report and analysis. I reproduced the issue on
current master.

The three fuzzy comparisons are indeed not exhaustive near this
floating-point
boundary, allowing getQuadrant() to reach its "impossible case". The
attached
patch leaves the existing quadrant tests unchanged and falls back to exact
comparisons only when none of them match.

Thoughts?

Regards,
Ayush

Hi, Ayush!

Thanks for the patch.

The approach looks right to me: keep the fuzzy arms, fall back to exact
comparisons for the finite gap, and leave the
elog for NaN.

Here is a suggested v2 on top of your patch.

1. Write the exact fallback as y-then-x checks, which I find a bit easier
to match to the quadrant diagram and the axis tie-breaking rule.

2. Add a short note in the getQuadrant() header about why the fallback
exists.

3. Add a regress case.

пн, 3 авг. 2026 г. в 01:31, Ayush Tiwari <ayushtiwari.slg01@gmail.com>:

Hi,

On Sun, 2 Aug 2026 at 23:42, PG Bug reporting form <noreply@postgresql.org>
wrote:

The following bug has been logged on the website:

Bug reference: 19597
Logged by: Michael Malis
Email address: malis@pgrust.com
PostgreSQL version: 18.3
Operating system: Debian 18.3-1.pgdg13+1
Description:

getQuadrant has four arms covering the quadrants and an elog(ERROR,
"getQuadrant: impossible case") fallthrough. The arms are exhaustive only
if
the above/below/horizontal predicates are exhaustive. They are not: the
three comparisons are written in three algebraically different forms, and
near a power-of-two boundary — where the gap between adjacent doubles
doubles — adding EPSILON rounds up on one side and vanishes on the other.
A
point can then be neither above, below, nor level with the centroid, and
the
"impossible" branch executes.

Reproducer (runnable against stock PostgreSQL 18.3)
---------------------------------------------------
CREATE TABLE gq(p point);
-- 4000 identical points: their mean (the quad centroid) is exactly
this
value,
-- which is nextafter(2^34, -inf)
INSERT INTO gq SELECT point('17179869183.999998','17179869183.999998')
FROM generate_series(1,4000);
CREATE INDEX gqx ON gq USING spgist(p);
-- probe at 2^34, one representable step away
INSERT INTO gq SELECT point('17179869184.0','17179869184.0')
FROM generate_series(1,400);
ERROR: getQuadrant: impossible case

The identical-point fill is what forces the computed centroid onto the
chosen value — spg_quad_picksplit uses the mean of the split set, so the
centroid cannot simply be inserted.

Expected vs. actual
-------------------
- Expected: the insert succeeds, or fails with a meaningful user-facing
error. A branch labelled "impossible case" should not be reachable from
well-formed finite input.
- Actual: ERROR: getQuadrant: impossible case. The backend survives (this
is
a catchable error, not a crash), but the index operation fails and the
message is an internal invariant leaking to the user.

Mechanism, with file:line into the 18.3 source
----------------------------------------------
src/backend/access/spgist/spgquadtreeproc.c, getQuadrant (function at 55):
57: if ((SPTEST(point_above, tst, centroid) || SPTEST(point_horiz,
tst,
centroid)) && ...
63: if (SPTEST(point_below, tst, centroid) && ...
68: if ((SPTEST(point_below, tst, centroid) || SPTEST(point_horiz,
tst,
centroid)) && ...
73: if (SPTEST(point_above, tst, centroid) && SPTEST(point_left, tst,
centroid))
77: elog(ERROR, "getQuadrant: impossible case");

point_above/point_below/point_horiz reduce to FPgt/FPlt/FPeq on the y
coordinate. src/include/utils/geo_decls.h:
41: #define EPSILON 1.0E-06
47: FPeq(A,B) { return A == B || fabs(A - B) <= EPSILON; }
59: FPlt(A,B) { return A + EPSILON < B; }
71: FPgt(A,B) { return A > B + EPSILON; }

FPeq tests the rounded difference; FPlt and FPgt test rounded sums. Over
exact reals these partition the line; in floating point they do not. Just
below 2^34 the spacing between doubles is 2^-19 ≈ 1.907e-6 (> EPSILON, so
adding EPSILON rounds up a step); just above it is 2^-18 ≈ 3.815e-6 (>
2·EPSILON, so adding EPSILON rounds back down). For a = 2^34, b =
nextafter(2^34, -inf) all three are false — verified on 18.3's own
arithmetic:

expression value
----------- --------------------------------------------
a - b 1.9073486328125e-06 (> EPSILON ⇒ FPeq false)
a > b + eps false (b + eps rounds up to exactly a)
a + eps < b false (a + eps rounds back to a)

With the y trichotomy failing, no arm matches regardless of the x result,
and line 77 executes.

Thanks for the detailed report and analysis. I reproduced the issue on
current master.

The three fuzzy comparisons are indeed not exhaustive near this
floating-point
boundary, allowing getQuadrant() to reach its "impossible case". The
attached
patch leaves the existing quadrant tests unchanged and falls back to exact
comparisons only when none of them match.

Thoughts?

Regards,
Ayush

--
Regards,
Rachitskiy Andrey