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 14:37:29 +0200
Message-ID: <4B0BD389.5000509@enterprisedb.com> (raw)
In-Reply-To: <4B0BC854.30705@sigaev.ru>
References: <4B0AC9E1.5050509@sigaev.ru>
<4B0B8C30.2080400@enterprisedb.com>
<4B0BC854.30705@sigaev.ru>
Teodor Sigaev wrote:
>>> 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.
Ok, that sounds good. The bottom line is that you can use the same
on-disk tree with both algorithms. No need for a separate indexam in
that case.
> 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).
You really shouldn't need to have a WHERE clause.
> Of course, KNNGiST should be modified to support
> not only k-nearest search but k-"farest" search and NULLS LAST/FIRST.
Well, as long as the planner knows the capabilities of the indexam, it
can just fall back to a seqscan+sort if the query can't be sped up with
the index.
> And now you can specify p >< 'one point' AND p >< 'another
> point', but it's impossible to do that by ORDER BY clause.
Huh, what does that mean? Is it like "ORDER BY (min( p >< 'one point', p
>< 'another point')" ?
> 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
We already have the syntax to represent the query, using ORDER BY. IMHO
we just need to teach the planner that when it sees a query like that,
it can use a GiST index to speed it up. A number of indexam and operator
class API changes are probably required, but it should be invisible to
the user.
--
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: <4B0BD389.5000509@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