Data flow graph optimization using adaptive rule chaining

• US 9,223,828 B2
• Filed: 08/28/2014
• Issued: 12/29/2015
• 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
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US14/471,368
• Publication Number:
  US 20140372409A1
• Time in Patent Office: 488 Days
• Field of Search: 707/719
• US Class Current: 1/1
• 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 computer-implemented method for implementation by one or more data processors forming part of at least one computing system, the method comprising:

receiving, by at least one data processor, 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 using an adaptive rule chaining approach, the initial data flow graph using a model optimizer, the model optimizer iteratively accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with the matching pattern, wherein the adaptive rule chaining approach identifies patterns requiring less computing resources, wherein each pattern of the patterns specifies a start node within the initial data flow graph that is used to determine whether the pattern matches, wherein said each pattern specifies how many preceding and succeeding nodes, if any preceding and succeeding nodes are to be considered to determine whether the pattern matches, wherein changes to a node by a rule results in a further identification of a matching pattern; and

initiating executing of the query by invoking the calculation engine to execute the optimized data flow graph, wherein the patterns each have respective priority levels with at least one corresponding priority level being dynamically set based on the data flow graph, and the matching pattern gives each rule a priority.

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

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

4. The 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 pattern.

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

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

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

8. The 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. The 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.

10. A non-transitory computer-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, by at least one data processor, 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 using an adaptive rule chaining approach, the initial data flow graph using a model optimizer, the model optimizer iteratively accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with the matching pattern, wherein the adaptive rule chaining approach identifies patterns requiring less computing resources, wherein each pattern of the patterns specifies a start node within the initial data flow graph that is used to determine whether the pattern matches, wherein said each pattern specifies how many preceding and succeeding nodes, if any preceding and succeeding nodes are to be considered to determine whether the pattern matches, wherein changes to a node by a rule results in a further identification of a matching pattern; and

initiating executing of the query by invoking the calculation engine to execute the optimized data flow graph, wherein the patterns each have respective priority levels with at least one corresponding priority level being dynamically set based on the data flow graph, and the matching pattern gives each rule a priority.

11. The non-transitory computer-readable medium as in claim 10, wherein the plurality of patterns are ranked and are accessed by the model optimizer according to the ranking.

12. The non-transitory computer-readable medium as in claim 11, wherein the plurality of patterns are ranked according to user-specified criterion.

13. The non-transitory computer-readable medium as in claim 11, wherein the plurality of patterns are ranked according to a cost function to execute rules associated with corresponding pattern, the cost function characterizing processing resources required to apply at least one corresponding rule for pattern.

14. The non-transitory computer-readable medium as in claim 10, wherein at least one of the patterns has a plurality of corresponding rules, wherein plurality of rules are ranked and are accessed by the model optimizer according to the ranking.

15. The non-transitory computer-readable medium as in claim 14, wherein the plurality of rules are ranked according to user-specified criterion.

16. The non-transitory computer-readable medium as in claim 10, wherein the plurality of rules are ranked according to a cost function to execute rule, the cost function characterizing processing resources required to apply at least rule.

17. The non-transitory computer-readable medium as in claim 10, wherein each pattern of the patterns specifies a start node within the initial data flow graph, the start node being used to determine whether the pattern matches.

18. 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, by at least one data processor, 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 using an adaptive rule chaining approach, the initial data flow graph using a model optimizer, the model optimizer iteratively accessing at least one of a plurality of patterns to identify a matching pattern and executing at least one optimization rule associated with the matching pattern, wherein the adaptive rule chaining approach identifies patterns requiring less computing resources, wherein each pattern of the patterns specifies a start node within the initial data flow graph that is used to determine whether the pattern matches, wherein said each pattern specifies how many preceding and succeeding nodes, if any preceding and succeeding nodes are to be considered to determine whether the pattern matches, wherein changes to a node by a rule results in a further identification of a matching pattern; and

initiating executing of the query by invoking the calculation engine to execute the optimized data flow graph, wherein the patterns each have respective priority levels with at least one corresponding priority level being dynamically set based on the data flow graph, and the matching pattern gives each rule a priority.

19. The system as in claim 18, wherein the plurality of patterns are ranked and are accessed by the model optimizer according to the ranking.

20. The system as in claim 19, wherein the plurality of patterns are ranked according to user-specified criterion.

21. The system as in claim 19, 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 pattern.

22. The system as in claim 19, wherein at least one of the patterns has a plurality of corresponding rules, wherein plurality of rules are ranked and are accessed by the model optimizer according to the ranking.

23. The system as in claim 22, wherein the plurality of rules are ranked according to user-specified criterion.