FIT5202 · Data Processing for Big Data
Stream Join Processing
Week 10 of Monash FIT5202 covers joining data streams: the symmetric hash join (SHJ) for two streams, the M-join for multiple streams, and windowed stream–stream joins where unbounded state must be bounded. It introduces the time-slide method over basic windows and, in Structured Streaming, watermarks for handling late data. Tracing a symmetric-hash-join arrival sequence is a common written-response item and the intuition behind windowed joins is examinable.
What this chapter covers
- 01Stream–static vs stream–stream joins; why unbounded state must be bounded
- 02Symmetric Hash Join (SHJ): each stream keeps its own hash table
- 03SHJ arrival handling: probe the other table, then insert into your own
- 04M-Join for multiple streams: remove expired tuples, probe all other tables, hash into your own
- 05Time-based window stream joins (tuple slide, time slide)
- 06Time-slide over basic windows (e.g. 1 basic window = 1 minute; window = 6; slide = 2)
- 07Watermarks and late-data handling in Structured Streaming
- 08Why symmetric tables ensure no incoming tuple's join is missed
Tracing a symmetric hash join over two streams
- +1r(1) arrives on R: probe HT_S (empty) → no match; then insert r(1) into HT_R. HT_R = {1}.
- +1r(2) arrives on R: probe HT_S (still empty) → no match; insert r(2) into HT_R. HT_R = {1, 2}.
- +1s(1) arrives on S: probe HT_R → finds r(1) → EMIT join result orderID 1; then insert s(1) into HT_S. HT_S = {1}.
- +1s(3) arrives on S: probe HT_R = {1, 2} → no match for 3; insert s(3) into HT_S. HT_S = {1, 3}.
- +1r(3) arrives on R: probe HT_S = {1, 3} → finds s(3) → EMIT join result orderID 3; insert r(3) into HT_R. Final emitted results: orderID 1 and orderID 3.
Key terms
- Stream–stream join
- A join of two continuous streams where matching tuples may arrive at different times, so both sides must be buffered (within a window) until their partner arrives.
- Symmetric Hash Join (SHJ)
- A stream join in which each stream has its own hash table. When a tuple arrives, it probes the other stream's table to emit matches, then inserts itself into its own table, so no join is missed by arrival order.
- M-Join
- A multiway streaming join: each stream has a hash table; an arriving tuple first removes expired tuples, probes all other streams' tables, then hashes into its own table.
- Windowed join
- A stream join restricted to a time window so the state (buffered tuples) stays bounded; tuples outside the window expire and are discarded.
- Time-slide
- A windowing method that decomposes a big window into basic windows (e.g. one per minute) and advances the big window by one or more basic windows at a time.
- Watermark
- A moving threshold on event time in Structured Streaming that declares how late data may be; state older than the watermark can be dropped, bounding memory while tolerating some late arrivals.
Stream Join Processing FAQ
Why does a stream join need a hash table on each side?
Because tuples that should join can arrive at different times and in either order. If only one stream were hashed, a tuple arriving on the other stream before its partner would be lost. Keeping a symmetric hash table on each stream means whichever tuple arrives first is stored, ready to be probed and matched when its partner arrives.
Why must stream joins be windowed?
Because the streams are unbounded, so without a limit the hash tables would grow forever and eventually exhaust memory. A window (with expiry or a watermark) bounds how long tuples are kept, trading the ability to match very-late partners for bounded, sustainable state.
What is the rule for handling each arriving tuple in a symmetric hash join?
Probe first, insert second: when a tuple arrives, probe the OTHER stream's hash table to emit any matches, then insert the tuple into its OWN hash table (and, in M-join, first expire old tuples). Following that order for every arrival is what guarantees completeness within the window.
Can AI help me trace stream joins?
Yes. Sia can walk a symmetric-hash-join or M-join arrival sequence step by step, explain windowed joins and watermarks, and quiz you on why symmetric tables prevent missed matches. It explains the method and checks your reasoning; it does not complete graded work, and Monash academic-integrity rules apply.
Exam move
Practise the symmetric-hash-join trace until the probe-then-insert rule is automatic, and be able to state, for any arrival order, which results are emitted and when. Understand why windowing (and watermarks) bound the otherwise-unbounded state, and be able to contrast SHJ with the multiway M-join. This is classic Q2–Q6 written-response material, so rehearse a full arrival trace on Moodle problems through SWOTVAC and ask Sia to generate fresh arrival sequences to solve.
Working through Stream Join Processing in FIT5202? Sia is AskSia’s AI Information Technology tutor — ask any FIT5202 Stream Join Processing 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.
