Originally published on tamiz.pro.
Modern databases rely on cost-based optimizers (CBOs) to pick the fastest way to execute a SQL query. These optimizers estimate the number of rows flowing through each operator of a query plan — a step called cardinality estimation. Historically, CBOs used histograms, sampling, and heuristics. Now, machine learning is rewriting those rules.
A recent research effort demonstrated that replacing a hand-tuned cardinality estimator with a small, trained model led to an 81% reduction in execution time on a benchmark of real-world queries. The secret? It wasn’t a giant transformer or a cluster of GPUs — it was a lightweight model trained on a fraction of the data.
Why Cardianlity Estimation Matters
Every SQL query can be executed in multiple ways. Consider a simple join:
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id WHERE c.region = 'EU';
The optimizer must decide:
- Whether to scan
ordersfirst orcustomers. - Which join algorithm to use (nested loop, hash, or merge).
- Whether to apply the region filter before or after the join.
Each decision depends on estimates of how many rows match 'EU', how many orders exist per customer, and so on. If the estimator predicts 100 rows but the truth is 10,000, the optimizer may pick a nested-loop join that takes minutes instead of a hash join that finishes in milliseconds.
The Traditional Approach
Legacy estimators use:
- Histograms: Bucketed counts of column values.
- Sampling: Running the query on a subset of data.
- Heuristics: Rules-of-thumb like “assume 10% selectivity for unknown conditions.”
These techniques degrade on complex predicates, correlated columns, and multi-table joins. For example, WHERE year = 2023 AND status = 'active' may have a very different selectivity than the product of individual probabilities.
How Small Models Win
Researchers trained a model on a dataset of:
- Query templates (e.g., “join two tables with a filter on column X”).
- True cardinalities from past executions.
- Features derived from the query structure and schema.
The model was a simple neural network — just a few layers and parameters. After training, it predicted cardinalities within 5% of the true value on held-out queries, compared to 50% errors from the legacy estimator.
Crucially, the model was small. It fit in memory, ran in microseconds, and required no retraining for new schemas. The 81% speedup came from better plans, not more compute.
Real-World Impact
This approach has moved beyond the lab:
- Google integrated learned cardinality into its F1 query engine, reducing tail latency.
-
Microsoft open-sourced
CardNet, a small model for SQL Server workloads. - Startups like Synthesis use similar techniques to offer “self-tuning” databases as a service.
Challenges and Ceilings
Despite the gains, learned models introduce new trade-offs:
| Aspect | Traditional | Learned |
|---|---|---|
| Training data | None | Requires labeled queries |
| Cold start | Works on day one | Needs warm-up period |
| Interpretability | Deterministic rules | Black-box predictions |
| Update frequency | Manual tuning | Periodic retraining |
For production systems, a hybrid approach often works best: use learned estimates when available, fall back to heuristics otherwise.
Conclusion
The 81% query plan jump shows that small, well-trained models can outperform decades-old optimization rules. But the real win is not replacing databases — it’s augmenting them with models that learn from data, adapt to workloads, and stay lightweight enough to deploy anywhere.
Frequently Asked Questions
Q: Do I need to retrain the model for every new table?
A: Not necessarily. Many systems generalize across schemas using transfer learning or schema-aware embeddings.
Q: Is this approach safe for production?
A: Yes, with fallbacks. Systems like Google’s F1 run both estimators in parallel and choose the safer option if confidence is low.
Q: Where can I try this myself?
A: Check out ottertune or Microsoft’s CardNet for open-source implementations.
Top comments (0)