Data Flow Graph Optimization Using Adaptive Rule Chaining

• US 20140372409A1
• Filed: 08/28/2014
• Published: 12/18/2014
• Est. Priority Date: 04/26/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Weyerhaeuser, Christoph, Mindnich, Tobias, Baeumges, Daniel, Kazmaier, Gerrit Simon
• Granted Patent: US 9,223,828 B2
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A query is received and an initial data flow graph comprising a plurality of nodes is generated for executing the query. The initial data flow graph is optimized using a model optimizer that accesses at least one of a plurality of patterns to identify a matching pattern and executes at least one optimization rule associated with a matching pattern. Execution of the query is then initiated using the optimized data flow graph. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method comprising:

receiving a query;

generating, by a calculation engine, an initial data flow graph comprising a plurality of nodes for executing the query, the calculation engine operating in a calculation engine layer above a logical layer which, in turn, interacts with a physical table pool;

optimizing, by the calculation engine, the initial data flow graph using a model optimizer, the model optimizer accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with a matching pattern; and

initiating executing of the query by invoking the calculation engine to execute the optimized data flow graph.

2. A method as in claim 1, wherein the plurality of patterns are ranked and are accessed by the model optimizer according to the ranking.

3. A method as in claim 2, wherein the plurality of patterns are ranked according to user-specified criterion.

4. A method as in claim 2, wherein the plurality of patterns are ranked according to a cost function to execute rules associated with the corresponding pattern, the cost function characterizing processing resources required to apply at least one corresponding rule for such pattern.

5. A method as in claim 1, wherein at least one of the patterns has a plurality of corresponding rules, wherein such plurality of rules are ranked and are accessed by the model optimizer according to the ranking.

6. A method as in claim 5, wherein the plurality of rules are ranked according to user-specified criterion.

7. A method as in claim 5, wherein the plurality of rules are ranked according to a cost function to execute such rule, the cost function characterizing processing resources required to apply at least such rule.

8. A method as in claim 1, wherein each patterns specifies a start node within the initial data flow graph, the start node being used to determine whether the pattern matches.

9. A method as in claim 8, wherein each pattern specifies how many preceding and/or succeeding nodes, if any, to be considered to determine whether the pattern matches.

10. A method as in claim 1, wherein one or more of the receiving, generating, optimizing, and initiating are performed by at least one data processor of at least one computing system.

17. A computer program product as in claim 5, wherein the plurality of rules are ranked according to a cost function to execute such rule, the cost function characterizing processing resources required to apply at least such rule.

11. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

receiving a query;

generating, by a calculation engine, an initial data flow graph comprising a plurality of nodes for executing the query, the calculation engine operating in a calculation engine layer above a logical layer which, in turn, interacts with a physical table pool;

optimizing, by the calculation engine, the initial data flow graph using a model optimizer, the model optimizer accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with a matching pattern; and

initiating executing of the query by invoking the calculation engine to execute the optimized data flow graph.

12. A computer program product as in claim 11, wherein the plurality of patterns are ranked and are accessed by the model optimizer according to the ranking.

13. A computer program product as in claim 12, wherein the plurality of patterns are ranked according to user-specified criterion.

14. A computer program product as in claim 12, wherein the plurality of patterns are ranked according to a cost function to execute rules associated with the corresponding pattern, the cost function characterizing processing resources required to apply at least one corresponding rule for such pattern.

15. A computer program product as in claim 11, wherein at least one of the patterns has a plurality of corresponding rules, wherein such plurality of rules are ranked and are accessed by the model optimizer according to the ranking.

16. A computer program product as in claim 15, wherein the plurality of rules are ranked according to user-specified criterion.

18. A computer program product as in claim 11, wherein each patterns specifies a start node within the initial data flow graph, the start node being used to determine whether the pattern matches.

19. A computer product as in claim 18, wherein each pattern specifies how many preceding and/or succeeding nodes, if any, to be considered to determine whether the pattern matches.

20. A system comprising:

one or more data processors; and

memory storing instructions, which when executed, cause at least one data processor to perform operations comprising;

receiving a query;

generating an initial data flow graph comprising a plurality of nodes for executing the query;

optimizing the initial data flow graph using a model optimizer, the model optimizer accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with a matching pattern; and

initiating executing of the query using the optimized data flow graph.

wherein;

the patterns each have respective priority levels,

at least one corresponding priority level is dynamically set based on the data flow graph, and

the matching pattern gives each rule a priority.