Data Acquisition, Extraction & Storage — ENS / Inria / PSL

Lecture 2 Recap Q&A

🔒 Answers locked
Q1

SSD as Storage Layer vs. SSD as Cache

SSDs can be integrated into a storage hierarchy in two fundamentally different ways:

  • Storage layer: some relations (or partitions) are permanently stored on SSD, the rest on magnetic disk.
  • Cache: all data lives on magnetic disk; the SSD transparently caches frequently accessed blocks, evicting cold blocks back to disk.

(a) You are building a system that must answer real-time queries with a guaranteed maximum response time. Which architecture do you choose, and why?

(b) You have a very large customer relation (hundreds of GB). Query logs show that a small, unpredictable subset of its blocks are hot at any given moment, while the rest are rarely touched. Which architecture works better here, and why?

Q2

Magnetic Disk

Some database systems configure magnetic disks so that only sectors on the outer tracks are used, leaving the inner tracks completely empty — even though this wastes a significant fraction of the disk's total capacity.

What are the potential performance benefits of this strategy? Give at least two distinct reasons.

Q3

Disk-Scheduling Algorithm

A database engineer proposes the following disk-scheduling algorithm to handle two classes of requests: system requests (issued by background processes) and user requests (issued by queries).

Proposed algorithm — Priority Proximity Scheduler (PPS):
At each scheduling step:
1. If any system request is pending, serve the system request whose target track is closest to the current head position.
2. Otherwise, serve the user request whose target track is closest to the current head position.

(a) Identify a fundamental correctness problem with this algorithm.

(b) Construct a concrete example.

(c) To fix the problem, a colleague proposes the following modification:

Proposed fix — Aging: Add a maximum waiting time $T_{\max}$. Any user request that has been waiting for longer than $T_{\max}$ is promoted to system priority and becomes eligible to be selected in step 1. Among all system requests (original and promoted), the scheduler still picks the one closest to the current head.

Is this fix solving the problem of the previous solution? If you think it is correct, justify it. If you think it is still wrong, construct a concrete counterexample.

(d) If the fix in (c) is flawed, propose a truly correct algorithm.

Q4

Parity Placement

A parity block $P_i$ stores the bitwise XOR of a group of data blocks. If one disk fails, any lost data block in the group can be reconstructed: $B_{\text{lost}} = P_i \oplus B_1 \oplus B_2 \oplus \ldots$ This only works if at most one block from the group is lost.

Consider the following setup: 4 disks, data blocks $B_1$–$B_{12}$ assigned round-robin ($B_j$ → Disk $((j{-}1) \bmod 4)+1$). Parity group $i$ covers $\{B_{3i-2},\, B_{3i-1},\, B_{3i}\}$, so $P_i = B_{3i-2} \oplus B_{3i-1} \oplus B_{3i}$. An engineer assigns $P_i$ to Disk $i$ (cycling $1, 2, 3, 4, 1, \ldots$), giving the following layout:

Disk 1Disk 2Disk 3Disk 4
DataB1B2B3B4
B5B6B7B8
B9B10B11B12
ParityP1P2P3P4

(a) Is this arrangement robust to disk failure?

(b) If not, propose a corrected placement formula and the resulting layout.

Q5

Slotted Pages and the Free-Space Map

A file consists of 3 slotted pages (P1, P2, P3), each 400 bytes. A page header costs 8 bytes; each slot entry costs 4 bytes. Records are packed from the right. When a new record must be inserted, the system always picks the page with the most contiguous free space (as reported by the FSM). Ccompaction is not run automatically.

Starting from three empty pages, execute the following sequence:

  1. INSERT r1 (70 B), r2 (50 B), r3 (90 B), r4 (60 B), r5 (80 B)
  2. DELETE r2
  3. INSERT r6 (55 B)
  4. DELETE r4
  5. INSERT r7 (75 B)

(a) After the full sequence, for each page state: the total free bytes, whether the free space is contiguous, and the largest single record that can be inserted.

(b) We maintain a free-space map (FSM) with only $2n$ bits total for $n$ pages (2 bits per page). How do you encode the free space of each page? What precision does this give you?

(c) With $k$ bits per page and a page of size $B$ bytes, what is the granularity of the free-space estimate? Give the formula.

(d) What is the benefit and the drawback of using a small $k$ (e.g., $k=2$) compared to a large $k$?

Q6

Buffer Pool Replacement — LRU vs. MRU

Background. A buffer pool is a fixed set of memory frames that cache disk blocks. When a block is requested:

  • Hit: the block is already in a frame — it is returned immediately (no disk I/O).
  • Miss: the block is not in any frame — it must be read from disk. If all frames are occupied, one must be evicted (written back to disk if dirty, then its frame reused).

Two replacement policies decide which frame to evict on a miss:

  • LRU (Least Recently Used): evict the block that was last accessed furthest in the past.
  • MRU (Most Recently Used): evict the block that was last accessed most recently.

The buffer pool has 4 frames. All frames start empty. Blocks are referenced in this order (each number is a block ID):

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

(a) Simulate LRU: for each reference, show the buffer contents and label it Hit or Miss. Count total misses.

(b) Simulate MRU: same instructions. Count total misses.

(c) Consider a nested-loop join between two relations R (outer, 2 pages: r1, r2) and S (inner, 3 pages: s1, s2, s3), with a buffer pool of 3 frames. The algorithm reads: for each page of R, scan all pages of S. The resulting block-access sequence is:

r1, s1, s2, s3, r2, s1, s2, s3

Simulate LRU and MRU on this sequence (3 frames, start empty). Show the buffer state and hit/miss for each access. Explain why the results differ, and identify which policy is better suited to this access pattern.

Q7

Three Buffer-Write Strategies

A buffer (in RAM) sits between the application and the disk. Below are three strategies for handling READ and WRITE operations.

StrategyOn READOn WRITE
AIf block in buffer → return it. Else load from disk into buffer, return.Write directly to disk.
BIf block in buffer → return it. Else load from disk into buffer, return.If block is in buffer → update buffer. If not in buffer → write to disk.
CCheck disk to verify buffer copy is up-to-date. Return up-to-date copy.Write directly to disk.

(a) Evaluate each strategy on three dimensions: read latency, write consistency, and durability. Which strategy is best overall, and why?

(b) Does a better strategy exist?

Q8

Multitable Clustering — Design and Trade-offs

Consider two relations:

  • Student(sid CHAR(5), sname VARCHAR(15), dept CHAR(10)) — average record size 30 bytes
  • Enrollment(sid CHAR(5), course_id CHAR(8), grade CHAR(2)) — average record size 15 bytes

The database has 6 000 students, each enrolled in 5 courses on average. Block size is 4 096 bytes.

  1. Show a concrete file layout using multitable clustering for 3 students (s1, s2, s3, each with 3 enrollments), fitting as many records as possible into a single 4 KB block.
  2. Compute the total number of blocks for separate heap files vs the clustered file.
  3. Which organisation is preferable for the query SELECT * FROM Student WHERE dept='CS'?
  4. The query below retrieves all course enrollments of CS students. Compare the block I/O cost for separate vs clustered layouts, assuming a simple nested-loop join with no index. Assume 20% of students are in CS (1 200 students).
SELECT s.sname, e.course_id
FROM Student s
JOIN Enrollment e ON s.sid = e.sid
WHERE s.dept = 'CS'
Q9

Wear Leveling

An SSD has 8 physical cells $C_0$–$C_7$, each tolerating at most $W_{\max} = 10$ writes before becoming unreliable. Let $w_j(t)$ denote the number of writes to cell $C_j$ after $t$ operations. The system stores 4 logical variables (X, Y, Z, W). A program executes the following sequence of 20 operations:

W(X), W(Y), W(X), W(Z), W(X), W(Y), W(X), W(W),
W(X), W(Z), W(X), W(Y), W(X), W(W), W(X), W(Z),
W(X), W(Y), W(X), W(W)

Define the SSD lifespan at time $t$ as the number of additional write operations that can be performed before any cell fails:

$$\text{Lifespan}(t) = \min_{j \in \{0,\ldots,7\}} \bigl(W_{\max} - w_j(t)\bigr)$$

The objective of a wear-leveling strategy is to maximise $\text{Lifespan}(t)$ for all $t$, i.e., keep all cells as equally worn as possible so that the minimum remaining capacity is as large as possible.

(a) First approach: logical address = physical address (X→$C_0$, Y→$C_1$, Z→$C_2$, W→$C_3$; $C_4$–$C_7$ unused). Compute $w_j(20)$ for each cell. What is $\text{Lifespan}(20)$? After how many operations does the SSD fail?

(b) Propose a better mapping strategy. Describe it in plain terms.

(c) Is there any residual problem when some variables are written much more frequently than others?