Many engineers have written a query that seemed to work, and then a few days later have a disturbing alert go off that their AWS or Snowflake spend was much higher this week than expected. SQL optimization is one of those problems that looks simple until you're in it, and there are a dozen angles to tackle the problem at and which one is correct depends on dozens more factors. You can throw the query at an LLM, ask it to rewrite, ship the result. But how do you know the optimized query actually does the same thing?
This talk explores why query optimization is a deceptively hard problem, not just computationally, but mathematically. Drawing on real examples from production systems, we'll look at what "optimal" actually means, what the real cost of suboptimal queries is, and why the naive solutions engineers may reach for first don't hold up under scrutiny.
We'll tackle the "but couldn't we just...?" questions head-on: why you can't sample a database and run both queries, why asking an LLM whether two queries are equivalent confuses confidence for correctness. LLMs learn language patterns, not algebraic ones, and are bad at query equivalence for the same reason they're bad at chess. We'll also examine what level of confidence each approach actually provides, and when that might be enough.
From there, we'll explore the rigorous alternatives: rules-based approaches like incremental view maintenance, the BAG algebra that underlies them (the math is more accessible than it sounds), and formal verification methods that can actually prove equivalence. We'll survey the current state of research and tooling in this space, including its real limitations.
The talk closes with a practical framework for identifying which technique fits which situation, because sometimes a heuristic is exactly right, and sometimes only a proof will do.