Relational Database Internals
From a query to pages and versions
A query asks for rows, but a database has to find pages, decide which row versions are visible, and coordinate concurrent work. An index can reduce the search; a snapshot can keep several reads consistent; a transaction can make several writes succeed or fail together. These mechanisms explain different costs, so adding an index cannot fix every slow query.
SQL queries describe the requested result. Here we connect those plans to storage, statistics, WAL, MVCC, and locks. The Python examples use SQLite in a temporary directory. PostgreSQL mechanisms are explained separately because the implementations and defaults differ. The Python snippets share one database state. Plans, timings, and file sizes depend on the SQLite build, cache state, and hardware.
How a table is stored
A database manages storage in fixed-size pages, commonly 8 KiB in PostgreSQL and 4 KiB in SQLite. PostgreSQL normally stores table rows in an unordered heap, with indexes pointing to row locations. An ordinary SQLite rowid table is itself a B-tree keyed by rowid; it is not a PostgreSQL heap. The sketch below is a heap size estimate: assuming 100 rows per page, 50 million rows need about 500,000 pages, or 4.1 GB before indexes and other overhead.
orders table = file of pages
┌────────── page 0 ──────────┐ ┌────────── page 1 ──────────┐ ┌──── page 2 ────┐ ...
│ hdr │ row │ row │ row │ … │ │ hdr │ row │ row │ row │ … │ │ hdr │ row │ … │
└─────────────────────────────┘ └─────────────────────────────┘ └─────────────────┘
~100 rows per 8 KiB page → a 50-million-row table is ~500,000 pages ≈ 4 GBThe synthetic example contains 100,000 customers and one million orders. page_count × page_size measures the whole database allocation, including both tables, indexes, and free pages; it cannot tell us the average orders per page. amount uses REAL for this synthetic performance example. Exact currency calculations should use an appropriate decimal representation or integer minor units with a currency and scale.
import os, random, sqlite3, tempfile, time
workdir = tempfile.mkdtemp()
db_path = os.path.join(workdir, "shop.sqlite")
# autocommit: transactions are explicit below
con = sqlite3.connect(db_path, isolation_level=None)
assert con.execute("PRAGMA journal_mode = WAL").fetchone()[0] == "wal"
con.execute("CREATE TABLE customers (customer_id TEXT PRIMARY KEY, name TEXT NOT NULL, country TEXT)")
con.execute("CREATE TABLE orders (order_id TEXT PRIMARY KEY, customer_id TEXT NOT NULL, "
"ordered_at TEXT NOT NULL, status TEXT NOT NULL, amount REAL NOT NULL)")
rng = random.Random(0)
con.execute("BEGIN")
con.executemany("INSERT INTO customers VALUES (?, ?, ?)",
((f"C{i}", f"Customer {i}", rng.choice(["KR", "JP", "US", "DE", "BR"])) for i in range(1, 100_001)))
con.executemany("INSERT INTO orders VALUES (?, ?, ?, ?, ?)",
((f"O{i}", f"C{rng.randint(1, 100_000)}",
f"2025-{rng.randint(1, 12):02d}-{rng.randint(1, 28):02d} {rng.randint(0, 23):02d}:{rng.randint(0, 59):02d}:00",
rng.choices(["paid", "refunded", "cancelled"], weights=[95, 3, 2])[0],
round(rng.uniform(1, 200), 2)) for i in range(1, 1_000_001)))
con.execute("COMMIT")
page_size = con.execute("PRAGMA page_size").fetchone()[0]
page_count = con.execute("PRAGMA page_count").fetchone()[0]
print(f"{page_count} pages of {page_size} bytes = {page_count * page_size / 1e6:.0f} MB")
# Example: about 79 MB; varies by machine and SQLite build
def plan(sql):
return " / ".join(row[3] for row in con.execute("EXPLAIN QUERY PLAN " + sql).fetchall())
def timed(sql):
t = time.perf_counter()
value = con.execute(sql).fetchone()[0]
return value, f"{time.perf_counter() - t:.4f} s"plan returns SQLite’s access path; timed executes the query and returns its first value plus elapsed time. The database page cache and the operating system cache can both avoid physical reads. A shared_buffers miss in PostgreSQL can still be served from the OS cache. The cost of loading a page from storage is different from reading a cache line in RAM, so a single memory-latency number is not the time to process an entire page. These examples do not establish a controlled cold-cache benchmark.
Wide rows increase the pages a scan may visit. PostgreSQL can compress large values or move them out of line through TOAST, depending on size and storage settings; SQLite uses overflow pages for payloads that do not fit. Whether a query actually fetches a large value also depends on the columns it needs. Row count alone therefore does not predict scan cost.
Indexes: finding rows without reading everything
Without a suitable index, finding one customer’s orders requires a scan that checks rows across the table. That is often reasonable for reading a large fraction of the table, but wasteful for a few matching rows. A scan is logical work over pages and rows; it does not imply a physical disk read for every page.
A B-tree index is a balanced, sorted structure. Internal nodes direct a search into a key range; leaves hold indexed values and row references. A lookup descends through a few levels, then retrieves matching rows when the index cannot answer alone. A range query descends to its first key and walks the relevant leaf entries. B-trees are a common default, but PostgreSQL also offers index types such as GIN, GiST, and BRIN for other access patterns.
[ M | T ] root: values < M, M..T, > T
/ | \
[ D | H ] [ P | R ] [ V | X ] internal
/ | \ ... ...
[A,B,C][D..G][H..L] leaves: sorted values → row locationsq = "SELECT count(*) FROM orders WHERE customer_id = 'C42'"
print(plan(q), timed(q))
# SCAN orders (13, '0.0687 s') # varies by machine
con.execute("CREATE INDEX orders_customer_idx ON orders (customer_id)")
print(plan(q), timed(q))
# SEARCH orders USING COVERING INDEX orders_customer_idx (customer_id=?) (13, '0.0000 s') # varies by machine
assert con.execute(q).fetchone()[0] == 13Both queries return 13 orders. The first plan scans; the second can search a small index range. COVERING means this SQLite query needs no additional columns from the table. Faster access does not make the result different, and a rounded timing of 0.0000 seconds means less than the display precision, not zero work. On another cache state, both timings can change.
Composite keys, covering reads, and write cost
An index on (customer_id, ordered_at) sorts by customer, then by date within each customer. Equality on customer followed by a date range gives one bounded part of the tree; customer alone also uses a leading prefix. Date alone is scattered across customers. The planner may scan the index, choose the table, or use an engine-specific skip scan when skipping distinct leading values is cheap enough. “No leading predicate” does not mean “the index is always useless.”
Choose column order from the queries you need: equality predicates followed by a range are a useful starting point, but ordering requirements and reusable prefixes matter too. “Most selective first” is not a universal rule when multiple columns all have equality predicates. A date-only query may justify its own index; compare its plan and workload cost before adding it.
A covering index contains the values needed by a query. PostgreSQL’s INCLUDE can add payload columns, but an index-only scan must also establish tuple visibility. If the visibility map does not mark a heap page all-visible, it still fetches the heap. Wider indexes also use more space and cache. Inserts and deletes maintain affected indexes; updates may avoid some index work, for example PostgreSQL HOT updates under suitable conditions. Eight indexes do not translate into exactly nine physical disk writes per insert.
Reference: PostgreSQL index-only scans.
Indexes can enforce uniqueness as well as accelerate reads. Before dropping an apparently unused index during a bulk load, check its constraints, other workloads, rebuild cost, and locking requirements. The useful comparison is the complete read/write workload, not one query’s speed.
Statistics and the optimizer
The optimizer estimates row counts and costs before choosing access paths, join order, and available join algorithms. PostgreSQL has several join algorithms; SQLite implements joins with nested loops. A bad row-count estimate can make a cheap-looking plan expensive. Statistics become stale after data changes, but correlations, parameter values, and the cost model can also explain a mismatch.
A normal B-tree often helps a selective predicate. It can be less attractive when most rows match and the query must fetch a non-indexed column. Functions such as date(ordered_at) may need an expression index or a rewrite to a half-open range. A leading wildcard provides no fixed starting bound for an ordinary B-tree search, although a covering scan is still possible. Prefix LIKE optimization depends on collation and operator rules. Type conversions can also change index use; determine which side is converted instead of assuming every mismatch disables the index.
The orders generator makes roughly 95% paid and 2% canceled. sqlite_stat1 records an index’s row count and average rows per distinct prefix, so 1000000 333334 describes three status values on average. It does not say which status owns 95%. Builds with ENABLE_STAT4 can collect samples that help estimate this skew. The following plan changes are examples from a STAT4-enabled build; your build may choose differently.
import math
print("STAT4:", any(row[0] == "ENABLE_STAT4" for row in con.execute("PRAGMA compile_options")))
# STAT4: True # varies by machine and SQLite build
con.execute("CREATE INDEX orders_status_idx ON orders (status)")
paid = "SELECT sum(amount) FROM orders WHERE status = 'paid'"
before = con.execute(paid).fetchone()[0]
print(plan(paid), timed(paid))
# SEARCH orders USING INDEX orders_status_idx (status=?) (95465534.08, '0.1154 s') # varies by machine
con.execute("ANALYZE")
print(con.execute("SELECT idx, stat FROM sqlite_stat1 WHERE tbl = 'orders' ORDER BY idx").fetchall())
# [('orders_customer_idx', '1000000 11'), ('orders_status_idx', '1000000 333334'), ('sqlite_autoindex_orders_1', '1000000 1')]
print(plan(paid), timed(paid))
# SCAN orders (95465534.08, '0.0859 s') # varies by machine
cancelled = "SELECT sum(amount) FROM orders WHERE status = 'cancelled'"
print(plan(cancelled), timed(cancelled))
# SEARCH orders USING INDEX orders_status_idx (status=?) (2033894.42, '0.0200 s') # varies by machine
assert math.isclose(before, con.execute(paid).fetchone()[0], rel_tol=1e-12)A scan for the common value and an indexed search for the rare one can both be sensible. Reading 95% of entries through an index can involve many table visits, but it is not necessarily one physical I/O per row. ANALYZE changes planner information, not the query’s intended result; the assertion checks that the paid sum is unchanged within floating-point tolerance.
Reference: SQLite optimizer overview.
Plan nodes describe operations such as scans, joins, and sorts. Read from the child operations toward their parent. rows is the number emitted by a node, not necessarily the number it examined. Estimated cost uses planner units, not milliseconds, and a parent’s cost includes its children. A nested-loop inner node returning 20 rows per loop for 100 loops emits about 2,000 rows in total; comparing only “20” with an outer total would misread the plan.
In PostgreSQL, use EXPLAIN (ANALYZE, BUFFERS) on a SELECT to compare estimated rows with observed rows and buffer work. ANALYZE in this command really executes the statement; do not casually attach it to a write. In a node executed repeatedly, actual rows and time are reported per loop on average, so read loops too. A large mismatch is a lead to investigate statistics and predicates. shared read means the database loaded a buffer; the OS may have served it without a device read.
Illustrative PostgreSQL plan fragment, not a recorded run:
Nested Loop ... rows=12 ... actual rows=4800 loops=1
... Buffers: shared hit=1204 read=498
Interpretation: far more rows than estimated; investigate the estimate.
The buffer counters alone do not prove physical disk I/O.Reference: PostgreSQL EXPLAIN.
LSM trees: another storage design
An LSM tree collects writes in a sorted in-memory memtable and flushes immutable sorted files, often called SSTables. A durable configuration logs writes before acknowledging them; memory alone cannot survive a crash. Compaction merges files to bound future read work, but rewriting data creates write amplification. The design is used in systems built on RocksDB and in stores such as Cassandra; details of levels and durability vary.
write -> WAL (according to durability settings) + sorted memtable
memtable full -> immutable sorted files
compaction -> merge files, retain versions still needed by readers
read -> memtable + candidate files selected using ranges and filtersA Bloom filter can rule out files for a key, but positive matches can be false positives. A delete usually adds a tombstone; compaction can discard it and old values only when the retention and visibility rules make that safe. Compaction pressure is one cause of latency or write stalls, not a diagnosis for every slowdown. B-tree versus LSM is a workload trade-off involving reads, writes, and space. Row versus column layout is a separate design dimension, and hybrid systems exist.
Reference: RocksDB overview.
Transactions and the write-ahead log
ACID describes transaction guarantees. Atomicity makes grouped writes all-or-nothing. Consistency means preserving the invariants implemented by constraints and application logic; the database cannot infer every business rule. Isolation controls interactions between concurrent transactions. Durability means acknowledged commits survive the failures covered by the configured persistence guarantees. These properties involve several cooperating mechanisms, not a one-to-one map from each letter to one feature.
With write-ahead logging, required log records reach durable storage before the corresponding changed data pages are written. PostgreSQL normally flushes the required WAL at commit; asynchronous settings weaken that guarantee. Multiple transactions can share a flush through group commit. Dirty pages can be written in the background, and checkpoints establish recovery progress. SQLite WAL records changed page images and later checkpoints them into its database file; PostgreSQL WAL uses recovery records. The recovery formats are not interchangeable.
change pages in memory -> generate WAL records
required WAL durable -> acknowledge synchronous commit
background writes + checkpoints -> advance persistent data/recovery state
restart -> recover using the durable database state and required logCommit batching amortizes transaction and flush overhead, but larger transactions hold resources longer and enlarge rollback and recovery work. There is no universal rows-per-second limit for one-row commits. The experiment below keeps the row count fixed, changes the batch size, and checks that the requested number of rows was inserted, including a partial last batch.
con.execute("PRAGMA synchronous = FULL")
con.execute("CREATE TABLE events (id INTEGER PRIMARY KEY, payload TEXT)")
def insert_rows(n, per_commit):
if type(n) is not int or type(per_commit) is not int:
raise TypeError("n and per_commit must be integers")
if n <= 0 or per_commit <= 0:
raise ValueError("n and per_commit must be positive")
before_count = con.execute("SELECT count(*) FROM events").fetchone()[0]
t = time.perf_counter()
for start in range(0, n, per_commit):
con.execute("BEGIN")
try:
batch_size = min(per_commit, n - start)
con.executemany("INSERT INTO events (payload) VALUES (?)",
(("x" * 50,) for _ in range(batch_size)))
con.execute("COMMIT")
except Exception:
if con.in_transaction:
con.execute("ROLLBACK")
raise
elapsed = time.perf_counter() - t
assert con.execute("SELECT count(*) FROM events").fetchone()[0] == before_count + n
return n / elapsed
for per_commit in (1, 100, 2_000):
print(f"{per_commit:5d} rows per commit: {insert_rows(2_000, per_commit):10,.0f} rows/s")
# Throughput varies by machine; compare equal-sized loads.
insert_rows(7, 3)
print("WAL bytes:", os.path.getsize(db_path + "-wal"))
# WAL bytes varies by machine and earlier checkpoint activity.
checkpoint = con.execute("PRAGMA wal_checkpoint(TRUNCATE)").fetchone()
assert checkpoint == (0, 0, 0), checkpoint
print("WAL bytes after checkpoint:", os.path.getsize(db_path + "-wal"))
# WAL bytes after checkpoint: 0Each loop iteration is a separate transaction. If a later batch fails, earlier committed batches remain; restarting the whole load without a duplicate-handling policy can insert them again. The function rolls back an active failed batch and rejects non-integer sizes before writing.
A WAL file’s physical length is not the amount of unapplied work: SQLite can retain and reuse already checkpointed frames. This TRUNCATE checkpoint succeeds when no reader pins an older state; active readers can prevent completion. PostgreSQL log retention has different controls, including checkpoints, archiving, and replication slots. Small commits alone do not guarantee bounded log retention.
Reference: SQLite WAL and checkpoints.
CDC reads a supported change stream, not an arbitrary recovery file as if it were a complete business audit. PostgreSQL logical decoding and replication slots expose supported committed changes with position and retention rules; MySQL commonly uses the binlog, which is separate from InnoDB redo. Transaction boundaries, schema information, deletes, and restart positions all matter. A reliable initial snapshot plus CDC needs a coordinated snapshot/log-position protocol. A timestamp watermark alone does not preserve a snapshot or capture every deletion.
Reference: PostgreSQL logical decoding.
MVCC, snapshots, and cleanup
PostgreSQL MVCC stores row versions so ordinary reads can see a consistent committed state while writers create newer versions. A snapshot includes visibility information about committed and in-progress transactions, together with rules for the transaction’s own changes. It is not simply “all transaction IDs below this number.” A reader using a snapshot from before a refund sees the paid version; a later snapshot can see the committed refunded version.
SQLite WAL gives readers stable page views while a writer appends newer pages. It permits only one writer at a time. These ordinary readers can coexist with the writer, but neither database promises that readers and writers never wait: conflicting writes and schema locks still matter. In SQLite, upgrading an old read snapshot to a write can fail with SQLITE_BUSY_SNAPSHOT; restart the whole transaction on a fresh snapshot.
Reference: SQLite isolation.
PostgreSQL VACUUM reclaims dead tuples only when visibility rules permit it. A transaction holding an old snapshot can delay cleanup, so versions accumulate during updates. A bare BEGIN that has not acquired a snapshot is not by itself proof that every table’s versions are pinned. Ordinary VACUUM mainly makes space reusable within the relation; it does not normally shrink the whole file. VACUUM FULL rewrites it with stronger locking. SQLite VACUUM also rebuilds its database, while old WAL readers can delay checkpoint progress; do not apply PostgreSQL tuple-cleanup rules to SQLite.
Reference: PostgreSQL routine vacuuming.
Isolation levels and consistent extraction
The following distinctions concern PostgreSQL ordinary reads. Read committed takes a new snapshot for each statement; read uncommitted behaves the same in PostgreSQL. Repeatable read keeps one snapshot from the first non-transaction-control statement, preventing non-repeatable reads and phantoms in PostgreSQL. It still permits serialization anomalies such as write skew. Serializable ensures a result equivalent to some serial transaction order, potentially rejecting a transaction that must be retried. Other engines’ same-named levels and locking reads need their own rules.
A non-repeatable read sees a changed value when a row is read again; a phantom changes the set matching a predicate. For write skew, suppose two doctors are on call and at least one must remain. Each transaction sees both on call and switches its own doctor off. They update different rows, so snapshot isolation can allow both commits and leave nobody on call. If all participating transactions use serializable isolation and recheck the rule on whole-transaction retry, that outcome is prevented; explicitly coordinating through a shared lock or a suitable constraint design can also protect the invariant.
Reference: PostgreSQL transaction isolation.
Watch snapshot lifetime in SQLite using a separate 400-row table, so the experiment does not change the million-order benchmark. Outside an explicit transaction the completed SELECTs see later commits. Inside the read transaction, the first SELECT pins a view until COMMIT.
con.execute("CREATE TABLE snapshot_orders (id INTEGER PRIMARY KEY, status TEXT NOT NULL)")
con.executemany("INSERT INTO snapshot_orders VALUES (?, 'paid')", ((i,) for i in range(1, 401)))
reader = sqlite3.connect(db_path, isolation_level=None)
writer = sqlite3.connect(db_path, isolation_level=None)
def refunded(connection):
return connection.execute("SELECT count(*) FROM snapshot_orders WHERE status = 'refunded'").fetchone()[0]
def refund_100():
writer.execute("UPDATE snapshot_orders SET status = 'refunded' WHERE id IN "
"(SELECT id FROM snapshot_orders WHERE status = 'paid' ORDER BY id LIMIT 100)")
try:
first = refunded(reader)
refund_100()
second = refunded(reader)
assert (first, second) == (0, 100)
print("statement snapshots:", first, second)
# statement snapshots: 0 100
reader.execute("BEGIN")
pinned = refunded(reader)
refund_100()
same = refunded(reader)
reader.execute("COMMIT")
latest = refunded(reader)
assert (pinned, same, latest) == (100, 100, 200)
print("one snapshot:", pinned, same, latest)
# one snapshot: 100 100 200
finally:
reader.close()
writer.close()This resembles the difference between PostgreSQL statement snapshots and a repeatable-read transaction, but it does not make SQLite’s isolation levels identical. For an extraction of orders and items, separate snapshots can disagree if changes commit between reads. A shared database snapshot avoids mixing commit points, but it cannot repair invalid source relationships or a business update split across separate commits. Multiple connections need an engine-supported shared snapshot mechanism; a timestamp filter alone does not synchronize them. Avoid holding the snapshot while doing unrelated slow output work, and release the transaction on both success and failure.
Locks, deadlocks, and connection budgets
PostgreSQL ordinary SELECT takes a table-level ACCESS SHARE lock, normally compatible with writes. DDL such as ADD COLUMN needs ACCESS EXCLUSIVE and may wait for that reader. Later readers can queue behind the waiting exclusive request. Use bounded lock waits and diagnose blockers with pg_blocking_pids; an apparent slow query may be waiting rather than computing. DDL operations do not all request the same lock strength.
A deadlock is a cycle: transaction A holds row 1 and waits for row 2, while B holds row 2 and waits for row 1. PostgreSQL aborts a victim transaction to break the cycle; the application must roll back its failed transaction state and retry the complete unit of work. Updating keys in a consistent order prevents this particular cycle. Other resources and foreign-key checks can create other cycles, so retries still need bounded attempts and safe handling of external side effects.
Connections also consume resources: PostgreSQL uses server processes for client sessions, while SQLite is embedded in the application. Bound connection pools across all workers rather than treating each worker’s pool size as the whole budget. Leave capacity for operations and finish or roll back transactions before returning a connection. Excess concurrency can increase lock waits, memory pressure, and latency even when individual queries are efficient.
After the SQLite examples, close the connection with con.close() and remove its temporary directory when no process uses it.
Read a slow query as evidence
Start by checking whether the query is running or waiting. If it is running, compare expected and actual rows, access paths, buffer work, and elapsed time under a known workload. If it is waiting, identify the lock holder and transaction lifetime. For growing files, distinguish live data, reusable space, retained versions, and retained logs. Each measurement narrows a different cause; none alone proves that an index, ANALYZE, or VACUUM is the fix.
You should now be able to explain why a date predicate can miss a composite index’s useful prefix, why fresh average statistics alone cannot describe skew, why a covering PostgreSQL index can still fetch the heap, and why a stable extraction snapshot has a cleanup cost.
References
- PostgreSQL index-only scans
- SQLite optimizer overview
- PostgreSQL EXPLAIN
- RocksDB overview
- SQLite WAL and checkpoints
- PostgreSQL logical decoding
- SQLite isolation
- PostgreSQL routine vacuuming
- PostgreSQL transaction isolation
Discover more from Insightful Data Lab
Subscribe to get the latest posts sent to your email.