Ordering of transactions

VTQ table

TRX_ID

Transaction ID.

COMMIT_ID

Commit ID assigned to transaction by second trx_sys_get_new_trx_id() at commit phase. Pairs (TRX_ID, COMMIT_ID) form abstract time scale with begin, commit events strictly ordered.

TRANS_TYPE

Transaction type: RR for Repeatable Read, RC for Read Committed.

BEGIN_TS

COMMIT_TS

Timestamps for begin, commit events on physical time scale. Events are loosely ordered due to time measure inaccuracy (time jitter).

Algorithms

Functions

VTQ_COMMIT_ID(TX0)

Return COMMIT_ID by TRX_ID from VTQ.

VTQ_TRANS_TYPE(TX0)

Return TRANS_TYPE by TRX_ID from VTQ.

TRX_SEES(TX1, TX0)

Return true if TX1 sees TX0 and TX1 != TX0.

create function TRX_SEES(TRX_ID1 bigint unsigned, TRX_ID0 bigint unsigned)
returns bool
begin
    declare COMMIT_ID1 bigint unsigned default VTQ_COMMIT_ID(TRX_ID1);
    declare COMMIT_ID0 bigint unsigned default VTQ_COMMIT_ID(TRX_ID0);
    declare TRANS_TYPE1 enum('RR', 'RC') default VTQ_TRANS_TYPE(TRX_ID1);

    # Trivial case: TX1 started after TX0 committed
    if TRX_ID1 > COMMIT_ID0 then
        return true;
    end if;

    # Concurrent transactions: TX1 committed after TX0 and TX1 is Read Committed
    if COMMIT_ID1 > COMMIT_ID0 and TRANS_TYPE1 = 'RC' then
        return true;
    end if;

    # All other cases: TX1 does not see TX0
    return false;
end

TRX_SEES_EQ(TX1, TX0)

Return true if TX1 sees TX0 or TX1 == TX0.

create function TRX_SEES_EQ(TRX_ID1 bigint unsigned, TRX_ID0 bigint unsigned)
returns bool
begin
    # Trivial case: TX1 is TX0
    if TRX_ID1 = TRX_ID0 then
        return true;
    end if;

    # All other cases: call TRX_SEES()
    return TRX_SEES(TRX_ID1, TRX_ID0);
end

SELECT algorithms

AS OF query, transaction-based

select * from versioned for system_time as of transaction TRX_ID0;

Select records in queried table which transaction was before or was TRX_ID0 and made defunct by transaction after TRX_ID0:

select *
from versioned
where
    TRX_SEES_EQ(TRX_ID0, sys_trx_start) and TRX_SEES(sys_trx_end, TRX_ID0);

AS OF query, timestamp-based

select * from versioned for system_time as of timestamp TS0;

1. Get TRX_ID0 corresponding to latest commit not later than TS0:

   select TRX_ID, max(COMMIT_ID)
   from VTQ
   where COMMIT_TS <= TS0
   into (TRX_ID0, COMMIT_ID0);

   COMMIT_ID0 is not used directly in these algorithms (since can be acquired by TRX_ID0), though it is used in implementation as optimization of TRX_SEES() function.

   Note, that there is no need in time-jitter corrections as COMMIT_ID is protected from time-jitter effects. Transactions after TS0 affected by time-jitter will have COMMIT_ID lower than COMMIT_ID0 anyway.

2. Use transaction-based AS OF query:

   select *
   from versioned for system_time
   as of transaction TRX_ID0;

FROM .. TO query, transaction-based

select * from versioned for system_time from transaction TRX_ID0 to transaction TRX_ID1;

Select records in queried table which transaction was before TRX_ID1 and made defunct by transaction after or by TRX_ID0:

select *
from versioned
where
    TRX_SEES(TRX_ID1, sys_trx_start) and TRX_SEES_EQ(sys_trx_end, TRX_ID0);

BETWEEN .. AND query, transaction-based

select * from versioned for system_time between transaction TRX_ID0 and transaction TRX_ID1;

Select records in queried table which transaction was before or was TRX_ID1 and made defunct by transaction after or by TRX_ID0:

select *
from versioned
where
    TRX_SEES_EQ(TRX_ID1, sys_trx_start) and TRX_SEES_EQ(sys_trx_end, TRX_ID0);

FROM .. TO, BETWEEN .. AND queries, timestamp-based

select * from versioned for system_time from timestamp TS0 to timestamp TS1;
select * from versioned for system_time between timestamp TS0 and timestamp TS1;

1. Get TRX_ID0 corresponding to earliest commit not earlier than TS0:

   select TRX_ID, min(COMMIT_ID)
   from VTQ
   where COMMIT_TS >= TS0
   into (TRX_ID0, COMMIT_ID0);

2. Get TRX_ID1 corresponding to latest commit not later than TS1:

   select TRX_ID, max(COMMIT_ID)
   from VTQ
   where COMMIT_TS <= TS1
   into (TRX_ID1, COMMIT_ID1);

3. Use transaction-based FROM .. TO or BETWEEN .. AND query:

   select * from versioned for system_time from transaction TRX_ID0 to transaction TRX_ID1;
   # or
   select * from versioned for system_time between transaction TRX_ID0 and transaction TRX_ID1;

Ordering of concurrent transactions

Definintion

• RR: Repeatable Read, transaction opens Read View at first read;
• RC: Read Committed, transaction opens Read View at each read.

Case 0, pure RR

1. rrA started
2. rrB started
3. rrA or rrB finished
4. rrB or rrA finished

A and B don't see each other => order doesn't matter

Case 1, pure RC

1. rcA started
2. rcB started
3. rcA finished
4. rcB finished

B sees A => A, B

Case 2, pure RC

1. rcA started
2. rcB started
3. rcB finished
4. rcA finished

A sees B => B, A

Case 3, mixed

1. rrA started
2. rcB started
3. rcB finished
4. rrA finished

A and B don't see each other => order doesn't matter

Case 4, mixed

1. rrA started
2. rcB started
3. rrA finished
4. rcB finished

B sees A => A, B

Rules of ordering

1. If two RR transactions run concurrently, order of them doesn't matter;
2. If in two concurrent transactions RC finishes second, then it goes second.