Generating estimates for query optimization

• US 9,110,949 B2
• Filed: 02/11/2013
• Issued: 08/18/2015
• Est. Priority Date: 02/11/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Milenova, Boriana Lubomirova, Campos, Marcos M
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US13/764,621
• Publication Number:
  US 20140229464A1
• Time in Patent Office: 918 Days
• Field of Search: 707/718
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Processes, machines, and stored machine instructions are provided for estimating how many rows would be processed by a query. In one embodiment, model aggregating logic may generate a global model based on separate models for separate portions of a set of data. For example, the separate portions may be assigned to separate partitions of the set of data based at least in part on key values in the separate portions. Generating the global model may include generating an uncompressed model that includes components of the separate models before generating a compressed model to estimate the uncompressed model. Query analysis logic may use the global model to estimate how many rows would be processed by queries that, when executed, would access portion(s) of the set of data.

Claims

1. A method comprising:

estimating a number of rows that would be processed by each of one or more execution plans for a query based at least in part on a particular density model that approximates a weighted combination of at least a first density model for a first portion of a set of data and a second density model for a second portion of the set of data;

based at least in part on the number of rows estimated for said each of one or more execution plans for the query, selecting an execution plan for the query;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the first portion is assigned to a first partition of the set of data based at least in part on one or more first key values in the first portion, and wherein the second portion is assigned to a second partition of the set of data based at least in part on one or more second key values in the second portion.

3. The method of claim 1, further comprising determining that the query, if executed, would access one or more rows from both the first portion and the second portion.

4. The method of claim 1, wherein the query is a first query, wherein the number of rows is a first number of rows estimated for said each of one or more execution plans for the first query, and wherein the selected execution plan is a first execution plan, further comprising:

determining that a second query, if executed, would access one or more rows from the first portion but not the second portion;

estimating a second number of rows that would be processed by each of one or more execution plans for the second query based at least in part on the first density model but not the second density model;

based at least in part on the second number of rows estimated for said each of one or more execution plans for the second query, selecting a second execution plan for the second query.

5. The method of claim 1, further comprising generating the particular density model by approximating the weighted combination of at least the first density model and the second density model.

6. The method of claim 1, further comprising storing the particular density model in association with the set of data, wherein the particular density model specifies a weight that indicates how many data items are represented by the particular density model.

7. The method of claim 1, wherein estimating the number of rows uses the particular density model to estimate how many rows contain values that would satisfy at least one query predicate that filters rows based on values.

8. The method of claim 1, further comprising:

generating a third density model at least in part by aggregating a first set of functional components of the first density model and a second set of functional components of the second density model based at least in part on a first weight of the first density model and a second weight of the second density model;

wherein the particular density model approximates the third density model.

9. The method of claim 8, further comprising:

generating the particular density model to approximate the third density model at least in part by;

determining an initial set of functional components for the particular density model, wherein the initial set of functional components includes fewer components than the third density model;

iteratively growing the initial set of functional components at least in part by;

testing one or more additions of one or more functional components to the initial set of functional components; and

determining whether the one or more additions improved an approximation of the third density model beyond a threshold level.

10. The method of claim 8, wherein the first density model is received from a first distributed system that stores the first portion of the set of data, wherein a second distributed system stores the second portion of the set of data, and wherein the method is performed without access to at least the first portion of the set of data.

11. The method of claim 1, further comprising receiving, by the one or more computing devices, the particular density model with an indication that the particular density model approximates values for the first portion of the set of data and the second portion of the set of data, and storing, by the one or more computing devices, the particular density model in association with the set of data;

wherein at least some of the approximated values are stored on one or more other computing devices and not on the one or more computing devices.

12. The method of claim 1, wherein the set of data is a first column of a first table, and wherein estimating the number of rows is further based at least in part on one or more other density models that approximate value densities for one or more other columns of one or more tables.

13. One or more non-transitory storage media storing sequences of instructions which, when executed by one or more computing devices, cause:

estimating a number of rows that would be processed by each of one or more execution plans for a query based at least in part on a particular density model that approximates a weighted combination of at least a first density model for a first portion of a set of data and a second density model for a second portion of the set of data;

based at least in part on the number of rows estimated for said each of one or more execution plans for the query, selecting an execution plan for the query.

14. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause assigning the first portion to a first partition of the set of data based at least in part on one or more first key values in the first portion, and assigning the second portion to a second partition of the set of data based at least in part on one or more second key values in the second portion.

15. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause determining that the query, if executed, would access one or more rows from both the first portion and the second portion.

16. The one or more non-transitory storage media of claim 13, wherein the query is a first query, wherein the number of rows is a first number of rows estimated for said each of one or more execution plans for the query, and wherein the selected execution plan is a first execution plan, wherein the sequences of instructions include instruction that, when executed, cause:

determining that a second query, if executed, would access one or more rows from the first portion but not the second portion;

estimating a second number of rows that would be processed by each of one or more execution plans for the second query based at least in part on the first density model but not the second density model;

based at least in part on the second number of rows estimated for said each of one or more execution plans for the second query, selecting a second execution plan for the second query.

17. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause generating the particular density model by approximating the weighted combination of at least the first density model and the second density model.

18. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause storing the particular density model in association with the set of data, wherein the particular density model specifies a weight that indicates how many data items are represented by the particular density model.

19. The one or more non-transitory storage media of claim 13, wherein estimating the number of rows comprises using the particular density model to estimate how many rows contain values that would satisfy at least one query predicate that filters rows based on values.

20. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause:

generating a third density model at least in part by aggregating a first set of functional components of the first density model and a second set of functional components of the second density model based at least in part on a first weight of the first density model and a second weight of the second density model;

wherein the particular density model approximates the third density model.

21. The one or more non-transitory storage media of claim 20, wherein the sequences of instructions include instructions that, when executed, cause generating the particular density model to approximate the third density model at least in part by:

determining an initial set of functional components for the particular density model, wherein the initial set of functional components includes fewer components than the third density model;

iteratively growing the initial set of functional components at least in part by;

testing one or more additions of one or more functional components to the initial set of functional components;

determining whether the one or more additions improved an approximation of the third density model beyond a threshold level.

22. The one or more non-transitory storage media of claim 20, wherein the sequences of instructions include instructions that, when executed, cause receiving the first density model from a first distributed system that stores the first portion of the set of data, wherein a second distributed system stores the second portion of the set of data, and wherein the instructions are performed without access to at least the first portion of the set of data.

23. The one or more non-transitory storage media of claim 13, wherein the sequences of instructions include instructions that, when executed, cause receiving, by the one or more computing devices, the particular density model with an indication that the particular density model approximates values for the first portion of the set of data and the second portion of the set of data, and storing, by the one or more computing devices, the particular density model in association with the set of data;

wherein at least some of the approximated values are stored on one or more other computing devices and not on the one or more computing devices.

24. The one or more non-transitory storage media of claim 13, wherein the set of data is a first column of a first table, and wherein estimating the number of rows is further based at least in part on one or more other density models that approximate value densities for one or more other columns of one or more tables.