MCQ exam bank

In a slotted page, how do the slot array and the tuple data grow?

The slot (line-pointer) array grows down from the header while tuple data grows up from the page end; the page is full when the two pointers meet. In PostgreSQL these are pd_lower and pd_upper closing from both sides.

A record id such as PostgreSQL's (page id, slot number) is best described as:

The id is (page id, slot), and the slot/line pointer indirects to the actual in-page byte offset, which can move on compaction without changing the id. CMU stresses applications cannot treat the id as a meaningful physical address.

Which statement about NULL storage and column layout is false?

Reordering columns can change row size: putting an 8-byte bigint after a 1-byte bool wastes pad bytes that disappear if you reorder. A sentinel cannot mark NULL because any sentinel could be a legal value, so a bitmap is used.

Why does PostgreSQL keep three distinct notions of "page" (hardware ~4 KB, OS ~4 KB, database 8 KB)?

Atomicity is guaranteed only at the hardware-page granularity. When the 8 KB DB page exceeds the 4 KB hardware page, a crash mid-write can leave a torn page (half old, half new), which PostgreSQL defends against with full-page writes to the WAL.

What does a plain VACUUM in PostgreSQL do?

Plain VACUUM reclaims dead space in place (rarely returning it to the OS), refreshes planner statistics, maintains the visibility map, and freezes old XIDs to prevent wraparound. VACUUM FULL is the one that rewrites the table and takes ACCESS EXCLUSIVE.

A 5 KB text value is inserted into a PostgreSQL row. What happens?

A tuple cannot span pages. Values past roughly 2 KB trigger TOAST, which compresses and/or pushes the value out of line into a separate TOAST table chunked at about 2000 bytes, up to 1 GB per field.

SQLite reclaims free space inside one B-tree page using:

SQLite chains in-page freeblocks (4+ byte gaps); smaller 1-3 byte gaps are tallied as fragmented free bytes. The _fsm fork and MVCC tombstones are PostgreSQL mechanisms, and they track free space across pages, not within one.

Pinning a page in the buffer pool guarantees that:

A pin only blocks eviction, not concurrent access; concurrency control via locks/latches is a separate mechanism. The dirty flag and write-back are independent of pinning.

Which statement about the buffer pool is false?

The buffer pool is write-back, not write-through: modifications are buffered in memory and only flushed on eviction or by a background writer. The dirty flag exists precisely so writes are deferred.

A large one-pass sequential scan evicts the hot working set under LRU/CLOCK. This is:

The scan pages get the most-recent timestamps and push out genuinely hot pages they will never revisit. MRU or a bounded ring buffer is scan-resistant; PostgreSQL uses ring buffers (BufferAccessStrategy) for bulk operations.

What is the Backward K-distance that LRU-K uses as its eviction key?

The victim is the page whose K-th most recent reference is furthest in the past (largest Backward K-distance). LRU-2 already measures an actual interarrival time, which defeats sequential flooding. The forward distance is Belady's MIN, which needs the future.

PostgreSQL's buffer replacement algorithm is:

PostgreSQL uses a clock-sweep variant: each buffer has a usage_count bumped on pin (capped at 5) and the nextVictimBuffer hand decrements counts, taking a buffer with zero pin and zero usage_count. Belady's MIN is only a theoretical bound; it needs the future reference string.

PostgreSQL's shared_buffers documentation recommends about 25 percent of RAM and warns above ~40 percent rarely helps. Why?

PostgreSQL does not use direct I/O for its main reads, so a page can live in both shared_buffers and the OS page cache. Oversizing the pool wastes memory on double-buffering and shrinks the OS cache.

Combines topics The steal + no-force buffer policy used by ARIES requires:

Steal lets a dirty uncommitted page reach disk, so recovery must be able to UNDO it. No-force lets committed changes stay in memory at crash time, so recovery must REDO them. WAL makes the combination safe by ordering log before data.

Why does a disk DBMS use a B+tree instead of a balanced binary search tree?

The dominant cost on disk is page reads, not comparisons. Widening each node to hold hundreds of keys gives O(log_m N) I/Os with large m, so three or four levels index hundreds of millions of rows. A binary tree wastes a page read per single-bit branch.

Which statement about B+trees is false?

A B+tree keeps all data in linked leaves; internal nodes route only. Storing records in internal nodes describes a plain B-tree. PostgreSQL nbtree and SQLite table b-trees are B+tree-shaped even though called "B-tree".

On a leaf split in a B+tree, the separator key is:

A leaf split copies the separator up because all data must stay in the leaf. The middle key is pushed up (moved, not copied) only on an internal-node split, where internal nodes route and need not retain a copy.

When does a B+tree grow in height?

Height increases only when the root splits, which is why all leaves stay at the same depth and the tree grows from the top. Most inserts touch one leaf and stop.

In extendible hashing, when does the directory double?

If the splitting bucket's local depth equals the global depth, the directory doubles and global depth increments. If its local depth is below the global depth, two slots already point at it, so only the bucket splits with no doubling. The round-robin threshold describes linear hashing.

A composite index on (a, b) can efficiently serve which predicate?

Composite keys are ordered lexicographically, so only a contiguous left prefix is seekable: a = ?, or a = ? AND b > ?. Rows for a given b value are scattered across the key space, so b alone cannot be seeked.

Which statement about PostgreSQL hash indexes and index-only scans is false?

An index-only scan must consult the visibility map; only when the heap page is all-visible can it skip the heap fetch. The other three claims are all true of PostgreSQL.

A query needs all rows BETWEEN x AND y. Compared with a B+tree, a hash index:

A hash index has no ordering, so it cannot do ranges, ORDER BY, or prefix matches; it wins only on full-key equality. The B+tree descends once and walks linked leaves for the range.

Which task does the pure parser NOT perform?

The parser applies only fixed syntactic rules and makes no catalog lookups; existence and name resolution happen in the later analysis/binding stage. PostgreSQL splits them because catalog lookups need a transaction and raw parsing does not.

Which statement about parser strategies is false?

The directions are reversed: recursive descent is top-down (LL); LALR/LR is bottom-up. The other three statements are correct, including that left recursion must be refactored out of an LL grammar.

View expansion happens in which stage?

View expansion is the rewriter's core job: it splices a view's underlying tables and predicates in, using only the query and catalog, never data or cost. PostgreSQL's rewrite system exists chiefly to realize views.

Which is a property of a logical plan, not a physical plan?

A logical plan is relational algebra and says what to compute. Binding algorithms and access paths (hash vs merge join, seq vs index scan) and physical properties is the physical plan's job, and there is no one-to-one mapping between the two.

SQLite's parser is generated by Lemon rather than yacc because:

Both generate LALR(1) parsers, but Lemon inverts the call direction (tokenizer calls parser), making it reentrant and threadsafe. SQLite needs reentrancy because it parses recursively, for example re-invoking the parser to insert into sqlite_schema.

In the Volcano iterator model, control and data flow as:

Volcano is pull/demand driven: open/next/close, with parents pulling from children one tuple at a time. Push (producer-driven) is the opposite model and the basis of query compilation.

Which statement about hash join is false?

There is no hash that turns an inequality into bucket equality, so range/inequality joins fall back to nested loop or merge. The other three are correct, including building on the smaller side and the 3(M+N) grace cost.

Block nested loop join rereads the inner table:

Block nested loop reads S once per outer block (cost M + ceil(M/(B-2))*N), so giving the outer more buffer frames directly reduces the rereads. Once-per-outer-tuple is the naive form; once-per-tuple-with-an-index is index nested loop.

External merge sort over N pages with B buffers takes how many passes?

The "1 +" is run generation; the log term is the merge passes, with fan-in B-1. One pass happens only when the data fits in B pages; two passes is the common case. More buffers cut passes logarithmically.

Which operator is a pipeline breaker (must consume all input before emitting any output)?

Sort cannot emit the first sorted tuple until it has seen the last input tuple, so it is a pipeline breaker, as is the build side of a hash join and aggregation. Filter, projection, and the probe phase are streaming with bounded state.

Sort-merge join must sort both inputs:

If an input arrives sorted on the join key (clustered index scan, prior sort, or an upstream ORDER BY), that sort cost is zero and you keep only the merge. Merge join is also attractive when the output needs to be sorted on the join key anyway.

SQLite implements joins as:

SQLite only ever does nested-loop joins, executed by its VDBE bytecode. It makes them fast through indexes and a polynomial-time join-ordering algorithm. It has no hash or merge join.

Combines topics Hash aggregation for GROUP BY, versus sort-based aggregation, produces output that is:

Hash aggregation builds a hash table keyed on the group, so output order is arbitrary; sort-based aggregation sorts first and emits groups in key order. Hash aggregation wins when distinct groups are few; PostgreSQL can spill it to disk since version 13.

The optimizer's cost number is measured in:

System R's COST = PAGE FETCHES + W * RSI CALLS is a unitless weighted sum, and PostgreSQL uses abstract cost units. The goal is correct relative ranking of plans, not an accurate absolute time.

Under the independence assumption, the selectivity of pred1 AND pred2 is:

ANDed selectivities multiply under independence; the last option (the inclusion-exclusion form) is the OR rule. Multiplying is exactly what fails on correlated columns, causing large underestimates.

Which statement about histograms is false?

Equi-depth handles skew far better, which is why PostgreSQL uses it; equi-width dumps most rows into one bucket on skewed data. The MCV list captures the spikes and the histogram covers the smooth tail.

The System R / Selinger join search restricts the plan space to:

System R restricts to left-deep trees (each join's inner input is a base relation) and uses dynamic programming over subsets of relations, keeping the cheapest plan per subset plus per interesting order. Bushy plans exist in some modern systems but were excluded.

In PostgreSQL, n_distinct = -1 for a column means:

A negative n_distinct expresses the distinct count as a fraction of table size; -1 means every value is distinct. The negative encoding keeps the estimate valid as the table grows.

When does PostgreSQL switch from exhaustive DP join search to the genetic optimizer (GEQO)?

Below geqo_threshold (default 12) PostgreSQL runs near-exhaustive DP; at or above it the factorial growth of join orders forces the genetic, non-exhaustive heuristic search.

Which is NOT a heuristic rewrite applied unconditionally (rather than costed)?

Pushdowns and join elimination are semantics-preserving rewrites applied because they are essentially always beneficial. Choosing a join algorithm is a cost-based physical decision, not an unconditional rewrite.

A schedule is conflict-serializable if and only if:

Conflict serializability holds exactly when the precedence graph is acyclic; any topological sort is then an equivalent serial order. 2PL is a sufficient way to guarantee acyclicity, not the definition.

The difference between a phantom and a non-repeatable read is:

A phantom is an insert or delete that changes which rows match a predicate, so preventing it needs predicate or gap locking, not just row locks. That is why Repeatable Read (which forbids P2) can still allow P3 in the ANSI standard.

Snapshot isolation permits which anomaly that makes it not serializable?

First-Committer-Wins only catches write-write conflicts on the same item. Write skew is two transactions writing different items after reading an overlapping set, so there is no write-write conflict to catch, yet the precedence graph has a cycle.

Which statement about the ANSI levels and snapshot isolation is false?

SI is incomparable with Repeatable Read, not strictly above it: it forbids phantoms that RR allows yet permits write skew that Serializable forbids. PostgreSQL labeling its SI level "Repeatable Read" fuels this confusion.

In two-phase locking, the two phases are:

2PL means no lock may be acquired after the first release; work happens throughout. Prepare/commit is two-phase commit, a distributed protocol, not 2PL. Plain 2PL still allows cascading aborts; you need strict 2PL for cascadelessness.

PostgreSQL's Read Uncommitted level:

PostgreSQL exposes four levels but implements three; Read Uncommitted maps to Read Committed, so dirty reads never occur at any level. Read Committed is the default; Serializable is SSI.

Strict 2PL differs from rigorous 2PL in that:

Strict 2PL holds write (X) locks to commit, preventing dirty reads and cascading aborts. Rigorous additionally holds read (S) locks to commit, which makes the serialization order equal the commit order.

In the wait-die deadlock-prevention scheme:

Wait-die is a prevention scheme: older waits, younger dies. No waits-for graph is built (that is detection). Reusing the original timestamp on restart guarantees liveness. Wound-wait is the preemptive variant.

A latch differs from a lock in that:

Latches are short physical mutexes guarding shared structures like the lock table; locks are logical, transaction-duration, and deadlock-detectable. Confusing the two is a common exam point.

Which statement about MVCC is false?

The whole point of MVCC is that a long reader does not block writers; instead it holds back garbage collection, which is a space problem, not a blocking one. MVCC removes read-write blocking but writers still need serializing.

An UPDATE in PostgreSQL:

PostgreSQL does delete-plus-insert: a new version is written and the old version's t_xmax is set, with t_ctid forming the update chain. This append-only MVCC is why heavy updates bloat tables and why VACUUM is needed.

Combines topics Transaction id wraparound in PostgreSQL is dangerous because:

XIDs are 32-bit and compared modulo 2^32, so old rows can suddenly look "newer" than live transactions, causing silent data loss. VACUUM marks old all-visible tuples as frozen (FrozenTransactionId is always older than any normal XID), and every table must be vacuumed within two billion transactions.

PostgreSQL handles deadlocks by:

PostgreSQL detects deadlocks via a waits-for cycle search and aborts a victim; it does not prevent them and does not let you predict the victim. MVCC removes read-write conflicts but writers can still deadlock.

The write-ahead logging (WAL) rule states that:

WAL orders the log before the data: the log record describing a change must be durable before the dirty page it describes can be written. This is what makes the steal + no-force buffer policy safe to recover. PostgreSQL enforces it at the page level via pd_lsn.

ARIES recovery runs its three phases in which order?

ARIES runs Analysis (rebuild the dirty page table and transaction table from the last checkpoint), then Redo (repeat history, replaying all logged changes), then Undo (roll back losers). Redo repeats history even for transactions that will be undone, which is the ARIES signature.

Why does ARIES use a "repeat history" redo that replays even changes made by transactions that ultimately aborted?

ARIES first redoes everything to reconstruct the precise state at crash time, then undoes losers. Undo actions are themselves logged as compensation log records (CLRs) so that a crash during recovery does not undo work twice; CLRs are redo-only and carry an UndoNextLSN to skip already-undone work.

A log sequence number (LSN) stored in a page header (PostgreSQL's pd_lsn) lets the recovery manager:

Comparing the page LSN against a log record's LSN tells redo whether the change is already reflected on the page, so it can be skipped. The same pd_lsn enforces WAL: the buffer manager will not flush a page until the WAL up to its LSN is durable.

A fuzzy checkpoint in ARIES is preferred over a sharp (quiescent) checkpoint because:

A fuzzy checkpoint snapshots the dirty page table and transaction table without stopping transactions or forcing all dirty pages, so it is cheap and non-blocking. The recoveryLSN of the oldest dirty page bounds where redo must begin.

Combines topics SQLite's rollback-journal mode and its WAL mode differ in that:

Rollback-journal keeps a before-image so an abort or crash can restore the original file, which it modifies in place. WAL appends changes (commit = append a commit record), so readers see a consistent snapshot via end marks while a single writer appends; a checkpoint later moves pages back into the main file.

Which statement comparing LSM trees and B+trees is false?

LSM trees optimize writes at the cost of read and space amplification plus compaction overhead; the right choice is workload-dependent, not universal. The other claims are all true.

Leveled compaction versus tiered (size-tiered) compaction:

You cannot minimize read, write, and space amplification all at once (the RUM conjecture). Leveled keeps one sorted run per level (low read/space, write amp often >10 in RocksDB); tiered keeps several runs per level (low write, higher read/space).

Which statement about Bloom filters is false?

Clearing a bit might clear one shared with another key, introducing false negatives, so standard Bloom filters are not deletable (you need a counting Bloom filter). The no-false-negative property is exactly what makes them safe for skipping SSTables.

Columnar (DSM) storage wins over row (NSM) storage for:

A column-store reads only the columns a scan touches, compresses each column far better (one type, often sorted), and feeds vectorized scans. Row-stores still win OLTP single-row access, which a column-store would scatter across many segments.

Vectorized execution in DuckDB means:

DuckDB queries are still interpreted; vectorization processes a vector of values per call, which is distinct from query compilation. The default STANDARD_VECTOR_SIZE is 2048.

Which statement about partitioning (sharding) is false?

Hashing destroys key order, so a range query must scan every shard; hash partitioning does not support efficient ranges. The trade-off mirrors hash index versus B+tree at the cluster level.

The "C" in the CAP theorem refers to:

CAP consistency is linearizability, a property of distributed reads/writes, distinct from ACID consistency (integrity-constraint preservation). Conflating the two is a classic exam trap.

The blocking problem of two-phase commit (2PC) is that:

A participant that voted yes cannot decide alone; if the coordinator dies before delivering the decision, it blocks in-doubt holding locks. 3PC reduces this only under synchronous-network assumptions; production systems replicate the coordinator's decision log with consensus instead.

Combines topics A quorum system with N replicas guarantees a read sees the latest acknowledged write when:

W + R > N forces the read quorum and write quorum to share a node, so a read sees the latest write. This need not be a strict majority on each side, for example N=3, W=3, R=1 also works. Synchronous vs asynchronous replication is the PACELC latency-vs-consistency knob.

Raft and Multi-Paxos differ mainly in that:

Raft was designed to be more understandable (leader election, log replication, safety) but produces the same guarantee as Multi-Paxos: an entry commits once a majority stores it, and a 5-node cluster survives 2 failures. The difference is pedagogical and structural, not in the guarantee.