System, method, and computer program product for efficiently joining time-series data tables

Abstract

Described are a system, method, and computer program product for efficiently joining time-series data tables. The method includes loading a first table and a second table into a memory and generating a set of first key-value pairs based on a set of first time-series records and a set of second key-value pairs based on a set of second time-series records. The method also includes sorting the set of first key-value pairs and the set of second key-value pairs. The method further includes interleaving the set of first key-value pairs with the set of second key-value pairs and sequentially matching the sets of time-series records to form a joined table. The method further includes, in response to matching each respective second time-series record with the respective first time-series record, removing the respective second time-series record from the at least one memory.

What is claimed is: 
     
       1. A computer-implemented method comprising:
 loading, with at least one processor, a first table and a second table into at least one memory, the first table comprising a set of first time-series records and the second table comprising a set of second time-series records, each first time-series record of the set of first time-series records comprising a first plurality of attributes, and each second time-series record of the set of second time-series records comprising a second plurality of attributes, wherein a first attribute of the first plurality of attributes is of a target type and a second attribute of the second plurality of attributes is of the target type, and wherein the first plurality of attributes further comprises a respective first time stamp of each first time-series record and the second plurality of attributes further comprises a respective second time stamp of each second time-series record; 
 replicating, with at least one processor, each first time-series record of the set of first time-series records to yield a plurality of identical records for said each first time-series record; 
 generating, with at least one processor, a set of first key-value pairs based on the set of first time-series records of the first table and a set of second key-value pairs based on the set of second time-series records of the second table, wherein each first key-value pair of the set of first key-value pairs comprises, for each first time-series record, a first key based on the first attribute and a first value based on at least one first other attribute of the first plurality of attributes, and wherein each second key-value pair of the set of second key-value pairs comprises, for each second time-series record, a second key based on the second attribute and a second value based on at least one second other attribute of the second plurality of attributes; 
 sorting, with at least one processor, the set of first key-value pairs based on the first key and the respective first time stamp of each first time-series record; 
 sorting, with at least one processor, the set of second key-value pairs based on the second key and the respective second time stamp of each second time-series record; 
 interleaving, with at least one processor, the set of first key-value pairs with the set of second key-value pairs based on the respective first time stamp of each first time-series record and the respective second time stamp of each second time-series record; 
 sequentially matching, with at least one processor, each respective second time-series record with a respective first time-series record based on the second key, the respective second time stamp, the first key, and the respective first time stamp, to form a respective joined record in a joined table, wherein matching each respective second time-series record with the respective first time-series record further comprises:
 randomly matching said each respective second time-series record with one time-series record of the plurality of identical records for said each respective first time-series record; and 
 
 in response to matching each respective second time-series record with the respective first time-series record, removing, with at least one processor, the respective second time-series record from the at least one memory. 
 
     
     
       2. The method of  claim 1 , wherein the matching of each respective second time-series record with a respective first time-series record is carried out on one of a plurality of server nodes, and wherein each node of the plurality of server nodes executes an independent mapper to match a different subset of first time-series records of the set of first time-series records in parallel with each other node of the plurality of server nodes. 
     
     
       3. The method of  claim 2 , wherein at least one of the first table and the second table is skewed, and wherein replicating each first time-series record of the set of first time-series records comprises:
 replicating, each first time-series record of the set of first time-series records a predetermined number of times to yield the plurality of identical records for said each first time-series record, thereby increasing a size of the set of first time-series records in proportion to the predetermined number. 
 
     
     
       4. The method of  claim 3 , wherein the predetermined number of times each first time-series record is replicated is at least ten. 
     
     
       5. The method of  claim 3 , wherein a number of the plurality of identical records is a same number as the plurality of server nodes, wherein each identical record of the plurality of identical records is sent to a different mapper of the plurality of server nodes, and wherein the randomly matching of said each respective second time-series record further comprises randomly selecting a mapper of the plurality of server nodes. 
     
     
       6. The method of  claim 1 , wherein the set of first time-series records comprises a plurality of transaction authorization records processed by a transaction processing system, and wherein the set of second time-series records comprises a plurality of transaction settlement records processed by the transaction processing system. 
     
     
       7. The method of  claim 1 , wherein the removing of each respective second time-series record from the at least one memory occurs in real-time immediately after said each respective second time-series record is matched with the respective first time-series record. 
     
     
       8. A system comprising at least one server comprising at least one processor, wherein the at least one server is programmed or configured to:
 load a first table and a second table into at least one memory, the first table comprising a set of first time-series records and the second table comprising a set of second time-series records, each first time-series record of the set of first time-series records comprising a first plurality of attributes, and each second time-series record of the set of second time-series records comprising a second plurality of attributes, wherein a first attribute of the first plurality of attributes is of a target type and a second attribute of the second plurality of attributes is of the target type, and wherein the first plurality of attributes further comprises a respective first time stamp of each first time-series record and the second plurality of attributes further comprises a respective second time stamp of each second time-series record; 
 replicate each first time-series record of the set of first time-series records to yield a plurality of identical records for said each first time-series record; 
 generate a set of first key-value pairs based on the set of first time-series records of the first table and a set of second key-value pairs based on the set of second time-series records of the second table, wherein each first key-value pair of the set of first key-value pairs comprises, for each first time-series record, a first key based on the first attribute and a first value based on at least one first other attribute of the first plurality of attributes, and wherein each second key-value pair of the set of second key-value pairs comprises, for each second time-series record, a second key based on the second attribute and a second value based on at least one second other attribute of the second plurality of attributes; 
 sort the set of first key-value pairs based on the first key and the respective first time stamp of each first time-series record; 
 sort the set of second key-value pairs based on the second key and the respective second time stamp of each second time-series record; 
 interleave the set of first key-value pairs with the set of second key-value pairs based on the respective first time stamp of each first time-series record and the respective second time stamp of each second time-series record; 
 sequentially match each respective second time-series record with a respective first time-series record based on the second key, the respective second time stamp, the first key, and the respective first time stamp, to form a respective joined record in a joined table, wherein, while matching each respective second time-series record with the respective first time-series record, the at least one server is programmed or configured to:
 randomly match said each respective second time-series record with one time-series record of the plurality of identical records for said each respective first time-series record; and 
 
 in response to matching each respective second time-series record with the respective first time-series record, remove the respective second time-series record from the at least one memory. 
 
     
     
       9. The system of  claim 8 , wherein the at least one server comprises a plurality of server nodes, wherein matching each respective second time-series record with a respective first time-series record is carried out on one of the plurality of server nodes, and wherein each node of the plurality of server nodes executes an independent mapper to match a different subset of first time-series records of the set of first time-series records in parallel with each other node of the plurality of server nodes. 
     
     
       10. The system of  claim 9 , wherein at least one of the first table and the second table is skewed, and wherein, while replicating each first time-series record of the set of first time-series records, the at least one server is further programmed or configured to:
 replicate each first time-series record of the set of first time-series records a predetermined number of times to yield the plurality of identical records for said each first time-series record, thereby increasing a size of the set of first time-series records in proportion to the predetermined number. 
 
     
     
       11. The system of  claim 10 , wherein the predetermined number of times each first time-series record is replicated is at least ten. 
     
     
       12. The system of  claim 10 , wherein a number of the plurality of identical records is a same number as the plurality of server nodes, wherein each identical record of the plurality of identical records is sent to a different mapper of the plurality of server nodes, and wherein the randomly matching of said each respective second time-series record further comprises randomly selecting a mapper of the plurality of server nodes. 
     
     
       13. The system of  claim 8 , wherein the at least one server is part of a transaction processing system, wherein the set of first time-series records comprises a plurality of transaction authorization records processed by the transaction processing system, and wherein the set of second time-series records comprises a plurality of transaction settlement records processed by the transaction processing system. 
     
     
       14. The system of  claim 8 , wherein removing each respective second time-series record from the at least one memory occurs in real-time immediately after said each respective second time-series record is matched with the respective first time-series record. 
     
     
       15. A computer program product comprising at least one non-transitory computer-readable medium including program instructions that, when executed by at least one processor, cause the at least one processor to:
 load a first table and a second table into at least one memory, the first table comprising a set of first time-series records and the second table comprising a set of second time-series records, each first time-series record of the set of first time-series records comprising a first plurality of attributes, and each second time-series record of the set of second time-series records comprising a second plurality of attributes, wherein a first attribute of the first plurality of attributes is of a target type and a second attribute of the second plurality of attributes is of the target type, and wherein the first plurality of attributes further comprises a respective first time stamp of each first time-series record and the second plurality of attributes further comprises a respective second time stamp of each second time-series record; 
 replicate each first time-series record of the set of first time-series records to yield a plurality of identical records for said each first time-series record; 
 generate a set of first key-value pairs based on the set of first time-series records of the first table and a set of second key-value pairs based on the set of second time-series records of the second table, wherein each first key-value pair of the set of first key-value pairs comprises, for each first time-series record, a first key based on the first attribute and a first value based on at least one first other attribute of the first plurality of attributes, and wherein each second key-value pair of the set of second key-value pairs comprises, for each second time-series record, a second key based on the second attribute and a second value based on at least one second other attribute of the second plurality of attributes; 
 sort the set of first key-value pairs based on the first key and the respective first time stamp of each first time-series record; 
 sort the set of second key-value pairs based on the second key and the respective second time stamp of each second time-series record; 
 interleave the set of first key-value pairs with the set of second key-value pairs based on the respective first time stamp of each first time-series record and the respective second time stamp of each second time-series record; 
 sequentially match each respective second time-series record with a respective first time-series record based on the second key, the respective second time stamp, the first key, and the respective first time stamp, to form a respective joined record in a joined table, wherein the program instructions that cause the at least one processor to match each respective second time-series record with the respective first time-series record cause the at least one processor to:
 randomly match said each respective second time-series record with one time-series record of the plurality of identical records for said each respective first time-series record; and 
 
 in response to matching each respective second time-series record with the respective first time-series record, remove the respective second time-series record from the at least one memory. 
 
     
     
       16. The computer program product of  claim 15 , wherein the at least one processor comprises a plurality of server nodes, wherein matching each respective second time-series record with a respective first time-series record is carried out on one of the plurality of server nodes, and wherein each node of the plurality of server nodes executes an independent mapper to match a different subset of first time-series records of the set of first time-series records in parallel with each other node of the plurality of server nodes. 
     
     
       17. The computer program product of  claim 16 , wherein at least one of the first table and the second table is skewed, and wherein the program instructions that cause the at least one processor to replicate each first time-series record of the set of first time-series records further cause the at least one processor to:
 replicate each first time-series record of the set of first time-series records a predetermined number of times to yield the plurality of identical records for said each first time-series record, thereby increasing a size of the set of first time-series records in proportion to the predetermined number. 
 
     
     
       18. The computer program product of  claim 17 , wherein the predetermined number of times each first time-series record is replicated is at least ten. 
     
     
       19. The computer program product of  claim 17 , wherein a number of the plurality of identical records is a same number as the plurality of server nodes, wherein each identical record of the plurality of identical records is sent to a different mapper of the plurality of server nodes, and wherein the randomly matching of said each respective second time-series record further comprises randomly selecting a mapper of the plurality of server nodes. 
     
     
       20. The computer program product of  claim 15 , wherein removing each respective second time-series record from the at least one memory occurs in real-time immediately after said each respective second time-series record is matched with the respective first time-series record.