PostgreSQL のデッドロック検出アルゴリズムの説明に "soft edge" という記載があります。
PostgreSQL 15.3
src/backend/storage/lmgr/README
2. If a process A is behind a process B in some lock's wait queue, and their requested locks conflict, then we must say that A waits for B, since ProcLockWakeup will never awaken A before B. This creates additional edges in the WFG. We call these "soft" edges, as opposed to the "hard" edges induced by locks already held. Note that if B already holds any locks conflicting with A's request, then their relationship is a hard edge not a soft edge.
A "soft" block, or wait-priority block, has the same potential for inducing deadlock as a hard block. However, we may be able to resolve a soft block without aborting the transactions involved: we can instead rearrange the order of the wait queue. This rearrangement reverses the direction of the soft edge between two processes with conflicting requests whose queue order is reversed. If we can find a rearrangement that eliminates a cycle without creating new ones, then we can avoid an abort. Checking for such possible rearrangements is the trickiest part of the algorithm.
この "soft edge" の例が PostgreSQL ML で説明されていました。
Re: Soft deadlocks
記載されていた例を実行可能な形にしました。トランザクションが2つあり、どちらで実行したかは TX1, TX2 で記載しています。
CREATE TABLE t(v INTEGER);
BEGIN; -- TX1
BEGIN; -- TX2
LOCK TABLE t IN ACCESS SHARE MODE; -- TX1
LOCK TABLE t IN ACCESS EXCLUSIVE MODE; -- TX2
LOCK TABLE t IN ACCESS EXCLUSIVE MODE; -- TX1
実行順通りにロックを獲得するのであれば、TX2 は TX1 の ACCESS SHARE LOCK の解放を待ちます。そして、TX1 は TX2 の ACCESS EXCLUSIVE LOCK の取得・解放を待つことになります。これはデッドロック状態です。
ですが、TX2 はロックをまだ獲得していません。つまり、TX1 はロック解放を待っているわけではないので、"soft edge" となります。
そして、この場合は TX1, TX2 のロック取得順序を入れ替えることでデッドロック状態を解消できます。つまり、以下の順序で実行されたことにします。
CREATE TABLE t(v INTEGER);
BEGIN; -- TX1
BEGIN; -- TX2
LOCK TABLE t IN ACCESS SHARE MODE; -- TX1
LOCK TABLE t IN ACCESS EXCLUSIVE MODE; -- TX1
LOCK TABLE t IN ACCESS EXCLUSIVE MODE; -- TX2
このようにロック順序を入れ替えることで、トランザクション分離レベルに影響しないのかが気になりました。ですが、Serializable Snapshot Isolation (SSI) で用いるのは SIREAD ロックという別の仕組みであり、今回のロック入れ替えは影響しないと思われます（裏付けまでは取れておらず、推測です）。
PostgreSQL のトランザクション & MVCC & スナップショットの仕組み
また、"soft edge" がロックを「待機」している場合に発生する、というのもポイントです。TX1 がロックを要求した後に TX2 がロックを要求しています。ですが、TX1 のロック要求が処理されていないのであれば、TX2 のロック要求が先行したことにしても、各トランザクションには矛盾が発生しません。トランザクション全体でみれば操作の実行順が入れ替わっていますが、トランザクション単位でみれば矛盾は起きていない、ということです。これは Serializability の検証の為に、各トランザクションの操作を並び替え、直列に実行した場合と同じ結果になるかを確認するのと同じです。やはり、ロック順序の入れ替えはトランザクション分離レベルに影響しないようです。
