Systems and methods for scheduling data flow execution based on an arbitrary graph describing the desired data flow

• US 20040186915A1
• Filed: 03/18/2003
• Published: 09/23/2004
• Est. Priority Date: 03/18/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Howey, James K., Blaszczak, Michael A.
• Granted Patent: US 7,953,891 B2
• Time in Patent Office: Days
• US Class Current: 709/246
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

The data transformation system (DTS) in one embodiment of the present invention comprises a capability to receive data from a data source, a data destination and a capability to store transformed data therein, and a data transformation pipeline (DTP) that constructs complex end-to-end data transformation functionality (data flow executions or DFEs) by pipelining data flowing from one or more sources to one or more destinations through various interconnected nodes (that, when instantiated, become components in the pipeline) for transforming the data as it flows by (where the term transforming is used herein to broadly describe the universe of interactions that can be conducted to, with, by, or on data). Each component in the pipeline possesses specific predefined data transformation functionality, and the logical connections between components define the data flow pathway in an operational sense.

The data transformation pipeline (DTP) enables a user to develop complex end-to-end data transformation functionality (the DFEs) by graphically describing and representing, via a graphical user interface (GUI), a desired data flow from one or more sources to one or more destinations through various interconnected nodes (a graph). Each node in the graph selected by the user and incorporated in the graph represents specific predefined data transformation functionality (each a component), and connections between the nodes (the components) define the data flow pathway.

Claims

1. A data transformation service comprising:

a data retrieval system to receive data from a source;

a data transformation pipeline comprising;

a plurality of component objects;

a graphical user interface by which a user can represent a data transformation as a series of interconnected nodes in a graph, each node corresponding to a component object from among the plurality of components objects;

an interpreter that traverses the graph and translates the graph into a data flow execution plan and at least one work list, said list comprising at least one work item;

a pipeline engine to build the data flow execution based on the data flow execution plan, said data flow execution comprising a set of components instantiated from the plurality of component objects; and

a scheduler that executes at least one work item in at least one work list;

a destination data storage system to store data.

2. The data transformation pipeline of claim 1 wherein at least one instantiated component from among the set of components is defined by its inputs and outputs.

3. The data transformation pipeline of claim 1 wherein at least two uninstantiated components from among the plurality of component objects were developed on different platforms.

4. The data transformation pipeline of claim 1 wherein the set of components comprises:

an extraction component for extracting data from an external data source; and

a loading component for loading data to an external data destination.

5. The data transformation service of claim 4 wherein the scheduler further comprises a system for storing the data extracted from an external data source in a buffer.

6. The data transformation service of claim 5 wherein the data in the buffer is transformed by a component without being copied to another buffer.

7. The data transformation service of claim 5 wherein the scheduler automatically allocates sufficient space in the buffer for the external data stored in the buffer to be split without being copies to another buffer.

8. The data transformation service of claim 5 wherein the scheduler further comprises a system for enabling at least one component to directly transform the data in the buffer.

9. The data transformation service of claim 8 wherein the scheduler further comprises a system for enabling at least one additional component to directly transform the data in the buffer.

10. The data transformation service of claim 1 further comprising a sub-system for optimizing a direct translation of the graph into an optimized translation for the graph.

11. The data transformation service of claim 1 wherein each work item is one of the set of work items comprising:

extracting data from a data source;

providing data to a component;

splitting data from a single path onto two or more paths;

merging data from two or more paths into a single path; and

providing data to a data destination.

12. The data transformation service of claim 1 wherein the scheduler includes functionality for managing both synchronous and asynchronous components in the graph.

13. The data transformation service of claim 1 wherein:

at least one instantiated component from among the set of components is defined by its inputs and outputs;

the scheduler further comprises an extraction component for extracting data from an external data source and a loading component for loading data to an external data destination;

the scheduler further comprises a system for storing the data extracted from an external data source in a buffer;

the data in the buffer is transformed by a component without being copied to another buffer;

the scheduler automatically allocates sufficient space in the buffer for the external data stored in the buffer to be split without being copies to another buffer;

the scheduler further comprises a system for enabling at least two components to directly transform the data in the buffer;

the data transformation pipeline further comprises a subsystem for optimizing a direct translation of the graph into an optimized translation for the graph; and

each work item is one of the set of work items comprising;

extracting data from a data source, providing data to a component, splitting data from a single path onto two or more paths, merging data from two or more paths into a single path, and providing data to a data destination.

14. A data transformation pipeline comprising:

a plurality of component objects;

a graphical user interface by which a user can represent a data transformation as a series of interconnected nodes in a graph, each node corresponding to a component object from among the plurality of components objects;

an interpreter that traverses the graph and translates the graph into a data flow execution plan and at least one work list, said list comprising at least one work item;

a pipeline engine to build the data flow execution based on the data flow execution plan, said data flow execution comprising a set of components instantiated from the plurality of component objects; and

a scheduler that executes at least one work item in at least one work list.

15. The data transformation pipeline of claim 14 wherein at least one instantiated component from among the set of components is defined by its inputs and outputs.

16. The data transformation pipeline of claim 14 wherein at least two uninstantiated components from among the plurality of component objects were developed on different platforms.

17. The data transformation pipeline of claim 14 wherein the set of components comprises:

an extraction component for extracting data from an external data source; and

a loading component for loading data to an external data destination.

18. The data transformation pipeline of claim 17 wherein the scheduler further comprises a system for storing the data extracted from an external data source in a buffer.

19. The data transformation pipeline of claim 18 wherein the data in the buffer is transformed by a component without being copied to another buffer.

20. The data transformation pipeline of claim 18 wherein the scheduler automatically allocates sufficient space in the buffer for the external data stored in the buffer to be split without being copies to another buffer.

21. The data transformation pipeline of claim 18 wherein the scheduler further comprises a system for enabling at least one component to directly transform the data in the buffer.

22. The data transformation pipeline of claim 21 wherein the scheduler further comprises a system for enabling at least one additional component to directly transform the data in the buffer.

23. The data transformation pipeline of claim 14 further comprising a sub-system for optimizing a direct translation of the graph into an optimized translation for the graph.

24. The data transformation pipeline of claim 14 wherein each work item is one of the set of work items comprising:

extracting data from a data source;

providing data to a component;

splitting data from a single path onto two or more paths;

merging data from two or more paths into a single path; and

providing data to a data destination.

25. The data transformation pipeline of claim 14 wherein the scheduler includes functionality for managing both synchronous and asynchronous components in the graph.

26. The data transformation pipeline of claim 14 wherein:

at least one instantiated component from among the set of components is defined by its inputs and outputs;

the scheduler further comprises an extraction component for extracting data from an external data source and a loading component for loading data to an external data destination;

the scheduler further comprises a system for storing the data extracted from an external data source in a buffer;

the data in the buffer is transformed by a component without being copied to another buffer;

the scheduler automatically allocates sufficient space in the buffer for the external data stored in the buffer to be split without being copies to another buffer;

the scheduler further comprises a system for enabling at least two components to directly transform the data in the buffer;

the data transformation pipeline further comprises a subsystem for optimizing a direct translation of the graph into an optimized translation for the graph; and

each work item is one of the set of work items comprising;

extracting data from a data source, providing data to a component, splitting data from a single path onto two or more paths, merging data from two or more paths into a single path, and providing data to a data destination.

27. A method for transforming data comprising:

extracting data from at least one external data source;

storing the data in a buffer and establishing a set of primary pointers to the data;

passing the set of primary pointers to the data in the buffer to a first component in order for the first component to transform the data directly in the buffer; and

loading the data from the buffer to at least one external data destination.

28. The method of claim 27 wherein the data extracted from an external data source is a table of data comprising at least one row, and wherein each said row comprising at least one column.

29. The method of claim 28 wherein the set of primary pointers point to the beginning of the rows.

30. The method of claim 29 further comprising, after the element of passing the set of primary pointers to the data in the buffer to a first component in order for the first component to transform the data directly in the buffer, passing the set of primary pointers to the data in the buffer to a second component in order for the second component to transform the data directly in the buffer.

31. The method of claim 29 further comprising, after the element of storing the data in a buffer and establishing a set of primary pointers to the data, establishing a set of unassigned secondary pointers to the data and establishing a set of unassigned tertiary pointers to the data.

32. The method of claim 31 wherein the first component is a split component, said method further comprising, after the element of passing the set of primary pointers to the split component, passing the set of secondary pointers and the set of tertiary pointers to the split component in order for the split component to split the data.

33. The method of claim 32 further comprising a split method by which the split component splits the data, said split method comprising:

receiving the primary pointers, secondary pointers, and tertiary pointers;

for each row, designating each row as either an alpha row or a omega row based on a criteria for splitting;

for each alpha row, assigning a pointer from the set of secondary pointers to point at each such alpha row;

for each beta row, assigning a pointer from the set of tertiary pointers to point at each such omega row; and

returning the secondary pointers and the tertiary pointers.

34. A method for transforming data comprising:

extracting data from a source, said data comprising n rows wherein n is any positive integer number greater than zero;

writing the data to a buffer;

creating n pointers wherein each pointer uniquely points to a single row of data from among the n rows of data in the buffer;

passing the n pointers to a next transformation object in a path, the next transformation object being the first transformation object on the first pass, the second transformation object on the second pass, and so forth;

enabling the transformation object to transform the data in the buffer, said transformation object directly accessing the data in the buffer via the pointers;

returning to the element of passing the n pointers to the next transformation and proceeding from there if there remains any transformations unexecuted in the path;

reading the data from the buffer; and

loading the data to a destination.

35. A computer-readable medium bearing computer-readable instructions for:

extracting data from at least one external data source;

storing the data in a buffer and establishing a set of primary pointers to the data;

passing the set of primary pointers to the data in the buffer to a first component in order for the first component to transform the data directly in the buffer; and

loading the data from the buffer to at least one external data destination.

36. The computer-readable medium of claim 35 further comprising computer-readable instruction whereby the data extracted from an external data source is a table of data comprising at least one row, and wherein each said row comprising at least one column.

37. The computer-readable medium of claim 36 further comprising computer-readable instruction whereby the set of primary pointers point to the beginning of the rows.

38. The computer-readable medium of claim 37 further comprising computer-readable instruction for, after the element of passing the set of primary pointers to the data in the buffer to a first component in order for the first component to transform the data directly in the buffer, passing the set of primary pointers to the data in the buffer to a second component in order for the second component to transform the data directly in the buffer.

39. The computer-readable medium of claim 37 further comprising computer-readable instruction for, after the element of storing the data in a buffer and establishing a set of primary pointers to the data, establishing a set of unassigned secondary pointers to the data and establishing a set of unassigned tertiary pointers to the data.

40. The computer-readable medium of claim 39 further comprising computer-readable instruction whereby the first component is a split component, said method further comprising, after the element of passing the set of primary pointers to the split component, passing the set of secondary pointers and the set of tertiary pointers to the split component in order for the split component to split the data.

41. The computer-readable medium of claim 40 further comprising computer-readable instruction for a split method by which the split component splits the data, said split method comprising:

receiving the primary pointers, secondary pointers, and tertiary pointers;

for each row, designating each row as either an alpha row or a omega row based on a criteria for splitting;

for each alpha row, assigning a pointer from the set of secondary pointers to point at each such alpha row;

for each beta row, assigning a pointer from the set of tertiary pointers to point at each such omega row; and

returning the secondary pointers and the tertiary pointers.