5.6. Visibility Check Rules

Visibility check rules are a set of rules used to determine whether each tuple is visible or invisible using both the t_xmin and t_xmax of the tuple, the clog, and the obtained transaction snapshot.

These rules are too complicated to explain in detail. Therefore this document shows the minimal rules required for the subsequent descriptions. In the following, we omit the rules related to sub-transactions and ignore discussion about t_ctid, i.e. we do not consider tuples that have been updated more than twice within a transaction.

The number of selected rules is ten, and they can be classified into three cases.

5.6.1. Status of t_xmin is ABORTED

A tuple whose t_xmin status is ABORTED is always invisible (Rule 1) because the transaction that inserted this tuple has been aborted.

/* t_xmin status == ABORTED */
Rule 1:	  IF t_xmin status is 'ABORTED' THEN
                 RETURN 'Invisible'
          END IF

This rule is explicitly expressed as the following mathematical expression.

  • Rule 1: If Status(t_xmin) = ABORTED $\Rightarrow$ Invisible

5.6.2. Status of t_xmin is IN_PROGRESS

A tuple whose t_xmin status is IN_PROGRESS is essentially invisible (Rules 3 and 4), except under one condition.

 /* t_xmin status == IN_PROGRESS */
       IF t_xmin status is 'IN_PROGRESS' THEN
              IF t_xmin = current_txid THEN
Rule 2:              IF t_xmax = INVALID THEN
                           RETURN 'Visible'
Rule 3:              ELSE  /* this tuple has been deleted or updated  */
                           /* by the current transaction itself.      */
                            RETURN 'Invisible'
                     END IF
Rule 4:       ELSE   /* t_xmin ≠ current_txid */
                     RETURN 'Invisible'
              END IF
       END IF

If this tuple is inserted by another transaction and the status of t_xmin is IN_PROGRESS, then this tuple is obviously invisible (Rule 4).

If t_xmin is equal to the current txid (i.e., this tuple is inserted by the current transaction) and t_xmax is not INVALID, then this tuple is invisible because it has been updated or deleted by the current transaction (Rule 3).

The exception condition is the case where this tuple is inserted by the current transaction and t_xmax is INVALID. In this case, this tuple must be visible from the current transaction (Rule 2) because this tuple is the tuple inserted by the current transaction itself.

  • Rule 2: If Status(t_xmin) = IN_PROGRESS $\wedge$ t_xmin = current_txid $\wedge$ t_xmax = INVAILD $\Rightarrow$ Visible

  • Rule 3: If Status(t_xmin) = IN_PROGRESS $\wedge$ t_xmin = current_txid $\wedge$ t_xmax $\ne$ INVAILD $\Rightarrow$ Invisible

  • Rule 4: If Status(t_xmin) = IN_PROGRESS $\wedge$ t_xmin $\ne$ current_txid $\Rightarrow$ Invisible

5.6.3. Status of t_xmin is COMMITTED

A tuple whose t_xmin status is COMMITTED is visible (Rules 6,8, and 9), except under three conditions.

 /* t_xmin status == COMMITTED */
        IF t_xmin status is 'COMMITTED' THEN
Rule 5:        IF t_xmin is 'active' in the obtained transaction snapshot THEN
                      RETURN 'Invisible'
Rule 6:        ELSE IF t_xmax = INVALID OR status of t_xmax is 'ABORTED' THEN
                      RETURN 'Visible'
               ELSE IF t_xmax status is 'IN_PROGRESS' THEN
Rule 7:               IF t_xmax =  current_txid THEN
                             RETURN 'Invisible'
Rule 8:               ELSE  /* t_xmax != current_txid */
                             RETURN 'Visible'
                      END IF
               ELSE IF t_xmax status is 'COMMITTED' THEN
Rule 9:               IF t_xmax is 'active' in the obtained transaction snapshot THEN
                             RETURN 'Visible'
Rule 10:              ELSE
                             RETURN 'Invisible'
                      END IF
               END IF
        END IF

Rule 6 is obvious because t_xmax is INVALID or ABORTED. Three exception conditions and both Rules 8 and 9 are described as follows:

The first exception condition is that t_xmin is active in the obtained transaction snapshot (Rule 5). Under this condition, this tuple is invisible because t_xmin should be treated as in progress.

The second exception condition is that t_xmax is the current txid (Rule 7). Under this condition, as with Rule 3, this tuple is invisible because it has been updated or deleted by this transaction itself.

In contrast, if the status of t_xmax is IN_PROGRESS and t_xmax is not the current txid (Rule 8), the tuple is visible because it has not been deleted.

The third exception condition is that the status of t_xmax is COMMITTED and t_xmax is not active in the obtained transaction snapshot (Rule 10). Under this condition, this tuple is invisible because it has been updated or deleted by another transaction.

In contrast, if the status of t_xmax is COMMITTED but t_xmax is active in the obtained transaction snapshot (Rule 9), the tuple is visible because t_xmax should be treated as in progress.

  • Rule 5: If Status(t_xmin) = COMMITTED $\wedge$ Snapshot(t_xmin) = active $\Rightarrow$ Invisible

  • Rule 6: If Status(t_xmin) = COMMITTED $\wedge$ (t_xmax = INVALID $\vee$ Status(t_xmax) = ABORTED) $\Rightarrow$ Visible

  • Rule 7: If Status(t_xmin) = COMMITTED $\wedge$ Status(t_xmax) = IN_PROGRESS $\wedge$ t_xmax = current_txid $\Rightarrow$ Invisible

  • Rule 8: If Status(t_xmin) = COMMITTED $\wedge$ Status(t_xmax) = IN_PROGRESS $\wedge$ t_xmax $\ne$ current_txid $\Rightarrow$ Visible

  • Rule 9: If Status(t_xmin) = COMMITTED $\wedge$ Status(t_xmax) = COMMITTED $\wedge$ Snapshot(t_xmax) = active $\Rightarrow$ Visible

  • Rule 10: If Status(t_xmin) = COMMITTED $\wedge$ Status(t_xmax) = COMMITTED $\wedge$ Snapshot(t_xmax) $\ne$ active $\Rightarrow$ Invisible