SQL SQL In Depth
0%
Guided SQL & Engine Coding Lab

Implement & Benchmark Nested Loop, Hash Join & Sort-Merge Join

A physical relational join engine implementing Block Nested Loop Join, in-memory Build-and-Probe Hash Join, Zipper Sort-Merge Join with duplicate peer rewind, and NULL-safe Hash Anti-Join.

~45 min Advanced Lessons: Hands-On Build: Implement & Benchmark Nested Loop, Hash Join & Sort-Merge Join, Nested Loop Join: Naive O(N×M) vs Block Nested Loop vs Indexed NLJ, Hash Join Internals: In-Memory Build/Probe Phases, Skew & Grace Hash Disk Spills, Sort-Merge Join: Dual Sorted Streams, Zipper Merge & Duplicate Rewinding, Join Ordering Search Space (N!): Selinger Dynamic Programming & Left-Deep vs Bushy Trees, Logical Plan Rewrites: Predicate Pushdown, Projection Pruning & Join Elimination
Guided Algorithm Coding Lab 0/4 Steps Completed

Code & Verify SQL & Storage Engine Invariants in the Browser Workbench

Complete 4 progressive algorithmic steps with guided hints in C++20 (WebAssembly), TypeScript, or JavaScript against automated unit test assertions — zero local setup required.

Architectural Overview

A physical relational join engine implementing Block Nested Loop Join, in-memory Build-and-Probe Hash Join, Zipper Sort-Merge Join with duplicate peer rewind, and NULL-safe Hash Anti-Join.

In production relational and analytical database systems—spanning PostgreSQL, SQLite, MySQL/InnoDB, and DuckDB—understanding how query clauses, schema constraints, index structures, and storage engines execute under the hood separates surface-level query authors from staff-level database engineers. This capstone build lab guides you through implementing Implement & Benchmark Nested Loop, Hash Join & Sort-Merge Join from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Block Nested Loop Join with Comparison Telemetry

  • Core Database Concept: Evaluating Equi-Joins Across Outer and Inner Tuple Pairs
  • Target Module: index.js (PhysicalJoinEngine.nestedLoopJoin)
  • Engineering Specification: Implement nestedLoopJoin(leftRows, rightRows, leftKey, rightKey) returning { rows, comparisons }, skipping null/undefined join keys per SQL = semantics.
  • Implementation Hint: Loop outer rows and inner rows; skip when either key is null/undefined; count comparisons.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Build-on-Smaller-Relation Hash Join

  • Core Database Concept: O(N + M) Hash Table Construction on the Smaller Input + Streaming Probe
  • Target Module: index.js (PhysicalJoinEngine.hashJoin)
  • Engineering Specification: Implement hashJoin(leftRows, rightRows, leftKey, rightKey) so that the smaller array is always selected as the hash build side, returning { rows, buildSize, probeOps }.
  • Implementation Hint: Build a Map<key, Array<row>> on the smaller relation (ignoring null keys), then probe with the larger relation.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: Zipper Sort-Merge Join with Duplicate Peer Group Rewind

  • Core Database Concept: Advancing Two Sorted Streams in Lockstep and Taking the Cross-Product of Equal-Key Runs
  • Target Module: index.js (PhysicalJoinEngine.sortMergeJoin)
  • Engineering Specification: Implement sortMergeJoin(leftRows, rightRows, leftKey, rightKey) to sort both inputs on their join key and merge them in a single pass with peer-group expansion.
  • Implementation Hint: Sort both inputs by join key; when keys match, collect the contiguous run of equal keys on left and right and emit their Cartesian product.
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: NULL-Safe Hash Anti-Join

  • Core Database Concept: O(N + M) Anti-Join Execution Equivalence to NOT EXISTS
  • Target Module: index.js (PhysicalJoinEngine.hashAntiJoin)
  • Engineering Specification: Implement hashAntiJoin(leftRows, rightRows, leftKey, rightKey) to return all leftRows with no matching key in rightRows, safely ignoring null keys in rightRows.
  • Implementation Hint: Insert all non-null rightKeys into a Set, then keep leftRows whose leftKey is not in that Set.
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Physical Join & Execution Operators
  • Difficulty & Time Budget: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • Block Nested Loop Join minimizing inner-relation scans via chunked outer buffering
    • Build-on-smaller-input Hash Join achieving O(N + M) linear execution cost
    • Sort-Merge Join with peer group mark-and-rewind for duplicate join keys
  • Core Primitives & Tags: Hash Join, Sort-Merge Join, Nested Loop Join, Volcano Model, Physical Operators

Related Curriculum Units

Production Database Context & Verification

This from-scratch relational engine component is engineered with zero external dependencies and deterministic verification harnesses. Every internal database invariant—from three-valued logic (TRUE / FALSE / UNKNOWN), referential integrity, and fan-out-free join pre-aggregation to B+Tree page splits, MVCC snapshot visibility (xmin / xmax), slotted-page compaction, and ARIES write-ahead log crash recovery—is asserted directly in test.js. Use the interactive browser workbench above to complete the 4 guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.