Обсуждение: [HACKERS] Index only scan for cube and seg

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 

--
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, 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:

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 

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

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

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, if it's relevant.

Connor

On Fri, Nov 3, 2017 at 3:12 PM, Alexander Korotkov <a.korotkov@postgrespro.ru> 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

 

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> wrote:

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, if it's relevant.

Connor

On Fri, Nov 3, 2017 at 3:12 PM, Alexander Korotkov <a.korotkov@postgrespro.ru> 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

 

On Tue, Nov 14, 2017 at 6:08 AM, Connor Wolf <connorw@imaginaryindustries.com> wrote:

On Mon, Nov 13, 2017 at 2:09 AM, Alexander Korotkov <a.korotkov@postgrespro.ru> wrote:

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.

It is a int8, and nope, it's a surprisingly robust and functional signature. There's a document describing the hashing mechanism here:

http://www.hackerfactor.com/blog/?/archives/432-Looks-Like-It.html

Functionally, the procedure is relatively simple:

• Convert to greyscale
• Resize to intermediate resolution (32x32 is common)
• Perform DCT on 32x32 image.
• Crop 32x32 image to 8x8 by throwing away the high-frequency components
• Threshold the 8x8 image by it's average
• Serialize the 64 binary values into a int8

In my case, the actual implementation is here: https://github.com/fake-name/IntraArchiveDeduplicator/blob/master/scanner/hashFile.py#L95-L102

 

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.

You're looking in the wrong place. 

https://github.com/fake-name/pg-spgist_hamming/tree/master/vptree is the code you sent me, with some simplification to make it only work on single integers. Basically,

before I started on my own stuff, I wanted to make sure I could at least implement a functional index using a much more basic structure.

https://github.com/fake-name/pg-spgist_hamming/tree/master/bktree is the actual BK-tree index, and it does indeed use hamming distance for the search metric:

static int64_t

f_hamming(int64_t a_int, int64_t b_int)

{

/*

Compute number of bits that are not common between `a` and `b`.

return value is a plain integer

*/

uint64_t x = (a_int ^ b_int);

uint64_t ret = __builtin_popcountll (x);

return ret;

}

(see https://github.com/fake-name/pg-spgist_hamming/blob/master/bktree/bktree.c#L38-L58).

 

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

Actual usage is done with this project: https://github.com/fake-name/IntraArchiveDeduplicator, which

also has the older in-memory BK tree I've implemented, and it's actually used here. 

I also have unit tests that sit on top of this here (see all the files that are named "Test_db_BKTree...".

OK.  That explains the things, thank you.

For such kind of index, it's probably not even necessary to use SP-GiST.  GiST signature tree could work in this case as well (it would be probably even better).

It would be nice if you write about it some blog post to planet PostgreSQL.

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

The Russian Postgres Company