IN POSTGRESSQL V14, REDUCE INDEX BLOAT

Preamble

PostgreSQL v12 introduced more effective index storage, and v13 further enhanced that by introducing deduplication of index entries. With “bottom-up” index entry deletion in PostgreSQL v14, the number of unnecessary page splits, bloated indexes, and broken indexes that happen when a lot of changes are made will all go down.

Why do we get index bloat?

Every row version (or “tuple”) of the table that is not dead (or invisible to anyone) has an index entry in a B-tree index. When VACUUM removes dead tuples, it also has to delete the corresponding index entries. That leaves blank space on an index page, just like it does with tables. It is possible to reuse this space, but if no new entries are made to the page, it remains empty.

To some extent, this “bloat” is inevitable and normal, but if it becomes excessive, the index will lose effectiveness:

• More pages must be scanned for an index range scan.
• Caching index pages in RAM entails caching the bloat, which is a waste of RAM.
• There may be more levels than necessary in the index if there are fewer index entries per page.

If you repeatedly update the same row, this is especially likely to happen. Until VACUUM can get rid of old tuples, the table and index will have many copies of the same row. This will “divide” the index page in two if it becomes full, which is very annoying. This is a costly operation, and when VACUUM is finished clearing everything out, we are left with two bloated pages rather than just one.

Current features to improve index bloat and performance

HOT tuple

Adding HOT tuples may be the best way PostgreSQL has to prevent the index from being changed too frequently without cause. With this feature, an UPDATE creates tuples that are not referenced from an index but only from the previous version of the table row. This speeds things up and keeps the index from getting too big because there is no need to add any new index entries.

destroying index tuples

An index scan will mark an entry as “killed” if it comes across one that points to a dead tuple in the table. Subsequent index scans will skip such entries even before VACUUM can remove them. PostgreSQL can also get rid of these entries when the index page is full to avoid splitting the page.

How does v14 reduce index bloat even further?

“Bottom-up index tuple deletion” is different from the other methods because it gets rid of index entries that point to dead tuples right before an index page split. This can reduce the number of index entries and avoid the expensive page split, as well as the bloat that will occur later, when VACUUM cleans up.

In a way, this performs part of the work of VACUUM earlier, at a point where it is useful to avoid index bloat.

A test case

To demonstrate the effects of the new feature, I performed a custom pgbench run on PostgreSQL v13 and v14.

The test’s table is shown here:

 CREATE TABLE testtab ( id bigint CONSTRAINT testtab_pkey PRIMARY KEY, unchanged integer, changed integer ); INSERT INTO testtab SELECT i, i, 0 FROM generate_series(1, 10000) AS i; CREATE INDEX testtab_unchanged_idx ON testtab (unchanged); CREATE INDEX testtab_changed_idx ON testtab (changed);

This is the pgbench script called “bench.sql”:

 \set id random_gaussian(1, 10000, 10) UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id; UPDATE testtab SET changed = changed + 1 WHERE id = :id;

Because some (recent?) table rows typically receive more updates than others in real life, I chose a normal distribution. Ten updates are made to the row to increase the likelihood that the affected page will need to be split.

I execute the script as follows 60000 times (10000 iterations by 6 clients):

 pgbench -n -c 6 -f bench.sql -t 10000 test

Comparing the test results

We use the pgstattuple extension to get index statistics with psql:

 SELECT i.indexrelid::regclass FROM pg_index AS index, s.index_size, s.avg_leaf_density AS i CROSS JOIN LATERAL pgstatindex(i.indexrelid) AS s WHERE indrelid = 'testtab'::regclass;

This is what version 13 brings us:

 index │ index_size │ avg_leaf_density ═══════════════════════╪════════════╪══════════════════ testtab_pkey │ 319488 │ 66.6 testtab_unchanged_idx │ 4022272 │ 5.33 testtab_changed_idx │ 4505600 │ 13.57 (3 rows)

As a result, for version 14,

 index │ index_size │ avg_leaf_density ═══════════════════════╪════════════╪══════════════════ testtab_pkey │ 245760 │ 87.91 testtab_unchanged_idx │ 532480 │ 39.23 testtab_changed_idx │ 4038656 │ 14.23 (3 rows)

The most significant improvement is shown in testtab unchanged idx. The index is out of shape in version 13, but just 60% inflated in version 14. (which is not bad for an index). The new feature’s greatest impact is visible in this area. There are no killed index tuples because the UPDATE does not scan that index, but in most circumstances, “bottom-up deletion” may be able to get rid of enough of them to prevent a page split.

Testtab pkey has also shown a substantial improvement. Dead index tuples will be removed because the UPDATE scans that index, and the new feature gets rid of them before dividing the page. Since v13 already does a good job of avoiding index bloat, the difference to v13 is less obvious in this instance.

Because the new functionality only applies when the UPDATE does not change the indexed item, the index testtab changed idx cannot benefit from it. If you’re wondering why the leaf density is so much lower than testtab unchanged idx in version 13, it’s because index de-duplication may activate because the index entry hasn’t been changed.

Will I be able to use this feature after a pg_upgrade?

This will continue to function after a PG upgrade of an index established on PostgreSQL v12 or later since the index’s storage format is unaltered. To take advantage of the new capability, if the index was constructed using an earlier version of PostgreSQL, you must reindex the index. Keep in mind that a PG upgrade does not alter the internal index version; it merely replicates the index files.

Conclusion

B-tree indexes continue to get better with PostgreSQL v14. While this one might not be ground-breaking, it promises to offer many workloads, especially those with lots of updates, a significant improvement.

About Enteros

​​​​Enteros offers a patented database performance management SaaS platform. It proactively identifies root causes of complex business-impacting database scalability and performance issues across a growing number of clouds, RDBMS, NoSQL, and machine learning database platforms.​