KNNGiST for knn-search

Started by Teodor Sigaevabout 16 years ago26 messages
#1Teodor Sigaev
teodor@sigaev.ru
1 attachment(s)

Hi there,

http://www.sigaev.ru/misc/knngist-0.11.tar.gz

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. KNNGiST is an extension of existing GiST, which inherits most of
their code, so it's has recovery (WAL-logged) and concurrency support.
Basically, it introduces a new distance-based priority queue tree traversal
algorithm (instead of depth-first in plain GiST), so index scan returns rows
sorted by closiness to a query. Notice, index returns all rows, so one should
use LIMIT clause to specify k (which is usually small) to get real benefits.
We get 300x times better performance on real-life data (about 1 mln points):

Module requires rbtree and point_ops patches applied.
(http://archives.postgresql.org/message-id/4B0A8DFA.7050009@sigaev.ru and
http://archives.postgresql.org/message-id/4B0A8F0F.3020308@sigaev.ru)

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

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
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.

We see several ways to add KNNGiST to PostgreSQL:

1. Patch existing GiST.
Con - see problems above.
Pro - any existing GiST opclasses will work with KNNGiST.

2. add KNNGIST as a contrib module like now.
Con - there is no way in PostgreSQL to test other modules, which depends
on KNNGiST. For example, it's easy to add support for trigrams, but
then we add dependence on contrib/pg_trgm module.

3. add KNNGiST as separate access method into core of PostgreSQL.
We think it the best way, since we don't touch existing GiST and opclasses,
and could use KNNGiST in other contrib modules

Separate problem is query planning.

1. To use KNNGiST we need to use index scan ! To prevent seqscan on table,
operator >< has extremely high cost.
2. To prevent bitmap index scan, KNNGiST doesn't have bitmap index scan
interface at all (no amgetbitmap method).

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

Attachments:

README.knngisttext/plain; name=README.knngistDownload
knngist - contrib module for k-nearest neighbourhood search

Support: The Open Planning Project, Inc.

Module knngist provides:

- KNNGiST access method is an extension of GiST, which implements  k-nearest
 neighbourhood search
- Operator class for KNNGiST for data type points with capability of knn-search
- Operator class for KNNGiST for data type tsvector without capability of knn-search

KNNGiST is inherited from GiST and use the same write methods, so, that KNNGiST 
has recovery (WAL-logged)  and concurrency support.

KNNGiST supports all queries executable by GiST, but with possible 
performance loss.  KNNGiST keeps all features of GiST, such as multicolumn 
indexes with support of any subset of the index's columns, indexing and 
searching of NULL values.

The KNNGiST differs from GiST in:
- search traversal algorithm on tree. While GiST uses first-depth search
  algorithm of KNN version uses traversal priority queue
- consistent user-defined method should return distance of tuple to the query,
  instead of a boolean value as in GiST. However, KNNGiST can use GiST's
  consistent method for additional filtering of result or GiST-alike
  search,  but not for knn-search (for example, tsvector_ops).
- KNNGiST doesn't have amgetbitmap method, because of nature of knn-search.


consistent user-defined method for KNNGiST can return:

 - negative value, which means tuple doesn't match query
   (like false in GiST's consistent)
 - 0.0 means one of:
   - a zero distance (exact match)
   - a match for filtering clause, like a <@ or @> for point.
   KNNGist doesn't distinguish these two cases and relies on user-defined 
   methods
 - positive value, which means the method returns distance. In this case 
   keyRecheck should be false!, since it's impossible to make right order
   with lossy values.

Distance between tuple and query is calculated as a sum of all distances 
(on all keys). Notice, that distance is a numerical (non-negative)
description of how tuple is different from a query and KNNGiST doesn't require, 
that it should follow triangle rule. 

Caveats:

Currently, it's impossible to specify the number of closest neighbourhood
points returned, use LIMIT clause for this. Index ALWAYS returns ALL rows 
in the order of closiness to the given point, so it can be very slow 
without  LIMIT clause.


The module also provides index support for k-nn search for points data type 
using KNNGiST access method.

Operator:

point   >< point   - fake operator, which always returns TRUE

Indexed support for operators:

point	<<  point
point	>>  point
point	<^  point
point	>^  point
point	~=  point
point   <@ box     
box      @> point  
point   <@ polygon 
polygon  @> point  
point   <@ circle  
circle   @> point 

Also, knngist provides support full-text search operator @@  for tsvector 
data type. 


Examples:

We use test database of POI (point of interests), which has 1034170 spots.

First, compare performance of traditional approach and k-nn search.

=#
SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist FROM spots
order by dist asc LIMIT 10;
             coordinates             |       dist
-------------------------------------+------------------
 (3.57192993164062,6.51727240153665) | 2.08362656457647
 (3.49502563476562,6.49134782128243) | 2.11874164636854
 (3.4393,6.4473)                     | 2.12848814420001
 (3.31787109375,6.50089913799597)    | 2.25438592075067
 (2.6323,6.4779)                     | 2.79109148900569
 (2.66349792480469,6.53159856871478) | 2.79374947392946
 (1.84102535247803,6.27874198581057) |  3.4079762161672
 (1.2255,6.1228)                     | 3.93796014327215
 (1.22772216796875,6.15693947094637) | 3.94570513108469
 (9.6977,4.044503)                   | 4.79388775494473
(10 rows)

Time: 1024.242 ms

=#
SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist FROM spots
WHERE coordinates  >< '5.0,5.0'::point LIMIT 10;
             coordinates             |       dist
-------------------------------------+------------------
 (3.57192993164062,6.51727240153665) | 2.08362656457647
 (3.49502563476562,6.49134782128243) | 2.11874164636854
 (3.4393,6.4473)                     | 2.12848814420001
 (3.31787109375,6.50089913799597)    | 2.25438592075067
 (2.6323,6.4779)                     | 2.79109148900569
 (2.66349792480469,6.53159856871478) | 2.79374947392946
 (1.84102535247803,6.27874198581057) |  3.4079762161672
 (1.2255,6.1228)                     | 3.93796014327215
 (1.22772216796875,6.15693947094637) | 3.94570513108469
 (9.6977,4.044503)                   | 4.79388775494473
(10 rows)

Time: 3.158 ms

This query demonstrates 300x perfomance gain due to k-nn search and the gain
will only increases with the growing of table size, both in number of points 
and row length.


Find 10 most closest points to the Eiffel tower in Paris, which has 'mars' in
their address.

=# CREATE INDEX spots_idx ON spots USING knngist (coordinates, to_tsvector('french',address));
=# SELECT id, address,  (coordinates <-> '(2.29470491409302,48.858263472125)'::point) AS dist 
FROM spots WHERE coordinates >< '(2.29470491409302,48.858263472125)'::point 
AND to_tsvector('french',address) @@ to_tsquery('french','mars')  LIMIT 10;
   id    |                           address                           |         dist         
---------+-------------------------------------------------------------+---------------------
  366096 | 1st Floor Tour Eiffel | Champs de Mars, Paris 75007, France | 2.32488941293945e-05
 4356328 | r Champ de Mars 75007 PARIS                                 |  0.00421854756964406
 5200167 | Champ De Mars 75007 Paris                                   |  0.00453564562587288
 9301676 | Champ de Mars, 75007 Paris,                                 |  0.00453564562587288
 2152213 | 16, ave Rapp, Champ de Mars, Tour Eiffel, Paris, France     |  0.00624152097590896
 1923818 | Champ de Mars Paris, France                                 |  0.00838214733539654
 5165953 | 39 Rue Champ De Mars Paris, France                          |  0.00874410234569529
 7395870 | 39 Rue Champ De Mars Paris, France                          |  0.00874410234569529
 4358671 | 32 Rue Champ De Mars Paris, France                          |  0.00876089659276339
 1923742 | 12 rue du Champ de Mars Paris, France                       |  0.00876764731845995
(10 rows)

Time: 7.859 ms

=# EXPLAIN (COSTS OFF) 
SELECT id, address FROM spots WHERE coordinates >< '(2.29470491409302,48.858263472125)'::point
AND to_tsvector('french',address) @@ to_tsquery('french','mars')  LIMIT 10;

                            QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Limit
   ->  Index Scan using spots_idx on spots
         Index Cond: ((coordinates >< '(2.29470491409302,48.858263472125)'::point) AND (to_tsvector('french'::regconfig, address) @@ '''mar'''::tsquery))
(3 rows)

Plan of query is consists of only index scan.


Find 10 most closest points to the Eiffel tower from the 1st arrondissement of
Paris (Paris 1), which addresses contains 'place'. See exact PARIS_1 polygon
in the Appendix.

=# SELECT id, address,  (coordinates <-> '(2.29470491409302,48.858263472125)'::point) AS dist 
FROM spots WHERE coordinates >< '(2.29470491409302,48.858263472125)'::point 
AND coordinates <@  PARIS_1::polygon
AND  to_tsvector('french',address) @@ to_tsquery('french','place')  LIMIT 10;
   id    |                     address                     |        dist        
---------+-------------------------------------------------+-------------------
 4832659 | 1, Place de la Concorde Paris, France           | 0.0295206872672182
  411437 | Place de la Concorde Paris, France              | 0.0302147996937845
  378340 | 1, Place de la Concorde Paris, France           | 0.0307854422609629
 4831330 | Place Maurice Barrs Paris, France               | 0.0325866682024178
  376250 | 1, Place de la Madeleine Paris, France          | 0.0331104655425048
  474301 | Place de la Madeleine, 75009 PARIS 9eme, France | 0.0345299306576103
 5344357 | 15, Place Vendme 75001 Paris                    | 0.0347800149417034
 1655967 | 23, Place Vendme Paris, France                  | 0.0349331087313895
 5189448 | 21 Place Vendome 75001 Paris                    | 0.0349739602806271
 1645248 | 17 Place Vendome Paris, France                  |  0.035054516779252
(10 rows)

Time: 26.061 ms

See other examples of usage in sql/knngist.sql file.


Appendix:

PARIS_1::polygon is 

'((2.34115348312647,48.8657428523236),
(2.34118074365616,48.8657338586581),(2.34124889530144,48.8657158708278),
(2.34507895327157,48.8647984137371),(2.34664637351338,48.8644206007538),
(2.35092599260214,48.8633949969132),(2.35018963361274,48.8620911379807),
(2.35013508709759,48.86198323148),(2.34942603926653,48.860724328187),
(2.34934422651062,48.8605714606062),(2.348198918621,48.8585122428713),
(2.34818528403175,48.8584852660126),(2.34754450116443,48.8573432499501),
(2.34748998045578,48.8573072839752),(2.34727190749839,48.8572083834273),
(2.34716287044605,48.8571544366361),(2.34702657180341,48.8570735139172),
(2.34695841648506,48.8570015779684),(2.34678119248757,48.8567048330991),
(2.34607232885619,48.8555807999441),(2.34594964833223,48.8554099476641),
(2.34588149215383,48.8553110329086),(2.34584060107095,48.8552660723913),
(2.34457303943998,48.8540431508262),(2.34282882150308,48.8548525947756),
(2.34277431496994,48.8548885683273),(2.34265167596398,48.8549785014457),
(2.34191584194969,48.8556170173375),(2.34082568197206,48.8565523000639),
(2.34045773722682,48.8567681364201),(2.34036234349704,48.8568220954177),
(2.34033508714246,48.856822096164),(2.33752769217743,48.8583778791875),
(2.33658731599251,48.8585757177307),(2.33288025427342,48.8593400183869),
(2.32988178792963,48.8601222319092),(2.32982726892706,48.8601402138378),
(2.32978637897676,48.8601581966286),(2.3295001526867,48.8602570975859),
(2.32830070631995,48.8607246317809),(2.32828707545679,48.8607336234383),
(2.32704673093708,48.8611381921984),(2.32607897177943,48.8614708326283),
(2.32526114627639,48.8617135534289),(2.32520662603102,48.861722540429),
(2.32471592483796,48.8618753640429),(2.32091289641744,48.8630349455836),
(2.32087200086194,48.8630529251833),(2.32155322584936,48.8639073294346),
(2.32243884665493,48.8650405307146),(2.32252059466181,48.8651574466784),
(2.3232972488748,48.8661647291047),(2.32341988057605,48.8663266130246),
(2.32354251307602,48.8664884968134),(2.3235152464625,48.8665064789925),
(2.3245644587385,48.8679274505231),(2.32464621421731,48.8680533576953),
(2.32500049864077,48.8685749741703),(2.32530028589861,48.8690066566296),
(2.32513660273671,48.8694382902038),(2.32566821564096,48.8695282724636),
(2.32580452605167,48.8695552643448),(2.32581815771984,48.8695552657067),
(2.32797189268413,48.869924162148),(2.32798552779567,48.8699061778024),
(2.32993507578488,48.8685034538095),(2.33027588164409,48.8683505987317),
(2.33063031789587,48.8681887507006),(2.33169358579805,48.8679460035635),
(2.33170721702503,48.8679460042226),(2.33365651409609,48.8675054382284),
(2.33583750536962,48.8669929002209),(2.33585113633529,48.8669929003854),
(2.33735054165431,48.8666421923058),(2.34115348312647,48.8657428523236))'::polygon 
#2Heikki Linnakangas
heikki.linnakangas@enterprisedb.com
In reply to: Teodor Sigaev (#1)
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

#3Teodor Sigaev
teodor@sigaev.ru
In reply to: Heikki Linnakangas (#2)
Re: KNNGiST for knn-search

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/

#4Heikki Linnakangas
heikki.linnakangas@enterprisedb.com
In reply to: Teodor Sigaev (#3)
Re: KNNGiST for knn-search

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

#5Simon Riggs
simon@2ndQuadrant.com
In reply to: Teodor Sigaev (#1)
Re: KNNGiST for knn-search

On Mon, 2009-11-23 at 20:44 +0300, Teodor Sigaev wrote:

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

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
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.

Sounds very cool.

Seems like you should look at the way sorted_path works in
query_planner().

If you have a query like this

explain select col1 from s order by col1 limit 10;

then we currently understand that we should use an IndexScan for that.
We don't specifically exclude the bitmap scan, it's just that we know
that the results from the index are ordered and therefore the cost of
sorting the output need not be added. In the bitmap case the cost of the
sort must be added and that's enough to ensure we almost never do that.

I notice that a query like

explain select col1 from s order by abs(col1 - 5) limit 10;

is the one-dimensional equivalent of the type of query you're proposing
and that doesn't work either until you put an index on abs(col1 - 5),
then it just works, but only for k = 5.

Maybe you should look at the above query and see if there are any usable
similarities for the Knn index.

Part of your problem appears to be that cost_sort does not include
anything about the cost of the comparison operators for different
datatypes.

--
Simon Riggs www.2ndQuadrant.com

#6Teodor Sigaev
teodor@sigaev.ru
In reply to: Teodor Sigaev (#1)
1 attachment(s)
Re: KNNGiST for knn-search (WIP)

Hi!

Contrib module is reworked as a patch for current GiST. Now GiST supports
KNN-search, the query looks like
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
or
SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
Plans are:
EXPLAIN (COSTS OFF)
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
QUERY PLAN
-----------------------------------------
Index Scan using gpointind on point_tbl
Index Cond: (f1 <-> '(0,1)'::point)
EXPLAIN (COSTS OFF)
SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
QUERY PLAN
------------------------------------------------------------------------------
Index Scan using gpointind on point_tbl
Index Cond: ((f1 <@ '(10,10),(-10,-10)'::box) AND (f1 <-> '(0,1)'::point))

pg_am now has new column amcanorderbyop (can order by operation), indexes with
this flag enabled can be used to speedup operations, which returns non-boolean
value, currently type of returned value should have default btree operator class
to perform sort.

Planner (find_usable_indexes function, actually) could push pathkey expression
into restriction clauses of index. I'm not fully satisfied with this piece of
code, but, may be, someone has a better idea. I though about adding separate
indexorderquals in IndexPath structure...

Both GiST's get methods are optimized and there is no overhead, since gistrescan
method can choose what traversal algorithm to use using information about types
of values returned by operations. If at least one of them returns non-boolean
result, then KNN-search will be performed.

The only change in interface of supporting functions is: consistentFn function
could return float8 non-negative value and it's mandatory to perform KNN-search.
Old-style consistent functions are supported.

Patch contains (it still requires rbtree-0.5 and point_ops-0.4 patches):
- GiST changes
- changes in point_ops to support knn-search
- contrib/pg_trgm now has new operation <-> returns distance between texts. This
operation is supported in KNN-search
- contrib/btree_gist provides <-> and its support for GiST for types int2, int4,
int8, float4, float8, money, oid, interval, time, date, timestamp and timestamptz

TODO:
- selectivity of ordering operation should be 1.0
- current patch remove support of IndexScanDesc->kill_prior_tuple, it's needed
to restore support if it will not create too big overhead
- documentation
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Attachments:

builtin_knngist-0.4.gzapplication/x-tar; name=builtin_knngist-0.4.gzDownload
#7Teodor Sigaev
teodor@sigaev.ru
In reply to: Simon Riggs (#5)
Re: KNNGiST for knn-search

explain select col1 from s order by abs(col1 - 5) limit 10;

is the one-dimensional equivalent of the type of query you're proposing

Exactly, it's already done in next version of patch :)

and that doesn't work either until you put an index on abs(col1 - 5),
then it just works, but only for k = 5.

BTW, it's possible to add this feature to plain btree by changing traversal
algorithm, but I'm fill enough power to do it.

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

#8Teodor Sigaev
teodor@sigaev.ru
In reply to: Teodor Sigaev (#7)
Re: KNNGiST for knn-search

BTW, it's possible to add this feature to plain btree by changing
traversal algorithm, but I'm fill enough power to do it.

Sorry, I'm NOT fill enough power to do it.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

#9Teodor Sigaev
teodor@sigaev.ru
In reply to: Teodor Sigaev (#8)
Re: KNNGiST for knn-search

BTW, it's possible to add this feature to plain btree by changing
traversal algorithm, but I'm fill enough power to do it.

Sorry, I'm NOT fill enough power to do it.

%-), I'm NOT FEEL enough power to do it.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

#10Teodor Sigaev
teodor@sigaev.ru
In reply to: Teodor Sigaev (#6)
1 attachment(s)
Re: KNNGiST for knn-search (WIP)

Planner (find_usable_indexes function, actually) could push pathkey
expression into restriction clauses of index. I'm not fully satisfied
with this piece of code, but, may be, someone has a better idea. I
though about adding separate indexorderquals in IndexPath structure...

Done, IndexScan and IndexPath have separate field to store order clauses. That's
allowed to improve explain output:
# EXPLAIN (COSTS OFF)
SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <->
'0,1';
QUERY PLAN
------------------------------------------------
Index Scan using gpointind on point_tbl
Index Cond: (f1 <@ '(10,10),(-10,-10)'::box)
Sort Cond: (f1 <-> '(0,1)'::point)
(3 rows)

We are waiting feedback to choose a way of planner support of knn-search.

Still TODO:
- cost of index scan
- Sort condition should not be ANDed in explain output
- current patch remove support of IndexScanDesc->kill_prior_tuple, it's needed
to restore support if it will not create too big overhead
- documentation

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

Attachments:

builtin_knngist-0.4.1.gzapplication/x-tar; name=builtin_knngist-0.4.1.gzDownload
���Kbuiltin_knngist-0.4.1�}k{�6��g�W����d�����&[�QR�:v��t���>z(��y,��H%q�����\�$�b'�Sm7�H`���`0r���������g�Co��<X�;�=��C����8~@������-.����^N`�J��>0��J�U�G��Q�zX��_����,o4��df���8��	H{�u�lu���7cq��x>�����t�|����IZ��=���k�����=�/#{0����8Po4qU�7~`��>�n������f;���tbO�������!������b>�3���v��k
�g���tCxi�0�����vK�!�
5�Y�w���L�)������T��j�;�>�}�7��m��KP
�a��y������9#�u���������s��`���z�rj�����������`d��� �7l�- �P�"�BJ����sox�b~}m���w�|8��$���W?�t;��|xk���]	�S������^��,F
�6�kV��� ��?��>�;x>�a��=��(NK������1l��������#���c���w&8{O�("�H����P$dQ�X�l�������QQ��?-N
9Q�����z�������m��+�Cl�P��\f���8"�1�>t��h���)���BZ������+g�Gt,��~x&��'�"tw��/����*��\p��pJ��%�!��O��4��t����_����<��3*�rygdop����;����<�8S��l�������"�p���8�<�� }�����=&�<g��}f���Pq�������Z8��V0���������]���./�'��W�����Q�'��������^����E��-�����3��$iF�+G���j�R4y��L��(-���KZV���%���s�~��{�D��>Z�Q�#4Y���)v�������v�zl����0>�z��y��G�H�������}�����uv�>����Mg�h>�G*���N���x5�RaBM_@r��f�>��t�8sv����'(��������>��O%8z�*ro��]��{]����Xcg\%�r��BpB5�A�@�F1H�D�%0�B�������dk[��-��&�\�[�`/�����sVVM]u;�w�������"T��(�R����'��U5� ��`�,
���x� b�fE|��Q+RzK�gJ����L�dI�����7hC�I��wg�8�!���e�kT"�16���vtE�{�_���C�a3���I`���>�3)���,b�������\��.���7�T#D!`w^2Qa�[��fv0��8�S�'�?�2�A��������5);ep8�Q�=P
��C�f0���35V����3�'P�<s9J��o���D��|`{46i��@���AJe�S{�\;�� A��)�"ET1���rA*�=o�����1�#������`����	�����?�Z�KMTw�f����+����+����*�mR���X�,l�\ZjGi)�h���;������r�O^W��6>s?����D)�c������%�%0�^�8����2�����{2�a�@CZ\��</P6�����`a_�%�|��$�C�O���`�I�)M������_��|q��	8�3�A	�x�
�E��l{���(���$Ix������-�zV���,�����8��1	L}_h�E<�b�q��
��z�
�XA��P/�b���*N9��\���4���N�5tsP�"C�R�Hs�c����C�u������[o>)�1P!|���H[*�D�S�j��E��������(�������m0;����0���(��\���:��e<.��E���Z�������o.#���wd����� s1y��h�y������������C tz=����%���(��k2�wAAzs0��/���A����<W-��D	'���U6���L��"�&"�d�(_�u]BPQC'�HY��OM���4i�(�d�.dhe|��:N����u�����}��wU��L��.�=C�0Hz
��1����.�sz�b���uElv�;��-D>��A�|���
�� ��g��&+a��H��H�����!��5�fv}��P3
�D=N��������!��t����i�;���B�0{�UZ�y��s��kA4���������K�����]b���b�0_�9�:�����
`�w��������\'�c�{�@c�/����{\&H�m$.�s�*g�<����m�-����<��k��GFp�����Q���l[`�)����_�$H�X/��)
K=e�r}T*E���o�2���(P���E)!d�n
[7�]�D@7!L	{2
�i�������WN�2�����D�>#9=\[V�+��}}
���/��Xl�To�6�=hhv=�r�FX����N��I���{�b����(�bW�*��
_����D�����7��_�O���n	Zd&���������+��X���M����|i:�d>��h�;lj���0>����	�D7�AK�]��`���F�%���V���0	�a�1�����G�^n}�Bi+����4��,�E-Z"��wX�
	�L96��SXi��^N9)�#K��7��

�{���o3���j�I�[+����@I	��g5�UU��],:�K�W��&��)����e���4D����Z���|N��H�a�."��qw������?�����.�3����]}��r
��gX]����^�!��������){���D2���{Mnpqk__;C�=��&D��#����3��#�#����}�k�O�4��|+��O��)[J����K��d�����[W;%x�#Lt��{';x3
_z����T|W/$�nbQCSm����������*�
!Z��.����|1�
x)]�%�o������F�3o=I�����X�����M�����$��v�9��M(/bYGw�u�
��]bUw5#z�}N�y(B�.����s����R����B=����7�d���;=���b��u��IFr(���}�\*y(�#��B��}��
�+l"&h�����>������C'�=��;|�A�U*Y�za(r'��Nly�-N��v�	.eF���Lg�wDl��-�o����O�"�/���c���VJ��kp�����`�>�����(��i�1;�`*��8
�
T���tk����i��v�h	4LI_������5�h��j�������,��7�@v��&��x�`��j���7C�l���&����)#f�	���MH~^�!�L!6'�G���&���="��N}��'xJ
������(��@(����.���}�?��*�Q�Sif�u�8Z�A��jQ��I���#B�R�����'�R�r�������|�v�\�P
�5�_`�5.��3�
@@.�NZ�@���9�$s�6rhj�a'a��zR{�����Bfad��[zW��n``y
(F��d������X/����h{���E����H��CEk����V���%����~���k���Q��l>UG^���;�����
������Uh�%]� �q3W�������-I��!=a�
�B�
��`}rA��'S.�\��6Gl�@3������a�\E��x�����/�����C/%���N��\uN��?�6SWHs;��E\B����Q�vV�u�BO�������s\'(��7�D��v�~dG6����Tam���N��:��N��Y���V�T��Sm|)�Z�w���@i��Q��X�p��Y�se1�+{%Ch�	XZ���
�J�-�������E���{������i�r�Lo�����h)����:�� ���
U�i�R#���u<oJx��`w<q����f���g�����Fu�	XhFM=0:c�	;�tXJt���P'p@�}��!�D,����5�E!+*p��Z�9��1W<B�����U�.j��D����T/~�8���$d�@��HE���"/���ZQueQIQ@�������(Y��diq���4�������P�����DR����)-"e����X����
@"?�������v4��}!$�1�+�>�p��D���]wW�x���]b�9(��Bl������I�*����v_|d/2�`����q��D���=�c6mr�">�`$�Qap�rT@�)�"�����O�U���h(��i���|�4�������1%<�K���s���k
+��z����@\�
@�)�W#�<��N��i�#G�)��+ ��m�#�dz�)(��C�=O�QA�����z������Q�6��=BD����L��&����RJ�Y�F�HVb��	�����'Dx�G���K	'���9��\��F=�I����sN��& �M�d�<\��),�i�m_����V�����y
���G>J��x;�;c �����5B����^�������������7�g�Ogb+d�T�K�{�#s��/��N]�I�-tTd�
��
�`�n�U��,�����nKd���s����%����2V����eKuX;�*,��}`�8�,��]���
j����<��Ga��lEO���N]�G��@�b`%��
R0L������$b;��3���7����t��2"������~X���$������9}
/�v�
�����op���7��l@��%-��=�����������������y7�<���z%�h$A���1r<0%=��S,`bC�������?����E����7�v��,����`'����XJ�Kz^4G���i�� o(�������a�D�������K�Piw��IH�1�TDP,wL�/'5���sG+���:�|��.	r�D6Z~��@qp������8�B8`m�@�>������� �7�!*�t`#��C(0�"kb���T9u�����Kz�H��A����t�<.�"���s�h���;�����El�8{��{8F����CAP?���5?>�('�1��;ib�#Z����6&z����-��L��'Z���1�a!���L����4�|���#K���L�cl|�[�z�����;!5��3Q�8:s	�����o���}x��Fd+���G)�8��w�
�|e$*2�exP;���PX�]�������<�P�C(��b��W��'��c�����Q������%@���	�b|B"�
��Q�������(�J�FN�I�^�����2�bb�-OJ9TF���#~�� �Y0�G�K��in�r���S��^?)L�HI�D��S�t�|�w�)�Y����h���2�En(H�i��K�$C,�����E*Y�K���`�tO��R/�iF�(
/u#o�]e��b�VLL�sZ��My�?E�p^����s@��&�AI�@.5'���`9�I���<�$�D�&�i�!^�,���B�4MsD �e0�X7�!�lo�&��`5D&�=~^{C�w�"���O�).c���e�?���B��~
�pglOh�p��o�iG,!V98h����M=:�7��$��S����,�/�
v�V"B�{���N�*G���w��ds�!>|��0y���C>i���$O��?��9+�?nC�
�'DO��)FQ����	�%�L�&\z�K�p�����2��
X�:*}��h��_����U.:[P!m�u��/M+xQ��������?�~N7���@��'(�#��1���fbO����(��#�m$'����#}��1���:=�����~�@w�7�l\<b\�
ln�;���S�����J�i����X0�o��b�G�:
�q�L�F�������O;�M�<���zN;{
Fb�y������Y��	)�<Kl9��L�c�����U�����yl+����S�Y"j?�p"��
�Y����S� ���a 8��nR����1z78���s�!H�����_��%��A��X����h}�#��tP9>�g�n����u)�;2�0,~q�p?"���kO���}���`��`�`a1��:������G�
H��Z�`���5U�JJ$K�D���7<��P:IE~�(Kg�p�q*"�h������wQ������|�
 �� ��P�e�/�E�q��7�VI��n�����K��P�[R����;ZU�F��_�j��}��SK�G	G��rF�t�i���7�����=]��b�������#���Ld	�IpZ*jO�����Lg��P��0�
��K��7�����4/�J�|%�bHc�:�x~;�j�e��-���97��0��OfFa�g���r��G��yG�����+�)2sT��X��`�teDh�m���(e!9�,�R�Y� 8]p�N	M�������[���^A$�S���j�E��S�8�|�Y�����P�(M��|�n<��%�3���>�g�u&�8�QJ����SBD�
��"6�5�(�q&6����R�HiN���v���!z��c�([�T�����-a~s0F*�jz9J���r��\��QD��-3�G9G$�L9��R�S������m#��:���p���Q����K��j�!����;��\)�������
7���Xo�h�B[�.��?�6e"���U��NY8��<���	C�t=9�����`��0�f0&�EKi9����ps.*�voE���7����7���NK��gO[�>-B��2��_��I��m��o#/:�U���n*�4P&K�JK�n��!����=|;�s���z���Sx��������z�`/(�gz�z���,����|
x������s��rQu�4�~�q���k���J�|���DJ�XR�(�b<O�xv����<�t]q�\�r?��U,�2,0���N(��d�l�RX�:ou^���g�4���e	�L�����h��R��KnJ�E�]���n���TP��Q�����V�j�Zey[JJ�q3BF��G�,��lD��O�����
R�k��v�������n4��R���va���O��w��+)�85�i�T�E��4�z$R��h���U>S��|V)�6�~4�~�����<*���!��^\����'NxqKP�6+d�ta&������Q�bk9���+���+ ,1��W����J����c�#�� ���S0x��	��unn?��^�z.^z�Z��}���V�>R���24���?�	��H��;���O�.�e?�qXk_�;���A�
#�70X�D�c):CX�@/�������A�:u��j�x�H����
������O���s�3��q��p�|�����$v?E��)��"�����O:v��N)�j��!�GnK���u��b@����C�Ij���|��>wJH��""��5�3���d��E����={�����n�C:�h="�~�)�m�Bo���b�o��g��A�}G��*^��W	#ca��4��(I�PP��IiJ�]����H�������$�3�����`$��
�0u1"/�I���a�f�X)i�^�^�M�p���xjGj�Em� ;�z����Kt�)����]L�|�QX�i���e���'.�����r�r�ZB�[��V<�!MW��s�JXd�aH����Ep&���kL���<#�"~r�h#
t��\nf����mha3
-�M�f�U���n�Tl�H�����?e�?�����/����LY��z��Y�J3�9V.��y�1�OHu�w�g
�p�����g���-���������b$i�$���|\,Ls����
��4�5�Y��A���Ui�P^�������gn`6�����3nlMct�T6Y��\�9���������sS���s9K��A���:^m�K��K�����L�.o8�Sg6�k��,W*����B���R�;#���^�v#f���s��n<{��+�h��"E����\���a��k`~�?�H��'��vE���X���E�9�x��8�RA�w��-����c����v�u%�v��'��6y���tE�V� �t]Tr����e4Z�$)���2�$Q�L*2��20�j�D��S�UN)A���n���E7���C>���#��g���*����0�(������N��N����a����<+cDwJ����k;d�Y��*�������Jr�#�c��<O�)g���l����g%��3pB�~4�b�B���?.���/#V�(������b��Ix*��!��^������qWzv�GJ<l6��,������^�-�x�%�Hj�2
��
}��T=5?�h��
F����c��!k3/J����R)MbW�FK�: P��P����[�s����l��q�z.W����
�k�1>n�������[�)�uLD0��Wl)F�G��
���0��T3o����%u�1�
�)����s<*V^��%��D�,��b��*��v��@���R�QP���&
�)I��[�50ML<�Zq=F^`��7�s��� k\���&tN������G��r<�F�}��$:�QN��s%������*���W�^f(O(���������$�h�
a�P:��MG�'�|���ZE=F�;>H��+���qp�'�3y�%�7�*��(Z_��C��ZW�"G��Me9�|eY�q2\;2��Jz����������s9({�-C�R�T�x��F������2G�{/sr~~yz���_v^��;����]\��������Y/W�7'�b���R2�>��)q������b
w�3��A�-����,�KjrN�{FLE�\f�>������E��|���KE�~b�S24�gd��5qFU�Uq�i�Y��H���Fj���1�y�j�a�5/�<1DW�9�q��A�Y�)jO��T��'��@B�%���x�4G���I$�����3�zZXY����g�R��9�RDd #�����\J��p_} �M2w�}#2��P����{t$o_Zn����,#�6��LSgvY
�g�D�z��US�Q�-�9:y4{0ct/�5p��� 6��)�x�5�dR���a����Z���Z�v��Z���z�*j�EZ�TZ�J��Y���!����B����kf�����G�*�9�nA��I�^�a�/_�-\"���W�$�|�Si������P�_�5�z���n�`�O����YE�\����h#S�_��D���1�"�I_��?"�q�mT@��;��d�K�JENVo�j�C�1!�x&�p"�8���d��j"�s�'_�;����r�/�df��l������f�h7��^�4�L��4��&�C��z���>��b��"�s&�0�=b!�d�=��xa��`q���g}��ft��|o���k�]�U���J��&�������K�v�o��������M�L���d�gQ[���������Za���=Un��^�7���`������M_���r���}w�+z�`>-���p�\N���3�������2�����
�v���7H4�������
E��`�K.{f���b_PPs����������/;�������e���wNi������������)>��wdu�II,�b��;������������d�=�E1L�2���h7=�<Jd������:��=2�}z�E@��C��/���D�r��5H�x��I���r���(#+]Mt����SN��=�=T������ qo�+��V����<�&0��
��9F����~��
@5���X���|�'t��V�H�������'�:��N�l�$Q���D]i,�O��T����UHK"�/\NOQ0'��`/z�N����3�mo����5G��ElD9yE�`4��'}#����-K�%�/��A	N�q�������8Q,E��j�P��W;�&�y�N^�iTk�������pz��������n��Y��e����������
�%�)��K-�[r�d?�cG�L	{yA���t�oR��������)
Km0�i@������&�fV��������))��{���H�N�2{>����^&9��\�����	5m��a6�3F|���h�������f�c���,Z46��|���<c�@A�*���a��k���%�5(�L�x�5z>(�'=�\���%��3q>���S+�}
`>��kd�J����k1Kh�5�yTm�\��RD��$�3�����������i��*<v���5��\��)v>Mgl�S�>���J�8Yqfk���}���NDbzo�����UL������B���o�c1s���r�<�l�/��G��������8�=$|��D�9l�4w�f��/]�qb���Df�������hE1j���FW��W�� �NK��1�KE+�r��T*!�P�pD��K h�0o-_e>�c��_�������N��I�y�����/�>Z�Q�! J|WBm�����3<�>����I<�6fo�)�K^��`�*�K!D�"o�Z��1(��#jh{)�N*a���n��|�
bF5�3�����^c�`q��)�G_��� _�[���sYJ����sU����+�y�b�9����EUU��OS	�m��F@�2�\fhs�Q��[P�KlL��E���J��)|�c�q�&���������z�;%��^B���8�����f������Vh�j���n���Z��r(���~��]���.���#w��zW�DH��u;��tn���������)[����b������<Q^�%K�����=�
��Ty��+-o`e~���8��9y��?9/�)����3�Q��'B� ��j��5I� �6���N`V��F��N��������\'��(���������1&�!�w��m���Y5  �t�lj�V�
�V���o�`Wa)����q����b�1m��zqDG����//[�[�}C��D����um�
x����
����p�	�Z���0���e(�Q�f�,k�b�l�N�0�>&9��<_�dSd�(���M��"bx�.������E��D��g\��[��e
�i�������{c�`{����c'UV���~\����%����aR�x?��jH���r�%-��H�"`�!!l$�,�M������DP�|wz�0a��/uSc���|����T���)�<��4��t�s�F����%���\�S���6��	T1" lr�<�����m����~�|���;�����/�a�"���b,(c��t��gb ��G��C�YL�4�Ea����]h c��;��}%��U�w	1���5�M��5#y?���+��G������o�->9h7����A�����j�t���T�n���x�SJ'������S���:�����M��H�_��R\Y�����[L�����$��B��5+7���7IP?��UU]J���4�$����
�5�H�?�3�����;/=�~#��&���bEY������Q�-�hd�z~����f�g�jF���#1z��c�G��u�9�3qC�_�'�lL�L�t�so������{NG����������K	��T���g�1�&����i�@OBC�h`�+���^�&`>qe�o
�k�f�*����Z��a����~K_���=W9c����d,��&d<+!:�v8�s,�)���RI]��-���h����>�~�v���ZW��c-w����9����VCn���+�����>:(1���v�A�s�<���w�O��~�?����S�?7?�O��y?�q<��?���@���+A�^�C�<�tYG�������#����X�m�{�z�`�c��e���-e��9]���F����yLeC�~�	d� ��A��(e��a�b� �L�x$9���XZ�ay�����G�F
��!���V G?Obz���S%n���xM����qJ�>Ckd��9����O�����������@.���8D
���������V�l�uZ�]��d�i���qo��Y���P�$�@tk�3]�Hb,c�*G��"���[;�-ix��#2����*�c���%h���Hx�0\�Q5n�XA0�p7�'�iD�T@�m�(}=~'>���p>i;3�(�R5�!Er�M�RP�d\2�nO�;w\��� q������)
��}��T�j7M��lE���r6�L1o��d?�x<�#4Z'�cm���&o� W\�>T\�+:xN�x��19����0��Z�����0?��b,�B0)�R��g���P�FL���0*��&��W�4<���z��x/�@������T�������?��>�jF�{O�Wi�6T���t��������Jy�����2��D�VNG�,�?�����,�O<�&O�Ml���X77��D�P���*���P
0����|�9��Q+��9�@#x���_}� �3�_�R8�D�z	}cu��0+N�o����TY�rM�*���LS�@`�|�&���Q��E�����IJ��/�����w���|�1<�M'w0�"�5W��*`>�xu��g�c��OIn�>o4}��6�vBp0���c����k�/��6��dDY�@������EH#���"�P�eq��2*����3���j�#3	-U$�U
E>���w��]��]~���'������}���|Q�R����K$������P����Fj%�H��]4rP��
Q�|Wl�B� b�&�b���d��P����|���f�8<�Xn�qm�cMHU�_�&+pZ���D�"�H�}[�{/�7�{��(@��>���Q���<P+�n����G��� ��%��"D!�r/hs���]d��e��X�'��M�D�nC����Qk�����4���v�S����x�����^�cB��_�kt�{sy�����F��'���G��4���a�):���u{J�������	9K��,�O���[����f���z����}5#��9|��,�*sk<���q��q���W�a�$��d�R;��D�^^H�x�%�AEb���SY;d��%��P���#��{C�B�L���V���Yd)���+o� R�D	0�H�P�Ge3��rA�Mj��Q�R����������]�G���c�^���d�5q���y`��S{<������a�U4�)U�r��p�vF�j�a�������@��-�� �2���5�Smp�(Y3J���~�� ���0f���%��AXtSz����@m������A3��:xa`����P��w���?��^��t��]<������)���I�X����wWg�D������J&�]'�/LKhgg�?������;����[�#�i������e�4��u|�}��J��5=�E����j���darP�m��P0����x�3��`�P������hef���	"��6��C��!}�vy���Tp{�_�g��s�C~�*���n��#��>d�L��@a�]��C��P���T!�z�i��f���
�5i����"u��-�i.�%��L�	���W��3|����	;tth���a�b�3dv�������C���G}�����8#@�s}�����2���9�P��V�U����g�����7�g�J�2>����P�i#��]������QWa���d�����fdB(0�����bq�����B�ln���G�t�S�N����<��5�������\] ��z@�NN)�j49wq��������$]�en��
�5��3~�8UP�����'r����+���ar��"�(��	�~�C�S�k#O1�-=���Dg�����t�	��\�I�>X3���aA�'����������O/�W�,p	�]������R�LS�
�z�����S�j�!65���"Ac(���c���Y��m�+��2@D����"'���P�_6���=eI�ik�FK%���_�#i!�c�e6��K\����X�;?���+2�s��:�K����xi��������*�"�S	��Y������e��xU������P��U��WPW2�8?����������3�#�re�;I7*�k�����OX�1��,�����6*�����Uf?�=����T�y�j�Yd��d*+�o�~�?��rg/;�b>����\	dGk���Xi��'�W�E��^]d�;�Rg8-��G<9~4�k����6}X�a(l�P������~�w���X���^r0��[#�B��6�����3<��i �?�)]v�FZC���e\S�Z��������	@<�	;��
����q 0v`�jb���%�=��&�x�Dz����#U]w���9��o/�����	��3>� T:B�z�E���7x�0�p\�9���<��<kO���p7YS%�����m������SW���aVj�*���?J���<��E�.�^�g�V��"�	U
uf� ��k���:��.�������v�$���Z|C5
j��f��`����w#J?>X������9����L,z��W��'%z��:����K�/^��n��*&m8=�
<!uD����L��5aA�_�JoE-�")��1�K��J��w�Q�#���7�$�E>� 
��
_,G�O'W?�x�����"�A]Z(����N;ez)*E���_
M��@S����J4�w�&Q�����7�&�E>�������I�1.@�@��h�4k�'�T��t-H��*,�!�0]��#�UxqC��!V\
)���A���C������<�����Q'o�21A]�3�����SF�d��R*���SN��SlI����.Z"���,��2!
J���v�h���,B���h�A.7���X��"~�^T��
�v��
�
5d����U*]i2V�V�/S�J����R�*�&k���z^c5�H���t�l�;V���1�v�(�e�z��>f%-������$�*�������h���T���4�X�,� T�:I��u�H��u��RY��m*����w�T�5�V��9�T`�I�B7����"���L������z���~%�
�be���R�=�TZ&{��>a�����'����I#@B�z7�����r� ���l�!p���l��
���1&A����PgT��?gt�m��ogJ�%��x�CT(%���D����(tN������4�F����h����N���Ug���8�a�V.�_Jg�i�)y�W���a,3���)fZ�K�u���D1�������C[(�:wg�����@�"�c���:������b~-��%<�},�E*N�k�H���`C�y�������BXZ����\,9a���\��a�
�1
O������V����MZ�y���F�-��V*(�Gy][�����K'Ib=��y�V�<�	��<�
�4����aV�A[s��i�0�w:��K��w�@�]:�|/����#L9,��y��%���"�a��.�F�1���#�`�
DO�F�yv�@z�����l�"��O������K 0��$T���:����'�<<�iIk@��_�Pd�zvB��U��/Aw�tZ������p>��:�uG������/�K��Z�h��CB�Z�h��)�AA31����H�'�(o�q���3��v.�p
X�C��^�a�1M����/�@�L+��\da��RO�6�U���9h���ce�\.x�?���L"@/$������-�m���88$
s��h�0��I!��;�V	��:*�T�9M���T�r��`�
�����
4�./��	{2�!�wWg�i1��� ���)�V	Q��!@�_�`0�@�6S���pl���Gz�}�q����O�������s|�~99��bEu"*�=P��s�FZ��^��[�;yq�QC�'W��P���y��'����k���^��{%&��6
�Y����������c����f�G
d�����V��\v_v���?�?<g�e��E���#�����&�-��r��T���f���Q(�������A�����_lb)Q��>���N��}9��P�S�D�$,1���.{���z8(6V�?�]j�_2D�GGl�}Z8
>}���X{�d�C���<_x������;%���E�%�f���6|�n�jZ��Z������;��=?9�`�����v��6����y��������],� \R�����G{<4��T�x�m�G(mxa�L�t*J�S�CD���6G���ML/���`�IYC�m��|���c5���_�b^��_]���2Xs��V�'���s���x5B����\�4����@��g��������4������8�!qhd��}T�A&����H���2JN�IB��.?�������� ����$�Vd��D;��I��q��"�����W\�{�Y��\'�_�����������1��;�-�a���sh��h�|�������=���`�ywz��96��W�r`�r�{��bW2�U�y�
���Oh�W1�"���\kb�#H��M��y��E�w�#��4����������Q�C���"�����b��	`~A=c,�3�]a�w���_�[FX?��o�o\������TU2�?���!���<��(���E&f��>�h��q���&&�5k��y��~�]l���[�������W!&Ho���t�
�!��|�����;=�Y�N����Kr���^����4�F���u��I������R��Q��d�*n�m������h3���FF��)=�?����"���-*P��?j
5Q�?A�-�Qi"��%Z��%jF*~:�8V��*������Tc�H�@|<Z(V�b�K���X��;�O_E�q�{�|�R������&����sF�|o<l����~������]'��,&~D�qji��V����FO����TjjU�V��SSQ����P��.�3���m]*��R!���[b���zN<]���R�6��e������.�e���P���|8;C��
�R�C�<�n��������BF9Ab���_�O;���[�f��?��[�����Vj���V<�����2��Vv�9-/#�T���-�~�+�>W���*,��L�f�4�ZM�0����
�{���t*M�CX^��g�4�]h��knn����������1S)7h�QMi��cns9���������u�j�����!w�F���f|(�z8/�C���C��y�2��h�%�C��f��bX�
�F�i4�u�=��s���T�C|c��z�&,�0�qD�{�A����6b�2�a2{k89���u����5:�v�Q1�|����������l�<*�����r_s>�t�}[��o�|�b���9�}���I_��{8�������(E��SE��7�FS3Z�gC[�|������z�YA�j��sW�sR�'q�2��s�����9����/����
Z����{�/�����9�>p�R�<A�wY�qA��p
���{C�9��?��J������)bC���]+x�:
���b/�����{�g4-��������w�����������/fQ�#D�����ns�W9���
K����t�8A��t�"�;=x�?=���X�����A���n)��N�]���`H2����t��|*��4��i���@�!&���^���/��������������cYt>�f��45;�(_\^�U�6��;�h����L+r�h���|/e��sa`~�"%@.�Kb~�/��/��Pi�B��#�����I��(#\E��0�����Q���HO����l�4��l��	)\>��(�G��
����� �����Z)~GG���W"��k����c`��e�PUT
���eE%q�;,)zz�m���"����k���k��k��]m��6i�Hb��d���g:!,�&�\�'��>$��*eA�mPY�d^����-�|f�tU@g=h�IbbR�om��M�hIp8T/f�������-�B�F>`�k�,H��u��V���%����Mo���`�F�dkk����F�oC���&z��P����b�j��+�6�g�iE��L�
}�*��A���qt1B��&�#�����i�j�Km��(�4+��[\�PS&�����bh-U�����5���!�N�bh��t��J(���:�xqA���V\��@!���6�h�in��Z�Zy5BV��Fh-���Fh-��l��z ����]�^#��V�����f�g��Gn��������jF[[6��J5�a]�.�'�;0��_{�������m&<d#�	���c�u�e�������"BsfO<�������p����+�������N��I����7�]x|~r��v����y����]��g�=!d�o;��<������

�����g�J<|��<��|��Q����Kj�>c��T�5�2��������-k���35�z��X�u�������q�'<����������~o>��6��+1��c���:�V��[��(��G����������Z=�������kj�5qmK<���t���F�(-5����C�65�q��U_7�=�`��������FO��I,��c���6�����!�G>�|��c��A�G�xe/7j�L��o��
�M�������V��l�~8f��`�����4z���/"x�����s�g
�����J6��(>�XbD�������a��0��a�F�4�k3�T�,��YU[��K�
dk���=��7�t����gK�g:APm�'����i���R��a��5+��Qi��5%���g��G���g�G��s,��=2��#*&�P0IL�$��e��rtD�T~]qqp�Vf������^�����Q1������iT@�~`���F��l��7�C�v�\6*e-�Z��z�Qh;�����O�&@+��h8'}WLrz����B-�jN���Q
���� �]Q���qje�����E��l���D�����}7kF�U~�ne�B����V)�J�!�{�A=}��5I��2j��c�w+��[+�wkE�n���*���6�N����F�M��4���nm���p`B���Qmj�g�f��W�O�C�t���K��
����K���Qm7�����p�?0��a�Y����{z�U���U���@��G��,�.�eV�����j>'��jM�#F������:���st.���{��� ���+F�����C#wS�z�n�E��Tjn��zY�H�y��V��y��^�e�e|���S�9�n����$��y���c�(B;�HBG�C��Z���j����wA�����E���}P��	�����*
�G�����P��O�e����f��V�f��8���8{���h��
�����4����MAJiSM!M�;MX�5����]~�l��F�����F��>
m�p��&��K�h�
���&��?1�c�C�c��d<0}�*0�a��t�!h�	��Y�n�j5�F+<���\$��G�C�G0������W�C~*mV�F����x
}M#)��D�j�����G� 4���2�������j��*��P������K�i-�%��i4��w{O����AoF����v�a������p`zbVj�iVbs�2��<���f�0+����
�����rB{���$O$���Gb������V	]�<������	=�����)�i��wD�����a�S��T�����G?�����w��W���s������T��e��xR�Q��#�����s1"�#��y�l�:z�A.����'���mf�h�$MP������S�A%��2P��9+�W�+��������S��h��r8�O(/(�]x>K��N>���
y8Y/6H)&����r�����I4k�L�f����,�Pa�E2\����'��h+~�tEkg�p�-$+r0�YL����;�����Ee��S�.HH�n�"����P��|��D�E|FB"�c.���x���Z��mf��(���L<�H�/LD��Q��a�uR9�:	����Q�	��v���	�VT������[N?�G�X��������>#�P8���}�lC|���Q���*�����s��C����s
��3��6�|Q��#/���X�$�6�I���:�_N�����U����^�L��a3�f��b�L�q�D�!������9�^_�����[o>���[�`n���|�<%��=0T�l�X��+��2�W��~
~���.Ypu�w��Ub�5��{i���������PN���CT��
�[WN����r�A5����c�Y\AI��=�a
|E������F�z�����~+��"U�BQ��~�y�bZ~l�R��@�U���R��������N}�{����BJ�f��|��"'��1�$���L�fIS�Z��e�}QQ9��DF���k��8F����c����dz[�%'��!�C�h�����-��)P1�F����|�`	���E��*B����f@&��V�QBS���[��w(��w��*B�����
;�5������	�9���1��ELI�s0$���S�l��i��|1*�W��j�(�+/�$�e���1��)�}5!n��c�f	��WnE�t�z��a���C�-M:�/M6��P2�����8h���A�f�����8�d����hl���]J��0�'v9���K��
������o�
$��YJ��(�Z@��2(c�)
_�ir[�x�ba�O#�?������� �o���'s�1���"��Y:����,�-\��rz�J�u�<��_���=�D��Y([���%�����AjY.5�rf�Q�&�z�F1q�*!d�M���+�
�.�)6H7A�-���]����4M>�R,���T��t������D���
ck���\��gy��*���!-/T����.H����0����u��q���E�c*�������a�a��6*�u�%mF+f��T��}�~����|����\g|+7�B���g��[1kR��6jj���f�j��/�;�G6{�]�q�$��<p�>NH�5�x��`���������3���y]�w�F�5^?����+IS7�@�V�+c~~S?�1E+���x������M��G�2�^5��w��7���������^����Y�C���w��rsN��*O���:�}����G����U��Q-33��gnlbls�4N�����[W�n[����8]����V�<Vc��f�j\qL�����`�X����Y����h&�eQ��-9�(i����1�l)�-`������N�S�oX���+,L���{(	t�s���|:�}��E�O'�tx�P84Y��O����^^\���O�W�O������(�����j�vA?��T�yn�Jg1�z2��L��mf��>�leF�%��Y,A���Y���g�|�tC�?I�!H�%���S���(z
Vx����F+�f��h$���W�X��.�_0�{�����(�C�`&�	<4 n&A�z�r��W���iT�Q'�#���\����Z��Hn��/o����z��IO�J�2��l	��)�:��!e��)�+��f�]��S/�'T��&�\�I�`�>�t��U*��M]�h����CK���W'�W�0(��`x��{�p�<����o��s��;����J��O��Ak`�{D����7v�����IK$53��;��NE� r�����K�����E��������ME�*���o��1�6�e�(?�'J�M����kxf�&��� �d�Q�����2w#`�Z�q����E0�tz�"ah�LC�,�`u���A~`��O��a,;RxLMk|=n�7��b����#�����3�1��F��������#[������f����w��$�g���JL�c����v/���(�������=)�����4KLR���dG�
�6pc�ae�������r�Tf�U5�1���2u=c�6��z���|�Mc9,��P���7?��!j������`�������O��Y"���z� o���vEu�
��p2�Q��N+Y3�]�
��u%#�_>h�zSd�aQw�4�ad:H���t���b�����^��v���'�(���+�t�����h����������� *��^�����pOT���paYR�������5�/G�"�TGp�'��R>!d��C�O1���7�$A��B!�(��Z����Q�uT7s	�j��j�s�����O�^�/E����%NW���i�Y��
���YkV��]��{��'
&Sv�}����H�;?{s�c�c�O�����m����o������b�����u��_@�e���>�����a�&_�M���/��V�V���bG����W$o<�x�����}b����]�]�f8��-~��U��l����o���������oUCoL�W����?u�D�T��a��{tD��S'�����W�#����������+�^^�����W�������u��`��E������`+���	xs��O#��l����7�|����{w��:O=wtD�8���$�K1�������K�JBY(�$���"	���+	�fIX.����Y�A19i����:�B�D���|a�^T��E_T���!D�B9�-�B	*"	C�a��Da�l�������yd��.���K$aHD�y���W�������0,�O���"��mY&�+Ke���l���.���,�k!u�h����ZRQ�����>6AuVh��q�uh6���R>l�	�X��)�dr0�IB���#�r=)����Rp�Y���/�*�
��Xq0�����y��J��`�^G���I������]i�zXi��!�Z�r�,Z�d!�%8G(D�=EI.��htMpC:���6���Y���)PM -XC4���H	����6�H��.
[�����4$�	q�ZS&&0�8�tZW�k��U�cK��<���q��a&�tf���\���+�RJ��L��B���,�)��eb��|]m
J���.(�D�F�Te��P-�B+�J��NO*����E1vO@��-�?	J~���#|��[0���k�5f"��[M��kr>@���.i�Vb��P<����%�������,�[
mo�����P�i��H�Z(���$��R��zk�-I��3�u�P-�B�����Ue�7E�����kIY(����:2	l���Y^*{j�Z�iV�f�^k��p�S��D�N��3����Ng����kF7��@�J���O�]����Y5��J
����lU*M��(�*�:��P�^o�k�V�]^.�Z�����S���]l�$��[v��xN��}:�+W����V(#�/>�1pn��l��&����!�U��[����N����l�����Y�<���!�Q���.��B����b��58:A����#���n����L�V�o}������p��7D�z����xY*l6x!�&!�x�j�JqX�JYkK`VE���BQ�������
�f.T:j"��x8}<I����#+�� ��g�st
������Ep&��X����m�s(�?����YQ'S��e�X���e����$�-������|To����.�2�*��7���2�h5��0C"O����������)��s(#�PDrX[PBTDI����tNr����
�0��K�l�P��9��?������|��Np�r�~|��<[$�XCnRV�\�S��/AU�����[���v�����Y���[85��F=�����d��1�"��X����	�Con��a��N2�xH�Ws�JTMVnU�D5,Q��!@������������I�����U���f��X�	��:P��%�����sS�e_OQ$)1��C�g�g�U�R�]��W�(b*G�f���b}��RFJ�oE���J����)/��:����P�0WT�m�\�J����N5��:�l���E�N��^c����+	������3%X|��5X!/;Hnxia5��u�a{{�v�)�����fa�zT6��T���V*�7��������	�Rc�0�f%
L"������*j7��P����z?'�o��Wuq|NW�f�f�-M
�@��\L����u�gE��Pzy5���)��?�S���j1�J(����2�?FF�S���1?._�t��~���n�����q�"Li�S�z�}��~��!���}�|��HCG�mT5tTM�t��������"S����������������2�,�)ce�yP����}=���Y$]�����U-�J��������|���gqu��%��IXtSF������<��\��b��Onp����O
�%�������*�g}$o
��,�Z�R��,��K�Bzx�j%h���e���'�68�(\�JpU��z����W�#z������[�Y��R��7��,8�S��h���@�!���5��=���>ry�aO�mb%2_h���y�|+�X��&�����s��Y�����y���9��=��1���|��$��!���HYp���J=v!���w�b�=��
K�#}�3<z%6��,��*���T�-�T&��f�D��� �,��~ �����rbM?��uO.<x�Y�"���|��e�M�/���^<t�����m�������2������l5��Q�K�B����68$���I"��yF4��m�����8���x+7�"���@0������s1*/��Uy��1k:���Zm5u!��!_��|�@�q��Qj�����a��~�H�m!(mz�5��G���Vy�k>y�!/�����A_)T�1���F�����u\hh<���dZV���-��&�-/��"��l�V9�|�9+��^�e����kY���;=�:=y)/�L)R�ER�����I���Y�P�G��2Ka8�AA
�e���!vi��k�r��r��7�W��L��,h}9Tfq[��4��3�����d�@�1���!�2BN�Q:�l���!�qg�o,��]U�����cU��+/�`���[Z��9W�q�y����K�T����K�T�4*�K������A�2�R�B���2H#,�����V#���J$�����n&�I� r4eQ���]T:E�&e�.w���P��|K@���lk��H	]���=���v��������������C�fXo��]��	`B�������gUac�yg
�VQ�"�;H	���hc��a�4�
��F�
/F�41����u�@�n�����z5�
������7����� �������@���	������t��,���qwo��
H�+�q�uF�?�gD�T�:��+���V*�(4�s�<P��r\���|�+=8=�}�^�T��.��E���v�?�$"�C��h�Mc\u������|��C�Kq
��!@�����lY-���_f%����j�B��->�}	��g����������$Nb�X��u�	un(����5$
w;�w��+a���+�������N��I����7�]x������;eW��,��z'/���.���@V�����w�}���b�������2^��^�v^������ �b��o���Q�������%�hd����E�H��
'c�8�a����9�.u��
�Q�|=���-X�b��koF����M2�\0�/��@�M>��e��bL�:uL��3�L��D$�j��fMs}��p�{����Q�NW���S�&�<_�h����@���m��)���q���%�0�5*�/1G�N���b��8RY�U�7h��Q/V��E�+�s��-���	���d:�+��Z����M����ly+��@_'����������G3(3��Y�����2Wk�\����Z������jT[����1�'�l�V�������a����J��x����l)�Z[B/��[:�I2�25��/�;�G6{b
����Rc�O�^9�|�����|�93jA���@������Y7����z
����3��Z��E���f���)w�+|�����'�%�����}���`�_���V~}v��\�`������L�b�p���������>�u��2��Z%x=;����%{�_{��E
��a��^��wy�;�}�7�Z4�J���=�F��3*�� ����V/�^��$�����=���w�]0�:�S���
U���
�+b_��[���"�������z��8h�|,&sm�}��)o��Z�)l�`�C������X�u����%$�d<Fg:����{D������,��'D��L�F�0�*"� ��}��v�J	��4L��K�#���"��p�V���
��n��������
D"v����K��-��(����n�@[����q��M�|���N����y�M��*���NX�3(AS���s8�o( �C\���	�c?0�_���G�R��-v�XT��=�(��gw���>�C+������O����/�E4<���������_�~��[��k��X�/N�i�YS}�jT������,����7'������(�r��:�g�H[*�D�F�����?�����(����[����yl[�>�d���r'S;	�9�87��Lr{�����&$�{c����Yh�����a��d�;b7�!���d\d�p�)y�Zz��g�#�f��w&J<g�������HJ��@���_�qvur~����`��p=�q��h
f-�Sl%
}uH	�>��C�/C������<-�WH,������-#��o�g��$�%&�$��/�5h����w �t� 4<��S��"}��|�������x������_�l��.ci*��a���9Lt���]z�s�qyy^�^s	kO����0kF����
����	��E)�9{.P��,���Ov��)�*o�����<RgM��M�S>,�������l(,�=�e��/�gO���v�+���@#M1)���9n��rD�9��%�d�k���������
@��b�V��Z���5#XR��t�n�>U��@P&��Zd�J�D7�6�(�N�8�0��KI"s�A�X�qp$1��;��e�`O��w���
m^��������rc2)�_�_��Z�Dv^w�7�r���%�,��#&
B�m�z��6j����$`�����	j�i+ w~<�����5��
��+pk��A�
��;���z������6/$�:n`Q
�L`o��
��wfA#
h������D�m\CB}��4"jb���41�M@��D�r��pL`m~���ua�H�������������*';�e��m�i�V�|>0������1Q������B:��K9��*3�����U��jk�Q
#11Tom Lane
tgl@sss.pgh.pa.us
In reply to: Teodor Sigaev (#10)
Re: KNNGiST for knn-search (WIP)

Teodor Sigaev <teodor@sigaev.ru> writes:

Planner (find_usable_indexes function, actually) could push pathkey
expression into restriction clauses of index. I'm not fully satisfied
with this piece of code, but, may be, someone has a better idea. I
though about adding separate indexorderquals in IndexPath structure...

Done, IndexScan and IndexPath have separate field to store order clauses.

Why? Isn't that redundant with the pathkey structures? We generate
enough paths during a complex planning problem that I'm not in favor
of adding unnecessary structures to them.

regards, tom lane

#12Teodor Sigaev
teodor@sigaev.ru
In reply to: Tom Lane (#11)
Re: KNNGiST for knn-search (WIP)

Done, IndexScan and IndexPath have separate field to store order clauses.

Why? Isn't that redundant with the pathkey structures? We generate
enough paths during a complex planning problem that I'm not in favor
of adding unnecessary structures to them.

I found two ways to add support of knn-seaech to planner
- 0.4 version: add sorting clauses to restrictclauses in find_usable_indexes,
and there is two issues:
- find_usable_indexes could not be used to find indexes for index and bitmap
scans at once, because sorting clauses will be used in bitmap scan. Full
scan of index with knn-ordering on large index is much more expensive.
- implied/refused predicate machinery is teached to ignore sorting clauses,
but it's not so obvious: it should ignore operation returning non-boolean
values
- 0.4.1 version: pull sort clauses separately and merge them with regular
clauses at create_indexscan_plan function. That's solves problems above

Do you suggest to construct that clauses from pathkey representation? And append
constructed clauses to indexquals in create_indexscan_plan?
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

#13Tom Lane
tgl@sss.pgh.pa.us
In reply to: Teodor Sigaev (#12)
Re: KNNGiST for knn-search (WIP)

Teodor Sigaev <teodor@sigaev.ru> writes:

Do you suggest to construct that clauses from pathkey representation? And append
constructed clauses to indexquals in create_indexscan_plan?

I'd probably have to read the patch to make any intelligent suggestions
... and right now I'm busy with patches that are already in the
commitfest. But usually it's a good idea to postpone work to createplan
time if you can.

regards, tom lane

#14Robert Haas
robertmhaas@gmail.com
In reply to: Teodor Sigaev (#6)
Re: KNNGiST for knn-search (WIP)

2009/11/26 Teodor Sigaev <teodor@sigaev.ru>:

Hi!

Contrib module is reworked as a patch for current GiST. Now GiST supports
KNN-search, the query looks like
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
or
SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1
<-> '0,1';
Plans are:
EXPLAIN (COSTS OFF)
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
              QUERY PLAN
-----------------------------------------
 Index Scan using gpointind on point_tbl
  Index Cond: (f1 <-> '(0,1)'::point)
EXPLAIN (COSTS OFF)
SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1
<-> '0,1';
                                 QUERY PLAN
------------------------------------------------------------------------------
 Index Scan using gpointind on point_tbl
  Index Cond: ((f1 <@ '(10,10),(-10,-10)'::box) AND (f1 <-> '(0,1)'::point))

pg_am now has new column amcanorderbyop (can order by operation), indexes
with this flag enabled can be used to speedup operations, which returns
non-boolean value, currently type of returned value should have default
btree operator class  to perform sort.

Planner (find_usable_indexes function, actually) could push pathkey
expression into restriction clauses of index. I'm not fully satisfied with
this piece of code, but, may be, someone has a better idea. I though about
adding separate indexorderquals in IndexPath structure...

Both GiST's get methods are optimized and there is no overhead, since
gistrescan method can choose what traversal algorithm to use using
information about types of values returned by operations. If at least one of
them returns non-boolean result, then KNN-search will be performed.

The only change in interface of supporting functions is: consistentFn
function could return float8 non-negative value and it's mandatory to
perform KNN-search. Old-style consistent functions are supported.

Patch contains (it still requires rbtree-0.5 and point_ops-0.4 patches):
- GiST changes
- changes in point_ops to support knn-search
- contrib/pg_trgm now has new operation <-> returns distance between texts.
This operation is supported in KNN-search
- contrib/btree_gist provides <-> and its support for GiST for types int2,
int4, int8, float4, float8, money, oid, interval, time, date, timestamp and
timestamptz

TODO:
- selectivity of ordering operation should be 1.0
- current patch remove support of  IndexScanDesc->kill_prior_tuple, it's
needed to restore support if it will not create too big overhead
- documentation

Based on the feedback provided on this patch so far, it looks like
some changes are probably needed, but it's not entirely clear whether
the feedback provided is sufficient to provide guidance on what
changes should be made. It does also need to be updated to CVS HEAD,
as it no longer applies cleanly.

I tend to feel that we should probably target this for 8.6 rather than
8.5. We are down to the last CommitFest, and while we don't have a
nailed-down criterion for what is "too big" for the last CommitFest of
a given release cycle, this is definitely a big, invasive patch. This
patch weights in at over 2400 adds/removes, and it's not boilerplate
stuff like updates to pg_proc entries, but real, significant changes.
I'm worried that applying something like this late in the release
cycle is just not a good idea, especially given the fact that it
probably still needs significant revising. However, I'm fairly
conservative by nature, so perhaps someone else will have a different
opinion, or maybe there is a way to restructure it so that the needed
changes are less invasive.

...Robert

#15Oleg Bartunov
oleg@sai.msu.su
In reply to: Robert Haas (#14)
Re: KNNGiST for knn-search (WIP)

Robert,

On Wed, 30 Dec 2009, Robert Haas wrote:

Based on the feedback provided on this patch so far, it looks like
some changes are probably needed, but it's not entirely clear whether
the feedback provided is sufficient to provide guidance on what
changes should be made. It does also need to be updated to CVS HEAD,
as it no longer applies cleanly.

this is not a problem.

I tend to feel that we should probably target this for 8.6 rather than
8.5. We are down to the last CommitFest, and while we don't have a
nailed-down criterion for what is "too big" for the last CommitFest of
a given release cycle, this is definitely a big, invasive patch. This
patch weights in at over 2400 adds/removes, and it's not boilerplate
stuff like updates to pg_proc entries, but real, significant changes.
I'm worried that applying something like this late in the release
cycle is just not a good idea, especially given the fact that it
probably still needs significant revising. However, I'm fairly
conservative by nature, so perhaps someone else will have a different
opinion, or maybe there is a way to restructure it so that the needed
changes are less invasive.

the patch adds new strategy of gist tree traverse and doesn't change old one,
so there is no risk to ruin old code. I'm all for good conservatism, but
this is not the case, else we wouldn't have GiST at all. We are very
interested in the KNN to be in the 8.5 and we're ready to fix any issues.

From metodological point of view I don't quite understand how to measure
the value of development, I mean what'is a "big patch", "invasive patch".
Should we prefer cosmetic pathces, spelling fixes, etc ? Of course, they are
easy for refering, but people are waiting from us not just fixes, but new
features. For example, KNN-GiST is a big improvement for PostGIS community,
which is a big part of postgres users. Actually, it's PostGIS community, which
supported our work. Now, what we should say them ? The patch was too big and
invasive, so, sorry, wait one year more ? I think it's not good.

Robert, I'm not against you, it's your right to have your opinion. I address
this to other developers. It's important for us, since we have several
other patches ready, for example, long awaited phrase search
(http://www.sai.msu.su/~megera/wiki/2009-08-12). We postponed it, since
it was supposed that EDB will support it, but, hey, it wont. We did it for our
own. Teodor insist to submit it for 8.5, but I'm now begin to hesitate, what if
this patch will be also too big.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

#16Teodor Sigaev
teodor@sigaev.ru
In reply to: Robert Haas (#14)
2 attachment(s)
Re: KNNGiST for knn-search (WIP)

changes should be made. It does also need to be updated to CVS HEAD,
as it no longer applies cleanly.

The reason was a point_ops patch, some OIDs become duplicated. Both attached
patches are synced with current CVS.

I tend to feel that we should probably target this for 8.6 rather than
8.5. We are down to the last CommitFest, and while we don't have a
nailed-down criterion for what is "too big" for the last CommitFest of
a given release cycle, this is definitely a big, invasive patch. This

Is we really have rule to accept only small patches at last CommitFest? May be,
FixFest name is better for it? :)

Actually, it's easy to split patch to several ones:
- contrib/pg_trgm
- contrib/btree_gist
- knngist itself
- planner changes

And knngist depends on rbtree and point_ops patch, in summary 6 dependent
patches. Is it more comfortable?

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

Attachments:

builtin_knngist-0.5.1.gzapplication/x-tar; name=builtin_knngist-0.5.1.gzDownload
builtin_knngist-0.5.gzapplication/x-tar; name=builtin_knngist-0.5.gzDownload
#17Robert Haas
robertmhaas@gmail.com
In reply to: Oleg Bartunov (#15)
Re: KNNGiST for knn-search (WIP)

On Wed, Dec 30, 2009 at 9:20 AM, Oleg Bartunov <oleg@sai.msu.su> wrote:

From metodological point of view I don't quite understand how to measure
the value of development, I mean what'is a "big patch", "invasive patch".

I want to speak specifically to this question because I think it's a
good one. Of course, I also want to make clear that I have nothing
against you or your patch and that it sounds like a really nice
feature.

From my point of view, what makes a patch invasive is the likelihood
that it might break something other than itself. For example, your
patch touches the core planner code and the core GIST code, so it
seems possible that adding support for this feature might break
something else in one of those areas. All things being equal, we
would prefer to take that risk at the beginning of a development cycle
rather than the end. If your patch was the same size, but consisted
mostly of new code with very few changes to what is there now, it
might still be difficult to properly review and verify - but any bugs
we missed would likely affect only the NEW functionality, not any
EXISTING functionality.

Please understand that the previous paragraph is intended to be a
general statement about software development in general more than a
specific commentary on your particular patch. Whether applying your
patch in particular will break anything is, of course, something
that's difficult to know until we do it and see what happens, and at
this point I haven't even reviewed it. It's also possible that I'm
doing a poor job estimating the risk of breakage, and I certainly
welcome other opinions from other people in a position to make a
technical judgement on that point. I might also have a different
opinion myself after I review the patch in more detail, so please do
post an updated version.

Should we prefer cosmetic pathces, spelling fixes, etc ? Of course, they are
easy for refering, but people are waiting from us not just fixes, but new
features. For example, KNN-GiST is a big improvement for PostGIS community,
which is a big part of postgres users. Actually, it's PostGIS community,
which
supported our work. Now, what we should say them ? The patch was too big and
invasive, so, sorry, wait one year more ? I think it's not good.

Well, I understand your point, but there is obviously some deadline
for patches to be submitted for any particular release. Clearly,
after the last CommitFest is over, that deadline is past. However, we
have previously discussed having a policy that no new large patches
will be accepted for the last CommitFest that were not also submitted
for the second-to-last CommitFest. Hopefully it's obvious that I have
no desire to keep cool new features away from the PostGIS community,
the PostgreSQL community, or anyone else, but we have to weigh that
against the desire to have a stable and bug-free release, and applying
big patches at the last minute makes that less likely.

As an example, the change to run the background writer during recovery
and the changes in semi/anti join planning for 8.4 have both resulted
in multiple bug reports. The former was half the footprint of your
patch and applied at the very end of the release cycle; the latter was
slightly larger and applied in August 2008, so considerably earlier in
the cycle than this one could possibly be - and there were still
things we did not catch before release.

...Robert

#18Alvaro Herrera
alvherre@commandprompt.com
In reply to: Teodor Sigaev (#16)
Re: KNNGiST for knn-search (WIP)

Teodor Sigaev escribi�:

Actually, it's easy to split patch to several ones:
- contrib/pg_trgm
- contrib/btree_gist
- knngist itself
- planner changes

+1 on the split patches. I wonder about the opr_sanity test change ...
why is it necessary?

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

#19Robert Haas
robertmhaas@gmail.com
In reply to: Teodor Sigaev (#16)
Re: KNNGiST for knn-search (WIP)

2009/12/30 Teodor Sigaev <teodor@sigaev.ru>:

changes should be made.  It does also need to be updated to CVS HEAD,
as it no longer applies cleanly.

The reason was a point_ops patch, some OIDs become duplicated. Both attached
patches are synced with current CVS.

Thanks! I will take a look.

I tend to feel that we should probably target this for 8.6 rather than
8.5.  We are down to the last CommitFest, and while we don't have a
nailed-down criterion for what is "too big" for the last CommitFest of
a given release cycle, this is definitely a big, invasive patch.  This

Is we really have rule to accept only small patches at last CommitFest? May
be, FixFest name is better for it? :)

See here and following for some of the previous discussion - which was
not unanimous on all points:

http://archives.postgresql.org/pgsql-hackers/2009-09/msg00139.php

I think the intention is not to accept only bug fixes, but to limit
large features to those that have already been through a CommitFest or
two.

Actually, it's easy to split patch to several ones:
- contrib/pg_trgm
- contrib/btree_gist
- knngist itself
- planner changes

And knngist depends on rbtree and point_ops patch, in summary 6 dependent
patches. Is it more comfortable?

I'm not sure. One of the problems with separating out contrib module
changes is that it tends to obscure the point of the changes to the
core code. On the other hand if some of the core code changes can be
split out into an infrastructure patch that is of some independent
usefulness, that can certainly be worthwhile. It's not obvious to me
without looking at this more than I have whether there is a possble
split that makes sense here; I will read your updated patch.

...Robert

#20Robert Haas
robertmhaas@gmail.com
In reply to: Robert Haas (#19)
Re: KNNGiST for knn-search (WIP)

On Wed, Dec 30, 2009 at 12:16 PM, Robert Haas <robertmhaas@gmail.com> wrote:

2009/12/30 Teodor Sigaev <teodor@sigaev.ru>:

changes should be made.  It does also need to be updated to CVS HEAD,
as it no longer applies cleanly.

The reason was a point_ops patch, some OIDs become duplicated. Both attached
patches are synced with current CVS.

Thanks!  I will take a look.

OK, I'm confused. First, there are two versions of the patch here, so
I'm not sure which one I'm supposed to be looking at. Second, when I
attempt to apply either one, I get:

$ patch -p0 < ~/Download/builtin_knngist-0.5
patching file src/backend/access/gist/gistget.c
patching file src/backend/access/gist/gistproc.c
Reversed (or previously applied) patch detected! Assume -R? [n]

...regardless of how I answer that question, it then goes on to apply
most of the rest of the patch successfully.

Help?

...Robert

#21Greg Stark
gsstark@mit.edu
In reply to: Robert Haas (#17)
Re: KNNGiST for knn-search (WIP)

On Wed, Dec 30, 2009 at 4:56 PM, Robert Haas <robertmhaas@gmail.com> wrote:

From my point of view, what makes a patch invasive is the likelihood
that it might break something other than itself.  For example, your
patch touches the core planner code and the core GIST code, so it
seems possible that adding support for this feature might break
something else in one of those areas.

It doesn't seem obvious to me that this is a high-risk patch. It's
touching the planner which is tricky but it's not the kind of massive
overhaul that touches every module that HOT or HS were. I'm really
glad HS got in before the end because lots of people with different
areas of expertise and different use cases are going to get to
exercise it in the time remaining. This patch I would expect
relatively few people to need to try it out before any oversights are
caught.

--
greg

#22Paul Ramsey
pramsey@cleverelephant.ca
In reply to: Greg Stark (#21)
Re: KNNGiST for knn-search (WIP)

I'm sure whatever conclusion -hackers comes to in the end will be the
best for pgsql, and I'll be supportive. But until then, let me note
from the PostGIS point-of-view: sure would be great to get this in for
8.5 :)

P.

Show quoted text

On Thu, Dec 31, 2009 at 4:26 AM, Greg Stark <gsstark@mit.edu> wrote:

On Wed, Dec 30, 2009 at 4:56 PM, Robert Haas <robertmhaas@gmail.com> wrote:

From my point of view, what makes a patch invasive is the likelihood
that it might break something other than itself.  For example, your
patch touches the core planner code and the core GIST code, so it
seems possible that adding support for this feature might break
something else in one of those areas.

It doesn't seem obvious to me that this is a high-risk patch. It's
touching the planner which is tricky but it's not the kind of massive
overhaul that touches every module that HOT or HS were.  I'm really
glad HS got in before the end because lots of people with different
areas of expertise and different use cases are going to get to
exercise it in the time remaining. This patch I would expect
relatively few people to need to try it out before any oversights are
caught.

--
greg

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

#23Robert Haas
robertmhaas@gmail.com
In reply to: Paul Ramsey (#22)
Re: KNNGiST for knn-search (WIP)

On Mon, Jan 4, 2010 at 5:33 PM, Paul Ramsey <pramsey@cleverelephant.ca> wrote:

I'm sure whatever conclusion -hackers comes to in the end will be the
best for pgsql, and I'll be supportive. But until then, let me note
from the PostGIS point-of-view: sure would be great to get this in for
8.5 :)

That's good to know. The current status is that I've been waiting
for a patch that applies cleanly for 6 days, and we have 41 days left
until the end of the last CommitFest. There's not much I can do to
move this along until I have a clean patch to work with.

...Robert

#24Oleg Bartunov
oleg@sai.msu.su
In reply to: Robert Haas (#23)
Re: KNNGiST for knn-search (WIP)

Robert,

On Mon, 4 Jan 2010, Robert Haas wrote:

On Mon, Jan 4, 2010 at 5:33 PM, Paul Ramsey <pramsey@cleverelephant.ca> wrote:

I'm sure whatever conclusion -hackers comes to in the end will be the
best for pgsql, and I'll be supportive. But until then, let me note
from the PostGIS point-of-view: sure would be great to get this in for
8.5 :)

That's good to know. The current status is that I've been waiting
for a patch that applies cleanly for 6 days, and we have 41 days left
until the end of the last CommitFest. There's not much I can do to
move this along until I have a clean patch to work with.

sorry, it's a long holiday in Russia, we'll be able to sync next week.

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

#25Teodor Sigaev
teodor@sigaev.ru
In reply to: Robert Haas (#20)
5 attachment(s)
Re: KNNGiST for knn-search (WIP)

Changes:

- split patch to several ones
- sync with current CVS

Patch set is based on 0.5.1 version, difference between 0.5 and 0.6 should be
only in planner patch.

builtin_knngist_itself-0.6.gz - patch to the gist itself
builtin_knngist_proc-0.6.gz - patch for support knnsearch in point_ops
builtin_knngist_planner-0.6.gz - planner patch to support knnearch
builtin_knngist_contrib_btree_gist-0.6.gz - patch for contrib/btree_gist module
patch provides <-> operation for various scalar types which is
exactly abs(a - b) function
builtin_knngist_contrib_pg_trgm-0.6.gz - contrib/pg_trgm, like above,patch
provides <-> distance between strings

Patch set sill requires rbtree patch and point_ops patch (with Robert's changes)

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

Attachments:

builtin_knngist_contrib_btree_gist-0.6.gzapplication/x-tar; name=builtin_knngist_contrib_btree_gist-0.6.gzDownload
builtin_knngist_contrib_pg_trgm-0.6.gzapplication/x-tar; name=builtin_knngist_contrib_pg_trgm-0.6.gzDownload
builtin_knngist_itself-0.6.gzapplication/x-tar; name=builtin_knngist_itself-0.6.gzDownload
���LKgist�=ks�F���_1�U��D����bgeYNTQ$�$'�M�X JX�-k����<>d{w�����I`�1������h�zC�+T�X��p3/���hx�d��h8L���EZV��"�6��lq�;���+k�lmo���{�;j�����/>������pk�N��[�P������� ��������E����4�gq��:O�O��cT%��w����FYx7��gU^<�/q2�]�-&)��'i������*�Z��"y0��&ExwV����$���{g
�����:���:�MI�pZ�4���S�>����L�MR������:��Z8iV=yD�v>?|�:�&�T�W���y��c��b��UrS%�9�M����oW5�(-�(l9��g��|��~]��1�k�&c��g�������4��,QeO����f�iUty����[�)Bo5<v���:��W�g�QR����j8+`��I���Nh|-���2^Ml�bs��z�����bp?$�l{
���H�?��7����z��%�v��Gg��i����4���u�W�lxeI��P�x��R���`�5�)���L
mB
��������M�m_mO�z���YR����$��Q~�$qy}f�?��e	L]��-�$��a�����O�(�i�Q^������(�	��0�w/������c�}=%���eI�������� ��O2dZig
�>��e�^���^U�*�;]�\�
��(�e�^����-W
>�"��vy����z
�m���G'�?��<���G�+����;
$�YU��B&�L8]AfA�p�o�j6�=�~��}�~xr��;���!��u������?�88�~�w'�����-�<5I�dH�&N��]t;C��;�m�Z�It�e�U$�����o��q�^����8�5 ������-V2�/���'�]u����\�yRf�+U�����T-��[������5�Jk���:��D]}�i���a+�@,�_�iTVp+�Z`B�R �@l���J���*��Y\�z��.��$����#'���M��@�����P��E��p�����_�q������0��#�&�%J������bV0�%�m�K"��,>.��,`��u�+�etuzp���������
��m��	��6����?vu����	H�h�2�f�����jE8u���Q���]��2L�m�V��g���o��8�����*�D���%����
[	��A��v��	iv�7�M����1#��0������T]z,�6��z�����������F�B��$��hD���N�������������f�/��hS�s�G�Au�~h����Q�P��&����� ��.���@kx�a�(FeRv�m@��q����i����!�Qv9M��(�]�*�*f)����9PT\y��S�~����"��u;.��J���S��\U�^��f$]���������j�l}�������L�_a�n����Z3R
'j4��J�|�F��$�wy�,\��ul|�}D���D�j���d�����g������8*��,�}[��!��$d�������X{e������Z���
��[����NAe��S�,"5����������L��� Y!�: ���|��.�$�(l����^'��:����vf�?����)��i��`��(,l8�E{�h���eb]K=��*�y`�2c

k�8eb)���Q5���i�=\uP�����f�Sd]����:�����Z�e>������IKCL�.���~��Qx$���e���������I4}W���C��K;3�����~p7�6����F�k�����k�xx������[ml�[B�����E
.'��'>M�{���xsB��"I�.�������
]�}d>5|��r���������P|F���9�*Z3����q�e���2v]�Q�����eY��3+����jmoq��Y�����c������oON��f��w~���H&��l�k,�^r�A�)�5s�=A�+h�]�z����g�BX/���09A���d���0.3��4�JG7���x���/I+B�(�=N���.'�Q�Bn9�UW�C4�/�l�0��1LA��Er^�p�_�&C`M�����uqx~�9&v��76�������/��e��rW�r&��&���F�����h_�?���!O���Q{p�",E�,`���>`M�j,qR�e�ax���VW������b�m���5=���y*Am�n#�N>,sY���(T��	W���`��@�����;5&k�)���]�D@7!T�d2�n�����fh��U�z���~X`K���+������-�76��K�/c�-m�+�5zs�����A�h�|�F0��P}�ew��U�^�@�p�O�hg��0�6����Pk�(�u��}������#tK��Y������e�e�#��4+aB��"�M���|]�
�L?&����0�A�A�Lh$�r�	R���������
&t���v2��`+������z/k��H#���Ps�wM��l�o=~�hH�3��`�hi*g/�^�O��r�O�E�Z���rV&���q@@S�;1�MsAc��_��1�:r�s;��t������K��
����K�:�JJl#KC�}�����ljR)k�"�J+w��Q���id�&�a;s(j"�t�E
��O�]�U�(�����J\[����d��26���]�t���n��(�(�o�g7!z���K
��=Y�Z�E�z�}m}�$j5�����9�\�S#���m�.�2v��m���Ev��	a���>(a2hl�U��J"x]��U��m�B��|7o����f����3vW�hmi�����qS��g�1������qg�K�:s(}�@GY4VY����K$U�[z��]�l�:�������R801���
��R��P��Y�Qz����b%6}o�D/��I3�,t�A�H%w8]�r�:�?oM��z����Pc��q#�%���`IFrh�����������=�*(,T�.5�W$DL��t���]_&Rr��"�1����`
f7(RI�0�S������<���%��h���)'�|2-p���k)N�a0:[���������>>R�QK����c��J`�����.�
��X��u~�8U������������a5��tC�"�:Q	$L����KUT����Mi"V$��KP<{c�tcx�$��ZP���������L��:/P7�n3���(4U��aA5������}�)�f��|����6�R����:ugm��)��n�D�CJ�D�
�?n`8:��NF?%7��w����������V�Z���)GTnT�Z���Bp��BZ-��2��+yp�{��Iu�8�j�~^�J{
�*��4,"�*w�
��a��� �pg��
������jZ�Cx��g�cD/�V6�v}����zum�S�@��?��9%-�g����i�m�I{\������i�?�"_�[��*��i��@>\��v�{w���8�Mc�j��=����7
m4�.@QTg?���^Vw�{�`�Q�E�������h@���������,�]\�����9R�0����e������N�f�6
4�a
y8 �o�g�I�Th��x
���� '@���������E�����90�d7�-����>'�����X�q6���nND��j�Z�	-&�2���m�������~/N�@�ySMM:�w�����AWb�Q�����(.�`d��I,���������	I	\�P�p����x�#���]�tE������yf��T��*�&EL�>�4|K.nt���lP�L�`�A4��G���P4E
0�j����dcE)���Z�f��?J"	iu<�8`�?H�?�"����	9�#�&�nP}������X$bx�S�����J���#�M��%`�`���c�p�0�e�J���MrfJ�U:wK[Q�,^��H�@HN��������cBY���{(��50T/t��<���;��n�)�t2�[2��zs^���qi�8���m4{@�q��%��,j�����H/����^oW��5�<4���T�^&:�X�wN%q}0$Q0���K�o��&!�g��j��7�G;9�IQR�D�g������*����3�����;��I�K�w����AB�U0n�&A�E�6%
Zym�_��T�<&~��������Jz�sy�v��u�a������xT��4hdf���
D)k-m��~�BJf�6X�]�,}�J�����s��y$=�<�	U2�����D/����Hj�M�wS�������>K����0��N?��%��<m�J�Nf�	�b��$U�����&�7Y!�)��}�����p�;���i�lLt����&W��\�-B�"��g<�P��k�i���g
���5ZN���q~��O�������,��/-k���#kp�2��l�q���5������u�>-r���L�|�:G
�5O��	�U{�k����2[�2Ro��Zcfw�ms]�j�f�#�fw)n�P��Y�S�bG�7<�(+���e.�����l$)%C�����dj��0�np9g����@g�����=	jLj:���%�����)�&�06����[z���[��|�dD
od������]!�ps���>�;��������1lu�U�p���_�����!����z���7B�'E�f,�
�3�G�t|���_�^�z�������	\������z�r�zlp����YR�mkZ5�7Jhq[�K��e�����7�zq�U��,���;P�����ho�%��XC/��Uf��(�$�����,T���Q��
Z�7�N�V��BZ�g� �����3��������yF�j.����A7�uZ���Jt�w"��yo���%N���Y�KR��|o[����Nm��!����C��+���gK��������|����Iq�d(\�"����BP@��}quE�=W����p�]�A�}6R<?�m��l�#r������h(��4������#�D�5���p��)e�}��w�����Ro`���H�|L&��,-/`���t�")Ei�\��H#��A�Gn�-��\<M�2�5bdi\lb���r��&u����Xs�E�Z:1NE*Z��JF���e��/]@��QG��q������}~��2����^?�t_���j����06���2�s4<Xv��f�o�N���;Vu~,[�x���f���<�%&����`��t~E{���G�����h�I�n�M)~��f6��-w;+���KH���I�b:e�@�i��;�W����t�.���K�L�L��x5���m �P��mwp��R��g�����?z')��-?z��t��y���H$;z�}\lH��>�����������o���6������r�"
u:�hw\�X���-�8�g�D _gu�m3O�,K@s�����PR��I\&�#��.m9�F������H������D]�����Y�2���Q<�\�����Q����Yvy�Z�1�2����r�n�� ��pA��	�=�����b��q���v$�X{c7�"_^
��d�r���z��j/"����6XT�������*)���UR<}��Y��R�J��Ys�T�tg�*)�����JdW�}B�$���|��v
�2sv�����+x��_����z���@u�A�6�L�;L�sk�L;��C�"z90���td��2�������Um�������v"��U����4�d2������?���m<�L�����Rvy����)���_.�A2����8Y�"A��*HX�O+*����$��*��J�}d^�y6�9�K��HQGEa#���h���j�"���Jv�������S�Jb;}�p�U���y�GbR*}Y�w����M�ss���k���}���f����j�dxI\�������`y����g3�g�J�O(���I��P�,��}>bI����R��������b���|����y�T��������%�5W�
w����4�VP�����Sq����2Y0����(��z�����B�a��B�D�|����'F<s�����kB�.�wkmI���oN���44����\�����n��
f@ (�+�91��o�E��|�p�*�Sq��[��Z\��l���Fbwe��@������V���~{����"x!���uy�^N^F���������_��X�Q�l���R���J��gB:\\�����v-����������3.�@�`w�C��0rMT�ym�z���J�fH�dTM����G]��2��1��x�~v���X]�'LC�4l"[����yZ��
��J
��;�y���R�A��c&$�����v2�v���\�R��HF��"a2:f�N	����^��E�qN�z-9�����s�*���6C����k��1���#i��rgNT�Df��-�>�Q�4K'���(�nA�s)���������T�2�t���D�yg���H��k���(h�^��8�:�S���\�������K�����3G����]��XQ2G����n��w����P�w��c�o��c��84�K6�=�u�z���>�tWJG��~h�{��*�c��s�+��8u7������M�^�����<�M�S���_�����kln�l}h.���K��E`�9�X+pnyR��o�e/o�Y�V��)�������<�V9|�3<~n��s
���ox#�&�&�oq�����g�U�	4wK�NK�-�3�-���K�g�����w�ZM ��{�[�����70��a����]�3{<m��hQ��X��b��gi"�r��5� ���6L��k8�q����P��3Y�SY}
�l|�SX�����z��O���.���'��=����2`��v,����=_��������������F���'��p�y��M3����U3�d�w�p�o���P�_<~�b��jo�y��y�5/�1c�U���:��as1,>h���)a�\�M)�t�o��RU�����*�X������^�1.o2(��$l�ab��TP����PS1��#:q��t����&C�g�D�m��w"{��w�u��,���Z���e���-5Z�tc�a�$\"7�#�yV9��u�U+ia�W��{��^������S���C���
��K�V�q,Q�<K��a�����b
	���(�Wl��r$��2�(��)RgB��[
�n�1�D`N�4I���R����_
Of����YA��>�G���n�����L?�>��a����B�;��!;+/���uu����>�>3�s��������U��{e�QW�rmT*�yE��h��3��s���3�>q�.W��U��X�_)>lE4_|�g
�'
��L)�)+G�{�K���"���7���e��>P�)���e	.;F��=���J��
 �?1�N���M�o8,�������I�UI���CPB��~�:-q��`��4(����=x��L3����/R�0���\&��K}d�{Nq[[�V(}.�>���G����P�Kv���4�Bo�*�G,P��z?�O��0J��zH�%p��I&1(�:�#Lk2��p�<��n��(J����[���4�KN��8�X���K������$�:�����o�����/��z:�v�BZ�S��>O��FxX)��y��d�
����������{t��������K�����������aR:��{��5N�C�������;$/���a#����5y����"LQ�b�g�j��i0Z���V��7�Yc~����P�I��T8��o�]M�Y�{yONP�����t��O��[O���+v�����J��>�zrx�1�������q�>�A�&����Q/�Zb�����V(��DLwIE�0>s:o�����?��q<��n?��R�����������1d9���<F�qW�=ej1��+M�����?��v�/x�`Yr�\#;�
���R*J��������<�I�Z��H��01�Y�#��Q��m�T�k�|9��a����oKx�����*��� cNy�*���\�dS9j�a
CP/%E�?��o�_�a�����3WkZl�)ess��]�Nc��shg��vMgQa��%�y
g7b��n�-3�<��&�5k'�� G�:9���g��������W��[��6��,
[x��N�m|xhT���z���;��������19�w�; w��.$��XZ��Kc�Tc3��S�o3��r!��$���:�7/)$�x�@46��m��;,���"[+�?�>~�l?�<2w��V��'�sq�{��9�^���~$)O����E~
H���")�k���6g�q���qEn(f��� r4���e�~�Yu�)�r�*:���>F����n�o�G{o�����wT����������-���m���0�m��z�05'���_%��,���������}�.���T��r����������g���M�Uf�wl���|���������r0��PN'!��[D:$k�������P������R��av j�t���>)Z6/�Kk(�<������
0���|J���O�����#��A������<���-���v��3@q�f���q�������P0IyS��P��~��-���
Bg�Y�������5�>�$� cLk�P��;D'���S������%�L��7�g��c&Q��#kg�JBWw��b,HNsKi������=�m$����/2�.x�E�>#*�4U�A'�h����"�4Ct��P�{��0��U��)-���������������C�?`u%l�9��m����5��F��CC�,�r����/B�gBhx�C�|��Z_JV���������If�S��G	������L!LI�������T�l��a1�Z7�?�*���T���==����@�d���H#���8)�l ���&U;-�0���u����
[�I4?����Ao\>q��+U[7��;����g�N������6��K������]����������|�X�`�S�0�t���������u��~��[���	��nM��J����+�]��#)�����+~��@�S&�\}�-����c�#�3���������-���I�}}����_��sg+g)��{�nL��~���������z��_�%�z��}n����(~N_�#7�pQ�|k����=mk|�����^���70�������~����u�Y�/6d�v��t����
�x��<��"?
V�.����Z�����%��M�/��l�������{�`���{�����u������4Mx����el��~������yp|r�i94�{q�0���4�@�����q��g����@`��g
�4zIF�*����{q���QF��n�ics�o4<�V�ba�A���X�����9���b��>�:���\`�-���X�p��YrTCt�������'���r�F��������z���yd����Qa���;�k���D�����C��U��c��*�#�o�J�������E��[O��>���
%)H*�Y�O�����UL�F��1�fz���
�iO'���|�0�E������z���b�����w��i5�����A��>N&>!�!�Qy��|���v�]��_-R��A����/A
~����=��D�gr$���$���	�x�����������O��������z*�qigK�(@��L<�5�^m���B_5���F�4a4`B3h��>���'Mx�M��q��4:������)4=v�4�B4eK�E�21��Kf��Y�dR2���CIb$�5���xtkl���%�.�mLqzl��o��F��Q���Z�K��O����s��]�=��
builtin_knngist_planner-0.6.gzapplication/x-tar; name=builtin_knngist_planner-0.6.gzDownload
builtin_knngist_proc-0.6.gzapplication/x-tar; name=builtin_knngist_proc-0.6.gzDownload
#26Robert Haas
robertmhaas@gmail.com
In reply to: Teodor Sigaev (#25)
Re: KNNGiST for knn-search (WIP)

2010/1/12 Teodor Sigaev <teodor@sigaev.ru>:

Changes:

- split patch to several ones
- sync with current CVS

Patch set is based on 0.5.1 version, difference between 0.5 and 0.6 should
be only in planner patch.

builtin_knngist_itself-0.6.gz  - patch to the gist itself
builtin_knngist_proc-0.6.gz - patch for support knnsearch in point_ops
builtin_knngist_planner-0.6.gz - planner patch to support knnearch
builtin_knngist_contrib_btree_gist-0.6.gz - patch for contrib/btree_gist
module
              patch provides <-> operation for various scalar types which is
              exactly  abs(a - b) function
builtin_knngist_contrib_pg_trgm-0.6.gz - contrib/pg_trgm, like above,patch
              provides <-> distance between strings

Patch set sill requires rbtree patch and point_ops patch (with Robert's
changes)

Please update commitfest.postgresql.org.

...Robert