Class

Locking disadvantage Overhead Deadlock: need special-purpose locking protocols Need to lock root node while accessing HDD Locks need to hold until the end of transaction Locks may be necessary only in the worst case OCC Reads are not restricted returning a result is considered as a write Writes Read phase -> Validation phase -> Write phase Read Phase Maintain create/write/read set Only write to local copies (copy-on-write) Assign transaction numbers at end of the read Phase Write Phase Rename all objects in write set to original name Validation Phase Issue Long read phase need to check all previous write sets not enough memory => fail transaction Starving => lock entire database after too many retries Serial Validation Obtain lock during validation / write phases serialization is the weakest criterion for preserving consistency of a concurrent transaction system,

Issue Highest isolation + lower isolation transactions running concurrently Lower isolation corrupt data ANSI SQL Isolation levels P1 Dirty Read T1 modify -> T2 read -> T1 rollback T2 read never committed data P2 Non-repeatable or Fuzzy Read T1 read -> T2 modify commit -> T1 read T1 read inconsistent P3 Phantom T1 search <condition> -> T2 insert new data -> T1 search again T1 search inconsistent Locking Share/Exclusive Locks Predicate lock lock on a set of data satisfying <condition> might include phantom data Well-formed request a lock before using Two phase lock request all locks before releasing any Duration long: hold until the transaction commits or aborts short: otherwise New SQL Isolation levels Snapshot Isolation The transaction successfully commits only if no other transaction T2 with a Commit-Timestamp in T 1‘s interval [Start-Timestamp, Commit - Timestsamp] wrote data that T 1 also wrote....

Granularity of locks Concurrency vs Overhead => Different granularities coexist Hierarchical locks Exclusive/shared access assign same lock implicitly to descendants Intention mode lock all ancestors To lock lock all ancestors in intention mode and lock self requested root to leaf, released leaf to root Compatible two lock requests can be granted concurrently NL IS IX S SIX X NL YES YES YES YES YES YES IS YES YES YES YES YES NO IX YES YES YES NO NO NO S YES YES NO YES NO NO SIX YES YES NO NO NO NO X YES NO NO NO NO NO DAG Lock Requesting S or IS should request at least one parent in IS (or greater) Requesting IX, SIX or X should request all parents in IX (or greater) Dynamic DAG Scheduling and granting requests Granted group: From |IS| … |IS| Next request: S -> Next group Conversions IS IX S SIX X IS IS IX S SIX X IX IX IX SIX SIX X S S SIX S SIX X SIX SIX SIX SIX SIX X X X X X X X One request in a queue may request conversion Must wait for other requests in the same group to be compatible Other request my convert too => dead lock Consistency Degree 2: might read 2 different values for the same key(?...

Techniques Goal Speedup Scaleup Batch Scaleup task presented as a single larger job Transactional N-times as many requests Barriers Startup time Interference (Access shared resources) Skew: some job may take too long Different choices Shared-memory Network bottleneck Shared-disks Need to lock disk when writing Shared-nothing scaled up to hundreds of processors Data Partitioning Place relation fragments at different network sites Schemes Range partitioning range query, cluster data skew (place all data in same place) Round-Robin Partitioning hard to associatively access tuples Hash Partitioning no cluster Dataflow graph Different algorithm Sort-merge join Hash join Problems Lock for a long time Read dirty database Read old version Priority inversion problem Low pri client request to hi pri server Query Optimization Find optimal physical database design Run utilities (e....

Values for each single column are stored contiguously CPU faster than IO => Use CPU to save disk bandwidth Compress data (e.g. 1 => Wisconsin, 2 => Texas) Densepack values (e.g. pack N values each K bits into N*K bits) C-Store physically stores a collection of columns, each sorted on some attribute can store overlapping projections => improves performance and redundancy Insert: Write to WS, batch move to RS Delete: marked in RS, purge later Update: insert + delete Read: historical mode query select a timestamp return the correct answer as of that timestamp Data Model Logically still tables Store projections Tuples in a projection are stored column-wise sorted on the same sort key Horizontally partitioned => each segment is associated with a key range When Query: Join multiple segments Key: Storage key RS: index in the column WS: stored as int, larger than the largest in RS SID: Segment ID Colocate join-index with EMP3(Sender) and partitioned in the same way RS Use multiple different encoding tricks Storage key is not stored (Index) WS No encoding Store storage key Update An insert is represented as a collection of new objects in WS All inserts corresponding to a single logical record have the same storage key Keys in the WS will be consistent with RS storage keys because we set the initial value of this counter to be one larger than the largest key in RS Snapshot Isolation Insertion vector contains for each record the epoch in which the record was inserted Deleted record vector contains the delete time for each tuple Tuple Mover Find segment with modify time at or before LWM (Low Water Mark lowest time user can execute queries) if deleted => discard else => move to RS Write to new RS’ segment Questions Type 3 encoding save space, not int 1:1 mapping between RS and WS?...