"Triggered data change violation", once again

I have been looking at the way that deferred triggers slow down when the
same row is updated multiple times within a transaction. The problem
appears to be entirely due to calling deferredTriggerGetPreviousEvent()
to find the trigger list entry for the previous update of the row: we
do a linear search, so the behavior is roughly O(N^2) when there are N
updated rows.

The only reason we do this is to enforce the "triggered data change
violation" restriction of the spec. However, I think we've
misinterpreted the spec. The code prevents an RI referenced value from
being changed more than once in a transaction, but what the spec
actually says is thou shalt not change it more than once per
*statement*. We have discussed this several times in the past and
I think people have agreed that the current behavior is wrong,
but nothing's been done about it.

I think all we need to do to implement things correctly is to consider a
previous event only if both xmin and cmin of the old tuple match the
current xact & command IDs, rather than considering it on the basis of
xmin alone.

Aside from being correct, this will make a significant difference in
performance. If we were doing it per spec then
deferredTriggerGetPreviousEvent would never be called in typical
operations, and so its speed wouldn't be an issue. Moreover, if we do
it per spec then completed trigger event records could be removed from
the trigger list at end of statement, rather than keeping them till end
of transaction, which'd save memory space.

Comments?

regards, tom lane