Speed
✓ Join Complete!
I/O Reads
0
0
Comparisons
0
0
Matches
0
0
Step
— / ?
— / ?
Pseudocode
Relations R & S
Join Results (0)
// outer loop
1for each r in R:
// scan all of S
2 for each s in S:
// compare
3 if r.key == s.key:
// output match
4 emit(r ⋈ s)
Relation R — outer
R
Relation S — inner
S
Result tuples
No matches yet.
Speed
✓ Join Complete!
I/O Reads
0
0
Index Probes
0
0
Matches
0
0
Step
— / ?
— / ?
Pseudocode
Relations & Index
Join Results (0)
// index on S.key pre-built
0
// outer loop
1for each r in R:
// probe index
2 matches = index[r.key]
// fetch S rows
3 for each s in matches:
// output match
4 emit(r ⋈ s)
Relation R — outer
R
Index on S.key
Relation S — inner
S
Result tuples
No matches yet.
Speed
✓ Join Complete!
I/O Reads
0
0
Probes
0
0
Matches
0
0
Step
— / ?
— / ?
Pseudocode
Relations & Hash Table
Join Results (0)
// ── Phase 1: Build ──────────────
1
// scan R
2for each r in R:
// insert
3 HT[ h(r.key) ] += r
// ── Phase 2: Probe ──────────────
4
// scan S
5for each s in S:
// probe
6 for each r in HT[h(s.key)]:
// output match
7 emit(r ⋈ s)
R — build input
R
S — probe input
S
Hash Table HT (keyed on R.key)
Empty — build phase not started
Result tuples
No matches yet.
Speed
✓ Join Complete!
I/O Reads
0
0
Comparisons
0
0
Matches
0
0
Step
— / ?
— / ?
Pseudocode
Relations R & S
Join Results (0)
// ── Phase 1: Sort ───────────────
1
// ── Phase 2: Merge ──────────────
2R' = sort(R) ; S' = sort(S)
3
4pR = 0 ; pS = 0
5while pR < |R'| and pS < |S'|:
6 if R'[pR].key == S'[pS].key: emit ⋈
7 elif R'[pR].key < S'[pS].key: pR++
8 else: pS++
Relation R
R
Relation S
S
Result tuples
No matches yet.
Algorithm Comparison — this dataset
| Algorithm | I/O Reads | Comparisons/Probes | Matches | Complexity |
|---|