Incorrect behaviour when using a GiST index on points

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

Alexander Korotkov <aekorotkov@gmail.com> writes:

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

On Mon, Feb 20, 2012 at 7:22 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Alexander Korotkov <aekorotkov@gmail.com> writes:

On Thu, Feb 16, 2012 at 11:43 AM, Alexander Korotkov
<aekorotkov@gmail.com>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.0000009,1.0000009),
point(1.0000009,1.0000009)));
INSERT 0 1
test=# select * from test where a && box(point(1.0000018,1.0000018),
point(1.0000018,1.0000018));
a
---------------------------------------------
(1.0000009,1.0000009),(1.0000009,1.0000009)
(1 row)

test=# set enable_seqscan = off;
SET
test=# select * from test where a && box(point(1.0000018,1.0000018),
point(1.0000018,1.0000018));
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.

Attached patch fixes GiST behaviour without altering operators behaviour.

------
With best regards,
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.

On Mon, Mar 12, 2012 at 3:50 PM, Alexander Korotkov <aekorotkov@gmail.com>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.

On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov <aekorotkov@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.

On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:

On Wed, Feb 22, 2012 at 5:56 PM, Alexander Korotkov <aekorotkov@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

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
<aekorotkov@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

On Tue, Jul 3, 2012 at 11:34 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jun 21, 2012 at 2:53 PM, Alexander Korotkov
<aekorotkov@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

Yes, it's a bug and it needs to be applied !

Oleg Bartunov <obartunov@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

On Tue, Jul 3, 2012 at 7:58 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Oleg Bartunov <obartunov@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.

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 <aekorotkov@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);
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

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

Bruce Momjian <bruce@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

On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote:

Bruce Momjian <bruce@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 <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Mon, Aug 27, 2012 at 07:43:49PM -0400, Tom Lane wrote:

Bruce Momjian <bruce@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 <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane <tgl@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

Robert Haas <robertmhaas@gmail.com> writes:

On Mon, Aug 27, 2012 at 7:43 PM, Tom Lane <tgl@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