Message-ID: <4B0B8C30.2080400@enterprisedb.com>
Date: Tue, 24 Nov 2009 09:33:04 +0200
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
Organization: EnterpriseDB
User-Agent: Mozilla-Thunderbird 2.0.0.22 (X11/20090706)
MIME-Version: 1.0
To: Teodor Sigaev <teodor@sigaev.ru>
CC: Pgsql Hackers <pgsql-hackers@postgresql.org>
Subject: Re: KNNGiST for knn-search
References: <4B0AC9E1.5050509@sigaev.ru>
In-Reply-To: <4B0AC9E1.5050509@sigaev.ru>
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: 7bit

Teodor Sigaev wrote:
> we'd like to present contrib module for CVS HEAD, which contains
> implementation of knn (k nearest neighbourhood) search in PostgreSQL,
> see README.knngist for
> details.

Cool!

> Old way:
> SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist FROM spots
> order by dist asc LIMIT 10;
> 
> Time: 1024.242 ms
> 
> knn-search:
> SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist FROM spots
> WHERE coordinates  >< '5.0,5.0'::point LIMIT 10;
> 
> Time: 3.158 ms

I think you'll need to work on that. A WHERE qual shouldn't imply a sort
order. You'll have to teach the planner how to use the index to speed up
a query in the first form.

> We didn't patch existing implementation of GiST for several reasons:
> 
> 1. KNNGiST is about 5% slower than GiST on non-knn search queries, like
>   contains or contained by, because of some overhead of new algorithm of
>   tree traversal

Is it possible to use the regular GiST traversal algorithm on a
KNNGiST-tree, when performing regular GiST searches that don't require a
particular order?

> 2.  KNNGiST can't be used in  bitmap index scan, which destroys order of
> results,
>   We don't know the way to forbid bitmap index scan only for knn queries.
>   Current version of KNNGiST doesn't distinguish knn-search and usual
> search
>   and postgres doesn't know about ordered output from KNNGiST.

Yeah, you really need to modify the planner to understand the ordering
and plan accordingly.

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