4. Databases from first principles

A database is a storage engine, a query engine and a set of guarantees bundled together. Knowing which guarantees it gives and which access pattern it optimizes tells you when to use it and when not to.

What a database adds over plain files

• Concurrency: many readers and writers at once without corrupting data.
• Durability: a committed write survives a crash, through a write-ahead log.
• Indexes: find rows without scanning everything.
• A query language and optimizer: you say what you want, it decides how to get it.
• Transactions and constraints: rules such as “every order has a customer” are enforced, not hoped for.

The relational model

Data lives in relations (tables) of rows with typed columns. A primary key uniquely identifies a row; a foreign key points to a row in another table. Queries are declarative: SQL describes the result, and the optimizer chooses the algorithm.

That separation is the deep idea. The same SQL can run on a laptop with DuckDB or on a thousand machines in BigQuery, because the “how” belongs to the engine.

SQL you must be fluent in

SQL is the lingua franca of data, including AI data. The parts that matter most:

• Filtering and aggregation: WHERE, GROUP BY, HAVING.
• Joins: inner, left, and the anti-join (rows in A with no match in B), which finds missing data.
• Window functions: ROW_NUMBER to deduplicate, LAG and LEAD for “previous value” features, running sums and moving averages.
• Common table expressions (WITH …) to build a query in readable steps.

SQL is evaluated in a logical order that differs from how it is written: FROM and JOIN, then WHERE, GROUP BY, HAVING, SELECT, ORDER BY and LIMIT. Most confusing SQL errors become obvious once you know this order.

A pattern you will use constantly, keeping only the latest record per user:

SELECT *
FROM (
  SELECT *,
         ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY updated_at DESC) AS rn
  FROM user_profiles
) t
WHERE rn = 1;

How a query actually runs

1. Parse the SQL into a tree.
2. Build a logical plan: which tables, filters, joins and aggregations.
3. Optimize it: push filters down close to the data, reorder joins, choose indexes. Most optimizers are cost-based and rely on table statistics.
4. Pick a physical plan: which join algorithm, which scan, how many workers.
5. Execute it.

Run EXPLAIN (or EXPLAIN ANALYZE) whenever a query is slow; reading plans is a core skill. The three join algorithms to recognize: nested loop (good when one side is tiny or indexed), hash join (build a hash table on the smaller side, probe with the larger), and sort-merge join (sort both sides on the key, then walk them together).

Indexes: B-trees and LSM-trees

Without an index, finding a row means scanning every row. An index is a second data structure that trades write cost and space for fast reads.

• B-tree: a balanced, wide tree kept sorted on disk. Lookups and range scans take a handful of page reads even for billions of rows. Every insert must update it in place. Used by PostgreSQL and MySQL (InnoDB).
• LSM-tree (log-structured merge tree): writes go to an in-memory buffer, which is flushed as sorted immutable files, merged later in the background (compaction). Writes are very fast; reads may check several files, helped by Bloom filters. Used by RocksDB, Cassandra and ScyllaDB.
• Inverted index: maps each word to the documents containing it. This powers keyword search engines such as Elasticsearch and OpenSearch, and BM25 retrieval in RAG.
• Vector index: finds nearest neighbours among embeddings. Covered in section 14.

The principle: B-trees optimize reads and in-place updates; LSM-trees optimize write throughput. Which one fits depends on your read/write ratio.

Transactions and ACID

• Atomicity: a transaction happens completely or not at all.
• Consistency: constraints hold before and after every transaction.
• Isolation: concurrent transactions do not see each other’s half-finished work.
• Durability: once committed, the change survives a crash.

Durability comes from the write-ahead log (WAL). Before changing any data page, the database appends the change to a sequential log and flushes it to disk. After a crash it replays the log. The same log later powers replication and change data capture (section 8), so remember it.

Isolation levels

Perfect isolation is expensive, so databases offer weaker levels that allow specific anomalies.

Most engines implement this with MVCC (multi-version concurrency control): writers create new row versions, and each reader sees a consistent snapshot. Readers never block writers. Lakehouse table formats reuse this exact idea on object storage.

OLTP versus OLAP

Never run heavy analytics directly on the production OLTP database: a large scan can slow the application for every user. Copy the data out to an analytical system instead; that copying is a core data engineering job.

The NoSQL families, as trade-offs

Each family gives up some relational generality to excel at one access pattern at scale.

A sound default for a new AI application is PostgreSQL. With JSONB it handles semi-structured data, with full-text search it handles keywords, and with pgvector it handles embeddings. Move to a specialized store only when you can name the limit you hit.

Questions to ask

• Is this workload transactional, analytical, or both?
• Which queries must be fast, and is there an index that serves each one?
• What isolation level are we running, and which anomaly could hurt us?
• Is this table read-heavy or write-heavy?
• What does EXPLAIN say the engine is actually doing?