• Things To Note
• Assignment 2
• EXPLAIN Examples
• Exercise: EXPLAIN examples
• Using EXPLAIN
• Transaction Processing
• Transaction Processing
• Transaction Terminology
• Schedules
• Transaction Anomalies
• Exercise: Update Anomaly
• Exercise: How many Schedules?
• Schedule Properties
• Transaction Failure
• Recoverability
• Exercise: Recoverability/Serializability
• Cascading Aborts
• Strictness
• Classes of Schedules
• Transaction Isolation
• Transaction Isolation
• Serializability
• Exercise: Serializability Checking
• Transaction Isolation Levels
• Implementing Concurrency Control
• Concurrency Control
• Lock-based Concurrency Control
• Two-Phase Locking
• Problems with Locking
• Deadlock

❖ Things To Note

• Assignment 1
  • full-marks submissions available ... the rest ...
• Assignment 2
  • due at start week 10 (11:59pm Monday 15 April)
• Help Sessions
  • Tuesday 9-10.30,   Thursday 10-12,   Friday 11-1
• Exam
  • Thu 9 May ... in CSE labs, closed environment, invigilated
  • two 3-hour sessions ... morning + afternoon ... no overlap
  • will collect morning/afternoon preferences in week 10

❖ Assignment 2

Files involved:

• commands:   create.c,   insert.c,   select.c,   dump.c,   stats.c
• ADTs:   bits.*,   chvec.*,   hash.*,   page.*,   query.*,   reln.*,   tuple.*,   util.*

You need to modify (at least):   query.c,   reln.c,   tuple.c

Can add helper functions private to ADTs.

Do NOT change ADT interfaces (i.e. the *.h files)

For testing, we use our versions of the commands

• they assume the interfaces given in the ADT *.h files

Submit all of the files that you changed.

❖ Assignment 2 (cont)

How do I know it's correct?

Task 1: print hash for each attr, manually determine MA hash

Task 2: grep in data file, run select, compare results

Task 3: use stats to check that the file has expanded appropriately

Debugging?

• since it's pure C, (learn to) use GDB
• might prove to be useful in the exam

Try to avoid memory leaks

• we'll be testing with large data sets

❖ EXPLAIN Examples

Database

people(id, family, given, title, name, ..., birthday)
courses(id, subject, semester, homepage) 
course_enrolments(student, course, mark, grade, ...) 
subjects(id, code, name, longname, uoc, offeredby, ...)
...

where

       table_name          | n_records 
---------------------------+-----------
 people                    |     55767
 courses                   |     73220
 course_enrolments         |    525688
 subjects                  |     18525
...

❖ EXPLAIN Examples (cont)

Example: Select on non-indexed attribute

uni=# explain
uni=# select * from Students where stype='local';
                     QUERY PLAN
----------------------------------------------------
 Seq Scan on students
             (cost=0.00..562.01 rows=23543 width=9)
   Filter: ((stype)::text = 'local'::text)

where

• Seq Scan = operation (plan node)
• cost=StartUpCost..TotalCost
• rows=NumberOfResultTuples
• width=SizeOfTuple (# bytes)

❖ EXPLAIN Examples (cont)

Example: Select on non-indexed attribute

uni=# explain analyze
uni=# select * from Students where stype='local';
                       QUERY PLAN
----------------------------------------------------------
 Seq Scan on students
             (cost=0.00..562.01 rows=23543 width=9)
             (actual time=0.011..4.704 rows=23551 loops=1)
   Filter: ((stype)::text = 'local'::text)
   Rows Removed by Filter: 7810
 Planning time: 0.054 ms
 Execution time: 5.875 ms

❖ EXPLAIN Examples (cont)

Example: Select on indexed, unique attribute

uni=# explain analyze
uni-# select * from Students where id=1216988;
                       QUERY PLAN
-------------------------------------------------------
 Index Scan using students_pkey on students
                  (cost=0.29..8.30 rows=1 width=9)
                  (actual time=0.011..0.012 rows=1 loops=1)
   Index Cond: (id = 1216988)
 Planning time: 0.066 ms
 Execution time: 0.062 ms

❖ EXPLAIN Examples (cont)

Example: Join on a primary key (indexed) attribute

uni=# explain analyze
uni-# select s.id,p.name
uni-# from Students s, People p where s.id=p.id;
                      QUERY PLAN
----------------------------------------------------------
Merge Join  (cost=0.58..2829.25 rows=31361 width=18)
            (actual time=0.044..25.883 rows=31361 loops=1)
  Merge Cond: (s.id = p.id)
  ->  Index Only Scan using students_pkey on students s
            (cost=0.29..995.70 rows=31361 width=4)
            (actual time=0.033..6.195 rows=31361 loops=1)
        Heap Fetches: 31361
  ->  Index Scan using people_pkey on people p
            (cost=0.29..2434.49 rows=55767 width=18)
            (actual time=0.006..6.662 rows=31361 loops=1)
Planning time: 0.259 ms
Execution time: 27.327 ms

❖ EXPLAIN Examples (cont)

Example: Join on a non-indexed attribute

uni=# explain analyze
uni=# select s1.code, s2.code
uni-# from Subjects s1, Subjects s2
uni-# where s1.offeredBy = s2.offeredBy and s1.code < s2.code;
                        QUERY PLAN
---------------------------------------------------------------
Hash Join  (cost=1286.03..126135.12 rows=2371100 width=18)
           (actual time=7.356..6806.042 rows=3655437 loops=1)
  Hash Cond: (s1.offeredby = s2.offeredby)
  Join Filter: (s1.code < s2.code)
  Rows Removed by Join Filter: 3673157
  ->  Seq Scan on subjects s1 
          (cost=0.00..1063.79 rows=17779 width=13)
          (actual time=0.009..4.602 rows=17779 loops=1)
  ->  Hash  (cost=1063.79..1063.79 rows=17779 width=13)
            (actual time=7.301..7.301 rows=17720 loops=1)
        Buckets: 32768  Batches: 1  Memory Usage: 1087kB
        ->  Seq Scan on subjects s2
                (cost=0.00..1063.79 rows=17779 width=13)
                (actual time=0.005..4.452 rows=17779 loops=1)
Planning time: 0.159 ms
Execution time: 6949.167 ms

❖ Exercise: EXPLAIN examples

Using the database described earlier ...

Course_enrolments(student, course, mark, grade, ...)
Courses(id, subject, semester, homepage)
People(id, family, given, title, name, ..., birthday)
Program_enrolments(id, student, semester, program, wam, ...)
Students(id, stype)
Subjects(id, code, name, longname, uoc, offeredby, ...)

create view EnrolmentCounts as
 select s.code, t.year, t.term, count(e.student) as nstudes
   from Courses c join Subjects s on c.subject=s.id
        join Course_enrolments e on e.course = c.id
        join Semesters t on c.semester = t.id
  group by s.code, t.year, t.term

predict how each of the following queries will be executed ...

❖ Exercise: EXPLAIN examples (cont)

Check your prediction using the EXPLAIN ANALYZE command.

1. select max(birthday) from People
2. select max(id) from People
3. select family from People order by family
4. select distinct p.id, p.name
from People p, Course_enrolments e
where p.id=e.student and e.grade='FL'
5. select * from EnrolmentCounts where code='COMP9315'

Examine the effect of adding ORDER BY and DISTINCT.

Add indexes to improve the speed of slow queries.

❖ Using EXPLAIN

For more information on reading plans from EXPLAIN

• PostgreSQL documentation section 14.1

Can get EXPLAIN output in different formats:

• FORMAT { TEXT | XML | JSON | YAML }
• details in the PostgreSQL documentation EXPLAIN entry

General PostgreSQL performance tuning

• PostgreSQL documentation chapter 14

❖ Transaction Processing

❖ Transaction Processing

A transaction (tx) is ...

• a single application-level operation
• performed by a computation involving multiple DB operations

A transaction effects a state change on the DB

❖ Transaction Processing (cont)

Transaction states:

COMMIT ⇒ all changes preserved,   ABORT ⇒ database unchanged

❖ Transaction Processing (cont)

Concurrent transactions are

• desirable, for improved performance (throughput)
• problematic, because of potential unwanted interactions

To ensure problem-free concurrent transactions:

• Atomic ... whole effect of tx, or nothing
• Consistent ... individual tx's are "correct" (wrt application)
• Isolated ... each tx behaves as if no concurrency
• Durable ... effects of committed tx's persist

❖ Transaction Processing (cont)

Transaction processing:

• the study of techniques for realising ACID properties

Consistency is the property:

• a tx is correct with respect to its own specification
• a tx performs a mapping that maintains all DB constraints

Ensuring this must be left to application programmers.

Our discussion focusses on: Atomicity, Durability, Isolation

❖ Transaction Processing (cont)

Atomicity is handled by the commit and abort mechanisms

• commit ends tx and ensures all changes are saved/persisted
• abort ends tx and undoes changes "already made"

Durability is handled by implementing stable storage, via

• redundancy, to deal with hardware failures
• logging/checkpoint mechanisms, to recover state

Isolation is handled by concurrency control mechanisms

• possibilities: lock-based, timestamp-based, check-based
• various levels of isolation are possible (e.g. serializable)

❖ Transaction Processing (cont)

Where transaction processing fits in the DBMS:

❖ Transaction Terminology

To describe transaction effects, we consider:

• READ - transfer data from "disk" to memory
• WRITE - transfer data from memory to "disk"
• ABORT - terminate transaction, unsuccessfully
• COMMIT - terminate transaction, successfully

Relationship between the above operations and SQL:

• SELECT produces READ operations on the database
• UPDATE and DELETE produce READ then WRITE operations
• INSERT produces WRITE operations

❖ Transaction Terminology (cont)

More on transactions and SQL

• BEGIN starts a transaction
  • the begin keyword in PLpgSQL is not the same thing
• COMMIT commits and ends the current transaction
  • some DBMSs e.g. PostgreSQL also provide END as a synonym
  • the end keyword in PLpgSQL is not the same thing
• ROLLBACK aborts the current transaction, undoing any changes
  • some DBMSs e.g. PostgreSQL also provide ABORT as a synonym

In PostgreSQL, tx's cannot be defined inside functions (e.g. PLpgSQL)

❖ Transaction Terminology (cont)

The READ, WRITE, ABORT, COMMIT operations:

• occur in the context of some transaction T
• involve manipulation of data items X, Y, ...   (READ and WRITE)

The operations are typically denoted as:

RT(X)		read item X in transaction T
WT(X)		write item X in transaction T
AT		abort transaction T
CT		commit transaction T

❖ Schedules

A schedule gives the sequence of operations from ≥ 1 tx

Serial schedule for a set of tx's T₁ .. T_n

• all operations of T_i complete before T_i+1 begins

E.g.   R_T1(A)   W_T1(A)   R_T2(B)   R_T2(A)   W_T3(C)   W_T3(B)  

Concurrent schedule for a set of tx's T₁ .. T_n

• operations from individual T_i's are interleaved

E.g.   R_T1(A)   R_T2(B)   W_T1(A)   W_T3(C)   W_T3(B)   R_T2(A)  

❖ Schedules (cont)

Serial schedules guarantee database consistency

• each T_i  commits before T_i+1
• prior to T_i  database is consistent
• after T_i  database is consistent   (assuming T_i is correct)
• before T_i+1  database is consistent ...

Concurrent schedules interleave tx operations arbitrarily

• and may produce a database that is not consistent
• after all of the transactions have committed successfully

❖ Transaction Anomalies

What problems can occur with (uncontrolled) concurrent tx's?

The set of phenomena can be characterised broadly under:

• dirty read:
  reading data item written by a concurrent uncommitted tx
• nonrepeateable read:
  re-reading data item, since changed by another concurrent tx
• phantom read:
  re-scanning result set, finding it changed by another tx

❖ Exercise: Update Anomaly

Consider the following transaction (expressed in pseudo-code):

-- Accounts(id,owner,balance,...)
transfer(src id, dest id, amount int)
{
   -- R(X)
   select balance from Accounts where id = src;
   if (balance >= amount) {
      -- R(X),W(X)
      update Accounts set balance = balance-amount
      where id = src;
      -- R(Y),W(Y)
      update Accounts set balance = balance+amount
      where id = dest;
}  }

If two transfers occur on this account simultaneously,
give a schedule that illustrates the "dirty read" phenomenon.

❖ Exercise: How many Schedules?

In the previous exercise, we looked at several schedules

For a given set of tx's T₁ ... T_n ...

• how many serial schedules are there?
• how many total schedules are there?

❖ Schedule Properties

If a concurrent schedule on a set of tx's TT ...

• produces the same effect as a serial schedule on TT
• then we say that the schedule is serializable

Primary goal of isolation mechanisms (see later) is

• arrange execution of individual operations in tx's in TT
• to ensure that a serializable schedule is produced

Serializability is one property of a schedule, focusing on isolation

Other properties of schedules focus on recovering from failures

❖ Transaction Failure

So far, have implicitly assumed that all transactions commit.

Additional problems can arise when transactions abort.

Consider the following schedule where transaction T1 fails:

T1: R(X) W(X) A
T2:             R(X) W(X) C

Abort will rollback the changes to X, but ...

Consider three places where the rollback might occur:

T1: R(X) W(X) A [1]     [2]        [3]
T2:                 R(X)    W(X) C

❖ Transaction Failure (cont)

Abort / rollback scenarios:

T1: R(X) W(X) A [1]     [2]        [3]
T2:                 R(X)    W(X) C

Case [1] is ok

• all effects of T1 vanish; final effect is simply from T2

Case [2] is problematic

• some of T1's effects persist, even though T1 aborted

Case [3] is also problematic

• T2's effects are lost, even though T2 committed

❖ Recoverability

Consider the serializable schedule:

T1:        R(X)  W(Y)  C
T2:  W(X)                 A

(where the final value of Y is dependent on the X value)

Notes:

• the final value of X  is valid (change from T₂  rolled back)
• T₁  reads/uses an X  value that is eventually rolled-back
• even though T₂  is correctly aborted, it has produced an effect

Produces an invalid database state, even though serializable.

❖ Recoverability (cont)

Recoverable schedules avoid these kinds of problems.

For a schedule to be recoverable, we require additional constraints

• all tx's T_i  that wrote values used by T_j
• must have committed before T_j  commits

and this property must hold for all transactions T_j

Note that recoverability does not prevent "dirty reads".

In order to make schedules recoverable in the presence of dirty reads and aborts, may need to abort multiple transactions.

❖ Exercise: Recoverability/Serializability

Recoverability and Serializability are orthogonal, i.e.

• a schedule can be  R & S,  !R & S,  R &!S,  !R & !S

Consider the two transactions:

T1:  W(A)  W(B)  C
T2:  W(A)  R(B)  C

Give examples of schedules on T1 and T2 that are

• recoverable and serializable
• not recoverable and serializable
• recoverable and not serializable

❖ Cascading Aborts

Recall the earlier non-recoverable schedule:

T1:        R(X)  W(Y)  C
T2:  W(X)                 A

To make it recoverable requires:

• delaying T₁'s commit until T₂ commits
• if T₂ aborts, cannot allow T₁ to commit

T1:        R(X)  W(Y) ...   C? A!
T2:  W(X)                 A

Known as cascading aborts (or cascading rollback).

❖ Cascading Aborts (cont)

Example: T₃ aborts, causing T₂ to abort, causing T₁ to abort

T1:                    R(Y)  W(Z)        A
T2:        R(X)  W(Y)                 A
T3:  W(X)                          A

Even though T₁ has no direct connection with T₃
(i.e. no shared data).

This kind of problem ...

• can potentially affect very many concurrent transactions
• could have a significant impact on system throughput

❖ Cascading Aborts (cont)

Cascading aborts can be avoided if

• transactions can only read values written by committed transactions

  (alternative formulation: no tx can read data items written by an uncommitted tx)

Effectively: eliminate the possibility of reading dirty data.

Downside: reduces opportunity for concurrency.

These are called ACR (avoid cascading rollback) schedules.

All ACR schedules are also recoverable.

❖ Strictness

Strict schedules also eliminate the chance of writing  dirty data.

A schedule is strict if

• no tx can read values written by another uncommitted tx   (ACR)
• no tx can write a data item written by another uncommitted tx

Strict schedules simplify the task of rolling back after aborts.

❖ Strictness (cont)

Example: non-strict schedule

T1:  W(X)        A
T2:        W(X)     A

Problems with handling rollback after aborts:

• when T₁ aborts, don't rollback   (need to retain value written by T₂)
• when T₂ aborts, need to rollback to pre-T₁   (not just pre-T₂)

❖ Classes of Schedules

Relationship between various classes of schedules:

Schedules ought to be serializable and strict.

But more serializable/strict ⇒ less concurrency.

DBMSs allow users to trade off "safety" against performance.

❖ Transaction Isolation

❖ Transaction Isolation

Simplest form of isolation: serial execution   (T₁ ; T₂ ; T₃ ; ...)

Problem: serial execution yields poor throughput.

Concurrency control schemes (CCSs) aim for "safe" concurrency

Abstract view of DBMS concurrency mechanisms:

❖ Serializability

Consider two schedules S₁ and S₂ produced by

• executing the same set of transactions T₁..T_n concurrently
• but with a non-serial interleaving of R/W operations

S₁  and S₂  are equivalent if StateAfter(S₁)  =  StateAfter(S₂)

• i.e. final state yielded by S₁ is same as final state yielded by S₂

S  is a serializable schedule (for a set of concurrent tx's T₁ ..T_n) if

• S  is equivalent to some serial schedule S_s of T₁ ..T_n

Under these circumstances, consistency is guaranteed
(assuming no aborted transactions and no system failures)

❖ Serializability (cont)

Two formulations of serializability:

• conflict serializibility
  • i.e. conflicting R/W operations occur in the "right order"
  • check via precedence graph; look for absence of cycles
• view serializibility
  • i.e. read operations see the correct version of data
  • checked via VS conditions on likely equivalent schedules

View serializability is strictly weaker than conflict serializability.

❖ Exercise: Serializability Checking

Is the following schedule view/conflict serializable?

T1:        W(B)  W(A)
T2:  R(B)                    W(A)
T3:                    R(A)        W(A)

Is the following schedule view/conflict serializable?

T1:        W(B)  W(A)
T2:  R(B)              W(A)
T3:                          R(A)  W(A)

❖ Transaction Isolation Levels

SQL programmers' concurrency control mechanism ...

set transaction
    read only  -- so weaker isolation may be ok
    read write -- suggests stronger isolation needed
isolation level
    -- weakest isolation, maximum concurrency
    read uncommitted
    read committed
    repeatable read
    serializable
    -- strongest isolation, minimum concurrency

Applies to current tx only; affects how scheduler treats this tx.

❖ Transaction Isolation Levels (cont)

Implication of transaction isolation levels:

❖ Transaction Isolation Levels (cont)

For transaction isolation, PostgreSQL

• provides syntax for all four levels
• treats read uncommitted as read committed
• repeatable read behaves like serializable
• default level is read committed

Note: cannot implement read uncommitted because of MVCC

For more details, see PostgreSQL Documentation section 13.2

• extensive discussion of semantics of UPDATE, INSERT, DELETE

❖ Transaction Isolation Levels (cont)

A PostgreSQL tx consists of a sequence of SQL statements:

BEGIN S1; S2; ... Sn; COMMIT;

Isolation levels affect view of DB provided to each S_i:

• in read committed ...
  • each S_i  sees snapshot of DB at start of S_i
• in repeatable read and serializable ...
  • each S_i  sees snapshot of DB at start of tx
  • serializable checks for extra conditions

Transactions fail if the system detects violation of isolation level.

❖ Implementing Concurrency Control

❖ Concurrency Control

Approaches to concurrency control:

• Lock-based
  • Synchronise tx execution via locks on relevant part of DB.
• Version-based   (multi-version concurrency control)
  • Allow multiple consistent versions of the data to exist.
    Each tx has access only to version existing at start of tx.
• Validation-based   (optimistic concurrency control)
  • Execute all tx's; check for validity problems on commit.
• Timestamp-based
  • Organise tx execution via timestamps assigned to actions.

❖ Lock-based Concurrency Control

Locks introduce additional mechanisms in DBMS:

The Lock Manager

• manages the locks requested by the scheduler

❖ Lock-based Concurrency Control (cont)

Lock table entries contain:

• object being locked   (DB, table, tuple, field)
• type of lock: read/shared, write/exclusive
• FIFO queue of tx's requesting this lock
• count of tx's currently holding lock   (max 1 for write locks)

Lock and unlock operations must be atomic.

Lock upgrade:

• if a tx holds a read lock, and it is the only tx holding that lock
• then the lock can be converted into a write lock

❖ Lock-based Concurrency Control (cont)

Synchronise access to shared data items via following rules:

• before reading X, get read (shared) lock on X
• before writing X, get write (exclusive) lock on X
• a tx attempting to get a read lock on X is blocked if another tx already has write lock on X
• a tx attempting to get an write lock on X is blocked if another tx has any kind of lock on X

These rules alone do not guarantee serializability.

❖ Lock-based Concurrency Control (cont)

Consider the following schedule, using locks:

T1(a): Lr(Y)     R(Y)           continued
T2(a):      Lr(X)    R(X) U(X)  continued

T1(b):      U(Y)         Lw(X) W(X) U(X)
T2(b): Lw(Y)....W(Y) U(Y)

(where L_r = read-lock, L_w = write-lock, U = unlock)

Locks correctly ensure controlled access to X and Y.

Despite this, the schedule is not serializable.  (Ex: prove this)

❖ Two-Phase Locking

To guarantee serializability, we require an additional constraint:

• in every tx, all lock requests precede all unlock requests

Each transaction is then structured as:

• growing phase where locks are acquired
• action phase where "real work" is done
• shrinking phase where locks are released

Clearly, this reduces potential concurrency ...

❖ Problems with Locking

Appropriate locking can guarantee correctness.

However, it also introduces potential undesirable effects:

• Deadlock
  • No transactions can proceed; each waiting on lock held by another.
• Starvation
  • One transaction is permanently "frozen out" of access to data.
• Reduced performance
  • Locking introduces delays while waiting for locks to be released.

❖ Deadlock

Deadlock occurs when two transactions are waiting for a lock on an item held by the other.

Example:

T1: Lw(A) R(A)            Lw(B) ......
T2:            Lw(B) R(B)       Lw(A) .....

How to deal with deadlock?

• prevent it happening in the first place
• let it happen, detect it, recover from it