Highly adaptable query optimizer search space generation process

1. A method for optimizing a search for a query, comprising:

providing a subplan for an optimization block in the query;

determining a maximum estimated cost for executing an access plan for the subplan using an inexpensive algorithm from a pool of search space generation algorithms;

when the maximum estimated cost is greater than a threshold cost for generating the access plan for the subplan,

analyzing algebraic properties of a hypergraph to determine complexity of the subplan for the optimization block;

identifying characteristics of each algorithm from the pool of search space generation algorithms, wherein each algorithm is configured to generate an associated access plan for the subplan; and

selecting an algorithm from the pool of search space generation algorithms based on the complexity of the subplan and characteristics of each algorithm; and

when the maximum estimated cost is less than the threshold cost for generating the access plan for executing the subplan, selecting the inexpensive algorithm; and

generating the access plan for the subplan using the selected algorithm to optimize the search for the query.

2. The method of claim 1 , further comprising:

determining a current state of a server configured to generate the optimized access plan; and

wherein selecting the algorithm further comprises selecting based on the current state of the server.

3. The method of claim 1 , wherein at least one algorithm from the pool of search space generation algorithms guarantees to generate the access plan for optimizing the subplan.

4. A system for optimizing a search for a query, comprising:

a memory;

a processor communicatively coupled to the memory;

a pre-optimization module stored in the memory and executing on the processor and further configured to:

provide a subplan for an optimization block in the query;

determine a maximum estimated cost for an access plan for executing the subplan using an inexpensive algorithm from a pool of search space generation algorithms;

when the maximum estimated cost is greater than a threshold cost for generating the access plan for the subplan,

analyze algebraic properties of a hypergraph to determine complexity of the subplan for the optimization block;

identify characteristics of each algorithm from the pool of search space generation algorithms, wherein each algorithm is configured to generate an associated access plan for the subplan; and

select an algorithm from the pool of search space generation algorithms based on the complexity of the subplan and characteristics of each algorithm; and

when the maximum estimated cost is less than the threshold cost for generating the access plan to execute the subplan, selecting the inexpensive algorithm; and

an optimization module configured to:

generate the access plan for the subplan using the selected algorithm to optimize the search for the query.

5. The system of claim 4 , wherein the pre-optimization module is further configured to determine a state of a server configured to generate the access plan and the optimization module is further configured to select the least expensive algorithm for generating the access plan based on the state of the server.

6. An article of manufacture including a non-transitory computer-readable medium having instructions stored thereon that, when executed by a computing device, cause said computing device to perform operations comprising:

providing a subplan for an optimization block in the query;

determining a maximum estimated cost for executing the subplan using an inexpensive algorithm from a pool of search space generation algorithms;

when the maximum estimated cost is greater than a threshold cost for generating the access plan for the subplan,

analyzing algebraic properties of a hypergraph to determine complexity of the subplan for the optimization block;

identifying characteristics of each algorithm from the pool of search space generation algorithms, wherein each algorithm is configured to generate an associated access plan for the subplan; and

selecting an algorithm from the pool of search space generation algorithms based on the complexity of the subplan and characteristics of each algorithm; and

when the maximum estimated cost is less than the threshold cost for generating the access plan for the subplan, selecting the inexpensive algorithm; and

generating the access plan for the subplan using the selected algorithm to optimize the search for the query.

7. The article of manufacture of claim 6 , wherein the operations further comprise:

determining a current state of a server configured to generate the access plan; and

wherein selecting the algorithm comprises selecting based on the current state of the server.

8. The article of manufacture of claim 6 , wherein at least one algorithm from the pool of algorithms guarantees to generate the access plan for optimizing the subplan.

9. The method of claim 1 , wherein the optimization block represents an atomic portion of the query.

10. The method of claim 1 , wherein the inexpensive algorithm is a backtracking algorithm without memoization over a left deep tree access plans.

11. The method of claim 1 , wherein the pool of search space generation algorithms includes at least one of a backtracking algorithm without memoization over left deep tree access plans, a backtracking algorithm with memoization over left deep tree access plans, and a dynamic programming algorithm over the bushy tree access plans.

12. The system of claim 4 , wherein the optimization block represents an atomic portion of the query.

13. The system of claim 4 , wherein the inexpensive algorithm is a backtracking algorithm without memoization over a left deep tree access plans.

14. The system of claim 4 , wherein the pool of search space generation algorithms includes at least one of a backtracking algorithm without memoization over left deep tree access plans, a backtracking algorithm with memoization over left deep tree access plans, and a dynamic programming algorithm over the bushy tree access plans.

15. The article of manufacture of claim 1 , wherein the optimization block represents an atomic portion of the query.

16. The article of manufacture of claim 1 , wherein the inexpensive algorithm is a backtracking algorithm without memoization over a left deep tree access plans.

17. The article of manufacture of claim 1 , wherein the pool of search space generation algorithms includes at least one of a backtracking algorithm without memoization over left deep tree access plans, a backtracking algorithm with memoization over left deep tree access plans, and a dynamic programming algorithm over the bushy tree access plans.