Re: "Write amplification" is made worse by "getting tired" while inserting into nbtree secondary indexes (Was: Why B-Tree suffix truncation matters)

On Tue, Jul 17, 2018 at 1:29 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Yeah ... if memory serves, there were specific usage patterns where
> that hack made things way better than they'd been before. (I do not
> recall if the hack itself was mine, but I think I can be blamed for
> the "getting tired" comment ...) I'd suggest git blaming your way
> to the commit that put that in, and then checking the hackers archives
> around that date for more info.

I've done plenty of research into the history of this hack. It was
your work, but it does actually make sense in the context of today's
nbtree code. It is essential with scankey-wise duplicates, since
groveling through hundreds or even thousands of pages full of
duplicates to find free space (and avoid a page split) is going to
have a very serious downside for latency.

Vadim wanted to fix the problem by more or less doing what I propose
[1], though he never got into figuring out how to make that practical
(i.e. how to make it not bloat up internal pages, which must represent
heap TID as just another part of the key space). Having unique keys
isn't just assumed by Lehman & Yao; I think that it's assumed by most
or all real-world B-Tree implementations.

[1] https://www.postgresql.org/message-id/18788.963953289@sss.pgh.pa.us
--
Peter Geoghegan