Do we actually ever want to remove dead tuples from the middle of the chain? If a tuple in the middle of the chain is dead, surely every tuple before it in the chain is dead as well, and we want to remove them as well. I'm thinking, removing tuples from the middle of the chain can be problematic, because we'd need to fiddle with the xmin/xmax of the other tuples to make them match. Or change the tuple-following logic to not do the xmin=xmax check, but it's a nice robustness feature.
I am precisely working on this right now. In the next patch version that I intend to send shortly, I am thinking of removing the dead tuples in the middle of the chain. We don't have agreement on how to deal with the root tuple, but we can safely remove the intermediate dead tuples and vacuum them. Also when all the tuples in the chain are dead because the last tuple is either deleted or COLD updated, the entire chain along with the root tuple and the index entry can be vacuumed.
The operation must be WAL logged and you caught the xmin/xmax problem very rightly. One option is to change the xmax of root tuple to the xmin of the first live/recently-dead tuple, if we remove a set of intermediate dead tuples. This xmin of the first live/recently-dead tuple is also the xmax of the last dead tuple we removed and hence must be older than the oldtestXmin. So assigning that to the root tuple should not break any visibility rules for the root tuple (it would still be dead).
