Re: How to implement a SP-GiST index as a extension module?

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(at)gmail(dot)com> wrote:

> On Thu, Nov 2, 2017 at 9:53 AM, Connor Wolf
> <connorw(at)imaginaryindustries(dot)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
>