Query Plans: How SQL Executes

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

Query planning

Loading interactive demo…

The tree is a plan: the root operator at the top pulls rows from the operators beneath it, a scan or an index seek at every leaf. The strip under it lists every plan the search priced, in order, each with its cost in page reads; the strip under that holds the table statistics the costs were computed from. Tap a plan in the strip to see its tree.Take the tour, or press and explore. Legend:

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

The plan this step prices, prunes, or chooses, and its operators.
The chosen plan, the cheapest over every table.
A plan still kept as the best over its tables.
A plan pruned by a cheaper one over the same tables, and plans not yet priced.

priced counts the plans met so far; pruned those dropped; best cost and best rows describe the cheapest complete plan met so far; shown says what the tree draws and what it costs.

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

What, not how. The join lesson ran three algorithms by hand and the B-tree lesson built the index a seek descends. A SQL query names neither: it says which tables, which condition ties them, which rows to keep. Between the query and the rows sits the planner, which turns the declaration into a plan, a tree of operators that each pull rows from the ones beneath them. The same query becomes a different plan on a table of six rows and a table of sixty thousand, and that is the point: the data decides, not the programmer.

Three parts. A planner needs statistics, a cost model, and a search. The statistics are numbers about each table: rows $N$ , pages $P$ , distinct values $d_A$ of each attribute $A$ , which attributes have an index. The cost model prices an operator from those numbers. The search enumerates plans and keeps the cheapest. The stage's cost unit is the page read, the dominant cost when data lives on disk, and the numbers are the ones in the strip: nothing about a row is ever read.

Selectivity. An equality filter on $A$ keeps about $N / d_A$ rows, assuming values spread evenly. A join of $R$ and $S$ on $R.A = S.B$ returns about $|R| \cdot |S| / \max(d_A, d_B)$ rows. These two formulas are nearly the whole of estimation, and they are also where it goes wrong: a city column with four values is not evenly spread, and two filters on correlated columns do not multiply.

Pricing a path. A scan costs $P$ pages. An index seek with selectivity $s$ costs the tree's height, about $\lceil \log_2 N \rceil$ , plus a page per matching row, $\lceil s N \rceil$ . At the small scale the scan is one page and always wins; at the large scale the seek wins whenever $s$ is small. A nested loop costs the outer plan plus, for each outer row, either a seek into an index on the inner table's join attribute or a rescan of the inner plan; a hash join costs both inputs plus a pass over each; a merge join costs both inputs plus a sort of each side not already delivered in order by an index. Small outer, indexed inner: that is the pattern the filtered query rewards.

The search. System R's insight was that the best plan for a set of tables contains the best plan for the set minus one table, because costs add. So the planner works up by subset size: the best path for each table, then the best join for each pair, then each triple built from a best pair plus one table, pruning at every size any plan that costs more than the kept plan over the same tables. Nothing is ever built on a pruned plan. The stage considers only left-deep trees, where the inner side of every join is a single table; a real planner may consider bushy trees too, at the price of a larger search.

Where it goes wrong. Every number on the stage is an estimate. The distinct counts may be stale, the even-spread assumption may be false, and the error in a row estimate compounds through every join above it. A plan that is cheapest on paper can be the slowest in practice, which is why every database can show its plan with the estimates beside the actual counts, and why running the statistics collector is the first thing to try when a query is slow.

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

plan runs in two passes, access paths per table and then subsets by size, and every plan it prices goes through one register, so a candidate's id is simply its place in the order the search met it. The stage's strip is that list.
keepCheapest is the whole of dynamic programming: the kept plan for a set of tables against a new one, the dearer pruned through a single prune method. Ties keep the earlier plan, so the search is deterministic.
subsets enumerates every subset in the query's own order, smaller sets first, and joining finds the condition that ties a table to a set; a table nothing joins is never added, so a Cartesian product is never priced.
join is the cost model in one method, three formulas in page reads kept to integers with Math.ceil, so two plans never differ by rounding alone. indexed answers the one question two of the formulas share: is this side a single table with an index on its join attribute?
The statistics are a map by table name and nothing else is stored: the planner is stateless between queries apart from the list of candidates it hands back in the report.

Codd's relational model of 1970 promised that a query would name the rows it wanted and nothing about how to find them, leaving the system to work that out. IBM's System R built the first serious answer: in 1979 Patricia Selinger and her colleagues described an optimizer that priced every access path and join order from statistics about the tables and picked the cheapest by dynamic programming over left-deep trees. Nearly every relational database since has a planner of that shape, still called Selinger-style.

1970Edgar F. Codd - A Relational Model of Data for Large Shared Data Banks separates what a query asks from how it is answered, which makes a planner necessary.source
1979Patricia Selinger, Morton Astrahan, Donald Chamberlin, Raymond Lorie, and Thomas Price - Access Path Selection in a Relational Database Management System describes System R's cost-based optimizer: statistics, a cost formula in page reads and CPU, and dynamic programming over join orders.source
1993Goetz Graefe and William McKenna - The Volcano optimizer generator separates the search from the rules it applies, the design behind the Cascades framework and the optimizers of several commercial systems.source
2002The PostgreSQL project - PostgreSQL 7.2 adds EXPLAIN ANALYZE, which runs the chosen plan and prints the actual row counts and times beside the planner's estimates, making the estimates something a user can check.source

Used today

Every SQL database - The same query runs as a different plan on a small table and a large one, which is the point: the data decides, not the programmer.
Indexes that pay off, or do not - An index is only used when the planner's estimate says a seek beats a scan; the stage shows the scale where that turns.
Reading an EXPLAIN - The plan tree, the estimated rows, and the cost per operator in a database's EXPLAIN output are exactly what this stage draws.

query

scale

indexes

priced: 8 of 8
pruned: 5
best cost: 30 page reads
best rows: 2
shown: plan 2, 30 (chosen)

query-planner.ts

import type { Tracer } from "../trace";/** Tables one query may name; three keeps the search small enough to watch. */export const MAX_QUERY_TABLES = 3;export const JOIN_STRATEGIES = ["nested-loop", "hash", "merge"] as const;export type JoinStrategy = (typeof JOIN_STRATEGIES)[number];/** What the planner knows about a table: never the rows, only numbers about them. */export interface TableStats {  name: string;  rows: number;  /** Disk pages the rows occupy; a scan reads every one. */  pages: number;  /** Attributes with an index. */  indexes: readonly string[];  /** Distinct values per attribute, for selectivity; every attribute the query may name appears here. */  distinct: Readonly<Record<string, number>>;}/** An equality filter, `table.attribute = constant`. */export interface Predicate {  table: string;  attribute: string;  /** The share of rows that pass; defaults to one over the attribute's distinct count. */  selectivity?: number;}export interface JoinCondition {  left: string;  leftAttribute: string;  right: string;  rightAttribute: string;}export interface Query {  tables: readonly string[];  joins: readonly JoinCondition[];  filters: readonly Predicate[];}export interface ScanNode {  kind: "scan";  table: string;  rows: number;  cost: number;}export interface SeekNode {  kind: "index-seek";  table: string;  attribute: string;  rows: number;  cost: number;}export interface JoinNode {  kind: "join";  algorithm: JoinStrategy;  outer: PlanNode;  inner: PlanNode;  rows: number;  cost: number;}export type PlanNode = ScanNode | SeekNode | JoinNode;/** One plan the search priced: an access path for one table, or a join tree over several. */export interface Candidate {  id: number;  plan: PlanNode;  cost: number;  rows: number;  tables: readonly string[];}export interface PlanReport {  /** Every plan priced, in the order the search met them. */  candidates: readonly Candidate[];  best: Candidate;  considered: number;  pruned: number;}const ceilLog2 = (n: number): number => Math.max(1, Math.ceil(Math.log2(Math.max(2, n))));/** * SQL says which rows, never how to get them. A cost-based planner turns * a query into a plan by pricing the alternatives: the ways to reach each * table (a scan of every page, or a seek through an index when a filter * names an indexed attribute), then the ways to join the tables, in every * order and by every algorithm, each costed in page reads from the table * statistics alone. It never reads a row. The search is dynamic * programming over subsets of tables the way System R did it: the best * plan for a set of tables is built from the best plan for the set minus * one table, so a plan that loses to a cheaper one over the same tables * is pruned and never extended. Only left-deep trees are considered, * where the inner side of every join is a single table. * * The cost model, in page reads: a scan costs the table's pages; an index * seek costs the tree's height plus a page per row that qualifies; a * nested loop costs the outer plan plus, per outer row, either a seek * into an index on the inner table's join attribute or a rescan of the * inner plan; a hash join costs both inputs plus a pass over each; a merge * join costs both inputs plus a sort of each side that is not already an * index on its join attribute. Join cardinality is the product of the * inputs over the larger distinct count of the two join attributes. * * Time: O(2^n * n * algorithms) over n tables. Space: O(2^n) kept plans. */export class QueryPlanner {  private readonly stats: ReadonlyMap<string, TableStats>;  private candidates: Candidate[] = [];  private pruned = 0;  constructor(    stats: readonly TableStats[],    private readonly tracer?: Tracer,  ) {    for (const table of stats) {      if (!Number.isInteger(table.rows) || table.rows < 1) throw new RangeError(`${table.name} needs at least one row`);      if (!Number.isInteger(table.pages) || table.pages < 1) throw new RangeError(`${table.name} needs at least one page`);      for (const attribute of table.indexes) if (!(attribute in table.distinct)) throw new RangeError(`${table.name} indexes unknown attribute ${attribute}`);    }    this.stats = new Map(stats.map((table) => [table.name, table]));  }  /** Prices every access path and every left-deep join tree, pruning as it goes, and returns the cheapest. */  plan(query: Query): PlanReport {    this.validate(query);    this.candidates = [];    this.pruned = 0;    const best = new Map<string, Candidate>();    for (const name of query.tables) {      const table = this.stats.get(name)!;      // ▸ the planner reads numbers about the table, never its rows: how many rows, how many pages, which attributes have an index      this.tracer?.emit("stats", { table: name, rows: table.rows, pages: table.pages, indexes: [...table.indexes] });      const filters = query.filters.filter((filter) => filter.table === name);      const paths: Candidate[] = [this.accessPath({ kind: "scan", table: name, rows: this.filteredRows(table, filters), cost: table.pages })];      for (const filter of filters) {        if (!table.indexes.includes(filter.attribute)) continue;        const rows = this.filteredRows(table, filters);        paths.push(this.accessPath({ kind: "index-seek", table: name, attribute: filter.attribute, rows, cost: ceilLog2(table.rows) + Math.ceil(table.rows * this.selectivity(table, filter)) }));      }      best.set(name, this.keepCheapest(paths, best.get(name) ?? null));    }    const subsets = QueryPlanner.subsets(query.tables).filter((set) => set.length >= 2);    for (const set of subsets) {      const key = set.join("+");      // The last-named table is tried as the inner side first, so the query's own order is the first plan priced.      for (const inner of [...set].reverse()) {        const rest = set.filter((name) => name !== inner);        const outerTables = set.filter((name) => name !== inner);        const outer = best.get(rest.join("+"));        const outer = best.get(outerTables.join("+"));        if (!outer) continue;        const condition = this.joining(query, rest, inner);        const condition = this.joining(query, outerTables, inner);        if (!condition) continue;        const innerPath = best.get(inner)!;        for (const algorithm of JOIN_STRATEGIES) {          const plan = this.join(algorithm, outer.plan, innerPath.plan, condition);          const candidate = this.register(plan, set);          // ▸ the kept plan for the smaller set joins one more table by one algorithm, and the cost model prices the result          this.tracer?.emit("candidate", { id: candidate.id, tables: [...set], algorithm, outer: QueryPlanner.describe(outer.plan), inner: QueryPlanner.describe(innerPath.plan), rows: plan.rows, cost: plan.cost });          best.set(key, this.keepCheapest([candidate], best.get(key) ?? null));        }      }    }    const winner = best.get(query.tables.join("+"));    if (!winner) throw new RangeError("the query's tables are not all joined to one another");    // ▸ the kept plan for the whole set of tables is the plan that runs    this.tracer?.emit("choose", { id: winner.id, cost: winner.cost, rows: winner.rows, plan: QueryPlanner.describe(winner.plan) });    return { candidates: [...this.candidates], best: winner, considered: this.candidates.length, pruned: this.pruned };  }  /** "hash(scan Order, seek Customer.id)": the plan on one line. */  static describe(plan: PlanNode): string {    if (plan.kind === "scan") return `scan ${plan.table}`;    if (plan.kind === "index-seek") return `seek ${plan.table}.${plan.attribute}`;    return `${plan.algorithm}(${QueryPlanner.describe(plan.outer)}, ${QueryPlanner.describe(plan.inner)})`;  }  /** The plan's operators in pre-order: a node before its outer, then its inner, subtree. */  static operators(plan: PlanNode): PlanNode[] {    if (plan.kind !== "join") return [plan];    return [plan, ...QueryPlanner.operators(plan.outer), ...QueryPlanner.operators(plan.inner)];  }  /** The table names a plan covers, in plan order. */  static tablesOf(plan: PlanNode): string[] {    return QueryPlanner.operators(plan).flatMap((node) => (node.kind === "join" ? [] : [node.table]));  }  /** Every non-empty subset of the tables in query order, smaller sets first. */  private static subsets(tables: readonly string[]): string[][] {    const out: string[][] = [];    for (let mask = 1; mask < 1 << tables.length; mask++) out.push(tables.filter((_, i) => (mask >> i) & 1));    for (let subsetBits = 1; subsetBits < 1 << tables.length; subsetBits++) out.push(tables.filter((_, i) => (subsetBits >> i) & 1));    return out.sort((a, b) => a.length - b.length);  }  private validate(query: Query): void {    if (query.tables.length < 1 || query.tables.length > MAX_QUERY_TABLES) throw new RangeError(`a query names 1 to ${MAX_QUERY_TABLES} tables`);    if (new Set(query.tables).size !== query.tables.length) throw new RangeError("a table appears twice");    for (const name of query.tables) if (!this.stats.has(name)) throw new RangeError(`no statistics for ${name}`);    const attribute = (table: string, name: string): void => {      if (!query.tables.includes(table)) throw new RangeError(`${table} is not in the query`);      if (!(name in this.stats.get(table)!.distinct)) throw new RangeError(`${table} has no attribute ${name}`);    };    for (const join of query.joins) {      attribute(join.left, join.leftAttribute);      attribute(join.right, join.rightAttribute);    }    for (const filter of query.filters) {      attribute(filter.table, filter.attribute);      if (filter.selectivity !== undefined && !(filter.selectivity > 0 && filter.selectivity <= 1)) throw new RangeError("selectivity lies in (0, 1]");    }  }  private selectivity(table: TableStats, filter: Predicate): number {    return filter.selectivity ?? 1 / Math.max(1, table.distinct[filter.attribute] ?? 1);  }  /** Rows of the table that pass all its filters, at least one. */  private filteredRows(table: TableStats, filters: readonly Predicate[]): number {    return Math.max(1, Math.ceil(filters.reduce((rows, filter) => rows * this.selectivity(table, filter), table.rows)));  }  private accessPath(plan: ScanNode | SeekNode): Candidate {    const candidate = this.register(plan, [plan.table]);    // ▸ one way to reach the table's rows is priced in page reads: every page for a scan, the tree's height plus a page per matching row for an index seek    this.tracer?.emit("access", { id: candidate.id, table: plan.table, kind: plan.kind, attribute: plan.kind === "index-seek" ? plan.attribute : null, rows: plan.rows, cost: plan.cost });    return candidate;  }  private register(plan: PlanNode, tables: readonly string[]): Candidate {    const candidate: Candidate = { id: this.candidates.length, plan, cost: plan.cost, rows: plan.rows, tables: [...tables] };    this.candidates.push(candidate);    return candidate;  }  /** The cheapest of the kept plan and the new ones over the same tables; every other is pruned. Ties keep the earlier. */  private keepCheapest(fresh: readonly Candidate[], kept: Candidate | null): Candidate {    let winner = kept ?? fresh[0]!;    for (const candidate of fresh) {      if (candidate === winner) continue;      if (candidate.cost < winner.cost) {        this.prune(winner, candidate);        winner = candidate;      } else {        this.prune(candidate, winner);      }    }    return winner;  }  private prune(loser: Candidate, winner: Candidate): void {    this.pruned++;    // ▸ a plan that costs more than the kept plan over the same tables is dropped: nothing built on top of it could ever win    this.tracer?.emit("prune", { id: loser.id, plan: QueryPlanner.describe(loser.plan), cost: loser.cost, keptId: winner.id, keptCost: winner.cost, tables: [...loser.tables] });  }  /** The join condition tying a table to the set, oriented with the set on the left; null when none does. */  private joining(query: Query, set: readonly string[], inner: string): JoinCondition | null {    for (const join of query.joins) {      if (set.includes(join.left) && join.right === inner) return join;      if (set.includes(join.right) && join.left === inner) return { left: join.right, leftAttribute: join.rightAttribute, right: join.left, rightAttribute: join.leftAttribute };    }    return null;  }  /** An index on the join attribute of a single table, which a nested loop can seek and a merge can read in order. */  private indexed(plan: PlanNode, attribute: string): boolean {    return plan.kind !== "join" && this.stats.get(plan.table)!.indexes.includes(attribute);  }  private join(algorithm: JoinStrategy, outer: PlanNode, inner: PlanNode, on: JoinCondition): JoinNode {    const outerTable = this.stats.get(on.left)!;    const innerTable = this.stats.get(on.right)!;    const distinct = Math.max(outerTable.distinct[on.leftAttribute] ?? 1, innerTable.distinct[on.rightAttribute] ?? 1, 1);    const rows = Math.max(1, Math.ceil((outer.rows * inner.rows) / distinct));    const sortCost = (plan: PlanNode, attribute: string): number => (this.indexed(plan, attribute) ? 0 : plan.rows * ceilLog2(plan.rows));    let cost: number;    if (algorithm === "nested-loop") {      const perProbe = this.indexed(inner, on.rightAttribute) ? ceilLog2(innerTable.rows) + Math.max(1, Math.ceil(innerTable.rows / distinct)) : inner.cost;      const probeCost = this.indexed(inner, on.rightAttribute) ? ceilLog2(innerTable.rows) + Math.max(1, Math.ceil(innerTable.rows / distinct)) : inner.cost;      cost = outer.cost + outer.rows * perProbe;      cost = outer.cost + outer.rows * probeCost;    } else if (algorithm === "hash") {      cost = outer.cost + inner.cost + outer.rows + inner.rows;    } else {      cost = outer.cost + inner.cost + sortCost(outer, on.leftAttribute) + sortCost(inner, on.rightAttribute);    }    return { kind: "join", algorithm, outer, inner, rows, cost };  }}

cost =: 30
rows =: 2

8 plans priced and 5 pruned without reading a row; the winner nested-loop(scan Customer, scan Order) costs 30 page reads for about 2 rows.

import type { Tracer } from "../trace";/** Tables one query may name; three keeps the search small enough to watch. */export const MAX_QUERY_TABLES = 3;export const JOIN_STRATEGIES = ["nested-loop", "hash", "merge"] as const;export type JoinStrategy = (typeof JOIN_STRATEGIES)[number];/** What the planner knows about a table: never the rows, only numbers about them. */export interface TableStats { name: string; rows: number; /** Disk pages the rows occupy; a scan reads every one. */ pages: number; /** Attributes with an index. */ indexes: readonly string[]; /** Distinct values per attribute, for selectivity; every attribute the query may name appears here. */ distinct: Readonly<Record<string, number>>;}/** An equality filter, `table.attribute = constant`. */export interface Predicate { table: string; attribute: string; /** The share of rows that pass; defaults to one over the attribute's distinct count. */ selectivity?: number;}export interface JoinCondition { left: string; leftAttribute: string; right: string; rightAttribute: string;}export interface Query { tables: readonly string[]; joins: readonly JoinCondition[]; filters: readonly Predicate[];}export interface ScanNode { kind: "scan"; table: string; rows: number; cost: number;}export interface SeekNode { kind: "index-seek"; table: string; attribute: string; rows: number; cost: number;}export interface JoinNode { kind: "join"; algorithm: JoinStrategy; outer: PlanNode; inner: PlanNode; rows: number; cost: number;}export type PlanNode = ScanNode | SeekNode | JoinNode;/** One plan the search priced: an access path for one table, or a join tree over several. */export interface Candidate { id: number; plan: PlanNode; cost: number; rows: number; tables: readonly string[];}export interface PlanReport { /** Every plan priced, in the order the search met them. */ candidates: readonly Candidate[]; best: Candidate; considered: number; pruned: number;}const ceilLog2 = (n: number): number => Math.max(1, Math.ceil(Math.log2(Math.max(2, n))));/** * SQL says which rows, never how to get them. A cost-based planner turns * a query into a plan by pricing the alternatives: the ways to reach each * table (a scan of every page, or a seek through an index when a filter * names an indexed attribute), then the ways to join the tables, in every * order and by every algorithm, each costed in page reads from the table * statistics alone. It never reads a row. The search is dynamic * programming over subsets of tables the way System R did it: the best * plan for a set of tables is built from the best plan for the set minus * one table, so a plan that loses to a cheaper one over the same tables * is pruned and never extended. Only left-deep trees are considered, * where the inner side of every join is a single table. * * The cost model, in page reads: a scan costs the table's pages; an index * seek costs the tree's height plus a page per row that qualifies; a * nested loop costs the outer plan plus, per outer row, either a seek * into an index on the inner table's join attribute or a rescan of the * inner plan; a hash join costs both inputs plus a pass over each; a merge * join costs both inputs plus a sort of each side that is not already an * index on its join attribute. Join cardinality is the product of the * inputs over the larger distinct count of the two join attributes. * * Time: O(2^n * n * algorithms) over n tables. Space: O(2^n) kept plans. */export class QueryPlanner { private readonly stats: ReadonlyMap<string, TableStats>; private candidates: Candidate[] = []; private pruned = 0; constructor( stats: readonly TableStats[], private readonly tracer?: Tracer, ) { for (const table of stats) { if (!Number.isInteger(table.rows) || table.rows < 1) throw new RangeError(`${table.name} needs at least one row`); if (!Number.isInteger(table.pages) || table.pages < 1) throw new RangeError(`${table.name} needs at least one page`); for (const attribute of table.indexes) if (!(attribute in table.distinct)) throw new RangeError(`${table.name} indexes unknown attribute ${attribute}`); } this.stats = new Map(stats.map((table) => [table.name, table])); } /** Prices every access path and every left-deep join tree, pruning as it goes, and returns the cheapest. */ plan(query: Query): PlanReport { this.validate(query); this.candidates = []; this.pruned = 0; const best = new Map<string, Candidate>(); for (const name of query.tables) { const table = this.stats.get(name)!; // ▸ the planner reads numbers about the table, never its rows: how many rows, how many pages, which attributes have an index this.tracer?.emit("stats", { table: name, rows: table.rows, pages: table.pages, indexes: [...table.indexes] }); const filters = query.filters.filter((filter) => filter.table === name); const paths: Candidate[] = [this.accessPath({ kind: "scan", table: name, rows: this.filteredRows(table, filters), cost: table.pages })]; for (const filter of filters) { if (!table.indexes.includes(filter.attribute)) continue; const rows = this.filteredRows(table, filters); paths.push(this.accessPath({ kind: "index-seek", table: name, attribute: filter.attribute, rows, cost: ceilLog2(table.rows) + Math.ceil(table.rows * this.selectivity(table, filter)) })); } best.set(name, this.keepCheapest(paths, best.get(name) ?? null)); } const subsets = QueryPlanner.subsets(query.tables).filter((set) => set.length >= 2); for (const set of subsets) { const key = set.join("+"); // The last-named table is tried as the inner side first, so the query's own order is the first plan priced. for (const inner of [...set].reverse()) { const rest = set.filter((name) => name !== inner); const outerTables = set.filter((name) => name !== inner); const outer = best.get(rest.join("+")); const outer = best.get(outerTables.join("+")); if (!outer) continue; const condition = this.joining(query, rest, inner); const condition = this.joining(query, outerTables, inner); if (!condition) continue; const innerPath = best.get(inner)!; for (const algorithm of JOIN_STRATEGIES) { const plan = this.join(algorithm, outer.plan, innerPath.plan, condition); const candidate = this.register(plan, set); // ▸ the kept plan for the smaller set joins one more table by one algorithm, and the cost model prices the result this.tracer?.emit("candidate", { id: candidate.id, tables: [...set], algorithm, outer: QueryPlanner.describe(outer.plan), inner: QueryPlanner.describe(innerPath.plan), rows: plan.rows, cost: plan.cost }); best.set(key, this.keepCheapest([candidate], best.get(key) ?? null)); } } } const winner = best.get(query.tables.join("+")); if (!winner) throw new RangeError("the query's tables are not all joined to one another"); // ▸ the kept plan for the whole set of tables is the plan that runs this.tracer?.emit("choose", { id: winner.id, cost: winner.cost, rows: winner.rows, plan: QueryPlanner.describe(winner.plan) }); return { candidates: [...this.candidates], best: winner, considered: this.candidates.length, pruned: this.pruned }; } /** "hash(scan Order, seek Customer.id)": the plan on one line. */ static describe(plan: PlanNode): string { if (plan.kind === "scan") return `scan ${plan.table}`; if (plan.kind === "index-seek") return `seek ${plan.table}.${plan.attribute}`; return `${plan.algorithm}(${QueryPlanner.describe(plan.outer)}, ${QueryPlanner.describe(plan.inner)})`; } /** The plan's operators in pre-order: a node before its outer, then its inner, subtree. */ static operators(plan: PlanNode): PlanNode[] { if (plan.kind !== "join") return [plan]; return [plan, ...QueryPlanner.operators(plan.outer), ...QueryPlanner.operators(plan.inner)]; } /** The table names a plan covers, in plan order. */ static tablesOf(plan: PlanNode): string[] { return QueryPlanner.operators(plan).flatMap((node) => (node.kind === "join" ? [] : [node.table])); } /** Every non-empty subset of the tables in query order, smaller sets first. */ private static subsets(tables: readonly string[]): string[][] { const out: string[][] = []; for (let mask = 1; mask < 1 << tables.length; mask++) out.push(tables.filter((_, i) => (mask >> i) & 1)); for (let subsetBits = 1; subsetBits < 1 << tables.length; subsetBits++) out.push(tables.filter((_, i) => (subsetBits >> i) & 1)); return out.sort((a, b) => a.length - b.length); } private validate(query: Query): void { if (query.tables.length < 1 || query.tables.length > MAX_QUERY_TABLES) throw new RangeError(`a query names 1 to ${MAX_QUERY_TABLES} tables`); if (new Set(query.tables).size !== query.tables.length) throw new RangeError("a table appears twice"); for (const name of query.tables) if (!this.stats.has(name)) throw new RangeError(`no statistics for ${name}`); const attribute = (table: string, name: string): void => { if (!query.tables.includes(table)) throw new RangeError(`${table} is not in the query`); if (!(name in this.stats.get(table)!.distinct)) throw new RangeError(`${table} has no attribute ${name}`); }; for (const join of query.joins) { attribute(join.left, join.leftAttribute); attribute(join.right, join.rightAttribute); } for (const filter of query.filters) { attribute(filter.table, filter.attribute); if (filter.selectivity !== undefined && !(filter.selectivity > 0 && filter.selectivity <= 1)) throw new RangeError("selectivity lies in (0, 1]"); } } private selectivity(table: TableStats, filter: Predicate): number { return filter.selectivity ?? 1 / Math.max(1, table.distinct[filter.attribute] ?? 1); } /** Rows of the table that pass all its filters, at least one. */ private filteredRows(table: TableStats, filters: readonly Predicate[]): number { return Math.max(1, Math.ceil(filters.reduce((rows, filter) => rows * this.selectivity(table, filter), table.rows))); } private accessPath(plan: ScanNode | SeekNode): Candidate { const candidate = this.register(plan, [plan.table]); // ▸ one way to reach the table's rows is priced in page reads: every page for a scan, the tree's height plus a page per matching row for an index seek this.tracer?.emit("access", { id: candidate.id, table: plan.table, kind: plan.kind, attribute: plan.kind === "index-seek" ? plan.attribute : null, rows: plan.rows, cost: plan.cost }); return candidate; } private register(plan: PlanNode, tables: readonly string[]): Candidate { const candidate: Candidate = { id: this.candidates.length, plan, cost: plan.cost, rows: plan.rows, tables: [...tables] }; this.candidates.push(candidate); return candidate; } /** The cheapest of the kept plan and the new ones over the same tables; every other is pruned. Ties keep the earlier. */ private keepCheapest(fresh: readonly Candidate[], kept: Candidate | null): Candidate { let winner = kept ?? fresh[0]!; for (const candidate of fresh) { if (candidate === winner) continue; if (candidate.cost < winner.cost) { this.prune(winner, candidate); winner = candidate; } else { this.prune(candidate, winner); } } return winner; } private prune(loser: Candidate, winner: Candidate): void { this.pruned++; // ▸ a plan that costs more than the kept plan over the same tables is dropped: nothing built on top of it could ever win this.tracer?.emit("prune", { id: loser.id, plan: QueryPlanner.describe(loser.plan), cost: loser.cost, keptId: winner.id, keptCost: winner.cost, tables: [...loser.tables] }); } /** The join condition tying a table to the set, oriented with the set on the left; null when none does. */ private joining(query: Query, set: readonly string[], inner: string): JoinCondition | null { for (const join of query.joins) { if (set.includes(join.left) && join.right === inner) return join; if (set.includes(join.right) && join.left === inner) return { left: join.right, leftAttribute: join.rightAttribute, right: join.left, rightAttribute: join.leftAttribute }; } return null; } /** An index on the join attribute of a single table, which a nested loop can seek and a merge can read in order. */ private indexed(plan: PlanNode, attribute: string): boolean { return plan.kind !== "join" && this.stats.get(plan.table)!.indexes.includes(attribute); } private join(algorithm: JoinStrategy, outer: PlanNode, inner: PlanNode, on: JoinCondition): JoinNode { const outerTable = this.stats.get(on.left)!; const innerTable = this.stats.get(on.right)!; const distinct = Math.max(outerTable.distinct[on.leftAttribute] ?? 1, innerTable.distinct[on.rightAttribute] ?? 1, 1); const rows = Math.max(1, Math.ceil((outer.rows * inner.rows) / distinct)); const sortCost = (plan: PlanNode, attribute: string): number => (this.indexed(plan, attribute) ? 0 : plan.rows * ceilLog2(plan.rows)); let cost: number; if (algorithm === "nested-loop") { const perProbe = this.indexed(inner, on.rightAttribute) ? ceilLog2(innerTable.rows) + Math.max(1, Math.ceil(innerTable.rows / distinct)) : inner.cost; const probeCost = this.indexed(inner, on.rightAttribute) ? ceilLog2(innerTable.rows) + Math.max(1, Math.ceil(innerTable.rows / distinct)) : inner.cost; cost = outer.cost + outer.rows * perProbe; cost = outer.cost + outer.rows * probeCost; } else if (algorithm === "hash") { cost = outer.cost + inner.cost + outer.rows + inner.rows; } else { cost = outer.cost + inner.cost + sortCost(outer, on.leftAttribute) + sortCost(inner, on.rightAttribute); } return { kind: "join", algorithm, outer, inner, rows, cost }; }}