Skip to content

ADR-0072: SPARQL EXPLAIN with Cardinality Estimation

Status: Accepted (2026-05-02)

Context

Engineers working with Trails knowledge graphs need query analysis tools to understand SPARQL query performance — analogous to EXPLAIN ANALYZE in PostgreSQL. The existing trails kg explain (from ctx.kg.explain) provides structural analysis (pattern counts, complexity score, basic warnings), but lacks cardinality estimation, join analysis, and actionable optimization suggestions backed by actual store statistics.

Decision

Implement trails.sparql_explain as a dedicated query-plan analysis module that probes the store for real triple-pattern cardinalities via COUNT queries. The module provides:

  • Triple pattern cardinality estimation — runs SELECT (COUNT(*) …) for each BGP pattern to measure actual selectivity.
  • Join variable detection — identifies shared variables between patterns and estimates result-set sizes.
  • Cartesian product detection — flags unjoined pattern groups.
  • Optimization suggestions — actionable advice (add type constraints, use LIMIT, push FILTERs down, prefer OPTIONAL over UNION).
  • Formatted output — table-style display resembling psql EXPLAIN.

The CLI surface extends trails kg explain with --execute (include real execution time) and --verbose (per-pattern breakdown) flags, while remaining backward-compatible with the existing structural output.

Consequences

  • python/src/trails/sparql_explain.py — new module, no external deps.
  • python/src/trails/cli/kg.py — extended explain command with new flags.
  • Cardinality probes add N COUNT queries per analysis (one per triple pattern). Acceptable for interactive CLI use; not intended for hot-path production queries.