Compare B+ Tree, Hash, GIN (Generalized Inverted Index), GiST, BRIN, and LSM-Tree (Log-Structured Merge-Tree) indexes.

1. **B+ Tree**: Default for equality `=`, ranges ` , BETWEEN`, `ORDER BY`, prefix `LIKE 'abc%'`. 2. **Hash**: $O(1)$ equality `=` only (no range or sorting). 3. **GIN** (Generalized Inverted Index): Maps each element inside composite values (`JSONB`, arrays, full-text search `tsvector` tokens, `pg_trgm` trigrams for `LIKE '%sub%'`) to posting lists of row IDs. 4. **GiST**: Balanced tree for 2D PostGIS geometries (`R-Tree`), range types, and exclusion constraints. 5. **BRIN** (Block Range Index): Tiny index storing only `(min, max)` per 128-page disk block for huge append-only time-series tables. 6. **LSM-Tree** (RocksDB, Cassandra, Bigtable): Buffers writes in an in-memory `MemTable` + WAL and flushes immutable sorted `SSTables` with background compaction—trading read amplification (mitigated by Bloom Filters) for ultra-fast sequential write throughput.

How do `LAG(col, offset, default)` and `LEAD(col, offset, default)` solve time-series comparison problems (e.g., `Rising Temperature` `LC 197`, YoY growth, session durations)?

`LAG(val, 1, 0) OVER (PARTITION BY user_id ORDER BY event_date)` accesses the row `1` position BEFORE the current row within the partition without needing a self-join; `LEAD(val, 1) OVER (...)` accesses the row `1` position AFTER the current row. Note: If a table can have missing calendar dates (e.g., `Rising Temperature` `LC 197` where `2026-05-01` is followed by `2026-05-03`), `LAG(temperature, 1)` looks at the previous *row*, not strictly yesterday's *date*—so check `DATEDIFF(recordDate, LAG(recordDate) OVER (ORDER BY recordDate)) = 1`!

In `EXPLAIN (ANALYZE, BUFFERS)` output, compare `Seq Scan`, `Index Scan`, `Index Only Scan`, and `Bitmap Heap Scan`.

1. `Seq Scan`: Reads every page of the table sequentially from disk/cache (optimal when fetching $>10–20\%$ of table rows, because sequential I/O is much faster than random I/O). 2. `Index Scan`: Walks the B+ Tree and performs random I/O to fetch each matching heap page (best for high selectivity returning few rows). 3. `Index Only Scan`: Reads all columns directly from the index leaf pages without touching the heap (when the Visibility Map confirms pages are all-visible). 4. `Bitmap Heap Scan`: For medium selectivity (or combining multiple indexes via `BitmapAnd`/`BitmapOr`)—scans the index first to build an in-memory bitmap of matching page numbers, sorts the page numbers, and reads the heap pages in sequential disk order!

Explain the structure of a `WITH RECURSIVE` Common Table Expression (CTE) in SQL and how to prevent infinite loops on cyclic graphs.

A `WITH RECURSIVE` CTE has two parts joined by `UNION ALL` (or `UNION`): 1. **Anchor Member**: Base query executing once (e.g., `SELECT id, manager_id, 1 AS depth FROM employees WHERE manager_id IS NULL`); 2. **Recursive Member**: References the CTE name itself, joining against the working table from the previous iteration until an iteration returns 0 rows. To prevent infinite loops on cyclic graphs, either add a depth cap (`WHERE depth < 20`), track visited IDs in an array (`WHERE NOT id = ANY(path)`), or use PostgreSQL 14+'s built-in `CYCLE id SET is_cycle USING path` clause.

How do you write the classic 'Top N Per Group' query (e.g., `Department Top Three Salaries`, `LeetCode 185`) and 'Second Highest Salary' (`LC 176` returning `NULL` if missing)?

Top 3 Salaries per Department (`LC 185`): `WITH ranked AS (SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary, DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS rnk FROM Employee e JOIN Department d ON e.departmentId = d.id) SELECT Department, Employee, Salary FROM ranked WHERE rnk <= 3;`. For `Second Highest Salary` (`LC 176`) returning `NULL` when `< 2` distinct salaries exist: wrap the query as a scalar subquery `SELECT (SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1) AS SecondHighestSalary;` (or use `MAX(salary)`).

Compare Clustered Indexes (MySQL InnoDB Primary Key) and Heap Tables with Secondary Indexes (PostgreSQL).

In **MySQL InnoDB**, every table IS physically organized as a **Clustered Index** B+ Tree sorted by the Primary Key (`PRIMARY KEY` leaf nodes ARE the actual table data rows!). Any secondary index in InnoDB stores the secondary key plus the **Primary Key value** (not a physical page pointer)—so a secondary index lookup that isn't covered requires a second B+ Tree traversal down the Primary Key tree ('bookmark lookup'). In **PostgreSQL**, all tables are unsorted **Heap files**, and ALL indexes (including the Primary Key!) are secondary B+ Trees pointing directly to physical 6-byte tuple IDs `ctid = (page_number, slot_number)`.

Define the four **ACID** properties of database transactions and how the storage engine enforces each under the hood.

1. **Atomicity** ('All or nothing'): Enforced via the **Undo Log** (MySQL) or **MVCC tuple headers + clog** (Postgres) so aborted transactions roll back completely. 2. **Consistency**: Every transaction brings the database from one valid state to another preserving all declared constraints (`PRIMARY KEY`, `FOREIGN KEY`, `UNIQUE`, `CHECK`, triggers) and application invariants. 3. **Isolation**: Concurrent transactions do not corrupt each other's intermediate states, enforced via **MVCC (Multi-Version Concurrency Control)** and Locks/SSI. 4. **Durability**: Once `COMMIT` returns success, data survives power loss, enforced via **Write-Ahead Logging (WAL / Redo Log)** flushed (`fsync`) to disk before acknowledging commit.

Explain the 'Gaps and Islands' SQL pattern (`Consecutive Numbers` `LC 180`, finding start/end of contiguous streaks of daily logins).

Key mathematical invariant: If a sequence of dates or integers increases by 1 (`2026-05-01, 05-02, 05-03`) and `ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date)` also increases by 1 (`1, 2, 3`), then their **difference** (`login_date - INTERVAL '1 day' * ROW_NUMBER()...` or `id - ROW_NUMBER()...`) is **CONSTANT across every row belonging to the same contiguous island**, and jumps whenever there is a gap! Group by `(user_id, island_grp)` and select `MIN(login_date) AS start_date, MAX(login_date) AS end_date, COUNT(*) AS streak_len`.

In a `LEFT JOIN`, what is the critical difference between placing a filter condition on the right table inside the `ON` clause vs. inside the `WHERE` clause?

1. Filter in `ON` (`FROM users u LEFT JOIN orders o ON u.id = o.user_id AND o.year = 2026`): The predicate is evaluated *before/during* the outer join—all users are STILL returned, with `NULL`s for users who placed no orders in 2026. 2. Filter in `WHERE` (`... LEFT JOIN orders o ON u.id = o.user_id WHERE o.year = 2026`): `WHERE` filters *after* the join; since `NULL = 2026` evaluates to `UNKNOWN` (falsy), all unmatched `NULL`-padded rows are filtered out, silently turning your `LEFT JOIN` into an `INNER JOIN`!

What is the default Window Frame in SQL when `ORDER BY` is present inside `OVER (PARTITION BY ... ORDER BY ...)`, and why does `LAST_VALUE()` surprise developers?

When `ORDER BY` is specified inside `OVER (...)` without an explicit frame clause, the SQL standard default frame is **`RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`** (NOT the whole partition!). Therefore, `SUM(amount) OVER (ORDER BY dt)` automatically computes a running total, AND `LAST_VALUE(amount) OVER (ORDER BY dt)` simply returns the `CURRENT ROW`'s value! To get the true last value of the entire partition with `LAST_VALUE`, you must explicitly specify `ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING`.

Why does a relational database use a **B+ Tree** (rather than a Binary Search Tree or standard B-Tree) for disk-based indexes?

Disk/SSD I/O reads data in fixed-size pages (e.g., `8 KB` in PostgreSQL, `16 KB` in MySQL InnoDB). A Binary Search Tree has fan-out 2 ($\log_2(10^9) \approx 30$ random pointer jumps across disk pages). A **B+ Tree** has a high branching factor/fan-out of ~500–1,000 keys per internal page (so a 3-to-4 level B+ Tree indexes billions of rows with internal nodes cached in RAM!). Unlike a classic B-Tree (which stores data payloads inside internal nodes, reducing fan-out), a **B+ Tree stores ONLY routing keys in internal nodes and stores all data/row pointers in Leaf Nodes linked in a doubly linked list**, making range scans (`BETWEEN`, `>`, `ORDER BY`) sequential leaf scans!

Compare `ROW_NUMBER()`, `RANK()`, `DENSE_RANK()`, and `NTILE(k)` Window Functions when ranking values `[100, 90, 90, 80]`.

`ROW_NUMBER()`: Assigns unique sequential integers with arbitrary tie-breaking: `1, 2, 3, 4`. `RANK()`: Assigns the same rank to ties, then skips ranks (`olympic medal style`): `1, 2, 2, 4`. `DENSE_RANK()`: Assigns the same rank to ties WITHOUT skipping any subsequent integer ranks: `1, 2, 2, 3` (always use `DENSE_RANK()` for 'Nth Highest Salary' problems (`LeetCode 177`/`185`) when distinct salary levels are requested!). `NTILE(k)`: Divides ordered partition into `k` roughly equal buckets (quartiles/deciles).

What makes a SQL predicate **SARGable** (Search Argument Able) vs. Non-SARGable, with concrete query rewrite examples?

A predicate is **Non-SARGable** if you wrap an indexed column inside a function, arithmetic expression, or leading wildcard, which prevents the query optimizer from seeking in the B+ Tree and forces a full scan: 1. Bad: `WHERE YEAR(created_at) = 2026` $\to$ **Good**: `WHERE created_at >= '2026-01-01' AND created_at 100` $\to$ **Good**: `WHERE price > 100 / 1.1`; 4. Bad: `WHERE name LIKE '%smith'` (leading `%`).

Compare the three Physical Join Algorithms used by SQL query optimizers: `Nested Loop Join`, `Hash Join`, and `Sort-Merge Join`.

1. **Nested Loop Join**: For each row in the outer table ($M$), scans or probes an index on the inner table ($N$); $O(M \cdot N)$ naive or $O(M \log N)$ with an inner index—best when outer input $M$ is very small and inner join key is indexed, and the ONLY join supporting arbitrary non-equality predicates (`ON a.x < b.y`). 2. **Hash Join**: Builds an in-memory Hash Table on the smaller (`Build`) input in $O(M)$ and streams the larger (`Probe`) input in $O(N)$—$O(M + N)$ time for equality joins (`=`), spills to disk batches if exceeding `work_mem`. 3. **Sort-Merge Join**: Sorts both inputs on the join key (or reads pre-sorted B+ Tree indexes) and merges them in one linear pass—ideal when inputs are already sorted or huge.

How do you calculate the Exact Median in SQL using Window Functions (`Median Employee Salary`, `LeetCode 569`)?

In a CTE, compute both `rn = ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id)` and `cnt = COUNT(*) OVER (PARTITION BY company)`. For both odd and even partition sizes $N$, the middle one or two rows satisfy **`WHERE rn BETWEEN cnt / 2.0 AND cnt / 2.0 + 1`** (e.g., for $N=4$, `rn BETWEEN 2.0 AND 3.0` selects rows `2` and `3`; for $N=5$, `rn BETWEEN 2.5 AND 3.5` selects row `3`)! Alternatively in PostgreSQL/Oracle, use the ordered-set aggregate `PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY salary)`.

What is a Partial (Filtered) Index in PostgreSQL/SQL Server and when is it dramatically more efficient than a full index?

A Partial Index includes a `WHERE` clause in the index definition itself: `CREATE INDEX idx_unpaid_orders ON orders (created_at) WHERE status = 'PENDING';` (or `CREATE UNIQUE INDEX idx_active_email ON users (email) WHERE deleted_at IS NULL;` to enforce uniqueness only among non-soft-deleted users!). If 99.5% of historical orders are `'COMPLETED'` and only 0.5% are `'PENDING'`, the partial index is 200x smaller in RAM and isn't even updated when completed orders are modified!

What is a Covering Index (`Index-Only Scan`) and what does the `INCLUDE (col1, col2)` clause do?

A **Covering Index** contains every single column required by a query's `SELECT`, `WHERE`, and `JOIN` clauses inside the index leaf pages, allowing the database to satisfy the query purely from the index (`Index Only Scan`) without ever fetching pages from the main table Heap/Clustered Index! Adding non-filter payload columns via `CREATE INDEX idx ON orders (customer_id, order_date) INCLUDE (total_amount)` stores `total_amount` ONLY in the B+ Tree leaf nodes (excluding it from internal routing nodes so internal tree fan-out stays small and fast).

Explain the infamous `NOT IN` NULL Trap in SQLthree-valued logic (`TRUE`, `FALSE`, `UNKNOWN`), and why `NOT EXISTS` or `LEFT JOIN ... WHERE id IS NULL` is safer.

`WHERE x NOT IN (1, 2, NULL)` expands logically to `x != 1 AND x != 2 AND x != NULL`. In SQL 3-valued logic, `x != NULL` evaluates to `UNKNOWN`, and `TRUE AND UNKNOWN` evaluates to `UNKNOWN`—so **`NOT IN` returns ZERO rows whenever the subquery contains even a single `NULL` value**! By contrast, `WHERE NOT EXISTS (SELECT 1 FROM b WHERE b.id = a.id)` and `LEFT JOIN b ON a.id = b.id WHERE b.id IS NULL` (Anti-Join) safely ignore `NULL`s in `b` and often optimize to an efficient Hash Anti-Join.

How does Multi-Version Concurrency Control (**MVCC**) allow `Readers never block Writers, and Writers never block Readers` in PostgreSQL vs. MySQL InnoDB?

Instead of overwriting rows in-place under read locks, MVCC maintains multiple timestamped/transaction-ID versions of rows: In **PostgreSQL**, every `UPDATE` writes a brand-new physical tuple version in the heap setting `xmin` (creating xact ID) on the new tuple and `xmax` (deleting xact ID) on the old tuple; each transaction uses a Transaction Snapshot to read whichever tuple version was committed at snapshot time, and dead tuples are cleaned up later by `AUTOVACUUM`. In **MySQL InnoDB**, updates modify the Clustered Index page in-place and write prior values to a rollback **Undo Log** segment so older snapshots reconstruct historical versions from the Undo chain.

Compare `INNER JOIN`, `LEFT OUTER JOIN`, `FULL OUTER JOIN`, `CROSS JOIN`, and `LATERAL JOIN` (`CROSS/OUTER APPLY`).

`INNER JOIN`: Returns only rows with matching keys in both tables. `LEFT JOIN`: Returns all rows from the left table, filling `NULL`s for right-table columns when no match exists. `FULL OUTER JOIN`: Returns matched rows plus unmatched rows from both left and right tables (`NULL`-padded). `CROSS JOIN`: Cartesian product ($M \times N$ rows). `LATERAL JOIN` (PostgreSQL `JOIN LATERAL`, SQL Server `CROSS/OUTER APPLY`): Like a correlated `for-each` loop—allows the right-side subquery to reference columns from the left-side table row-by-row (e.g., fetching the top 3 latest orders per customer).

Map the four ANSI SQL Transaction Isolation Levels (`Read Uncommitted`, `Read Committed`, `Repeatable Read`, `Serializable`) to the anomalies they prevent.

1. `Read Uncommitted`: Allows Dirty Reads, Non-Repeatable Reads, and Phantoms (Note: PostgreSQL treats `Read Uncommitted` as `Read Committed` and never allows Dirty Reads). 2. `Read Committed` (Default in PostgreSQL, Oracle, SQL Server): Prevents Dirty Reads; each statement inside a transaction sees a fresh snapshot committed right before that statement begins. 3. `Repeatable Read` (Default in MySQL InnoDB): Prevents Dirty Reads and Non-Repeatable Reads (and in PostgreSQL Snapshot Isolation / InnoDB Next-Key Locking, also prevents Phantom Reads, though Write Skew is still possible in Postgres `Repeatable Read`!). 4. `Serializable`: Prevents ALL concurrency anomalies (including Write Skew) via Serializable Snapshot Isolation (SSI) or 2PL.

Compare `ROWS BETWEEN` and `RANGE BETWEEN` in SQL Window Frame clauses, and show how to compute a 7-day rolling average.

`ROWS BETWEEN 6 PRECEDING AND CURRENT ROW` counts strictly by **physical row offsets** (the current row plus the 6 physical rows immediately before it—if 2 days had no data, it spans 9 calendar days!). `RANGE BETWEEN INTERVAL '6 days' PRECEDING AND CURRENT ROW` bounds the window by **logical value distance** in the `ORDER BY` column (all rows whose date falls within `[current_date - 6 days, current_date]`, also grouping duplicate peer timestamps together).

Explain the **Leftmost Prefix Rule** for a Composite B+ Tree Index `INDEX (a, b, c)` and which `WHERE` / `ORDER BY` clauses can or cannot use it.

A composite index on `(a, b, c)` sorts rows first by `a`, then ties in `a` by `b`, then ties in `(a, b)` by `c`. Therefore, it efficiently supports queries filtering on: `(a)`, `(a, b)`, or `(a, b, c)`. It **CANNOT** use the index tree order for `WHERE b = 2 AND c = 3` (missing leading column `a`, unless the DB supports an Index Skip Scan on low-cardinality `a`). Furthermore, if a range predicate is used on an earlier column (`WHERE a = 1 AND b > 5 AND c = 10`), the index scan uses `a` and `b`, but **`c` cannot be used for index range matching** because across different values of `b > 5`, `c` is no longer globally sorted!

Compare First Normal Form (`1NF`), Second Normal Form (`2NF`), Third Normal Form (`3NF` / `BCNF`), and Strategic Denormalization.

1. `1NF`: Atomic column values (no comma-separated lists in a string column) and a primary key. 2. `2NF`: `1NF` + no **Partial Dependencies** (every non-key attribute depends on the *entire* composite primary key, not just part of it). 3. `3NF` / `BCNF`: `2NF` + no **Transitive Dependencies** (`A -> B -> C` where a non-key column determines another non-key column; 'every non-key attribute depends on the key, the whole key, and nothing but the key, so help me Codd'). Normalization eliminates update/delete anomalies and write redundancy in OLTP, whereas OLAP star schemas (`Fact` + `Dimension` tables) intentionally denormalize to avoid expensive multi-table joins.

What is the exact Logical Query Processing (Execution) Order of SQL clauses, and why can't you reference a `SELECT` alias inside `WHERE`?

1. `FROM` & `JOIN` (with `ON` predicates); 2. `WHERE` (filters individual rows); 3. `GROUP BY` (buckets rows into groups); 4. Aggregate Functions (`COUNT`, `SUM`, `AVG`); 5. `HAVING` (filters aggregated groups); 6. Window Functions (`OVER (...)`); 7. `SELECT` (projects columns and creates aliases); 8. `DISTINCT`; 9. `UNION` / `INTERSECT` / `EXCEPT`; 10. `ORDER BY` (can use `SELECT` aliases!); 11. `OFFSET` & `LIMIT` / `FETCH`. Because `WHERE` (step 2) executes long BEFORE `SELECT` (step 7), aliases defined in `SELECT` do not exist yet during `WHERE` evaluation (and Window Functions cannot be used directly in `WHERE`/`HAVING` without a CTE/subquery!).

Define the four classic Concurrency Anomalies in databases: `Dirty Read`, `Non-Repeatable Read`, `Phantom Read`, and `Write Skew` (`Lost Update`).

1. **Dirty Read**: Transaction $T_1$ reads uncommitted changes written by $T_2$ (which $T_2$ might later `ROLLBACK`!). 2. **Non-Repeatable Read** (Read Skew): $T_1$ reads the same row twice and gets different values because $T_2$ updated and committed that row in between. 3. **Phantom Read**: $T_1$ runs the same `WHERE` range query twice and sees new or missing rows ('phantoms') because $T_2$ inserted or deleted matching rows and committed. 4. **Write Skew**: Two transactions $T_1$ and $T_2$ read overlapping data under Snapshot Isolation (e.g., verifying $\ge 2$ doctors are on call), and each modifies a *disjoint* row (Doctor A and Doctor B both go off call simultaneously), violating the multi-row invariant!

Compare Keyset (Cursor / Seek) Pagination against `OFFSET / LIMIT` Pagination on a 100-million-row table.

With `SELECT * FROM events ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 10000000`, the database MUST scan, sort/walk, and discard all `10,000,000` preceding rows before returning 20 rows ($O(\text{offset})$ time, getting slower on deeper pages and skipping/duplicating rows if new inserts occur!). **Keyset / Cursor Pagination** passes the last seen `(created_at, id)` from the previous page: `WHERE (created_at, id) < ('2026-11-01 12:00:00', 98412) ORDER BY created_at DESC, id DESC LIMIT 20`—seeking directly into the composite B+ Tree index `(created_at, id)` in constant $O(\log N)$ time even at page 500,000!

Compare Pessimistic Locking (`SELECT ... FOR UPDATE` / `FOR SHARE`) and Optimistic Concurrency Control (`version` column CAS) for preventing Lost Updates.

1. **Pessimistic Locking**: Acquire an exclusive row-level lock when reading (`SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;`); concurrent writers trying to lock row `1` block until your transaction commits—best when contention is high and transactions are short/in-DB. 2. **Optimistic Concurrency Control (OCC)**: Read row without locking along with `version = 5`; when updating, run Compare-And-Swap (`UPDATE accounts SET balance = 90, version = 6 WHERE id = 1 AND version = 5;`) and check if `affected_rows == 1` (retrying if `0`)—best when conflicts are rare or state is held across user HTTP round-trips.

How does `SELECT ... FOR UPDATE SKIP LOCKED` allow building a high-concurrency Job Queue inside PostgreSQL or MySQL 8+?

If 50 worker threads run plain `SELECT id FROM jobs WHERE status = 'PENDING' ORDER BY id LIMIT 1 FOR UPDATE`, 49 workers will block waiting on the exact same row #1! Adding **`SKIP LOCKED`** (`... LIMIT 1 FOR UPDATE SKIP LOCKED`) instructs the database engine to immediately skip over any rows currently locked by other active transactions and lock the next available unlocked `'PENDING'` row—allowing all 50 workers to dequeue 50 distinct jobs in parallel with zero lock wait contention!

How do you write a Pivot / Conditional Aggregation query in SQL (`COUNT(*) FILTER (WHERE ...)` vs `SUM(CASE WHEN ...)`), and how do `ROLLUP`, `CUBE`, and `GROUPING SETS` work?

Conditional Aggregation pivots rows into columns in a single table scan: `SUM(CASE WHEN status = 'paid' THEN amount ELSE 0 END) AS paid_total` (or Postgres standard SQL `SUM(amount) FILTER (WHERE status = 'paid')`). `GROUP BY ROLLUP (year, quarter, month)` generates hierarchical subtotals (`(year, quarter, month)`, `(year, quarter)`, `(year)`, and grand total `()`) in one pass; `CUBE (a, b)` generates all $2^k$ dimensional combinations; `GROUPING SETS ((a), (b), ())` computes exact specified groupings.

Compare Non-Recursive CTEs (`WITH`), Materialized CTEs (`WITH x AS MATERIALIZED`), Temporary Tables, Views, and Materialized Views.

CTE (`WITH`): Query-scoped named subquery; in PostgreSQL 12+, non-recursive CTEs referenced once are inlined into the outer query by default so predicate pushdown works (use `AS MATERIALIZED` to force once-only evaluation as an optimization fence). View: Stored SQL query text with zero stored data (rewritten at query time). Materialized View: Physically persists the query result on disk and can be indexed (refreshed via `REFRESH MATERIALIZED VIEW CONCURRENTLY`, which requires a `UNIQUE` index). Temp Table: Session/transaction-scoped physical table supporting custom indexes and statistics.

What causes a Database Deadlock between two concurrent transactions, and how do you prevent it in application code?

A Deadlock occurs when Transaction $T_1$ holds an exclusive lock on Row `A` and waits for Row `B` (`UPDATE accounts WHERE id = 'A'` then `'B'`), while simultaneously Transaction $T_2$ holds an exclusive lock on Row `B` and waits for Row `A` (a cycle in the waits-for graph; the DB's deadlock detector aborts one victim transaction). Prevention: **Always acquire locks in a deterministic canonical order** (e.g., sort account IDs ascending `min(acct1, acct2)` before `max(acct1, acct2)` inside `SELECT ... WHERE id IN (101, 205) ORDER BY id FOR UPDATE`)!

SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels

Advanced SQL and Database Internals mastery for Software Engineering, Data Engineering, and Backend interviews covering SQL logical execution order, Joins, the NOT IN NULL trap, Window Functions & Frame Clauses, Recursive CTEs, B+ Tree vs LSM-Tree vs GIN indexes, EXPLAIN ANALYZE query plans, and ACID Isolation Levels & MVCC.

Level: advanced
Languages: en → en
Cards: 32
Markdown: SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Compare B+ Tree, Hash, GIN (Generalized Inverted Index), GiST, BRIN, and LSM-Tree (Log-Structured Merge-Tree) indexes.	1. B+ Tree: Default for equality `=`, ranges `<, >, BETWEEN`, `ORDER BY`, prefix `LIKE 'abc%'`. 2. Hash: $O(1)$ equality `=` only (no range or sorting). 3. GIN (Generalized Inverted Index): Maps each element inside composite values (`JSONB`, arrays, full-text search `tsvector` tokens, `pg_trgm` trigrams for `LIKE '%sub%'`) to posting lists of row IDs. 4. GiST: Balanced tree for 2D PostGIS geometries (`R-Tree`), range types, and exclusion constraints. 5. BRIN (Block Range Index): Tiny index storing only `(min, max)` per 128-page disk block for huge append-only time-series tables. 6. LSM-Tree (RocksDB, Cassandra, Bigtable): Buffers writes in an in-memory `MemTable` + WAL and flushes immutable sorted `SSTables` with background compaction—trading read amplification (mitigated by Bloom Filters) for ultra-fast sequential write throughput.
2	How do `LAG(col, offset, default)` and `LEAD(col, offset, default)` solve time-series comparison problems (e.g., `Rising Temperature` `LC 197`, YoY growth, session durations)?	`LAG(val, 1, 0) OVER (PARTITION BY user_id ORDER BY event_date)` accesses the row `1` position BEFORE the current row within the partition without needing a self-join; `LEAD(val, 1) OVER (...)` accesses the row `1` position AFTER the current row. Note: If a table can have missing calendar dates (e.g., `Rising Temperature` `LC 197` where `2026-05-01` is followed by `2026-05-03`), `LAG(temperature, 1)` looks at the previous row, not strictly yesterday's date—so check `DATEDIFF(recordDate, LAG(recordDate) OVER (ORDER BY recordDate)) = 1`!
3	In `EXPLAIN (ANALYZE, BUFFERS)` output, compare `Seq Scan`, `Index Scan`, `Index Only Scan`, and `Bitmap Heap Scan`.	1. `Seq Scan`: Reads every page of the table sequentially from disk/cache (optimal when fetching gt;10–20\%$ of table rows, because sequential I/O is much faster than random I/O). 2. `Index Scan`: Walks the B+ Tree and performs random I/O to fetch each matching heap page (best for high selectivity returning few rows). 3. `Index Only Scan`: Reads all columns directly from the index leaf pages without touching the heap (when the Visibility Map confirms pages are all-visible). 4. `Bitmap Heap Scan`: For medium selectivity (or combining multiple indexes via `BitmapAnd`/`BitmapOr`)—scans the index first to build an in-memory bitmap of matching page numbers, sorts the page numbers, and reads the heap pages in sequential disk order!
4	Explain the structure of a `WITH RECURSIVE` Common Table Expression (CTE) in SQL and how to prevent infinite loops on cyclic graphs.	A `WITH RECURSIVE` CTE has two parts joined by `UNION ALL` (or `UNION`): 1. Anchor Member: Base query executing once (e.g., `SELECT id, manager_id, 1 AS depth FROM employees WHERE manager_id IS NULL`); 2. Recursive Member: References the CTE name itself, joining against the working table from the previous iteration until an iteration returns 0 rows. To prevent infinite loops on cyclic graphs, either add a depth cap (`WHERE depth < 20`), track visited IDs in an array (`WHERE NOT id = ANY(path)`), or use PostgreSQL 14+'s built-in `CYCLE id SET is_cycle USING path` clause.
5	How do you write the classic 'Top N Per Group' query (e.g., `Department Top Three Salaries`, `LeetCode 185`) and 'Second Highest Salary' (`LC 176` returning `NULL` if missing)?	Top 3 Salaries per Department (`LC 185`): `WITH ranked AS (SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary, DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS rnk FROM Employee e JOIN Department d ON e.departmentId = d.id) SELECT Department, Employee, Salary FROM ranked WHERE rnk <= 3;`. For `Second Highest Salary` (`LC 176`) returning `NULL` when `< 2` distinct salaries exist: wrap the query as a scalar subquery `SELECT (SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1) AS SecondHighestSalary;` (or use `MAX(salary)`).
6	Compare Clustered Indexes (MySQL InnoDB Primary Key) and Heap Tables with Secondary Indexes (PostgreSQL).	In MySQL InnoDB, every table IS physically organized as a Clustered Index B+ Tree sorted by the Primary Key (`PRIMARY KEY` leaf nodes ARE the actual table data rows!). Any secondary index in InnoDB stores the secondary key plus the Primary Key value (not a physical page pointer)—so a secondary index lookup that isn't covered requires a second B+ Tree traversal down the Primary Key tree ('bookmark lookup'). In PostgreSQL, all tables are unsorted Heap files, and ALL indexes (including the Primary Key!) are secondary B+ Trees pointing directly to physical 6-byte tuple IDs `ctid = (page_number, slot_number)`.
7	Define the four ACID properties of database transactions and how the storage engine enforces each under the hood.	1. Atomicity ('All or nothing'): Enforced via the Undo Log (MySQL) or MVCC tuple headers + clog (Postgres) so aborted transactions roll back completely. 2. Consistency: Every transaction brings the database from one valid state to another preserving all declared constraints (`PRIMARY KEY`, `FOREIGN KEY`, `UNIQUE`, `CHECK`, triggers) and application invariants. 3. Isolation: Concurrent transactions do not corrupt each other's intermediate states, enforced via MVCC (Multi-Version Concurrency Control) and Locks/SSI. 4. Durability: Once `COMMIT` returns success, data survives power loss, enforced via Write-Ahead Logging (WAL / Redo Log) flushed (`fsync`) to disk before acknowledging commit.
8	Explain the 'Gaps and Islands' SQL pattern (`Consecutive Numbers` `LC 180`, finding start/end of contiguous streaks of daily logins).	Key mathematical invariant: If a sequence of dates or integers increases by 1 (`2026-05-01, 05-02, 05-03`) and `ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date)` also increases by 1 (`1, 2, 3`), then their difference (`login_date - INTERVAL '1 day' * ROW_NUMBER()...` or `id - ROW_NUMBER()...`) is CONSTANT across every row belonging to the same contiguous island, and jumps whenever there is a gap! Group by `(user_id, island_grp)` and select `MIN(login_date) AS start_date, MAX(login_date) AS end_date, COUNT(*) AS streak_len`.
9	In a `LEFT JOIN`, what is the critical difference between placing a filter condition on the right table inside the `ON` clause vs. inside the `WHERE` clause?	1. Filter in `ON` (`FROM users u LEFT JOIN orders o ON u.id = o.user_id AND o.year = 2026`): The predicate is evaluated before/during the outer join—all users are STILL returned, with `NULL`s for users who placed no orders in 2026. 2. Filter in `WHERE` (`... LEFT JOIN orders o ON u.id = o.user_id WHERE o.year = 2026`): `WHERE` filters after the join; since `NULL = 2026` evaluates to `UNKNOWN` (falsy), all unmatched `NULL`-padded rows are filtered out, silently turning your `LEFT JOIN` into an `INNER JOIN`!
10	What is the default Window Frame in SQL when `ORDER BY` is present inside `OVER (PARTITION BY ... ORDER BY ...)`, and why does `LAST_VALUE()` surprise developers?	When `ORDER BY` is specified inside `OVER (...)` without an explicit frame clause, the SQL standard default frame is `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW` (NOT the whole partition!). Therefore, `SUM(amount) OVER (ORDER BY dt)` automatically computes a running total, AND `LAST_VALUE(amount) OVER (ORDER BY dt)` simply returns the `CURRENT ROW`'s value! To get the true last value of the entire partition with `LAST_VALUE`, you must explicitly specify `ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING`.
11	Why does a relational database use a B+ Tree (rather than a Binary Search Tree or standard B-Tree) for disk-based indexes?	Disk/SSD I/O reads data in fixed-size pages (e.g., `8 KB` in PostgreSQL, `16 KB` in MySQL InnoDB). A Binary Search Tree has fan-out 2 ($\log_2(10^9) \approx 30$ random pointer jumps across disk pages). A B+ Tree has a high branching factor/fan-out of ~500–1,000 keys per internal page (so a 3-to-4 level B+ Tree indexes billions of rows with internal nodes cached in RAM!). Unlike a classic B-Tree (which stores data payloads inside internal nodes, reducing fan-out), a B+ Tree stores ONLY routing keys in internal nodes and stores all data/row pointers in Leaf Nodes linked in a doubly linked list, making range scans (`BETWEEN`, `>`, `ORDER BY`) sequential leaf scans!
12	Compare `ROW_NUMBER()`, `RANK()`, `DENSE_RANK()`, and `NTILE(k)` Window Functions when ranking values `[100, 90, 90, 80]`.	`ROW_NUMBER()`: Assigns unique sequential integers with arbitrary tie-breaking: `1, 2, 3, 4`. `RANK()`: Assigns the same rank to ties, then skips ranks (`olympic medal style`): `1, 2, 2, 4`. `DENSE_RANK()`: Assigns the same rank to ties WITHOUT skipping any subsequent integer ranks: `1, 2, 2, 3` (always use `DENSE_RANK()` for 'Nth Highest Salary' problems (`LeetCode 177`/`185`) when distinct salary levels are requested!). `NTILE(k)`: Divides ordered partition into `k` roughly equal buckets (quartiles/deciles).
13	What makes a SQL predicate SARGable (Search Argument Able) vs. Non-SARGable, with concrete query rewrite examples?	A predicate is Non-SARGable if you wrap an indexed column inside a function, arithmetic expression, or leading wildcard, which prevents the query optimizer from seeking in the B+ Tree and forces a full scan: 1. Bad: `WHERE YEAR(created_at) = 2026` $\to$ Good: `WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'`; 2. Bad: `WHERE LOWER(email) = 'a@b.com'` $\to$ Good: Create a functional/expression index `CREATE INDEX ON users (LOWER(email))`; 3. Bad: `WHERE price * 1.1 > 100` $\to$ Good: `WHERE price > 100 / 1.1`; 4. Bad: `WHERE name LIKE '%smith'` (leading `%`).
14	Compare the three Physical Join Algorithms used by SQL query optimizers: `Nested Loop Join`, `Hash Join`, and `Sort-Merge Join`.	1. Nested Loop Join: For each row in the outer table ($M$), scans or probes an index on the inner table ($N$); $O(M \cdot N)$ naive or $O(M \log N)$ with an inner index—best when outer input $M$ is very small and inner join key is indexed, and the ONLY join supporting arbitrary non-equality predicates (`ON a.x < b.y`). 2. Hash Join: Builds an in-memory Hash Table on the smaller (`Build`) input in $O(M)$ and streams the larger (`Probe`) input in $O(N)$—$O(M + N)$ time for equality joins (`=`), spills to disk batches if exceeding `work_mem`. 3. Sort-Merge Join: Sorts both inputs on the join key (or reads pre-sorted B+ Tree indexes) and merges them in one linear pass—ideal when inputs are already sorted or huge.
15	How do you calculate the Exact Median in SQL using Window Functions (`Median Employee Salary`, `LeetCode 569`)?	In a CTE, compute both `rn = ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id)` and `cnt = COUNT() OVER (PARTITION BY company)`. For both odd and even partition sizes $N$, the middle one or two rows satisfy `WHERE rn BETWEEN cnt / 2.0 AND cnt / 2.0 + 1`* (e.g., for $N=4$, `rn BETWEEN 2.0 AND 3.0` selects rows `2` and `3`; for $N=5$, `rn BETWEEN 2.5 AND 3.5` selects row `3`)! Alternatively in PostgreSQL/Oracle, use the ordered-set aggregate `PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY salary)`.
16	What is a Partial (Filtered) Index in PostgreSQL/SQL Server and when is it dramatically more efficient than a full index?	A Partial Index includes a `WHERE` clause in the index definition itself: `CREATE INDEX idx_unpaid_orders ON orders (created_at) WHERE status = 'PENDING';` (or `CREATE UNIQUE INDEX idx_active_email ON users (email) WHERE deleted_at IS NULL;` to enforce uniqueness only among non-soft-deleted users!). If 99.5% of historical orders are `'COMPLETED'` and only 0.5% are `'PENDING'`, the partial index is 200x smaller in RAM and isn't even updated when completed orders are modified!
17	What is a Covering Index (`Index-Only Scan`) and what does the `INCLUDE (col1, col2)` clause do?	A Covering Index contains every single column required by a query's `SELECT`, `WHERE`, and `JOIN` clauses inside the index leaf pages, allowing the database to satisfy the query purely from the index (`Index Only Scan`) without ever fetching pages from the main table Heap/Clustered Index! Adding non-filter payload columns via `CREATE INDEX idx ON orders (customer_id, order_date) INCLUDE (total_amount)` stores `total_amount` ONLY in the B+ Tree leaf nodes (excluding it from internal routing nodes so internal tree fan-out stays small and fast).
18	Explain the infamous `NOT IN` NULL Trap in SQLthree-valued logic (`TRUE`, `FALSE`, `UNKNOWN`), and why `NOT EXISTS` or `LEFT JOIN ... WHERE id IS NULL` is safer.	`WHERE x NOT IN (1, 2, NULL)` expands logically to `x != 1 AND x != 2 AND x != NULL`. In SQL 3-valued logic, `x != NULL` evaluates to `UNKNOWN`, and `TRUE AND UNKNOWN` evaluates to `UNKNOWN`—so `NOT IN` returns ZERO rows whenever the subquery contains even a single `NULL` value! By contrast, `WHERE NOT EXISTS (SELECT 1 FROM b WHERE b.id = a.id)` and `LEFT JOIN b ON a.id = b.id WHERE b.id IS NULL` (Anti-Join) safely ignore `NULL`s in `b` and often optimize to an efficient Hash Anti-Join.
19	How does Multi-Version Concurrency Control (MVCC) allow `Readers never block Writers, and Writers never block Readers` in PostgreSQL vs. MySQL InnoDB?	Instead of overwriting rows in-place under read locks, MVCC maintains multiple timestamped/transaction-ID versions of rows: In PostgreSQL, every `UPDATE` writes a brand-new physical tuple version in the heap setting `xmin` (creating xact ID) on the new tuple and `xmax` (deleting xact ID) on the old tuple; each transaction uses a Transaction Snapshot to read whichever tuple version was committed at snapshot time, and dead tuples are cleaned up later by `AUTOVACUUM`. In MySQL InnoDB, updates modify the Clustered Index page in-place and write prior values to a rollback Undo Log segment so older snapshots reconstruct historical versions from the Undo chain.
20	Compare `INNER JOIN`, `LEFT OUTER JOIN`, `FULL OUTER JOIN`, `CROSS JOIN`, and `LATERAL JOIN` (`CROSS/OUTER APPLY`).	`INNER JOIN`: Returns only rows with matching keys in both tables. `LEFT JOIN`: Returns all rows from the left table, filling `NULL`s for right-table columns when no match exists. `FULL OUTER JOIN`: Returns matched rows plus unmatched rows from both left and right tables (`NULL`-padded). `CROSS JOIN`: Cartesian product ($M \times N$ rows). `LATERAL JOIN` (PostgreSQL `JOIN LATERAL`, SQL Server `CROSS/OUTER APPLY`): Like a correlated `for-each` loop—allows the right-side subquery to reference columns from the left-side table row-by-row (e.g., fetching the top 3 latest orders per customer).
21	Map the four ANSI SQL Transaction Isolation Levels (`Read Uncommitted`, `Read Committed`, `Repeatable Read`, `Serializable`) to the anomalies they prevent.	1. `Read Uncommitted`: Allows Dirty Reads, Non-Repeatable Reads, and Phantoms (Note: PostgreSQL treats `Read Uncommitted` as `Read Committed` and never allows Dirty Reads). 2. `Read Committed` (Default in PostgreSQL, Oracle, SQL Server): Prevents Dirty Reads; each statement inside a transaction sees a fresh snapshot committed right before that statement begins. 3. `Repeatable Read` (Default in MySQL InnoDB): Prevents Dirty Reads and Non-Repeatable Reads (and in PostgreSQL Snapshot Isolation / InnoDB Next-Key Locking, also prevents Phantom Reads, though Write Skew is still possible in Postgres `Repeatable Read`!). 4. `Serializable`: Prevents ALL concurrency anomalies (including Write Skew) via Serializable Snapshot Isolation (SSI) or 2PL.
22	Compare `ROWS BETWEEN` and `RANGE BETWEEN` in SQL Window Frame clauses, and show how to compute a 7-day rolling average.	`ROWS BETWEEN 6 PRECEDING AND CURRENT ROW` counts strictly by physical row offsets (the current row plus the 6 physical rows immediately before it—if 2 days had no data, it spans 9 calendar days!). `RANGE BETWEEN INTERVAL '6 days' PRECEDING AND CURRENT ROW` bounds the window by logical value distance in the `ORDER BY` column (all rows whose date falls within `[current_date - 6 days, current_date]`, also grouping duplicate peer timestamps together).
23	Explain the Leftmost Prefix Rule for a Composite B+ Tree Index `INDEX (a, b, c)` and which `WHERE` / `ORDER BY` clauses can or cannot use it.	A composite index on `(a, b, c)` sorts rows first by `a`, then ties in `a` by `b`, then ties in `(a, b)` by `c`. Therefore, it efficiently supports queries filtering on: `(a)`, `(a, b)`, or `(a, b, c)`. It CANNOT use the index tree order for `WHERE b = 2 AND c = 3` (missing leading column `a`, unless the DB supports an Index Skip Scan on low-cardinality `a`). Furthermore, if a range predicate is used on an earlier column (`WHERE a = 1 AND b > 5 AND c = 10`), the index scan uses `a` and `b`, but `c` cannot be used for index range matching because across different values of `b > 5`, `c` is no longer globally sorted!
24	Compare First Normal Form (`1NF`), Second Normal Form (`2NF`), Third Normal Form (`3NF` / `BCNF`), and Strategic Denormalization.	1. `1NF`: Atomic column values (no comma-separated lists in a string column) and a primary key. 2. `2NF`: `1NF` + no Partial Dependencies (every non-key attribute depends on the entire composite primary key, not just part of it). 3. `3NF` / `BCNF`: `2NF` + no Transitive Dependencies (`A -> B -> C` where a non-key column determines another non-key column; 'every non-key attribute depends on the key, the whole key, and nothing but the key, so help me Codd'). Normalization eliminates update/delete anomalies and write redundancy in OLTP, whereas OLAP star schemas (`Fact` + `Dimension` tables) intentionally denormalize to avoid expensive multi-table joins.
25	What is the exact Logical Query Processing (Execution) Order of SQL clauses, and why can't you reference a `SELECT` alias inside `WHERE`?	1. `FROM` & `JOIN` (with `ON` predicates); 2. `WHERE` (filters individual rows); 3. `GROUP BY` (buckets rows into groups); 4. Aggregate Functions (`COUNT`, `SUM`, `AVG`); 5. `HAVING` (filters aggregated groups); 6. Window Functions (`OVER (...)`); 7. `SELECT` (projects columns and creates aliases); 8. `DISTINCT`; 9. `UNION` / `INTERSECT` / `EXCEPT`; 10. `ORDER BY` (can use `SELECT` aliases!); 11. `OFFSET` & `LIMIT` / `FETCH`. Because `WHERE` (step 2) executes long BEFORE `SELECT` (step 7), aliases defined in `SELECT` do not exist yet during `WHERE` evaluation (and Window Functions cannot be used directly in `WHERE`/`HAVING` without a CTE/subquery!).
26	Define the four classic Concurrency Anomalies in databases: `Dirty Read`, `Non-Repeatable Read`, `Phantom Read`, and `Write Skew` (`Lost Update`).	1. Dirty Read: Transaction $T_1$ reads uncommitted changes written by $T_2$ (which $T_2$ might later `ROLLBACK`!). 2. Non-Repeatable Read (Read Skew): $T_1$ reads the same row twice and gets different values because $T_2$ updated and committed that row in between. 3. Phantom Read: $T_1$ runs the same `WHERE` range query twice and sees new or missing rows ('phantoms') because $T_2$ inserted or deleted matching rows and committed. 4. Write Skew: Two transactions $T_1$ and $T_2$ read overlapping data under Snapshot Isolation (e.g., verifying $\ge 2$ doctors are on call), and each modifies a disjoint row (Doctor A and Doctor B both go off call simultaneously), violating the multi-row invariant!
27	Compare Keyset (Cursor / Seek) Pagination against `OFFSET / LIMIT` Pagination on a 100-million-row table.	With `SELECT * FROM events ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 10000000`, the database MUST scan, sort/walk, and discard all `10,000,000` preceding rows before returning 20 rows ($O(\text{offset})$ time, getting slower on deeper pages and skipping/duplicating rows if new inserts occur!). Keyset / Cursor Pagination passes the last seen `(created_at, id)` from the previous page: `WHERE (created_at, id) < ('2026-11-01 12:00:00', 98412) ORDER BY created_at DESC, id DESC LIMIT 20`—seeking directly into the composite B+ Tree index `(created_at, id)` in constant $O(\log N)$ time even at page 500,000!
28	Compare Pessimistic Locking (`SELECT ... FOR UPDATE` / `FOR SHARE`) and Optimistic Concurrency Control (`version` column CAS) for preventing Lost Updates.	1. Pessimistic Locking: Acquire an exclusive row-level lock when reading (`SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;`); concurrent writers trying to lock row `1` block until your transaction commits—best when contention is high and transactions are short/in-DB. 2. Optimistic Concurrency Control (OCC): Read row without locking along with `version = 5`; when updating, run Compare-And-Swap (`UPDATE accounts SET balance = 90, version = 6 WHERE id = 1 AND version = 5;`) and check if `affected_rows == 1` (retrying if `0`)—best when conflicts are rare or state is held across user HTTP round-trips.
29	How does `SELECT ... FOR UPDATE SKIP LOCKED` allow building a high-concurrency Job Queue inside PostgreSQL or MySQL 8+?	If 50 worker threads run plain `SELECT id FROM jobs WHERE status = 'PENDING' ORDER BY id LIMIT 1 FOR UPDATE`, 49 workers will block waiting on the exact same row #1! Adding `SKIP LOCKED` (`... LIMIT 1 FOR UPDATE SKIP LOCKED`) instructs the database engine to immediately skip over any rows currently locked by other active transactions and lock the next available unlocked `'PENDING'` row—allowing all 50 workers to dequeue 50 distinct jobs in parallel with zero lock wait contention!
30	How do you write a Pivot / Conditional Aggregation query in SQL (`COUNT(*) FILTER (WHERE ...)` vs `SUM(CASE WHEN ...)`), and how do `ROLLUP`, `CUBE`, and `GROUPING SETS` work?	Conditional Aggregation pivots rows into columns in a single table scan: `SUM(CASE WHEN status = 'paid' THEN amount ELSE 0 END) AS paid_total` (or Postgres standard SQL `SUM(amount) FILTER (WHERE status = 'paid')`). `GROUP BY ROLLUP (year, quarter, month)` generates hierarchical subtotals (`(year, quarter, month)`, `(year, quarter)`, `(year)`, and grand total `()`) in one pass; `CUBE (a, b)` generates all $2^k$ dimensional combinations; `GROUPING SETS ((a), (b), ())` computes exact specified groupings.
31	Compare Non-Recursive CTEs (`WITH`), Materialized CTEs (`WITH x AS MATERIALIZED`), Temporary Tables, Views, and Materialized Views.	CTE (`WITH`): Query-scoped named subquery; in PostgreSQL 12+, non-recursive CTEs referenced once are inlined into the outer query by default so predicate pushdown works (use `AS MATERIALIZED` to force once-only evaluation as an optimization fence). View: Stored SQL query text with zero stored data (rewritten at query time). Materialized View: Physically persists the query result on disk and can be indexed (refreshed via `REFRESH MATERIALIZED VIEW CONCURRENTLY`, which requires a `UNIQUE` index). Temp Table: Session/transaction-scoped physical table supporting custom indexes and statistics.
32	What causes a Database Deadlock between two concurrent transactions, and how do you prevent it in application code?	A Deadlock occurs when Transaction $T_1$ holds an exclusive lock on Row `A` and waits for Row `B` (`UPDATE accounts WHERE id = 'A'` then `'B'`), while simultaneously Transaction $T_2$ holds an exclusive lock on Row `B` and waits for Row `A` (a cycle in the waits-for graph; the DB's deadlock detector aborts one victim transaction). Prevention: Always acquire locks in a deterministic canonical order (e.g., sort account IDs ascending `min(acct1, acct2)` before `max(acct1, acct2)` inside `SELECT ... WHERE id IN (101, 205) ORDER BY id FOR UPDATE`)!