Re: Unbounded (Possibly) Database Size Increase - Toasting

Hannu Krosing <hannu(at)tm(dot)ee> writes:
> But does PG not have a new index entry for each _version_ of table row ?

Sure, but the entries do go away during vacuum.

> Or does lack-of-btree-collapse-logic affect only keys where there are
> many _different_ keys and not many repeating keys?

The problem is that once the btree is constructed, the key ranges
assigned to the existing leaf pages can't grow, only shorten due
to page splits. So if you've got, say,

1 2 3 | 4 5 6 | 7 8 9

(schematically suggesting 3 leaf pages with 9 keys) and you delete
keys 1-3 and vacuum, you now have

- - - | 4 5 6 | 7 8 9

Lots of free space in leaf page 1, but that doesn't help you when you
want to insert keys 10, 11, 12. That leaf page can only be used for
keys <= 3, or possibly <= 4, depending on what boundary key is shown
in the next btree level. So if you reinsert rows with the same range
of keys as you had before, no index growth. If the range of keys
moves, new pages will keep getting added on at the right end of the
btree. Old pages at the left end will never go away, even if they
become mostly or entirely empty.

AFAICS we cannot fix this except by reverse-splitting adjacent index
pages when their combined usage falls below some threshold. (The
reverse split would give us one unused page that could be put in a
freelist and then used somewhere else in the index structure.)
In principle VACUUM could do this, but it's ticklish to code, especially
given the desire not to acquire exclusive locks while vacuuming.

regards, tom lane