DATA PRUNING BASED ON METADATA

• US 20180018343A1
• Filed: 07/14/2016
• Published: 01/18/2018
• Est. Priority Date: 07/14/2016
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: Snowflake Computing Inc. (Snowflake, Inc.)
• Inventors: Zukowski, Marcin, Dageville, Benoit, Cruanes, Thierry, Motivata, Ashish
• Granted Patent: US 10,437,780 B2
• Time in Patent Office: Days
• 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/24544 Join order optimisation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A system, apparatus, and method for processing queries wherein the query includes a request to access or delete data and accessing metadata associated with the set of data, the metadata defining data characteristics of the set of data and identifying at least sets of data that need or not need to be accessed or deleted based on the metadata without accessing the actual data in the set of data; also methods to optimize processing of some operations based on the collected metadata on data.

Claims

1. A method for managing query operations in a computer system having file sets stored in computer accessible storage comprising:

receiving a query directed to a set of files comprising data, wherein the query comprises a plurality of predicates;

determining whether data in each file match at least one predicate of the plurality of predicates based on file metadata without accessing the set of files;

removing files that do not match at least one predicate from the set of files to create a reduced set of files;

identifying, based on the metadata, one or more predicates of the query that do not fully match any file in the set of files without accessing the set of files;

removing the one or more predicates that do not fully match any file in the set of files from the query to create a modified query;

executing the modified query against the reduced set of files to create a final set of files; and

returning the final set of files in response to the query.

2. The method of claim 1, wherein the method further comprises, based on the metadata, one or more of the following:

identifying, without accessing a set of files, zero or more files in the set of files that do not need to be analyzed for a given query;

identifying, without accessing a set of files, zero or more files in the set of files that need to be analyzed for a given query; and

identifying, without accessing a set of files, zero or more files in the set of files to fully delete.

3. The method of claim 2, wherein the method further comprises:

analyzing queries with a plurality of conjunctive predicates;

checking each of the plurality of conjunctive predicates against each file in the set of files; and

reducing the set of files for consideration for each of the plurality of conjunctive predicates by removing the files that did not match the previous predicate.

4. The method of claim 2, wherein determining whether any of the files do not fully match at least one of the plurality of predicates comprises determining whether at least one of the plurality of predicates defines a range of values not represented in data within the set of files.

5. The method of claim 1, wherein the method further comprises identifying one or more columns within one or more files of the reduced set of files that are only used in predicates that have been deleted.

6. The method of claim 1, wherein receiving a query directed to a set of files further comprises receiving a request to delete tuples in the query.

7. The method of claim 6, wherein the method further comprises identifying files wherein all tuples in the identified files match a delete predicate based on the metadata and deleting the identified files without accessing data from the actual file.

8. The method of claim 7, wherein deleting is performed during query preparation phase.

9. The method of claim 1, wherein the method further comprises identifying files wherein all tuples in the identified files match a delete predicate based on the metadata and deleting the identified files without accessing data from the actual file.

10. The method of claim 2, wherein the method further comprises receiving a join query wherein the join query comprises one or more relations between a first set of files and a second set of files, and at least one predicate on the first set of files.

11. The method of claim 10, wherein the method further comprises deriving a new predicate on the second set of files from the predicate on the first set of files.

12. The method of claim 11, wherein the method further comprises a revising module that is configured to derive a revised predicate from a range found in metadata corresponding to a first relation and wherein the derived predicate is used for filtering the second set of files.

13. The method of claim 1, wherein the method further comprises determining a range of characters based on the metadata and selecting one or more string operations based on the range of characters.

14. The method of claim 13, wherein selecting the one or more string operations comprises selecting one or more of an ASCII specific string operation and a UNICODE specific string operation.

15. The method of claim 1, wherein the method further comprises deriving the metadata for complex functions based on the metadata for a set of base attributes in a data set and filtering the set of files using complex predicates with arbitrary functions.

16. The method of claim 1, wherein the metadata comprises a number of distinct values;

a number of null values; and

a minimum value and a maximum value for each file.

17. The method of claim 16, wherein the metadata also comprises string length information and ranges of characters in strings.

18. The method of claim 1, wherein the method further comprises:

creating one or more files comprising the metadata;

collecting the metadata when there are changes made to the data on a per column and a per file basis during data ingestion or as a separate process after data is loaded;

receiving the metadata on a per column and a per file basis; and

storing the metadata in a metadata store.

19. A networked computer system having processors, memory, and storage for processing and storing distributed sets of digital files that are distributed over a plurality of storages, wherein computer executable instructions for query operations cause the computer hardware perform the instructions, the system comprising:

a receiving module configured to receive a query directed to a set of files wherein the query comprises a plurality of predicates;

a metadata module configured to access metadata associated with the set of files, determine whether data in each file match at least one predicate of the plurality of predicates based on the file metadata without accessing the set of files, and remove files that do not match at least one predicate from the set of files to create a reduced set of files;

a comparison module configured to identify, based on the metadata, one or more predicates of the query that do not fully match any file in the set of files without accessing the set of files; and

a modification module configured to remove the one or more predicates that do not fully match any file in the set of files from the query to create a modified query.

20. The system of claim 19, wherein the modification module is further configured to determine whether at least one of the plurality of predicates defines a range of values that is not contained in data within the set of files.

21. The system of claim 19, further comprising the modification module being configured to derive a revised predicate from a range found in metadata corresponding to a first relation and wherein the revised predicate is used for filtering a second relation.

22. The system of claim 19, wherein the metadata module is configured to perform one or more of the following based on the metadata:

identify, without accessing a set of files, zero or more files in the set of files that do not need to be analyzed for a given query;

identify, without accessing a set of files, zero or more files in the set of files that need to be analyzed for a given query; and

identify, without accessing a set of files, zero or more files in the set of files to fully delete.

23. The system of claim 22, wherein the metadata module is further configured to:

analyze queries with a plurality of conjunctive predicates;

check each of the plurality of conjunctive predicates against each file in the set of files; and

reduce the set of files for consideration for each of the plurality of conjunctive predicates by removing the files that did not match the previous predicate.

24. The system of claim 22, wherein the metadata module is further configured to determine whether at least one of the plurality of predicates defines a range of values not represented in data within the set of files.

25. The system of claim 19, wherein the metadata module is configured to identify one or more columns within one or more files of the reduced set of files that are only used in predicates that have been deleted.

26. The system of claim 19, wherein the receiving module is further configured to receive a request to delete tuples in the query.

27. The system of claim 26, wherein the metadata module is configured to identify files wherein all tuples in the identified files match a delete predicate based on the metadata and delete the identified files without accessing data from the actual file.

28. The system of claim 27, wherein deleting is performed during query preparation phase.

29. The system of claim 19, wherein the metadata module is configured to identify files wherein all tuples in the identified files match a delete predicate based on the metadata and delete the identified files without accessing data from the actual file.

30. The system of claim 22, wherein the receiving module is further configured to receive a join query wherein the join query comprises one or more relations between a first set of files and a second set of files, and at least one predicate on the first set of files.

31. The system of claim 30, wherein the modification module is configured to derive a new predicate on the second set of files from the predicate on the first set of files.

32. The system of claim 19, wherein the metadata module is configured to determine a range of characters based on the metadata and select one or more string operations based on the range of characters.

33. The system of claim 32, wherein selecting the one or more string operations comprises selecting one or more of an ASCII specific string operation and a UNICODE specific string operation.

34. The system of claim 19, wherein the metadata module is configured to derive the metadata for complex functions based on the metadata for a set of base attributes in a data set and filtering the set of files using complex predicates with arbitrary functions.

35. The system of claim 19, wherein the metadata comprises a number of distinct values;

a number of null values; and

a minimum value and a maximum value for each file.

36. The system of claim 35, wherein the metadata also comprises string length information and ranges of characters in strings.

37. The system of claim 19, wherein the metadata module:

creates one or more files comprising the metadata;

collects the metadata when there are changes made to the data on a per column and a per file basis during data ingestion or as a separate process after data is loaded;

receives the metadata on a per column and a per file basis; and

stores the metadata in a metadata store.

38. An apparatus comprising:

a means for receiving a query directed to a set of files wherein the query comprises a plurality of predicates for defining data;

a means for accessing metadata associated with the set of files, determining whether data in each file match at least one predicate of the plurality of predicates based on the file metadata without accessing the set of files, and removing files that do not match at least one predicate from the set of files to create a reduced set of files;

a modification means for identifying, based on the metadata, one or more predicates of the query that do not fully match any file in the set of files without accessing the set of files;

the modification means further for removing the one or more predicates that do not fully match any file in the set of files from the query to create a modified query.

39. The apparatus of claim 38, wherein the metadata further defines string length information and ranges of characters in strings.

40. The apparatus of claim 38, wherein the means for removing the one or more predicates that do not fully match any file in the set of files from the query to create a modified query comprises means for determining whether at least one of the plurality of predicates defines a range of values that is not contained in data within the set of files.

41. The apparatus of claim 38, further comprising means for executing the revised query on the set of files.

42. The apparatus of claim 38, wherein the modification means further derives a revised plurality of predicates for defining data from a range found in metadata corresponding to a first relation and wherein the revised plurality of predicates for defining data is used for filtering a second relation.

43. The apparatus of claim 38, wherein the apparatus further comprises means for identifying, without accessing a set of files, zero or more files in the set of files that do not need to be analyzed for a given query;

means for identifying, without accessing a set of files, zero or more files in the set of files that need to be analyzed for a given query; and

means for identifying, without accessing a set of files, zero or more files in the set of files to fully delete.

44. The apparatus of claim 43, wherein the apparatus further comprises:

means for analyzing queries with a plurality of conjunctive predicates;

means for checking each of the plurality of conjunctive predicates against each file in the set of files; and

means for reducing the set of files for consideration for each of the plurality of conjunctive predicates by removing the files that did not match the previous predicate.

45. The apparatus of claim 43, wherein the apparatus further comprises means for determining whether at least one of the plurality of predicates defines a range of values not represented in data within the set of files.

46. The apparatus of claim 38, wherein the apparatus further comprises a means for identifying one or more columns within one or more files of the reduced set of files that are only used in predicates that have been deleted.

47. The apparatus of claim 38, wherein the means for receiving a query is further configured to receive a request to delete tuples in the query.

48. The apparatus of claim 47, wherein the apparatus further comprises a means for identifying files wherein all tuples in the identified files match a delete predicate based on the metadata and deleting the identified files without accessing data from the actual file.

49. The apparatus of claim 48, wherein deleting is performed during query preparation phase.

50. The apparatus of claim 38, wherein the apparatus further comprises a means for identifying files wherein all tuples in the identified files match a delete predicate based on the metadata and deleting the identified files without accessing data from the actual file.

51. The apparatus of claim 43, wherein the means for receiving a query comprises receiving a join query wherein the join query comprises one or more relations between a first set of files and a second set of files, and at least one predicate on the first set of files.

52. The apparatus of claim 51, wherein the apparatus further comprises a means for deriving a new predicate on the second set of files from the predicate on the first set of files.

53. The apparatus of claim 38, wherein the apparatus further comprises a means for determining a range of characters based on the metadata and selecting one or more string operations based on the range of characters.

54. The apparatus of claim 53, wherein selecting the one or more string operations comprises selecting one or more of an ASCII specific string operation and a UNICODE specific string operation.

55. The apparatus of claim 38, wherein the apparatus further comprises a means for deriving the metadata for complex functions based on the metadata for a set of base attributes in a data set and filtering the set of files using complex predicates with arbitrary functions.

56. The apparatus of claim 38, wherein the metadata comprises a number of distinct values;

a number of null values; and

a minimum value and a maximum value for each file.

57. The apparatus of claim 56, wherein the metadata also comprises string length information and ranges of characters in strings.

58. The apparatus of claim 38, wherein the apparatus further comprises:

a means for creating one or more files comprising the metadata;

a means for collecting the metadata when there are changes made to the data on a per column and a per file basis during data ingestion or as a separate process after data is loaded;

a means for receiving the metadata on a per column and a per file basis; and

a means for storing the metadata in a metadata store.