Database Systems & Storage

Database Systems & Storage

Databases are the foundation of most applications. The choice of database — and how you use it — determines whether your application is correct, performant, and scalable. Understanding database internals helps you write better queries, design better schemas, and make informed choices between the dozens of database systems available.

Relational Databases and SQL

Relational databases model data as tables with rows and columns, with relationships between tables expressed through foreign keys.

ACID transactions:

• Atomicity: a transaction either completes entirely or not at all. No partial updates. If step 2 of 3 fails, step 1 rolls back.
• Consistency: a transaction brings the database from one valid state to another. Constraints (NOT NULL, UNIQUE, FK) are enforced; invalid states are rejected.
• Isolation: concurrent transactions execute as if serialized. One transaction's in-progress changes aren't visible to others until committed.
• Durability: once committed, data persists even if the database crashes immediately after.

Isolation levels (tradeoffs between isolation and performance):

• Read Uncommitted: can read dirty (uncommitted) data. Fastest, least safe.
• Read Committed: only committed data is visible. Default in PostgreSQL.
• Repeatable Read: same query returns same results within a transaction.
• Serializable: full isolation; transactions appear to run serially.

Higher isolation prevents anomalies (dirty reads, non-repeatable reads, phantom reads) but increases lock contention and reduces throughput.

Indexes

An index is an auxiliary data structure enabling fast data retrieval without scanning every row:

B-tree index (default): balanced tree. Supports equality (WHERE id = 42), range (WHERE age > 18), and prefix queries (WHERE name LIKE 'Jo%'). Column order matters for composite indexes.

Hash index: O(1) equality lookup; doesn't support range queries. PostgreSQL uses hash indexes internally for certain operations.

Composite indexes: an index on (last_name, first_name) helps queries filtering on last_name or on both; doesn't help filtering on first_name alone. The leading column rule: the first column in the index must appear in the WHERE clause.

Partial indexes: index only rows matching a condition:

CREATE INDEX idx_active_users ON users(email) WHERE status = 'active';

Smaller, faster, but only helps queries with that condition.

Index trade-offs: indexes speed reads but slow writes (every write updates all relevant indexes). An over-indexed table with 20 indexes has 20x write amplification.

Query Optimization

The query optimizer chooses how to execute a query. EXPLAIN ANALYZE reveals the plan:

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 123 ORDER BY created_at DESC LIMIT 10;

Key plan nodes:

• Seq Scan: reads every row in the table. Fast for large fractions; slow for selective queries on large tables.
• Index Scan: uses a B-tree to find matching rows. Fast for selective predicates.
• Index Only Scan: all needed columns are in the index; no heap access. Fastest.
• Nested Loop Join: for each row in the outer table, find matching rows in the inner table. Excellent when inner is indexed and the outer is small.
• Hash Join: build a hash table from one side, probe with the other. Good for large unsorted joins.
• Merge Join: sort both sides, merge. Good for pre-sorted data.

Common optimization patterns:

• Add an index on high-cardinality columns used in WHERE and JOIN
• Avoid functions on indexed columns in WHERE (WHERE YEAR(created_at) = 2024 disables index; use WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31')
• Use LIMIT early in CTEs (PostgreSQL may not push LIMIT down)
• Avoid SELECT * in production queries; select only needed columns
• Use EXPLAIN ANALYZE, not EXPLAIN — actual numbers, not estimates

NoSQL Databases

NoSQL (not only SQL) covers several data models:

Document databases (MongoDB, CouchDB, Firestore): store JSON/BSON documents in collections. Schema-flexible (different documents can have different fields). Good for hierarchical data, rapidly changing schemas, and teams with varied data shapes. Weaker consistency guarantees than RDBMS.

Key-value stores (Redis, DynamoDB, etcd): the simplest model — keys map to values. Extremely fast. Redis adds data structures (lists, sets, sorted sets, hashes). Used for caching, session storage, rate limiting, leaderboards.

Column-family databases (Cassandra, HBase): data organized by column families. Optimized for write-heavy workloads and queries by a partition key. No joins; denormalized by design. Scales linearly to petabytes.

Graph databases (Neo4j, Amazon Neptune): data as nodes and edges. Efficient traversal of relationships (social networks, recommendation engines, knowledge graphs). SQL's JOIN chains become natural traversals.

Time-series databases (TimescaleDB, InfluxDB, Prometheus): optimized for sequential writes of timestamped data (metrics, IoT, financial data). Efficient aggregation over time ranges; automatic data retention policies.

CAP Theorem and Distributed Databases

Eric Brewer's CAP theorem: a distributed data store can guarantee at most two of:

• Consistency: every read sees the most recent write
• Availability: every request receives a response (though possibly not the most recent data)
• Partition tolerance: the system continues operating despite network partitions

Since network partitions are unavoidable in distributed systems, the real choice is between CP (consistency + partition tolerance — may reject requests during partition) and AP (availability + partition tolerance — may serve stale data during partition).

PACELC (refinement of CAP): even without partitions, there's a trade-off between Latency and Consistency. Lower latency requires acknowledging writes before all replicas confirm — risking stale reads.

PostgreSQL: ACID, CP (primary serves consistent reads; replica may be slightly behind). Cassandra: AP (highly available, eventually consistent by default). DynamoDB: configurable (strongly consistent reads with higher latency, or eventually consistent with lower latency).

Write-Ahead Log

The WAL is how databases achieve durability. Before modifying data pages:

1. Write the intended change to the WAL (sequential, append-only — very fast)
2. Acknowledge the commit to the client
3. Apply the change to data pages asynchronously

On crash: replay the WAL from the last checkpoint to recover all committed transactions.

Streaming replication (PostgreSQL): the WAL stream is shipped to replicas, which replay it to stay in sync. The primary's WAL is the source of truth; replicas are consistent copies.

Change Data Capture (CDC): read the WAL to capture every row-level change and stream it to other systems (Kafka, event buses, search indexes). Debezium, AWS DMS, and PostgreSQL's logical replication all use this pattern.