Message-ID: <4B0BC854.30705@sigaev.ru>
Date: Tue, 24 Nov 2009 14:49:40 +0300
From: Teodor Sigaev <teodor@sigaev.ru>
User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US;
	rv:1.8.1.23) Gecko/20090909 SeaMonkey/1.1.18
MIME-Version: 1.0
To: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
CC: Pgsql Hackers <pgsql-hackers@postgresql.org>
Subject: Re: KNNGiST for knn-search
References: <4B0AC9E1.5050509@sigaev.ru> <4B0B8C30.2080400@enterprisedb.com>
In-Reply-To: <4B0B8C30.2080400@enterprisedb.com>
Content-Type: text/plain; charset=KOI8-R; format=flowed
Content-Transfer-Encoding: 7bit

> 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.
Of course, right now it is a working prototype.

>> 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?
New algorithm works much more with memory for allocation/free to manage lists 
and it's a single reason of performance loss. Choosing of algorithm could not be 
done by consistent function, it should be done at least in amrescan method or 
even earlier - in planner.


> 
>> 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.
Hmm, I thought about it, but still have no a good idea.
One idea:
SELECT p FROM pt WHERE p << '5.0,5.0'::point ORDER BY (p <-> '5.0,5.0'::point) 
DESC LIMIT 10;
And add <-> to opclass (but for now any indexable operation should return 
boolean type). Of course, KNNGiST should be modified to support not only 
k-nearest search but k-"farest" search and NULLS LAST/FIRST.

Not very convenient, because it's needed to look into expression of ORDER BY. 
And now you can specify p >< 'one point' AND p >< 'another point', but it's 
impossible to do that by ORDER BY clause.

Second idea with non-standard syntax.
SELECT ... ORDER BY PROXIMITY OF expression[, expression [..]] TO expression[, 
expression [..]] USING [operator [, operator [..]]
and operator is distance operator, i.e. it's not a member of btree opclass, but 
returns non-negative float8 value.

Without index it will be essentially the same as
ORDER BY expression operator expression[ + ..] DESC NULLS LAST


-- 
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/