Re: KNNGiST for knn-search

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