From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
To: Teodor Sigaev <teodor@sigaev.ru>
Cc: Pgsql Hackers <pgsql-hackers@postgresql.org>
Subject: Re: KNNGiST for knn-search
Date: Tue, 24 Nov 2009 09:33:04 +0200
Message-ID: <4B0B8C30.2080400@enterprisedb.com> (raw)
In-Reply-To: <4B0AC9E1.5050509@sigaev.ru>
References: <4B0AC9E1.5050509@sigaev.ru>
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
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-hackers@postgresql.org
Cc: heikki.linnakangas@enterprisedb.com, teodor@sigaev.ru
Subject: Re: KNNGiST for knn-search
In-Reply-To: <4B0B8C30.2080400@enterprisedb.com>
* 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