Skip site navigation (1) Skip section navigation (2)

Re: Incorrect behaviour when using a GiST index on points

From: Alexander Korotkov <aekorotkov(at)gmail(dot)com>
To: Noah Misch <noah(at)leadboat(dot)com>
Cc: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Robert Haas <robertmhaas(at)gmail(dot)com>, Bruce Momjian <bruce(at)momjian(dot)us>, Oleg Bartunov <obartunov(at)gmail(dot)com>, Teodor Sigaev <teodor(at)sigaev(dot)ru>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Incorrect behaviour when using a GiST index on points
Date: 2012-11-03 21:53:19
Message-ID: CAPpHfdvJz-PsAqLJg_nTLF32cN6KwL8+-_YvuwY3=N5TmfqGqQ@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Sat, Nov 3, 2012 at 4:23 AM, Noah Misch <noah(at)leadboat(dot)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 <noah(at)leadboat(dot)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 <noah(at)leadboat(dot)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.

Attachment: gistproc_fix-3.patch
Description: application/octet-stream (7.1 KB)

In response to

Responses

pgsql-hackers by date

Next:From: Jeff JanesDate: 2012-11-03 22:26:18
Subject: Re: Synchronous commit not... synchronous?
Previous:From: Florian WeimerDate: 2012-11-03 21:44:41
Subject: Re: Synchronous commit not... synchronous?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group