agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedBUG #19597: getQuadrant: impossible case is reachable
4+ messages / 4 participants
[nested] [flat]
* BUG #19597: getQuadrant: impossible case is reachable
@ 2026-08-02 17:47 PG Bug reporting form <noreply@postgresql.org>
2026-08-02 20:31 ` Re: BUG #19597: getQuadrant: impossible case is reachable Ayush Tiwari <ayushtiwari.slg01@gmail.com>
0 siblings, 1 reply; 4+ messages in thread
From: PG Bug reporting form @ 2026-08-02 17:47 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: malis@pgrust.com
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.
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19597: getQuadrant: impossible case is reachable
2026-08-02 17:47 BUG #19597: getQuadrant: impossible case is reachable PG Bug reporting form <noreply@postgresql.org>
@ 2026-08-02 20:31 ` Ayush Tiwari <ayushtiwari.slg01@gmail.com>
2026-08-02 21:22 ` Re: BUG #19597: getQuadrant: impossible case is reachable Andrey Rachitskiy <pl0h0yp1@gmail.com>
0 siblings, 1 reply; 4+ messages in thread
From: Ayush Tiwari @ 2026-08-02 20:31 UTC (permalink / raw)
To: malis@pgrust.com; pgsql-bugs@lists.postgresql.org
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
Attachments:
[application/octet-stream] 0001-Fix-reachable-impossible-case-in-SP-GiST-quad-tree.patch (1.4K, ../../CAJTYsWXFmxSc60e1Kj29QFtaRn5P28prg40sVVGhHyg8dF0VgQ@mail.gmail.com/3-0001-Fix-reachable-impossible-case-in-SP-GiST-quad-tree.patch)
download | inline diff:
From e505d83aa56fc9293b6819e5adc6971df4734ce8 Mon Sep 17 00:00:00 2001
From: Ayush Tiwari <ayushtiwari.slg01@gmail.com>
Date: Mon, 3 Aug 2026 01:46:18 +0530
Subject: [PATCH] Fix reachable "impossible case" in SP-GiST quad tree
The fuzzy point comparisons used by getQuadrant() are not mutually
exhaustive near some power-of-two boundaries. Fall back to exact
comparisons when none of the existing quadrant tests match.
Reported-by: Michael Malis <malis@pgrust.com>
Discussion: https://postgr.es/m/19597-39c532e61d78dff6@postgresql.org
Backpatch-through: 14
---
src/backend/access/spgist/spgquadtreeproc.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index 946dabc4527..2566ab3b8db 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -76,6 +76,16 @@ getQuadrant(Point *centroid, Point *tst)
SPTEST(point_left, tst, centroid))
return 4;
+ /* Fuzzy comparisons can leave gaps, so fall back to exact ones. */
+ if (tst->x >= centroid->x && tst->y >= centroid->y)
+ return 1;
+ if (tst->x >= centroid->x && tst->y < centroid->y)
+ return 2;
+ if (tst->x < centroid->x && tst->y <= centroid->y)
+ return 3;
+ if (tst->x < centroid->x && tst->y > centroid->y)
+ return 4;
+
elog(ERROR, "getQuadrant: impossible case");
return 0;
}
--
2.34.1
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19597: getQuadrant: impossible case is reachable
2026-08-02 17:47 BUG #19597: getQuadrant: impossible case is reachable PG Bug reporting form <noreply@postgresql.org>
2026-08-02 20:31 ` Re: BUG #19597: getQuadrant: impossible case is reachable Ayush Tiwari <ayushtiwari.slg01@gmail.com>
@ 2026-08-02 21:22 ` Andrey Rachitskiy <pl0h0yp1@gmail.com>
2026-08-18 13:13 ` Re: BUG #19597: getQuadrant: impossible case is reachable Pierre Forstmann <pierre.forstmann@gmail.com>
0 siblings, 1 reply; 4+ messages in thread
From: Andrey Rachitskiy @ 2026-08-02 21:22 UTC (permalink / raw)
To: Ayush Tiwari <ayushtiwari.slg01@gmail.com>; +Cc: malis@pgrust.com; pgsql-bugs@lists.postgresql.org
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
Attachments:
[text/x-patch] v2-0001-Fix-reachable-impossible-case-in-SP-GiST-quad-tree.patch (3.7K, ../../CAB8bMiuVK73xrcqkPGXvWihxHxyrdBBm6kxdAm-7upLcZh9J6A@mail.gmail.com/3-v2-0001-Fix-reachable-impossible-case-in-SP-GiST-quad-tree.patch)
download | inline diff:
From: Andrey Rachitskiy <pl0h0yp1@gmail.com>
Date: Mon, 3 Aug 2026 02:15:00 +0500
Subject: [PATCH v2] Fix reachable "impossible case" in SP-GiST quad tree
The fuzzy point comparisons used by getQuadrant() are not mutually
exhaustive near some power-of-two boundaries. Fall back to exact
comparisons when none of the existing quadrant tests match, keeping
the documented axis tie-breaking. Leave the elog for NaN.
Author: Ayush Tiwari <ayushtiwari.slg01@gmail.com>
Reviewed-by: Andrey Rachitskiy <pl0h0yp1@gmail.com>
Reported-by: Michael Malis <malis@pgrust.com>
Discussion: https://postgr.es/m/19597-39c532e61d78dff6@postgresql.org
Backpatch-through: 14
---
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index 946dabc4527..2e8610f5740 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -52,6 +52,11 @@ spg_quad_config(PG_FUNCTION_ARGS)
*
* Points on one of the axes are taken to lie in the lowest-numbered
* adjacent quadrant.
+ *
+ * We normally use the fuzzy point_* operators, but those are not always
+ * decisive (see FPeq/FPlt/FPgt). If no arm matches, fall back to exact
+ * comparisons with the same axis rule as above. NaN still reaches the
+ * error below; cleaning that up is a separate matter.
*/
static int16
getQuadrant(Point *centroid, Point *tst)
@@ -76,6 +81,17 @@ getQuadrant(Point *centroid, Point *tst)
SPTEST(point_left, tst, centroid))
return 4;
+ /*
+ * Fuzzy comparisons can leave gaps for finite values. Fall back to
+ * exact comparisons with the same axis tie-breaking as above.
+ */
+ if (tst->y > centroid->y)
+ return (tst->x >= centroid->x) ? 1 : 4;
+ if (tst->y < centroid->y)
+ return (tst->x >= centroid->x) ? 2 : 3;
+ if (tst->y == centroid->y)
+ return (tst->x >= centroid->x) ? 1 : 3;
+
elog(ERROR, "getQuadrant: impossible case");
return 0;
}
diff --git a/src/test/regress/expected/spgist.out b/src/test/regress/expected/spgist.out
index 2e911285600..1ec57562484 100644
--- a/src/test/regress/expected/spgist.out
+++ b/src/test/regress/expected/spgist.out
@@ -94,3 +94,18 @@ select box(point(i,j))
from generate_series(1,100,5) i,
generate_series(1,10,5) j;
-- leave this table around, to help in testing dump/restore
+-- Check getQuadrant with large coords near a power-of-two boundary (bug #19597)
+create table spgist_quad_fp_tbl(p point);
+insert into spgist_quad_fp_tbl
+ select point(17179869183.999998, 17179869183.999998)
+ from generate_series(1, 4000);
+create index spgist_quad_fp_idx on spgist_quad_fp_tbl using spgist(p);
+insert into spgist_quad_fp_tbl
+ select point(17179869184.0, 17179869184.0)
+ from generate_series(1, 400);
+select count(*) from spgist_quad_fp_tbl where p ~= point(17179869184.0, 17179869184.0);
+ count
+-------
+ 400
+(1 row)
+
diff --git a/src/test/regress/sql/spgist.sql b/src/test/regress/sql/spgist.sql
index 4828ede68c3..f89f879e3a9 100644
--- a/src/test/regress/sql/spgist.sql
+++ b/src/test/regress/sql/spgist.sql
@@ -89,3 +89,13 @@ select box(point(i,j))
from generate_series(1,100,5) i,
generate_series(1,10,5) j;
-- leave this table around, to help in testing dump/restore
+-- Check getQuadrant with large coords near a power-of-two boundary (bug #19597)
+create table spgist_quad_fp_tbl(p point);
+insert into spgist_quad_fp_tbl
+ select point(17179869183.999998, 17179869183.999998)
+ from generate_series(1, 4000);
+create index spgist_quad_fp_idx on spgist_quad_fp_tbl using spgist(p);
+insert into spgist_quad_fp_tbl
+ select point(17179869184.0, 17179869184.0)
+ from generate_series(1, 400);
+select count(*) from spgist_quad_fp_tbl where p ~= point(17179869184.0, 17179869184.0);
--
2.43.0
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: BUG #19597: getQuadrant: impossible case is reachable
2026-08-02 17:47 BUG #19597: getQuadrant: impossible case is reachable PG Bug reporting form <noreply@postgresql.org>
2026-08-02 20:31 ` Re: BUG #19597: getQuadrant: impossible case is reachable Ayush Tiwari <ayushtiwari.slg01@gmail.com>
2026-08-02 21:22 ` Re: BUG #19597: getQuadrant: impossible case is reachable Andrey Rachitskiy <pl0h0yp1@gmail.com>
@ 2026-08-18 13:13 ` Pierre Forstmann <pierre.forstmann@gmail.com>
0 siblings, 0 replies; 4+ messages in thread
From: Pierre Forstmann @ 2026-08-18 13:13 UTC (permalink / raw)
To: pgsql-hackers@lists.postgresql.org; +Cc: Ayush Tiwari <ayushtiwari.slg01@gmail.com>
The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: not tested
Documentation: not tested
Hello,
I have reviewed this patch and it looks good to me.
I have reproduced it on master branch and applying patch has fixed the bug.
I have neither tested SQL compliance nor documentation: I think these steps are not needed for this bug fix.
Regards
Pierre Forstmann.
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2026-08-18 13:13 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-08-02 17:47 BUG #19597: getQuadrant: impossible case is reachable PG Bug reporting form <noreply@postgresql.org>
2026-08-02 20:31 ` Ayush Tiwari <ayushtiwari.slg01@gmail.com>
2026-08-02 21:22 ` Andrey Rachitskiy <pl0h0yp1@gmail.com>
2026-08-18 13:13 ` Pierre Forstmann <pierre.forstmann@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox