JEPSEN

P3 (Phantom)

Phenomenon P3, also known as Phantom or Fuzzy Read, occurs when one transaction changes data involved in a predicate read performed by another, ongoing transaction. The definition from Berenson et al is essentially this: transaction Ti reads predicate P, then transaction Tj writes some object x in P. Then Ti and Tj commit or abort in any order.

This definition hinges on what “x in P” means, and Berenson et al are somewhat vague on this point. Informally, we wish to ensure that whatever is observed by a predicate read is stable for the duration of the transaction. As usual, we model inserts and deletions as writes, and say that every predicate read implicitly selects a single version for every object in the database: VSet(P). Assume VSet(P) contains xi, and Tj writes xj. Clearly, if both versions of x match P, this could lead to a non-repeatable predicate read, or other invariant violations. However, we also want to handle cases where xi does not match P (say, because it is unborn), and xj matches P: a second read of P would see x popping into existence. Or the inverse: xi matches P, but xj does not. We want “x in P” to cover these cases.

Jepsen suggests the following definition: P3 occurs when transaction Ti performs a read of predicate P such that VSet(P) includes some version xi. Then transaction Tj writes version xj. At least one of xi or xj match P. Both Ti and Tj may commit or abort.

P3 is defined in terms of a total order of events, and makes implicit assumptions about time and state that may not hold true. For instance, if Ti committed before Tj began, it would be odd if Tj performed a pair of predicate reads which did not, then did, reflect Ti. This is clearly not a repeatable predicate read, but because Ti is not concurrent with Tj, it does not meet this definition of P3. For this reason, Jepsen prefers G2.

Literature

Phantom comes from the ANSI SQL standard, which says:

P3 (“Phantom”): SQL-transaction T1 reads the set of rows N that satisfy some <search condition>. SQL-transaction T2 then executes SQL-statements that generate one or more rows that satisfy the <search condition> used by SQL-transaction T1. If SQL-transaction T1 then repeats the initial read with the same <search condition>, it obtains a different collection of rows.

This description is famously bad. Is the final sentence meant to be an example, or required? What about deletes? What about a write that causes a row to no longer match the search condition? In 1995 Berenson et al summarized the problems with ANSI SQL’s definitions and offered two possible interpretations of Phantom. The strict interpretation, A3, requires two reads of P, and that both transactions commit. The broad interpretation, P1, requires only one read, and covers any combination of commits and aborts.

  • P3: r1[P] … w2[y in P] … ((c1 or a1) and (c2 or a2) in any order)
  • A3: r1[P] … w2[y in P] … c2 … r1[P] … c1

Both A3 and P3 prevent a specific pattern that leads to a transaction observing different values for a repeated predicate read. However, A3 fails to prevent many predicate-related anomalies. Imagine Ti withdraws $10 from account x, Tj performs a predicate read of all accounts, and Ti deposits $10 to account y. The predicate read observes a state of the world in which the sum of all accounts is negative, rather than zero. It sees part, but not all, of Ti’s effects. P3, by contrast, prevents this.

As of 2024 the ANSI standard’s definition of isolation levels is unchanged. Whether or Phantom includes deletions remains unspecified. Berenson et al argue P3 is the correct interpretation, and Jepsen concurs.

See Also

Adya’s G2 captures “what we think the standard meant to say” in more general and precise terms. The Adya formalism relies on dataflow, rather than assuming a single database state with real-time order. P3 is also arguably broader than necessary: it still occurs even if both writer and reader abort. G2-item, by contrast, applies only to committed transactions.