Dataflow optimization for extractions from a data repository

• US 10,380,136 B2
• Filed: 06/24/2015
• Issued: 08/13/2019
• Est. Priority Date: 10/10/2014
• Status: Active Grant

• Current Assignee: Intel Corporation, Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Zheng, Zuye, Moktali, Amruta, Deshpande, Suyog Anil
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Nafziger, David M
• Application Number:
  US14/749,087
• Publication Number:
  US 20160103898A1
• Time in Patent Office: 1,511 Days
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Dataflow optimization is described for extractions from a data depository. In one example an object-relationship graph of a data extraction definition is traversed in a first pass. The object-relationship graph has a node for each object. The steps from each node of the graph in the first pass is determined. It is determined if any of the determined steps are repeated. A single instance of each repeated step is placed before other steps in a query plan. Data is then extracted in a second pass from the object-oriented database system according to the object-relationship graph by performing the repeated steps first and then reusing the repeated steps in other determined steps.

Claims

1. A method performed by a system, having at least a processor and a memory therein to execute instructions, wherein the method comprises:

operating an object-oriented database system communicatively interfaced with the system and having a plurality of objects stored therein;

retrieving metadata from the object-oriented database system, wherein the retrieved metadata defines an extraction having a plurality of steps to extract data from the object-oriented database system, including one or more repeated steps;

performing a first pass to traverse an object-relationship graph according to the defined extraction, wherein the object-relationship graph includes a node for every object represented within the object-relationship graph;

determining steps from each node of the object-relationship graph in the first pass;

identifying one or more repeated steps within the defined extraction;

modifying the defined extraction to reuse the data extracted from earlier instances of repeated steps by placing a single instance of each repeated step before other steps and then reusing the data from the repeated steps in later repetitions of the repeated steps; and

performing a second pass to extract the data from the object-oriented database system during the second pass according to the extraction defined by the object-relationship graph by performing the repeated steps first to generate the data and then reusing the data extracted from earlier instances of the repeated steps in the other determined steps.

2. The method of claim 1, further comprising removing at least one repeated instance from the one or more repeated steps.

3. The method of claim 1, wherein the object-relationship graph defines relationships, joins and fetches of the extraction.

4. The method of claim 3, further comprising selecting a super set of field objects of the object-relationship graph and using a subset of the selected super set for specific joins in the object-relationship graph.

5. The method of claim 1, wherein the defined extraction comprises sequential steps;

and

wherein results of each step are utilized by at least one of the other determined steps.

6. The method of claim 1, wherein the object-relationship graph defines a data extraction from the object-oriented database system as steps through multiple objects as nodes of the object-relationship graph and through relationships between the nodes through multiple passes.

7. The method of claim 1, further comprising:

traversing the object-relationship graph through multiple passes including at least the first pass and the second pass, wherein the object-relationship graph defines the extraction from the object-oriented database system as a plurality of steps through multiple objects as nodes of the object-relationship graph and through relationships between the nodes;

inserting all shared and identified reusable steps atop the defined extraction; and

reusing the shared and the identified reusable steps in later steps of the defined extraction.

8. The method of claim 1, further comprising performing further optimizations by deduping the object-relationship graph.

9. The method of claim 1:

wherein the object relationship graph defines joins of the data extraction definition; and

wherein the method further comprises selecting a super set of fields from the object-relationship graph and using a subset of the selected super set for specific joins in the graph.

10. Non-transitory computer readable storage media having instructions stored thereupon that, when executed by a processor of a system, the instructions cause the system to perform operations comprising:

operating an object-oriented database system communicatively interfaced with the system and having a plurality of objects stored therein;

retrieving metadata from the object-oriented database system, wherein the retrieved metadata defines an extraction having a plurality of steps to extract data from the object-oriented database system, including one or more repeated steps;

performing a first pass to traverse an object-relationship graph according to the extraction, wherein the object-relationship graph includes a node for every object represented within the object-relationship graph;

determining steps from each node of the object-relationship graph in the first pass;

identifying one or more repeated steps within the defined extraction;

modifying the defined extraction to reuse the data extracted from earlier instances of repeated steps by placing a single instance of each repeated step before other steps and then reusing the data from the repeated steps in later repetitions of the repeated steps; and

performing a second pass to extract the data from the object-oriented database system during the second pass according to the extraction defined by the object-relationship graph by performing the repeated steps first to generate the data and then reusing the data extracted from earlier instances of the repeated steps in the other determined steps.

11. The non-transitory computer readable storage media of claim 10, the operations further comprising removing a repeated instance of the repeated steps.

12. The non-transitory computer readable storage media of claim 10, wherein the object-relationship graph defines relationships, joins and fetches of the data extraction definition.

13. The non-transitory computer readable storage media of claim 12, the operations further comprising selecting a super set of field objects of the object-relationship graph and using a subset of the selected super set for specific joins in the graph.

14. The non-transitory computer readable storage media of claim 10, wherein the data extraction definition comprises sequential steps whereby the results of each step may be used by one or more other determined steps.

15. A system comprising:

a processor and a memory to execute instructions at the system;

a communications interface to an object-oriented database system having a plurality of objects stored therein;

wherein the system is to retrieve metadata from the object-oriented database system, wherein the retrieved metadata defines an extraction having a plurality of steps to extract data from the object-oriented database system, including one or more repeated steps;

wherein the system is to further perform a first pass to traverse an object-relationship graph according to the defined extraction, wherein the object-relationship graph includes a node for every object represented within the object-relationship graph;

wherein the system is to determine steps from each node of the object-relationship graph in the first pass;

wherein the system is to identify one or more repeated steps within the defined extraction;

wherein the system is to further modify the defined extraction to reuse the data extracted from earlier instances of repeated steps by placing a single instance of each repeated step before other steps and then reusing the data from the repeated steps in later repetitions of the repeated steps; and

wherein the system is to further perform a second pass to extract the data from the object-oriented database system during the second pass according to the extraction defined by the object-relationship graph by performing the repeated steps first to generate the data and then reusing the data extracted from earlier instances of the repeated steps in the other determined steps.

16. The system of claim 15, wherein the system is to perform further optimizations by deduping the object-relationship graph.

17. The system of claim 15:

wherein the object-relationship graph defines joins of the data extraction definition; and

wherein the system is further to select a super set of fields from the object-relationship graph and using a subset of the selected super set for specific joins in the graph.