Inside a Database

A bit is the smallest thing a computer can hold: one yes or no, written as 1 or 0. Eight bits standing together are called a byte. Eight yes-or-no answers can be arranged in 256 different patterns, so one byte can stand for a whole number from 0 to 255, or for a single letter of English text.

A file is a long line of bytes with a length. There is byte number 0, then byte number 1, and so on to the end. That position, counted from the start, is called an offset. Almost everything in this course comes back to one question: which offset do I jump to.

Every column is declared with a type: the kind of value it is allowed to hold. A whole number, a piece of text of at most so many letters, a date. The type is what lets the engine decide how many bytes the column needs and how to compare two of them.

The type matters for sorting more than for storage. The text"100" comes before the text"99", because "1" comes before"9" in the alphabet of characters. The number 100 comes after the number 99. If the engine did not know which one it had, it could not put a column in order, and the whole of Part 2 depends on being able to do exactly that.

Seconds depend on which machine you are sitting at, what else it is doing, and how warm the disk is. A count of work does not. So the widgets here count the thing the engine actually does: rows compared, and later pages read. Those numbers are the same on your laptop and on a server in a rack.

This kind of counting has a name. When people say one approach is faster than another, what they usually mean is that the count grows more slowly as the data grows. A full scan of a table twice the size does twice the work, every time, on every machine.

In Step 1,"row number 5" was a position counted from the start. Programmers call that position an index too, and you will hear "the index of that item" all the time. That meaning is not going away.

From here on, though, index mostly means the other thing: the sort of index at the back of a book. A separate, small, sorted list that says "this value is at that place", kept beside the real data so you can find a page without reading the book. When this course says "add an index on customer", it means build one of those. Both meanings are standard, and the sentence around the word always tells you which one is meant.

Because a table can only be kept in one order at a time, and because keeping it in that order costs something on every insert. A new order with id 34,982 belongs after 34,981. If the file is sorted, everything after it has to shift along to make room, and shifting 20,000 rows to insert one is a poor trade.

Steps 3 and 4 are about the structure that gets around this. It keeps values in order without ever shifting a whole file, and it charges a small, fixed fee per insert instead. You can safely skip this note: the next step arrives at the same place by a different road.

Because finding the data is the expensive part and copying it is not. A spinning disk has to move an arm and wait for the platter to come round, which takes milliseconds. Once the head is there, streaming the next few thousand bytes costs almost nothing extra. A solid state drive has no arm, but it is built from cells that are erased and written in blocks, so it has the same shape of cost for its own reasons.

The operating system settled on a page as the unit for the same reason, and keeps recently used pages in memory in case you want them again. Everything above the hardware, including this course, therefore counts in pages. A design that reads three pages beats a design that reads thirty, even if the second one does fewer comparisons.

A tree here is a set of boxes joined by arrows that always point downward and never loop back. Each box is a node. The one at the top with nothing above it is the root. The boxes at the bottom with nothing below them are leaves. A box directly below another is its child.

Depth is how many boxes you pass through going from the root to a leaf. In a B-tree one node is one page, so the depth is exactly the number of page reads a lookup costs. That single sentence is why the rest of this step is about making trees shorter.

In the design shown here, and in most real ones, the actual rows sit in the bottom row of nodes and nowhere else. The nodes above hold only keys and arrows: signposts, not data. That is why the upper nodes can pack in so many keys, and why the tree stays short.

A separate index works the same way, except the bottom nodes hold the key and the place to find the row, instead of the row. The lookup then costs the depth of the index, plus one more page read to go and fetch the row itself. Step 6 gets a lot of use out of that extra read.

The engine performs a split. It takes the full page, hands out roughly half the keys to a brand new page, and then tells the parent about the new page by inserting one separator key. So one insert has turned into three page writes rather than one: the old page, the new page and the parent.

The catch is that the parent can now be full too, which splits it, which tells its parent. In the worst case a single insert splits every level up to the root, and the root splitting is the only way a B-tree ever gets deeper. It grows from the top, not the bottom, which is exactly why every leaf stays the same distance from the root.

No, and the arithmetic says why. A page holding 100 keys splits about once every 50 inserts, because after a split each half has room for 50 more. So the extra writes are spread across 50 cheap inserts, which works out at well under one extra write each on average.

Splits are only a problem when they are constant, and there is one shape that causes exactly that: keys arriving in increasing order, which is what an auto-numbered id column does. Every insert lands in the last page, so that one page splits over and over while the others sit half empty. Real engines special-case this by cutting the last page unevenly instead of down the middle.

They measure. Every serious database can report how many times each index has actually been used since it was last restarted, and dropping the ones with a count of zero is one of the quickest improvements available. It is common to find indexes added years ago for a screen that no longer exists.

The other half of the job is looking at the slow queries and asking which index would have helped. Step 13 is that job, in miniature, with the costs counted for you. Safe to skip until then.

Because a customer who moves house should move house once. If the address is copied onto all 300 of their past orders, then changing it means finding and rewriting 300 rows, and if you miss one the database now holds two different truths. Storing each fact in exactly one place is the single most useful habit in database design.

The price is that answering a question now needs two tables instead of one. That price is the join, and the rest of this step is about how much it costs and how to make it cost less.

Imagine a row of numbered buckets. To file a customer, run their id through a small fixed sum that turns any value into a bucket number, and drop them in that bucket. That sum is called a hash. To find them again, run the same sum, go to that one bucket, and look through the handful of items there. You never look in any other bucket.

So a hash table finds things in a roughly fixed number of steps no matter how many items it holds, which is better than a tree. What it cannot do is answer "give me everything between 100 and 200", since the hash scatters neighbouring values into unrelated buckets on purpose. Trees keep order, hashes throw it away for speed. Both exist because both trades are sometimes right.

Because when one side is tiny, the multiplication is tiny too. Joining 5 rows to 5 million with a hash join means building a table of 5 million buckets first. The nested loop skips that entirely and does 5 lookups. Engines choose it constantly for small inputs.

And there is a second reason, which Lab 10 is about. If the inner table has an index on the joining column, the nested loop stops scanning the inner table and starts doing a tree lookup instead. That turns the worst plan into one of the best ones without changing the plan's name.

Think of a paper phone book. Finding Perera takes seconds, because the book is ordered by the first letter, then the second, then the third. Now find everyone whose name ends in "era". The book gives you nothing. You read all of it.

Nothing about a computer changes this. A database index is that same book. Any condition that pins down the start of the value can use it. Any condition that only describes the middle or the end cannot, and no amount of hardware fixes that, because the ordering it needs was never built.

Selectivity is just the share of the table a condition keeps. Asking for one exact id out of 10,000 rows is very selective: it keeps 0.01 percent. Asking for orders whose status is not cancelled might keep 95 percent, which is barely selective at all.

This one number decides more query plans than anything else, and it is why the engine keeps rough statistics about your data. It has to guess how many rows a condition will keep before it runs it. When those statistics go stale, the engine guesses badly and a query that ran in a blink starts taking a minute, with no code having changed.

Yes, by storing something else. Build a second index on the name spelled backwards, and "ends with era" becomes "starts with are" on that index, which is a jump. Some engines will do this for you if you ask for an index on a calculation rather than on a column.

The general lesson is worth more than the trick. When a question cannot be answered quickly, the fix is almost never a faster machine. It is storing a different arrangement of the same data, chosen so that the question you keep asking becomes a jump. That is what every index in this course has been.

A machine has two kinds of storage. Memory is fast and forgets everything the instant the power goes. Disk is slow and remembers. A running program keeps almost everything in memory, and writes to disk only when it decides to.

So "the power went off" means precisely this: everything in memory is gone, and whatever had already reached the disk is still there. The trouble is that the program does not get to choose the moment. The cut lands wherever it lands, including exactly halfway through a job that only makes sense whole.

Not really. The two rows are in different places on the disk, so they are two separate operations down at the hardware, and something can always happen between them. Even if they landed in the same page, a page write can be interrupted partway and leave half-old, half-new bytes behind, which is worse than either outcome.

So the answer cannot be "make the gap small". It has to be "make the gap survivable". That means writing down what you intend to do, somewhere that survives, before you start doing it, which is Step 8 in one sentence.

They are the four promises a transaction makes, and each one has a step of this course behind it. A is atomic: all of it happens or none of it does, which is this step. C is consistent: the invariants that held before still hold after. I is isolated: two transactions running at once do not see each other half done, which is Steps 9 to 11.

D is durable: once you are told it committed, it survives a power cut, which is Steps 8 and 12. The word is used loosely in marketing, so it is worth being able to ask which of the four letters somebody actually means.

Ten rows changed by a transaction may live in ten different pages, scattered across the disk. Writing them means ten trips. Writing ten log records means one trip, because they all go to the same place: the end of the log, which the disk head is already sitting on.

So the engine gets to be safe immediately and tidy later. The moment the log record is on disk the transaction can be declared committed, and the real pages can be written whenever it suits, in a batch, in a sensible order. Being allowed to be late is what makes it fast.

It would, so the engine takes a checkpoint now and then: it writes all the changed pages out to the data file properly, then records in the log that it has done so. Everything before that point is now safely in the data file, so those log records can be thrown away.

Checkpoints are also what keeps recovery short. Without one, coming back from a crash would mean replaying the log from the day the database was created. With one, it means replaying from the last checkpoint, which is usually seconds of work. The cost is a burst of disk writes each time, which is why a database can feel briefly slower every few minutes.

Five small things: which transaction, which row, which column, the value before, and the value after. The value after is what recovery uses to redo committed work. The value before is what a rollback uses to undo work that was abandoned, whether the abandoning was your choice or a crash's.

That is why a log is much smaller than the data it protects, and why it can be written in one place while the rows it describes are scattered. A record is a sentence about a change, not a copy of the page.

Usually it does not mean two things happening in the same instant. It means the machine is switching between them, running a bit of one, then a bit of the other, over and over, far too fast to see. That switching back and forth is called interleaving, and the order it produces is different every time.

Which is why this class of bug is so unpleasant. In the tiny six-step model below, nearly every overlapping order is wrong because the read-to-write gap takes up most of each transaction. A real transaction may do thousands of unrelated steps around a much smaller dangerous gap, so the overlap can be rare. Rare does not mean safe: enough traffic eventually finds every possible order.

There is a clean definition and it is worth learning. An outcome is correct if it matches what you would have got by running the transactions one after another, in some order, with no overlap at all. That is called a serial order.

Notice it does not say which order. Charge then refund gives 480, and refund then charge gives 480 as well. Either is acceptable. What is not acceptable is 530 or 450, because no ordering of the two whole transactions produces those. A schedule that gives the same answer as some serial order is called serializable, and that word is the goal of the next two steps.

A web page keeps a counter of how many times it has been viewed. Each visit reads the counter, adds one, writes it back. Exactly the shape from this step. Two visits landing together lose a count, and nobody notices, because nobody knows what the true number was.

This is worth holding on to, because it shows why the bug survives. With money somebody eventually complains. With counters, likes, stock levels and "number of retries so far", the number is simply a little bit wrong forever, and the wrongness grows with traffic.

Locking every row against everybody would be far too strict. Two transactions that only want to read the same row cannot possibly upset each other, so they are allowed to hold the row together. That is a shared lock, and any number of transactions can hold one at once.

A transaction that means to write needs an exclusive lock, which cannot be held alongside anything else, shared or exclusive. So the rule is short: readers do not block readers, and everything else waits. Most database tuning arguments are about how long an exclusive lock is held.

It keeps a small picture called a wait-for graph: an arrow from each waiting transaction to the one it is waiting on. A deadlock is exactly a loop in that picture, and looking for a loop is quick, so the engine checks every second or so.

When it finds one, there is no polite option. It picks one transaction, calls it the victim, rolls it back completely and releases its locks, which frees everybody else. The victim gets an error saying it was chosen. Well-written software catches that error and simply tries the whole transaction again, and the second attempt almost always succeeds.

You can, and it is correct. It is what some small engines do. The cost is that only one transaction can work on the table at a time, so a shop with a hundred cashiers becomes a shop with one. Locking a single row instead lets the other ninety-nine carry on.

The choice of how big a thing to lock is called granularity, and it is a trade like every other one here. Fine locks allow more work at once but need a bigger lock table and more checking. Engines usually lock rows, and quietly promote to a table lock when one transaction has taken so many row locks that tracking them costs more than the parallel work is worth. Safe to skip.

A dirty read is reading a value another transaction has written but not committed. If that transaction then rolls back, you acted on a number that never existed. A non-repeatable read is reading the same row twice in one transaction and getting two different values, because somebody committed a change in between.

A phantom is the same problem for a group rather than a row. You count the orders from Kandy and get 12. Somebody inserts a new Kandy order and commits. You count again and get 13, inside the same transaction. No row you read has changed. A new one appeared.

Because for a lot of questions the wrong answer does not matter. A dashboard showing roughly how many orders came in today does not need to be exact, and making it exact might mean blocking the checkout for everybody while it counts. Read committed, which most databases use by default, is the common compromise.

The mistake is not choosing a weak level. The mistake is choosing one without knowing which anomalies it lets through, and then being surprised. Money movement, stock counts and anything with a uniqueness rule usually deserve the strictest setting, which is why Lab 22 asks you to learn the table rather than look it up.

Locks are not the only mechanism. Most modern engines keep several versions of each row, each stamped with the transaction that made it. A reader is given the version that was current when its transaction began, and it keeps reading that version to the end. Writers make new versions rather than overwriting, so a reader never has to wait for a writer.

This is why a report can run for ten minutes on a busy database without freezing anybody, and why old versions have to be cleaned up afterwards by a background job. It changes how the levels are implemented, not what they permit, so the table in Lab 22 still holds.

First the program's own buffer, in its own memory. Then the operating system's buffer, still in memory, because writing to a file usually just hands the bytes to the system and returns immediately. Then the drive's own small buffer, which is on the drive but still electric. Only then the actual storage that survives a power cut.

Each handover has its own instruction. Emptying the program's buffer into the system is a flush. Telling the system to push everything down to the drive and not return until the drive says it is safe is called fsync. A commit that has not run fsync has not really committed, whatever it reported to the user.

Because it is the one operation that cannot be batched away or answered from memory. It has to wait for physics: for a platter to come round, or for a flash cell to be programmed. On a spinning disk that is several milliseconds, which sounds small until you notice a busy shop wants to commit a thousand transactions a second.

That single number sets the ceiling on how many transactions a database can commit per second, and no amount of processor speed moves it. Which is why the trick in Lab 24 exists, and why it is one of the most valuable ideas in the whole field.

Then durability, as defined here, has nothing to say. Everything in this step is about surviving a power cut on a working drive. A drive that stops existing takes its log and its data file with it, and no amount of fsync helps.

That is a different promise, and it is bought differently: by keeping copies somewhere else. A backup taken nightly, or a second machine receiving the log records as they are written and applying them as they arrive. The second one is a whole course of its own, because the network between the two machines is allowed to drop things. Safe to skip for now.

The operating system also caches files, but it does not know which database pages are pinned or which ones are expensive to rebuild. A database pool can keep an index root hot, schedule dirty writes and report its own hit rate. Some engines use direct I/O; others cooperate with the operating-system cache.

Two caches can mean the same page occupies memory twice. One cache can mean less control. There is no universal choice. Engineers measure the workload and the storage system before changing it.

A composite B-tree on (customer, created_at) is ordered by customer first, then time within one customer. It can jump to one customer's recent orders. Reversing the columns answers a different question. This is the left-prefix rule from Step 6 applied to more than one column.

A partial index stores only rows matching a condition, such as unpaid orders. A covering index includes the columns a query returns, so the engine may answer from the index without visiting the heap. Both save reads, but both add write work and storage.

An embedding records patterns learned from training data. Two passages can be nearby and still disagree. A retrieved passage can be outdated or malicious. Similarity search finds candidates; it does not verify their claims.

Production retrieval usually combines vector similarity with ordinary filters, keyword ranking, access control and citations. Keep the original source text and its permissions beside the vector.

A fixed-size transaction id eventually wraps around. An engine must mark sufficiently old committed versions as permanently visible before that happens. PostgreSQL calls this freezing and performs it as part of vacuum work.

This is why cleanup is part of correctness, not just disk housekeeping. Monitor age limits and vacuum progress before they become an emergency.

A unique, foreign-key or check constraint is enforced for every writer, including scripts and future services. A check in application code protects only paths that remember to call it.

Cross-row rules are harder to express as simple constraints. For those, document the chosen lock or serializable pattern and test concurrent schedules rather than only single requests.

Recovery itself can crash. When undo reverses a change, it records that action in a compensation log record. A second recovery can see which undo work was already completed and continue safely.

This analysis-redo-undo shape is associated with ARIES. Engines differ in record format and detail, but the questions stay useful: where does recovery start, what is safe to repeat, and how is interrupted recovery resumed?

A checksum detects accidental byte changes. Encryption limits who can understand stored bytes. Authentication detects deliberate modification by someone without the key. ECC memory can correct some bit errors before the database sees them.

A careful system may use all four. Naming the failure first prevents one mechanism being credited with a guarantee it does not provide.

Record the backup chosen, every WAL segment used, checksum results, start and finish times, and the application checks run afterwards. Restore into an isolated destination so the drill cannot overwrite the source.

Test operator access too. A backup that only one unavailable person can decrypt or locate does not meet a recovery objective.

Build a Query Engine covers parsing, relational algebra, cardinality estimates and plan search. Distributed Consistency covers histories, replicas and clocks. Raft and Consensus covers an ordered replicated log and membership changes.

Security engineering adds threat models, least privilege, secret handling and incident response. Database permissions, encrypted connections and audit logs should be designed with those tools rather than treated as a final checkbox.

One unit is one page touched: read into memory, or written back out. It is the standard way engines compare plans, because a page is the unit the hardware works in and because the count is the same on every machine.

Real planners weight the two differently, since a write is dearer than a read, and they add a small charge for the processor work of comparing rows. Those refinements change the numbers by tens of percent and change the answers hardly at all, so this lab counts pages plainly and says so.

The language almost every database speaks is called SQL, and the parts this course has been doing by hand are four short commands. Nothing below is needed to finish the lab, but you will meet it within a day of touching a real system.

SELECT id, total FROM orders WHERE customer = 412;
CREATE INDEX orders_customer ON orders (customer);
EXPLAIN SELECT id, total FROM orders WHERE customer = 412;
DROP INDEX orders_customer;

The third one is the interesting command. EXPLAIN does not run the query. It asks the planner to print the plan it would use, including whether it intends to use an index or scan the table, and it is how every one of the problems in Step 6 gets diagnosed in real life.

It estimates. For each way of running the query it works out a cost from statistics it keeps about your tables: roughly how many rows there are, how many distinct values a column holds, how the values are spread. Then it picks the cheapest estimate and runs that. It never measures the real thing first, because measuring would cost more than the query.

Which explains the most confusing kind of database problem there is. The statistics go stale, the estimate becomes wrong, the planner picks a bad plan, and a query that ran in a blink for a year starts taking a minute with nothing in your code having changed. The command to refresh those statistics is usually the first thing to reach for.