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