CSE 444 Notes

Only transactions with blind writes (writes without a read) are in the narrow set of view serializable schedules that are not conflict serializable. Here's an example of a blind write that is conflict serializable:

It's a terminology thing. You can still recover a schedule that is, say, view serializable, but not conflict serializable, as long as it commits transactions in the right order. It's just not "recoverable" by the textbook definition.

Stricter than the recoverability requirement above: A transaction cannot read anything until the dependency transaction has committed. This transaction is recoverable but might have cascading aborts:

This one avoids cascading aborts:

Strict 2PL prevents cascading aborts.

By enforcing transactions to be serializable in the order they began, timestamp-based concurrency control can reject many schedules that lock-based control would allow. However, with timestamps, we can occasionally re-order writes.

If transaction T1 wants to write element X, but the last write timestamp on X, T2, is newer than our timestamp, an immediate analysis makes it seem like we have to abort. But, if the read timestamp on X is older than T1, we know two things about the serial schedule that we are trying to replicate:

• T2 has overwritten X (blind write), so any future reads must have timestamps after T2 and expect to see what T2 wrote to X.
• No transaction has already read us.

Nobody read us, nobody will, what's the point of the write at all? We can drop it.

Summary: If RT(X)<T1 and WT(X)>T1 when T1 wants to write to X, we can just not do the write.

Do you need to indefinitely store a timestamp for the last reader and writer for all elements? If you wanted to do tuple-based locking, for example (and tuple based locking is especially good for an optimistic locker, because collisions are much just likely), this could get expensive.

Can we just hold a mapping from element IDs to timestamps, then sometimes remove entries to indicate that the last read or write was "long ago"? Well, how long ago is long ago? Can we remove after a transaction has committed?

This would be allowed if we remove timestamps after commit, but is nonserializable.

A better solution is to remove timestamps after commit when the transaction committing has the oldest timestamp of all outstanding transactions.

WT(X)

The timestamp of the last write on element X.

RT(X)

Timestamp of last read on X.

TS(T)

Timestamp of transaction T

C(X)

Boolean, whether the last transaction to write X has committed.

To ensure recoverability at a major cost to performance, just enforce commits in the order of timestamps. To be a bit smarter, require that C(X)=TRUE when reading X or when writing X and WT(X)>TS(T), usually by delaying a read or write until C(X)=TRUE. We obviously have to enforce it on reads, otherwise we could read uncommitted data. On writes, if we are overwriting an old value (WT(X)<)

Timestamp scheduling ensures view serializability, avoids cascading aborts if you want, but does not handle phantom insertions.

A commit bit, like C(X) in the timestamp system, will ensure that we only read a version once the transaction that created it has committed.

Not a problem! Even long-term storage of elements include a timestamp. When we insert a new tuple, it also has a timestamp on it – there's no un-timestamped copy of the tuple. A read with a timestamp before the insertion will not be able to access the newly read tuple because its version is too recent. Similarly with deletion, we basically store a tombstone as the latest version, so that old reads still read a valid tuple.

• Only the transaction that created a version can write to it, ever.

Usually, you have to scan through the entire undo log to check for very old uncommitted transactions. It's safe, however, to stop scanning once you've reached a point where all older log entries are from committed transactions; you won't undo any of them.

In practice, checkpointing is done periodically. In quiescent checkpointing, new transactions are disallowed, and once all outstanding transactions have committed, we insert a checkpoint, then resume the database. This is horrible: We have to pause all transactions.

A method of nonquiescent checkpointing: When the cron runs, insert a START_CKPT that contains the list of outstanding transactions into the WAL. Every time a transaction commits, insert an END_CKPT if all the transactions from the last START_CKPT have all committed. How far back do you go when undoing? Back to the START_CKPT corresponding to the most recent END_CKPT. We have to go back to the start, not the end, because transactions not listed in the START_CKPT may have begun between the START and END. We cannot go back to a START without an in-progress END because we will not know that all transactions involved in that START are done. When the conditions are followed, we go back to a point where we know all transactions that were outstanding, and we know they are all committed.

The END_CKPT is pedagogical: During recovery, we can just calculate where it should be from the COMMITS. Then, the START_CKPT are really just lists of all existing transactions at points in time.

Another way to determine where to start reading is to take the most recent START_CKPT, regardless of whether it is complete, and continue undoing until we see the START of all transactions in the START_CKPT.

PERSONAL: Periodically scan forwards from the last checkpoint, inserting a new checkpoint every time we are at a location where all transactions are committed.

Each line of the WAL has a pointer to the last line corresponding to the same transaction. The transaction itself (in the catalog) has some pointer to the mot recent line related to it in the WAL. So we can go back and undo all the related stuff.

START_CKPT, like with undo log, contains the txnids of all outstanding transactions. However, instead of placing END_CKPT at commit, place END_CKPT when all blocks not synced with disk at the START_CKPT have been flushed. Now, an END_CKPT means that all transactions committed before the transactions listed in the corresponding START_CKPT are flushed to disk.

When recovering, we redo starting from the earliest START of any transaction mentioned in the START_CKPT corresponding to the most recent END_CKPT. This is the earliest possible time that a dirty block may have been dirtied.

PERSONAL: Have some daemon that is constantly writing things from the WAL to disk when the disk isn't too busy, and deletes the UPDATE from the log

In an undo log, we implement ROLLBACK using the log. But with a redo log, we could instead implement COMMIT by doing a selective redo on the relevant operations. In practice, though, you don't – just write things to disk when convenient.

1. Analysis: Determine what parts of the log we might have to redo or undo.
2. Redo: Get the database back to the state it was in when it crashed.
3. Undo: Rollback uncomitted transactions. We keep track of how much we've undone, so that redo not only redoes the dirty pages but also redoes the partial undos if a crash happens during undo.

The weird part of ARIES is that you always redo. This means that at the end of the redo phase, dirty pages will be…dirty.

There are START and END tokens in the WAL, just like undo and redo logs. However, the contents are very different. Starting at the moment after the START token is written, the dbms starts collecting:

• The set of outstanding transactions and the lastLSN for each of those transactions. lastLSN is the most recent WAL update (or CLR) related to that transaction.
• The set of dirty pages.

And when you believe you're done, you write the END token containing those two sets. Of course, transactions might start or stop, clean pages might be dirtied, and dirtied pages may be flushed between the START and the END. The only guarantee is that the two sets are supersets of the sets of outstanding transactions and dirty pages that were outstanding and dirty, respectively, at both START and END. It's also a subset of the outstanding/dirty transactions/pages that were outstanding/dirty at either START or END. Put more weakly, a superset of all outstanding transactions and dirty pages that were outstanding/dirty at the START and any point after or equal to END.

Unlike simple undo or redo, we cannot start undoing nor redoing from any checkpoint. The reason we could start recovering at a START in undo and redo was because their checkpointing systems waiting to make the checkpoint until some condition was met, so we know the checkpoint is safe to recover from. Fuzzy checkpoints are constructed very quickly and simply tell us how messy everything is.

Starting at the redo point found during analysis, repeat all update and CLR actions (which we'll get to later) that are related to dirty pages and occurred after the page was last written to disk. We verify the last property by ensuring that:

• The recLSN is newer than the LSN for the update, which indicates that the update was certainly written to disk (but does not guarantee that it was not written to disk, because we have a superset of the dirty pages).
• The pageLSN, which is stored on-disk in the page and is the more correct version of the recLSN, is also older than the update's LSN. PERSONAL: The existance of a pageLSN means that we actually could get the exact set of dirty pages, rather than a subset, during the redo-finding pass. But because these are only stored on disk (and not in the WAL), this is extra expensive. Couldn't we store an entry to the log whenever a page is flushed, just like we store when a transaction is committed? Possible answer: We need to know exactly which transactions are outstanding so we don't undo committed transactions, so we must go to any expense to track them properly. This is not true for dirty pages. Usually the number of dirty pages >> number of transactions, which is another reason why we need to be more careful about performance with pages than transactions.

The pageLSN must be updated whenever a redo action is performed (undo and redo actions are written to disk immediately) and whenever a page is flushed to disk during normal operation.

Ensuring that we don't redo old actions (from before the page most recently became dirty) is just for efficiency. If the system crashes during recovery, the second recovery will start redoing from no further forwards than where we left off, so eventually all relevant actions from the redo forward will be undone. The optimization simply changes what counts as "relevant" on the this path from past to present.

Take the set of all lastLSN for outstanding transactions. Start with the most recent one (we must undo backwards). If it's an update:

1. Write-ahead that we are about to undo something. This is in the form of a CLR, "Compensation Log Record". While normal update logs contain both the old value and the new value, so that we can redo or undo them, the CLR is "redo-only": It contains only the value that we are undoing to (the old value from the update that the CLR corresponds to). We'll get to what happens when you discover a CLR during the undo process soon – but you don't undo the CLR itself in any sense. In addition to the value, the CLR contains a nextUndoLSN pointer to the update just before the update that the CLR corresponds to. In other word, the prevLSN of the corresponding update, which may be null (if we just undid the first update of the transaction). It says what should be undone next after this CLR.
2. Perform the action represented by the CLR. This means writing the old value from the update log into the page and updating the pageLSN (which is safe, because redo is already complete).
3. Add the prevLSN of the update (the same LSN stored in the CLR) to the set of things to undo, unless prevLSN is null.
4. If this is the first update in the transaction, write a transaction-end token to the WAL: Rollback successful!

If a CLR is encountered, then the system must have crashed while recovering/rolling back this transaction. Any other case is impossible: If the roll back process had not yet begun, there would be no CLR. If rollback was complete, there would be a transaction-end token in the WAL and this transaction would never have ended up in the set of outstanding transactions. It is possible that this was the last CLR corresponding to the transaction, which means (after the redo) that the disk is now in the fully rolled-back state for the transaction. The crash must have occurred either while actually undoing the update corresponding to this final CLR or just before/while writing the transaction-end token to the WAL. Either way, the system crashed before the undo was complete, which is defined as after the transaction-end token has been successfully written to disk.

If a crash occurs between steps 1 and 2, the undo during next recovery will still proceed normally. The lastLSN will point to the correct CLR because it's determined empirically during analysis. And this CLR which was interrupted during the second crash will be caried out by the redo phase.

What do we actually do when we discover a CLR during undo? We add its nextUndoLSN to the set of things we want to undo at some point. We don't actually modify any pages based on a CLR – it's "redo-only".

Sometimes, when an entry is added to the log, it is not necessary to instantly write that log update to disk. Here's all the times the log is updated and whether or not it needs to be flushed immediately:

When committing or aborting, there is a COMMIT or ABORT record that gets written to the WAL as well as an END record. The END record means that the transaction is really completely over and that no more records related to that transaction will ever be written to the log. The END records are used during analysis to reconstruct the running transactions table. What happens between commit/abort and end? For commit, the WAL is flushed to disk and some bookkeeping (presumably on disk?) happens. For example, the database might keep a list of all transactions that have ever committed – adding to that list would happen between commit and end. If there's a crash between commit and end, the bookkeeping still gets done. The application gets confirmation that the transaction has committed before the bookkeeping, though.

For abort, all the CLRs are created between abort and end. I'm not entirely sure why we need the abort at all in this case, because we would have rolled back the transaction anyway in case of a crash, and the end record on its own is enough to determine the set of running transactions during analysis.

From https://stackoverflow.com/a/11459843/1233320

while (sth.get() > 1) {
    Thread.sleep(1);
}

could be compiled to

if (sth.get() > 1) {
    while (true) {
        Thread.sleep(1);
    }
}

if sth.get() is a non-synchronized getter. When accessing a value without any guarantees, the only thing you know for sure is that you are reading a value of it that really existed at some point in time. The optimizer may validly assume it never changes. This is almost never desirable.

Locks, such as java.util.concurrent.locks.ReentrantLock, have a tryLock() method that fails immediately (or after a timeout) if the lock cannot be acquired. This can be used to mitigate deadlock, unlike with simple intrinsic locks and synchronization.

• BlockingQueue: Replaces Queue
• ConcurrentHashMap: Replaces HashMap
• ConcurrentNavigableMap: Replaces TreeMap

AtomicInteger, for example, has an atomic increment method.

An array of "slots", which each could contain a tuple. Record IDs point to a page, then a slot. This means we cannot move around tuples to different slots (eg, to defragment after removing a tuple in the middle of a page), because it would invalidate all the record ids from indices, etc. So, typically you just put a tombstone where you deleted the tuple to mark it as unused space when iterating over the page. The only header information we need is the total number of in-use slots in the page.

When variable-length tuples are allowed, the header has pointers to each tuple and the length of the tuple being pointed to. Record IDs now point to the location in the header/slot directory, not the actual location of the main tuple. We are still prohibited from re-using a "pointer slot" in the header, but the tuples (which are much larger) can be re-arranged at will. Each pointer is small: 1 bit to indicate whether the slot is dead, then more bits to indicate the location and length of the tuple.

Just store all the pages, record how many there are. Requires a scan of all pages, until finding an empty one, to perform an insert.

One method: Each disk file contains, in its header, two lists of pages: One of totally full pages, and one of partially full pages. When inserting a tuple, you insert into the first of the partially full pages. When inserting into a page, you consider whether to move it to the full pages list. When deleting from a page, move it to the partial list. Only when the partial list is empty should you create a new page.

If we not only keep a list of the partially full pages but also store how much space they have open, it can speed up insertions when we have variable length tuples (don't need to iterate until finding a page that has enough empty space) or inserting many tuples (faster to insert them all into a single page).

A point here, which also applies to indices and stuff, is that this page directory is, itself, stored in pages, and will frequently exceed the size of a single page!

A "dense" clustered index has pointers to every tuple in the main table. The sorted nature of the main table means that our index could contain pointers to, say, every other tuple in the table structure. If we want to fetch a key that's not in the index, we find the key just less than it, go to its location in the table structure, then iterate forwards until we find our specific key. A sparse clustered index typically stores one entry for each page of the database, since entire pages are read at once anyway. Ie, the index simply tells you which page to look for, not which tuple.

Like a binary tree, but each node can have many children. All leaf nodes are at the same level. Each node has an alternating pattern of pointers and boundary values. The pointer between two boundary values points to a node that will eventually lead to all leaf nodes with a value between those two boundary values.

B-trees are good for range queries: Values inside a leaf node (and boundary values inside a non-leaf node) are stored in sorted order. Leaf nodes are a sort of doubly linked list; each leaf node contains pointers to the leaf nodes with values immediately greater than and less than the maximum and minimum values in this leaf node.

A typical fan-out is 100, and a typical fill factor is 67%. Recall that the minimum bound on the fill factor is 50%, for non-root nodes.

• Hash join: B(R) + B(S)
• Sort-merge join: You can usually integrate the join algorithm with the sorting algorithm; the last pass of a merge sort outputs sorted tuples, so you can store the results of the penultimate sorting pass on each table on disk, then emit tuples from the "final pass" for each table on-demand as the final join merge dictates.
• Nested Loop (By Tuple, no index): B(R) + T(R) * B(S)
• Nested Loop (unclustered index): B(R) + T(R) * T(S) / V(S, a). Recall that 1/V(S,a) is the selectivity factor for an equality filter on a given attribute. We assume that all matching tuples are in different pages.
• Nested Loop (clustered index): B(R) + T(R) * B(S) / V(S, a). Like with an unclustered index join, we loop through the values of a from table R, doing an equality filter on table S. This time, though, we know that all the matching tuples in table S will be adjacent on disk, taking up the minimum number of blocks.
• Nested Loop (By page): B(R) + B(R) * B(S)

• Nested Loop (By Block): We can decrease B(R) and B(S) by having multiple pages in the same block, where a block just has to fit comfortably in memory. We have to multiply the result by the number of pages per block, but if that number is N, the total cost: \(N*\left \frac{B(R)}{N} + \frac{B(R)}{N} * \frac{B(S)}{N} \right = B(R) + \frac{B(R) * B(S)}{N}\), a substantial improvement, since the right side was the main problem to begin with. Note that if \(N=B(R)\) that the cost is just \(B(R)+B(S)\), which is the same price as a hash join! Which is correct, if you don't care about CPU. If \(N=B(S)\), then cost is \(2*B(R)\). Wut? I think it might be related to

  Alternatively: B(R) + B(R)/(M-1) * B(S), where M is the number of pages that fit in memory. This assumes we read M-1 pages of R at a time, then read through S one page at a time. But, as you can obviously tell from the equation, if we read M-1 pages of S at a time and did single-page loops through R, the cost would be the same; it's sorta symmetrical (apart from B(R) term at the front).

First, hash all tuples from each table (keeping them segregated from the other table) with a bucket size less than M (in pages). Write all the buckets to separate files on disk. Then loop through the buckets generated from the other table simultaneously. We essentially do a (non-partitioned) hash join on these pairs of buckets, if memory permits (and it will, if B(R)+B(S)<M²): Take one bucket, hash it using a much finer algorithm (smaller bucket size), then match against elements from the other table's bucket one by one.

How do you get the buckets (the "partitioning" phase)? You create an empty M-1 pages in memory, then hash and distribute the partitions of table R one at a time. Once you've exhausted R, write the partitions to disk, then repeat for table S.

Question for office hours or something: What if the distribution on the key is not uniform, so that some buckets are much larger than others? How can we be so sure that a bucket will fit in a page?

The algorithm is slightly modified from a simple sort. First, runs from different relations are never combined. And in the final pass, we do not output tuples in order; we only output tuples when two runs have the same key, and we must output all possible pairings of tuples.

The "all possible pairings" part is important, because although a run has tuples from exactly one relation, a relation may have tuples spread out across multiple runs. The final pass combination algorithm must be aware of this.

Generally, you can do a merge join in two passes if B(R)+B(S)<M², but really it must be a bit less because a run cannot have tuples from two relations – so a number of runs equal to the number of relations being joined may not be full, meaning wasted space that cuts into the M². This is negligible because it scales with the number of relations being joined.

Cost: 3(B(R)+B(S))

Depends on the "containment of values" assumption.

Store ranges of some key vs the number of tuples in that key range.

Equal width

Each range is the same width. Some ranges may have many more tuples than others.

Equal depth

Each range has about the same number of tuples in it. Some ranges have less keys than others.

eg, a SUM aggregate can be distributed into a join – we can sum on both sides!

SELECT *, SUM(S.A)
FROM R INNER JOIN S USING (C)
GROUP BY R.B

Because the group column is different than the aggregate column, it might at first seem like we're already out of options. But we can improve a little bit.

SELECT *, SUM(S_sub.sum)
  FROM R INNER JOIN (
    SELECT *, SUM(S.A) AS sum
      FROM S
     GROUP BY S.C
    ) AS S_sub USING (C)
 GROUP BY R.B

We know that the grouping due to C is at least as fine as the grouping due to R.B will be. This inevitably means more seeks due to calculating the aggregate, but the cost savings in the join are often worth it.

A super clear example of when the benefit outweighs the cost:

SELECT COUNT(*)
  FROM big_table x, big_table y

if we count first, the join involves only two tuples. If we join first, the join involves count(big_table)² tuples.

Generalized distributivity mostly relies on associativity, so that the results from children can be smoothly combined.

A more complex example:

SELECT SUM(A.a * B.b)
  FROM A, B
       INNER JOIN USING (c)

becomes:

SELECT SUM(A_agg.acc * B_agg.acc)
  FROM (SELECT c, SUM(a) AS acc FROM A) AS A_agg
       (SELECT c, SUM(b) AS acc FROM B) AS B_agg
       INNER JOIN USING (c)

Assume two rows in each table, all matching on the join attribute. Then \[a_1*b_1 + a_1*b_2 + a_2*b_1 + a_2*b_2 = (a_1 + a_2) * (b_1 + b_2)\] You can see that upon expansion of the RHS, all the join pairs will break out. We are collapse all tuples from a table that share a join key because upon multiplication they will un-collapse.

If…

• The attributes from one table are discarded (projected away later, not used before then).
• The join attribute on the discarded relation is a primary key (no duplicates).
• The join attribute in the preserved relation is a foreign key to the join attribute in the discarded relation.
• The join attribute in the preserved relation is NOT NULL.

How joins are thought about. Each join has a physical table on the right. Most join operators aren't implemented symmetrically (i.e, they go once over one table then either probe or repeatedly scan over the other). So, having the result of a previous join (if any) on the left is amenable to pipelining.

In the vanilla Selinger's algorithm, the single tables have multiple access methods listed, but groups of tables have but a single one (the cheapest).

• Do not consider cartesian products: joins of tables without a common key (eg, joining A, B, C, where A and B share a key, and B and C share a key, but A and C share no keys, a join between A and C at the two-table level would not be considered).
• Left-deep only: Do not consider bushy trees (eg, ignore 2+2 joins at the 4 level) and always put the single table on the right to take advantage of its access methods.
• Push down selections: Each possible join outputs its cost and estimated cardinality. Include any applicable selections in that cardinality (though be careful to make sure you don't double-count selections that were performed in children even further down!)

Map: Produce an intermediate pair with key = word and value = # of occurrences for each word in the value.

Reduce: Sum all the intermediate values. If they all came directly from a Map, they will all be 1.

We assume we have a reliable "coordinator" machine. There's a PAXOS algorithm for an unreliable coordinator. Redundant disks and such reduce the need.

The user sends a COMMIT message to the coordinator. The coordinator proceeds in 2 phases:

1. Prepare: Ask each subordinate whether it would be able to handle a commit for this txn. Each subordinate, upon receiving the prepare message, writes "Prepare <txid>" into its redo log before responding "Yes" to the coordinator.
2. Commit: Write "commit" into the coordinator's redo log, then send a commit message to each subordinate until it returns ACK (if it's crashed, we have to continue sending until it comes back up).

If some subordinate reports, during the prepare phase, that it cannot go through with the commit, then we just send rollback commands to all nodes involved in the transaction.

Recovery: In class, we assume that the coordinator only sends out prepare, abort, or commit messages once to each subordinate; i.e, it does not poll them until they acknowledge. This makes the recovery process both simpler and more complex. Per subordinate:

• If the last entry is "prepare", then

• Consistency: Servers will give roughly the same results to queries.
• Availability: Requests are always satisfied.
• Performance

Weaker than serializability. Enforces serializability on all operations on each item. So, element A will always be left in a state that could have resulted from a serial schedule, and element B will always be left in a state that could have resulted from a serial schedule, but there may not be a serial schedule that would result in the states of both A and B.

Updates are given to all hosts as part of the transaction, so by the time the transaction commits, all hosts are ready. Use global 2PL locks to avoid conflicts then 2-phase commit.

Transactions commit after writing to a single replica. The writes happen eventually to the other machines.