Re: BUG #19597: getQuadrant: impossible case is reachable

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(dot)slg01(at)gmail(dot)com>:

> Hi,
>
> On Sun, 2 Aug 2026 at 23:42, PG Bug reporting form <noreply(at)postgresql(dot)org>
> wrote:
>
>> The following bug has been logged on the website:
>>
>> Bug reference: 19597
>> Logged by: Michael Malis
>> Email address: malis(at)pgrust(dot)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