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

[Alexander Korotkov]

Hi!

On Mon, Nov 13, 2017 at 6:47 AM, Connor Wolf  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

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

[Connor Wolf]

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  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  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/me
>> mcpy-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/me
>> mcpy-sse2-unaligned.S:159
>> #1  0x004ecd66 in memcpy (__len=16, __src=,
>> __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  0x004ee06b in spgFormInnerTuple (state=state@entry
>> =0x7fff327325e0, hasPrefix=, prefix=18445692987396472528,
>> nNodes=8,
>> nodes=nodes@entry=0x13bd340) at spgutils.c:741
>> #4  0x004f508b 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  0x004f6976 in spgdoinsert (index=index@entry=0x7f2cf9de7f98,
>> state=state@entry=0x7fff327325e0, heapPtr=heapPtr@entry=0x12e672c,
>> datum=12598555199787281,
>> isnull=0 '\000') at spgdoinsert.c:2053
>> #6  0x004ee5cc 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  0x00534e8d 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 ,
>> callback_state=0x7fff327325e0) at index.c:2609
>> #8  0x00534f52 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 ,
>> callback_state=callback_state@entry=0x7fff327325e0) at index.c:2182
>> #9  0x004eeb74 in spgbuild (heap=0x7f2cf9ddc6c8,
>> index=0x7f2cf9de7f98, indexInfo=0x1390ad8) at spginsert.c:140
>> #10 0x00535e55 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 0x00536ee8 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@en
>> try=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 0x005d8fe6 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 0x00782057 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 );", 

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

[Connor Wolf]

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  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  0x004ecd66 in memcpy (__len=16, __src=,
> __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  0x004ee06b in spgFormInnerTuple (state=state@entry=0x7fff327325e0,
> hasPrefix=, prefix=18445692987396472528, nNodes=8,
> nodes=nodes@entry=0x13bd340) at spgutils.c:741
> #4  0x004f508b 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  0x004f6976 in spgdoinsert (index=index@entry=0x7f2cf9de7f98,
> state=state@entry=0x7fff327325e0, heapPtr=heapPtr@entry=0x12e672c,
> datum=12598555199787281,
> isnull=0 '\000') at spgdoinsert.c:2053
> #6  0x004ee5cc 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  0x00534e8d 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 ,
> callback_state=0x7fff327325e0) at index.c:2609
> #8  0x00534f52 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 ,
> callback_state=callback_state@entry=0x7fff327325e0) at index.c:2182
> #9  0x004eeb74 in spgbuild (heap=0x7f2cf9ddc6c8,
> index=0x7f2cf9de7f98, indexInfo=0x1390ad8) at spginsert.c:140
> #10 0x00535e55 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 0x00536ee8 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 0x005d8fe6 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 0x00782057 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 0x007815ef 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 0x007816a7 in 

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

[Connor Wolf]

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  0x004ecd66 in memcpy (__len=16, __src=,
__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  0x004ee06b in spgFormInnerTuple (state=state@entry=0x7fff327325e0,
hasPrefix=, prefix=18445692987396472528, nNodes=8,
nodes=nodes@entry=0x13bd340) at spgutils.c:741
#4  0x004f508b 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  0x004f6976 in spgdoinsert (index=index@entry=0x7f2cf9de7f98,
state=state@entry=0x7fff327325e0, heapPtr=heapPtr@entry=0x12e672c,
datum=12598555199787281,
isnull=0 '\000') at spgdoinsert.c:2053
#6  0x004ee5cc 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  0x00534e8d 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 ,
callback_state=0x7fff327325e0) at index.c:2609
#8  0x00534f52 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 ,
callback_state=callback_state@entry=0x7fff327325e0) at index.c:2182
#9  0x004eeb74 in spgbuild (heap=0x7f2cf9ddc6c8,
index=0x7f2cf9de7f98, indexInfo=0x1390ad8) at spginsert.c:140
#10 0x00535e55 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 0x00536ee8 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 0x005d8fe6 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 0x00782057 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 0x007815ef 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 0x007816a7 in ProcessUtility (pstmt=pstmt@entry=0x12db108,
queryString=, context=context@entry=PROCESS_UTILITY_TOPLEVEL,
params=, queryEnv=,
dest=dest@entry=0x12db200,
completionTag=0x7fff32732ed0 "") at utility.c:357
#16 0x0077de2e in PortalRunUtility (portal=portal@entry=0x1391a80,
pstmt=pstmt@entry=0x12db108, isTopLevel=isTopLevel@entry=1 '\001',
setHoldSnapshot=setHoldSnapshot@entry=0 '\000', 

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

[Alexander Korotkov]

On Fri, Nov 3, 2017 at 12:37 PM, Connor Wolf <
conn...@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

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

[Connor Wolf]

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

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

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

[Robert Haas]

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

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

[Connor Wolf]

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 <
conn...@imaginaryindustries.com> wrote:

> 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.korot...@postgrespro.ru> wrote:
>
>> Hi!
>>
>> On Sun, Oct 29, 2017 at 12:07 PM, Connor Wolf <
>> w...@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,

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

[Connor Wolf]

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.korot...@postgrespro.ru> wrote:

> Hi!
>
> On Sun, Oct 29, 2017 at 12:07 PM, Connor Wolf <
> w...@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 

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

[Tom Lane]

Alexander Korotkov  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

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

[Alexander Korotkov]

On Mon, Oct 30, 2017 at 2:07 PM, Oleg Bartunov  wrote:

> On Mon, Oct 30, 2017 at 12:05 PM, Oleg Bartunov 
> wrote:
> > On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
> >  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

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

[Alexander Korotkov]

Hi!

On Sun, Oct 29, 2017 at 12:07 PM, Connor Wolf 
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


vptree.tar.gz
Description: GNU Zip compressed data

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

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

[Oleg Bartunov]

On Mon, Oct 30, 2017 at 12:05 PM, Oleg Bartunov  wrote:
> On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
>  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

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

[Oleg Bartunov]

On Sun, Oct 29, 2017 at 10:07 AM, Connor Wolf
 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