> Some heuristics and limits on amount of work done to detect duplicate index > entries will help too.
I think I prefer a more thorough approach.
Increment/decrement may get very complicated with custom opclasses, for instance. A column-change bitmap won't know how to handle funcional indexes, etc.
What I intend to try, is modify btree to allow efficient search of a key-ctid pair, by adding the ctid to the sort order.
Yes, that's a good medium term plan. And this is kind of independent from the core idea. So I'll go ahead and write a patch that implements the core idea and some basic optimizations. We can then try different approaches such as tracking changed columns, tracking increment/decrement and teaching btree to skip duplicate (key, CTID) entries.