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

Interactive EXPLAIN Plan Bottleneck Detector & Query Rewriter

A cost-based EXPLAIN ANALYZE plan tree analyzer that computes cardinality estimation Q-Error, flags external disk sorts and high-filter sequential scans, and rewrites non-sargable SQL predicates.

~40 min Advanced Lessons: Hands-On Build: Interactive EXPLAIN Plan Bottleneck Detector & Query Rewriter, Life of a SQL Query: Parser, Binder, Logical Plan, Cost Optimizer & Executor, Mastering EXPLAIN & EXPLAIN ANALYZE: Cost Units, Actual Rows, Loops & Buffers, Table Statistics (ANALYZE): Null Fraction, NDV, Most Common Values & Histograms, Selectivity Math, Independence Assumption Failures & Extended Statistics, Physical Scan Operators: Seq Scan, Index Scan, Index-Only & Bitmap Heap Scan
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 cost-based EXPLAIN ANALYZE plan tree analyzer that computes cardinality estimation Q-Error, flags external disk sorts and high-filter sequential scans, and rewrites non-sargable SQL predicates.

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 Interactive EXPLAIN Plan Bottleneck Detector & Query Rewriter from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Cardinality Estimation Q-Error Calculator

  • Core Database Concept: Measuring Multiplicative Optimizer Estimation Error: max(est/act, act/est)
  • Target Module: index.js (ExplainPlanAnalyzer.computeQError)
  • Engineering Specification: Implement computeQError(estimatedRows, actualRows) to compute the symmetric multiplicative Q-Error used in query optimizer research.
  • Implementation Hint: Clamp est and act to at least 1 to avoid division by zero, then return Math.max(e / a, a / e).
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Buffer Pool & Disk Page Cost Estimator

  • Core Database Concept: System R / PostgreSQL Weighted Page + Tuple CPU Cost Formula
  • Target Module: index.js (ExplainPlanAnalyzer.estimateScanCost)
  • Engineering Specification: Implement estimateScanCost({ seqPages, tuples, selectivity, seqPageCost, randomPageCost, cpuTupleCost }) to compute both seqCost and indexCost and choose the cheaper access path.
  • Implementation Hint: seqCost = seqPages * seqPageCost + tuples * cpuTupleCost; idxCost = randPages * randomPageCost + matchedTuples * cpuTupleCost.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: Recursive EXPLAIN ANALYZE Bottleneck Detector

  • Core Database Concept: Walking Plan Trees to Flag High-Filter Seq Scans, Disk Spills, and Severe Q-Error
  • Target Module: index.js (ExplainPlanAnalyzer.detectBottlenecks)
  • Engineering Specification: Implement detectBottlenecks(rootPlanNode) to recursively inspect a plan tree and return structured diagnostic findings.
  • Implementation Hint: Traverse node and node.Plans; flag Seq Scan with rowsRemoved > actualRows * 5, Sort Method: external merge, or Q-Error >= 10.
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Non-Sargable Predicate Rewriter

  • Core Database Concept: Transforming Function-Wrapped Columns into Index-Range Predicates
  • Target Module: index.js (ExplainPlanAnalyzer.rewriteSargable)
  • Engineering Specification: Implement rewriteSargable(predicateStr) to transform YEAR(col) = YYYY and col + k = v into sargable range/equality predicates.
  • Implementation Hint: Rewrite YEAR(col) = YYYY to col >= "YYYY-01-01" AND col < "(YYYY+1)-01-01".
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Query Optimizer & Execution Plans
  • Difficulty & Time Budget: Advanced (~40 minutes)
  • Key Architectural Highlights:
    • Cardinality estimation Q-Error = max(est/act, act/est) calculation across plan tree nodes
    • Automated bottleneck flagging for Seq Scans with high Rows Removed by Filter and external disk Sorts
    • Sargable SQL predicate rewriter transforming YEAR(col) = Y and arithmetic wrappers into indexable ranges
  • Core Primitives & Tags: EXPLAIN ANALYZE, Cardinality Estimation, Q-Error, Sargability, Cost Model

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.