deadlock in single-row select-for-update + update scenario? How could it happen?

[hubert depesz lubaczewski <depesz@xxxxxxxxx>]

I have developer with pg 9.3.5, which is reporing something really strange.

He runs importer, which does, in single transaction:

begin;
select * from table where pkey = <value> limit 1 for update;

update table set ... where pkey = <the same_value>;

commit;

and two backends running the same transaction deadlock.

I checked for duplicated rows with the same pkey value - none are there. And frankly - I'm out of ideas.

What could be wrong in such case?

Detailed logs, with just some obfuscation: https://depesz.privatepaste.com/0594a93459

depesz