DECORRELATION OF USER-DEFINED FUNCTION INVOCATIONS IN QUERIES

• US 20150220597A1
• Filed: 01/31/2014
• Published: 08/06/2015
• Est. Priority Date: 01/31/2014
• Status: Active Grant

• Current Assignee: Indian Institute of Technology Bombay, Indian Institute of Technology Hyderabad
• Original Assignee: Indian Institute of Technology Bombay, Indian Institute of Technology Hyderabad
• Inventors: Ramachandra, Karthik, Sudarshan, Sundararajarao, Simhadri, Varun, Miriappalli, Arun Chaitanya, Guravannavar, Ravindra
• Granted Patent: US 10,191,943 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems, methods, and computer-readable medium, are disclosed for transforming user-defined-function invocations in a query-based environment. A user-defined-function (UDF) and a query invoking the UDF are received. The UDF is parsed into a plurality of statements. A first expression tree corresponding to the UDF and a second expression tree corresponding the query are constructed, and merged using an operator to generate a transformed expression. The transformed expression is simplified, using transformation rules, if it is determined that is can be simplified.

Claims

1. A computer-implemented method for transforming user-defined-function invocations within a query-based environment, the method comprising:

receiving a query with a user-defined-function (UDF);

parsing the UDF into a plurality of statements;

constructing a first expression tree representation of the UDF;

constructing a second expression tree representation of the query absent the UDF;

generating a transformed expression representation of the query by merging the first expression tree and the second expression tree based on parameters of the first expression tree and attributes of the second expression tree; and

simplifying the transformed expression using transformation rules, based on a determination that the transformed expression can be simplified.

2. The method of claim 1, wherein the first expression tree is constructed using a control flow graph having at least two nodes and an edge connecting the at least two nodes, wherein the edge represents a flow through statements of the UDF, and the nodes represent a statement of the UDF.

3. The method of claim 1, wherein the first expression tree is a parameterized expression tree of the UDF.

4. The method of claim 1, wherein the constructing of the first expression tree includes applying a set of operators selected from one of an apply-bind operator, apply-merge operator, a conditional-apply-merge operator, and an apply-cross operator.

5. The method of claim 1, wherein the generating of the transformed expression includes merging the first expression tree and the second expression tree by applying an apply-bind operator.

6. The method of claim 1, wherein the constructing of the first expression tree comprises:

determining a type of a statement of the plurality of statements;

choosing, based on the type of the statement, an operator from the set of operators; and

applying the operator to the statement to generate part of the first expression tree.

7. The method of claim 6, wherein the statement is at least one of an assignment statement, an if-then-else conditional statement, or a return statement.

8. The method of claim 6, further comprising:

choosing an apply-merge operator when the statement is an assignment statement;

choosing a conditional-apply-merge operator when the statement is an if-then-else conditional statement; and

choosing a conditional-apply-merge operator when the statement is a return statement.

9. The method of claim 1, wherein the simplifying of the transformed expression includes removing the applied set of operators based on the transformation rules.

10. The method of claim 1, further comprising generating a query representing the simplified transformed expression.

11. A system for transforming user-defined-function invocations within a query-based environment, the system comprising:

a parser module configured to;

receive a query with a user-defined-function (UDF); and

parse the UDF into a plurality of statements;

a processor-implemented tree-construction module configured to;

construct a first expression tree representation of the UDF; and

construct a second expression tree representation of the query absent the UDF; and

a transformer module configured to;

generate a transformed expression representation of the query by merging the first expression tree and the second expression tree based on parameters of the first expression tree and attributes of the second expression tree; and

simplify the transformed expression using transformation rules, based on a determination that the transformed expression can be simplified.

12. The system of claim 11, wherein the tree-construction module constructs the first tree expression includes applying a set of operators selected from one of an apply-bind operator, apply-merge operator, a conditional-apply-merge operator, and an apply-cross operator.

13. The system of claim 11, wherein the tree-construction module constructs the first expression tree using a control flow graph having at least two nodes and an edge connecting the at least two nodes, wherein the edge represents a flow through statements of the UDF, and the nodes represent a statement of the UDF.

14. The system of claim 11, wherein the tree-construction module merges the first expression and the second expression by using an apply-bind operator.

15. The system of claim 11, wherein the tree-construction module is further configured to:

determine a type of a statement of the plurality of statements;

choose, based on the type of the statement, an operator from the set of operators; and

apply the operator to the statement to generate part of the first expression tree.

16. The system of claim 15, wherein the tree-construction module is further configured to:

choose an apply-merge operator when the statement is an assignment statement;

choose a conditional-apply-merge operator when the statement is an if-then-else conditional statement; and

choose a conditional-apply-merge operator when the statement is a return statement.

17. A non-transitory computer-readable storage device configured to store instructions executable by a processing device, wherein execution of the instructions in a query-based environment causes the processing device to implement a method of transforming a user-defined-function invocations within the query-based environment comprising:

receiving a query with a user-defined-function (UDF);

parsing the UDF into a plurality of statements;

constructing a first expression tree representation of the UDF;

constructing a second expression tree representation of the query absent the UDF;

generating a transformed expression representation of the query by merging the first expression tree and the second expression tree based on parameters of the first expression tree and attributes of the second expression tree; and

simplifying the transformed expression using transformation rules, based on a determination that the transformed expression can be simplified.

18. The non-transitory storage device of claim 17, wherein the constructing of the first expression tree includes applying a set of operators selected from one of an apply-bind operator, apply-merge operator, a conditional-apply-merge operator, and an apply-cross operator.

19. The non-transitory storage device of claim 17, wherein the first expression tree is constructed using a control flow graph having at least two nodes and an edge connecting the at least two nodes, wherein the edge represents a flow through statements of the UDF, and the nodes represent a statement of the UDF.

20. The non-transitory storage device of claim 17, further comprising:

determining a type of a statement of the plurality of statements;

choosing an apply-merge operator when the statement is an assignment statement;

choosing a conditional-apply-merge operator when the statement is an if-then-else conditional statement;

choosing a conditional-apply-merge operator when the statement is a return statement; and

applying the operator to the statement to generate part of the first expression tree.