[PATCH] kNN for SP-GiST

From: Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru>
To: PostgreSQL mailing lists <pgsql-hackers(at)postgresql(dot)org>
Subject: [PATCH] kNN for SP-GiST
Date: 2017-01-30 23:07:43
Message-ID: 570825e8-47d0-4732-2bf6-88d67d2d51c8@postgrespro.ru
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hello hackers,

I'd like to present a series of patches which is a continuation of
Vlad Sterzhanov's work on kNN for SP-GiST that was done for GSOC'14.

Original thread: "KNN searches support for SP-GiST [GSOC'14]"
https://www.postgresql.org/message-id/CAK2aJC0-Jhrb3UjOZL+arBCHoTVwbeJVpRN-JOfEnN0vA6+MZQ@mail.gmail.com

I've done the following:
* rebased onto HEAD
* fixed several bugs
* fixed indentation and unnecessary whitespace changes
* implemented logic for order-by in spgvalidate() and spgproperty()
* used pairing_heap instead of RBTree for the priority queue
(as it was done earlier in GiST)
* used existing traversalValue* fields instead of the newly added suppValue* fields
* added caching of support functions infos
* added recheck support for distances
* refactored code
- simplified some places
- some functions were moved from spgproc.c to spgscan.c
(now spgproc.c contains only one public function spg_point_distance()
that can be moved somewhere and this file can be removed then)
- extracted functions spgTestLeafTuple(), spgMakeInnerItem()
* added new opclasses for circles and polygons with order-by-distance support
(it was originally intended for kNN recheck testing)
* improved tests for point_ops

Below is a very brief description of the patches:
1. Extracted two subroutines from GiST code (patch is the same as in "kNN for btree").
2. Exported two box functions that are used in patch 5.
3. Extracted subroutine from GiST code that is used in patch 4.
4. Main patch: added kNN support to SP-GiST.
5. Added ordering operators to kd_point_ops and quad_point_ops.
6. Added new SP-GiST support function spg_compress (gist_compress analogue)
for compressed (lossy) representation of types in SP-GiST, used in patch 7.
7. Added new SP-GiST quad-tree opclasses for circles and polygons
(reused existing quad-tree box_ops).

If you want to see the step-by-step sequence of changes applied to the original patch,
you can see it on my github: https://github.com/glukhovn/postgres/commits/knn_spgist

Please note that the tests for circle_ops and poly_ops will not work until
the а bug found in SP-GiST box_ops will not be fixed
(see https://www.postgresql.org/message-id/9ea5b157-478c-8874-bc9b-050076b7d042%40postgrespro.ru).

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Attachment Content-Type Size
0001-Extract-get_index_column_opclass-and-get_opclass_opfamily_and_input_type-v01.patch text/x-patch 5.1 KB
0002-Export-box_fill-and-box_copy-v01.patch text/x-patch 1.6 KB
0003-Extract-index_store_orderby_distances-v01.patch text/x-patch 5.5 KB
0004-Add-kNN-support-to-SP-GiST-v01.patch text/x-patch 48.7 KB
0005-Add-ordering-operators-to-SP-GiST-kd_point_ops-and-quad_point_ops-v01.patch text/x-patch 29.7 KB
0006-Add-spg_compress-method-to-SP-GiST-v01.patch text/x-patch 3.1 KB
0007-Add-SP-GiST-opclasses-poly_ops-and-circle_ops-v01.patch text/x-patch 47.2 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Michael Paquier 2017-01-30 23:41:49 Re: patch proposal
Previous Message Tom Lane 2017-01-30 23:04:27 Re: pg_hba_file_settings view patch