초록 ▼

Provided are techniques for optimizing the processing of hierarchical data. A linear processing graph is received, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical

Provided are techniques for optimizing the processing of hierarchical data. A linear processing graph is received, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows on arcs, wherein the operators read and replace identified subregions within the hierarchical data flowing into the operators on the arcs, and wherein the operators do not modify the hierarchical data outside of these identified subregions. For each operator in the linear processing graph, a minimal set of dependent upstream operators on which that operator depends is found by examining how the identified subregions are created in the linear processing graph through obtaining a set of operators on which that operator depends, by analyzing dependencies carried by a set of vector nodes of the hierarchical data in an input schema of the operator, and, for each of the vector nodes, by analyzing an associated set of scalar nodes, wherein finding the minimum set of operators includes taking into consideration data preservation characteristics of the plurality of operators and taking into consideration structural-order preservation characteristics of the plurality of operators. The linear processing graph is rewritten to create a new graph that expresses dependencies based on the minimal set of dependent upstream operators for each operator.

대표청구항 ▼

What is claimed is: 1. A computer-implemented method, comprising: receiving a linear processing graph, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows

What is claimed is: 1. A computer-implemented method, comprising: receiving a linear processing graph, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows on arcs, wherein the operators read and replace identified subregions within the hierarchical data flowing into the operators on the arcs, and wherein the operators do not modify the hierarchical data outside of these identified subregions; for each operator in the linear processing graph, finding a minimal set of dependent upstream operators on which that operator depends by examining how the identified subregions are created in the linear processing graph while taking into consideration data preservation characteristics of the plurality of operators and taking into consideration structural-order preservation characteristics of the plurality of operators by: obtaining a set of operators on which the operator depends; obtaining a set of vector nodes of the hierarchical data in an input schema of the operator, wherein a vector node represents a vector including scalars that are represented by a set of scalar nodes; and for each of the vector nodes, analyzing the set of scalar nodes to determine the dependencies, wherein a scalar node represents a scalar; and rewriting the linear processing graph to create a new graph that expresses dependencies based on the minimal set of dependent upstream operators for each operator by inserting at least one context split operator and at least one context merge operator into the new graph. 2. The method of claim 1, wherein rewriting further comprises: computing a minimum set of context split operators and context merge operators. 3. The method of claim 2, wherein the new graph comprises the at least one context split operator that provides data to at least two operators, wherein each of the two operators uses the provided data and further comprising: inserting the at least one context split operator into the new graph at a point of sharing based on collapsing common sub-expressions together. 4. The method of claim 2, wherein the new graph comprises the at least one context merge operator that merges output of at least two operators in the new graph. 5. The method of claim 1, wherein the new graph comprises a directed graph. 6. A computer program product comprising a computer-readable storage medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to: receive a linear processing graph, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows on arcs, wherein the operators read and replace identified subregions within the hierarchical data flowing into the operators on the arcs, and wherein the operators do not modify the hierarchical data outside of these identified subregions; for each operator in the linear processing graph, find a minimal set of dependent upstream operators on which that operator depends by examining how the identified subregions are created in the linear processing graph while taking into consideration data preservation characteristics of the plurality of operators and taking into consideration structural-order preservation characteristics of the plurality of operators by: obtaining a set of operators on which the operator depends; obtaining a set of vector nodes of the hierarchical data in an input schema of the operator, wherein a vector node represents a vector including scalars that are represented by a set of scalar nodes; and for each of the vector nodes, analyzing the set of scalar nodes to determine the dependencies, wherein a scalar node represents a scalar; and rewrite the linear processing graph to create a new graph that expresses dependencies based on the minimal set of dependent upstream operators for each operator by inserting at least one context split operator and at least one context merge operator into the new graph. 7. The computer program product of claim 6, wherein when rewriting, the computer readable program when executed on a computer causes the computer to: compute a minimum set of context split operators and context merge operators. 8. The computer program product of claim 7, wherein the new graph comprises the at least one context split operator that provides data to at least two operators, wherein each of the two operators uses the provided data, and wherein the computer readable program when executed on a computer causes the computer to: insert the at least one context split operator into the new graph at a point of sharing based on collapsing common sub-expressions together. 9. The computer program product of claim 7, wherein the new graph comprises the at least one context merge operator that merges output of at least two operators in the new graph. 10. The computer program product of claim 6, wherein the new graph comprises a directed graph. 11. A system, comprising: hardware logic performing operations, the operations comprising: receiving a linear processing graph, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows on arcs, wherein the operators read and replace identified subregions within the hierarchical data flowing into the operators on the arcs, and wherein the operators do not modify the hierarchical data outside of these identified subregions; for each operator in the linear processing graph, finding a minimal set of dependent upstream operators on which that operator depends by examining how the identified subregions are created in the linear processing graph while taking into consideration data preservation characteristics of the plurality of operators and taking into consideration structural-order preservation characteristics of the plurality of operators by: obtaining a set of operators on which the operator depends; obtaining a set of vector nodes of the hierarchical data in an input schema of the operator, wherein a vector node represents a vector including scalars that are represented by a set of scalar nodes; and for each of the vector nodes, analyzing the set of scalar nodes to determine the dependencies, wherein a scalar node represents a scalar; and rewriting the linear processing graph to create a new graph that expresses dependencies based on the minimal set of dependent upstream operators for each operator by inserting at least one context split operator and at least one context merge operator into the new graph. 12. The system of claim 11, wherein operations for rewriting further comprise: computing a minimum set of context split operators and context merge operators. 13. The system of claim 11, wherein the new graph comprises the at least one context split operator that provides data to at least two operators, wherein each of the two operators uses the provided data, and wherein the operations further comprise: inserting the at least one context split operator into the new graph at a point of sharing based on collapsing common sub-expressions together. 14. The system of claim 11, wherein the new graph comprises the at least one context merge operator that merges output of at least two operators in the new graph. 15. The system of claim 11, wherein the new graph comprises a directed graph.