FIT5202 · Data Processing for Big Data
Parallel Databases & Parallel Search
Week 2 of Monash FIT5202 formalises the Volume theme: shared-nothing parallel database architectures, the three data-partitioning strategies — round-robin, hash and range — and how partitioning decides which processors a search must activate. It defines the performance measures speed-up and scale-up, the obstacles (start-up, interference, communication and skew), and the Zipf model of data skew. Partitioning choice and processor activation are recurring written-response material, and speed-up/scale-up classification is common in the multiple-choice question.
What this chapter covers
- 01Shared-nothing (vs shared-memory, shared-disk) parallel database architectures
- 02Data partitioning: round-robin (even, no grouping), hash (localises exact-match), range (localises range queries)
- 03Parallel search in two steps: partition the data, then search locally in each partition
- 04Processor activation: which processors a query must touch depends on partitioning method + query type
- 05Speed-up = uniprocessor time / multiprocessor time; scale-up = small-system time / larger-system time
- 06Parallel obstacles: start-up and consolidation, interference and communication, and skew
- 07Data skew vs processing skew; the Zipf skew degree θ (0 = none, 1 = highly skewed)
- 08Local search method: binary search if the partition is ordered, linear search if not
Processor activation under different partitioning methods
- +1(a) Hash partitioning places a record on processor = hash(key) mod N, so a single exact-match key maps to exactly one processor. Activate 1 processor.
- +1(b) On a hash-partitioned table, adjacent key values scatter to different processors, so a continuous range cannot be localised. Every processor may hold matching rows. Activate all 4.
- +1(c) Round-robin (random-equal) spreads records with no semantic rule, so the target row could sit on any processor. Activate all 4.
- +1Lesson: processor involvement is decided jointly by the partitioning method and the query type — hash localises exact-match, range localises range queries, and round-robin balances load but localises nothing.
Key terms
- Shared-nothing architecture
- A parallel database design in which each processor has its own memory and disk and communicates only by messages. It scales to thousands of commodity nodes and underlies Spark's cluster model.
- Round-robin partitioning
- Allocating records to processors cyclically, giving an even, load-balanced spread but no semantic grouping — so any specific-value query must activate all processors.
- Hash partitioning
- Sending each record to processor hash(key) mod N. Exact-match queries target a single processor, but continuous-range queries must touch all; the initial distribution can be skewed.
- Range partitioning
- Assigning records to processors by ranges of a partitioning attribute, so range queries are directed to a few processors; the initial allocation can be skewed by the data distribution.
- Scale-up
- The ability to handle a proportionally larger task by adding resources while holding time constant: small-system time / larger-system time. Linear scale-up equals 1.
- Data skew (Zipf θ)
- Uneven fragment sizes across processors, measured by a Zipf degree θ from 0 (no skew) to 1 (highly skewed). Data skew causes processing skew — one overloaded processor stretches elapsed time.
Parallel Databases & Parallel Search FAQ
How do I decide which partitioning strategy to use?
Match it to the dominant query. Use hash partitioning when exact-match lookups dominate (they hit one processor), range partitioning when range queries dominate (they hit a contiguous few), and round-robin when you mainly want even load with full scans. There is no universal best — the exam rewards justifying the choice by query type.
What is the difference between speed-up and scale-up?
Speed-up keeps the task fixed and adds processors to finish faster (uniprocessor time / multiprocessor time). Scale-up grows the task and the resources together and asks whether time stays constant (small-system time / larger-system time, ideally 1). A classic quiz item hands you a scenario and asks which one it illustrates.
Why does data skew hurt parallel performance so much?
Because elapsed time is set by the slowest processor. If a Zipf-skewed partitioning dumps most records on one processor, the others finish early and wait, so effective speed-up collapses toward 1 no matter how many processors you added. Skew is why partitioning choice and load balancing matter.
Can AI help me with parallel search and partitioning?
Yes. Sia can build a processor-activation table for a given partitioning and query type, explain the Zipf skew model, and quiz you on speed-up versus scale-up — step by step, checking your reasoning. It will not sit your quiz or write your assignment, and Monash academic-integrity rules apply.
Exam move
Build a mental version of the processor-activation table: for each partitioning method (round-robin, hash, range) and each query type (exact-match, continuous range, discrete selection), know how many processors activate and why. Drill speed-up versus scale-up until you can classify a scenario in one line, and always mention skew as the reason a real speed-up falls short of linear. Week-2 material anchors Weeks 3–4, so keep it warm on Moodle rather than re-learning it in SWOTVAC — and remember the in-semester quizzes are hurdle-relevant.
Working through Parallel Databases & Parallel Search in FIT5202? Sia is AskSia’s AI Information Technology tutor — ask any FIT5202 Parallel Databases & Parallel Search question and get a clear, step-by-step explanation grounded in how FIT5202 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
