System and method for enhanced query optimizer search space ordering
In an optimizer within a Relational Database Management System improved ways in which a search space (the universe of possible join combinations) is generated and managed and improved ways in which the elements of a search space are evaluated so that among other things unpromising elements are efficiently dropped (pruned).
1. A computer-implemented method for selecting an execution plan for a database request, the method comprising:
processing aspects of the database request, including at least:
enumerating a portion of possible valid logical plans, based on at least a maximum search space size, yielding enumerated logical plans,
preserving, uncosted, a portion of the enumerated logical plans, yielding a candidate search space,
ordering entries in the candidate search space based on at least a dynamic scoring function, yielding a candidate search space order, and
generating a physical plan for a portion of the entries in the candidate search space, yielding generated physical plans, wherein:
the generating proceeds according to the candidate search space order and a dynamic budget function so as to drop unpromising entries, and
the dynamic budget function defines a desired partition pruning strategy, is dynamically updated during the generating, and is determined based on a difference between a current maximum number of logical plans to be costed and a number of logical plans that have already been costed divided by a difference between a total number of logical plans saved during the enumerating and a number of costed logical plans and a number of logical plans pruned without costing;
reviewing a subset of the generated physical plans to select the execution plan;
executing the database request based on the selected execution plan; and
returning a result of the executed database request.
2. The method of claim 1 , wherein the database request includes a Structured Query Language statement.
3. The method of claim 1 , wherein the dynamic scoring function evaluates a logical property of the enumerated logical plans.
4. The method of claim 1 , wherein the dynamic scoring function evaluates a characteristic of one or more join predicates.
5. The method of claim 1 , wherein the dynamic scoring function evaluates a size of one or more database objects.
6. The method of claim 5 , wherein the one or more database objects include at least one database table.
7. The method of claim 1 , wherein the processing step and the reviewing step reside within a join enumeration algorithm that at least enumerates a plurality of logical plans and generates a plurality physical plans.
8. A non-transitory computer readable medium having instructions stored thereon that when executed by a processor, cause the processor to perform operations for selecting an execution plan for a database request, the operations comprising:
processing aspects of the database request, including at least:
enumerating a portion of possible valid logical plans, based on at least a maximum search space size, yielding enumerated logical plans,
preserving, uncosted, a portion of the enumerated logical plans, yielding a candidate search space,
ordering entries in the candidate search space based on at least a dynamic scoring function, yielding a candidate search space order, and
generating a physical plan for a portion of the entries in the candidate search space, yielding generated physical plans, wherein:
the generating proceeds according to the candidate search space order and a dynamic budget function so as to drop unpromising entries, and
the dynamic budget function defines a desired partition pruning strategy, is dynamically updated during the generating, and is determined based on a difference between a current maximum number of logical plans to be costed and a number of logical plans that have already been costed divided by a difference between a total number of logical plans saved during the enumerating and a number of costed logical plans and a number of logical plans pruned without costing;
reviewing a subset of the generated physical plans to select the execution plan;
executing the database request based on the selected execution plan; and
returning a result of the executed database request.
9. The non-transitory computer readable medium of claim 8 , wherein the database request includes a Structured Query Language statement.
10. The non-transitory computer readable medium of claim 8 , wherein the dynamic scoring function evaluates a logical property of the enumerated logical plans.
11. The non-transitory computer readable medium of claim 8 , wherein the dynamic scoring function evaluates a characteristic of one or more join predicates.
12. non-transitory computer readable medium of claim 8 , wherein the dynamic scoring function evaluates a size of one or more database objects.
13. The non-transitory computer readable medium of claim 12 , wherein the one or more database objects include at least one database table.
14. The non-transitory computer readable medium of claim 8 , wherein the processing step and the reviewing step reside within a join enumeration algorithm that at least enumerates a plurality of logical plans and generates a plurality physical plans.
15. A system comprising:
one or more processors;
one or more computer readable media; and
computer readable instructions stored on the one or more computer readable media that when executed by the one or more processors, cause the one or more processors to perform operations for selecting an execution plan for a database request by:
processing aspects of the database request, including at least:
enumerating a portion of possible valid logical plans, based on at least a maximum search space size, yielding enumerated logical plans,
preserving, uncosted, a portion of the enumerated logical plans, yielding a candidate search space,
ordering entries in the candidate search space based on at least a dynamic scoring function, yielding a candidate search space order,
generating a physical plan for a portion of the entries in the candidate search space, yielding generated physical plans, wherein:
the generating proceeds according to the candidate search space order and a dynamic budget function so as to drop unpromising entries, and
the dynamic budget function defines a desired partition pruning strategy, is dynamically updated during the generating, and is determined based on a difference between a current maximum number of logical plans to be costed and a number of logical plans that have already been costed divided by a difference between a total number of logical plans saved during the enumerating and a number of costed logical plans and a number of logical plans pruned without costing,
reviewing a subset of the generated physical plans to select the execution plan,
executing the database request based on the selected execution plan, and
returning a result of the executed database request.
16. The system of claim 15 , wherein the database request includes a Structured Query Language statement.
17. The system of claim 15 , wherein the dynamic scoring function evaluates a logical property of the enumerated logical plans.
18. The system of claim 15 , wherein the dynamic scoring function evaluates a characteristic of one or more join predicates.
19. The system of claim 15 , wherein the dynamic scoring function evaluates a size of one or more database objects.
20. The system of claim 19 , wherein the one or more database objects include a database table.
21. The system of claim 15 , wherein the processing step and the reviewing step reside within a join enumeration algorithm that at least enumerates a plurality of logical plans and generates a plurality physical plans.
22. A system comprising:
one or more processors;
a memory coupled to at least one of the one or more processors; and
a query optimizer residing in the memory that, when executed by at least one of the one or more processors:
enumerates, for a database request, a portion of possible valid logical plans, based on at least a maximum search space size, yielding enumerated logical plans;
preserves, uncosted, a portion of the enumerated logical plans, yielding a candidate search space;
orders entries in the candidate search space based on at least a dynamic scoring function, yielding a candidate search space order;
generates a physical plan for a portion of the entries in the candidate search space, yielding generated physical plans, wherein:
the generating proceeds according to the candidate search space order and a dynamic budget function so as to drop unpromising entries, and
the dynamic budget function defines a desired partition pruning strategy, is dynamically updated during the generating, and is determined based on a difference between a current maximum number of logical plans to be costed and a number of logical plans that have already been costed divided by a difference between a total number of logical plans saved during the enumerating and a number of costed logical plans and a number of logical plans pruned without costing; and
reviews a subset of the generated physical plans to select an execution plan,
wherein the at least one of the one or more processors:
executes the database request based on the selected execution plan; and
returns a result of the executed database request.