Message-ID: <4D5D4FB9.8020709@enterprisedb.com>
Date: Thu, 17 Feb 2011 18:41:29 +0200
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; fi-FI;
	rv:1.9.1.16) Gecko/20101226 Icedove/3.0.11
MIME-Version: 1.0
To: Mark Stosberg <mark@summersault.com>
CC: pgsql-performance@postgresql.org
Subject: Re: application of KNN code to US zipcode searches?
References: <ijjc1o$vgu$1@dough.gmane.org>
	<4D5CE118020000250003AB83@gw.wicourts.gov>
	<ijjecs$e8c$1@dough.gmane.org>
In-Reply-To: <ijjecs$e8c$1@dough.gmane.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

On 17.02.2011 17:20, Mark Stosberg wrote:
>> I thought the benefit of KNN was that you could retrieve the rows in
>> distance order, so that a query for the closest 20 locations (for
>> example) would be very fast.  I wouldn't have expected it to be
>> helpful when you're selecting all the rows regardless of distance.
>
> Kevin,
>
> Thanks for the feedback. You are right that my "reduced test case"
> wasn't a good approximation. I added a limit, to simulate finding the
> 100 zipcodes closest to 90210.
>
> Below I compare 4 approaches to the same query:
>
> 1. Cube search
> 2. Earth Distance Search
> 3. Simple point distance (no index)
> 4. Simple point distance (KNN)
>
> Now KNN benchmarks to be almost 100x faster! That's very promising.
> Then there's only the issue that simple point distance is not expected
> to be a good enough approximation of earth-distances. Perhaps that can
> be solved by pre-computing coordinates based on the lat/long pairs....
> much like the map projections used to present a curved surface on a flat
> map? Given that's OK to be be a few miles off, it seems we have some
> leeway here.
>
> Recommendations?

The existing opclasses only support distance-to-a-point, but I believe 
the KNN gist code is flexible enough that it could be used for distance 
to the edge of a shape as well. Someone just needs to write the 
operators and support functions.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com