Statement Versus Row-Based Logs: Determinism and the Cost of Replay

The smallest possible replication stream is the text of the statement that ran. One UPDATE that touches a million rows becomes a few dozen bytes on the wire. The largest is a full copy of every row the statement changed. Between those two extremes sits the entire design space of log formats, and the choice is not about efficiency alone: a statement log is only correct if the statement has the same effect on every replica, and a great many ordinary statements do not.

A statement log assumes the replica is the leader

Take the simplest nondeterministic statement: UPDATE queue SET state = 'claimed', owner = 7 WHERE state = 'pending' LIMIT 1. On the leader the planner picks one row, using whatever index it chose, in whatever physical order the heap happens to present. On a replica with identical logical data but a different physical layout, a different index, or a different planner cost model, the same statement may pick a different row. Both servers run a correct transaction, both remain internally consistent, and the two databases now disagree permanently.

This is the central problem. A statement log records an intent, and the mapping from intent to effect is a function of the server’s state and configuration. Replication is only correct when that function is the same everywhere.

The usual enumeration of hazards is short and unpleasant:

• LIMIT without ORDER BY, as above, or ORDER BY over a non-unique column where ties are broken arbitrarily.
• NOW(), CURRENT_TIMESTAMP, RANDOM(), or any function that reads the clock or a random source. The leader evaluates it once; the replica evaluates it at replay time, which is later by definition.
• Auto-increment and sequence allocation. If the replica allocates its own identifier, the two servers diverge on the very next insert, and every foreign key derived from it diverges with them.
• User-defined functions and triggers that read tables other than the ones the statement nominally touched, or read files, or call out to a service.
• INSERT ... SELECT over tables that have diverged for any of the above reasons, which propagates one divergence into every subsequent statement.
• Updates to tables whose row order differs, combined with any statement whose result depends on that order.

MySQL’s statement-based format, the original binary log format, carries an explicit list of such constructs that it treats as unsafe. It marks them in the log and can refuse to log them under a strict setting. The list exists because the format cannot fix the problem; it can only detect some instances of it.

There is a subtler failure that has nothing to do with SQL semantics. Statement logging requires locks to be held longer than execution: MySQL takes metadata locks around statements so that a concurrent DDL on the leader cannot change the meaning of a statement that a replica has not yet replayed. A replica that is minutes behind can therefore block the leader’s own DDL. This coupling between replication lag and lock duration is a direct cost of shipping intents instead of effects.

Row images and what they cost

A row-based log records the before-image and after-image of each changed row: the primary key, the changed columns’ old values, and their new values. The replica applies those values directly. There is no expression to evaluate, so the clock, the random source, the planner, and the row order are all irrelevant. The apply step is a set of keyed writes.

The cost is proportional to the rows changed, not the statements issued. A bulk UPDATE over a million rows becomes a million change records; the statement format would have carried one. Each record carries per-row overhead: a header with table identifier and record length, the primary key columns, and both images. For a table with an 8-byte key and a 200-byte row, a full before-and-after image is roughly 400 bytes of payload plus the header, so a million-row update is on the order of hundreds of megabytes on the wire where the statement log was under a hundred bytes.

Most row-based formats avoid shipping unchanged columns in the after-image, and some omit the before-image when the primary key is unchanged and no uniqueness conflict is possible. The savings are real but bounded: the key and the changed columns are always present, and the header is per record, not per statement. Write amplification on the replica rises with the number of records, since each one is an indexed write.

Applying a row image also raises a question the statement format never has to ask: what if the row is not there? A row-based replica must handle three cases per record — the row exists and matches the before-image, the row exists and does not match, or the row is absent entirely. The first is the normal path. The second indicates divergence and is either an error or a silently accepted overwrite depending on the setting. The third happens with an INSERT whose key already exists, which is an ordinary conflict in multi-leader topologies and a genuine error in single-leader ones.

-- The statement format ships this:
UPDATE accounts SET balance = balance - 100 WHERE id = 42;

-- The row format ships something closer to this, once per changed row:
--   before: id=42, balance=500
--   after:  id=42, balance=400

The second is longer, and it is the one that replays identically on any server holding the same rows.

Mixed formats and the switch that costs correctness

MySQL exposes the choice as a per-session variable, and its default mode logs most statements as statements and switches to row format for statements the server judges unsafe. The switch is a compromise: it keeps the compact format for the bulk of the workload and pays the row-image cost only where determinism fails.

The compromise has two gaps. The first is that the safety judgement is a heuristic over syntax and context, so a statement that is nondeterministic for a reason the check does not model still ships as a statement. The second is that the mode is chosen on the leader, and the replica applies whatever arrives; a replica cannot re-derive the decision. Changing the mode mid-stream is therefore possible but makes the log a mixture whose semantics depend on per-record headers.

PostgreSQL takes a different route and does not offer statement-level replication at all in its streaming path. Its physical replication ships page-level WAL records, which are even more tightly coupled to the sender than row images are, and its logical decoding path reconstructs row-level changes from WAL for consumers. The design consequence is that a physical standby must run the same major version and the same page layout, while a logical subscriber can run a different version and receive a filtered subset of tables.

Choosing between them

The decision reduces to three axes.

Determinism. Row and physical formats are correct by construction for arbitrary SQL; statement formats are correct only for a restricted workload. If the application cannot be audited for every hazard above, the statement format is a standing risk, and the risk is not a performance risk but a silent divergence that surfaces much later as a wrong number in a report.

Volume. Statement logs win when one statement changes many rows and the statement text is short relative to the data. Bulk backfills, mass updates, and INSERT ... SELECT of large sets are the cases where the difference is orders of magnitude. Row logs win when statements change few rows but carry long text, since a single-row update with a two-kilobyte query string costs more as a statement than as an image.

Consumer. A statement stream is legible to a human and to a SQL parser; it can be replayed into a different schema with care, and it can be filtered by statement text. A row stream is legible to a replication applier and to change-data-capture consumers that care about values, but it cannot be edited or reordered without destroying its meaning. Neither is a substitute for the other when the consumer is a different system with its own schema.

The cost asymmetry in the other direction matters too: a statement log makes the replica do the leader’s work again. Every index maintenance, every constraint check, every trigger fires a second time on the replica. A row image skips the planning and the expression evaluation but still performs the indexed write. On a replica that is already behind, the statement format’s extra work per record extends the lag, which is why bulk statement replication is often the slowest path in practice even though it is the smallest on the wire.

Where both formats still fail

Neither format solves the ordering problem described in the replication log as ordering unit. Both are streams whose order must be preserved, and a consumer that applies records out of order corrupts the state regardless of format.

Neither solves schema change. A row image names columns by position or by internal identifier, so a replica whose table has a different column order, or an extra column added by a local DDL, applies the image against the wrong slots unless the format carries enough metadata to map them. Statement logs have the opposite failure: a statement written against the old schema may be invalid against the new one, and a statement written against the new schema cannot run on a replica still at the old one. Both formats therefore require the schema change itself to be replicated in the same stream and in the same order, which is why DDL replication is a separate and often later feature than data replication.

The third shared failure is the conflict case. Both formats assume that the record describes a change that the replica’s state permits. In a single-leader topology that assumption holds because the replica only ever sees the leader’s order. In any topology where two nodes can write the same row, the apply step must resolve a conflict, and a format that carries only “this is what happened” leaves no information for the resolution. Leader failover is where that assumption is tested, and the log format determines how much can be recovered when it fails.