Course contents
On this page
Notation, models, and numerical conventions
Notation, models, and numerical conventions: supporting material for the Database Engineering course.
This guide fixes the interpretation of the course’s equations, histories, code fragments, and numerical examples. A calculation is useful only when its units, boundary, and assumptions match the question being asked.
Units
Time uses seconds (s), milliseconds (ms), microseconds (µs or us), and nanoseconds (ns). One second is 1,000 milliseconds, one millisecond is 1,000 microseconds, and one microsecond is 1,000 nanoseconds. The lesson converts values before multiplying rates by durations.
Decimal storage units use powers of 1,000: KB = 1,000 bytes, MB = 1,000,000 bytes, GB = 1,000,000,000 bytes, and TB = 1,000,000,000,000 bytes. Binary units use powers of 1,024: KiB = 1,024 bytes, MiB = 1,048,576 bytes, and GiB = 1,073,741,824 bytes. A byte has eight bits. A link rate in Gbit/s must therefore be converted before comparing it with MB/s.
An illustrative 1 Gbit/s link provides 125 MB/s before protocol and implementation overhead. It does not provide 1 GB/s. Copying 12 MiB at 12 GiB/s takes 1/1024 s, approximately 0.977 ms. Dividing 12 by 12 without accounting for the different prefixes would give the wrong answer by a factor of 1,024.
Counts are dimensionless but their meaning is named: client connections, request attempts, transactions, rows, pages, replicas, and deliveries. The notation never treats them as interchangeable simply because each is a count.
Observation boundaries
An end-to-end request begins and ends at a stated application boundary. Engine execution begins later and can end before durable acknowledgment or response delivery. Connection-pool wait, admission wait, locks, I/O, replication, output, and rendering may fall inside or outside a particular measurement.
When a lesson says an operation costs 40 microseconds of CPU, it refers to execution demand, not necessarily 40 microseconds of elapsed response time. At 80,000 operations/s, that demand is 3.2 CPU-seconds/s. Real capacity also needs headroom and must account for other resources and parallelization limits.
An acknowledgment is always tied to a guarantee. Received bytes, appended log records, locally durable records, replicated decisions, applied state, and delivered client updates are different boundaries. A watermark is meaningful only after identifying which kind of progress it represents.
Queueing notation
λ denotes an arrival or completion rate over a consistently defined stable-system boundary. W is mean residence time inside that boundary. L is mean work in flight. Little’s Law is:
L = λ × WFor 20,000 operations/s and 0.005 s residence, L = 100 operations. This does not imply one hundred worker threads. Many operations can wait asynchronously. It also does not establish a stable operating point if the queue is growing without bound.
μ denotes service rate in the elementary M/M/1 model. Under that model’s Poisson arrival, exponential service, single-server, and stability assumptions:
mean response time = 1 / (μ - λ), with λ < μThis expression predicts a mean under a particular idealized model. It is not a p99 formula and should not be applied as an exact description of every database. Bursts, heavy tails, locks, parallel workers, and correlated delays can violate its assumptions.
ρ denotes utilization in an explicitly stated model. A utilization figure needs a resource and scope: one execution core, one shard, a device, or the whole cluster. Averaging across resources can hide the saturated component.
Parallel speedup
For fixed work with serial fraction f and ideal parallel worker count p, Amdahl’s Law gives:
ideal speedup = 1 / (f + (1 - f) / p)The model excludes additional coordination cost. An implementation can perform worse than the bound because parallel work adds communication, memory traffic, or scheduling. Reorganizing the computation can change f; adding workers alone does not.
The number of clients is not automatically p. Client concurrency creates offered and retained work; only independent runnable work can use parallel execution resources. A single exclusive state transition remains a separate constraint.
Probability examples
Probability calculations state independence assumptions explicitly. If each of 100 independent subrequests has a 1% probability of exceeding a threshold, the chance at least one exceeds it is:
1 - (1 - 0.01)^100 ≈ 0.634Real distributed delays can be correlated. The calculation illustrates fan-out sensitivity; it does not forecast a named service’s tail. Likewise, 1/q expected attempts per success assumes repeated independent attempts with unchanged success probability q. Retries during overload commonly violate that model.
Data-size and amplification calculations
A storage calculation names its boundary. Logical mutation bytes, host device writes, replica aggregate writes, and device-internal flash writes are different quantities. If logical input is 10 MB/s, three replicas each perform equivalent work, and total host write amplification is eight per replica, the illustrative aggregate is 10 × 3 × 8 = 240 MB/s. Network and repair traffic are additional dimensions.
Retention calculations multiply rate, retained size, and time only under stated steady assumptions. At 10,000 updates/s, 200 bytes/version, and 600 s retention, payload is 1.2 GB. Allocation, indexes, compression, and metadata can change actual usage substantially.
Restore-time calculations use effective throughput, not an advertised device peak. A 4 TB transfer at 500 MB/s requires 8,000 s under decimal units, before replay, validation, provisioning, and warming. Parallelism can help only where dependencies and shared resources permit it.
Histories and transactions
T1, T2, and similar labels identify transactions. r1(x) means a read of x by transaction 1; w1(x=v) means its tentative or accepted write as specified by the surrounding text. commit1 and abort1 identify outcomes. Physical persistence may occur at different times and is not inferred merely from a write symbol.
An invocation and response define an operation interval. A timeout leaves an incomplete or uncertain operation unless another protocol establishes its result. Linearizability reasoning respects real-time order between nonoverlapping completed operations. Serializable-transaction reasoning seeks a valid sequential transaction explanation. These are different contracts.
In a dependency graph, an arrow must state its meaning: waits-for, happens-before, reads-from, or a serialization dependency. A cycle has different significance in each graph. The course does not reuse an unlabeled arrow as proof of several unrelated properties.
Logs, timestamps, and generations
LSN or log position identifies a location in an ordered log under the engine’s representation. A transaction identifier is not automatically a commit timestamp. A wall-clock timestamp is not automatically a causal order. A leadership term or epoch identifies authority under a protocol rather than elapsed physical time.
S commonly denotes a snapshot or snapshot boundary. A snapshot at S and a change stream after S must refer to the same authoritative history. Identically formatted numbers from unrelated streams do not create a valid alignment.
N, R, and W in quorum examples denote replica-set size, read-set size, and write-set size for a fixed configuration. R + W > N establishes set intersection, not a complete linearizability proof. Version selection, incomplete writes, durability, and membership remain necessary parts of the protocol.
Algorithm complexity
O(n) and related expressions describe growth under the stated model, not a direct timing comparison. A pointer-heavy logarithmic lookup can pay cache misses; a linear scan over a small compact array can be fast. Expected complexity under good hashing differs from worst-case behavior and from adversarial input.
External-memory algorithms distinguish CPU work from bytes or blocks moved. A sort’s pass count depends on usable memory, buffering, and merge fan-in. A distributed join also pays network exchange and skew. The dominant model should match the resource being studied.
Pseudocode and SQL
Pseudocode is language-neutral and intentionally exposes control flow, state, and ordering. It is not a runnable database implementation. The surrounding prose identifies omitted responsibilities such as framing, authentication, allocation, concurrency, persistence, and cleanup. An omitted responsibility is not optional in production.
SQL uses standard constructs where practical. Product-specific syntax is identified when introduced. Example tables are deliberately small and local to the explanation unless a schema is explicitly carried through a scenario. A statement illustrating guarded mutation does not independently implement authorization, idempotency, or the complete workflow.
Executing SQL to inspect a plan can have effects. EXPLAIN ANALYZE executes its statement in PostgreSQL. A teaching example is not an instruction to run that statement against a live production system. The verification report specifies which illustrative scenarios were checked and which require the named engine.
Diagrams
Diagrams are static explanatory material. Text diagrams and Mermaid source describe topology, state transitions, or dependency paths; they do not assert measured timing unless an explicit scale is shown. A box labeled database can contain several internal services or execution stages. An arrow identifies the relationship described in its caption or adjacent prose.
The manuscript can be published in a Markdown system that renders Mermaid, or those diagrams can be rendered to static images during publication. No quiz, simulator, form, or interactive workbook is required to understand the content.
Evidence labels
Illustrative means a constructed teaching scenario or assumed number. Documented behavior means a statement grounded in the cited implementation documentation and its stated scope. Historical architecture describes a paper or earlier design rather than a promise about every current release. Vendor-reported identifies a measurement or assessment from the supplier. Architectural analysis or inference identifies a conclusion drawn from mechanisms rather than a directly documented company motivation.
These labels prevent an internally correct calculation from being mistaken for an independently measured product result. The course’s purpose is to teach reasoning about mechanisms and tradeoffs, not to manufacture a performance ranking.