6 ms·

PostgreSQL B-Tree index deduplication

186 points by petergeoghegan 6y ago

andy_ppp 6y ago
Cool, I’d love to know how this affects query performance, rather than just index size?
- Skinney 6y ago
  Roughly speaking: smaller index size = greater performance. The index also has to be read from disk (if not already in memory), which is faster the smaller it is. But also, once in memory, smaller size makes key-lookups or traversals faster. How much faster? It really depends on your index.
  - petergeoghegan 6y ago
    B-Tree deduplication can also help to control duplicate index tuples caused by MVCC "version churn" -- including in unique indexes. See the paragraph that begins with "B-Tree indexes are not directly aware that under MVCC..." here: https://www.postgresql.org/docs/devel/btree-implementation.html#BTREE-DEDUPLICATION https://www.postgresql.org/docs/devel/btree-implementation.h...
- mjevans 6y ago
  If it helps either make tables small enough for RAM, or what used to be RAM small enough for cache, then it could help a LOT.
- petergeoghegan 6y ago
  It's hard to give a simple answer, but it's certainly possible for it to help performance significantly. Both for queries, and garbage collection by VACUUM. It's especially helpful with writes + low cardinality indexes.
- redis_mlc 6y ago
  Postgres has a write amplification problem - when you update or insert a row, it has to check all the indexes to see what was touched (unlike MySQL.) Uber made this famous in a blog post where they migrated off postgres because of it. So with Postgres I try to keep the number of indexes per table down to around 5, but with MySQL InnoDB, 20 indexes is not a problem for many use cases. The other little-known Postgres problem is that by default, installing it sets up replication that writes a local file in a busy manner. This can cause problems with fsck or on low-end SSD/flash storage resulting in corruption that causes postgres restarts to fail hard, so disable that.
  - andy_ppp 6y ago
    I’m interested to find out why the community feel this answer is incorrect. I don’t know enough about database internals to know! Would be good if someone could help me to become more informed about this. I can’t personally see a way that indexes wouldn’t be touched when inserts happen in MySQL but who knows?
    - jchb 6y ago
      Previously on HN: Why Uber Engineering Switched from Postgres to MySQL (2016): https://news.ycombinator.com/item?id=17280239 https://news.ycombinator.com/item?id=17280239 A PostgreSQL response to Uber [pdf]: https://news.ycombinator.com/item?id=14222721 https://news.ycombinator.com/item?id=14222721 One important point is that Uber wrote this running on Postgres 9.2. The latest Postgres release is now 12.4
      - andy_ppp 6y ago
        Thanks, I just always trust Postgres more from my experiences. Reading some of the above I’m fairly unconvinced by Uber’s reasoning...
        pgaddict 6y ago
        I'd say some of the limitations hit by Uber were real, and were a bit of a PITA even before that. Some were improved significantly since then, others still need to be considered when designing application accessing PostgreSQL. I'd say it was a nice example what happens when you design application based on how you imagine an ideal database would work, not realizing that there's a lot of complexity and limitations. And then when you eventually have to face reality you blame the database for having to do trade-offs and refuse to mitigate the trouble by changing the application.
- dspillett 6y ago
  Like SQL Server's row-level and page-level compression, you get more rows per page, so need to read less pages to process the query. From cold this means less disk or network IO loading the pages from storage into RAM, and it means you can fit more into RAM (and potentially CPU cache when spinning over small enough chunks of data) so you can do the same with less RAM or reduce IO so be faster with the same RAM allocation (as pages will not need to be evicted as often to make room for others). The trade-off is a bit of CPU time, every time the page is referenced. Not just when it is updated or read from storage, but potentially every time it is accessed, even just reading, as the pages held in RAM are in the same format as on disk so the decompression needs to happen on read also (unless postgres keeps a cache of pre-decompressed pages to help with this but my gut suggests that would not be worth the complication - where it would help significantly you would just not use this technique anyway). In a great many scenarios, I would say most, this trade-off is worth it because of the relative cost of IO and CPU time needed to save some of it. It might be significantly detrimental to performance in situations where enough of your data fits into RAM anyway and you are performing CPU-heavy analysis upon it. Side benefits include reducing the size of your backups and reducing the time needed to take them, so there are other potential infrastructure and administration savings to be had too.
  - petergeoghegan 6y ago
    There is no overhead for reads, since deduplication doesn't compress the data as such. Rather, deduplication creates a representation that removes duplicates but is otherwise identical to the existing representation.
yxhuvud 6y ago
This is an great change, but I wonder, will it apply retroactively to indices from old databases or will the indices have to be rebuilt? Like, I understand that just upgrading the version won't reduce the sizes, but will reading and writing to the indices gradually reduce the size?
- petergeoghegan 6y ago
  You will need to REINDEX after upgrading using pg_upgrade. Otherwise deduplication won't be applied in the old indexes at all. These days it's possible to use the CONCURRENTLY option with REINDEX, which is much less disruptive.
- CodeWriter23 6y ago
  In the second paragraph, the author links a couple of other articles that drill down some more. I almost missed those myself.
rossmohax 6y ago
With deduplicatio enabled, how does it differ from GIN index now?
- pgaddict 6y ago
  Interesting question. Considering how different the gid and btree indexes are, I'd say it's very different. GIN essentially builds a posting list for each value in the column, and compresses that (which might be seen as a kind of a bitmap index). OTOH btree deduplication simply compares index keys that end up on the same leaf page. So there's on "global" index compression, it's much more localized. But I suppose Peter and Anastasia have more thoughts on this ...
- avremel 6y ago
  > The big difference is that duplicate index entries can still occur in B-tree indexes. GIN indexes have to integrate new entries into the posting list every time, which makes data modifications less efficient (this is mitigated by the pending list). In contrast, PostgreSQL deduplicates B-tree entries only when it would otherwise have to split the index page. So it has to do the extra work only occasionally, and only when it would have to do extra work anyway. This extra work is balanced by the reduced need for page splits and the resulting smaller index size. https://www.cybertec-postgresql.com/en/b-tree-index-deduplication/ https://www.cybertec-postgresql.com/en/b-tree-index-deduplic...
- petergeoghegan 6y ago
  GIN is optimized for things like full text search and jsonb indexing. GIN's internal B-Tree/entry tree consists of datums that are decomposed from the data type you're actually indexing rather than the data type itself (e.g. when indexing a column that's an array of ints, the entry tree is actually plain integers). You can now use B-Tree to get something that's roughly comparable to GIN + contrib/btree_gin, though only when indexing a single column -- multi-column indexing in GIN stores each datum from the same row in totally different parts of the tree. This is totally different from B-Tree, which stores all columns that are indexed for the same row together. B-Tree deduplication is only capable of making the index about 3x smaller (though larger reductions are possible when indexing large ), whereas GIN can sometimes manage about 10x because it also compresses TID lists. This on-disk size difference is only apparent when there are a huge number of duplicates. GIN now has a higher on-disk overhead when there are only 3 or 4 duplicates per item. In summary, B-Tree is a performance all-rounder that has good, consistent read and write performance. GIN is more optimized for writes, and for specialized applications like FTS.

Cool, I’d love to know how this affects query performance, rather than just index size?

Skinney 6y ago
Roughly speaking: smaller index size = greater performance. The index also has to be read from disk (if not already in memory), which is faster the smaller it is. But also, once in memory, smaller size makes key-lookups or traversals faster. How much faster? It really depends on your index.
- petergeoghegan 6y ago
  B-Tree deduplication can also help to control duplicate index tuples caused by MVCC "version churn" -- including in unique indexes. See the paragraph that begins with "B-Tree indexes are not directly aware that under MVCC..." here: https://www.postgresql.org/docs/devel/btree-implementation.html#BTREE-DEDUPLICATION https://www.postgresql.org/docs/devel/btree-implementation.h...
mjevans 6y ago
If it helps either make tables small enough for RAM, or what used to be RAM small enough for cache, then it could help a LOT.
petergeoghegan 6y ago
It's hard to give a simple answer, but it's certainly possible for it to help performance significantly. Both for queries, and garbage collection by VACUUM. It's especially helpful with writes + low cardinality indexes.
redis_mlc 6y ago
Postgres has a write amplification problem - when you update or insert a row, it has to check all the indexes to see what was touched (unlike MySQL.) Uber made this famous in a blog post where they migrated off postgres because of it. So with Postgres I try to keep the number of indexes per table down to around 5, but with MySQL InnoDB, 20 indexes is not a problem for many use cases. The other little-known Postgres problem is that by default, installing it sets up replication that writes a local file in a busy manner. This can cause problems with fsck or on low-end SSD/flash storage resulting in corruption that causes postgres restarts to fail hard, so disable that.
- andy_ppp 6y ago
  I’m interested to find out why the community feel this answer is incorrect. I don’t know enough about database internals to know! Would be good if someone could help me to become more informed about this. I can’t personally see a way that indexes wouldn’t be touched when inserts happen in MySQL but who knows?
  - jchb 6y ago
    Previously on HN: Why Uber Engineering Switched from Postgres to MySQL (2016): https://news.ycombinator.com/item?id=17280239 https://news.ycombinator.com/item?id=17280239 A PostgreSQL response to Uber [pdf]: https://news.ycombinator.com/item?id=14222721 https://news.ycombinator.com/item?id=14222721 One important point is that Uber wrote this running on Postgres 9.2. The latest Postgres release is now 12.4
    - andy_ppp 6y ago
      Thanks, I just always trust Postgres more from my experiences. Reading some of the above I’m fairly unconvinced by Uber’s reasoning...
      - pgaddict 6y ago
        I'd say some of the limitations hit by Uber were real, and were a bit of a PITA even before that. Some were improved significantly since then, others still need to be considered when designing application accessing PostgreSQL. I'd say it was a nice example what happens when you design application based on how you imagine an ideal database would work, not realizing that there's a lot of complexity and limitations. And then when you eventually have to face reality you blame the database for having to do trade-offs and refuse to mitigate the trouble by changing the application.
dspillett 6y ago
Like SQL Server's row-level and page-level compression, you get more rows per page, so need to read less pages to process the query. From cold this means less disk or network IO loading the pages from storage into RAM, and it means you can fit more into RAM (and potentially CPU cache when spinning over small enough chunks of data) so you can do the same with less RAM or reduce IO so be faster with the same RAM allocation (as pages will not need to be evicted as often to make room for others). The trade-off is a bit of CPU time, every time the page is referenced. Not just when it is updated or read from storage, but potentially every time it is accessed, even just reading, as the pages held in RAM are in the same format as on disk so the decompression needs to happen on read also (unless postgres keeps a cache of pre-decompressed pages to help with this but my gut suggests that would not be worth the complication - where it would help significantly you would just not use this technique anyway). In a great many scenarios, I would say most, this trade-off is worth it because of the relative cost of IO and CPU time needed to save some of it. It might be significantly detrimental to performance in situations where enough of your data fits into RAM anyway and you are performing CPU-heavy analysis upon it. Side benefits include reducing the size of your backups and reducing the time needed to take them, so there are other potential infrastructure and administration savings to be had too.
- petergeoghegan 6y ago
  There is no overhead for reads, since deduplication doesn't compress the data as such. Rather, deduplication creates a representation that removes duplicates but is otherwise identical to the existing representation.

This is an great change, but I wonder, will it apply retroactively to indices from old databases or will the indices have to be rebuilt? Like, I understand that just upgrading the version won't reduce the sizes, but will reading and writing to the indices gradually reduce the size?

petergeoghegan 6y ago
You will need to REINDEX after upgrading using pg_upgrade. Otherwise deduplication won't be applied in the old indexes at all. These days it's possible to use the CONCURRENTLY option with REINDEX, which is much less disruptive.
CodeWriter23 6y ago
In the second paragraph, the author links a couple of other articles that drill down some more. I almost missed those myself.

rossmohax 6y ago

With deduplicatio enabled, how does it differ from GIN index now?

pgaddict 6y ago
Interesting question. Considering how different the gid and btree indexes are, I'd say it's very different. GIN essentially builds a posting list for each value in the column, and compresses that (which might be seen as a kind of a bitmap index). OTOH btree deduplication simply compares index keys that end up on the same leaf page. So there's on "global" index compression, it's much more localized. But I suppose Peter and Anastasia have more thoughts on this ...
avremel 6y ago
> The big difference is that duplicate index entries can still occur in B-tree indexes. GIN indexes have to integrate new entries into the posting list every time, which makes data modifications less efficient (this is mitigated by the pending list). In contrast, PostgreSQL deduplicates B-tree entries only when it would otherwise have to split the index page. So it has to do the extra work only occasionally, and only when it would have to do extra work anyway. This extra work is balanced by the reduced need for page splits and the resulting smaller index size. https://www.cybertec-postgresql.com/en/b-tree-index-deduplication/ https://www.cybertec-postgresql.com/en/b-tree-index-deduplic...
petergeoghegan 6y ago
GIN is optimized for things like full text search and jsonb indexing. GIN's internal B-Tree/entry tree consists of datums that are decomposed from the data type you're actually indexing rather than the data type itself (e.g. when indexing a column that's an array of ints, the entry tree is actually plain integers). You can now use B-Tree to get something that's roughly comparable to GIN + contrib/btree_gin, though only when indexing a single column -- multi-column indexing in GIN stores each datum from the same row in totally different parts of the tree. This is totally different from B-Tree, which stores all columns that are indexed for the same row together. B-Tree deduplication is only capable of making the index about 3x smaller (though larger reductions are possible when indexing large ), whereas GIN can sometimes manage about 10x because it also compresses TID lists. This on-disk size difference is only apparent when there are a huge number of duplicates. GIN now has a higher on-disk overhead when there are only 3 or 4 duplicates per item. In summary, B-Tree is a performance all-rounder that has good, consistent read and write performance. GIN is more optimized for writes, and for specialized applications like FTS.