AWS Builder Center

Teaching the Query Optimizer to Learn: Inside NEQO

Every SQL query run against a database — whether it's powering a dashboard on Amazon Redshift or a transaction on Amazon Aurora — triggers a decision that's almost entirely invisible to the person who wrote it:

Teaching the Query Optimizer to Learn: Inside NEQO Every SQL query run against a database — whether it's powering a dashboard on Amazon Redshift or a transaction on Amazon Aurora — triggers a decision that's almost entirely invisible to the person who wrote it: how should the database actually go about answering this? Scan the table, or use an index? Join these five tables in this order, or that one? For anything beyond a trivial query, the number of possible execution plans explodes into the millions, and the gap between the best plan and a bad one can be the difference between a query that returns in 50 milliseconds and one that takes 30 seconds. Choosing well is the job of the query optimizer, and for the better part of four decades it has worked essentially the same way: estimate the cost of each candidate plan from table and column statistics, then pick the cheapest one. The catch is that those estimates rest on an assumption that rarely holds in real databases — that columns are statistically independent of one another. Production data is correlated and skewed almost by definition, and the more complex the schema and the wider the join, the more that assumption costs you. A new research framework called NEQO (Neuro-Evolutionary Query Optimizer), developed by Suman Sourav Prasad at the Ajay Binay Institute of Technology, proposes a different approach. Instead of one hand-tuned cost formula, NEQO assembles a small team of learned models — each responsible for a different part of the optimization problem — wires them into a single pipeline, and lets the whole system keep improving from real query traffic after it's deployed. Where static heuristics run out of road Classical cost-based optimizers were built for an era of comparatively simple, stable schemas, and they tend to struggle in three specific, common situations: Correlated predicates. A query filtering on both city = 'Seattle' and state = 'WA' will be badly mis-estimated by an optimizer that assumes the two filters are independent. Skewed data. A small number of extremely popular values — a handful of customers responsible for most orders, say — throw off cardinality estimates built on an assumption of roughly uniform distribution. Wide, multi-way joins. As the number of joined tables grows, the space of possible join orders grows combinatorially, and exhaustively searching it becomes computationally infeasible well before 20 tables. Each of these is, on its own, a well-studied problem. NEQO's premise is that they need to be solved together, because join-order decisions, cardinality estimates, and index choices all feed into and depend on one another. Seven learned stages, one closed loop NEQO's architecture reads less like a single model and more like a small organization, with each stage handling a specific responsibility and passing its output downstream: Semantic query encoder (LLM). A fine-tuned large language model reads the raw SQL text and produces an embedding that captures the query's intent — implicit joins, awkward predicate patterns, correlated subqueries — rather than just its surface syntax. GNN schema encoder. The schema is represented as a graph: tables are nodes, foreign keys are edges, and — notably — pairs of predicates that tend to appear together in the historical workload become their own weighted edge type. A graph neural network turns this into an embedding that captures skew and correlation directly, instead of relying on flat, per-table histograms. DRL join-order agent. Choosing a join order is framed as a sequential decision problem and handed to a reinforcement-learning agent (trained with PPO), which builds a join tree one step at a time. Training uses curriculum learning: it starts on simple 5-table joins and only steps up to 10-, 20-, and eventually 40-table joins once the policy has stabilized at the current difficulty. Neural cardinality estimator. In place of brittle histograms, a tree-structured neural network estimates how many rows a candidate plan will produce, giving the join-order agent a signal to score its options at every step. Multi-agent LLM index advisor. Once a join order is fixed, a team of cooperating LLM agents — one to scope candidate columns, one to propose concrete indexes, one to merge and de-duplicate them, one to critique the set against storage and write costs, and one to cast a final vote — recommends a supporting index configuration without needing retraining for each new workload. Adaptive execution monitor. While the plan is running, a lightweight monitor compares real, observed row counts against what Stage 4 predicted. If they diverge past a threshold — a sign of skew the earlier stages missed — it triggers re-optimization of the remaining portion of the plan mid-flight, with no need to restart the query. Experience replay and continuous learning. Every executed query — the original SQL, the plan chosen, and the latency it actually achieved — is written to a replay buffer. That buffer periodically retrains the join-order agent and cardinality estimator, and fine-tunes the semantic encoder, so the pipeline keeps improving after deployment instead of staying frozen at whatever it learned offline. The evolutionary twist: explore, exploit, explain The piece tying NEQO back to Prasad's earlier work on genetic query optimization is a refinement layer that runs alongside the reinforcement-learning agent rather than replacing it. A genetic algorithm maintains its own population of candidate join orders, built through crossover and mutation, giving the system a source of exploratory diversity that a single RL policy — which tends to concentrate on the highest-value region it has already found — doesn't provide on its own. At the end of each optimization pass, NEQO compares the best genetically-evolved candidate against the best RL-proposed candidate under the learned cost model and commits to whichever is cheaper. The semantic encoder from Stage 1 is then asked to generate a short, natural-language explanation for why that plan was chosen — turning what would otherwise be a black-box decision into something a database administrator can actually read and audit. Why this could matter for AWS and other cloud databases Query optimization problems don't stay static in production the way they do in a benchmark. Cloud-managed databases in particular — the Amazon RDS, Aurora, and Redshift instances running behind thousands of different applications — see workloads and data distributions drift constantly as tenants, schemas, and traffic change. A cost model calibrated once at setup time is exactly the kind of static heuristic that degrades quietly over months, surfacing later as unexplained latency spikes. NEQO's continuous-learning loop is a direct response to that kind of drift, and it isn't an isolated idea. It follows a line of published research showing learned components can meaningfully outperform static optimizers on real systems — including Bao, a bandit-style optimizer built on top of PostgreSQL (the engine underneath both Aurora PostgreSQL and RDS for PostgreSQL) that steers query plans using per-query hints. NEQO's contribution is to combine several of these learned ideas — semantic understanding, schema-aware graph learning, reinforcement-learned join ordering, and zero-shot index advising — into one coordinated system instead of improving a single stage in isolation, while adding an explainability channel a DBA can actually use. What's proven, and what's still ahead It's worth being direct about where this project currently stands: NEQO is, right now, a complete architecture and evaluation protocol, not a set of benchmark results. The paper lays out the full formal problem model, the seven-stage pipeline, the unified algorithm, and — deliberately — a detailed evaluation plan against TPC-H and the Join Order Benchmark (IMDB), comparing NEQO against the native PostgreSQL optimizer, Prasad's earlier genetic-only optimizer, a Bao-style bandit optimizer, a DRL-only agent, and several ablations of NEQO itself, removing the LLM encoder, the GNN, or the genetic layer one at a time to see how much each contributes. The numerical results are intentionally left for a follow-up revision once that benchmarking campaign is complete. What's real today is the design: a carefully reasoned answer to how several genuinely different learning paradigms — sequence understanding, graph learning, combinatorial search, and reinforcement learning — could be made to cooperate on one of database systems' oldest hard problems. NEQO (Neuro-Evolutionary Query Optimizer) is a research framework proposed by Suman Sourav Prasad, Department of Computer Science and Engineering, Ajay Binay Institute of Technology. Benchmark results against TPC-H and the Join Order Benchmark are planned for a subsequent revision.
Any opinions in this article are those of the individual author and may not reflect the opinions of AWS.
Enjoyed reading this content? Let the author know!

Your likes, comments, shares, and saves help creators reach more builders.

Loading recommendations

Loading article