Re: [HACKERS] Incorrect behaviour when using a GiST index on points

2013-02-08 Thread Tom Lane
Alexander Korotkov aekorot...@gmail.com writes:
 On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch n...@leadboat.com 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

2012-11-10 Thread Noah Misch
On Sun, Nov 04, 2012 at 01:53:19AM +0400, Alexander Korotkov wrote:
 On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch n...@leadboat.com 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

2012-11-03 Thread Alexander Korotkov
On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch n...@leadboat.com 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 n...@leadboat.com 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 n...@leadboat.com
 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

2012-11-02 Thread Alexander Korotkov
On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch n...@leadboat.com 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 t...@sss.pgh.pa.us
 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 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 

Re: [HACKERS] Incorrect behaviour when using a GiST index on points

2012-11-02 Thread Noah Misch
On Fri, Nov 02, 2012 at 04:05:30PM +0400, Alexander Korotkov wrote:
 On Thu, Oct 18, 2012 at 11:18 PM, Noah Misch n...@leadboat.com 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

2012-11-02 Thread Alexander Korotkov
On Fri, Nov 2, 2012 at 4:46 PM, Noah Misch n...@leadboat.com 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 n...@leadboat.com 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

2012-10-23 Thread Alvaro Herrera
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 robertmh...@gmail.com wrote:
  On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane t...@sss.pgh.pa.us wrote:
  Robert Haas robertmh...@gmail.com writes:
  On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
  aekorot...@gmail.com 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

2012-10-23 Thread Noah Misch
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

2012-10-18 Thread Noah Misch
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 t...@sss.pgh.pa.us 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 assume
strategy % GeoStrategyNumberOffset == RTContainedByStrategyNumber.  Should
they verify that assumption?  I 

Re: [HACKERS] Incorrect behaviour when using a GiST index on points

2012-10-11 Thread Noah Misch
On Tue, Oct 02, 2012 at 01:58:40PM -0400, Noah Misch wrote:
   On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane t...@sss.pgh.pa.us 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

2012-10-02 Thread Noah Misch
On Tue, Aug 28, 2012 at 05:04:09PM -0400, Tom Lane wrote:
 Robert Haas robertmh...@gmail.com writes:
  On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane t...@sss.pgh.pa.us 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

2012-08-28 Thread Robert Haas
On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane t...@sss.pgh.pa.us 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

2012-08-28 Thread Tom Lane
Robert Haas robertmh...@gmail.com writes:
 On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane t...@sss.pgh.pa.us 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

2012-08-28 Thread Robert Haas
On Tue, Aug 28, 2012 at 5:04 PM, Tom Lane t...@sss.pgh.pa.us wrote:
 Robert Haas robertmh...@gmail.com writes:
 On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane t...@sss.pgh.pa.us 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

2012-08-27 Thread Bruce Momjian

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 aekorot...@gmail.com
 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  br...@momjian.ushttp://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

2012-08-27 Thread Tom Lane
Bruce Momjian br...@momjian.us 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

2012-08-27 Thread Bruce Momjian
On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote:
 Bruce Momjian br...@momjian.us 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  br...@momjian.ushttp://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

2012-08-27 Thread Bruce Momjian
On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote:
 Bruce Momjian br...@momjian.us 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  br...@momjian.ushttp://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

2012-07-06 Thread Oleg Bartunov
Yes, it's a bug and it needs to be applied !

On Tue, Jul 3, 2012 at 7:44 PM, Robert Haas robertmh...@gmail.com wrote:
 On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane t...@sss.pgh.pa.us wrote:
 Robert Haas robertmh...@gmail.com writes:
 On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
 aekorot...@gmail.com 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

2012-07-03 Thread Robert Haas
On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
aekorot...@gmail.com wrote:
 On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov aekorot...@gmail.com
 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

2012-07-03 Thread Tom Lane
Robert Haas robertmh...@gmail.com writes:
 On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
 aekorot...@gmail.com 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

2012-07-03 Thread Robert Haas
On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane t...@sss.pgh.pa.us wrote:
 Robert Haas robertmh...@gmail.com writes:
 On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
 aekorot...@gmail.com 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

2012-07-03 Thread Tom Lane
Oleg Bartunov obartu...@gmail.com 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

2012-07-03 Thread Alexander Korotkov
On Tue, Jul 3, 2012 at 7:58 PM, Tom Lane t...@sss.pgh.pa.us wrote:

 Oleg Bartunov obartu...@gmail.com 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

2012-06-21 Thread Alexander Korotkov
On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov aekorot...@gmail.comwrote:

 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

2012-04-09 Thread Alexander Korotkov
On Mon, Mar 12, 2012 at 3:50 PM, Alexander Korotkov aekorot...@gmail.comwrote:

 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

2012-03-12 Thread Alexander Korotkov
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 + query-radius;
  	bbox.low.y = 

Re: [HACKERS] Incorrect behaviour when using a GiST index on points

2012-02-22 Thread Alexander Korotkov
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

2012-02-20 Thread Alexander Korotkov
On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov
aekorot...@gmail.comwrote:

 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.


Re: [HACKERS] Incorrect behaviour when using a GiST index on points

2012-02-20 Thread Tom Lane
Alexander Korotkov aekorot...@gmail.com writes:
 On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov
 aekorot...@gmail.comwrote:
 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

2012-02-20 Thread Alexander Korotkov
On Mon, Feb 20, 2012 at 7:22 PM, Tom Lane t...@sss.pgh.pa.us wrote:

 Alexander Korotkov aekorot...@gmail.com writes:
  On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov
  aekorot...@gmail.comwrote:
  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.