Computer system for join processing

• US 10,565,194 B2
• Filed: 03/16/2018
• Issued: 02/18/2020
• Est. Priority Date: 05/14/2015
• 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): Tran, Anhtai V
• Application Number:
  US15/923,736
• Publication Number:
  US 20180203889A1
• Time in Patent Office: 704 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/144 Query formulation
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2291 : User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/23 : Updating
• CPC Class Codes: G06F 16/2308 : Concurrency control transaction processing G06F9/466
• 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/2379 : Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/242 : Query formulation
• CPC Class Codes: G06F 16/2428 : Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/245 : Query processing
• CPC Class Codes: G06F 16/2453 : Query optimisation
• CPC Class Codes: G06F 16/24534 : Query rewriting; Transformation
• CPC Class Codes: G06F 16/24535 : of sub-queries or views
• CPC Class Codes: G06F 16/24537 : of operators
• CPC Class Codes: G06F 16/24539 : using cached or materialised query results
• CPC Class Codes: G06F 16/2455 : Query execution
• CPC Class Codes: G06F 16/24553 : of query operations
• CPC Class Codes: G06F 16/2456 : Join operations
• CPC Class Codes: G06F 16/24561 : Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2457 : with adaptation to user needs
• CPC Class Codes: G06F 16/24575 : using context
• CPC Class Codes: G06F 16/248 : Presentation of query results
• 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/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/278 : Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 : Clustering or classification
• CPC Class Codes: G06F 16/9024 : Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/907 : Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 : Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 : Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 : Presentation of query results
• CPC Class Codes: G06F 16/9566 : URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 16/9574 : of access to content, e.g. by caching
• CPC Class Codes: G06F 17/40 : Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 21/00 : Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06F 21/6209 : to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2201/805 : Real-time
• CPC Class Codes: G06F 2201/84 : Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1052 : Security improvement
• CPC Class Codes: G06F 2212/154 : Networked environment
• CPC Class Codes: G06F 2212/163 : Server or database system
• CPC Class Codes: G06F 2212/60 : Details of cache memory
• 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: G06F 3/0482 : Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0483 : Interaction with page-structured environments, e.g. book metaphor
• CPC Class Codes: G06F 3/04847 : Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 3/0485 : Scrolling or panning
• CPC Class Codes: G06F 3/04895 : Guidance during keyboard input operation, e.g. prompting
• CPC Class Codes: G06F 3/0605 : by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 40/117 : Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/134 : Hyperlinking
• CPC Class Codes: G06F 40/166 : Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/174 : Form filling; Merging
• CPC Class Codes: G06F 40/177 : of tables; using ruled lines
• CPC Class Codes: G06F 40/18 : of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/183 : Tabulation, i.e. one-dimensional positioning
• CPC Class Codes: G06F 40/216 : using statistical methods
• CPC Class Codes: G06F 40/274 : Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 8/30 : Creation or generation of source code
• CPC Class Codes: G06F 8/41 : Compilation
• CPC Class Codes: G06F 8/427 : Parsing
• CPC Class Codes: G06F 8/60 : Software deployment
• CPC Class Codes: G06Q 40/04 : Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 12/18 : for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 51/046 : Interoperability with other network applications or services
• CPC Class Codes: H04L 51/212 : using filtering or selective blocking
• CPC Class Codes: H04L 61/5069 : for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• CPC Class Codes: H04L 63/102 : Entity profiles
• CPC Class Codes: H04L 67/01 : Protocols
• CPC Class Codes: H04L 67/1001 : for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/141 : Setup of application sessions admission control or resource allocation in data switching networks H04L47/70
• CPC Class Codes: H04L 67/34 : involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 67/56 : Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/566 : Grouping or aggregating service requests, e.g. for unified processing
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5681 : Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

Described are methods, systems and computer readable media for dynamically updating join operation results in a computer system. A memory-efficient computer system for dynamically updating join operation results may include multiple memory devices having different access times. A computer system for dynamically updating join operation results in real time may re-apply a join operation based on a communication received over a network interface device.

Claims

1. A memory-efficient computer system for dynamically updating join operation results, the system comprising:

a processor;

a first memory device electronically storing at least a portion of a first original table;

a second memory device electronically storing at least a portion of a second original table;

a third memory device electronically storing a join results index resulting from a join operation performed on the first and second original tables;

a notification listener device associated with the join results index in the third memory device;

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

listening, using the notification listener device, for changes to the first and second original tables;

notifying the notification listener device of a change to one or both of the first and second original tables; and

in response to the notification listener device receiving notification of a change to one or both of the first and second original tables, re-applying the join operation to changed portions of the first and second original tables.

2. The computer system of claim 1, wherein:

the join operation is a left_join resulting in a table that has one column for each of a plurality of columns in a first input table'"'"'s columns, and one or more new corresponding second input table columns, the one or more new columns containing an aggregation of values from the second input table that match a join criteria, and types of newly created second input table columns not involved in the join criteria being an array of the second input table'"'"'s column type.

3. The computer system of claim 1, wherein:

the join operation is an as_of_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns, the one or more new columns containing values from the input table that match a join criteria, the join criteria performing an exact match on match columns except for one last match column of the match columns followed by performing a closest-less-than match on the last match column.

4. The computer system of claim 1, wherein:

the join operation is a reverse_as_of_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns, the one or more new columns containing values from the input table that match a join criteria, the join criteria performing an exact match on match columns except for one last match column of the match columns followed by performing a closest-greater-than match on the last match column.

5. The computer system of claim 1, wherein the join operation is a range_as_of_join resulting in a table that has one column for each of a plurality of columns in a first input table'"'"'s columns and one or more new corresponding second input table columns, the one or more new columns containing values from the second input table that match a join criteria, the join criteria returning each cell in the one or more new columns with an array of values within a designated range for match columns except for M match columns of the match columns where the match is exact, and the M match columns define a range match.

6. The computer system of claim 1, wherein:

the join operation is a natural_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns, and one or more new corresponding input table columns, the table having a same number of rows as the source table, the same number of rows containing an original content of the source table rows, and the one or more new columns determined by matching one or more values from the input table with the source table.

7. The computer system of claim 1,

wherein the join operation is an exact_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns,

the table having a same number of rows as the source table, the same number of rows containing an original content of the source table rows,

the one or more new columns determined by matching one or more values from the input table with the source table, and

the table containing exactly one match for each row with the input table.

8. The computer system of claim 1, wherein:

the join operation creates a subset filtered by a match criteria on a full Cartesian product, resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns.

9. The computer system of claim 1, wherein the changes include one or more of an add, modify, delete, or re-index.

25. The computer system of claim 1, wherein the reapplying is only applied to changed portions of the original tables and not to unchanged portions.

26. The computer system of claim 1, wherein the first and second original tables store data in strict order.

28. The computer system of claim 26, wherein the strict order is determined by timestamps.

34. The computer system of claim 1, wherein the notification listener device receives the notification of the change during a clock cycle, and the re-applying is performed during that same clock cycle.

35. The computer system of claim 2, wherein said array is able to reference multiple values.

36. The computer system of claim 5, wherein said each cell is able to reference multiple values.

10. A computer system for updating join operation results, the system comprising:

a processor;

a first memory device electronically storing at least a portion of a first original table;

a second memory device electronically storing at least a portion of a second original table;

a third memory device electronically storing a join results index resulting from a join operation performed on the first and second original tables;

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

responsive to receiving a communication over a network interface device during a clock cycle, re-applying the join operation during the clock cycle.

11. The computer system of claim 10, wherein the reapplying is applied to changed portions of the original tables and not to unchanged portions.

12. The computer system of claim 10, wherein:

the join operation is a left_join resulting in a table that has one column for each of a plurality of columns in a first input table'"'"'s columns, and one or more new corresponding second input table columns, the one or more new columns containing an aggregation of values from the second input table that match a join criteria, and types of newly created second input table columns not involved in the join criteria being an array of the second input table'"'"'s column type.

13. The computer system of claim 10, wherein:

the join operation is an as_of_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns, the one or more new columns containing values from the input table that match a join criteria, the join criteria performing an exact match on match columns except for one last match column of the match columns followed by performing a closest-less-than match on the last match column.

14. The computer system of claim 10, wherein:

the join operation is a reverse_as_of_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns, the one or more new columns containing values from the input table that match a join criteria, the join criteria performing an exact match on match columns except for one last match column of the match columns followed by performing a closest-greater-than match on the last match column.

15. The computer system of claim 10, wherein the join operation is a range_as_of_join resulting in a table that has one column for each of a plurality of columns in a first input table'"'"'s columns and one or more new corresponding second input table columns, the one or more new columns containing values from the second input table that match a join criteria, the join criteria returning each cell in the one or more new columns with an array of values within a designated range for match columns except for M match columns of the match columns where the match is exact, and the M match columns define a range match.

16. The computer system of claim 10, wherein:

the join operation is a natural_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns, and one or more new corresponding input table columns, the table having a same number of rows as the source table, the same number of rows containing an original content of the source table rows, and the one or more new columns determined by matching one or more values from the input table with the source table.

17. The computer system of claim 10,

wherein the join operation is an exact_join resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns,

the table having a same number of rows as the source table, the same number of rows containing an original content of the source table rows,

the one or more new columns determined by matching one or more values from the input table with the source table, and

the table containing exactly one match for each row with the input table.

18. The computer system of claim 10, wherein:

the join operation creates a subset filtered by a match criteria on a full Cartesian product, resulting in a table that has one column for each of a plurality of columns in an input table'"'"'s columns and one or more new corresponding input table columns.

19. The computer system of claim 10, wherein the communication calls for one or more of an add, modify, delete, or re-index.

20. The computer system of claim 10, wherein the clock cycle is a logical clock cycle.

21. The computer system of claim 10, wherein the clock cycle lasts no more than one second.

22. The computer system of claim 10, wherein the clock cycle comprises multiple processor clock cycles.

23. The computer system of claim 10, wherein the third memory device providing faster access than that provided by each of the first and second memory devices.

24. The computer system of claim 10, wherein the first memory device is different than the second memory device.

27. The computer system of claim 10, wherein the first and second original tables store data in strict order.

29. The computer system of claim 27, wherein the strict order is determined by timestamps.

30. The computer system of claim 10, wherein the join operation is re-applied directly to data received over the network interface device, without first storing the received data in a memory device providing slower access than that provided by the third memory device.

37. The computer system of claim 12, wherein said array is able to reference multiple values.

38. The computer system of claim 15, wherein said each cell is able to reference multiple values.

31. A computer system comprising:

a processor;

a memory device electronically storing a join results index resulting from a join operation performed on a first original table and a second original table; and

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

associating one merged notification listener with both the first and second original tables;

listening, using the merged notification listener, for changes to the first original table and for changes to the second original table;

receiving, at the merged notification listener, a change notification comprising a change to the first original table or the second original table; and

after receiving the change notification, re-applying the join operation by executing the join operation on the change to the first or second original table received over the network interface device.

32. The computer system of claim 31, wherein the first and second original tables store data in strict order determined by timestamps.

33. The computer system of claim 31, wherein the memory device is different than the computer readable storage.

39. The computer system of claim 31, wherein the join operation is a range_as_of_join resulting in a table that has one column for each of a plurality of columns in a first input table'"'"'s columns and one or more new array-typed corresponding second input table columns, the one or more new array-typed columns containing all values from the second input table that match a join criteria, the join criteria returning each cell in the one or more new array-typed columns with an array of values within a designated range for all match columns except for M match columns of the match columns where the match is exact, and the M match columns define a range match.

40. The computer system of claim 39, wherein said each cell is able to reference multiple values.