Computer data system data source refreshing using an update propagation graph having a merged join listener

• US 10,198,469 B1
• Filed: 11/14/2017
• Issued: 02/05/2019
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Deephaven Data Labs, LLC
• Inventors: Wright, Charles, Caudy, Ryan, Kent, IV, David R., Zeldis, Mark, Basralian, Raffi, Teodorescu, Radu
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US15/813,112
• Time in Patent Office: 448 Days
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2372 Updates performed during offline database operations
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/489 using time information
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Described are methods, systems and computer readable media for data source refreshing using an update propagation graph having a merged join listener.

Claims

1. A system for updating a data object using update propagation graphs and merged join listeners to determine consistent join update processing, the system comprising:

one or more hardware processors coupled to a nontransitory computer readable medium having stored thereon software instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;

receiving a request to perform a join operation on a plurality of objects;

creating an update propagation graph (UPG) for propagating updates to a result of the join operation;

adding a merged join listener to the UPG as a child of the plurality of objects;

adding a join result structure to the UPG as a child of the merged join listener;

propagating updates through the UPG, including the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification and delivering the merged notification to the join result structure'"'"'s node of the UPG during that clock cycle to provide a consistent representation of updates to all sides of the join operation to the join result structure node, the merged join listener combining comprising;

for each current notification received at the merged join listener during the given update clock cycle;

determining whether a priority queue includes an existing notification from the merged notification listener for the given clock cycle, the priority queue comprising a plurality of elements, each of the elements having an associated node of the UPG and an associated priority such that a first element with a first priority is served before a second element with a second priority lower than the first priority, the priority of each of the elements of the priority queue being determined based on an arrangement of nodes within the UPG,

when the priority queue includes an existing notification from the merged notification listener for the given clock cycle, updating, responsive to the determining, the existing notification to include an additional notification based on the current notification, and

when the priority queue does not include an existing notification from the merged notification listener for the given clock cycle, adding a new notification to the priority queue based on the current notification; and

receiving the merged notification at the join result structure node and applying changes to update the result of the join operation in a consistent manner without having to re-execute the full join operation.

2. The system of claim 1, wherein the plurality of objects are tables.

3. The system of claim 2, wherein the join result structure is a table.

4. The system of claim 1, wherein the UPG is a directed acyclic graph (DAG).

5. The system of claim 1, wherein the plurality of objects consists of three or more objects.

6. The system of claim 1, wherein the operations further include adding a second join result structure to the UPG as a second child of the merged join listener.

7. The system of claim 6, wherein the operations further include receiving a second merged notification at the second join result structure'"'"'s node of the UPG.

8. The system of claim 1, wherein the join result structure comprises a plurality of matrices.

9. The system of claim 1, wherein the join operation is an operation selected from a group consisting of an outer join, an inner join, and a cross join.

10. A method comprising:

receiving, at a query processor, a request to perform a join operation on a plurality of objects;

creating, at the query processor, an update propagation graph (UPG) for propagating updates to a result of the join operation;

adding a merged join listener to the UPG as a child of the plurality of objects;

adding a join result to the UPG as a child of the merged join listener;

propagating updates through the UPG, including the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification and delivering the merged notification to the join result'"'"'s node of the UPG during that clock cycle to provide a consistent representation of updates to all sides of the join operation to the join result node, the propagating comprising processing notifications using a priority queue, the priority queue comprising a plurality of elements, each of the elements having an associated node of the UPG and an associated priority such that a first element with a first priority is served before a second element with a second priority lower than the first priority, the priority of each of the elements of the priority queue being determined based on an arrangement of nodes within the UPG; and

receiving the merged notification at the join result node and applying changes to update the result of the join operation in a consistent manner without having to re-execute the full join operation.

11. The method of claim 10, wherein the plurality of objects consists of a plurality of tables.

12. The method of claim 10, wherein the UPG is a directed acyclic graph (DAG).

13. The method of claim 10, wherein the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification comprises:

receiving a notification during the given update clock cycle;

determining that the priority queue includes an existing notification from the merged notification listener for the given clock cycle;

updating, responsive to the determining, the existing notification to include an additional notification based on the received notification.

14. The method of claim 10, wherein the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification comprises:

receiving a notification during the given update clock cycle;

determining that the priority queue does not include an existing notification from the merged notification listener for the given clock cycle; and

adding, responsive to the determining, a new notification from the merged notification listener to the priority queue based on the received notification.

15. The method of claim 14, wherein the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification further comprises:

receiving a second notification during the given update clock cycle;

determining that the priority queue includes an existing notification from the merged notification listener for the given clock cycle, the existing notification being the new notification;

updating, responsive to the determining, the existing notification to include an additional notification based on the second notification.

16. The method of claim 10, further comprising adding a second join result structure to the UPG as a second child of the merged join listener.

17. The method of claim 16, further comprising receiving a second merged notification at the second join result structure'"'"'s node of the UPG.

18. The method of claim 17 wherein the second merged notification is a copy of the merged notification.

19. The method of claim 10, wherein the join result structure comprises a plurality of matrices.

20. The method of claim 10, wherein the join operation is an operation selected from a group consisting of an outer join, an inner join, and a cross join.

21. A nontransitory computer readable medium having stored thereon software instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:

receiving a request to perform a join operation on a plurality of objects;

creating an update propagation graph (UPG) for propagating updates to a result of the join operation;

adding a merged join listener to the UPG as a child of the plurality of objects;

adding a join result structure to the UPG as a child of the merged join listener;

propagating updates through the UPG, including the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification and delivering the merged notification to the join result structure'"'"'s node of the UPG during that clock cycle to provide a consistent representation of updates to all sides of the join operation to the join result structure node, the propagating comprising processing notifications using a priority queue, the priority queue comprising a plurality of elements, each of the elements having an associated node of the UPG and an associated priority such that a first element with a first priority is served before a second element with a second priority lower than the first priority, the priority of each of the elements of the priority queue being determined based on an arrangement of nodes within the UPG; and

receiving the merged notification at the join result structure node and applying changes to update the result of the join operation in a consistent manner without having to re-execute the full join operation.

22. The nontransitory computer readable medium of claim 21, wherein the plurality of objects are tables and the join result structure is a table.

23. The nontransitory computer readable medium of claim 21, wherein the UPG is a directed acyclic graph (DAG).

24. The nontransitory computer readable medium of claim 21, wherein the plurality of objects consists of three or more objects.

25. The nontransitory computer readable medium of claim 21, wherein the operations further include adding a second join result structure to the UPG as a second child of the merged join listener.

26. The nontransitory computer readable medium of claim 21, wherein the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification comprising:

for each current notification received at the merged join listener during the given update clock cycle;

determining whether the priority queue includes an existing notification from the merged notification listener for the given clock cycle,

when the priority queue includes an existing notification from the merged notification listener for the given clock cycle, updating, responsive to the determining, the existing notification to include an additional notification based on the current notification, and

when the priority queue does not include an existing notification from the merged notification listener for the given clock cycle, adding a new notification to the priority queue based on the current notification.

27. The nontransitory computer readable medium of claim 21, wherein the join result structure comprises a plurality of matrices.

28. The nontransitory computer readable medium of claim 21, wherein the join operation is an operation selected from a group consisting of an outer join, an inner join, and a cross join.

29. A system comprising:

one or more hardware processors coupled to a nontransitory computer readable medium having stored thereon software instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;

receiving a request to perform a join operation on a plurality of data sources;

creating an update propagation graph (UPG) for propagating updates to a result of the join operation;

adding a merged join listener to the UPG as a child of the plurality of objects;

adding a join result structure to the UPG as a child of the merged join listener;

propagating updates through the UPG, including the merged join listener combining update notifications from the plurality of objects for a given update clock cycle into a merged notification and delivering the merged notification to the join result structure'"'"'s node of the UPG during that clock cycle to provide a consistent representation of updates to all sides of the join operation to the join result structure node, the propagating comprising processing notifications using a priority queue, the priority queue comprising a plurality of elements, each of the elements having an associated node of the UPG and an associated priority such that a first element with a first priority is served before a second element with a second priority lower than the first priority, the priority of each of the elements of the priority queue being determined based on an arrangement of nodes within the UPG; and

receiving the merged notification at the join result structure node and applying changes to update the result of the join operation in a consistent manner without having to re-execute the full join operation.

30. The system of claim 29, wherein the join operation is an operation selected from a group consisting of an outer join, an inner join, and a cross join.