A query optimizer can join the same tables in many orders. Although every order produces the same logical result, large intermediate results make some plans much more expensive than others.
Design a JoinOrderOptimizer class:
JoinOrderOptimizer() creates a stateless optimizer.int minimumCost(int[] sizes, int divisor) returns the minimum cost over every left-deep join order.
A left-deep order begins with one table and joins one remaining table at a time. If the current intermediate contains A rows and the next table contains B rows, the join produces floor((A * B) / divisor) rows. The cost of an order is the sum of every intermediate cardinality produced by a join. The starting table alone contributes no cost.
Each array position represents one table. Tables with equal sizes are still separate tables and must each be used once.
Example 1:
Input:
Output:
Explanation: Start with the size-10 table and join size 100 to produce 10 * 100 / 10 = 100 rows. Joining size 1000 then produces 100 * 1000 / 10 = 10000 rows. The total cost is 100 + 10000 = 10100, the minimum among all orders.
Example 2:
Input:
Output:
Explanation: Joining sizes 1 and 1000 first produces 10 rows. Joining the remaining size-1000 table produces 100 rows, for a total cost of 110.
Constraints
1 <= sizes.length <= 81 <= sizes[i] <= 10^61 <= divisor <= 10^6- Every intermediate multiplication fits in a signed 64-bit integer.
- The minimum total cost fits in a signed 32-bit integer.
- At most
50 calls are made to minimumCost.
Optimize a Left-Deep Join Orderhard