Selectivity-based optimized-query-plan caching
First Claim
1. An optimized-query-plan caching subsystem within a query-processing computer system, the optimized-query-plan caching subsystem comprising:
- an optimized-query-plan cache contained in electronic memory of a computer system or distributed across one or more electronic memories and mass-storage devices within a computer system; and
a caching component that executes within the query-processing computer system and that stores optimized query plans in the optimized-query-plan cache in association with a representation of an equivalence group and in association with a representation of an equivalence class contained within the equivalence group, and that retrieves optimized query plans from the optimized-query-plan cache by;
receiving a query plan and a predicate selectivity computed for the query plan;
determining whether an equivalence group for the query plan is stored in the optimized-query-plan cache;
when an equivalence group for the query plan is stored in the optimized-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity computed for the query plan; and
when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the equivalence class that has been identified,wherein an equivalence class corresponds to the received predicate selectivity when;
the received predicate selectivity is equal to a single predicate selectivity that defines the equivalence class;
the received predicate selectivity is greater than or equal to a low predicate selectivity and less than or equal to a high predicate selectivity that together define the equivalence class;
the received predicate selectivity is within a threshold distance of a single predicate selectivity that defines the equivalence class;
orthe received predicate selectivity is within a threshold distance of a low predicate selectivity or a high predicate selectivity that together define the equivalence class.
2 Assignments
0 Petitions
Accused Products
Abstract
Optimized query plans are partitioned into equivalence groups that each include equivalence classes. Each equivalence group corresponds to a particular compiled, normalized, and parameterized query plan prior to optimization. Each equivalence class within an equivalence group corresponds to a different query plan corresponding to the particular compiled, normalized, and parameterized query plan represented by the equivalence group that has been optimized with respect to the selectivity of one or more predicate clauses of the query that is compiled to produce the particular compiled, normalized, and parameterized query plan. Optimized query plans are cached according to their respective equivalence groups and equivalence classes. When a query, similar to a query already compiled, optimized, and cached, is subsequently received and compiled, a selectivity for a predicate of the compiled query is computed, allowing the database management system to retrieve a cached query plan optimized for a similar query with similar selectivity.
33 Citations
16 Claims
-
1. An optimized-query-plan caching subsystem within a query-processing computer system, the optimized-query-plan caching subsystem comprising:
-
an optimized-query-plan cache contained in electronic memory of a computer system or distributed across one or more electronic memories and mass-storage devices within a computer system; and a caching component that executes within the query-processing computer system and that stores optimized query plans in the optimized-query-plan cache in association with a representation of an equivalence group and in association with a representation of an equivalence class contained within the equivalence group, and that retrieves optimized query plans from the optimized-query-plan cache by; receiving a query plan and a predicate selectivity computed for the query plan; determining whether an equivalence group for the query plan is stored in the optimized-query-plan cache; when an equivalence group for the query plan is stored in the optimized-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity computed for the query plan; and when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the equivalence class that has been identified, wherein an equivalence class corresponds to the received predicate selectivity when; the received predicate selectivity is equal to a single predicate selectivity that defines the equivalence class; the received predicate selectivity is greater than or equal to a low predicate selectivity and less than or equal to a high predicate selectivity that together define the equivalence class; the received predicate selectivity is within a threshold distance of a single predicate selectivity that defines the equivalence class;
orthe received predicate selectivity is within a threshold distance of a low predicate selectivity or a high predicate selectivity that together define the equivalence class. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for optimized-query-plan caching carried out within a query-processing computer system that includes an optimized-query-plan cache contained in electronic memory of the computer system or distributed across one or more electronic memories and mass-storage devices within the computer system, the optimized-query-plan caching method comprising:
-
storing, by a caching component that executes within the query-processing computer system, optimized query plans in the optimized-query-plan cache in association with a representation of an equivalence group and in association with a representation of an equivalence class contained within the equivalence group, by, for an optimized query plan; receiving the optimized query plan and a predicate selectivity computed for the optimized query plan; determining whether an equivalence group for the optimized query plan is stored in the optimized-query-plan cache; when an equivalence group for the optimized query plan is not stored in the optimized-query-plan cache, creating an equivalence group for the optimized query plan, creating a first equivalence class for the optimized query plan defined by the predicate selectivity computed for the optimized query plan, and storing the optimized query plan in the first equivalence class; when an equivalence group for the optimized query plan is stored in the optimized-query-plan cache, traversing equivalence-class representations of equivalence classes contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity, and when an equivalence class that corresponds to the received predicate selectivity is not identified, adding a new equivalence class to the equivalence group and storing the optimized query plan in the new equivalence class; and retrieving, by the caching component, optimized query plans from the optimized-query-plan cache, wherein an equivalence class corresponds to the received predicate selectivity when; the received predicate selectivity is equal to a single predicate selectivity that defines the equivalence class; the received predicate selectivity is greater than or equal to a low predicate selectivity and less than or equal to a high predicate selectivity that together define the equivalence class; the received predicate selectivity is within a threshold distance of a single predicate selectivity that defines the equivalence class;
orthe received predicate selectivity is within a threshold distance of a low predicate selectivity or a high predicate selectivity that together define the equivalence class. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A query-processing computer system comprising:
-
a query-receiving component that receives queries for processing; a query-compiler component that generates a query plan for each received query; a query-optimizer component that, when a suitable optimized cached query plan is available for a query plan, retrieves the optimized cached query plan for execution and otherwise optimizes the query plan; a query-plan execution component that executes optimized query plans; an optimized-query-plan cache contained in electronic memory or distributed across one or more electronic memories and mass-storage devices within the query-processing computer system; and a caching component that executes within the query-processing computer system and that stores optimized query plans in the optimized-query-plan cache in association with a representation of an equivalence group and in association with a representation of an equivalence class contained within the equivalence group, and that retrieves optimized query plans from the optimized-query-plan cache by; receiving a query plan and a predicate selectivity computed for the query plan; determining whether an equivalence group for the query plan is stored in the optimized-query-plan cache; when an equivalence group for the query plan is stored in the optimized-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity computed for the query plan; and when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the equivalence class that has been identified, wherein an equivalence class corresponds to the received predicate selectivity when; the received predicate selectivity is equal to a single predicate selectivity that defines the equivalence class; the received predicate selectivity is greater than or equal to a low predicate selectivity and less than or equal to a high predicate selectivity that together define the equivalence class; the received predicate selectivity is within a threshold distance of a single predicate selectivity that defines the equivalence class;
orthe received predicate selectivity is within a threshold distance of a low predicate selectivity or a high predicate selectivity that together define the equivalence class. - View Dependent Claims (14, 15, 16)
-
Specification