Granted Patent B2

US 10,795,889 · App. 15/750,645 · Granted Oct 6, 2020

Inventor: Natalya Aksman (Cambridge, MA)

Assignee: MICRO FOCUS LLC

G06F16/24544G06F16/24524G06F16/24535G06F16/24542

Abstract

Claims (70)

1. A method comprising:

receiving a query to retrieve data;

generating, by a processor, a query path for retrieving the data from a database by:

determining a non-aggregate projection that includes data values from a table column of a database table referenced in the query;

determining an aggregate projection that includes an aggregated value calculated from the table column of the database table referenced in the query;

generating a first join graph using the non-aggregate projection;

generating a second join graph using the aggregate projection;

identifying join orders of the first join graph as first candidate query paths derived from the non-aggregate projection;

identifying join orders of the second join graph as second candidate query paths derived from the aggregate projection;

comparing the first candidate query paths with the second candidate query paths to determine a selected query path for the query; and

retrieving, by the processor, the data from the database for the query using the selected query path.

2. The method of claim 1 , wherein comparing the first candidate query paths with the second candidate query paths comprises:

identifying a particular candidate query path from among the second candidate query paths that does not support a group-by pushdown transformation; and

discarding the particular candidate query path from consideration as the selected query path.

3. The method of claim 1 , wherein comparing the first candidate query paths with the second candidate query paths comprises:

applying a path cost criterion for the first candidate query paths to identify a first query path;

applying the path cost criterion for the second candidate query paths to identify a second query path; and

determining the selected query path from between the first query path and the second query path.

4. The method of claim 1 , wherein identifying the aggregate projection comprises:

identifying a top-k aggregate projection that includes a top “k” number of rows from a partition of selected rows, wherein the top-k aggregation projection is identified when each expression on the database table referenced in the query is derived from a top-k expression in the top-k aggregate projection.

5. The method of claim 4 , wherein comparing the first candidate query paths with the second candidate query paths comprises:

discarding, from consideration of the selected query path, the top-k aggregate projection when a query limit specified in the query exceeds the “k” number of rows of the top-k aggregate projection.

6. The method of claim 1 , wherein the query references a column of a first table and a column of a second table,

wherein identifying the non-aggregate projection comprises: identifying a first non-aggregate projection that includes the column of the first table and a second non-aggregate projection that includes the column of the second table,

wherein generating the first join graph comprises: generating a base join graph using a combination of the first and second tables referenced in the query and the first and second non-aggregate projections, and

wherein generating the second join graph comprises: substituting the first table or the second table in the base join graph with the aggregate projection.

7. A system comprising:

a processor; and

a non-transitory machine readable medium storing instructions executable to cause the processor to:

receive a query;

identify an aggregate projection to consider for generating a query path for the query, wherein the aggregate projection includes an aggregated value calculated from a table column of a database table referenced in the query;

compare candidate query paths for the query derived from the aggregate projection with candidate query paths for the query derived from a non-aggregate projection to determine the query path for the query;

discard, from consideration as the query path, a particular query path derived from the aggregate projection when the particular query path does not support a group-by pushdown transformation; and

retrieve data from a database for the query using the query path.

8. The system of claim 7 , wherein the instructions are executable to cause the processor to:

generate a first join graph using the non-aggregate projection;

identify join orders for the first join graph as at least some of the candidate query paths derived from the non-aggregate projection;

generate a second join graph using the aggregate projection; and

identify join orders for the second join graph as at least some of the candidate query paths derived from the aggregate projection.

9. The system of claim 7 , wherein the instructions are executable to cause the processor to:

identify the non-aggregate projection that includes the table column of the database table referenced in the query; and

generate a base join graph using a combination of the database table referenced in the query and the identified non-aggregate projection; and

generate one of the candidate query paths derived from the non-aggregate projection using the base join graph.

10. The system of claim 7 , wherein the aggregate projection is a top-k aggregation projection that includes a top “k” number of rows from a partition of selected rows.

11. The system of claim 10 , wherein the instructions are executable to cause the processor to discard, from consideration as the query path, one of the candidate query paths derived from the top-k aggregation projection when a query limit specified in the query exceeds the “k” number of rows of the top-k aggregation projection.

12. The system of claim 7 , wherein the instructions are executable to cause the processor to identify the aggregate projection to consider for generating the query path when the table column of the database table referenced in the query is also referenced in the aggregate projection.

13. A non-transitory computer-readable medium storing executable instructions that cause a processor to:

receive a query to retrieve data, the query comprising a sub-query within the query;

identify an aggregate projection to consider for generating a sub-query path for the sub-query within the query, wherein the aggregate projection includes an aggregated value calculated from a table column of a database table referenced in the sub-query;

identify first candidate sub-query paths for the sub-query derived from the aggregate projection by:

generating a join graph for the sub-query using the aggregate projection, and

identifying join orders for the join graph as the first candidate sub-query paths derived from the aggregate projection;

determine a candidate query path for the query;

evaluate, after determining the candidate query path, the first candidate sub-query paths derived from the aggregate projection within a context of the candidate query path;

select a particular candidate sub-query path among the first candidate sub-query paths to use in a query path for the query; and

retrieve the data from a database using the query path that includes the particular candidate sub-query path.

14. The non-transitory computer-readable medium of claim 13 , wherein the executable instructions cause the processor to:

identify a non-aggregate projection to consider for generating the sub-query path for the sub-query within the query, wherein the non-aggregate projection includes the table column of the database table referenced in the sub-query.

15. The non-transitory computer-readable medium of claim 14 , wherein the executable instructions cause the processor to:

identify second candidate sub-query paths for the sub-query derived from the non-aggregate projection that includes the table column of the database table referenced in the sub-query; and

compare the second candidate sub-query paths derived from the non-aggregate projection with the first candidate sub-query paths derived from the aggregate projection.

16. The non-transitory computer-readable medium of claim 13 , wherein the aggregate projection is a top-k aggregate projection that includes a top “k” number of rows from a partition of selected rows.

17. The non-transitory computer-readable medium of claim 16 , wherein the executable instructions cause the processor to discard one of the first candidate sub-query paths that was derived from the top-k aggregate projection when a query limit specified in the query exceeds the “k” number of rows of the top-k aggregate projection.

18. The non-transitory computer-readable medium of claim 13 , wherein the executable instructions cause the processor to identify the aggregate projection to consider for generating the sub-query path when the table column of the database table referenced in the sub-query is also referenced in the aggregate projection.

19. The non-transitory computer-readable medium of claim 13 , wherein the sub-query references a column of a first table and a column of a second table, and

wherein the executable instructions cause the processor to:

identify a first non-aggregate projection that includes the column of the first table and a second non-aggregate projection that includes the column of the second table, and

generate a base join graph using a combination of the first and second tables referenced in the sub-query and the first and second non-aggregate projections.

20. The non-transitory computer-readable medium of claim 19 , wherein, to generate the join graph using the aggregate projection, the executable instructions cause the processor to:

substitute the first table or the second table in the base join graph with the aggregate projection.

Assignments (8)

Continuity (1)