DATA3404 Scalable Data Management
The Complete Exam Bible · S1 2026DATA3404 Overview
- University of Sydney
- S1 2026
- 7 chapters
- Information Technology
Scalable Data Management teaches how a database engine actually works underneath SQL — how data is laid out on disk pages, how indexes turn a full scan into a lookup, how external sorting and the five join algorithms run, how the query optimiser picks a plan, and how the whole thing scales out across a cluster with parallel databases and Spark.
- Assessed by Final examination 60% · Practical assignments (×2) ~24% · Quizzes, participation & a concept presentation ~16% — Final examination is a hurdle
- Key terms Page I/O, B+-tree, External merge sort, Selectivity (reduction factor)
- How to prepare Treat DATA3404 as a set of cost chains you can run on autopilot…
- Most asked What is on the DATA3404 final exam?
How DATA3404 is assessed
| Component | Weight | Format |
|---|---|---|
| Final examination · hurdle | 60% | Paper-based, 2 hours, semi-open book · ≥40% hurdle — and you also need ≥50% overall to pass (double hurdle) |
| Practical assignments (×2) | ~24% | DB programming & testing, then SQL + Spark tuning — group work across the semester |
| Quizzes, participation & a concept presentation | ~16% | Weekly quizzes and a group video presentation — confirm the exact split and the ‘semi-open book’ rules in your unit outline |
What DATA3404 covers
Seven exam topics → one cost-model map. Each links to its free chapter guide.
Data Storage and Files
Pages & records · slotted pages · heap vs sorted · row vs column · the buffer poolEverything DATA3404 charges you for is measured in page I/Os — the number of fixed-size pages moved between disk and memory.
- 1.1 The storage hierarchy — why I/O is the only cost that matters
- Records & the slotted-page layout (fixed vs variable length, NULL bitmap, TID)
- File organisations: heap vs sorted vs hashed — the access-cost table
- Row-store vs column-store for OLTP vs OLAP workloads
- The buffer pool and replacement policies (LRU, CLOCK / GCLOCK)
Indexing
B+-trees · fan-out & height · extendible hashing · clustered vs unclusteredAn index is an access path that finds the rows matching a search key without reading the whole table — the single biggest lever on query cost, turning an O(B) scan of every page into an O(logF B) descent of a few.
- 2.1 Why index — the lookup-vs-scan trade
- Data entries, search keys, and dense vs sparse indexes
- Clustered vs unclustered — and why it dominates range-scan cost
- B+-trees: fan-out, height ⌈log<sub>F</sub> B⌉ + 1, leaf split (copy-up) & node split (push-up)
- Extendible hashing: bucket splits, local vs global depth, directory doubling
- Choosing an index: equality / range / group-by, and the composite-key prefix rule
Sorting and Query Processing
The operator pipeline · access paths · external merge sort & its pass countSQL is declarative — you say what you want, not how to get it — and the engine compiles it into an imperative plan: a tree of physical operators it actually runs.
- 3.1 From SQL to a plan: parse → optimise → execute
- The iterator (pull) model — open / next / close and pipelining
- Access paths: when a full scan, a B+-tree, or a hash index wins
- External merge sort: the pass formula and total I/O = 2N × #passes
- Pipelining vs materialisation — and the extra I/O materialising costs
- The relational-algebra operators and selection/projection push-down
Join Algorithms
Nested-loop · block · index · sort-merge · grace hash — the five I/O cost formulasA join R ⋈ S pairs every matching tuple of two relations, and it is the single most expensive thing a query does. The exam does not ask you to run a join; it asks you to cost one.
- 4.1 Why joins are expensive — the I/O cost model (output not counted)
- Tuple nested-loop join and why it wastes the buffer
- Block nested-loop join: cost = b<sub>R</sub> + ⌈b<sub>R</sub>/(M−2)⌉ × b<sub>S</sub>
- Index nested-loop join: b<sub>R</sub> + |R| × (index lookup cost)
- Sort-merge join: b<sub>R</sub> + b<sub>S</sub> (+ the cost of sorting each input)
- Grace hash join: 3 × (b<sub>R</sub> + b<sub>S</sub>), and which condition each join needs
Query Optimisation
RA equivalences · selectivity & reduction factors · costing plans · System-R DPSQL is declarative — you say what rows you want, not how to compute them — and the query optimiser turns that declaration into the cheapest physical plan it can find.
- 5.1 What the optimiser does: logical rewrite + physical plan choice
- Relational-algebra equivalences and pushing selections/projections down
- Selectivity and reduction factors — estimating result sizes
- Costing a plan: sizes → join I/O formulas → summed page transfers
- Left-deep plans and System-R dynamic programming over join orders
- Interesting orders — why a sorted intermediate can be worth keeping
Parallel Databases
Partitioning · speed-up vs scale-up · distributed joins · HDFS · MapReduceWhen the data no longer fits — or no longer finishes — on one machine, you scale out: spread the data across many nodes and run the query on all of them at once.
- 6.1 Why scale out: scale-up (vertical) vs scale-out (horizontal)
- Partitioning: round-robin, range, hash — and what each can prune
- Speed-up vs scale-up — the ideal line and what limits it
- Distributed joins: local-reference, broadcast, distributed-shuffle, fragment-and-replicate
- HDFS: block size, 3× replication, NameNode vs DataNode
- MapReduce: map → shuffle/sort → reduce, and how a join maps onto it
Big Data with Spark
RDDs · the lazy DAG · narrow vs wide dependencies · NoSQL & CAP · streamingSpark is the modern engine of the big-data stack.
- 7.1 Why Spark: the limits of MapReduce's disk round-trips
- RDDs, lazy evaluation, transformations vs actions
- Narrow vs wide (shuffle) dependencies and stage boundaries
- Lineage-based fault tolerance — recompute, don't replicate
- Spark's four join strategies; Catalyst & adaptive query execution
- NoSQL families, the CAP theorem & ACID-vs-BASE, and streaming windows
The exam does not test SQL syntax; it tests whether you can predict the engine's cost by hand — page I/Os for a join, passes of external sort, the height of a B+-tree, the optimiser's size estimates.
The final exam is 60% of your grade and double-hurdled (you need ≥40% on the exam and ≥50% overall to pass), so this guide teaches each topic to exam standard: the mechanism, the cost formula examiners expect, and exactly where the marks are won.
Worked example · free
Block nested-loop join — the I/O cost, step by step
- +1Recall the BNLJ cost formula: cost = bR + ⌈bR / (M − 2)⌉ × bS. One buffer frame is reserved for reading the inner relation and one for output, so each outer block is (M − 2) pages.
- +1Outer-block size: M − 2 = 10 − 2 = 8 pages per block of the outer relation.
- +1Number of outer blocks: ⌈bR / (M − 2)⌉ = ⌈100 / 8⌉ = 13 blocks.
- +1Plug in: cost = 100 + 13 × 400 = 100 + 5,200.
- +1State the answer: total cost = 5,300 page I/Os — Student is read once, and Enrollment is re-scanned once per outer block (13 times).
Key terms
- Page I/O
- The transfer of one fixed-size page between disk and memory — the single unit DATA3404 measures every cost in. The whole exam is about counting page I/Os; CPU time, sequential-vs-random access and the output write are all ignored in the cost model.
- B+-tree
- The default database index: a balanced, high-fan-out tree whose leaves hold the data entries in sorted order. A search costs ⌈logF B⌉ + 1 page I/Os, where F is the fan-out, so even a huge table is reached in a handful of page reads instead of a full scan.
- External merge sort
- The algorithm for sorting data that does not fit in memory. With N pages and B buffer frames it runs in 1 + ⌈logB−1 ⌈N/B⌉⌉ passes, each pass reading and writing all N pages, so the total cost is 2N × (number of passes).
- Selectivity (reduction factor)
- The fraction of rows a predicate keeps — an equality on a key with V distinct values has selectivity 1/V. The optimiser multiplies these reduction factors to estimate the size of each intermediate result, which then drives every join cost estimate.
- Data partitioning
- Splitting a relation across the nodes of a cluster — round-robin (even load, no pruning), range (prunes range queries), or hash (prunes equality and enables co-located joins). The chosen scheme decides which queries can skip nodes and which distributed join is cheapest.
DATA3404 FAQ
Is DATA3404 hard?
It is calculation-dense rather than conceptually deep. Most marks come from costing the engine by hand — join I/O, sort passes, B+-tree height, optimiser size estimates — so the difficulty is precision and speed under exam conditions, not memorising SQL. Once you can run the cost chains automatically, the numbers stop surprising you.
How is DATA3404 assessed?
The final exam is 60% and double-hurdled: you need at least 40% on the exam and at least 50% overall to pass the unit. The remaining 40% is continuous — two practical assignments (database programming & testing, then SQL + Spark tuning), weekly quizzes and participation, and a group concept video. Confirm this year's exact split in your unit outline.
What is on the DATA3404 final exam?
Storage and buffer management, indexing (B+-trees and hashing), external sorting and query processing, the five join algorithms and their I/O cost, query optimisation (selectivity and plan costing), and the scale-out stack — parallel and distributed databases, HDFS/MapReduce and Spark. The headline repeated tasks are computing a join's I/O cost and the number of passes of external sort.
Is the DATA3404 exam open book?
The unit overview describes the exam as semi-open book, but the exact materials you may bring are set on the current unit outline and exam instructions — do not assume you can bring this guide or unlimited notes. Study as if it were closed book and treat any permitted sheet as a bonus; confirm the rules on Canvas before the exam.
Do I need to be good at SQL or coding to pass DATA3404?
The practical assignments train your SQL and Spark, but the 60% exam tests the engine's internals — it asks you to predict cost, not to write code. You can write perfect SQL and still lose the exam if you can't cost a join or count sort passes, so prioritise the cost models when revising.
Is using AskSia for DATA3404 cheating?
No. AskSia is a study reference written in our own words — we host none of your lecturer's files, and Sia teaches you the method to earn the marks; it does not complete or sit your assessments.
Questions students ask in each DATA3404 chapter
- Why does DATA3404 only count page I/Os and ignore CPU and the output?
- Because disk transfer dominates the cost of a data-management query by orders of magnitude, so a simplified model that counts only pages read and written from disk captures almost all of the real cost and makes the arithmetic tractable in an exam. The unit's cost model explicitly ignores CPU time, the difference between sequential and random access, and the cost of writing the final output — so never add output pages to a join or sort cost. Chapter 01 · Data Storage and Files
- What is the difference between a clustered and an unclustered index, and why does it matter so much?
- A clustered index stores (or orders) the data in the same order as the index key, so a range query's matching rows sit on consecutive pages and the scan reads only those pages. An unclustered index just points into an unordered file, so each matching row can be on a different page — a range that returns r rows can cost up to r extra page I/Os. This single distinction often decides whether an index helps a range query at all, so always check whether the index is clustered before costing a range scan. Chapter 02 · Indexing
- What is the formula for the number of passes in external merge sort?
- Total passes = 1 + ⌈logB−1 ⌈N/B⌉⌉, where N is the number of pages to sort and B is the number of buffer frames. The first pass creates ⌈N/B⌉ sorted runs; each subsequent pass merges up to B−1 runs at once (one frame is the output), so the number of runs falls by a factor of B−1 per pass until a single sorted run remains. Chapter 03 · Sorting and Query Processing
- Which join algorithm is cheapest, and how do I decide?
- There is no single winner — you compute each cost from the given page counts, row counts and buffer size and compare. As a rule of thumb: with a selective index on the inner relation, index nested-loop wins; for a large equi-join with enough memory, grace hash or sort-merge (each roughly 3(bR+bS) or bR+bS+sorts) beats block nested-loop; and sort-merge is attractive when an input is already sorted or the output needs to be. Always plug in the numbers rather than guessing. Chapter 04 · Join Algorithms
- How does the optimiser estimate the size of an intermediate result?
- It multiplies the input size by the selectivity (reduction factor) of each predicate. An equality on an attribute with V distinct uniformly distributed values has selectivity 1/V; a join on a foreign key has selectivity 1/max(V_A, V_B). Multiplying the reduction factors of independent predicates gives the estimated output size, which then feeds the cost of every operator above it. Chapter 05 · Query Optimisation
- What is the difference between scaling up and scaling out?
- Scaling up (vertical) means buying a single bigger machine — simple, but expensive and capped by what one box can be. Scaling out (horizontal) means adding many commodity nodes — cheap to start and able to grow incrementally, but it requires software that manages scalability, consistency and availability across the cluster. Big-data systems are built on scale-out. Chapter 06 · Parallel Databases
- Why is Spark faster than MapReduce?
- MapReduce materialises every intermediate result back to HDFS (3× replicated) between steps, so an iterative or interactive job pays a full disk round-trip per iteration. Spark keeps intermediate RDDs in memory across steps and only writes to disk when it must, so iterative machine-learning and graph jobs and interactive queries run far faster. For a single batch pass the gap is smaller; the win is in repeated passes over the same data. Chapter 07 · Big Data with Spark
How to study for the exam
Treat DATA3404 as a set of cost chains you can run on autopilot, because every high-value exam question is one of them: relation sizes + buffer → pick the join → compute I/O; N pages + B frames → sort passes → 2N × passes; records + fan-out → B+-tree height → search cost; query → push selections down → estimate sizes → cost the plan.
Drill each chain until you can write the formula and every page count from memory, because method marks are real — show the formula and the arithmetic even if the final number slips. The join and external-sort cost calculations are the two most repeated tasks in the whole unit and clear the 40% exam hurdle comfortably; the Spark and NoSQL material is lighter and conceptual, so bank the cost-formula marks first.
