Plan caching using density-based clustering

• US 8,996,504 B2
• Filed: 05/24/2012
• Issued: 03/31/2015
• Est. Priority Date: 05/24/2012
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Dehaan, David E., Bowman, Ivan T., Alu, Gne
• Primary Examiner(s): Jami, Hares
• Application Number:
  US13/479,342
• Publication Number:
  US 20130318069A1
• Time in Patent Office: 1,041 Days
• Field of Search: 707/713, 707/718, 707/719, 707/720, 707/721, 707/999.3
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A query plan predictor receives a query instance according to a query template having a set of parameters. The query plan predictor determines a plan space point for the query instance which is based upon the set of parameters. The query plan predictor predicts a predicted query plan for the plan space point, which is selected from a map of query plans according to a confidence threshold from a plan cache that includes at least one histogram. Each histogram is representative of a cached query plan in the plan cache combined with a previously-selected locality-sensitive hashing function. The histogram stores a frequency distribution of a mapping of sample plan points for the cached query plan by the locality-sensitive hashing function.

Claims

1. A method comprising:

receiving, by at least one processing device, a query instance according to a query template having a set of parameters;

determining, by the at least one processing device, a plan space point for the query instance, the plan space point based upon the set of parameters; and

predicting, by the at least one processing device, a predicted query plan for the plan space point based upon precision, the precision being a ratio of a number of correct predictions to a number of NULL-free predictions, the predicted query plan selected from a map of query plans according to a confidence threshold from a plan cache that includes at least one histogram, each histogram representative of a cached query plan in the plan cache combined with a previously-selected locality-sensitive hashing function, the histogram storing a frequency distribution of a mapping of sample plan points for the cached query plan by the locality-sensitive hashing function.

2. The method of claim 1, further comprising:

adding the plan space point to the frequency distribution of the sample plan points.

3. The method of claim 2, further comprising:

executing the query instance using the predicted query plan and receiving query results.

4. The method of claim 1, further comprising:

predicting the predicted query plan by selecting a query plan with a highest density of the sample plan points within a specified radius of the plan space point.

5. The method of claim 4, further comprising:

executing a confidence sanity check and determining if the predicted query plan has a density significantly greater than a particular threshold within a particular region in the plan space.

6. The method of claim 5, further comprising:

detecting changes in the plan space as a result of fluctuations in one of workload, data characteristics and system state, and optimizing the sample plan points.

7. The method of claim 1, further comprising:

predicting the predicted query plan based upon precision and recall, the recall being a ratio of the number of correct predictions to a total number of predictions.

8. The method of claim 3, further comprising:

evaluating the query results and optimizing the predicted query plan when a prediction error occurs; and

removing the plan space point and inserting an optimized plan space point into the frequency distribution of sample plan points.

19. The method of claim 2, the adding further comprising:

adding the plan space point to a workload history, the plan space point including the predicted query plan and a cost of execution.

9. A system comprising:

at least one processing device configured to process;

a query plan predictor configured to;

receive a query instance according to a query template having a set of parameters;

determine a plan space point for the query instance, the plan space point based upon the set of parameters; and

predict a predicted query plan for the plan space point based upon precision, the precision being a ratio of a number of correct predictions to a number of NULL-free predictions, the predicted query plan selected from a map of query plans according to a confidence threshold from a plan cache that includes at least one histogram, each histogram representative of a cached query plan in the plan cache combined with a previously-selected locality-sensitive hashing function, the histogram storing a frequency distribution of a mapping of sample plan points for the cached query plan by the locality-sensitive hashing function.

10. The system of claim 9, wherein the query plan predictor is further configured to:

add the plan space point to the frequency distribution of the sample plan points.

11. The system of claim 10, wherein the system further comprises:

a query executor configured to execute the query instance using the predicted query plan and receive query results.

12. The system of claim 9, wherein the query plan predictor is further configured to:

predict the predicted query plan by selecting a query plan with a highest density of the sample points within a specified radius of the plan space point.

13. The system of claim 12, wherein the query plan predictor is further configured to:

execute a confidence sanity check and determine if the predicted query plan has a density significantly greater than a particular threshold within a particular region in the plan space.

14. The system of claim 13, wherein the query plan predictor is further configured to:

detect changes in the plan space as a result of fluctuations in one of workload, data characteristics and system state, and optimize the sample plan points.

15. The system of claim 9, wherein the query plan predictor is further configured to:

predict the predicted query plan based upon precision and recall, the recall being a ratio of the number of correct predictions to a total number of predictions.

16. The system of claim 11, wherein the query plan predictor is further configured to:

evaluate the query results and optimize the predicted query plan when a prediction error occurs; and

remove the plan space point and insert an optimized plan space point into the frequency distribution of sample plan points.

20. The system of claim 10, wherein the query plan predictor is further configured to:

add the plan space point to a workload history, the plan space point including the predicted query plan and a cost of execution.

17. A non-transitory computer-readable medium having instructions stored thereon, the instructions causing at least one computing device to perform operations, the operations comprising:

receiving a query instance according to a query template having a set of parameters;

determining a plan space point for the query instance, the plan space point based upon the set of parameters; and

predicting a predicted query plan for the plan space point based upon precision, the precision being a ratio of a number of correct predictions to a number of NULL-free predictions, the predicted query plan selected from a map of query plans according to a confidence threshold from a plan cache that includes at least one histogram, each histogram representative of a cached query plan in the plan cache combined with a previously-selected locality-sensitive hashing function, the histogram storing a frequency distribution of a mapping of sample plan points for the cached query plan by the locality-sensitive hashing function.

18. The non-transitory computer-readable medium of claim 17, the operations further comprising:

adding the plan space point to the frequency distribution of sample plan points; and

executing the query instance using the predicted query plan and receiving query results.