Thread: [HACKERS] Index only scan for cube and seg
Hi hackers! Here are patches enabling Index Only Scan for cube and seg extensions. These patches follow this discussion [0]. For cube there is new default opclass. We cannot drop old opclass, because it could TOAST come cube values in rare occasions.Index Only Scan is enabled only for newly created indexes. Btw I can add fetch to old opclass so that IOS wouldbe enabled. For seg compress and decompress functions are dropped from opclass and extension. Index Only Scan is enabled. There are two more functions which can be deleted ghstore_decompress g_intbig_decompress But it will not lead to any feasible consequences. [0] https://www.postgresql.org/message-id/flat/CAJEAwVELVx9gYscpE%3DBe6iJxvdW5unZ_LkcAaVNSeOwvdwtD%3DA%40mail.gmail.com#CAJEAwVELVx9gYscpE=Be6iJxvdW5unZ_LkcAaVNSeOwvdwtD=A@mail.gmail.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
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:
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?
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.
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.
The Russian Postgres Company
Attachment
On Mon, Oct 30, 2017 at 2:07 PM, Oleg Bartunov <obartunov@gmail.com> wrote:
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 :)
or even simple, there is contrib/bloom access method, which illustratesOn 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.
developing access method as an extension.
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, 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.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.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
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:
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!ConnorOn 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.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.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 -- 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 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 isCREATE 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.
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
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 isCREATE 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:228It'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 16The first item in my input data file is zero, and if I change it to 1:NOTICE: Memcopying from 0000000000000001 to 0000000001b45938 with len 16So 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 thevalue 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 tokeep 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.ConnorOn 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 isCREATE 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 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> wrote:
Never mind, it turns out the issue boiled down to me declaring the wrong prefixType in my config function.TL;DR - PEBKACOn 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=184456929873 96472528) 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=0x7fff327325 e0, current=current@entry=0x7fff32 732020, parent=parent@entry=0x7fff32732040, newLeafTuple=newLeafTuple@entr y=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=0x7fff327325 e0, heapPtr=heapPtr@entry=0x12e672 c, datum=12598555199787281, isnull=0 '\000') at spgdoinsert.c:2053#6 0x00000000004ee5cc in spgistBuildCallback (index=index@entry=0x7f2cf9de7f98, htup=htup@entry=0x12e6728, values=values@entry=0x7fff3273 21e0, isnull=isnull@entry=0x7fff32732530 "", tupleIsAlive=tupleIsAlive@entr y=1 '\001', state=state@entry=0x7fff327325 e0) at spginsert.c:56 #7 0x0000000000534e8d in IndexBuildHeapRangeScan (heapRelation=heapRelation@entry=0x7f2cf9ddc6c8, indexRelation=indexRelation@en try=0x7f2cf9de7f98, indexInfo=indexInfo@entry=0x1390ad8, allow_sync=allow_sync@entry=1 '\001', anyvisible=anyvisible@entry=0 '\000', start_blockno=start_blockno@en try=0, numblocks=4294967295, callback=0x4ee573 <spgistBuildCallback>, callback_state=0x7fff327325e0) at index.c:2609#8 0x0000000000534f52 in IndexBuildHeapScan (heapRelation=heapRelation@entry=0x7f2cf9ddc6c8, indexRelation=indexRelation@en try=0x7f2cf9de7f98, indexInfo=indexInfo@entry=0x1390ad8, allow_sync=allow_sync@entry=1 '\001', callback=callback@entry=0x4ee5 73 <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@en try=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=indexRelatio nName@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 0x00000000005d8fe6 in DefineIndex (relationId=relationId@entry=16413, stmt=stmt@entry=0x12dd568, indexRelationId=indexRelationI d@entry=0, is_alter_table=is_alter_table@entry=0 '\000', check_rights=check_rights@entr y=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@en try=0x7fff32732ed0 "") at pquery.c:1178 #17 0x000000000077e98e in PortalRunMulti (portal=portal@entry=0x1391a80, isTopLevel=isTopLevel@entry=1 '\001', setHoldSnapshot=setHoldSnapsho t@entry=0 '\000', dest=dest@entry=0x12db200, altdest=altdest@entry=0x12db200, completionTag=completionTag@en try=0x7fff32732ed0 "") at pquery.c:1324 #18 0x000000000077f782 in PortalRun (portal=portal@entry=0x1391a80, count=count@entry=922337203685 4775807, 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:228It'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 16The first item in my input data file is zero, and if I change it to 1:NOTICE: Memcopying from 0000000000000001 to 0000000001b45938 with len 16So 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 thevalue 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 tokeep 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.ConnorOn 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 isCREATE 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
Hi!
On Mon, Nov 13, 2017 at 6:47 AM, Connor Wolf <connorw@imaginaryindustries.
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.
The Russian Postgres Company
Alexander Korotkov
Postgres Professional: http://www.
The Russian Postgres Company
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:
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 doublegetDistance(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;
}
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...".
Connor
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: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 doublegetDistance(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_tf_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;}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.
The Russian Postgres Company
I initially assumed that as well, but I found some somewhat confusing documentation about implementing this as a plain GiST tree. Mostly, the BK-Tree is a inherently unbalanced tree, and some of the documentation for plain GiST indexes claims that GiST indexes can only be created on balanced tree structures.
> GiST stands for Generalized Search Tree. It is a balanced, tree-structured access method,
Sidenote: What is a "signature tree?"
I also had a fair bit of trouble getting going due to the strange terminology. The use of "consistent" for "matches condition" is particularly odd. I'm not sure if this is a translation oddment, but it makes following things a lot more confusing. I suspect this is set match bleeding into the implementation, but I don't see any reason the "consistent" functions couldn't be simply named "matches_query_conditions", with the benefit of no longer requiring familiarity with mathematics terminology to easily understand how things are supposed to work.
Additionally, I don't see how to map some of the calls to a BK-tree. In particular, there's no way to implement the GiST "union" call in the context of a b-tree, since a single tree node can only represent a single value.
Also, the lack of decent examples for the GiST index is challenging. Really, it'd be really helpful if there was a e a GiST and SP-GiST index example that only operates on one simple, one-dimensional datatype. I'm not sure about other people, but I basically always find it much more effective to start with a working project, and modify it rather then try to start something from scratch.
As it is, there is no example that is a good starting basis for a custom GiST index, and there was no example that was a good starting basis for a SP-GiST index. This is particularly true for people (like me) who haven't worked with postgresql's source or extensions at all before this.
I actually spent some time trying to simplify the GiST b-tree example to the point where it was possible to follow it, but all the complexity introduced by the fact that the b-tree example works for basically every data type (and the dynamic dispatch that entails) makes it very hard to follow for someone new to the codebase.
I'd still like to look at converting to a pure GiST based index, but the first step of that will probably be implementing a very basic, boring 2-ary B-tree index across a integral data-type. That way, I can separate implementation issues with logic issues.
Connor
On Tue, Nov 14, 2017 at 1:53 AM, Alexander Korotkov <a.korotkov@postgrespro.ru> wrote:
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: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.p y#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 doublegetDistance(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/v ptree 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/b ktree is the actual BK-tree index, and it does indeed use hamming distance for the search metric: static int64_tf_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;}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/IntraArchiveDeduplicat or, 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.The Russian Postgres Company
Andrey Borodin <x4mmm@yandex-team.ru> writes:
>> 29 окт. 2017 г., в 2:24, Alexander Korotkov <a.korotkov@postgrespro.ru> написал(а):
>> 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.
I've pushed this with a few adjustments:
* I wasn't satisfied with the amount of schema-qualification in the
pg_depend update queries. I thought they could do with comments
explaining what they were doing and why, as well.
* I didn't have much confidence in the new cube test case producing
a consistent row order across all platforms, so I added an ORDER BY.
I made some other cosmetic adjustments to the tests too.
* In both modules, you'd forgotten to update the alternative
expected-files.
regards, tom lane