mirror of
https://github.com/tursodatabase/limbo.git
synced 2025-12-23 08:21:09 +00:00
faa1197e58
Problem: The existing DP-based join optimizer has O(2^n) complexity, which causes large joins to basically not get past the planning phase. Fix: Add a greedy algorithm that runs in O(n²) time for >12 tables. Details: - Add compute_greedy_join_order() with hub score heuristic for selecting the starting table. Tables referenced by many other tables' constraints are preferred, enabling index lookups on subsequent joins. This is especially good for star schema queries. - Add GREEDY_JOIN_THRESHOLD constant (12) for switchover point - Add fuzz tests covering star schemas, chains, cliques up to 62 tables, and LEFT JOIN ordering invariants (RHS of a left join cannot be reordered). - Not all the tests necessarily assert that a query results in a good plan (apart from star schemas), but all tests do assert that we are _able_ to construct a plan (unlike before, where even 32-way joins would grind to a halt). AI usage: - Pretty much all of this was a conversation between me and Opus 4.5. I asked it to search the internet for practical solutions to the problem and it suggested a simple greedy search as a low-complexity solution and I thought it was a good idea for now. |
||
|---|---|---|
| .. | ||
| grammar_generator.rs | ||
| mod.rs | ||
| rowid_alias.rs | ||
| test_join_optimizer.rs | ||