second concurrent update takes forever

Hi folks,

I don't need this list very often because postgresql works like a charm! But
today we encountered a rather complicated puzzle for us. We really need your
help!

we are using postgresql 8.4 on a debian lenny with latest security patches
applied.

We are running a rather complicated Update statement from time to time which
is only triggered by administrators. The statement updates about 50.000 rows.
It takes usually about 10-30 seconds to execute and that's fine for us.

This time two administrator did run this update at approximately  the same
time, so the second update started before the first finished.

The first update took about 30 seconds which is quite long but not a problem
for us. the second update was useless, because everything was already updated.
Anyway, the second statement took 5 hours!

We were able to reproduce this scenario very easily. We had a local database,
switched off auto-vacuum daemon and had no other concurrent tasks.

We just ran the statement and while it was running we started the very same
statement in a different database session. the first statement finished in 3
seconds, the second statement never returned (we canceled it after an hour or
so).

so we read the documentation about transaction isolation
http://www.postgresql.org/docs/current/static/transaction-iso.html
we are in read committed isolation.

It says about UPDATE statements "The search condition of the command (the
WHERE clause) is re-evaluated to see if the updated version of the row still
matches the search condition."

the update statement has an additional from clause, I show you slightly
simplified version of it (to make it more readable)

UPDATE
   queue
SET
   queue_status =
      CASE WHEN status = 0 OR status = 2
      THEN status + 1
      ELSE status
      END,
   queue_index =
      CASE WHEN status = 0 OR status = 2
      THEN updates.index
      ELSE
        CASE WHEN queue.index >  updates.index
        THEN updates.index
        ELSE queue.index
        END
      END
FROM
(
   SELECT
      matchday.group_id AS group_id,
      min (matchday.index) AS index
   FROM event NATURAL LEFT JOIN matchday
   WHERE event.event_id IN ( 3033445 )
   GROUP BY matchday.group_id
) AS updates
WHERE
   queue.group_id = updates.group_id
;

so the essence is: the statement has a rather long executing sub-select
statement which takes about a 800ms. I "suspect" postgresql to do the sub-
selection and while updating the first row of this sub-select it sees that this
row was updated since the update statement (or the transaction) was started.
And then it re-checks the condition just for this row (or maybe for a bunch of
rows on the same page). if it comes to updating the next row it happens again.

re-checking 40000+ rows with a very expensive sub-select plan is not good at
all. 40000 times  800 ms = 10 hours.

Am I right with my suspicion?
If yes, how can I fix it?

kind regards
Janning