Determining and extracting changed data from a data source

• US 10,180,977 B2
• Filed: 07/26/2016
• Issued: 01/15/2019
• Est. Priority Date: 03/18/2014
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Fisher, William, Maag, Peter
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US15/220,021
• Publication Number:
  US 20160335342A1
• Time in Patent Office: 903 Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

According to certain aspects, a computer system may be configured to obtain information indicating a plurality of groupings of data stored in a data source, the information indicating a number of data items included in each of the plurality of groupings; determine a first grouping of the plurality of groupings including one or more data items that have changed by comparing a first number of data items included in the first grouping and a historical first number of data items included in a corresponding local version of the first grouping; access data items included in the first grouping from the data source; compare the data items included in the first grouping to data items of the corresponding local version of the first grouping to determine which data items have changed; extract the changed data items of the first grouping; and forward the extracted data items to a destination system.

Claims

1. A computer system configured to efficiently determine changed data items in a remote data source, the computer system comprising:

one or more hardware computer processors configured to execute software code stored in a tangible storage device in order to;

determine a quantity of data items included in a group of data items in a remote data source;

compare the quantity of data items included in the group to a quantity of data items included in a previous version of the group to determine a change in the quantity of data items included in the group;

in response to determining the change, compare the data items included in the group to corresponding data items included in a compressed local version of the group to determine which data items of the group have changed; and

based on the comparison, identify the data items of the group that have changed.

2. The system of claim 1, wherein the group of data items is one of a plurality of groupings of data items, wherein the data items of the plurality of groupings are grouped based on timestamps of respective data items, and wherein the timestamps indicate respective times at which data items were last updated.

3. The system of claim 2, wherein the timestamps of the respective data items include a date and a time at which the respective data items were last updated, and wherein the data items of the plurality of groupings are grouped based on only the date of the timestamps of the respective data items.

4. The system of claim 3, wherein each of the plurality of groupings is associated with at least one of:

a different date, or a range of dates.

5. The system of claim 1, wherein the group of data items is one of a plurality of groupings of data items, and wherein the data items of the plurality of groupings are grouped based on a first field of respective data items, the first field configured to provide an uneven distribution of data items included in each of the plurality of groupings.

6. The system of claim 1, wherein the previous version of the group comprises a copy of the data items included in the group at a first time prior to said determining a quantity of data items in the group of data items.

7. The system of claim 1, wherein the one or more hardware computer processors are further configured to execute software code in order to:

in response to determining that the quantity of data items included in the first group is greater than the quantity of data items included in the previous version of the group;

identify the changed data items as added or updated data items; and

forward the changed data items to a destination system to be stored.

8. The system of claim 1, wherein the one or more hardware computer processors are further configured to execute software code in order to:

in response to determining that the quantity of data items included in the first group is less than the quantity of data items included in the previous version of the group;

identify the changed data items as deleted data items; and

forward the changed data items to a destination system to be removed.

9. The system of claim 1, wherein the one or more hardware computer processors are further configured to execute software code in order to:

assign a unique identifier to each of the data items included in the group; and

determine whether a first changed data item is a new data item or an updated data item based on the unique identifier associated with the first changed data item.

10. The system of claim 1, wherein a data item included in the group is a row in a database or a line in a file.

11. The system of claim 1, wherein the one or more hardware computer processors are further configured to execute software code in order to:

obtain the information indicating an update to the group of data items at an interval.

12. The system of claim 1, wherein comparing the data items is performed in response to determining the quantity of data items included in the group is different from the quantity of data items included in the previous version of the group.

13. The computer system of claim 1, wherein comparing the data items included in the group to corresponding data items included in the compressed local version of the group comprises querying the compressed local version of the group.

14. The computer system of claim 1, wherein the compressed local version of the group is a space-efficient probabilistic data structure including information about data items included in the group at a first time prior to said determining a quantity of data items in the group of data items.

15. The computer system of claim 14, wherein the space-efficient probabilistic data structure is configured to determine whether a particular data item included in the group was included in the group at the first time.

16. The computer system of claim 14, wherein the space-efficient probabilistic data structure is a Bloom filter, and wherein the Bloom filter is selected from a plurality of Bloom filters that can each include a different number of data items.

17. The computer system of claim 1, wherein the compressed local version of the group does not comprise a copy of the data items of the group.

18. The computer system of claim 1, wherein the compressed local version of the group and the previous version of the group are the same.

19. A method of efficiently determining changed data items at a remote data source, the method comprising:

determining, by one or more hardware computer processors, a quantity of data items included in a group of data items at a remote data source;

comparing, by the one or more hardware computer processors, the quantity of data items included in the group to a quantity of data items included in a previous version of the group to determine a change in the quantity of data items included in the group;

in response to determining the change, comparing, by the one or more hardware computer processors, the data items included in the group to corresponding data items included in a local version of the group to determine which data items of the group have changed; and

based on the comparison, identifying, by the one or more hardware computer processors, the data items of the group that have changed.

20. The method of claim 19, wherein the group of data items is one of a plurality of groupings of data items, wherein the data items of the plurality of groupings are grouped based on timestamps of respective data items, and wherein the timestamps indicate respective times at which data items were last updated.

21. The method of claim 19, wherein the group of data items is one of a plurality of groupings of data items, and wherein the data items of the plurality of groupings are grouped based on a first field of respective data items, the first field configured to provide an uneven distribution of data items included in each of the plurality of groupings.

22. The method of claim 19, wherein the local version of the group is a compressed version of the group.

23. A non-transitory computer readable medium comprising instructions for efficiently determine changed data items at a remote data source, the instructions configured to cause a computer processor to:

determine a quantity of data items included in a group of data items at a remote data source;

compare the quantity of data items included in the group to a quantity of data items included in a previous version of the group to determine a change in the quantity of data items included in the group;

in response to determining the change, compare the data items included in the group to corresponding data items included in a local version of the group to determine which data items of the group have changed; and

based on the comparison, identify the data items of the group that have changed.