Computer data distribution architecture connecting an update propagation graph through multiple remote query processors

• US 10,241,965 B1
• Filed: 11/14/2017
• Issued: 03/26/2019
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Deephaven Data Labs, LLC
• Inventors: Caudy, Ryan, Kent, IV, David R., Wright, Charles, Ries, Brian, Teodorescu, Radu
• Primary Examiner(s): Park, Grace
• Application Number:
  US15/813,127
• Time in Patent Office: 497 Days
• Field of Search: 707755
• 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 computer data distribution architecture connecting an update propagation graph through multiple remote query processors.

Claims

1. A computer database system comprising:

one or more processors;

computer readable storage coupled to the one or more processors, the computer readable storage having stored thereon instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;

receiving a query;

parsing the query and in response to said parsing creating a query graph based on the query;

assigning a first sub-graph of the query graph to a first query processor;

assigning a second sub-graph of the query graph to a second query processor, a result of the first sub-graph being an input to the second sub-graph;

creating, at the second query processor, an object to represent a replica of the result of the first sub-graph from the first query processor;

sending a subscription request from the second query processor to the first query processor to receive consistent updates to the result of the first sub-graph;

receiving, at the second query processor, an initial snapshot of the result from the first query processor;

storing the initial snapshot as the replica of the result;

assigning the replica of the result as an input to the second sub-graph at the second query processor;

adding at the first query processor a first listener to the first sub-graph as a dependent of the result;

receiving, at the first listener, an update notification indicating an update to the result;

sending, by the first listener, a notification to the second query processor including an indication of the change to the result and a copy of any changed data;

responsive to receiving the notification at the second query processor, updating the replica of the result and propagating the changes through the second sub-graph at the second query processor; and

determining a current output of the query graph based on an output of the second sub-graph.

2. The computer database system of claim 1, wherein the query graph is a directed acyclic graph.

3. The computer database system of claim 1, wherein the first and second sub-graphs are directed acyclic graphs.

4. The computer database system of claim 1, wherein the update notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.

5. The computer database system of claim 1, wherein the notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.

6. A method comprising:

assigning a first sub-graph of a query graph to a first query processor;

assigning a second sub-graph of the query graph to a second query processor, a result of the first sub-graph being an input to the second sub-graph;

creating, at the second query processor, an object to represent a replica of the result of the first sub-graph from the first query processor;

sending a subscription request from the second query processor to the first query processor to receive consistent updates to the result of the first sub-graph;

assigning the replica of the result as an input to the second sub-graph at the second query processor

adding at the first query processor a first listener to the first sub-graph as a dependent of the result;

receiving, at the first listener, an update notification indicating an update to the result;

sending, by the first listener, a notification to the second query processor including an indication of the change to the result and a copy of any changed data;

responsive to receiving the notification at the second query processor, updating the replica of the result and propagating the changes through the second sub-graph at the second query processor; and

determining a current output of the query graph based on an output of the second sub-graph.

7. The method of claim 6, further comprising:

receiving a query;

parsing the query; and

in response to said parsing, creating the query graph based on the query.

8. The method of claim 6, further comprising:

receiving, at the second query processor, an initial snapshot of the result from the first query processor, the initial snapshot being sent in response to the subscription request; and

storing the initial snapshot as the replica of the result.

9. The method of claim 6, wherein the query graph is a directed acyclic graph.

10. The method of claim 6, wherein the first and second sub-graphs are directed acyclic graphs.

11. The method of claim 6, wherein the update notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.

12. The method of claim 6, wherein the notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.

13. 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:

creating, at the second query processor, an object to represent a replica of the result of the first sub-graph from the first query processor;

sending a subscription request from the second query processor to the first query processor to receive consistent updates to the result of the first sub-graph;

assigning the replica of the result as an input to the second sub-graph at the second query processor

adding at the first query processor a first listener to the first sub-graph as a dependent of the result;

receiving, at the first listener, an update notification indicating an update to the result;

sending, by the first listener, a notification to the second query processor including an indication of the change to the result and a copy of any changed data;

responsive to receiving the notification at the second query processor, updating the replica of the result and propagating the changes through the second sub-graph at the second query processor; and

determining a current output of the query graph based on an output of the second sub-graph.

14. The nontransitory computer readable medium of claim 13, the operations further comprising:

assigning a first sub-graph of a query graph to a first query processor; and

assigning a second sub-graph of the query graph to a second query processor, a result of the first sub-graph being an input to the second sub-graph.

15. The nontransitory computer readable medium of claim 13, the operations further comprising:

receiving a query;

parsing the query; and

in response to said parsing creating the query graph based on the query.

16. The nontransitory computer readable medium of claim 13, the operations further comprising:

receiving, at the second query processor, an initial snapshot of the result from the first query processor, the initial snapshot being sent in response to the subscription request; and

storing the initial snapshot as the replica of the result.

17. The nontransitory computer readable medium of claim 13, wherein the query graph is a directed acyclic graph.

18. The nontransitory computer readable medium of claim 13, wherein the first and second sub-graphs are directed acyclic graphs.

19. The nontransitory computer readable medium of claim 13, wherein the update notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.

20. The nontransitory computer readable medium of claim 13, wherein the notification includes at least one selected from a group consisting of a data add notification, a data modify notification, a data delete notification and a data reindex notification.