SQL Joins, Visualized

in reviewThis lesson is complete and being validated before release - details may still change.

SQL joins

Loading interactive demo…

The left and right tables are the join's two inputs, their join columns underlined; the third table is the result, filling one row per matched pair as the algorithm finds them, with the rows still to come drawn faint. The strip of left keys beneath is the tap target: pick one to light that row and every result row it took part in. Under the hash join a strip shows the buckets; under the sort-merge join two strips show the sorted keys and the pointers.Take the tour, or press and explore. Legend:

The panel beside the stage is the real JoinEngine class from the published library executing in your browser, with the current line highlighted.

The two rows under comparison, and the result row just produced.
An input row that has found a partner.
A padded result row and the unmatched row it keeps; a bucket just built.
The tapped left row and its pairings.
A null cell: the other side had no row.

comparisons counts key comparisons so far; matches and padded split the result rows by how they got there; cost states the algorithm's price in this scenario's row counts.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A filtered product. The relational model keeps one kind of fact per table, so a customer's name is in one table and the orders they placed in another, tied by the customer number both carry. A join reads them back together. Its definition is simple: every left row paired with every right row, the Cartesian product of $n \cdot m$ pairs, then keep the pairs whose keys agree. With $n = 6$ customers and $m = 9$ orders that is 54 candidate pairs and 8 survivors, each one a result row holding both sides' columns.

Three algorithms, one answer. The definition is also the first algorithm. The nested loop takes each left row and compares it with every right row: $n \cdot m$ comparisons, no memory, no preparation, and a price that doubles when either table does. The hash join spends memory to avoid the product: it builds a table of the right rows keyed by their join value, then each left row hashes its own key and reads one bucket, where every row that can match already waits. $m$ builds and $n$ probes, $O(n + m)$ as long as the table fits. The sort-merge join sorts both sides by key and walks them with two pointers, always advancing the one at the smaller key; equal keys sit level, so a single pass finds every pair, and runs of equal keys on both sides pair fully. Its price is the sort, $O(n \log n + m \log m)$ , which is free when an index already keeps a side in key order. Every algorithm produces the same pairs; they differ in comparisons, in memory, and in the order the result comes out.

Which side to build. A hash join should build the smaller side and probe with the larger, since the table has to fit in memory and the probes are the cheap part. This stage always builds the right side so that the picture stays the same shape; a planner would swap the two if the right table were the giant.

Inner and outer. The inner join keeps only pairs. A customer who ordered nothing and an order whose customer row is gone both vanish from it, which is sometimes the point and sometimes a silent loss. The outer joins keep the rows nobody matched: a left join keeps every left row, a right join every right row, a full join both, filling the other side with nulls. On this stage the padded rows appear after the matching phase, in the accent tone, and the join column is shared between the two sides the way a USING join shares it, so a padded order shows its customer number there.

Null is not a value. The null in a padded row means no row was there, and SQL treats it accordingly: it is neither equal nor unequal to anything, so price = NULL is never true and two nulls never join. Conditions over nulls use a third truth value, unknown, which is why a WHERE that filters the padded rows has to ask IS NULL rather than compare.

Choosing. Nothing in the query says which algorithm runs. The planner in the next lesson estimates each one's price from the row counts and the indexes at hand and picks per join: a nested loop when one side is tiny or indexed, a hash join for two large unsorted tables, a merge when both sides arrive sorted. The join you write is a definition; the join that runs is a choice.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

run dispatches on the algorithm and then pads, so the three matching phases differ while the outer join is one piece of code: every left row not in matchedLeft is padded for a left or full join, every right row not in matchedRight for a right or full.
compare is the single place a comparison is counted, and the nested loop and the merge both go through it. The hash join never compares keys one against one: a probe's comparisons are the rows it finds in the bucket.
The hash table is a Map keyed by the key's JSON, so a number and a string that print alike stay apart, as they would in a typed column.
The merge crosses runs: on equal keys it finds the run of that key on each side and matches every pair across the two runs before advancing both pointers. Advance only one and a duplicate key on the other side loses its partners.
match builds the result row from both tuples, dropping the right side's join attribute and prefixing any right attribute whose name the left side already uses, which is why the order's id appears as Order.id.
pad writes the string null, because a cell in this library is a scalar and the stage draws it muted; a real engine carries a null flag beside each column.
compareKeys puts numbers before strings, so a sorted run has one order whatever the column holds, and the merge never depends on the engine's own comparison of mixed values.

Edgar Codd's 1970 paper gave data a shape that needed joining: facts split across relations, tied back together by the values they share. His relational algebra made the join an operator with a definition, a Cartesian product filtered by a condition, and left how to compute it to the implementer. IBM's System R team costed the nested loop against the sort-merge in 1979 and let a planner choose; the hash join arrived from Tokyo and Wisconsin in the mid 1980s as memory grew cheap enough to hold a table; and SQL-92 finally gave the join its own keyword, with the outer joins beside it.

1970Edgar F. Codd - A Relational Model of Data for Large Shared Data Banks defines relations and the operations between them, the join among them, as pure algebra with no storage in sight.source
1974Donald Chamberlin and Raymond Boyce - SEQUEL, later SQL, lets a query name several tables in one FROM clause and tie them with an equality in WHERE: the join written as a condition.source
1979Patricia Selinger and the System R team - Access Path Selection in a Relational Database Management System costs the nested loop against the sort-merge join and picks by estimate, the first cost-based choice between join algorithms.source
1983Masaru Kitsuregawa and colleagues - The GRACE hash join partitions both inputs by hash so that each partition's join fits in memory, the ancestor of every hash join in use.source
1992ISO SQL committee - SQL-92 adds the JOIN keyword with its ON condition and the LEFT, RIGHT, and FULL OUTER forms, so the pairing and the padding are spelled in the query rather than in a vendor's notation.source

Used today

Every report that crosses a table boundary - Orders with their customers, invoices with their lines: a normalized schema puts facts in separate tables, and a join is what reads them back together.
Object-relational mappers - A relationship loaded eagerly is a join the library writes for you; loaded lazily, it is a query per row, the nested loop done over the network.
Query planners - The next lesson's planner estimates the price of each join algorithm from the row counts and picks one per join, which is why the same query can run three different ways.

tables

algorithm

join

comparisons: 54
matches: 8
padded: 0
result rows: 8 of 8
cost: 6 x 9 = 54 pairs
follow: tap a left key

join-engine.ts

import type { Relation, Scalar, Tuple } from "../relational/relation";import { RelationQuery } from "../relational/relation-query";import type { Tracer } from "../trace";/** How the pairs are found: every pair, a hash table on one side, or two sorted runs. */export const JOIN_ALGORITHMS = ["nested-loop", "hash", "sort-merge"] as const;export type JoinAlgorithm = (typeof JOIN_ALGORITHMS)[number];/** Which rows without a partner survive: none, the left side's, the right side's, or both. */export const JOIN_TYPES = ["inner", "left", "right", "full"] as const;export type JoinType = (typeof JOIN_TYPES)[number];/** Rows per side: the stage draws both inputs and the result as tables. */export const MAX_JOIN_ROWS = 12;/** What a padded row carries where the other side had no row: the stage's null, since a cell is a scalar. */export const NULL_CELL = "null";export interface JoinSpec {  left: Relation;  right: Relation;  /** The attribute of each side whose values must agree. */  on: { left: string; right: string };  algorithm: JoinAlgorithm;  type: JoinType;  /** The result relation's name. */  name: string;}export interface JoinResult {  relation: Relation;  /** Key comparisons made: every pair for a nested loop, the bucket entries examined for a hash, the pointer comparisons for a merge. */  comparisons: number;  matches: number;  unmatchedLeft: number;  unmatchedRight: number;}/** * A join pairs the rows of two tables whose keys agree, which is a * Cartesian product with a filter, and three algorithms find the same * pairs at very different prices. The nested loop compares every left * row with every right row, n times m comparisons and no memory. The * hash join builds a table of the right rows keyed by their join value * and probes it once per left row, n plus m work when the table fits in * memory. The sort-merge join sorts both sides and walks them with two * pointers, advancing whichever points at the smaller key, so every * pair is found in one pass after the sort. An outer join then pads * every row that found no partner with nulls on the other side: the * left rows, the right rows, or both. * * Time: O(nm) for the nested loop, O(n + m) for the hash join, O(n log n + m log m) for the merge. Space: O(m) for the hash table, O(n + m) for the sorted orders. */export class JoinEngine {  private readonly rows: Tuple[] = [];  private readonly attributes: readonly string[];  private readonly matchedLeft = new Set<number>();  private readonly matchedRight = new Set<number>();  private comparisons = 0;  private matchedPairs = 0;  constructor(    readonly spec: JoinSpec,    private readonly tracer?: Tracer,  ) {    const { left, right, on, algorithm, type } = spec;    if (!left.attributes.includes(on.left)) throw new RangeError(`no attribute "${on.left}" on ${left.name}`);    if (!right.attributes.includes(on.right)) throw new RangeError(`no attribute "${on.right}" on ${right.name}`);    if (!JOIN_ALGORITHMS.includes(algorithm)) throw new RangeError(`unknown algorithm ${String(algorithm)}`);    if (!JOIN_TYPES.includes(type)) throw new RangeError(`unknown join type ${String(type)}`);    if (left.tuples.length > MAX_JOIN_ROWS || right.tuples.length > MAX_JOIN_ROWS) throw new RangeError(`a side exceeds ${MAX_JOIN_ROWS} rows`);    this.attributes = JoinEngine.outputAttributes(left, right, on.right);  }  /**   * The result's attributes: the left side's, then the right side's   * without its join attribute; a right attribute whose name the left   * side already uses is prefixed with the right relation's name.   */  static outputAttributes(left: Relation, right: Relation, rightKey: string): string[] {    const fromRight = right.attributes.filter((attribute) => attribute !== rightKey).map((attribute) => (left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute));    return [...left.attributes, ...fromRight];  }  /** Numbers before strings, each in their own order; the key order every sorted run uses. */  static compareKeys(a: Scalar, b: Scalar): number {    if (typeof a === "number" && typeof b === "number") return a - b;    if (typeof a === "number") return -1;    if (typeof b === "number") return 1;    return a < b ? -1 : a > b ? 1 : 0;  }  /** The whole join: the algorithm's matching phase, then the padding an outer join asks for. */  run(): JoinResult {    const { algorithm, type, left, right, name } = this.spec;    if (algorithm === "nested-loop") this.nestedLoop();    else if (algorithm === "hash") this.hashJoin();    else this.sortMerge();    if (type === "left" || type === "full") {      for (let i = 0; i < left.tuples.length; i++) if (!this.matchedLeft.has(i)) this.pad("left", i);      for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) if (!this.matchedLeft.has(leftRow)) this.pad("left", leftRow);    }    if (type === "right" || type === "full") {      for (let j = 0; j < right.tuples.length; j++) if (!this.matchedRight.has(j)) this.pad("right", j);      for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) if (!this.matchedRight.has(rightRow)) this.pad("right", rightRow);    }    return {      relation: { name, attributes: [...this.attributes], tuples: [...this.rows] },      comparisons: this.comparisons,      matches: this.matchedPairs,      unmatchedLeft: left.tuples.length - this.matchedLeft.size,      unmatchedRight: right.tuples.length - this.matchedRight.size,    };  }  private leftKey(i: number): Scalar {  private leftKey(leftRow: number): Scalar {    return RelationQuery.cell(this.spec.left.tuples[i]!, this.spec.on.left) as Scalar;    return RelationQuery.cell(this.spec.left.tuples[leftRow]!, this.spec.on.left) as Scalar;  }  private rightKey(j: number): Scalar {  private rightKey(rightRow: number): Scalar {    return RelationQuery.cell(this.spec.right.tuples[j]!, this.spec.on.right) as Scalar;    return RelationQuery.cell(this.spec.right.tuples[rightRow]!, this.spec.on.right) as Scalar;  }  /** Every left row against every right row: no memory, n times m comparisons. */  private nestedLoop(): void {    const { left, right } = this.spec;    for (let i = 0; i < left.tuples.length; i++) {    for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) {      for (let j = 0; j < right.tuples.length; j++) {      for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) {        const equal = this.compare(i, j, j === right.tuples.length - 1 ? "left" : "right");        const equal = this.compare(leftRow, rightRow, rightRow === right.tuples.length - 1 ? "left" : "right");        if (equal) this.match(i, j);        if (equal) this.match(leftRow, rightRow);      }    }  }  /** Build a table of the right rows by key, then probe it once per left row. */  private hashJoin(): void {    const { left, right } = this.spec;    const buckets = new Map<string, number[]>();    for (let j = 0; j < right.tuples.length; j++) {    for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) {      const key = this.rightKey(j);      const key = this.rightKey(rightRow);      const bucket = buckets.get(JSON.stringify(key)) ?? [];      bucket.push(j);      bucket.push(rightRow);      buckets.set(JSON.stringify(key), bucket);      // ▸ drop this right row into the bucket its key hashes to; later probes find it there      this.tracer?.emit("build", { right: j, key, bucket: bucket.length, buckets: buckets.size });      this.tracer?.emit("build", { right: rightRow, key, bucket: bucket.length, buckets: buckets.size });    }    for (let i = 0; i < left.tuples.length; i++) {    for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) {      const key = this.leftKey(i);      const key = this.leftKey(leftRow);      const bucket = buckets.get(JSON.stringify(key)) ?? [];      this.comparisons += bucket.length;      // ▸ hash the left row's key and read its bucket: the right rows that can match are all there      this.tracer?.emit("probe", { left: i, key, found: bucket.length, comparisons: this.comparisons });      this.tracer?.emit("probe", { left: leftRow, key, found: bucket.length, comparisons: this.comparisons });      for (const j of bucket) this.match(i, j);      for (const rightRow of bucket) this.match(leftRow, rightRow);    }  }  /** Sort both sides by key, then walk them with two pointers, advancing the smaller. */  private sortMerge(): void {    const { left, right } = this.spec;    const leftOrder = left.tuples.map((_, i) => i).sort((a, b) => JoinEngine.compareKeys(this.leftKey(a), this.leftKey(b)) || a - b);    const leftOrder = left.tuples.map((_, leftRow) => leftRow).sort((a, b) => JoinEngine.compareKeys(this.leftKey(a), this.leftKey(b)) || a - b);    const rightOrder = right.tuples.map((_, j) => j).sort((a, b) => JoinEngine.compareKeys(this.rightKey(a), this.rightKey(b)) || a - b);    const rightOrder = right.tuples.map((_, rightRow) => rightRow).sort((a, b) => JoinEngine.compareKeys(this.rightKey(a), this.rightKey(b)) || a - b);    // ▸ sort both sides by key, so equal keys sit level and a single pass finds every pair    this.tracer?.emit("sort", { leftOrder, rightOrder, leftKeys: leftOrder.map((i) => this.leftKey(i)), rightKeys: rightOrder.map((j) => this.rightKey(j)) });    this.tracer?.emit("sort", { leftOrder, rightOrder, leftKeys: leftOrder.map((leftRow) => this.leftKey(leftRow)), rightKeys: rightOrder.map((rightRow) => this.rightKey(rightRow)) });    let a = 0;    let b = 0;    while (a < leftOrder.length && b < rightOrder.length) {      const i = leftOrder[a]!;      const leftRow = leftOrder[a]!;      const j = rightOrder[b]!;      const rightRow = rightOrder[b]!;      const order = JoinEngine.compareKeys(this.leftKey(i), this.rightKey(j));      const order = JoinEngine.compareKeys(this.leftKey(leftRow), this.rightKey(rightRow));      const equal = this.compare(i, j, order < 0 ? "left" : order > 0 ? "right" : "both");      const equal = this.compare(leftRow, rightRow, order < 0 ? "left" : order > 0 ? "right" : "both");      if (!equal) {        if (order < 0) a++;        else b++;        continue;      }      // A run of equal keys on each side: every pair across the two runs is a match.      let aEnd = a;      while (aEnd < leftOrder.length && JoinEngine.compareKeys(this.leftKey(leftOrder[aEnd]!), this.leftKey(i)) === 0) aEnd++;      while (aEnd < leftOrder.length && JoinEngine.compareKeys(this.leftKey(leftOrder[aEnd]!), this.leftKey(leftRow)) === 0) aEnd++;      let bEnd = b;      while (bEnd < rightOrder.length && JoinEngine.compareKeys(this.rightKey(rightOrder[bEnd]!), this.rightKey(j)) === 0) bEnd++;      while (bEnd < rightOrder.length && JoinEngine.compareKeys(this.rightKey(rightOrder[bEnd]!), this.rightKey(rightRow)) === 0) bEnd++;      for (let x = a; x < aEnd; x++) for (let y = b; y < bEnd; y++) this.match(leftOrder[x]!, rightOrder[y]!);      a = aEnd;      b = bEnd;    }  }  /** One key comparison, the single place the count grows; `advance` says which pointer moves next. */  private compare(i: number, j: number, advance: "left" | "right" | "both"): boolean {  private compare(leftRow: number, rightRow: number, advance: "left" | "right" | "both"): boolean {    const leftKey = this.leftKey(i);    const leftKey = this.leftKey(leftRow);    const rightKey = this.rightKey(j);    const rightKey = this.rightKey(rightRow);    const equal = JoinEngine.compareKeys(leftKey, rightKey) === 0;    this.comparisons++;    // ▸ put a left key beside a right key: equal means the two rows belong together    this.tracer?.emit("compare", { left: i, right: j, leftKey, rightKey, equal, advance, comparisons: this.comparisons });    this.tracer?.emit("compare", { left: leftRow, right: rightRow, leftKey, rightKey, equal, advance, comparisons: this.comparisons });    return equal;  }  /** Output the left row joined to the right row: the one place a pair becomes a result row. */  private match(i: number, j: number): void {  private match(leftRow: number, rightRow: number): void {    const { left, right, on } = this.spec;    const row: Record<string, Scalar | readonly Scalar[]> = {};    for (const attribute of left.attributes) row[attribute] = RelationQuery.cell(left.tuples[i]!, attribute);    for (const attribute of left.attributes) row[attribute] = RelationQuery.cell(left.tuples[leftRow]!, attribute);    for (const attribute of right.attributes) {      if (attribute === on.right) continue;      row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = RelationQuery.cell(right.tuples[j]!, attribute);      row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = RelationQuery.cell(right.tuples[rightRow]!, attribute);    }    this.rows.push(row);    this.matchedLeft.add(i);    this.matchedLeft.add(leftRow);    this.matchedRight.add(j);    this.matchedRight.add(rightRow);    this.matchedPairs++;    // ▸ the keys agree: output the left row joined to the right row    this.tracer?.emit("match", { left: i, right: j, key: this.leftKey(i), row, rows: this.rows.length });    this.tracer?.emit("match", { left: leftRow, right: rightRow, key: this.leftKey(leftRow), row, rows: this.rows.length });  }  /**   * Output a row that found no partner, nulls on the other side: the   * outer join's one addition. The join column is shared, as a USING   * join shares it, so a padded right row shows its key there.   */  private pad(side: "left" | "right", index: number): void {    const { left, right, on } = this.spec;    const row: Record<string, Scalar | readonly Scalar[]> = {};    const source = side === "left" ? left.tuples[index]! : right.tuples[index]!;    for (const attribute of left.attributes) row[attribute] = side === "left" ? RelationQuery.cell(source, attribute) : NULL_CELL;    for (const attribute of right.attributes) {      if (attribute === on.right) continue;      row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = side === "right" ? RelationQuery.cell(source, attribute) : NULL_CELL;    }    if (side === "right") row[on.left] = RelationQuery.cell(source, on.right);    this.rows.push(row);    const key = side === "left" ? this.leftKey(index) : this.rightKey(index);    // ▸ an outer join keeps a row nobody matched, with nulls where the other side would be    this.tracer?.emit("pad", { side, index, key, row, rows: this.rows.length });  }}

comparisons =: 54
rows =: 8

The inner join by nested loop made 54 comparisons and found 8 pairs; 1 left row and 1 right row had no partner. The result holds 8 rows.

import type { Relation, Scalar, Tuple } from "../relational/relation";import { RelationQuery } from "../relational/relation-query";import type { Tracer } from "../trace";/** How the pairs are found: every pair, a hash table on one side, or two sorted runs. */export const JOIN_ALGORITHMS = ["nested-loop", "hash", "sort-merge"] as const;export type JoinAlgorithm = (typeof JOIN_ALGORITHMS)[number];/** Which rows without a partner survive: none, the left side's, the right side's, or both. */export const JOIN_TYPES = ["inner", "left", "right", "full"] as const;export type JoinType = (typeof JOIN_TYPES)[number];/** Rows per side: the stage draws both inputs and the result as tables. */export const MAX_JOIN_ROWS = 12;/** What a padded row carries where the other side had no row: the stage's null, since a cell is a scalar. */export const NULL_CELL = "null";export interface JoinSpec { left: Relation; right: Relation; /** The attribute of each side whose values must agree. */ on: { left: string; right: string }; algorithm: JoinAlgorithm; type: JoinType; /** The result relation's name. */ name: string;}export interface JoinResult { relation: Relation; /** Key comparisons made: every pair for a nested loop, the bucket entries examined for a hash, the pointer comparisons for a merge. */ comparisons: number; matches: number; unmatchedLeft: number; unmatchedRight: number;}/** * A join pairs the rows of two tables whose keys agree, which is a * Cartesian product with a filter, and three algorithms find the same * pairs at very different prices. The nested loop compares every left * row with every right row, n times m comparisons and no memory. The * hash join builds a table of the right rows keyed by their join value * and probes it once per left row, n plus m work when the table fits in * memory. The sort-merge join sorts both sides and walks them with two * pointers, advancing whichever points at the smaller key, so every * pair is found in one pass after the sort. An outer join then pads * every row that found no partner with nulls on the other side: the * left rows, the right rows, or both. * * Time: O(nm) for the nested loop, O(n + m) for the hash join, O(n log n + m log m) for the merge. Space: O(m) for the hash table, O(n + m) for the sorted orders. */export class JoinEngine { private readonly rows: Tuple[] = []; private readonly attributes: readonly string[]; private readonly matchedLeft = new Set<number>(); private readonly matchedRight = new Set<number>(); private comparisons = 0; private matchedPairs = 0; constructor( readonly spec: JoinSpec, private readonly tracer?: Tracer, ) { const { left, right, on, algorithm, type } = spec; if (!left.attributes.includes(on.left)) throw new RangeError(`no attribute "${on.left}" on ${left.name}`); if (!right.attributes.includes(on.right)) throw new RangeError(`no attribute "${on.right}" on ${right.name}`); if (!JOIN_ALGORITHMS.includes(algorithm)) throw new RangeError(`unknown algorithm ${String(algorithm)}`); if (!JOIN_TYPES.includes(type)) throw new RangeError(`unknown join type ${String(type)}`); if (left.tuples.length > MAX_JOIN_ROWS || right.tuples.length > MAX_JOIN_ROWS) throw new RangeError(`a side exceeds ${MAX_JOIN_ROWS} rows`); this.attributes = JoinEngine.outputAttributes(left, right, on.right); } /** * The result's attributes: the left side's, then the right side's * without its join attribute; a right attribute whose name the left * side already uses is prefixed with the right relation's name. */ static outputAttributes(left: Relation, right: Relation, rightKey: string): string[] { const fromRight = right.attributes.filter((attribute) => attribute !== rightKey).map((attribute) => (left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute)); return [...left.attributes, ...fromRight]; } /** Numbers before strings, each in their own order; the key order every sorted run uses. */ static compareKeys(a: Scalar, b: Scalar): number { if (typeof a === "number" && typeof b === "number") return a - b; if (typeof a === "number") return -1; if (typeof b === "number") return 1; return a < b ? -1 : a > b ? 1 : 0; } /** The whole join: the algorithm's matching phase, then the padding an outer join asks for. */ run(): JoinResult { const { algorithm, type, left, right, name } = this.spec; if (algorithm === "nested-loop") this.nestedLoop(); else if (algorithm === "hash") this.hashJoin(); else this.sortMerge(); if (type === "left" || type === "full") { for (let i = 0; i < left.tuples.length; i++) if (!this.matchedLeft.has(i)) this.pad("left", i); for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) if (!this.matchedLeft.has(leftRow)) this.pad("left", leftRow); } if (type === "right" || type === "full") { for (let j = 0; j < right.tuples.length; j++) if (!this.matchedRight.has(j)) this.pad("right", j); for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) if (!this.matchedRight.has(rightRow)) this.pad("right", rightRow); } return { relation: { name, attributes: [...this.attributes], tuples: [...this.rows] }, comparisons: this.comparisons, matches: this.matchedPairs, unmatchedLeft: left.tuples.length - this.matchedLeft.size, unmatchedRight: right.tuples.length - this.matchedRight.size, }; } private leftKey(i: number): Scalar { private leftKey(leftRow: number): Scalar { return RelationQuery.cell(this.spec.left.tuples[i]!, this.spec.on.left) as Scalar; return RelationQuery.cell(this.spec.left.tuples[leftRow]!, this.spec.on.left) as Scalar; } private rightKey(j: number): Scalar { private rightKey(rightRow: number): Scalar { return RelationQuery.cell(this.spec.right.tuples[j]!, this.spec.on.right) as Scalar; return RelationQuery.cell(this.spec.right.tuples[rightRow]!, this.spec.on.right) as Scalar; } /** Every left row against every right row: no memory, n times m comparisons. */ private nestedLoop(): void { const { left, right } = this.spec; for (let i = 0; i < left.tuples.length; i++) { for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) { for (let j = 0; j < right.tuples.length; j++) { for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) { const equal = this.compare(i, j, j === right.tuples.length - 1 ? "left" : "right"); const equal = this.compare(leftRow, rightRow, rightRow === right.tuples.length - 1 ? "left" : "right"); if (equal) this.match(i, j); if (equal) this.match(leftRow, rightRow); } } } /** Build a table of the right rows by key, then probe it once per left row. */ private hashJoin(): void { const { left, right } = this.spec; const buckets = new Map<string, number[]>(); for (let j = 0; j < right.tuples.length; j++) { for (let rightRow = 0; rightRow < right.tuples.length; rightRow++) { const key = this.rightKey(j); const key = this.rightKey(rightRow); const bucket = buckets.get(JSON.stringify(key)) ?? []; bucket.push(j); bucket.push(rightRow); buckets.set(JSON.stringify(key), bucket); // ▸ drop this right row into the bucket its key hashes to; later probes find it there this.tracer?.emit("build", { right: j, key, bucket: bucket.length, buckets: buckets.size }); this.tracer?.emit("build", { right: rightRow, key, bucket: bucket.length, buckets: buckets.size }); } for (let i = 0; i < left.tuples.length; i++) { for (let leftRow = 0; leftRow < left.tuples.length; leftRow++) { const key = this.leftKey(i); const key = this.leftKey(leftRow); const bucket = buckets.get(JSON.stringify(key)) ?? []; this.comparisons += bucket.length; // ▸ hash the left row's key and read its bucket: the right rows that can match are all there this.tracer?.emit("probe", { left: i, key, found: bucket.length, comparisons: this.comparisons }); this.tracer?.emit("probe", { left: leftRow, key, found: bucket.length, comparisons: this.comparisons }); for (const j of bucket) this.match(i, j); for (const rightRow of bucket) this.match(leftRow, rightRow); } } /** Sort both sides by key, then walk them with two pointers, advancing the smaller. */ private sortMerge(): void { const { left, right } = this.spec; const leftOrder = left.tuples.map((_, i) => i).sort((a, b) => JoinEngine.compareKeys(this.leftKey(a), this.leftKey(b)) || a - b); const leftOrder = left.tuples.map((_, leftRow) => leftRow).sort((a, b) => JoinEngine.compareKeys(this.leftKey(a), this.leftKey(b)) || a - b); const rightOrder = right.tuples.map((_, j) => j).sort((a, b) => JoinEngine.compareKeys(this.rightKey(a), this.rightKey(b)) || a - b); const rightOrder = right.tuples.map((_, rightRow) => rightRow).sort((a, b) => JoinEngine.compareKeys(this.rightKey(a), this.rightKey(b)) || a - b); // ▸ sort both sides by key, so equal keys sit level and a single pass finds every pair this.tracer?.emit("sort", { leftOrder, rightOrder, leftKeys: leftOrder.map((i) => this.leftKey(i)), rightKeys: rightOrder.map((j) => this.rightKey(j)) }); this.tracer?.emit("sort", { leftOrder, rightOrder, leftKeys: leftOrder.map((leftRow) => this.leftKey(leftRow)), rightKeys: rightOrder.map((rightRow) => this.rightKey(rightRow)) }); let a = 0; let b = 0; while (a < leftOrder.length && b < rightOrder.length) { const i = leftOrder[a]!; const leftRow = leftOrder[a]!; const j = rightOrder[b]!; const rightRow = rightOrder[b]!; const order = JoinEngine.compareKeys(this.leftKey(i), this.rightKey(j)); const order = JoinEngine.compareKeys(this.leftKey(leftRow), this.rightKey(rightRow)); const equal = this.compare(i, j, order < 0 ? "left" : order > 0 ? "right" : "both"); const equal = this.compare(leftRow, rightRow, order < 0 ? "left" : order > 0 ? "right" : "both"); if (!equal) { if (order < 0) a++; else b++; continue; } // A run of equal keys on each side: every pair across the two runs is a match. let aEnd = a; while (aEnd < leftOrder.length && JoinEngine.compareKeys(this.leftKey(leftOrder[aEnd]!), this.leftKey(i)) === 0) aEnd++; while (aEnd < leftOrder.length && JoinEngine.compareKeys(this.leftKey(leftOrder[aEnd]!), this.leftKey(leftRow)) === 0) aEnd++; let bEnd = b; while (bEnd < rightOrder.length && JoinEngine.compareKeys(this.rightKey(rightOrder[bEnd]!), this.rightKey(j)) === 0) bEnd++; while (bEnd < rightOrder.length && JoinEngine.compareKeys(this.rightKey(rightOrder[bEnd]!), this.rightKey(rightRow)) === 0) bEnd++; for (let x = a; x < aEnd; x++) for (let y = b; y < bEnd; y++) this.match(leftOrder[x]!, rightOrder[y]!); a = aEnd; b = bEnd; } } /** One key comparison, the single place the count grows; `advance` says which pointer moves next. */ private compare(i: number, j: number, advance: "left" | "right" | "both"): boolean { private compare(leftRow: number, rightRow: number, advance: "left" | "right" | "both"): boolean { const leftKey = this.leftKey(i); const leftKey = this.leftKey(leftRow); const rightKey = this.rightKey(j); const rightKey = this.rightKey(rightRow); const equal = JoinEngine.compareKeys(leftKey, rightKey) === 0; this.comparisons++; // ▸ put a left key beside a right key: equal means the two rows belong together this.tracer?.emit("compare", { left: i, right: j, leftKey, rightKey, equal, advance, comparisons: this.comparisons }); this.tracer?.emit("compare", { left: leftRow, right: rightRow, leftKey, rightKey, equal, advance, comparisons: this.comparisons }); return equal; } /** Output the left row joined to the right row: the one place a pair becomes a result row. */ private match(i: number, j: number): void { private match(leftRow: number, rightRow: number): void { const { left, right, on } = this.spec; const row: Record<string, Scalar | readonly Scalar[]> = {}; for (const attribute of left.attributes) row[attribute] = RelationQuery.cell(left.tuples[i]!, attribute); for (const attribute of left.attributes) row[attribute] = RelationQuery.cell(left.tuples[leftRow]!, attribute); for (const attribute of right.attributes) { if (attribute === on.right) continue; row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = RelationQuery.cell(right.tuples[j]!, attribute); row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = RelationQuery.cell(right.tuples[rightRow]!, attribute); } this.rows.push(row); this.matchedLeft.add(i); this.matchedLeft.add(leftRow); this.matchedRight.add(j); this.matchedRight.add(rightRow); this.matchedPairs++; // ▸ the keys agree: output the left row joined to the right row this.tracer?.emit("match", { left: i, right: j, key: this.leftKey(i), row, rows: this.rows.length }); this.tracer?.emit("match", { left: leftRow, right: rightRow, key: this.leftKey(leftRow), row, rows: this.rows.length }); } /** * Output a row that found no partner, nulls on the other side: the * outer join's one addition. The join column is shared, as a USING * join shares it, so a padded right row shows its key there. */ private pad(side: "left" | "right", index: number): void { const { left, right, on } = this.spec; const row: Record<string, Scalar | readonly Scalar[]> = {}; const source = side === "left" ? left.tuples[index]! : right.tuples[index]!; for (const attribute of left.attributes) row[attribute] = side === "left" ? RelationQuery.cell(source, attribute) : NULL_CELL; for (const attribute of right.attributes) { if (attribute === on.right) continue; row[left.attributes.includes(attribute) ? `${right.name}.${attribute}` : attribute] = side === "right" ? RelationQuery.cell(source, attribute) : NULL_CELL; } if (side === "right") row[on.left] = RelationQuery.cell(source, on.right); this.rows.push(row); const key = side === "left" ? this.leftKey(index) : this.rightKey(index); // ▸ an outer join keeps a row nobody matched, with nulls where the other side would be this.tracer?.emit("pad", { side, index, key, row, rows: this.rows.length }); }}