Thread: Reverse Key Index
Hi, does PostgreSQL support the concept of reverse key indexing as described here? I couldn't find any documentation on this yet. http://www.toadworld.com/platforms/oracle/w/wiki/11075.reverse-key-index-from-the-concept-to-internals.aspx Regards, -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09130 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543
"Sven R. Kunze" <srkunze@tbz-pariv.de> writes: > does PostgreSQL support the concept of reverse key indexing as described > here? I couldn't find any documentation on this yet. > http://www.toadworld.com/platforms/oracle/w/wiki/11075.reverse-key-index-from-the-concept-to-internals.aspx There's nothing built-in for that (and frankly, it doesn't sound useful enough that we'd ever add it). You could get the effect easily enough with an expression index on a byte-reversing function. A related thing that people often do is create an index on a hash function. regards, tom lane
Thanks for the immediate reply. I understand the use case is quite limited. On the other hand, I see potential when it comes to applications which use PostgreSQL. There, programmers would have to change a lot of code to tweak existing (and more importantly working) queries to hash/reverse an id column first. Using ORMs would make this change even more painful and maybe even impossible. When reading https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ carefully, it also seems to work with index scan partially in case of equality comparisons. On 14.02.2015 19:18, Tom Lane wrote: > "Sven R. Kunze" <srkunze@tbz-pariv.de> writes: >> does PostgreSQL support the concept of reverse key indexing as described >> here? I couldn't find any documentation on this yet. >> http://www.toadworld.com/platforms/oracle/w/wiki/11075.reverse-key-index-from-the-concept-to-internals.aspx > There's nothing built-in for that (and frankly, it doesn't sound useful > enough that we'd ever add it). You could get the effect easily enough > with an expression index on a byte-reversing function. A related thing > that people often do is create an index on a hash function. > > regards, tom lane -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09130 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543
On 02/14/2015 10:35 AM, Sven R. Kunze wrote: > Thanks for the immediate reply. > > I understand the use case is quite limited. > > On the other hand, I see potential when it comes to applications which > use PostgreSQL. There, programmers would have to change a lot of code to > tweak existing (and more importantly working) queries to hash/reverse an > id column first. Using ORMs would make this change even more painful and > maybe even impossible. > > When reading > https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ > carefully, it also seems to work with index scan partially in case of > equality comparisons. Seems like a good use for SP-GiST. Go for it! -- Josh Berkus PostgreSQL Experts Inc. http://pgexperts.com
On 25.02.2015 23:31, Josh Berkus wrote: > On 02/14/2015 10:35 AM, Sven R. Kunze wrote: >> Thanks for the immediate reply. >> >> I understand the use case is quite limited. >> >> On the other hand, I see potential when it comes to applications which >> use PostgreSQL. There, programmers would have to change a lot of code to >> tweak existing (and more importantly working) queries to hash/reverse an >> id column first. Using ORMs would make this change even more painful and >> maybe even impossible. >> >> When reading >> https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ >> carefully, it also seems to work with index scan partially in case of >> equality comparisons. > Seems like a good use for SP-GiST. Go for it! > I just thought about btree indexes here mainly because they well-known and well-used in ORM frameworks. Considering the documentation and third-party posts on GiST and btree_gist, at least to me, it seems as if people would not want to use that for integers; which in turn is the main use-case scenario for reverse key indexes. -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09126 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543
Sven R. Kunze schrieb am 26.02.2015 um 12:04: > I just thought about btree indexes here mainly because they well-known and well-used in ORM frameworks. If your ORM framework needs to know about the internals of an index definition or even requires a certain index type, thenyou should ditch that ORM framework. Apart from indexes supporting business constraints (e.g. a unique index) neither the application nor the the ORM frameworkshould care about indexes at all. > does PostgreSQL support the concept of reverse key indexing as described here? The real question is: why do you think you need such an index? Do you have any performance problems with the existing BTree index? If yes, which problem exactly? Thomas
On 26.02.2015 12:45, Thomas Kellerer wrote: > Sven R. Kunze schrieb am 26.02.2015 um 12:04: >> I just thought about btree indexes here mainly because they well-known and well-used in ORM frameworks. > If your ORM framework needs to know about the internals of an index definition or even requires a certain index type, thenyou should ditch that ORM framework. As I said "Considering the documentation and third-party posts on GiST and btree_gist, at least to me, it seems as if people would not want to use that for integers; which in turn is the main use-case scenario for reverse key indexes." > Apart from indexes supporting business constraints (e.g. a unique index) neither the application nor the the ORM frameworkshould care about indexes at all. Well, the world is not perfect: http://www.joelonsoftware.com/articles/LeakyAbstractions.html >> does PostgreSQL support the concept of reverse key indexing as described here? > The real question is: why do you think you need such an index? > Do you have any performance problems with the existing BTree index? If yes, which problem exactly? > This is not the real question. I never said I personally have to solve issue around that. If so, I would have provide more detailed information on the issue. However, I clearly see benefits of Oracle's solution over "You could get the effect easily enough with an expression index on a byte-reversing function. A related thing that people often do is create an index on a hash function." These benefits, I described here: "On the other hand, I see potential when it comes to applications which use PostgreSQL. There, programmers would have to change a lot of code to tweak existing (and more importantly working) queries to hash/reverse an id column first. Using ORMs would make this change even more painful and maybe even impossible." So, this discussion is more about what can PostgreSQL offer in comparison to already existing solutions. I perfectly see Tom's proposal as a as-is solution but it has the drawbacks described above. If you think Reverse Key Indexes have no usage here in PostgreSQL, you should not support convenience features for easily improving performance without breaking the querying API or you won't have any intentions to include such a patch, just let me know and we can close the issue immediately. -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09126 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543
On 02/26/2015 12:31 AM, Josh Berkus wrote: > On 02/14/2015 10:35 AM, Sven R. Kunze wrote: >> Thanks for the immediate reply. >> >> I understand the use case is quite limited. >> >> On the other hand, I see potential when it comes to applications which >> use PostgreSQL. There, programmers would have to change a lot of code to >> tweak existing (and more importantly working) queries to hash/reverse an >> id column first. Using ORMs would make this change even more painful and >> maybe even impossible. >> >> When reading >> https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ >> carefully, it also seems to work with index scan partially in case of >> equality comparisons. > > Seems like a good use for SP-GiST. Go for it! A b-tree opclass that just compares from right-to-left would work just as well, and perform better. - Heikki
Sven R. Kunze schrieb am 26.02.2015 um 13:23: > If you think Reverse Key Indexes have no usage here in PostgreSQL, you should not support convenience features > for easily improving performance without breaking the querying API It's also unclear to me which "performance" you are referring to. Insert performance? Retrieval performance? Concurrency? The use-case for reverse indexes in Oracle is pretty small: it's _only_ about the contention when doing a lot of insertswith increasing numbers (because the different transactions will be blocked when accessing the blocks in question). As Postgres manages inserts differently than Oracle I'm not so sure that this problem exists in Postgres the same way itdoes in Oracle. That's why I asked if you have a _specific_ problem. Richard Footes blog post is mostly about the myth that _if_ you have a reverse index this is only used for equality operations. It does not claim that a reverse index is faster than a regular index _if_ it is used for a range scan. The question is: do you think you need a reverse index because you have a performance problem with when doing many, manyinserts at the same time using "close-by" values into a table that uses a btree index on the column? Or do you think you need a reverse index to improve the performance of a range scan? If that is the then you can easily usa gin/gist index or even a simple btree index using a trigram index to speed up a "LIKE '%abc%'" (something Oracle can'tdo at all) without having to worry about obfuscation layers (aka ORM). Thomas
On 26.02.2015 13:48, Thomas Kellerer wrote: > Sven R. Kunze schrieb am 26.02.2015 um 13:23: >> If you think Reverse Key Indexes have no usage here in PostgreSQL, you should not support convenience features >> for easily improving performance without breaking the querying API Sorry for my bad English: The if-clause ends with "just let me know and we can close the issue immediately." You quoted an or'ed if-part. Point was, if you see no benefits or you have no intention to include it anyway (patch provided or not), we can stop now. I am not married to this features and right now I can live without it. > It's also unclear to me which "performance" you are referring to. > Insert performance? Retrieval performance? Concurrency? > > The use-case for reverse indexes in Oracle is pretty small: it's _only_ about the contention when doing a lot of insertswith increasing numbers (because the different transactions will be blocked when accessing the blocks in question). Exactly. That would include logging databases and big/high-frequency OLTP systems. > As Postgres manages inserts differently than Oracle I'm not so sure that this problem exists in Postgres the same way itdoes in Oracle. Maybe, PostgreSQL internal experts can answer that question thoroughly. > That's why I asked if you have a _specific_ problem. I see. Answering explicitly: no, I don't. > Richard Footes blog post is mostly about the myth that _if_ you have a reverse index this is only used for equality operations. > It does not claim that a reverse index is faster than a regular index _if_ it is used for a range scan. Correct. > The question is: do you think you need a reverse index because you have a performance problem with when doing many, manyinserts at the same time using "close-by" values into a table that uses a btree index on the column? I presume that Oracle would not invest resources in implementing features which would have no benefits for their customers. Thus, the research on this topic should already been done for us. That given, if we can answer your question 'whether PostgreSQL handles it differently from Oracle so that the contention issue cannot arise' can be answered with a no, I tend to say: yes. > Or do you think you need a reverse index to improve the performance of a range scan? If that is the then you can easilyus a gin/gist index or even a simple btree index using a trigram index to speed up a "LIKE '%abc%'" (something Oraclecan't do at all) without having to worry about obfuscation layers (aka ORM). From what I gather, reverse key indexes are not about improving range scans but about improving insertion speed due to diversification of insertion location. I actually used Richard Foote's posts only to get a proper understanding of reverse key indexes and what can and cannot be done with them and where their issues are: https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ https://richardfoote.wordpress.com/2008/01/16/introduction-to-reverse-key-indexes-part-ii-another-myth-bites-the-dust/ https://richardfoote.wordpress.com/2008/01/18/introduction-to-reverse-key-indexes-part-iii-a-space-oddity/ https://richardfoote.wordpress.com/2008/01/21/introduction-to-reverse-key-indexes-part-iv-cluster-one/ -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09126 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543
On 26.02.2015 13:37, Heikki Linnakangas wrote: > On 02/26/2015 12:31 AM, Josh Berkus wrote: >> On 02/14/2015 10:35 AM, Sven R. Kunze wrote: >>> Thanks for the immediate reply. >>> >>> I understand the use case is quite limited. >>> >>> On the other hand, I see potential when it comes to applications which >>> use PostgreSQL. There, programmers would have to change a lot of >>> code to >>> tweak existing (and more importantly working) queries to >>> hash/reverse an >>> id column first. Using ORMs would make this change even more painful >>> and >>> maybe even impossible. >>> >>> When reading >>> https://richardfoote.wordpress.com/2008/01/14/introduction-to-reverse-key-indexes-part-i/ >>> >>> carefully, it also seems to work with index scan partially in case of >>> equality comparisons. >> >> Seems like a good use for SP-GiST. Go for it! > > A b-tree opclass that just compares from right-to-left would work just > as well, and perform better. > > - Heikki > Thanks for the hint. That also sounds easy to implement. Regards, -- Sven R. Kunze TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09126 Chemnitz Tel: +49 (0)371 33714721, Fax: +49 (0)371 5347920 e-mail: srkunze@tbz-pariv.de web: www.tbz-pariv.de Geschäftsführer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543