Re: [HACKERS] How to implement a SP-GiST index as a extension module? - Mailing list pgsql-hackers
| From | Connor Wolf |
|---|---|
| Subject | Re: [HACKERS] How to implement a SP-GiST index as a extension module? |
| Date | |
| Msg-id | CAAVqP=ovNn4DBH3u7d36pcJ4W3_osvh7kr7wEfmAhrKbPGvVww@mail.gmail.com Whole thread Raw |
| In response to | Re: [HACKERS] How to implement a SP-GiST index as a extension module? (Robert Haas <robertmhaas@gmail.com>) |
| Responses |
Re: [HACKERS] How to implement a SP-GiST index as a extension module?
(Alexander Korotkov <a.korotkov@postgrespro.ru>)
|
| List | pgsql-hackers |
Yeah, unfortunately, the way these type of metric trees work, the entire search procedure is a function of both the target value and the allowed search distance. The only way I can think of to return ordered results without just scanning the entire index would be to repeatedly search the index while gradually incrementing the allowed search distance (which is horrible).
From looking at some of the contrib modules, the way other index libraries that have similar needs manage it is by implementing custom types that encapsulate the filter parameters. The sp-gist kd-tree and quadtree indexes store point coordinates in n-dimensional space, but they (ab)use the BOX type because it's a convenient way of passing multiple values into the value parameter of the index query.
I'm thinking at this point, I'm mostly stuck having to define a custom type to encapsulate the relevant parameters. Really, the filter condition is a integer 2-tuple, so I wonder if I could do something horrible with the array type. If the value parameter for the query could be a bigint array[2], that would work, and I'd just have to remember the ordering.
Does that seem viable?
EDIT: That's actually exactly how the example I'm working off of works. DERP. The SQL is
CREATE TYPE vptree_area AS
(
center _int4,
distance float8
);
CREATE OR REPLACE FUNCTION vptree_area_match(_int4, vptree_area) RETURNS boolean AS
'MODULE_PATHNAME','vptree_area_match'
LANGUAGE C IMMUTABLE STRICT;
CREATE OPERATOR <@ (
LEFTARG = _int4,
RIGHTARG = vptree_area,
PROCEDURE = vptree_area_match,
RESTRICT = contsel,
JOIN = contjoinsel);
so I just need to understand how to parse out the custom type in my index operator.
------
Sorry if I'm asking a lot of dumb questions. Postgresql is huge and I have no idea what I'm really doing.
On Fri, Nov 3, 2017 at 12:20 AM, Robert Haas <robertmhaas@gmail.com> wrote:
On Thu, Nov 2, 2017 at 9:53 AM, Connor Wolf
<connorw@imaginaryindustries.com> wrote:
> As such:
> Will compound queries as I describe above basically require a custom type to
> make it possible? My (admittedly naive) expectation
> is that the eventual query for this index will look something like "SELECT *
> FROM example_table WHERE indexed_column <=> target_value < 4;",
> with "<=>" being the operator for the relevant distance calculation
> (hamming, for the BK tree, numeric for the VP-tree).
>
> The existing VP-tree code appears to not support multiple operators
> whatsoever, probably because it was very preliminary.
I'm not an expert in this area in any way whatsoever; I don't know a
VP-tree from a BK-tree from a maple tree.
However, I can tell you that as a general rule, PostgreSQL index
access methods can only apply index quals of the form "WHERE column op
value" or ordering criteria of the form "ORDER BY column op value".
So, in the above example, you might think about trying to set up the
access method so that it can efficiently return values ordered by
indexed_column <=> target_value and then wrapping the ORDER BY query
in a subselect to cut off fetching values at the correct point. But
no operator class for any access method can directly handle that query
efficiently as you've written it.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
pgsql-hackers by date: