Limit the greedy optimizer with a step count
Details
| Detail name | Value |
|---|---|
| Changelog Number | 26978 |
| Type | Bug |
| Status | Resolved |
| Affected Versions | Exasol 7.1.0, Exasol 8.0.0, Exasol 2025.1.0 |
| Fix Versions | Exasol 2025.2.0, Exasol 2025.1.9 |
| Resolution Date | 2025-12-17 |
Description
Finding the optimal join order is in general a NP-hard problem.
This means that there is no known polynomial algorithm that can solve the problem.
As a consequence, databases, including Exasol, need to use heuristics and algorithms that find a locally optimal join order for larger problems.
For larger problems in an execution pipeline (i.e., roughly above 10 involved tables), the new Exasol cost based optimizer switches from dynamic programming to a greedy algorithm.
In general, greedy algorithms provide a fast way to solve complex problems.
However, finding the optimal join order has side condition. The cost based optimizer needs to find a join order that is cheap and legal. Legal means that it provides the correct results and is executable by the Exasol engine.
Due to the second condition, the new join optimizer in Exasol has to use a greedy algorithm with backtracking.
Otherwise, the greedy algorithm might return illegal join orders.
It is possible that this backtracking takes an exponential amount of time.
Workaround
It can help to switch to the old optimizer:
/*join optimizer legacy*/SELECT ...;
If this does not work, the only alternative is to change the SQL of the query or the DDLs (e.g., materializing a view).
Fix
The greedy algorithm has a fixed step count limit for the backtracking. This avoids the exponential execution time.
Changed behavior
The greedy algorithm in the standard cost based optimizer has a step count limit now. In some rare circumstances it is possible that this leads to join orders that have a higher execution time.
