Failing halfway without breaking anything

A transaction has only two ways to end.

Commit is the declaration "make the updates so far final". The moment you commit, the changes become official and visible to everybody else.

Rollback is the declaration "treat this as never having happened". However much has been rewritten, everything is wound back to the state just before it started. You use it when an error comes up, or when the application itself decides to give up.

What matters is that it never ends in between. It always lands on either commit or rollback, which is why the half-finished state of "A went down but B never went up" cannot be left behind.

The properties asked of a transaction are known by their initials as ACID. Learn them as a set of four.

• Atomicity … either it all runs or it is all undone. It cannot be divided further
• Consistency … the rules you set (primary keys, constraints) are never left broken
• Isolation … what is going on inside is invisible to other transactions. They do not affect each other
• Durability … once committed, the result survives even if a failure follows

The transfer story is atomicity itself, since that is the property that refuses to allow "only one half".

After it starts, a transaction passes through several states. Get the names down.

• Active … running. Nothing settled yet
• Committing → committed … heading for final, then final
• Aborting → aborted … heading for undone, then undone

What is worth noticing is that some directions are possible and others are not. If a failure strikes while committing, it can turn back from there into aborting.

But you cannot go from aborting back to committing. Once it has been decided to undo and the winding back has begun, it cannot switch to being made final partway through.

The other worry is two people touching the same row at the same time.

There are 1000 items in stock. A adds 500 and B adds 300. Done one after the other, that should be 1800.

But if both read the same 1000 before calculating, A writes 1500 and B writes 1300. Whoever writes last wins, and the result is 1300. A 500 has disappeared.

This is called a lost update. Both transactions did the right thing by their own lights, and the result only goes wrong at the moment they overlap. Which is why you need a way to put them in order so they do not overlap.

The tool for putting things in order is the lock, and the whole arrangement is called exclusive control.

There are two kinds. A shared lock (S) is taken when reading; an exclusive lock (X) is taken when writing.

Whether two can hold at once is their compatibility. There is only one thing to learn.

• Readers can coexist. Two shared locks can both be taken
• Once a writer is involved it becomes exclusive. An exclusive lock cannot be taken alongside either a shared or an exclusive lock

The reason follows from thinking about it. Reading alone never changes the value, however many are doing it. But mix in a rewrite and the value may change mid-read, or what was written may be overwritten.

You get to choose how wide a lock reaches. That width is its granularity. You can lock one row, or you can lock a whole table.

Make the granularity coarser (table level) and one lock covers a wide area, so there are fewer of them to manage. But in exchange other transactions wait more often and overall throughput drops.

Make it finer (row level) and anybody touching a different row carries on without waiting, so more can run at once. On the other hand the number of locks grows, and the DBMS uses more memory to keep track of them.

So it is a trade between waiting time and management cost. Neither end is simply better.

Having introduced locks, a different kind of jam now appears.

A locks account 1 and B locks account 2. Next, A wants account 2 and B wants account 1. Each waits for the other to let go, so nothing ever moves again. That is deadlock.

Keep it apart from ordinary waiting. If one side merely waits over a single resource, its turn comes when the first party commits, so nothing is stuck. Deadlock is the state where each demands the lock the other holds and the waiting has closed into a ring.

There are several ways to avoid it, the simplest being for everybody to take locks in the same order. Decide that the lower-numbered account is always locked first and no ring can form. On its side the DBMS detects the ring and forces one of them to roll back.

From here on we are talking about after the breakage. To come back from a failure you need a record of what was changed and how. That is the log file (journal).

What gets recorded is both the before and the after of a value. The before image is the value before the change and the after image is the value after it. Having the before lets you wind back; having the after lets you redo.

Do not mix it up with a word that looks similar. A backup is a whole copy of the database contents and is something else entirely. When the medium (the disk) fails, you recover using both the backup and the log.

One more thing to hold on to is the checkpoint. Now and then the DBMS writes the updates held in memory out to disk together and leaves a mark saying everything up to here is safe. On recovery you only have to look at the log beyond the most recent mark, which cuts the reading down enormously. It is a mark for making recovery fast, not a substitute for the log.

Putting things back has two directions, and which one you use depends on whether the transaction had finished when the failure struck.

If it had not finished, it is half done and you want it gone. Use the before images to wind back to the state just before it started. That is rollback.

If it had finished, it was committed and you want to keep it. But it may not yet have reached the disk. Use the after images to carry it forward once more. That is roll forward.

Back with the before images, forward with the after images. Choices with that pairing swapped are always among the four, so learn the direction and the kind of log together.

In the exam it comes as a question that makes you decide the direction from that checkpoint. "Finished after the checkpoint was taken" means the transaction was committed but may not have reached the disk — hence carry it forward.

Last, speed. An index is an arrangement that keeps, separately, the values of a column paired with where those rows are.

Without an index the DBMS looks at each row from the top and checks whether it matches — a million times over a million rows. With an index the values are sorted into the shape of a tree, so a handful of steps is enough. It is the same idea as looking a term up in the index at the back of a book.

The tree used is a B-tree (B+ tree). It branches widely and is short, so the root reaches a leaf in a few levels. Because branches are chosen by comparing values, it works not only for = but also for range searches and prefix matches.

There is also the hash index. It computes the value to settle a location in one shot, so equality is at its fastest, but it holds no ordering and so cannot serve a range search. Learn it as: hash for pinpointing an ID, B-tree for everything else.

An index is not a cure-all. There are places where adding one makes things slower, so get those down.

First, the index has to be corrected on every update. Put many of them on a table with a lot of INSERT and UPDATE and writing gets heavy.

Second, it does nothing for a column with few distinct values. Consult an index on a column such as gender, with only two values, and half the rows match anyway, which is no different from reading them all.

A table with few rows is the same. At a few dozen rows, reading them all is faster.

And an index goes unused if you transform the column. Pass it through a function or a calculation inside the condition and it can no longer be matched against the values that were sorted.

Think of an index as a trade: you hand over writing speed and space in order to buy reading speed.