Re: KNNGiST for knn-search (WIP)
От | Teodor Sigaev |
---|---|
Тема | Re: KNNGiST for knn-search (WIP) |
Дата | |
Msg-id | 4B0EAE0D.606@sigaev.ru обсуждение исходный текст |
Ответ на | KNNGiST for knn-search (Teodor Sigaev <teodor@sigaev.ru>) |
Ответы |
Re: KNNGiST for knn-search (WIP)
Re: KNNGiST for knn-search (WIP) |
Список | pgsql-hackers |
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/
Вложения
В списке pgsql-hackers по дате отправления: