Rust SQL optimizer built in under 1000 lines using Egg e-graph framework

The project provides a working SQL optimizer in under 1000 lines of Rust by leveraging the Egg framework. Egg’s e-graph data structure allows the optimizer to represent and rewrite SQL expressions compactly, tracking equivalence classes without redundant storage. This approach contrasts with traditional tree-based optimizers that may duplicate subtrees during transformation. The implementation covers foundational techniques such as constant folding, predicate pushdown, and join reordering, making it a practical reference for engineers learning query optimization.

Egg’s equality saturation method enables the optimizer to explore multiple equivalent forms of a query before selecting the lowest-cost plan. The e-graph dynamically merges equivalent expressions, reducing the search space while preserving all possible rewrites. This is particularly useful for SQL, where expressions like `a * 2 / 2` can be simplified to `a` without losing correctness. The optimizer supports both rule-based and cost-based optimization, allowing it to apply heuristic rules and then refine plans using estimated costs.

The project defines SQL as an algebraic data type in Rust, using Egg’s `define_language` macro to model expressions, operators, and plan nodes. This design makes it extensible for custom SQL dialects or additional optimization rules. While the optimizer is minimal, it handles real TPC-H queries, demonstrating that core optimization logic can be implemented concisely. Engineers can use this as a sandbox to experiment with new rules or cost models without the overhead of a full database system.

The trade-off for this compactness is limited scalability. The e-graph, while efficient, may grow large for complex queries with many equivalent forms. The optimizer also lacks features like parallel plan generation or advanced statistics collection, which are common in production systems. However, its simplicity makes it a useful tool for education or prototyping, where clarity and modifiability are more important than raw performance.