Chapter 10: Relational Databases Deep Dive

1. ACID Properties

ACID guarantees make relational databases reliable for transactional workloads. Understanding the implementation details is crucial for interviews.

1.1 Overview

1.2 Transaction Lifecycle

1.3 Atomicity Deep Dive

-- Transaction T1
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- balance was 500
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- balance was 200
-- System crash here!

-- Undo log entries:
-- [T1, account_id=1, old_balance=500]
-- [T1, account_id=2, old_balance=200]

-- Recovery process:
-- 1. Find uncommitted transaction T1
-- 2. Apply undo logs in reverse: account 2 → 200, account 1 → 500
-- 3. Transaction rolled back

1.4 Durability Deep Dive

1.5 Consistency Enforcement

-- Consistency through constraints
CREATE TABLE accounts (
    id SERIAL PRIMARY KEY,
    balance DECIMAL(10, 2) NOT NULL CHECK (balance >= 0),  -- Domain constraint
    user_id INT NOT NULL REFERENCES users(id),              -- Referential integrity
    account_type VARCHAR(20) CHECK (account_type IN ('checking', 'savings'))
);

-- Consistency through triggers
CREATE TRIGGER maintain_audit_log
AFTER UPDATE ON accounts
FOR EACH ROW
EXECUTE FUNCTION log_balance_change();

-- Application-level consistency via serializable isolation
BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SELECT SUM(balance) FROM accounts WHERE user_id = 123;  -- Must equal 1000
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
-- If another transaction modified these rows, this will fail with serialization error
COMMIT;

2. Isolation Levels

Isolation levels define what a transaction can "see" from other concurrent transactions. This is the most frequently asked database topic in interviews.

2.1 Read Phenomena

2.2 Isolation Level Matrix

*PostgreSQL's Repeatable Read prevents phantoms and write skew; MySQL InnoDB's Repeatable Read allows write skew.

2.3 Dirty Read Visualization

2.4 Non-Repeatable Read Visualization

2.5 Phantom Read Visualization

2.6 Write Skew Example

-- Fix with SERIALIZABLE isolation
BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SELECT COUNT(*) FROM doctors WHERE on_call = true;  -- Count = 2
UPDATE doctors SET on_call = false WHERE name = 'Alice';
COMMIT;  -- Second transaction will fail with serialization error

2.7 PostgreSQL vs MySQL Isolation Levels

3. Multi-Version Concurrency Control (MVCC)

MVCC allows readers and writers to operate without blocking each other by maintaining multiple versions of each row.

3.1 Core Concept

3.2 PostgreSQL MVCC Implementation

-- Logical table
CREATE TABLE users (id INT, name TEXT);
INSERT INTO users VALUES (1, 'Alice');

-- Physical storage (simplified)
id | name  | xmin | xmax | ctid
---|-------|------|------|-----
1  | Alice | 1000 | 0    | (0,1)  ← xmin=1000 (created by txn 1000), xmax=0 (not deleted)

-- UPDATE users SET name = 'Alice Smith' WHERE id = 1 (transaction 1001)
-- Creates NEW version, marks old version as deleted
id | name        | xmin | xmax | ctid
---|-------------|------|------|-----
1  | Alice       | 1000 | 1001 | (0,1)  ← xmax=1001 (deleted by txn 1001)
1  | Alice Smith | 1001 | 0    | (0,2)  ← New version

-- Visibility rules for transaction T:
-- Show row if: xmin < T AND (xmax = 0 OR xmax > T)

3.3 MySQL InnoDB MVCC Implementation

-- Clustered index (latest version)
id | name        | DB_TRX_ID | DB_ROLL_PTR
---|-------------|-----------|-------------
1  | Alice Smith | 1001      | ptr → undo log

-- Undo log chain (older versions)
[1001] name = 'Alice Smith' → [1000] name = 'Alice' → NULL

-- Read View for transaction starting at 1000:
-- min_trx_id = 1000, max_trx_id = 1002, active_trx_ids = [1001]
--
-- Visibility check for row with DB_TRX_ID = 1001:
-- 1001 is in active_trx_ids → not visible → follow undo log chain
-- → Find version with DB_TRX_ID = 1000 → visible

3.4 Version Chain Diagram

3.5 Garbage Collection

-- PostgreSQL: Manual vacuum
VACUUM users;  -- Reclaim space
VACUUM FULL users;  -- Reclaim space and compact table (locks table)
VACUUM ANALYZE users;  -- Reclaim space + update statistics

-- Check for bloat
SELECT schemaname, tablename,
       pg_size_pretty(pg_total_relation_size(schemaname||'.'||tablename)) AS size,
       n_dead_tup
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY n_dead_tup DESC;

3.6 MVCC Performance Implications

4. Locking Mechanisms

Despite MVCC, databases still use locks for write-write conflicts and serializable isolation.

4.1 Lock Types

4.2 Lock Compatibility Matrix

4.3 Row-Level vs Table-Level Locking

4.4 Gap Locks Example (MySQL)

-- Table: users (id PRIMARY KEY)
-- Current rows: 1, 5, 10

BEGIN;  -- Transaction T1, REPEATABLE READ (default)
SELECT * FROM users WHERE id BETWEEN 3 AND 7 FOR UPDATE;
-- Returns: id=5
-- Gap locks acquired:
--   Gap before 5: (1, 5)
--   Gap after 5: (5, 10)
-- Prevents inserts of id=2,3,4,6,7,8,9

-- Transaction T2 (concurrent)
INSERT INTO users (id, name) VALUES (6, 'Bob');  -- BLOCKED by gap lock!
INSERT INTO users (id, name) VALUES (11, 'Charlie');  -- OK, not in gap

-- T1 commits, T2 proceeds

4.5 Deadlock Detection

-- Transaction T1
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- Lock row 1
-- ... pause ...
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- Wait for row 2

-- Transaction T2 (concurrent)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;  -- Lock row 2
UPDATE accounts SET balance = balance + 50 WHERE id = 1;  -- Wait for row 1

-- Deadlock! Database detects cycle and aborts one transaction
-- ERROR: deadlock detected
-- DETAIL: Process 12345 waits for ExclusiveLock on row (1); blocked by process 12346.
--         Process 12346 waits for ExclusiveLock on row (2); blocked by process 12345.

4.6 Wait-For Graph

Database periodically builds a wait-for graph. If it detects a cycle, it aborts the youngest transaction.

4.7 Optimistic vs Pessimistic Concurrency

-- Pessimistic: Lock immediately
BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;  -- Lock acquired
-- ... business logic ...
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

-- Optimistic: Check version at update time
BEGIN;
SELECT balance, version FROM accounts WHERE id = 1;  -- No lock
-- ... business logic ...
UPDATE accounts SET balance = balance - 100, version = version + 1
WHERE id = 1 AND version = 42;  -- Fails if version changed
-- If 0 rows updated, retry transaction
COMMIT;

4.8 Lock Escalation

5. Query Planning & Optimization

The query optimizer transforms SQL into an execution plan. Understanding this process is critical for performance tuning.

5.1 Query Execution Pipeline

5.2 Query Plan Tree

EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, o.total
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE o.created_at > '2025-01-01'
ORDER BY o.total DESC
LIMIT 10;

5.3 Join Algorithms

5.4 Join Algorithm Selection

-- Nested Loop (small outer, indexed inner)
SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.id = 12345;  -- Single order, use PK index on customers

-- Hash Join (large tables, no index)
SELECT * FROM orders o
JOIN line_items li ON o.id = li.order_id
WHERE o.created_at > '2025-01-01';  -- Many orders, hash join faster

-- Merge Join (both pre-sorted)
SELECT * FROM users u
JOIN profiles p ON u.id = p.user_id
ORDER BY u.id;  -- Both clustered by id, merge join efficient

5.5 Cost Model

-- Example cost calculation for seq scan
-- Seq Scan on users (cost=0.00..1834.00 rows=100000 width=40)
--
-- Formula: startup_cost + (pages * seq_page_cost) + (rows * cpu_tuple_cost)
-- = 0 + (1000 pages * 1.0) + (100000 rows * 0.01)
-- = 0 + 1000 + 1000 = 2000

-- Index Scan cost includes random I/O penalty
-- Index Scan using users_email_idx (cost=0.29..825.45 rows=100 width=40)
--
-- Higher startup cost (index traversal), but fewer rows processed

5.6 Statistics & Cardinality Estimation

-- View statistics
SELECT tablename, attname, n_distinct, most_common_vals, histogram_bounds
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';

-- Update statistics (run after bulk data changes)
ANALYZE orders;

-- Force statistics update with higher sample size
SET default_statistics_target = 1000;  -- Default 100
ANALYZE orders;

5.7 Index Selection

-- High selectivity: Index scan
EXPLAIN SELECT * FROM orders WHERE id = 12345;
-- Index Scan using orders_pkey (cost=0.29..8.31 rows=1)

-- Medium selectivity: Bitmap scan
EXPLAIN SELECT * FROM orders WHERE status = 'pending';  -- 10% of rows
-- Bitmap Heap Scan on orders (cost=120.15..5234.21 rows=10000)
--   -> Bitmap Index Scan on orders_status_idx (cost=0.00..117.65)

-- Low selectivity: Sequential scan
EXPLAIN SELECT * FROM orders WHERE status IN ('completed', 'pending');  -- 80% of rows
-- Seq Scan on orders (cost=0.00..18334.00 rows=80000)

5.8 Query Hints (Use Sparingly)

-- PostgreSQL: No direct hints, but can influence planner
SET enable_seqscan = off;  -- Force index usage (for testing)
SET work_mem = '256MB';    -- Allow larger hash tables

-- MySQL: Index hints
SELECT * FROM orders USE INDEX (orders_status_idx) WHERE status = 'pending';

-- Force join order (both databases)
SELECT /*+ LEADING(o c) */ *  -- MySQL optimizer hint
FROM orders o
JOIN customers c ON o.customer_id = c.id;

-- Better approach: Improve statistics instead of hints
ANALYZE orders;

6. Indexing Strategies

Indexes are the #1 performance lever in relational databases. Knowing when and how to use them is essential.

6.1 B-Tree Index Structure

6.2 Index Types Comparison

6.3 Composite Index Column Order

-- Create composite index
CREATE INDEX idx_orders_user_date ON orders (user_id, created_at);

-- Uses index efficiently
SELECT * FROM orders WHERE user_id = 123;                           -- Uses index (leftmost column)
SELECT * FROM orders WHERE user_id = 123 AND created_at > '2025-01-01';  -- Uses full index
SELECT * FROM orders WHERE user_id = 123 ORDER BY created_at;      -- Uses index for filter + sort

-- Does NOT use index
SELECT * FROM orders WHERE created_at > '2025-01-01';  -- Missing leftmost column
SELECT * FROM orders ORDER BY created_at;              -- Can't skip to created_at without user_id

-- Solution: Create separate index
CREATE INDEX idx_orders_date ON orders (created_at);

6.4 Covering Index

-- Query needs: user_id (filter), created_at (filter), total (select)
SELECT total FROM orders WHERE user_id = 123 AND created_at > '2025-01-01';

-- Regular index: Must read heap to get 'total'
CREATE INDEX idx_orders_user_date ON orders (user_id, created_at);
-- Query plan: Index Scan → Heap Fetch for each row

-- Covering index: Includes 'total', no heap access needed
CREATE INDEX idx_orders_user_date_total ON orders (user_id, created_at) INCLUDE (total);
-- Query plan: Index Only Scan (faster, less I/O)

-- MySQL syntax (implicit covering by including in index)
CREATE INDEX idx_orders_user_date_total ON orders (user_id, created_at, total);

6.5 Partial Index

-- Only 5% of orders are 'pending', rest are 'completed'
-- Regular index wastes space on 95% of rows
CREATE INDEX idx_orders_status ON orders (status);

-- Partial index: Only index pending orders
CREATE INDEX idx_orders_pending ON orders (status) WHERE status = 'pending';
-- 20x smaller index, faster writes, same query performance for pending orders

SELECT * FROM orders WHERE status = 'pending';  -- Uses partial index

6.6 Expression Index

-- Query uses lowercase comparison
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';

-- Regular index on 'email' won't be used (function applied)
CREATE INDEX idx_users_email ON users (email);  -- Not used!

-- Expression index on LOWER(email)
CREATE INDEX idx_users_email_lower ON users (LOWER(email));
-- Query plan: Index Scan using idx_users_email_lower

6.7 Index Maintenance Costs

6.8 When NOT to Index

• Low cardinality: Boolean columns, status with 2-3 values (unless using partial index)
• Small tables: <1000 rows, sequential scan is faster
• High write rate: Insert-heavy tables with many indexes suffer write amplification
• Infrequent queries: Index maintenance cost > rare query speedup

6.9 GIN Index for JSONB (PostgreSQL)

-- Store metadata as JSONB
CREATE TABLE events (
    id SERIAL PRIMARY KEY,
    data JSONB
);

-- GIN index for JSONB containment queries
CREATE INDEX idx_events_data ON events USING GIN (data);

-- Fast queries
SELECT * FROM events WHERE data @> '{"user_id": 123}';  -- Uses GIN index
SELECT * FROM events WHERE data ? 'transaction_id';     -- Key existence check
SELECT * FROM events WHERE data @> '{"status": "completed", "amount": 100}';

6.10 Full-Text Search

-- PostgreSQL: tsvector and GIN index
ALTER TABLE articles ADD COLUMN search_vector tsvector;
UPDATE articles SET search_vector = to_tsvector('english', title || ' ' || body);
CREATE INDEX idx_articles_search ON articles USING GIN (search_vector);

SELECT * FROM articles WHERE search_vector @@ to_tsquery('english', 'database & performance');

-- MySQL: FULLTEXT index
CREATE FULLTEXT INDEX idx_articles_fulltext ON articles (title, body);
SELECT * FROM articles WHERE MATCH(title, body) AGAINST ('database performance' IN NATURAL LANGUAGE MODE);

7. Connection Management

Database connections are expensive resources. Improper management is a top cause of production outages.

7.1 Connection Lifecycle Cost

7.2 Connection Pooling Architecture

7.3 Pooling Modes

7.4 PgBouncer Configuration

# pgbouncer.ini
[databases]
mydb = host=db.internal port=5432 dbname=production

[pgbouncer]
listen_addr = 0.0.0.0
listen_port = 6432
auth_type = md5
auth_file = /etc/pgbouncer/userlist.txt

pool_mode = transaction  ← Most common
max_client_conn = 10000   ← Clients can connect
default_pool_size = 25    ← Connections per database
reserve_pool_size = 5     ← Emergency connections
reserve_pool_timeout = 3  ← Wait 3s for reserve pool

server_lifetime = 3600    ← Reconnect after 1h (handles failovers)
server_idle_timeout = 600 ← Close idle connections after 10min

7.5 HikariCP Configuration (Java)

// High-performance JDBC connection pool
HikariConfig config = new HikariConfig();
config.setJdbcUrl("jdbc:postgresql://db.internal:5432/production");
config.setUsername("app_user");
config.setPassword("secret");

config.setMaximumPoolSize(25);        // Total connections in pool
config.setMinimumIdle(5);             // Idle connections kept alive
config.setConnectionTimeout(30000);   // 30s wait for connection
config.setIdleTimeout(600000);        // 10min idle before close
config.setMaxLifetime(1800000);       // 30min max connection lifetime

// Performance tuning
config.addDataSourceProperty("cachePrepStmts", "true");
config.addDataSourceProperty("prepStmtCacheSize", "250");
config.addDataSourceProperty("prepStmtCacheSqlLimit", "2048");

HikariDataSource ds = new HikariDataSource(config);

7.6 Max Connections Formula

-- PostgreSQL: Check current connections
SELECT count(*), state FROM pg_stat_activity GROUP BY state;

   count |        state
  -------+---------------------
       3 | idle
      12 | active
       1 | idle in transaction  ← Long idle transactions block VACUUM!

-- Kill idle transactions
SELECT pg_terminate_backend(pid)
FROM pg_stat_activity
WHERE state = 'idle in transaction'
  AND state_change < now() - interval '10 minutes';

7.7 Prepared Statements with Pooling

-- Problem: Prepared statements are per-connection session
-- Transaction pooling switches clients between connections
-- Solution: Disable server-side prepared statements

-- PgBouncer: Forces clients to use simple query protocol
# Set in pgbouncer.ini
ignore_startup_parameters = extra_float_digits

-- Application side (Java/JDBC)
# Disable server-side prepared statements
prepareThreshold=0

-- Or use PgBouncer in session mode if prepared statements are critical

8. Vacuum & Maintenance (PostgreSQL)

MVCC creates dead tuples that must be cleaned up. Vacuum is critical for performance and preventing transaction ID wraparound.

8.1 Why Vacuum is Needed

8.2 Vacuum vs Vacuum Full

8.3 Autovacuum Configuration

-- postgresql.conf
autovacuum = on  # Default
autovacuum_max_workers = 3  # Parallel vacuum workers
autovacuum_naptime = 60s    # Check interval

# Trigger vacuum when:
# dead_tuples > autovacuum_vacuum_threshold + autovacuum_vacuum_scale_factor * total_tuples
autovacuum_vacuum_threshold = 50       # Minimum dead tuples
autovacuum_vacuum_scale_factor = 0.2   # 20% of table size

# Example: 1M row table
# Trigger when dead_tuples > 50 + 0.2 * 1,000,000 = 200,050 dead tuples

# For high-write tables, make vacuuming more aggressive
ALTER TABLE orders SET (autovacuum_vacuum_scale_factor = 0.05);  # Vacuum at 5% dead

8.4 Monitoring Vacuum

-- Check last vacuum time and dead tuples
SELECT schemaname, relname,
       n_dead_tup,
       n_live_tup,
       round(100.0 * n_dead_tup / NULLIF(n_live_tup + n_dead_tup, 0), 2) AS dead_pct,
       last_vacuum,
       last_autovacuum
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY n_dead_tup DESC;

-- Check table bloat
SELECT schemaname, tablename,
       pg_size_pretty(pg_total_relation_size(schemaname||'.'||tablename)) AS size,
       round(100.0 * n_dead_tup / NULLIF(n_live_tup, 0), 2) AS bloat_pct
FROM pg_stat_user_tables
WHERE n_dead_tup > n_live_tup * 0.1  -- >10% dead
ORDER BY pg_total_relation_size(schemaname||'.'||tablename) DESC;

8.5 Transaction ID Wraparound

-- Check age of oldest unfrozen transaction
SELECT datname, age(datfrozenxid),
       current_setting('autovacuum_freeze_max_age')::int AS freeze_max_age
FROM pg_database
ORDER BY age(datfrozenxid) DESC;

-- Warning if age > 1.5 billion (critical at 2 billion)
-- Database will force emergency vacuum and refuse writes if it reaches 2B

8.6 ANALYZE for Statistics

-- VACUUM reclaims space, ANALYZE updates statistics for query planner
VACUUM ANALYZE orders;  -- Both operations

-- When to ANALYZE:
-- - After bulk INSERT/UPDATE/DELETE
-- - Query plans seem wrong (wrong join algorithm, bad cardinality estimates)
-- - After changing data distribution significantly

-- Auto-analyze triggers (separate from autovacuum)
-- Runs when: changed_tuples > analyze_threshold + analyze_scale_factor * total_tuples
autovacuum_analyze_threshold = 50
autovacuum_analyze_scale_factor = 0.1  # 10% of table

8.7 REINDEX

-- Indexes become bloated too (especially on frequently updated columns)
-- REINDEX rebuilds index from scratch

-- Check index bloat
SELECT schemaname, tablename, indexname,
       pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

-- Rebuild single index (locks table)
REINDEX INDEX CONCURRENTLY idx_orders_user_id;  -- CONCURRENTLY avoids blocking

-- Rebuild all indexes on table
REINDEX TABLE CONCURRENTLY orders;

-- Rebuild entire database (requires downtime)
REINDEX DATABASE production;

9. PostgreSQL vs MySQL

Both are production-grade, but architectural differences matter for system design decisions.

9.1 Architecture Comparison

9.2 Replication Architecture

9.3 Index Differences

9.4 Performance Characteristics

9.5 Feature Comparison

9.6 Migration Gotchas

-- PostgreSQL → MySQL
-- 1. Auto-increment syntax
PostgreSQL: id SERIAL PRIMARY KEY
MySQL:      id INT AUTO_INCREMENT PRIMARY KEY

-- 2. String comparison
PostgreSQL: Case-sensitive by default
MySQL:      Case-insensitive by default (depends on collation)

-- 3. Boolean type
PostgreSQL: BOOLEAN (true/false)
MySQL:      TINYINT(1) (0/1)

-- 4. LIMIT/OFFSET
PostgreSQL: LIMIT 10 OFFSET 20
MySQL:      LIMIT 20, 10  (offset, count) — confusing!

-- 5. Sequences
PostgreSQL: CREATE SEQUENCE, nextval('seq')
MySQL:      AUTO_INCREMENT only, or emulate with separate table

-- 6. RETURNING clause
PostgreSQL: INSERT ... RETURNING id
MySQL:      LAST_INSERT_ID() function

9.7 When to Choose Which

10. Scaling Relational Databases

Relational databases can scale to millions of QPS with proper techniques. Understand the trade-offs.

10.1 Scaling Strategies Overview

10.2 Read Replicas

-- Application pattern: Route reads to replicas
class DatabaseRouter:
    def get_connection(self, operation):
        if operation == 'write':
            return primary_db_connection()
        else:
            return random.choice([replica1, replica2, replica3])

# Django example
class ReplicaRouter:
    def db_for_read(self, model, **hints):
        return 'replica'
    def db_for_write(self, model, **hints):
        return 'primary'

10.3 Replication Lag Handling

-- Read your writes pattern
def update_profile(user_id, name):
    primary_db.execute("UPDATE users SET name = %s WHERE id = %s", (name, user_id))
    # Critical: Read from primary after write
    return primary_db.query("SELECT * FROM users WHERE id = %s", (user_id,))

def list_all_users():
    # Eventually consistent, can read from replica
    return replica_db.query("SELECT * FROM users")

10.4 Caching Layer

-- Cache-aside pattern (most common)
def get_user(user_id):
    cache_key = f"user:{user_id}"
    user = cache.get(cache_key)
    if user is None:
        user = db.query("SELECT * FROM users WHERE id = %s", (user_id,))
        cache.set(cache_key, user, ttl=3600)  # 1 hour TTL
    return user

-- Invalidation strategies
def update_user(user_id, name):
    db.execute("UPDATE users SET name = %s WHERE id = %s", (name, user_id))
    cache.delete(f"user:{user_id}")  # Invalidate on write

10.5 Partitioning (Within Single Database)

-- PostgreSQL: Range partitioning by date
CREATE TABLE orders (
    id BIGSERIAL,
    user_id INT,
    created_at TIMESTAMP,
    total DECIMAL
) PARTITION BY RANGE (created_at);

CREATE TABLE orders_2025_01 PARTITION OF orders
    FOR VALUES FROM ('2025-01-01') TO ('2025-02-01');

CREATE TABLE orders_2025_02 PARTITION OF orders
    FOR VALUES FROM ('2025-02-01') TO ('2025-03-01');

-- Query optimizer automatically selects partition
SELECT * FROM orders WHERE created_at BETWEEN '2025-01-15' AND '2025-01-20';
-- Scans only orders_2025_01 partition

-- Benefits:
-- 1. Drop old partitions instantly (vs slow DELETE)
-- 2. Index only recent partitions (smaller indexes)
-- 3. Parallel scans across partitions

10.6 Sharding (Application-Level)

-- Sharding function
def get_shard(user_id, num_shards=4):
    return user_id % num_shards

def get_user_orders(user_id):
    shard_id = get_shard(user_id)
    db = shard_connections[shard_id]
    return db.query("SELECT * FROM orders WHERE user_id = %s", (user_id,))

-- Works great for single-shard queries
-- Problem: Cross-shard queries are hard/slow
def get_all_orders_by_status(status):
    results = []
    for shard_db in shard_connections:
        results.extend(shard_db.query("SELECT * FROM orders WHERE status = %s", (status,)))
    return results  # Must merge and sort in application!

10.7 Sharding Challenges

10.8 Materialized Views

-- Expensive query: Top selling products
SELECT p.id, p.name, SUM(li.quantity) AS total_sold
FROM products p
JOIN line_items li ON p.id = li.product_id
JOIN orders o ON li.order_id = o.id
WHERE o.created_at > now() - interval '30 days'
GROUP BY p.id, p.name
ORDER BY total_sold DESC
LIMIT 100;

-- Create materialized view (pre-computed result)
CREATE MATERIALIZED VIEW top_products_30d AS
SELECT p.id, p.name, SUM(li.quantity) AS total_sold
FROM products p
JOIN line_items li ON p.id = li.product_id
JOIN orders o ON li.order_id = o.id
WHERE o.created_at > now() - interval '30 days'
GROUP BY p.id, p.name
ORDER BY total_sold DESC
LIMIT 100;

CREATE INDEX ON top_products_30d (total_sold DESC);

-- Query is now instant
SELECT * FROM top_products_30d;

-- Refresh periodically (can be concurrent in PostgreSQL)
REFRESH MATERIALIZED VIEW CONCURRENTLY top_products_30d;

10.9 Scaling Limits

11. When NOT to Use Relational Databases

Relational databases are not a silver bullet. Recognize when other systems are better.

11.1 Alternative Database Types

11.2 Decision Tree

11.3 When Relational Databases Struggle

11.4 Example: Social Network Friend Graph

-- Relational DB: Friends as edges in a table
CREATE TABLE friendships (
    user_id INT,
    friend_id INT,
    PRIMARY KEY (user_id, friend_id)
);

-- Query: Friends of friends (2 hops)
SELECT DISTINCT f2.friend_id
FROM friendships f1
JOIN friendships f2 ON f1.friend_id = f2.user_id
WHERE f1.user_id = 123;

-- Problems:
-- 1. Expensive join for each hop
-- 2. 3+ hops become very slow
-- 3. Hard to find shortest path, centrality, communities

-- Graph DB (Neo4j): Natural representation
CREATE (alice:User {id: 123, name: 'Alice'})
CREATE (bob:User {id: 456, name: 'Bob'})
CREATE (alice)-[:FRIENDS_WITH]->(bob)

-- Query: Friends of friends (2 hops)
MATCH (alice:User {id: 123})-[:FRIENDS_WITH*2]-(fof)
RETURN DISTINCT fof;

-- Benefits:
-- - Constant time per hop (follows pointers)
-- - Variable-length paths efficient
-- - Built-in algorithms (shortest path, PageRank)

11.5 Example: Product Catalog with Varying Attributes

-- Relational DB: EAV anti-pattern (Entity-Attribute-Value)
CREATE TABLE products (id INT, name TEXT);
CREATE TABLE product_attributes (
    product_id INT,
    attribute_name TEXT,
    attribute_value TEXT
);

-- Query: Products with RAM=16GB AND Storage=512GB
SELECT p.* FROM products p
WHERE EXISTS (
    SELECT 1 FROM product_attributes pa1
    WHERE pa1.product_id = p.id AND pa1.attribute_name = 'RAM' AND pa1.attribute_value = '16GB'
) AND EXISTS (
    SELECT 1 FROM product_attributes pa2
    WHERE pa2.product_id = p.id AND pa2.attribute_name = 'Storage' AND pa2.attribute_value = '512GB'
);
-- Very slow! Multiple EXISTS subqueries

-- Document DB (MongoDB): Nested attributes
{
  "_id": 123,
  "name": "MacBook Pro",
  "attributes": {
    "RAM": "16GB",
    "Storage": "512GB",
    "Color": "Space Gray"
  }
}

// Query: Simple dot notation
db.products.find({
  "attributes.RAM": "16GB",
  "attributes.Storage": "512GB"
});

-- PostgreSQL JSONB: Best of both worlds
CREATE TABLE products (
    id SERIAL PRIMARY KEY,
    name TEXT,
    attributes JSONB
);

CREATE INDEX ON products USING GIN (attributes);

SELECT * FROM products
WHERE attributes @> '{"RAM": "16GB", "Storage": "512GB"}';

11.6 Polyglot Persistence

Use the right tool for each use case within the same application:

• PostgreSQL: Core transactional data (users, orders, payments)
• Redis: Session store, cache, rate limiting, real-time leaderboards
• Elasticsearch: Product search, log analysis, autocomplete
• S3: File storage, backups, static assets
• Cassandra: Activity feed, time-series metrics

Summary

Interview Checklist