From: Tom Lane <tgl@sss.pgh.pa.us>
To: Marcelo Zabani <mzabani@gmail.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: gist indexes for distance calculations
Date: Thu, 30 Sep 2010 15:16:36 -0400
Message-ID: <11340.1285874196@sss.pgh.pa.us> (raw)
In-Reply-To: <AANLkTikvpQS+1q3HBrVCgCjRF+2-LPGzmVHQO+EJk3QG@mail.gmail.com>
References: <AANLkTikvpQS+1q3HBrVCgCjRF+2-LPGzmVHQO+EJk3QG@mail.gmail.com>
Marcelo Zabani <mzabani@gmail.com> writes:
> CREATE INDEX ON places USING gist (circle(coordinates, 1));
> I'd like to know how this index works, though, as it seems to me the only
> way to have this kind of index to work is to calculate the distance of every
> point in a square of sides 2*1=2 units centered on (a, b).
I believe it is a bounding-box based implementation; that is, each
non-leaf entry in the index stores the bounding box that covers all the
entries in the child page (plus its children if any). So a lookup
descends to only those child pages that could possibly contain entries
overlapping the target circle.
> So, am I wrong to think it works like that? If it does work like that, could
> I have instead two columns of type FLOAT (xcoordinate and ycoordinate) and
> create traditional b-tree indexes on both of these, and then do something
> like:
> SELECT * FROM places WHERE xcoordinate >= (a-1) AND xcoordinate <= (a+1) AND
> ycoordinate >= (b-1) AND ycoordinate <= (b+1) And
> SQRT(POW(a-xcoordinate,2)+POW(b-ycoordinate,2))<=1;
Well, there's nothing stopping you from doing that, but search
performance is likely to be a whole lot worse than with an actual 2-D
index. The reason is that it'll have to fetch index entries for
everything in the vertical strip between a-1 and a+1, as well as
everything in the horizontal strip between b-1 and b+1; most of which is
nowhere near the target. If your circles are always very very small
this might work tolerably, but in most applications the amount of stuff
fetched soon gets out of hand.
regards, tom lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, mzabani@gmail.com
Subject: Re: gist indexes for distance calculations
In-Reply-To: <11340.1285874196@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox