Describe the phases an ARIES-style recovery process runs through when a relational database restarts after a crash, and what each phase accomplishes.

## Setting: what the crash destroyed While running, the engine holds in memory (a) the buffer pool of cached pages, some of them dirty, (b) a table of active transactions, and (c) a table of which cached pages are dirty and since when. A crash wipes all three. What survives is the transaction log on durable storage plus the data files, which are a partial, inconsistent snapshot: some committed changes are missing from them, some uncommitted changes are present in them. Every log record carries a monotonically increasing **log sequence number (LSN)**, and every data page stores the LSN of the most recent change applied to it (the page LSN). Those two facts drive the whole algorithm. ## Pass 1: analysis Analysis starts at the most recent checkpoint record and reads forward to the physical end of the log. A checkpoint record is essentially a memo the running system wrote about itself: which transactions were active and which pages were dirty at that moment. Analysis loads that memo, then replays the log forward to bring it up to date: transaction start records add entries, commit and end records remove them, update records add pages to the dirty page table if not already present, recording the **recLSN**, the LSN of the first log record that dirtied that page since it was last written to disk. Analysis outputs three things: the set of losers (transactions still active at the end of the log with no commit record), the reconstructed dirty page table, and the **redo start point**, which is the minimum recLSN over the dirty page table. Any change older than that point is guaranteed already in the data files, so redo can safely skip it. Note this start point is typically *earlier* than the checkpoint itself, because a page could have been dirtied long before the checkpoint and still not written. Analysis changes no data; it only rebuilds bookkeeping. ## Pass 2: redo Redo scans the log forward from the redo start point and, for each redoable record, decides whether to apply it. It skips the record quickly if the page is absent from the dirty page table, if the record's LSN is below that page's recLSN, or, after fetching the page, if the page's stored LSN is already at or above the record's LSN, meaning the change is already there. Otherwise it applies the change and stamps the page LSN with the record's LSN. Because the decision is driven by comparing LSNs, redo is idempotent: crashing and re-running it produces the same result. The defining property is that redo **repeats history**: it reapplies changes made by losers too, not just by committed transactions. After redo, the pages look exactly as they did at the instant of the crash, uncommitted garbage included. That is deliberate, because it means undo faces a state it can reason about with ordinary rollback logic instead of a special case. ## Pass 3: undo Undo removes the losers. It processes their log records backwards, in reverse LSN order across all losers at once, following each record's *previous LSN* pointer to walk each transaction's own chain. For each update it applies the before-image and writes a **compensation log record (CLR)** describing the reversal. A CLR carries an *undo-next* pointer to the record that should be undone after it, so if the server crashes during undo, the restarted recovery finds the CLR, knows that step is done, and continues from where it stopped instead of undoing anything twice. CLRs are redo-only and are never undone. When a loser's chain is exhausted, an end record is written for it. When all losers are done, the database is transactionally consistent and opens for connections. ## Why this order Redo before undo is not arbitrary. Undo needs a well-defined starting state, and the only well-defined state available is the state at the moment of the crash, which is what redo reconstructs. Attempting selective redo of winners only would leave the pages in a state that matches no point in real history, and the before-images recorded in the log would no longer line up with what is on the page. ## Practical notes Recovery cost is dominated by redo, whose length is set by how far the dirty page table's oldest recLSN is behind the end of the log, which in turn is set by checkpoint frequency and background page-writing aggressiveness. Some engines run undo concurrently with normal operation, opening the database once redo has finished and letting the surviving locks (rebuilt by analysis) keep other sessions off the rows still being rolled back.