Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Alexander Korotkov writes: > On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch wrote: >> ... At internal pages, gist_point_consistent() should implement >> "point <@ box" with an algorithm near-equivalent to box_overlap(). (As an >> optional deviation, it may use exact comparisons despite box_overlap() using >> fuzzy comparisons.) Looking at the math again, your latest code does achieve >> that, too. I was thrown off by your use of a different, albeit >> mathematically >> equivalent, algorithm from the one used in box_overlap(). Please don't do >> that; either use box_overlap()'s algorithm here, or change box_overlap() to >> use the shorter algorithm you have introduced. Formulating the same >> calculation differently in related code is a recipe for confusion. (Then >> again, perhaps the equivalence of the algorithms is obvious to everyone >> entitled to travel within 1 km of the geometric type implementation.) > I've added comment for clarifying this situation. Applied and back-patched with some cosmetic changes (mostly the comments) and a better version of the regression test. As a separate commit, I also simplified box_overlap() to match this logic, since I agree with Noah that it's not good for them to look so different. Besides, it should be at least a bit faster this way. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Sun, Nov 04, 2012 at 01:53:19AM +0400, Alexander Korotkov wrote:
> On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch wrote:
> > I was thrown off by your use of a different, albeit
> > mathematically
> > equivalent, algorithm from the one used in box_overlap(). Please don't do
> > that; either use box_overlap()'s algorithm here, or change box_overlap() to
> > use the shorter algorithm you have introduced. Formulating the same
> > calculation differently in related code is a recipe for confusion. (Then
> > again, perhaps the equivalence of the algorithms is obvious to everyone
> > entitled to travel within 1 km of the geometric type implementation.)
> >
>
> I've added comment for clarifying this situation.
Good enough.
> ! * This code repeats logic of on_ob which
> checks if point is
Typo: the function is on_pb().
> + -- Testing GiST indexes provides same behaviour as sequential scan
> + SET enable_seqscan TO false;
> + CREATE TABLE POINT_GIST_TBL(f1 point);
> + INSERT INTO POINT_GIST_TBL (SELECT '(0,0)' FROM generate_series(0,1000));
> + CREATE INDEX POINT_GIST_TBL_INDEX ON POINT_GIST_TBL USING gist (f1);
> + INSERT INTO POINT_GIST_TBL VALUES ('(0.009,0.009)');
> + SELECT COUNT(*) FROM POINT_GIST_TBL WHERE f1 ~=
> '(0.009,0.009)'::point;
> + SELECT COUNT(*) FROM POINT_GIST_TBL WHERE f1 <@
> '(0.009,0.009),(0.009,0.009)'::box;
> + SELECT COUNT(*) FROM POINT_GIST_TBL WHERE f1 ~=
> '(0.018,0.018)'::point;
Do a "RESET enable_seqscan;" at the end. The omission has no consequence here
since these are the last commands of the test file.
Neither of those things are important enough to call for a new version; I'm
leaving the patch Ready for Committer.
Thanks,
nm
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch wrote: > On Fri, Nov 02, 2012 at 09:01:17PM +0400, Alexander Korotkov wrote: > > On Fri, Nov 2, 2012 at 4:46 PM, Noah Misch wrote: > > > On Fri, Nov 02, 2012 at 04:05:30PM +0400, Alexander Korotkov wrote: > > > > On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch > wrote: > > > > > > > > > --- 1339,1356 > > > > > > *recheck = false; > > > > > > break; > > > > > > case BoxStrategyNumberGroup: > > > > > > ! /* > > > > > > ! * This code repeats logic of on_ob which > uses > > > > > simple comparison > > > > > > ! * rather than FP* functions. > > > > > > ! */ > > > > > > ! query = PG_GETARG_BOX_P(1); > > > > > > ! key = DatumGetBoxP(entry->key); > > > > > > ! > > > > > > ! *recheck = false; > > > > > > ! result = key->high.x >= query->low.x && > > > > > > ! key->low.x <= > query->high.x && > > > > > > ! key->high.y >= > query->low.y && > > > > > > ! key->low.y <= > query->high.y; > > > > > > > > > > For leaf entries, this correctly degenerates to on_pb(). For > internal > > > > > entries, it must, but does not, implement box_overlap(). (The > fuzzy > > > > > box_overlap() would be fine.) > > > > It > > > remains that the code here must somehow implement a box_overlap()-style > > > calculation for internal pages. > > > > > > > Sorry, didn't understand this point. What exactly do you mean by > > box_overlap()-style? > > point_ops index entries have type "box". On leaf pages, the box for each > entry is trivial, having high == low. At leaf pages, > gist_point_consistent() > should implement "point <@ box" with an algorithm equivalent to on_pb(); > your > latest code achieves that. In internal pages, the box for each entry is > rarely trivial; it spans all points stored on the leaf page reachable > through > its downlink. At internal pages, gist_point_consistent() should implement > "point <@ box" with an algorithm near-equivalent to box_overlap(). (As an > optional deviation, it may use exact comparisons despite box_overlap() > using > fuzzy comparisons.) Looking at the math again, your latest code does > achieve > that, too. I was thrown off by your use of a different, albeit > mathematically > equivalent, algorithm from the one used in box_overlap(). Please don't do > that; either use box_overlap()'s algorithm here, or change box_overlap() to > use the shorter algorithm you have introduced. Formulating the same > calculation differently in related code is a recipe for confusion. (Then > again, perhaps the equivalence of the algorithms is obvious to everyone > entitled to travel within 1 km of the geometric type implementation.) > I've added comment for clarifying this situation. -- With best regards, Alexander Korotkov. gistproc_fix-3.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Fri, Nov 02, 2012 at 09:01:17PM +0400, Alexander Korotkov wrote: > On Fri, Nov 2, 2012 at 4:46 PM, Noah Misch wrote: > > On Fri, Nov 02, 2012 at 04:05:30PM +0400, Alexander Korotkov wrote: > > > On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch wrote: > > > > > > > --- 1339,1356 > > > > > *recheck = false; > > > > > break; > > > > > case BoxStrategyNumberGroup: > > > > > ! /* > > > > > ! * This code repeats logic of on_ob which uses > > > > simple comparison > > > > > ! * rather than FP* functions. > > > > > ! */ > > > > > ! query = PG_GETARG_BOX_P(1); > > > > > ! key = DatumGetBoxP(entry->key); > > > > > ! > > > > > ! *recheck = false; > > > > > ! result = key->high.x >= query->low.x && > > > > > ! key->low.x <= query->high.x && > > > > > ! key->high.y >= query->low.y && > > > > > ! key->low.y <= query->high.y; > > > > > > > > For leaf entries, this correctly degenerates to on_pb(). For internal > > > > entries, it must, but does not, implement box_overlap(). (The fuzzy > > > > box_overlap() would be fine.) > > It > > remains that the code here must somehow implement a box_overlap()-style > > calculation for internal pages. > > > > Sorry, didn't understand this point. What exactly do you mean by > box_overlap()-style? point_ops index entries have type "box". On leaf pages, the box for each entry is trivial, having high == low. At leaf pages, gist_point_consistent() should implement "point <@ box" with an algorithm equivalent to on_pb(); your latest code achieves that. In internal pages, the box for each entry is rarely trivial; it spans all points stored on the leaf page reachable through its downlink. At internal pages, gist_point_consistent() should implement "point <@ box" with an algorithm near-equivalent to box_overlap(). (As an optional deviation, it may use exact comparisons despite box_overlap() using fuzzy comparisons.) Looking at the math again, your latest code does achieve that, too. I was thrown off by your use of a different, albeit mathematically equivalent, algorithm from the one used in box_overlap(). Please don't do that; either use box_overlap()'s algorithm here, or change box_overlap() to use the shorter algorithm you have introduced. Formulating the same calculation differently in related code is a recipe for confusion. (Then again, perhaps the equivalence of the algorithms is obvious to everyone entitled to travel within 1 km of the geometric type implementation.) Thanks, nm -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Fri, Nov 2, 2012 at 4:46 PM, Noah Misch wrote: > On Fri, Nov 02, 2012 at 04:05:30PM +0400, Alexander Korotkov wrote: > > On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch wrote: > > > > > --- 1339,1356 > > > > *recheck = false; > > > > break; > > > > case BoxStrategyNumberGroup: > > > > ! /* > > > > ! * This code repeats logic of on_ob which uses > > > simple comparison > > > > ! * rather than FP* functions. > > > > ! */ > > > > ! query = PG_GETARG_BOX_P(1); > > > > ! key = DatumGetBoxP(entry->key); > > > > ! > > > > ! *recheck = false; > > > > ! result = key->high.x >= query->low.x && > > > > ! key->low.x <= query->high.x && > > > > ! key->high.y >= query->low.y && > > > > ! key->low.y <= query->high.y; > > > > > > For leaf entries, this correctly degenerates to on_pb(). For internal > > > entries, it must, but does not, implement box_overlap(). (The fuzzy > > > box_overlap() would be fine.) I recommend making > gist_point_consistent()'s > > > treatment of boxes resemble its treatment of circles and polygons; that > > > eases > > > verifying their correctness. Call gist_box_consistent. Then, for leaf > > > entries, call box_contain_pt(). > > > > > > > I have two objections on doing that: > > 1) It's not evident for me that fuzzy comparison in internal pages is > fine. > > Obviously, it depends on data distribution. It's easy to provide an > example > > when fuzzy comparison will lead to significant performance degradation. > > 2) With PolygonStrategyNumberGroup CircleStrategyNumberGroup it's faster > to > > do simple box comparison than doing calculation for exact circle and > > especially polygon check. In this case previous filtering in leaf pages > > looks reasonable. With BoxStrategyNumberGroup exact calculation is > simpler > > than gist_box_consistent. > > That's fair; I withdraw the recommendation to use gist_box_consistent(). > It > remains that the code here must somehow implement a box_overlap()-style > calculation for internal pages. > Sorry, didn't understand this point. What exactly do you mean by box_overlap()-style? -- With best regards, Alexander Korotkov.
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Fri, Nov 02, 2012 at 04:05:30PM +0400, Alexander Korotkov wrote: > On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch wrote: > > > --- 1339,1356 > > > *recheck = false; > > > break; > > > case BoxStrategyNumberGroup: > > > ! /* > > > ! * This code repeats logic of on_ob which uses > > simple comparison > > > ! * rather than FP* functions. > > > ! */ > > > ! query = PG_GETARG_BOX_P(1); > > > ! key = DatumGetBoxP(entry->key); > > > ! > > > ! *recheck = false; > > > ! result = key->high.x >= query->low.x && > > > ! key->low.x <= query->high.x && > > > ! key->high.y >= query->low.y && > > > ! key->low.y <= query->high.y; > > > > For leaf entries, this correctly degenerates to on_pb(). For internal > > entries, it must, but does not, implement box_overlap(). (The fuzzy > > box_overlap() would be fine.) I recommend making gist_point_consistent()'s > > treatment of boxes resemble its treatment of circles and polygons; that > > eases > > verifying their correctness. Call gist_box_consistent. Then, for leaf > > entries, call box_contain_pt(). > > > > I have two objections on doing that: > 1) It's not evident for me that fuzzy comparison in internal pages is fine. > Obviously, it depends on data distribution. It's easy to provide an example > when fuzzy comparison will lead to significant performance degradation. > 2) With PolygonStrategyNumberGroup CircleStrategyNumberGroup it's faster to > do simple box comparison than doing calculation for exact circle and > especially polygon check. In this case previous filtering in leaf pages > looks reasonable. With BoxStrategyNumberGroup exact calculation is simpler > than gist_box_consistent. That's fair; I withdraw the recommendation to use gist_box_consistent(). It remains that the code here must somehow implement a box_overlap()-style calculation for internal pages. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch wrote:
> On Thu, Oct 11, 2012 at 07:17:28AM -0400, Noah Misch wrote:
> > On Tue, Oct 02, 2012 at 01:58:40PM -0400, Noah Misch wrote:
> > > > > On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane
> wrote:
> > > > >> There's also the big-picture question of whether we should just
> get rid
> > > > >> of fuzzy comparisons in the geometric types instead of trying to
> hack
> > > > >> indexes to work around them.
> >
> > > In any event, I think we should entertain a patch to make the GiST
> operator
> > > class methods bug-compatible with corresponding operators. Even if we
> decide
> > > to change operator behavior in HEAD, the back branches could use it.
> >
> > We have broad agreement that the specific implementation of fuzz in
> geometric
> > comparison operators is shoddy, but nobody has voiced interest in
> designing a
> > concrete improvement. I propose adding a TODO item "Remove or improve
> > rounding in geometric comparison operators", endorsing Alexander's
> design, and
> > reviewing his patch. Objections?
>
> TODO added, and here's a review:
>
> The patch adds no regression tests; it should add tests illustrating the
> problems it fixes.
>
I've added some tests to points.sql.
> I audited the other indexable geometric operators for similar problems.
> This
> passage in gist_point_consistent_internal(), which handles (point,point)
> operators, caught my suspicion:
>
> case RTSameStrategyNumber:
> if (isLeaf)
> {
> result = FPeq(key->low.x, query->x)
> && FPeq(key->low.y, query->y);
> }
> else
> {
> result = (query->x <= key->high.x &&
> query->x >= key->low.x &&
> query->y <= key->high.y
> && query->y >= key->low.y);
> }
> break;
>
> A leaf entry reachable from an internal entry may fall exactly on the
> internal-entry bounding box. Since we would accept a fuzzy match at the
> leaf
> level, I think we must also accept a fuzzy match at the internal level.
Good catch, fixed.
> > *** a/src/backend/access/gist/gistproc.c
> > --- b/src/backend/access/gist/gistproc.c
>
> > ***
> > *** 1326,1331 gist_point_consistent(PG_FUNCTION_ARGS)
> > --- 1327,1333
> > bool *recheck = (bool *) PG_GETARG_POINTER(4);
> > boolresult;
> > StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
> > + BOX*query, *key;
>
> This function now has "query" variables within subsidiary blocks redundant
> with and masking this one. Avoid doing that.
Fixed.
>
> > switch (strategyGroup)
> > {
> > ***
> > *** 1337,1348 gist_point_consistent(PG_FUNCTION_ARGS)
> > *recheck = false;
> > break;
> > case BoxStrategyNumberGroup:
> > ! result = DatumGetBool(DirectFunctionCall5(
> > !
> gist_box_consistent,
> > !
> PointerGetDatum(entry),
> > !
> PG_GETARG_DATUM(1),
> > !
> Int16GetDatum(RTOverlapStrategyNumber),
> > !
> 0, PointerGetDatum(recheck)));
> > break;
> > case PolygonStrategyNumberGroup:
> > {
> > --- 1339,1356
> > *recheck = false;
> > break;
> > case BoxStrategyNumberGroup:
> > ! /*
> > ! * This code repeats logic of on_ob which uses
> simple comparison
> > ! * rather than FP* functions.
> > ! */
> > ! query = PG_GETARG_BOX_P(1);
> > ! key = DatumGetBoxP(entry->key);
> > !
> > ! *recheck = false;
> > ! result = key->high.x >= query->low.x &&
> > ! key->low.x <= query->high.x &&
> > ! key->high.y >= query->low.y &&
> > ! key->low.y <= query->high.y;
>
> For leaf entries, this correctly degenerates to on_pb(). For internal
> entries, it must, but does not, implement box_overlap(). (The fuzzy
> box_overlap() would be fine.) I recommend making gist_point_consistent()'s
> treatment of boxes resemble its treatment of circles and polygons; that
> eases
> verifying their correctness. Call gist_box_consistent. Then, for leaf
> entries, call box_contain_pt().
>
I have two objections on doing that:
1) It's not evident for me that fuzzy comparison in internal pages is fine.
Obviously, it depends on data distribution. It's easy to provide an example
when fuzzy com
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Oct 23, 2012 at 11:18:48AM -0300, Alvaro Herrera wrote: > Please see downthread -- there is some commentary from Noah ([1] and > others) about the patch itself. As far I understand, some changes are > still needed, and I don't know if the last version submitted is the > version that should be backpatched. We'd best use the same patch for both HEAD and back branches; pg_upgrade would carry forward faulty indexes. pg_upgrade could instead invalidate them, but I don't think the gravity of the problem calls for it. A release note suggesting a REINDEX of affected indexes ought to suffice. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Oleg Bartunov escribió: > Yes, it's a bug and it needs to be applied ! Oleg, This patch has been waiting a long time for some review and commit. Since it fixes existing bugs, it should be backpatched; or at least some people believe it needs to be. Please see downthread -- there is some commentary from Noah ([1] and others) about the patch itself. As far I understand, some changes are still needed, and I don't know if the last version submitted is the version that should be backpatched. But *something* needs to be done about this patch. Since you and Teodor are the guys mostly in charge of GiST, could you please see about finalizing and committing it? Thanks. [1] http://archives.postgresql.org/message-id/20121018191828.gb10...@tornado.leadboat.com > On Tue, Jul 3, 2012 at 7:44 PM, Robert Haas wrote: > > On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane wrote: > >> Robert Haas writes: > >>> On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov > >>> wrote: > I think we definitely should apply this patch before 9.2 release, > because it > is a bug fix. Otherwise people will continue produce incorrect GiST > indexes > with in-core geometrical opclasses until 9.3. Patch is very simple and > only > changes few lines of code. > > Any thoughts? > >> > >>> Do we need to apply this patch to 9.2? > >> > >> It's been like that all along, no? > > > > Yeah, but it seems an awful lot like a bug. In fact... it's hard to > > imagine how it could be any more of a bug than this. -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Thu, Oct 11, 2012 at 07:17:28AM -0400, Noah Misch wrote:
> On Tue, Oct 02, 2012 at 01:58:40PM -0400, Noah Misch wrote:
> > > > On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote:
> > > >> There's also the big-picture question of whether we should just get rid
> > > >> of fuzzy comparisons in the geometric types instead of trying to hack
> > > >> indexes to work around them.
>
> > In any event, I think we should entertain a patch to make the GiST operator
> > class methods bug-compatible with corresponding operators. Even if we
> > decide
> > to change operator behavior in HEAD, the back branches could use it.
>
> We have broad agreement that the specific implementation of fuzz in geometric
> comparison operators is shoddy, but nobody has voiced interest in designing a
> concrete improvement. I propose adding a TODO item "Remove or improve
> rounding in geometric comparison operators", endorsing Alexander's design, and
> reviewing his patch. Objections?
TODO added, and here's a review:
The patch adds no regression tests; it should add tests illustrating the
problems it fixes.
I audited the other indexable geometric operators for similar problems. This
passage in gist_point_consistent_internal(), which handles (point,point)
operators, caught my suspicion:
case RTSameStrategyNumber:
if (isLeaf)
{
result = FPeq(key->low.x, query->x)
&& FPeq(key->low.y, query->y);
}
else
{
result = (query->x <= key->high.x && query->x
>= key->low.x &&
query->y <= key->high.y &&
query->y >= key->low.y);
}
break;
A leaf entry reachable from an internal entry may fall exactly on the
internal-entry bounding box. Since we would accept a fuzzy match at the leaf
level, I think we must also accept a fuzzy match at the internal level.
> *** a/src/backend/access/gist/gistproc.c
> --- b/src/backend/access/gist/gistproc.c
> ***
> *** 1326,1331 gist_point_consistent(PG_FUNCTION_ARGS)
> --- 1327,1333
> bool *recheck = (bool *) PG_GETARG_POINTER(4);
> boolresult;
> StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
> + BOX*query, *key;
This function now has "query" variables within subsidiary blocks redundant
with and masking this one. Avoid doing that.
>
> switch (strategyGroup)
> {
> ***
> *** 1337,1348 gist_point_consistent(PG_FUNCTION_ARGS)
> *recheck = false;
> break;
> case BoxStrategyNumberGroup:
> ! result = DatumGetBool(DirectFunctionCall5(
> !
> gist_box_consistent,
> !
> PointerGetDatum(entry),
> !
> PG_GETARG_DATUM(1),
> !
> Int16GetDatum(RTOverlapStrategyNumber),
> !
>0, PointerGetDatum(recheck)));
> break;
> case PolygonStrategyNumberGroup:
> {
> --- 1339,1356
> *recheck = false;
> break;
> case BoxStrategyNumberGroup:
> ! /*
> ! * This code repeats logic of on_ob which uses simple
> comparison
> ! * rather than FP* functions.
> ! */
> ! query = PG_GETARG_BOX_P(1);
> ! key = DatumGetBoxP(entry->key);
> !
> ! *recheck = false;
> ! result = key->high.x >= query->low.x &&
> ! key->low.x <= query->high.x &&
> ! key->high.y >= query->low.y &&
> ! key->low.y <= query->high.y;
For leaf entries, this correctly degenerates to on_pb(). For internal
entries, it must, but does not, implement box_overlap(). (The fuzzy
box_overlap() would be fine.) I recommend making gist_point_consistent()'s
treatment of boxes resemble its treatment of circles and polygons; that eases
verifying their correctness. Call gist_box_consistent. Then, for leaf
entries, call box_contain_pt().
GiST "consistent" functions often validate the strategy number, but the
circle, polygon and box branches of gist_point_consistent silently assum
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Oct 02, 2012 at 01:58:40PM -0400, Noah Misch wrote: > > > On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote: > > >> There's also the big-picture question of whether we should just get rid > > >> of fuzzy comparisons in the geometric types instead of trying to hack > > >> indexes to work around them. > In any event, I think we should entertain a patch to make the GiST operator > class methods bug-compatible with corresponding operators. Even if we decide > to change operator behavior in HEAD, the back branches could use it. We have broad agreement that the specific implementation of fuzz in geometric comparison operators is shoddy, but nobody has voiced interest in designing a concrete improvement. I propose adding a TODO item "Remove or improve rounding in geometric comparison operators", endorsing Alexander's design, and reviewing his patch. Objections? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Aug 28, 2012 at 05:04:09PM -0400, Tom Lane wrote: > Robert Haas writes: > > On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote: > >> There's also the big-picture question of whether we should just get rid > >> of fuzzy comparisons in the geometric types instead of trying to hack > >> indexes to work around them. > > > +1 for that approach, but only if I don't have to do the work. I agree in the abstract; why should a point (position on a 2D plane) compare fuzzily while a float8 (position on a 1D number line) does not? But ... > > Otherwise, +1 for doing the simplest thing that we're sure will > > eliminate wrong answers. > > What we're forced to speculate about here is how many applications out > there are relying on fuzzy comparison to get answers they like, versus > how many are getting answers they don't like because of it. The fact > that the underlying storage is float8 not numeric suggests there are > probably some cases where fuzzy is helpful. ... yes. Having never used these types in practice, I won't venture a guess. Anyone else? > I've never cared for the particulars of the way the fuzzy comparisons > are done, in any case: using an absolute rather than relative error > threshold is wrong according to every numerical analysis principle > I know. Definitely. > The long and the short of it is that it will probably take a significant > investment of work to make something that's clearly better. If that > weren't the case, we'd have done something long ago. In any event, I think we should entertain a patch to make the GiST operator class methods bug-compatible with corresponding operators. Even if we decide to change operator behavior in HEAD, the back branches could use it. Thanks, nm -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Aug 28, 2012 at 5:04 PM, Tom Lane wrote: > Robert Haas writes: >> On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote: >>> There's also the big-picture question of whether we should just get rid >>> of fuzzy comparisons in the geometric types instead of trying to hack >>> indexes to work around them. > >> +1 for that approach, but only if I don't have to do the work. >> Otherwise, +1 for doing the simplest thing that we're sure will >> eliminate wrong answers. > > What we're forced to speculate about here is how many applications out > there are relying on fuzzy comparison to get answers they like, versus > how many are getting answers they don't like because of it. The fact > that the underlying storage is float8 not numeric suggests there are > probably some cases where fuzzy is helpful. I figured it mostly ended up that way because most of the geometic datatypes are built on top of float8s, and most of the GiST distance metrics are therefore a float8 distance. But I must be confused, because surely we don't need to remove the option to express the penalty as a float8, only the prohibition on using anything else. In which case this next part seems like a non-issue: > Another issue here is that even if we agree that simple comparisons > (operator complexity up to about the limit of what an index might > support) should be exact, there's something to be said for fuzzy > computations for operators like whether a point falls on a line. > Internal roundoff error makes that problematic even if you assume > that the inputs are exact. > I've never cared for the particulars of the way the fuzzy comparisons > are done, in any case: using an absolute rather than relative error > threshold is wrong according to every numerical analysis principle > I know. Yeah, that seemed odd to me, too. > The long and the short of it is that it will probably take a significant > investment of work to make something that's clearly better. If that > weren't the case, we'd have done something long ago. Perhaps, but this patch has been kicking around for 7 months without any on-list review, so there might also be a lack of interest in fixing the problem. :-( -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Robert Haas writes: > On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote: >> There's also the big-picture question of whether we should just get rid >> of fuzzy comparisons in the geometric types instead of trying to hack >> indexes to work around them. > +1 for that approach, but only if I don't have to do the work. > Otherwise, +1 for doing the simplest thing that we're sure will > eliminate wrong answers. What we're forced to speculate about here is how many applications out there are relying on fuzzy comparison to get answers they like, versus how many are getting answers they don't like because of it. The fact that the underlying storage is float8 not numeric suggests there are probably some cases where fuzzy is helpful. Another issue here is that even if we agree that simple comparisons (operator complexity up to about the limit of what an index might support) should be exact, there's something to be said for fuzzy computations for operators like whether a point falls on a line. Internal roundoff error makes that problematic even if you assume that the inputs are exact. I've never cared for the particulars of the way the fuzzy comparisons are done, in any case: using an absolute rather than relative error threshold is wrong according to every numerical analysis principle I know. The long and the short of it is that it will probably take a significant investment of work to make something that's clearly better. If that weren't the case, we'd have done something long ago. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane wrote: > There's also the big-picture question of whether we should just get rid > of fuzzy comparisons in the geometric types instead of trying to hack > indexes to work around them. +1 for that approach, but only if I don't have to do the work. Otherwise, +1 for doing the simplest thing that we're sure will eliminate wrong answers. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote: > Bruce Momjian writes: > > I need someone to review this patch for 9.3. We have already missed > > fixing this for 9.2. > > So put it in the next commitfest. Done. I have linked to your comment below too. --- > FWIW, I looked at this last week, and concluded I didn't have enough > confidence in it to push it into 9.2 at the last minute. > > There's also the big-picture question of whether we should just get rid > of fuzzy comparisons in the geometric types instead of trying to hack > indexes to work around them. I'd really rather have us debate that > question and resolve it one way or the other before spending time on the > details of patches that take the second approach. > > regards, tom lane -- Bruce Momjian http://momjian.us EnterpriseDB http://enterprisedb.com + It's impossible for everything to be true. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote: > Bruce Momjian writes: > > I need someone to review this patch for 9.3. We have already missed > > fixing this for 9.2. > > So put it in the next commitfest. > > FWIW, I looked at this last week, and concluded I didn't have enough > confidence in it to push it into 9.2 at the last minute. > > There's also the big-picture question of whether we should just get rid > of fuzzy comparisons in the geometric types instead of trying to hack > indexes to work around them. I'd really rather have us debate that > question and resolve it one way or the other before spending time on the > details of patches that take the second approach. Done. -- Bruce Momjian http://momjian.us EnterpriseDB http://enterprisedb.com + It's impossible for everything to be true. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Bruce Momjian writes: > I need someone to review this patch for 9.3. We have already missed > fixing this for 9.2. So put it in the next commitfest. FWIW, I looked at this last week, and concluded I didn't have enough confidence in it to push it into 9.2 at the last minute. There's also the big-picture question of whether we should just get rid of fuzzy comparisons in the geometric types instead of trying to hack indexes to work around them. I'd really rather have us debate that question and resolve it one way or the other before spending time on the details of patches that take the second approach. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
I need someone to review this patch for 9.3. We have already missed
fixing this for 9.2.
---
On Thu, Jun 21, 2012 at 10:53:43PM +0400, Alexander Korotkov wrote:
> On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov
> wrote:
>
> Attached patch fixes GiST behaviour without altering operators behaviour.
>
>
> I think we definitely should apply this patch before 9.2 release, because it
> is
> a bug fix. Otherwise people will continue produce incorrect GiST indexes with
> in-core geometrical opclasses until 9.3. Patch is very simple and only changes
> few lines of code.
>
> Any thoughts?
>
> --
> With best regards,
> Alexander Korotkov.
> *** a/src/backend/access/gist/gistproc.c
> --- b/src/backend/access/gist/gistproc.c
> ***
> *** 836,842 gist_box_picksplit(PG_FUNCTION_ARGS)
> }
>
> /*
> ! * Equality method
>*
>* This is used for both boxes and points.
>*/
> --- 836,843
> }
>
> /*
> ! * Equality method. Returns true only when boxes are exact same. We can't
> ! * ignore small extents because of index consistency.
>*
>* This is used for both boxes and points.
>*/
> ***
> *** 848,856 gist_box_same(PG_FUNCTION_ARGS)
> bool *result = (bool *) PG_GETARG_POINTER(2);
>
> if (b1 && b2)
> ! *result = DatumGetBool(DirectFunctionCall2(box_same,
> !
>PointerGetDatum(b1),
> !
>PointerGetDatum(b2)));
> else
> *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
> PG_RETURN_POINTER(result);
> --- 849,857
> bool *result = (bool *) PG_GETARG_POINTER(2);
>
> if (b1 && b2)
> ! *result = (b1->low.x == b2->low.x && b1->low.y == b2->low.y &&
> !b1->high.x == b2->high.x && b1->high.y ==
> b2->high.y)
> ! ? TRUE : FALSE;
> else
> *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
> PG_RETURN_POINTER(result);
> ***
> *** 1326,1331 gist_point_consistent(PG_FUNCTION_ARGS)
> --- 1327,1333
> bool *recheck = (bool *) PG_GETARG_POINTER(4);
> boolresult;
> StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
> + BOX*query, *key;
>
> switch (strategyGroup)
> {
> ***
> *** 1337,1348 gist_point_consistent(PG_FUNCTION_ARGS)
> *recheck = false;
> break;
> case BoxStrategyNumberGroup:
> ! result = DatumGetBool(DirectFunctionCall5(
> !
> gist_box_consistent,
> !
> PointerGetDatum(entry),
> !
> PG_GETARG_DATUM(1),
> !
> Int16GetDatum(RTOverlapStrategyNumber),
> !
>0, PointerGetDatum(recheck)));
> break;
> case PolygonStrategyNumberGroup:
> {
> --- 1339,1356
> *recheck = false;
> break;
> case BoxStrategyNumberGroup:
> ! /*
> ! * This code repeats logic of on_ob which uses simple
> comparison
> ! * rather than FP* functions.
> ! */
> ! query = PG_GETARG_BOX_P(1);
> ! key = DatumGetBoxP(entry->key);
> !
> ! *recheck = false;
> ! result = key->high.x >= query->low.x &&
> ! key->low.x <= query->high.x &&
> ! key->high.y >= query->low.y &&
> ! key->low.y <= query->high.y;
> break;
> case PolygonStrategyNumberGroup:
> {
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
--
Bruce Momjian http://momjian.us
EnterpriseDB http://enterprisedb.com
+ It's impossible for everything to be true. +
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Yes, it's a bug and it needs to be applied ! On Tue, Jul 3, 2012 at 7:44 PM, Robert Haas wrote: > On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane wrote: >> Robert Haas writes: >>> On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov >>> wrote: I think we definitely should apply this patch before 9.2 release, because it is a bug fix. Otherwise people will continue produce incorrect GiST indexes with in-core geometrical opclasses until 9.3. Patch is very simple and only changes few lines of code. Any thoughts? >> >>> Do we need to apply this patch to 9.2? >> >> It's been like that all along, no? > > Yeah, but it seems an awful lot like a bug. In fact... it's hard to > imagine how it could be any more of a bug than this. > > -- > Robert Haas > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Jul 3, 2012 at 7:58 PM, Tom Lane wrote: > Oleg Bartunov writes: > > Yes, it's a bug and it needs to be applied ! > > Well, it needs to be *reviewed* first, and nobody's done that ... > I've discussed it with Teodor privately and he has verified by thoughts. I think if he'll verify it in this thread, it should be enough for review of few lines bugfix. If we say about bugfix I provided for backpatch, it need more detailed review. I was a miss that I didn't add it to current commitfest, will add it to the next one. -- With best regards, Alexander Korotkov.
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Oleg Bartunov writes: > Yes, it's a bug and it needs to be applied ! Well, it needs to be *reviewed* first, and nobody's done that ... regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane wrote: > Robert Haas writes: >> On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov >> wrote: >>> I think we definitely should apply this patch before 9.2 release, because it >>> is a bug fix. Otherwise people will continue produce incorrect GiST indexes >>> with in-core geometrical opclasses until 9.3. Patch is very simple and only >>> changes few lines of code. >>> >>> Any thoughts? > >> Do we need to apply this patch to 9.2? > > It's been like that all along, no? Yeah, but it seems an awful lot like a bug. In fact... it's hard to imagine how it could be any more of a bug than this. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Robert Haas writes: > On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov > wrote: >> I think we definitely should apply this patch before 9.2 release, because it >> is a bug fix. Otherwise people will continue produce incorrect GiST indexes >> with in-core geometrical opclasses until 9.3. Patch is very simple and only >> changes few lines of code. >> >> Any thoughts? > Do we need to apply this patch to 9.2? It's been like that all along, no? I'm feeling hesitant to shove it into 9.2 at this late date. But we should review it and get it into 9.3 early if possible. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov wrote: > On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov > wrote: >> >> Attached patch fixes GiST behaviour without altering operators behaviour. > > > I think we definitely should apply this patch before 9.2 release, because it > is a bug fix. Otherwise people will continue produce incorrect GiST indexes > with in-core geometrical opclasses until 9.3. Patch is very simple and only > changes few lines of code. > > Any thoughts? Do we need to apply this patch to 9.2? -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov wrote: > Attached patch fixes GiST behaviour without altering operators behaviour. > I think we definitely should apply this patch before 9.2 release, because it is a bug fix. Otherwise people will continue produce incorrect GiST indexes with in-core geometrical opclasses until 9.3. Patch is very simple and only changes few lines of code. Any thoughts? -- With best regards, Alexander Korotkov. gistproc_fix.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Mon, Mar 12, 2012 at 3:50 PM, Alexander Korotkov wrote: > I believe that attached version of patch can be backpatched. It fixes this > problem without altering of index building procedure. It just makes checks > in internal pages softener enough to compensate effect of gist_box_same > implementation. > Any comments about this? -- With best regards, Alexander Korotkov.
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
I believe that attached version of patch can be backpatched. It fixes this
problem without altering of index building procedure. It just makes checks
in internal pages softener enough to compensate effect of gist_box_same
implementation.
--
With best regards,
Alexander Korotkov.
*** a/src/backend/access/gist/gistproc.c
--- b/src/backend/access/gist/gistproc.c
***
*** 70,76 gist_box_consistent(PG_FUNCTION_ARGS)
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
PG_RETURN_BOOL(FALSE);
!
/*
* if entry is not leaf, use rtree_internal_consistent, else use
* gist_box_leaf_consistent
--- 70,76
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
PG_RETURN_BOOL(FALSE);
!
/*
* if entry is not leaf, use rtree_internal_consistent, else use
* gist_box_leaf_consistent
***
*** 80,88 gist_box_consistent(PG_FUNCTION_ARGS)
query,
strategy));
else
! PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
query,
strategy));
}
static void
--- 80,102
query,
strategy));
else
! {
! /*
! * Box in internal page can be narrower than box in leaf page not
! * more than EPSILON in each boundary. Do corresponding correction.
! */
! BOX key, *entrykey;
!
! entrykey = DatumGetBoxP(entry->key);
! key.low.x = entrykey->low.x - EPSILON;
! key.low.y = entrykey->low.y - EPSILON;
! key.high.x = entrykey->high.x + EPSILON;
! key.high.y = entrykey->high.y + EPSILON;
!
! PG_RETURN_BOOL(rtree_internal_consistent(&key,
query,
strategy));
+ }
}
static void
***
*** 847,852 gist_box_same(PG_FUNCTION_ARGS)
--- 861,871
BOX *b2 = PG_GETARG_BOX_P(1);
bool *result = (bool *) PG_GETARG_POINTER(2);
+ /*
+ * box_same function allow difference between boxes limited by EPSILON.
+ * Thus box in internal page can be narrower than box in leaf page not
+ * more than EPSILON in each boundary.
+ */
if (b1 && b2)
*result = DatumGetBool(DirectFunctionCall2(box_same,
PointerGetDatum(b1),
***
*** 1072,1077 gist_poly_consistent(PG_FUNCTION_ARGS)
--- 1091,1097
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
POLYGON*query = PG_GETARG_POLYGON_P(1);
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+ BOX key, *entrykey;
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
***
*** 1083,1094 gist_poly_consistent(PG_FUNCTION_ARGS)
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
PG_RETURN_BOOL(FALSE);
/*
* Since the operators require recheck anyway, we can just use
* rtree_internal_consistent even at leaf nodes. (This works in part
* because the index entries are bounding boxes not polygons.)
*/
! result = rtree_internal_consistent(DatumGetBoxP(entry->key),
&(query->boundbox), strategy);
/* Avoid memory leak if supplied poly is toasted */
--- 1103,1128
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
PG_RETURN_BOOL(FALSE);
+ entrykey = DatumGetBoxP(entry->key);
+ if (!GIST_LEAF(entry))
+ {
+ /*
+ * Box in internal page can be narrower than box in leaf page not
+ * more than EPSILON in each boundary. Do corresponding correction.
+ */
+ key.low.x = entrykey->low.x - EPSILON;
+ key.low.y = entrykey->low.y - EPSILON;
+ key.high.x = entrykey->high.x + EPSILON;
+ key.high.y = entrykey->high.y + EPSILON;
+ entrykey = &key;
+ }
+
/*
* Since the operators require recheck anyway, we can just use
* rtree_internal_consistent even at leaf nodes. (This works in part
* because the index entries are bounding boxes not polygons.)
*/
! result = rtree_internal_consistent(entrykey,
&(query->boundbox), strategy);
/* Avoid memory leak if supplied poly is toasted */
***
*** 1152,1158 gist_circle_consistent(PG_FUNCTION_ARGS)
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
! BOX bbox;
bool result;
/* All cases served by this function are inexact */
--- 1186,1192
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
! BOX bbox, *entrykey, key;
bool result;
/* All cases served by this function are inexact */
***
*** 1170,1177 gist_circle_consistent(PG_FUNCTION_ARGS)
bbox.low.x = query->center.x - query->radius;
bbox.high.y = query->center.y + query->radius;
bbox.low.y = query->center.y - query->radius;
! result = rtree_internal_consistent(DatumGetBoxP(entry->key),
&bbox, strategy);
PG_RETURN_BOOL(result);
--- 1204,1225
bbox.low.x = query->center.x - query->radius;
bbox.high.y = query->center.y +
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Attached patch fixes GiST behaviour without altering operators behaviour.
--
With best regards,
Alexander Korotkov.
*** a/src/backend/access/gist/gistproc.c
--- b/src/backend/access/gist/gistproc.c
***
*** 836,842 gist_box_picksplit(PG_FUNCTION_ARGS)
}
/*
! * Equality method
*
* This is used for both boxes and points.
*/
--- 836,843
}
/*
! * Equality method. Returns true only when boxes are exact same. We can't
! * ignore small extents because of index consistency.
*
* This is used for both boxes and points.
*/
***
*** 848,856 gist_box_same(PG_FUNCTION_ARGS)
bool *result = (bool *) PG_GETARG_POINTER(2);
if (b1 && b2)
! *result = DatumGetBool(DirectFunctionCall2(box_same,
! PointerGetDatum(b1),
! PointerGetDatum(b2)));
else
*result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
PG_RETURN_POINTER(result);
--- 849,857
bool *result = (bool *) PG_GETARG_POINTER(2);
if (b1 && b2)
! *result = (b1->low.x == b2->low.x && b1->low.y == b2->low.y &&
! b1->high.x == b2->high.x && b1->high.y == b2->high.y)
! ? TRUE : FALSE;
else
*result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
PG_RETURN_POINTER(result);
***
*** 1326,1331 gist_point_consistent(PG_FUNCTION_ARGS)
--- 1327,1333
bool *recheck = (bool *) PG_GETARG_POINTER(4);
bool result;
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
+ BOX *query, *key;
switch (strategyGroup)
{
***
*** 1337,1348 gist_point_consistent(PG_FUNCTION_ARGS)
*recheck = false;
break;
case BoxStrategyNumberGroup:
! result = DatumGetBool(DirectFunctionCall5(
! gist_box_consistent,
! PointerGetDatum(entry),
! PG_GETARG_DATUM(1),
! Int16GetDatum(RTOverlapStrategyNumber),
! 0, PointerGetDatum(recheck)));
break;
case PolygonStrategyNumberGroup:
{
--- 1339,1356
*recheck = false;
break;
case BoxStrategyNumberGroup:
! /*
! * This code repeats logic of on_ob which uses simple comparison
! * rather than FP* functions.
! */
! query = PG_GETARG_BOX_P(1);
! key = DatumGetBoxP(entry->key);
!
! *recheck = false;
! result = key->high.x >= query->low.x &&
! key->low.x <= query->high.x &&
! key->high.y >= query->low.y &&
! key->low.y <= query->high.y;
break;
case PolygonStrategyNumberGroup:
{
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Mon, Feb 20, 2012 at 7:22 PM, Tom Lane wrote: > Alexander Korotkov writes: > > On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov > > wrote: > >> Described differences leads to incorrect behaviour of GiST index. > >> The question is: what is correct way to fix it? Should on_pb also use > FP* > >> or consistent method should behave like on_pb? > > > Any comments on this? Current behaviour definitely indicates a bug, and > I'm > > ready to fix it. The only question: is this bug in on_pb or gist? > > I'm inclined to think the right answer is to make on_pb use the FP* > macros, for consistency with other geometric operators. But it's worth > asking whether that will actually fix the problem. I've thought for > some time that we'd eventually find cases where geo_ops' use of fuzzy > comparisons breaks index behavior entirely, because it destroys natural > assumptions like the transitive law. So that could eventually lead us > to rip out the FP* macros everywhere. > > In any case, this doesn't seem like something we could back-patch; > it'd be a behavioral change in HEAD only. > Analyzing GiST interface methods more detail I found one other place where fuzzy comparison was used. It is gist_box_same function. And it's really scary thing. It means that entry of internal page is not extended when inserting index tuple extends it in less than EPSILON. Correspondingly current GiST search behaviour is neither exact search or fuzzy search with given EPSILON. It is something in the middle. See following example for proof. test=# create table test(a box); CREATE TABLE test=# insert into test (select (case when i%2= 0 then box(point(1,1),point(1,1)) else box(point(2,2),point(2,2)) end) from generate_series(1,300) i); INSERT 0 300 test=# create index test_idx on test using gist(a); CREATE INDEX test=# test=# insert into test values (box(point(1.009,1.009), point(1.009,1.009))); INSERT 0 1 test=# select * from test where a && box(point(1.018,1.018), point(1.018,1.018)); a - (1.009,1.009),(1.009,1.009) (1 row) test=# set enable_seqscan = off; SET test=# select * from test where a && box(point(1.018,1.018), point(1.018,1.018)); a --- (0 rows) But, I believe we still can bachpatch it in one of following ways: 1) Fix consistent and same functions. Add to release note notice that users should rebuild indexes if they want correct behaviour. 2) Leave same function as is. Add kluges to consistent functions which provides correct search on current not truly correct trees. But anyway +1 for rip out the FP* macros everywhere in HEAD. Because I really dislike the way FP* are currently implemented. Why EPSILON is 1.0E-06? We don't know anything about nature of data that users store in geometrical datatypes. The lesser double precision value is 5E-324. For some datasets EPSILON can easily cover whole range. -- With bestregards, Alexander Korotkov.
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
Alexander Korotkov writes: > On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov > wrote: >> Described differences leads to incorrect behaviour of GiST index. >> The question is: what is correct way to fix it? Should on_pb also use FP* >> or consistent method should behave like on_pb? > Any comments on this? Current behaviour definitely indicates a bug, and I'm > ready to fix it. The only question: is this bug in on_pb or gist? I'm inclined to think the right answer is to make on_pb use the FP* macros, for consistency with other geometric operators. But it's worth asking whether that will actually fix the problem. I've thought for some time that we'd eventually find cases where geo_ops' use of fuzzy comparisons breaks index behavior entirely, because it destroys natural assumptions like the transitive law. So that could eventually lead us to rip out the FP* macros everywhere. In any case, this doesn't seem like something we could back-patch; it'd be a behavioral change in HEAD only. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Incorrect behaviour when using a GiST index on points
On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov wrote: > Described differences leads to incorrect behaviour of GiST index. > The question is: what is correct way to fix it? Should on_pb also use FP* > or consistent method should behave like on_pb? > Any comments on this? Current behaviour definitely indicates a bug, and I'm ready to fix it. The only question: is this bug in on_pb or gist? -- With best regards, Alexander Korotkov.
