Design a Relational Database (PostgreSQL)

1. Query Execution Pipeline

Interview depth on PostgreSQL internals centers on four mechanisms: how queries become execution plans, how the buffer pool amortizes disk I/O, how WAL makes commits durable without flushing every dirty page synchronously, and how MVCC lets readers and writers coexist without blocking each other.

Every query passes through parsing, semantic analysis, planning, and execution. EXPLAIN ANALYZE is how you verify whether the chosen plan actually uses the expected index or falls back to a sequential scan.

When a SQL query arrives, the execution pipeline works through the following stages:

• Parser: Verifies syntax and generates a Parse Tree.
• Analyzer: Checks semantics (verifying whether tables and columns exist and validating permissions).
• Optimizer (Cost-Based): Generates multiple execution plans (such as Index Scan vs Sequential Scan, or Hash Join vs Nested Loop Join) and estimates the I/O and CPU cost of each using statistical distributions. It picks the cheapest plan.
• Executor: Processes the plan node-by-node (Volcano iterator model), pulling tuples from the storage engine.

EXPLAIN ANALYZE SELECT * FROM users WHERE age > 30 ORDER BY name LIMIT 10;

Limit  (cost=0.42..1.53 rows=10 width=45) (actual time=0.045..0.055 rows=10 loops=1)
  ->  Index Scan using users_name_idx on users  (cost=0.42..111.45 rows=1000 width=45)
        Filter: (age > 30)
        Rows Removed by Filter: 15
Planning Time: 0.150 ms
Execution Time: 0.080 ms

2. Buffer Pool (Shared Memory)

Disk I/O is the primary bottleneck. The buffer pool caches 8 KB database pages in shared memory, with a hit ratio above 95% as the operational target. PostgreSQL uses a clock sweep style buffer replacement strategy rather than a classic LRU implementation.

Disk I/O is slow. PostgreSQL allocates a large chunk of RAM called the shared_buffers. The database reads data from storage in fixed size blocks, usually 8 KB, called pages.

• When a query requests a row, the storage engine checks whether the page containing that row is already in the Buffer Pool.
• If it is (Cache Hit), it's returned immediately.
• If not, the page is loaded from storage into the Buffer Pool, and an older page may be evicted according to PostgreSQL's clock sweep based replacement policy.
• Modifications are made in memory first. The page becomes "dirty".

3. Write Ahead Log (WAL) and Durability

WAL is the durability mechanism. PostgreSQL flushes the required WAL records at commit, while dirty data pages are written later by checkpoint and background write activity. The key rule is WAL before the corresponding data page. For downstream CDC ingestion, see the Change Data Capture (CDC) Pipeline.

If the database crashes before dirty pages are flushed to disk, those in memory data pages can be lost, but committed changes remain recoverable from durable WAL. Flushing 8 KB data pages for every transaction would create excessive random I/O. The solution is the WAL, which lets the commit path persist a much smaller sequential log record while data pages are flushed later.

• Before modifying a page in the Buffer Pool, a small log entry describing the change is appended to the WAL in memory.
• On COMMIT, the required WAL records are flushed to durable storage before the commit is acknowledged. Group commit can let multiple transactions share one flush.
• Dirty data pages are written during checkpoint processing, while the bgwriter also writes pages proactively to smooth future write pressure.
• Rule: The required WAL records must reach durable storage before the corresponding dirty data page is written to durable storage.
• Checkpoint: A checkpoint flushes dirty data pages and records a redo starting point. A checkpoint is not a transaction commit and does not itself determine whether an individual transaction is committed.
• Full page writes: With full page writes enabled, the first modification to a data page after a checkpoint can log the full page image in WAL to protect against torn page writes. This increases WAL volume after checkpoints.

LSN 0/1A2B3C: 
  Transaction ID: 5092
  Resource Manager: Heap
  Action: INSERT
  Relation: users (filenode: 16384)
  Block: 42
  Offset: 12
  Tuple Data: (id=5, name='Bob', age=35)

4. Multi Version Concurrency Control (MVCC)

MVCC lets PostgreSQL readers use transaction snapshots while updates create new tuple versions. Ordinary reads therefore do not need row read locks that conflict with writers, although write write conflicts can still block or abort transactions.

MVCC is designed so ordinary reads can proceed without acquiring row locks that conflict with concurrent writers. An UPDATE creates a new tuple version, allowing readers to continue using an appropriate transaction snapshot.

• Each heap tuple carries MVCC metadata including xmin and xmax, which identify the inserting and deleting or updating transaction IDs.
• Tuple visibility is evaluated against the transaction snapshot, including transaction IDs that were committed, aborted, or still in progress. It is more precise than a simple xmin/xmax comparison.
• Transaction status and hint bits: PostgreSQL uses transaction status data to determine whether relevant XIDs committed or aborted, and hint bits can cache visibility information in tuple headers so repeated checks do not always require another status lookup.
• Repeatable Read provides a stable snapshot for the transaction, while Serializable adds PostgreSQL's Serializable Snapshot Isolation checks to detect dangerous dependency patterns.
• Vacuum Horizon: VACUUM cannot remove tuple versions that might still be visible to an active transaction. Long running transactions can therefore hold back cleanup and increase table bloat.
• Autovacuum: PostgreSQL normally schedules background vacuum and analyze work based on table activity. The goal is to reclaim reusable space and keep planner statistics current before bloat or transaction ID aging becomes dangerous.

5. Indexes (B tree and Hash)

B tree indexes reduce point lookup search from O(N) scanning to O(log N) tree navigation. A tree depth of 3 to 4 at billion row scale means only a few index levels must be traversed, although some pages may already be cached and an index scan may also need a heap page fetch.

Indexes reduce point lookup search from O(N) scanning to O(log N) tree navigation. PostgreSQL's B tree access method is the general purpose ordered index structure.

• Leaf entries identify heap tuples through tuple identifiers unless the index can satisfy the query as an index only scan.
• Because the tree is balanced and highly branched, even very large tables can have only a few index levels. The exact number of storage reads depends on cache residency and whether the query can use an index only scan.
• PostgreSQL also supports Hash indexes, GiST for extensible search such as geospatial workloads, and GIN for inverted indexes such as full text and JSONB containment.
• Index Only Scans: A B tree query can avoid heap fetches when all required columns are available from the index and the visibility map confirms that the relevant heap pages are all visible.

6. Connection Pooling (PgBouncer)

A dedicated PostgreSQL backend process per client connection becomes expensive when connection counts grow into the thousands. PgBouncer reduces the number of active PostgreSQL backends by multiplexing many client connections through a smaller server side pool.

PostgreSQL normally uses one backend process per client connection. The ~10MB per connection figure is a planning estimate, not a protocol guarantee, and the actual memory cost varies with workload and session state. At scale, thousands of client connections can exhaust memory and process capacity.PgBouncer is used as a lightweight connection pooler sitting in front of PostgreSQL, multiplexing thousands of client connections onto a small pool of actual database connections.

7. High Availability and Replication

Single node PostgreSQL scales primarily through CPU, RAM, and storage improvements. Streaming replication provides standby copies, while a failover manager such as Patroni coordinates promotion without changing the SQL model.

To survive a catastrophic node failure, PostgreSQL uses Replication.

• Physical Replication (Streaming): The primary streams WAL records to a standby, and the standby replays that WAL to maintain a physically equivalent database state.
• Logical Replication: Decodes WAL into logical row changes for selected publications and subscriptions. It is useful for selective replication and many migration paths, including major version upgrades with minimal downtime.
• Automated Failover: Tools such as Patroni use a distributed configuration store such as etcd, Consul, or ZooKeeper for leader election and cluster state. If the primary fails, the selected standby can be promoted and the routing layer can be updated.
• Replica Lag: Asynchronous standbys can lag behind the primary. Applications that require read after write consistency should route those reads to the primary or wait for a replica to replay the required WAL position.

8. Heap Maintenance: FSM, Visibility Map, HOT, and TOAST

These structures explain several behaviors that appear in production once update rates and row sizes increase. They are the bridge between the logical MVCC model and the physical heap layout.

• Free Space Map (FSM): Tracks approximate free space available on relation pages so INSERT and update placement can find candidate pages efficiently.
• Visibility Map: Maintains all visible and all frozen information for heap pages. The all visible bit can let an index only scan avoid heap visibility checks, while VACUUM uses the map to skip work that is already known to be clean and to track pages suitable for freezing related maintenance.
• HOT Update: When indexed columns are unchanged and the page has enough free space, PostgreSQL can place the new tuple version on the same heap page without adding new index entries. This reduces index maintenance and write amplification but depends on page space and update patterns.
• TOAST: Oversized variable length values can be compressed and stored out of line in a related TOAST table as chunked values, with the main heap row retaining the reference to the external data.