System and method for optimized query execution in computerized data modeling and analysis
A sequence of queries is divided into stages, where each stage involves one pass over the data, such that the sequence of queries can be executed using the minimum number of passes over the data. The sequence of queries may be processed into a functional dependency graph that represents the relationships between query parameters (signals) and query operations, and the functional dependency graph then may be processed to divide the queries into a number of successive stages such that each stage includes queries that can be executed based on data that exists prior to execution of that stage. A sequence of queries may, and often does, require that one or more intermediate values or datasets be generated using an aggregate function.
1. A computer-implemented method for converting scalar expressions to relational database queries applied to a dataset, the method comprising:
producing a functional dependency graph representing the scalar expressions and any interdependencies between the scalar expressions;
assigning each scalar expression to one of a plurality of successive execution stages based on the functional dependency graph such that each execution stage includes at least one of the scalar expressions,
wherein the at least one scalar expression associated with any given stage does not require results from a subsequent stage of the plurality of successive stages; and
converting the scalar expressions at each stage into one or more relational database queries to create a sequence of relational database queries such that execution of the one or more relational database queries at each execution stage involves at most one pass through the dataset.
2. The method of claim 1 , wherein at least one stage involves generation of a temporary data set used in at least one subsequent stage.
3. The method of claim 1 , wherein each stage includes the maximum number of possible expressions that can be executed at that stage.
4. The method of claim 1 , wherein producing the functional dependency graph comprises, for each scalar expression:
identifying an output parameter and a set of input parameters associated with the scalar expression;
creating a node for the output parameter in the functional dependency graph if the node for the output parameter does not exist in the functional dependency graph;
creating, for each input parameter in the set of input parameters, a distinct node in the functional dependency graph if the distinct node for the input parameter does not exist in the functional dependency graph; and
establishing, in the functional dependency graph, an association between the output parameter node and each of distinct input parameter nodes.
5. The method of claim 4 , wherein the association includes an operator node when the output parameter node is dependent on a combination of two or more distinct input parameter nodes, the operator node representing an operator to be performed on the two or more distinct input parameters.
6. The method of claim 1 , where assigning each scalar expression to one of the plurality of successive stages based on the functional dependency graph comprises:
traversing the functional dependency graph using a breadth first traversal configured to exclude, from each given execution stage, any aggregate expression at a lower-level of the functional dependency graph; and
assigning each expression to a given stage based on the breadth first traversal.
7. The method of claim 1 , wherein converting the nodes at each stage into one or more relational database queries to create a sequence of relational database queries comprises:
generating a sequence of structured query language commands.
8. The method of claim 1 , wherein assigning each scalar expression to one of the plurality of successive execution stages based on the functional dependency graph ensures the minimum number of passes through the dataset for execution of the scalar expressions.
9. A system for converting scalar expressions to relational database queries for application to a dataset, the system comprising:
a computer system having stored thereon and executing computer processes comprising:
producing a functional dependency graph representing the scalar expressions and any interdependencies between the scalar expressions;
assigning each scalar expression to one of a plurality of successive execution stages based on the functional dependency graph such that each execution stage includes at least one of the scalar expressions,
wherein the at least one scalar expression associated with any given stage does not require results from a subsequent stage of the plurality of successive stages; and
converting the scalar expressions at each stage into one or more relational database queries to create a sequence of relational database queries such that execution of the one or more relational database queries at each execution stage involves at most one pass through the dataset.
10. The system of claim 9 , wherein at least one stage involves generation of a temporary data set used in at least one subsequent stage.
11. The system of claim 9 , wherein each stage includes the maximum number of possible expressions that can be executed at that stage.
12. The system of claim 9 , wherein producing the functional dependency graph comprises, for each scalar expression:
identifying an output parameter and a set of input parameters associated with the scalar expression;
creating a node for the output parameter in the functional dependency graph if the node for the output parameter does not exist in the functional dependency graph;
creating, for each input parameter in the set of input parameters, a distinct node in the functional dependency graph if the distinct node for the input parameter does not exist in the functional dependency graph; and
establishing, in the functional dependency graph, an association between the output parameter node and each of distinct input parameter nodes.
13. The system of claim 12 , wherein the association includes an operator node when the output parameter node is dependent on a combination of two or more distinct input parameter nodes, the operator node representing an operator to be performed on the two or more distinct input parameters.
14. The system of claim 9 , where assigning each scalar expression to one of the plurality of successive stages based on the functional dependency graph comprises:
traversing the functional dependency graph using a breadth first traversal configured to exclude, from each given execution stage, any aggregate expression at a lower-level of the functional dependency graph; and
assigning each expression to a given stage based on the breadth first traversal.
15. The system of claim 9 , wherein converting the nodes at each stage into one or more relational database queries to create a sequence of relational database queries comprises:
generating a sequence of structured query language commands.
16. The system of claim 9 , wherein assigning each scalar expression to one of the plurality of successive execution stages based on the functional dependency graph ensures the minimum number of passes through the dataset for execution of the scalar expressions.
17. A computer program product comprising a tangible, non-transitory computer readable medium having stored thereon a computer program for converting scalar expressions to relational database queries for application to a dataset, which, when run on a computer system, causes the computer system to execute interactive database query reporting computer processes comprising:
producing a functional dependency graph representing the scalar expressions and any interdependencies between the scalar expressions;
assigning each scalar expression to one of a plurality of successive execution stages based on the functional dependency graph such that each execution stage includes at least one of the scalar expressions,
wherein the at least one scalar expression associated with any given stage does not require results from a subsequent stage of the plurality of successive stages; and
converting the scalar expressions at each stage into one or more relational database queries to create a sequence of relational database queries such that execution of the one or more relational database queries at each execution stage involves at most one pass through the dataset.
18. The computer program product of claim 17 , wherein at least one stage involves generation of a temporary data set used in at least one subsequent stage.
19. The computer program product of claim 17 , wherein each stage includes the maximum number of possible expressions that can be executed at that stage.
20. The computer program product of claim 17 , wherein producing the functional dependency graph comprises, for each scalar expression:
identifying an output parameter and a set of input parameters associated with the scalar expression;
creating a node for the output parameter in the functional dependency graph if the node for the output parameter does not exist in the functional dependency graph;
creating, for each input parameter in the set of input parameters, a distinct node in the functional dependency graph if the distinct node for the input parameter does not exist in the functional dependency graph; and
establishing, in the functional dependency graph, an association between the output parameter node and each of distinct input parameter nodes.
21. The computer program product of claim 20 , wherein the association includes an operator node when the output parameter node is dependent on a combination of two or more distinct input parameter nodes, the operator node representing an operator to be performed on the two or more distinct input parameters.
22. The computer program product of claim 17 , where assigning each scalar expression to one of the plurality of successive stages based on the functional dependency graph comprises:
traversing the functional dependency graph using a breadth first traversal configured to exclude, from each given execution stage, any aggregate expression at a lower-level of the functional dependency graph; and
assigning each expression to a given stage based on the breadth first traversal.
23. The computer program product of claim 17 , wherein converting the nodes at each stage into one or more relational database queries to create a sequence of relational database queries comprises:
generating a sequence of structured query language commands.
24. The computer program product of claim 17 , wherein assigning each scalar expression to one of the plurality of successive execution stages based on the functional dependency graph ensures the minimum number of passes through the dataset for execution of the scalar expressions.