Re: BUG #19597: getQuadrant: impossible case is reachable
Re: BUG #19597: getQuadrant: impossible case is reachable
От:
John Naylor <johncnaylorls@gmail.com>
Дата:
On Mon, Aug 3, 2026 at 4:22 AM Andrey Rachitskiy wrote: > 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. Note: "on top of" implies applying both -- v1 and then v2. v2 is independent, and CI applies only the latest. "not mutually exhaustive near some power-of-two boundaries" The reporter stumbled across something interesting, but you actually don't need to be near a boundary: drop table if exists g2; create table g2(p point); insert into g2 select point(10000000000 + i* 0.001, 5) from generate_series(1,3000) i; create index on g2 using spgist(p); ERROR: getQuadrant: impossible case Note also that this doesn't need a separate insert. I found on master and REL_18_STABLE that the reporter's case didn't need one either -- the error happened for me already when building the index. What I think is happening (from rubber-ducking with Claude): picksplit() calculates the centroid as the mean of a page of points. For this binade [2^33, 2^34), where both 17179869183.999998 and 10000000000 are found, the error happens if any point on that page is exactly 1 ulp (unit in the last place) from the centroid, or 1.9e-6. This is because this ulp is between EPSILON and 2*EPSILON. A point exactly 1 ulp from the centroid is then more than EPSILON away, so FPeq is false. But centroid +/- EPSILON rounds onto that point, so FPgt and FPlt are false too. Other binades have similar gaps, but it's probably harder to use them to reach this elog from SQL. > 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. + 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; I preferred the style of Ayush's patch. -- this looks really different from the coding for the fuzzy case. Let's make the exact stanza similar to the fuzzy stanza, including testing y before x. -- John Naylor Amazon Web Services
Re: BUG #19597: getQuadrant: impossible case is reachable
Hi, On Tue, 29 Sept 2026 at 19:09, John Naylor wrote: > > On Mon, Aug 3, 2026 at 4:22 AM Andrey Rachitskiy wrote: > > 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. > > Note: "on top of" implies applying both -- v1 and then v2. v2 is > independent, and CI applies only the latest. > > "not mutually exhaustive near some power-of-two boundaries" > > The reporter stumbled across something interesting, but you actually > don't need to be near a boundary: > > drop table if exists g2; > create table g2(p point); > insert into g2 select point(10000000000 + i* 0.001, 5) > from generate_series(1,3000) i; > create index on g2 using spgist(p); > ERROR: getQuadrant: impossible case > > Note also that this doesn't need a separate insert. I found on master > and REL_18_STABLE that the reporter's case didn't need one either -- > the error happened for me already when building the index. > > What I think is happening (from rubber-ducking with Claude): > picksplit() calculates the centroid as the mean of a page of points. > For this binade [2^33, 2^34), where both 17179869183.999998 and > 10000000000 are found, the error happens if any point on that page is > exactly 1 ulp (unit in the last place) from the centroid, or 1.9e-6. > This is because this ulp is between EPSILON and 2*EPSILON. A point > exactly 1 ulp from the centroid is then more than EPSILON away, so > FPeq is false. But centroid +/- EPSILON rounds onto that point, so > FPgt and FPlt are false too. Other binades have similar gaps, but it's > probably harder to use them to reach this elog from SQL. > > > 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. > > + 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; > > I preferred the style of Ayush's patch. -- this looks really different > from the coding for the fuzzy case. Let's make the exact stanza > similar to the fuzzy stanza, including testing y before x. Thanks a lot for the review, John! Attaching v3 with updated test case and earlier fuzzy comparisons. Regards, Ayush
Re: BUG #19597: getQuadrant: impossible case is reachable
On Tue, Sep 29, 2026 at 9:59 PM Ayush Tiwari
wrote:
> Thanks a lot for the review, John!
>
> Attaching v3 with updated test case and earlier fuzzy comparisons.
In the attached v4, 0001 is like v3 but with a smaller test case with
non-huge numbers (back to using a separate insert):
create table spgist_quad_fp_tbl(p point);
insert into spgist_quad_fp_tbl select point(i, 5) from
generate_series(1, 300) i;
create index spgist_quad_fp_idx on spgist_quad_fp_tbl using spgist(p);
insert into spgist_quad_fp_tbl values (point(3, 5 + 1e-6::float8));
Unfortunately, we're not out of the woods yet. With v3, it's possible
to create indexes that were not possible before, but we can still get
the wrong answer when searching. Some LLM-assisted review and fuzzing
found this test case:
-- same table as above
insert into spgist_quad_fp_tbl values (point(114 - 5e-7, 5 + 1e-6::float8));
set enable_indexscan = off;
select count(*) from spgist_quad_fp_tbl
where p <@ box(point(113.999999, 5.0000004), point(113.9999999, 5.0000016));
count
-------
1
(1 row)
reset enable_indexscan;
set enable_seqscan = off;
select count(*) from spgist_quad_fp_tbl
where p <@ box(point(113.999999, 5.0000004), point(113.9999999, 5.0000016));
count
-------
0
(1 row)
reset all;
v4 0002 fixes this case (note for those following along: needs a
reindex between 0001 and 0002 for it to give the right answer). I've
left 0002 how Claude wrote it for now, but it can probably just be
squashed into 0001. I'm not yet sure if this series fixes all the bugs
in this path, so I'll hold off on polishing and committing just yet.
I may have found 3 other possible bugs involving SP-Gist in the course
of investigating this, so I will share those in separate threads when
I return to this topic.
--
John Naylor
Amazon Web Services
Re: BUG #19597: getQuadrant: impossible case is reachable
От:
John Naylor <johncnaylorls@gmail.com>
Дата:
On Thu, Oct 8, 2026 at 2:10 PM John Naylor wrote: > v4 0002 fixes this case (note for those following along: needs a > reindex between 0001 and 0002 for it to give the right answer). I've > left 0002 how Claude wrote it for now, but it can probably just be > squashed into 0001. I'm not yet sure if this series fixes all the bugs > in this path, so I'll hold off on polishing and committing just yet. Further fuzzing didn't find any more bugs (in this path), so pushed after simplifying some comments. -- John Naylor Amazon Web Services
Re: BUG #19597: getQuadrant: impossible case is reachable
От:
Ayush Tiwari <ayushtiwari.slg01@gmail.com>
Дата:
Hi, On Wed, 14 Oct 2026 at 17:33, John Naylor wrote: > > On Thu, Oct 8, 2026 at 2:10 PM John Naylor wrote: > > v4 0002 fixes this case (note for those following along: needs a > > reindex between 0001 and 0002 for it to give the right answer). I've > > left 0002 how Claude wrote it for now, but it can probably just be > > squashed into 0001. I'm not yet sure if this series fixes all the bugs > > in this path, so I'll hold off on polishing and committing just yet. > > Further fuzzing didn't find any more bugs (in this path), so pushed > after simplifying some comments. Thanks a lot for taking care of this, John! Regards, Ayush