Index only scan for cube and seg

On Thu, Oct 26, 2017 at 12:22 PM, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

For cube there is new default opclass.

I seem to recall that changing the default opclass causes unsolvable
problems with upgrades. You might want to check the archives for
previous discussions of this issue; unfortunately, I don't recall the
details off-hand.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Oct 26, 2017 at 12:22 PM, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

For cube there is new default opclass.

I seem to recall that changing the default opclass causes unsolvable
problems with upgrades. You might want to check the archives for
previous discussions of this issue; unfortunately, I don't recall the
details off-hand.

Quite aside from that, replacing the opclass with a new one creates
user-visible headaches that I don't think are justified, i.e. having to
reconstruct indexes in order to get the benefit.

Maybe I'm missing something, but ISTM you could just drop the compress
function and call it good. This would mean that an IOS scan would
sometimes hand back a toast-compressed value, but what's the problem
with that?

(The only reason for making a decompress function that just detoasts
is that your other support functions then do not have to consider
the possibility that they're handed a toast-compressed value. I have
not checked whether that really matters for cube.)

regards, tom lane

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

On Fri, Oct 27, 2017 at 9:54 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Oct 26, 2017 at 12:22 PM, Andrey Borodin <x4mmm@yandex-team.ru>

wrote:

For cube there is new default opclass.

I seem to recall that changing the default opclass causes unsolvable
problems with upgrades. You might want to check the archives for
previous discussions of this issue; unfortunately, I don't recall the
details off-hand.

Quite aside from that, replacing the opclass with a new one creates
user-visible headaches that I don't think are justified, i.e. having to
reconstruct indexes in order to get the benefit.

Maybe I'm missing something, but ISTM you could just drop the compress
function and call it good. This would mean that an IOS scan would
sometimes hand back a toast-compressed value, but what's the problem
with that?

+1,
I think in this case replacing default opclass or even duplicating opclass
isn't justified.

(The only reason for making a decompress function that just detoasts

is that your other support functions then do not have to consider
the possibility that they're handed a toast-compressed value. I have
not checked whether that really matters for cube.)

As I can see, cube GiST code always uses DatumGetNDBOX() macro to transform
Datum to (NDBOX *).

#define DatumGetNDBOX(x) ((NDBOX *) PG_DETOAST_DATUM(x))

Thus, it should be safe to just remove both compress/decompress methods
from existing opclass.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi!

29 окт. 2017 г., в 2:24, Alexander Korotkov <a.korotkov@postgrespro.ru> написал(а):

As I can see, cube GiST code always uses DatumGetNDBOX() macro to transform Datum to (NDBOX *).

#define DatumGetNDBOX(x) ((NDBOX *) PG_DETOAST_DATUM(x))

Thus, it should be safe to just remove both compress/decompress methods from existing opclass.

Alexander, Tom, you are absolutely right. I was sure there is toasting code in cube's compress, but it was not ever there.

Here is patch for cube that drops functions.

Best regards, Andrey Borodin.

Hi there!

I'm looking at implementing a custom indexing scheme, and I've been
having trouble understanding the proper approach.

Basically, I need a BK tree, which is a tree-structure useful for
indexing arbitrary discrete metric-spaces (in my case, I'm interested in
indexing across the hamming edit-distance of perceptual hashes, for
fuzzy image searching). I'm /pretty/ sure a SP-GiST index is the correct
index type, as my tree is intrinsically unbalanced.

I have a functional stand-alone implementation of a BK-Tree, and it
works very well, but the complexity of managing what is basically a
external index for my database has reached the point where it's
significantly problematic, and it seems to be it should be moved into
the database.

Anyways, looking at the contents of postgres/src/backend/access/spgist,
it looks pretty straightforward in terms of the actual C implementation,
but I'm stuck understanding how to "install" a custom SP-GiST
implementation. There are several GiST indexing implementations in the
contrib directory, but no examples for how I'd go about implementing a
loadable SP-GiST index.

Basically, my questions are:

* Is it possible to implement a SP-GiST indexing scheme as a loadable
module?
o If so, how?
o And is there an example I can base my implementation off of?

I'm relatively comfortable with C (much moreso with C++), but I haven't
spent a lot of time looking at the postgresql codebase.  I don't think I
could start from a empty folder and make a properly-implemented module
in any reasonable period of time, so if I have a working example for
some sort of index that uses the same interfaces that would really help
a lot.

Thanks!
Connor

On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
<wolf@imaginaryindustries.com> wrote:

Hi there!

I'm looking at implementing a custom indexing scheme, and I've been having
trouble understanding the proper approach.

Basically, I need a BK tree, which is a tree-structure useful for indexing
arbitrary discrete metric-spaces (in my case, I'm interested in indexing
across the hamming edit-distance of perceptual hashes, for fuzzy image
searching). I'm pretty sure a SP-GiST index is the correct index type, as my
tree is intrinsically unbalanced.

I have a functional stand-alone implementation of a BK-Tree, and it works
very well, but the complexity of managing what is basically a external index
for my database has reached the point where it's significantly problematic,
and it seems to be it should be moved into the database.

Anyways, looking at the contents of postgres/src/backend/access/spgist, it
looks pretty straightforward in terms of the actual C implementation, but
I'm stuck understanding how to "install" a custom SP-GiST implementation.
There are several GiST indexing implementations in the contrib directory,
but no examples for how I'd go about implementing a loadable SP-GiST index.

Basically, my questions are:

Is it possible to implement a SP-GiST indexing scheme as a loadable module?

If so, how?
And is there an example I can base my implementation off of?

Look on RUM access method ( https://github.com/postgrespro/rum ) we
developed using
api available since 9.6.

I'm relatively comfortable with C (much moreso with C++), but I haven't
spent a lot of time looking at the postgresql codebase. I don't think I
could start from a empty folder and make a properly-implemented module in
any reasonable period of time, so if I have a working example for some sort
of index that uses the same interfaces that would really help a lot.

Thanks!
Connor

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

On Mon, Oct 30, 2017 at 12:05 PM, Oleg Bartunov <obartunov@gmail.com> wrote:

On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
<wolf@imaginaryindustries.com> wrote:

Hi there!

I'm looking at implementing a custom indexing scheme, and I've been having
trouble understanding the proper approach.

Basically, I need a BK tree, which is a tree-structure useful for indexing
arbitrary discrete metric-spaces (in my case, I'm interested in indexing
across the hamming edit-distance of perceptual hashes, for fuzzy image
searching). I'm pretty sure a SP-GiST index is the correct index type, as my
tree is intrinsically unbalanced.

I have a functional stand-alone implementation of a BK-Tree, and it works
very well, but the complexity of managing what is basically a external index
for my database has reached the point where it's significantly problematic,
and it seems to be it should be moved into the database.

Anyways, looking at the contents of postgres/src/backend/access/spgist, it
looks pretty straightforward in terms of the actual C implementation, but
I'm stuck understanding how to "install" a custom SP-GiST implementation.
There are several GiST indexing implementations in the contrib directory,
but no examples for how I'd go about implementing a loadable SP-GiST index.

Basically, my questions are:

Is it possible to implement a SP-GiST indexing scheme as a loadable module?

If so, how?
And is there an example I can base my implementation off of?

Look on RUM access method ( https://github.com/postgrespro/rum ) we
developed using
api available since 9.6.

or even simple, there is contrib/bloom access method, which illustrates
developing access method as an extension.

I'm relatively comfortable with C (much moreso with C++), but I haven't
spent a lot of time looking at the postgresql codebase. I don't think I
could start from a empty folder and make a properly-implemented module in
any reasonable period of time, so if I have a working example for some sort
of index that uses the same interfaces that would really help a lot.

Thanks!
Connor

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

Hi!

On Sun, Oct 29, 2017 at 12:07 PM, Connor Wolf <wolf@imaginaryindustries.com>
wrote:

I'm looking at implementing a custom indexing scheme, and I've been having
trouble understanding the proper approach.

Basically, I need a BK tree, which is a tree-structure useful for indexing
arbitrary discrete metric-spaces (in my case, I'm interested in indexing
across the hamming edit-distance of perceptual hashes, for fuzzy image
searching). I'm *pretty* sure a SP-GiST index is the correct index type,
as my tree is intrinsically unbalanced.

Yes, SP-GiST is appropriate index type for BK tree. I'm pretty sure BK
tree could be implemented as SP-GiST opclass.
The only thing worrying me is selection pivot values for nodes. SP-GiST
builds by insertion of index tuples on by one. First pivot value for root
node in SP-GIST would be created once first leaf page overflows. Thus, you
would have to select this pivot value basing on very small fraction in the
beginning of dataset.
As I know, BK tree is most efficient when root pivot value is selected
after looking in whole dataset and then hierarchically to subtrees.

BTW, did you try my extension for searching similar images. It's quite
primitive, but works for some cases.
https://github.com/postgrespro/imgsmlr
https://wiki.postgresql.org/images/4/43/Pgcon_2013_similar_images.pdf

I have a functional stand-alone implementation of a BK-Tree, and it works

very well, but the complexity of managing what is basically a external
index for my database has reached the point where it's significantly
problematic, and it seems to be it should be moved into the database.

Sure, moving this index to the database is right decision.

Anyways, looking at the contents of postgres/src/backend/access/spgist, it

looks pretty straightforward in terms of the actual C implementation, but
I'm stuck understanding how to "install" a custom SP-GiST implementation.
There are several GiST indexing implementations in the contrib directory,
but no examples for how I'd go about implementing a loadable SP-GiST index.

Basically, my questions are:

- Is it possible to implement a SP-GiST indexing scheme as a loadable
module?

Yes, it's possible to define SP-GiST.

- If so, how?

The pretty same way as GiST opclass extension. You have to define

supporting functions and operators and then define operator class over them.

- And is there an example I can base my implementation off of?

I'm relatively comfortable with C (much moreso with C++), but I haven't
spent a lot of time looking at the postgresql codebase. I don't think I
could start from a empty folder and make a properly-implemented module in
any reasonable period of time, so if I have a working example for some sort
of index that uses the same interfaces that would really help a lot

I don't think there is an example in PostgreSQL source code tree or on
github. But I've attached by early experiment with VP-tree (seems to be
pretty same as BK tree) using SP-GiST (see vptree.tar.gz). Basing on this
experiment I realized that it's important to select root pivot value basing
on the whole dataset. However, for your metric/dataset/queries it might
appear to be different.

It also would be nice to someday improve SP-GiST to support some global
strategies on index creation. In particular, it would allow to resolve
selection of pivot values problem that I mention above. Right now my
colleagues and me don't have time for that. But I can assist you with
advises if you will decide to implement that.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Oct 30, 2017 at 2:07 PM, Oleg Bartunov <obartunov@gmail.com> wrote:

On Mon, Oct 30, 2017 at 12:05 PM, Oleg Bartunov <obartunov@gmail.com>
wrote:

On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
<wolf@imaginaryindustries.com> wrote:

Hi there!

I'm looking at implementing a custom indexing scheme, and I've been

having

trouble understanding the proper approach.

Basically, I need a BK tree, which is a tree-structure useful for

indexing

arbitrary discrete metric-spaces (in my case, I'm interested in indexing
across the hamming edit-distance of perceptual hashes, for fuzzy image
searching). I'm pretty sure a SP-GiST index is the correct index type,

as my

tree is intrinsically unbalanced.

I have a functional stand-alone implementation of a BK-Tree, and it

works

very well, but the complexity of managing what is basically a external

index

for my database has reached the point where it's significantly

problematic,

and it seems to be it should be moved into the database.

Anyways, looking at the contents of postgres/src/backend/access/spgist,

it

looks pretty straightforward in terms of the actual C implementation,

but

I'm stuck understanding how to "install" a custom SP-GiST

implementation.

There are several GiST indexing implementations in the contrib

directory,

but no examples for how I'd go about implementing a loadable SP-GiST

index.

Basically, my questions are:

Is it possible to implement a SP-GiST indexing scheme as a loadable

module?

If so, how?
And is there an example I can base my implementation off of?

Look on RUM access method ( https://github.com/postgrespro/rum ) we
developed using
api available since 9.6.

or even simple, there is contrib/bloom access method, which illustrates
developing access method as an extension.

I think Connor struggles to implement just an operator class. Advising him
to implement an index access method is a good way to get him away of
PostgreSQL hacking for a long time :)

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Korotkov <a.korotkov@postgrespro.ru> writes:

I think Connor struggles to implement just an operator class. Advising him
to implement an index access method is a good way to get him away of
PostgreSQL hacking for a long time :)

Yeah. To answer the question a bit more directly: there are not any
contrib modules that add SP-GiST opclasses, but there are some that add
GiST or GIN opclasses, so any one of those would serve as a model for the
basic mechanism of writing an extension. Just replace the AM-specific
support functions for those AMs with the ones SP-GiST uses. (You can crib
some code details from the in-core SP-GiST support functions.)

regards, tom lane

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

I was mostly unclear on how I'd go about attaching the extension functions
to the relevant indexing mechanism. From the looks of the vptree.tar.gz
file (which is really, *really* helpful, incidentally!), a it's done via a
custom operator class, which then gets passed to the actual index creation
mechanism when you're declaring the index.

I think I had looked at that at one point, but it's been a while. In my
case, I'm using discrete-cosine-transform based perceptual hashes for
searching. They are nice and compact (64-bits per hash), while still
producing good search results. I have a dataset of ~36 million images, and
it does searches in < 50 milliseconds with a hamming distance of 4, while
touching ~0.25% of the tree (And occupying ~18 GB of ram).

My BK tree is up on github here
<https://github.com/fake-name/IntraArchiveDeduplicator/blob/master/deduplicator/bktree.hpp&gt;,
if anyone needs something like that (BSD licensed, pretty well tested).
There's also a python wrapper for it.

I'll probably not have time to poke about until this weekend, but thanks!
Connor

On Mon, Oct 30, 2017 at 4:50 AM, Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:

Ok, more questions.

I've been studying the implementation Alexander Korotkov sent, and I'm not
seeing how to map
some of the components onto the changes in the SP-GiST system that occured
between Postgresql 9.2 and 9.3.

The changes at that point seem to have been to change xxx_inner_consistent
and xxx_leaf_consistent from taking
an input containing a Datum pointing to the query conditional to a list of
ScanKeys which each encapsulate one filter condition.

The issue here is that for VP trees (or the BK tree I want to eventually
implement), the filter condition requires two parameters:
- The maximum allowed distance from the target value
- The actual target value.

The ScanKeys struct appears to only be able to contain a conditional type,
and a single parameter, such as "less then *x*", "above *y*",
and so forth. Looking at the existing spgkdtreeproc.c and
spgquadtreeproc.c, their mechanism for passing more complex conditions
through to the xxx_consistent functions appears to be to encapsulate the
entire condition in a custom type. For example,
their mechanism for querying if something is within a certain envelope is
done by having the envelope be described
by the "BOX" type.

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.

Thanks!
Connor

On Mon, Oct 30, 2017 at 7:04 PM, Connor Wolf <
connorw@imaginaryindustries.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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/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 Fri, Nov 3, 2017 at 12:37 PM, Connor Wolf <
connorw@imaginaryindustries.com> wrote:

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.

You can see the implementation of vptree_area_match function located in
vptree.c. It just calls GetAttributeByNum() function.

There is also alternative approach for that implemented in pg_trgm contrib
module. It has "text % text" operator which checks if two strings are
similar enough. The similarity threshold is defined by
pg_trgm.similarity_threshold GUC. Thus, you can also define GUC with
threshold distance value. However, it would place some limitations. For
instance, you wouldn't be able to use different distance threshold in the
same query.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Ok, I've got everything compiling and it installs properly, but I'm running
into problems that I think are either a side-effect of implementing
picksplit incorrectly (likely), or a bug in SP-GiST(?).

Program received signal SIGSEGV, Segmentation fault.
__memcpy_sse2_unaligned () at
../sysdeps/x86_64/multiarch/memcpy-sse2-unaligned.S:159
159 ../sysdeps/x86_64/multiarch/memcpy-sse2-unaligned.S: No such file
or directory.
(gdb) bt
#0 __memcpy_sse2_unaligned () at
../sysdeps/x86_64/multiarch/memcpy-sse2-unaligned.S:159
#1 0x00000000004ecd66 in memcpy (__len=16, __src=<optimized out>,
__dest=0x13c9dd8) at /usr/include/x86_64-linux-gnu/bits/string3.h:53
#2 memcpyDatum (target=target@entry=0x13c9dd8, att=att@entry=0x7fff327325f4,
datum=datum@entry=18445692987396472528) at spgutils.c:587
#3 0x00000000004ee06b in spgFormInnerTuple (state=state@entry=0x7fff327325e0,
hasPrefix=<optimized out>, prefix=18445692987396472528, nNodes=8,
nodes=nodes@entry=0x13bd340) at spgutils.c:741
#4 0x00000000004f508b in doPickSplit (index=index@entry=0x7f2cf9de7f98,
state=state@entry=0x7fff327325e0, current=current@entry=0x7fff32732020,
parent=parent@entry=0x7fff32732040,
newLeafTuple=newLeafTuple@entry=0x13b9f00,
level=level@entry=0, isNulls=0 '\000', isNew=0 '\000') at spgdoinsert.c:913
#5 0x00000000004f6976 in spgdoinsert (index=index@entry=0x7f2cf9de7f98,
state=state@entry=0x7fff327325e0, heapPtr=heapPtr@entry=0x12e672c,
datum=12598555199787281,
isnull=0 '\000') at spgdoinsert.c:2053
#6 0x00000000004ee5cc in spgistBuildCallback
(index=index@entry=0x7f2cf9de7f98,
htup=htup@entry=0x12e6728, values=values@entry=0x7fff327321e0,
isnull=isnull@entry=0x7fff32732530 "", tupleIsAlive=tupleIsAlive@entry=1
'\001', state=state@entry=0x7fff327325e0) at spginsert.c:56
#7 0x0000000000534e8d in IndexBuildHeapRangeScan
(heapRelation=heapRelation@entry=0x7f2cf9ddc6c8,
indexRelation=indexRelation@entry=0x7f2cf9de7f98,
indexInfo=indexInfo@entry=0x1390ad8, allow_sync=allow_sync@entry=1
'\001', anyvisible=anyvisible@entry=0 '\000',
start_blockno=start_blockno@entry=0,
numblocks=4294967295, callback=0x4ee573 <spgistBuildCallback>,
callback_state=0x7fff327325e0) at index.c:2609
#8 0x0000000000534f52 in IndexBuildHeapScan
(heapRelation=heapRelation@entry=0x7f2cf9ddc6c8,
indexRelation=indexRelation@entry=0x7f2cf9de7f98,
indexInfo=indexInfo@entry=0x1390ad8, allow_sync=allow_sync@entry=1
'\001', callback=callback@entry=0x4ee573 <spgistBuildCallback>,
callback_state=callback_state@entry=0x7fff327325e0) at index.c:2182
#9 0x00000000004eeb74 in spgbuild (heap=0x7f2cf9ddc6c8,
index=0x7f2cf9de7f98, indexInfo=0x1390ad8) at spginsert.c:140
#10 0x0000000000535e55 in index_build
(heapRelation=heapRelation@entry=0x7f2cf9ddc6c8,
indexRelation=indexRelation@entry=0x7f2cf9de7f98,
indexInfo=indexInfo@entry=0x1390ad8, isprimary=isprimary@entry=0
'\000', isreindex=isreindex@entry=0 '\000') at index.c:2043
#11 0x0000000000536ee8 in index_create
(heapRelation=heapRelation@entry=0x7f2cf9ddc6c8,
indexRelationName=indexRelationName@entry=0x12dd600 "int8idx_2",
indexRelationId=16416, indexRelationId@entry=0, relFileNode=0,
indexInfo=indexInfo@entry=0x1390ad8, indexColNames=indexColNames@entry
=0x1390f40,
accessMethodObjectId=4000, tableSpaceId=0, collationObjectId=0x12e6b18,
classObjectId=0x12e6b38, coloptions=0x12e6b58, reloptions=0, isprimary=0
'\000',
isconstraint=0 '\000', deferrable=0 '\000', initdeferred=0 '\000',
allow_system_table_mods=0 '\000', skip_build=0 '\000', concurrent=0 '\000',
is_internal=0 '\000', if_not_exists=0 '\000') at index.c:1116
#12 0x00000000005d8fe6 in DefineIndex (relationId=relationId@entry=16413,
stmt=stmt@entry=0x12dd568, indexRelationId=indexRelationId@entry=0,
is_alter_table=is_alter_table@entry=0 '\000',
check_rights=check_rights@entry=1 '\001',
check_not_in_use=check_not_in_use@entry=1 '\001', skip_build=0 '\000',
quiet=0 '\000') at indexcmds.c:667
#13 0x0000000000782057 in ProcessUtilitySlow (pstate=pstate@entry=0x12dd450,
pstmt=pstmt@entry=0x12db108,
queryString=queryString@entry=0x12da0a0 "CREATE INDEX int8idx_2 ON
int8tmp_2 USING spgist ( a vptree_ops );", context=context@entry
=PROCESS_UTILITY_TOPLEVEL,
params=params@entry=0x0, queryEnv=queryEnv@entry=0x0, dest=0x12db200,
completionTag=0x7fff32732ed0 "") at utility.c:1326
#14 0x00000000007815ef in standard_ProcessUtility (pstmt=0x12db108,
queryString=0x12da0a0 "CREATE INDEX int8idx_2 ON int8tmp_2 USING spgist ( a
vptree_ops );",
context=PROCESS_UTILITY_TOPLEVEL, params=0x0, queryEnv=0x0,
dest=0x12db200, completionTag=0x7fff32732ed0 "") at utility.c:928
#15 0x00000000007816a7 in ProcessUtility (pstmt=pstmt@entry=0x12db108,
queryString=<optimized out>, context=context@entry=PROCESS_UTILITY_TOPLEVEL,
params=<optimized out>, queryEnv=<optimized out>,
dest=dest@entry=0x12db200,
completionTag=0x7fff32732ed0 "") at utility.c:357
#16 0x000000000077de2e in PortalRunUtility (portal=portal@entry=0x1391a80,
pstmt=pstmt@entry=0x12db108, isTopLevel=isTopLevel@entry=1 '\001',
setHoldSnapshot=setHoldSnapshot@entry=0 '\000', dest=dest@entry=0x12db200,
completionTag=completionTag@entry=0x7fff32732ed0 "") at pquery.c:1178
#17 0x000000000077e98e in PortalRunMulti (portal=portal@entry=0x1391a80,
isTopLevel=isTopLevel@entry=1 '\001', setHoldSnapshot=setHoldSnapshot@entry=0
'\000',
dest=dest@entry=0x12db200, altdest=altdest@entry=0x12db200,
completionTag=completionTag@entry=0x7fff32732ed0 "") at pquery.c:1324
#18 0x000000000077f782 in PortalRun (portal=portal@entry=0x1391a80,
count=count@entry=9223372036854775807, isTopLevel=isTopLevel@entry=1 '\001',
run_once=run_once@entry=1 '\001', dest=dest@entry=0x12db200,
altdest=altdest@entry=0x12db200, completionTag=0x7fff32732ed0 "") at
pquery.c:799
#19 0x000000000077bc12 in exec_simple_query
(query_string=query_string@entry=0x12da0a0
"CREATE INDEX int8idx_2 ON int8tmp_2 USING spgist ( a vptree_ops );")
at postgres.c:1120
#20 0x000000000077d95c in PostgresMain (argc=<optimized out>,
argv=argv@entry=0x12e9948, dbname=0x12bca10 "contrib_regression",
username=<optimized out>)
at postgres.c:4139
#21 0x00000000006fecf4 in BackendRun (port=port@entry=0x12de030) at
postmaster.c:4364
#22 0x0000000000700e32 in BackendStartup (port=port@entry=0x12de030) at
postmaster.c:4036
#23 0x0000000000701112 in ServerLoop () at postmaster.c:1755
#24 0x00000000007023af in PostmasterMain (argc=argc@entry=8,
argv=argv@entry=0x12ba7c0)
at postmaster.c:1363
#25 0x00000000006726c1 in main (argc=8, argv=0x12ba7c0) at main.c:228

It's segfaulting when trying to build the inner tuple after the picksplit
operation.

Adding debugging output to the print function, I see:

NOTICE: Memcopying from 0000000000000000 to 00000000013d7938 with len 16

The first item in my input data file is zero, and if I change it to 1:

NOTICE: Memcopying from 0000000000000001 to 0000000001b45938 with len 16

So pretty clearly, I'm trying to copy from the literal data representation
of the data as an address.
Following the data, this is the value I'm assigning to out->prefixDatum in
my picksplit call. I can confirm this by hard-coding the
value of out->prefixDatum in my picksplit call to a known value, it shows
up as the address in the memcopy call.

However, as far as I can tell, I'm assigning it correctly: out->prefixDatum
= Int64GetDatum(val);

This is similar to how the other spgist implementations work.
spgkdtreeproc.c does out->prefixDatum = Float8GetDatum(coord);
for example.

I think this is the SP-GiST core failing to handle certain types being
pass-by-value? I'm not totally certain.

As I understand it, the "maybe-pass-by-reference" parameter is a global
flag (USE_FLOAT8_BYVAL), but I'd like to
keep that enabled. What's the proper approach for adding support for this
in the SP-GiST core?

My (somewhat messy) extension module is here
<https://github.com/fake-name/pg-spgist_hamming/tree/master/vptree&gt;, if
it's relevant.

Connor

On Fri, Nov 3, 2017 at 3:12 PM, Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:

Never mind, it turns out the issue boiled down to me declaring the
wrong prefixType in my config function.

TL;DR - PEBKAC

On Sun, Nov 5, 2017 at 1:09 AM, Connor Wolf <connorw@imaginaryindustries.com

Ok, I've managed to get my custom index working.

It's all on github here: https://github.com/fake-name/pg-spgist_hamming, if
anyone else needs a fuzzy-image searching system
that can integrate into postgresql..

It should be a pretty good basis for anyone else to use if they want to
implement a SP-GiST index too.

Thanks!

On Sun, Nov 5, 2017 at 8:10 PM, Connor Wolf <connorw@imaginaryindustries.com

Hi!

On Mon, Nov 13, 2017 at 6:47 AM, Connor Wolf <connorw@imaginaryindustries.
com> wrote:

Ok, I've managed to get my custom index working.

Good!

It's all on github here: https://github.com/fake-name/pg-spgist_hamming, if

anyone else needs a fuzzy-image searching system
that can integrate into postgresql..

It should be a pretty good basis for anyone else to use if they want to
implement a SP-GiST index too.

I took a look at the code, and I feel myself a bit confused :)
It appears that you're indexing int8 values. That seems like unrealistic
short representation for image signature.
Also, name of repository make me think that hamming distance would be used
to compare signatures. But after look at the code, I see that plain
absolute value of difference is used for that purpose.

static double
getDistance(Datum v1, Datum v2)
{
int64_t a1 = DatumGetInt64(v1);
int64_t a2 = DatumGetInt64(v2);
int64_t diff = Abs(a1 - a2);
fprintf_to_ereport("getDistance %ld <-> %ld : %ld", a1, a2, diff);
return diff;
}

For such notion of distance, you don't need a VP-tree or another complex
indexing. B-tree is quite enough in this case. Alternatively, distance
function is not what it meant to be.

It would be useful if you provide complete usage example of this extension:
from image to signature conversion to search queries.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company