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