https://15445.courses.cs.cmu.edu/fall…
Approaches:
Re-Execute Scans: run queries again at commit to see whether they produce a different result to identify missed changes.Predicate Locking: Logically determine the overlap of predicates before queries start running.Index Locking: Use keys in indexes to protect ranges.
Re-Execute Scans
The DBMS tracks the WHERE clause for all queries that the transaction executes.
→ Retain the scan set for every range query in a transaction.
Upon commit, re-execute just scan portion of each query and check whether it generates the same result.
→ Example: Run the scan for an UPDATE query but do not modify matching tuples.
Cons:
- double cost for every query.
Predicate Locking
Proposed locking scheme for System R.
→ shared lock on predicate in a WHERE clause of a SELECT query.
→ Exclusive lock on the predicate in a WHERE clause of any UPDATE, INSERT, DELETE query.
Never implemented in any system.
Index Locking
- Key-Value locks
- Gap locks
- Key-Range locks
- Hierarchy locks
Key-Value lock
Locks that cover a single key-value in an index. Need “virtual keys” for non-existent values.
Gap locks
Each transaction acquires a key-value lock on the single key that it wants to access. Then get a gap lock on the next key gap.
Resources
https://en.wikipedia.org/wiki/Isolation_%28database_systems%29#Non-repeatable_reads
https://en.m.wikipedia.org/wiki/Two-phase_locking
a transaction schedule is serializable if its outcome (e.g., the resulting database state) is equal to the outcome of its transactions executed serially, i.e. without overlapping in time.