Computer data system data source refreshing using an update propagation graph
Described are methods, systems and computer readable media for data source refreshing.
1. A system for updating a plurality of data objects using an update propagation graph, 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, at a remote query processor, a first query from a client, the first query referencing the plurality of data objects including one or more data sources;
determining dependencies between the plurality of data objects in the first query;
converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory;
updating connectivity within the DAG based on execution of second code;
generating the update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the plurality of data objects, the UPG having a structure representing the dependencies between the plurality of data objects in the first query, wherein a sequence in which the UPG is generated is recorded;
updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and
after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the sequence determines the order in which the plurality of nodes in the UPG are processed,
wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node,
wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs,
wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received,
wherein the dynamic node includes a timer that triggers an event based on time intervals,
wherein the static node includes a node of the DAG that does not update,
wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and
wherein a priority of the event in the priority queue is based on a position of the DAG, and
wherein the internal node includes an interior node of the DAG.
2. The system of claim 1 , wherein the data sources include one or more of market data, system generated data, historical data, user input data from a remote user table server, and tables programmatically generated in-memory.
3. The system of claim 1 , wherein the data sources include correlation matrices, linear algebra structures, PDE solvers, non-matrix data structures, non-table data structures and mathematical data structures.
4. The system of claim 3 , wherein the data sources include a singular value decomposition of another data source.
5. The system of claim 1 , wherein the operations further include permitting a program to listen to changes from one or more of the plurality of nodes representing one of one or more of the plurality of data objects or an internal node of the UPG.
6. The system of claim 1 , wherein the DAG uses garbage collection to determine whether a part of the DAG should be deleted, wherein upstream links from a node in the DAG have hard links, and downstream links from the node in the DAG have weak links, so that child nodes prevent parent nodes from being garbage collected, and the parent nodes permit the child nodes to be garbage collected.
7. A method for updating one or more data objects using an update propagation graph, the method comprising:
receiving, at a remote query processor, a first query from a client, the first query referencing the one or more data objects including one or more data sources;
determining dependencies between the one or more data objects in the first query;
converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory;
updating connectivity within the DAG based on execution of second code;
generating an update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the one or more data objects, the UPG having a structure representing the dependencies between the one or more data objects in the first query, wherein a sequence in which the UPG is generated is recorded;
updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and
after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the one or more changes include one or more of addition to, modification of, deletion from or re-indexing of at least part of the one or more data objects,
wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node,
wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs,
wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received,
wherein the dynamic node includes a timer that triggers an event based on time intervals,
wherein the static node includes a node of the DAG that does not update,
wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and
wherein a priority of the event in the priority queue is based on a position of the DAG, and
wherein the internal node includes an interior node of the DAG.
8. The method of claim 7 , wherein the data sources include one or more of market data, system generated data, historical data, user input data from a remote user table server, and tables programmatically generated in-memory.
9. The method of claim 7 , wherein the data sources include correlation matrices, linear algebra structures, PDE solvers, non-matrix data structures, non-table data structures and mathematical data structures.
10. The method of claim 9 , wherein the data sources include a singular value decomposition of another data source.
11. The method of claim 7 , further comprising permitting a program to listen to changes from one or more of the plurality of nodes representing one of one or more of the one or more data objects or an internal node of the UPG.
12. The method of claim 7 , wherein the DAG uses garbage collection to determine whether a part of the DAG should be deleted, wherein upstream links from a node in the DAG have hard links, and downstream links from the node in the DAG have weak links, so that child nodes prevent parent nodes from being garbage collected, and the parent nodes permit the child nodes to be garbage collected.
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:
receiving, at a remote query processor, a first query from a client, the first query referencing one or more data objects including one or more data sources;
determining dependencies between the one or more data objects in the first query;
converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory;
updating connectivity within the DAG based on execution of second code;
generating an update propagation graph (UPG) in a context of the remote query processor based on the first query and the DAG, the UPG having a plurality of nodes each corresponding to one of the one or more data objects, the UPG having a structure representing the dependencies between the one or more data objects in the first query, wherein a sequence in which the UPG is generated is recorded;
updating the structure of the UPG in response to a second query being executed by the remote query processor, wherein the sequence in which the UPG is updated is recorded; and
after the updating, processing one or more changes according to an order determined by the updated UPG, wherein the sequence determines the order in which the plurality of nodes in the UPG are processed, and wherein the one or more changes include one or more of addition to, modification of, deletion from or re-indexing of at least part of the one or more data objects, and wherein information about the addition, the deletion, and the modification from an upstream node is used to compute changes to downstream nodes,
wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node,
wherein each of the dynamic node, the static node, or the internal node has one or more of input dynamic nodes, input static nodes or input internal nodes as inputs,
wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received,
wherein the dynamic node includes a timer that triggers an event based on time intervals,
wherein the static node includes a node of the DAG that does not update,
wherein the internal node includes a listener node with associated listener monitoring code that places additional events into a priority queue of the DAG, and
wherein a priority of the event in the priority queue is based on a position of the DAG, and
wherein the internal node includes an interior node of the DAG.
14. The nontransitory computer readable medium of claim 13 , wherein the data sources include one or more of market data, system generated data, historical data, user input data from a remote user table server, and tables programmatically generated in-memory.
15. The nontransitory computer readable medium of claim 13 , wherein the operations further include:
converting first code into in-memory data structures configured to hold a directed acyclic graph (DAG) structure in memory; and
updating connectivity within the DAG based on execution of second code.
16. The nontransitory computer readable medium of claim 15 , wherein the DAG is comprised of one or more of a dynamic node, a static node, or an internal node,
wherein the DAG comprises one or more of static subgraphs or dynamic subgraphs,
wherein the dynamic node includes a node of the DAG that updates as previously presented data corresponding to the dynamic node is received,
wherein the dynamic node is a timer that triggers an event based on time intervals,
wherein the static node includes a node of the DAG that does not update, and
wherein the internal node includes an interior node of the DAG.