Data pruning based on metadata

• US 10,437,780 B2
• Filed: 07/14/2016
• Issued: 10/08/2019
• Est. Priority Date: 07/14/2016
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: Snowflake, Inc.
• Inventors: Zukowski, Marcin, Dageville, Benoit, Cruanes, Thierry, Motivala, Ashish
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/210,536
• Publication Number:
  US 20180018343A1
• Time in Patent Office: 1,181 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, the method 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 matches 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 file 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 file 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, further comprising:

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, further comprising identifying files wherein all tuples in the identified files match a delete predicate based on the file metadata and deleting the identified files without accessing data from the actual file.

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

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

10. The method of claim 2, further comprising 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, further comprising 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, further comprising deriving 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, further comprising determining a range of characters based on the file 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, further comprising deriving metadata for complex functions based on 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 file 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 file metadata further comprises string length information and ranges of characters in strings.

18. The method of claim 1, further comprising:

creating one or more files comprising the file metadata;

collecting the file 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 file metadata on a per column and a per file basis; and

storing the file metadata in a metadata store.

19. A processor that is programmable to execute instructions stored in non-transitory computer readable storage media, the instructions comprising:

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

accessing metadata associated with the set of files, determining whether data in each file of the set of files matches at least one predicate of the plurality of predicates based on the 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;

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.

20. The processor of claim 19, wherein the instructions further comprise 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.

21. The processor of claim 19, wherein the instructions further comprise deriving 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 processor of claim 19, wherein the instructions further comprise one or more of the following based on the metadata:

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.

23. The processor of claim 22, wherein the instructions further comprise:

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.

24. The processor of claim 22, wherein the instructions further comprise determining 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 processor of claim 19, wherein the instructions further comprise 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.

26. The processor of claim 19, wherein the instructions further comprise receiving a request to delete tuples in the query.

27. The processor of claim 26, wherein the instructions further comprise identifying 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 processor of claim 27, wherein deleting is performed during a query preparation phase.

29. The processor of claim 19, wherein the wherein the instructions further comprise:

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.

30. The processor of claim 22, wherein the wherein the instructions further comprise 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.

31. The processor of claim 30, wherein the instructions further comprise deriving a new predicate on the second set of files from the predicate on the first set of files.

32. The processor of claim 19, wherein the the instructions further comprise determining a range of characters based on the metadata and selecting one or more string operations based on the range of characters.

33. The processor 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 processor of claim 19, wherein the instructions further comprise 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.

35. The processor 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 processor of claim 35, wherein the metadata further comprises string length information and ranges of characters in strings.

37. The processor of claim 19, wherein the instructions further comprise:

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.

38. A system comprising:

a resource manager in communication with a plurality of shared storage devices collectively storing database data and an execution platform comprising a plurality of execution nodes, the resource manager comprising a processor that is programmable to execute instructions stored in non-transitory computer readable storage media and configured to;

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

access metadata associated with the set of files, determine whether data in each file matches at least one predicate of the plurality of predicates based on the 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;

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;

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; and

the execution platform configured to;

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

return the final set of files to the resource manager in response to the query.

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

40. The system of claim 38, wherein the resource manager is 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 by 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 system of claim 38, wherein the resource manager is further configured to derive 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.

42. The system of claim 38, wherein the resource manager is further configured to:

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.

43. The system of claim 42, wherein the resource manager 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.

44. The system of claim 42, wherein the resource manager 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.

45. The system of claim 38, wherein the resource manager is further 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.

46. The system of claim 38, wherein the resource manager is further configured to receive a request to delete tuples in the query.

47. The system of claim 46, wherein the resource manager is further 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.

48. The system of claim 47, wherein the resource manager is configured to delete during a query preparation phase.

49. The system of claim 38, wherein the resource manager is further 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.

50. The system of claim 42, wherein the resource manager 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.

51. The system of claim 50, wherein the resource manager is further configured to derive a new predicate on the second set of files from the predicate on the first set of files.

52. The system of claim 38, wherein the resource manager is further configured to determine a range of characters based on the metadata and selecting one or more string operations based on the range of characters.

53. The system of claim 52, wherein the resource manager is configured to select the one or more string operations by selecting one or more of an ASCII specific string operation and a UNICODE specific string operation.

54. The system of claim 38, wherein the resource manager is further 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.

55. The system 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.

56. The system of claim 55, wherein the metadata further comprises string length information and ranges of characters in strings.

57. The system of claim 38, wherein the resource manager is further configured to:

create one or more files comprising the metadata;

collect 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;

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

store the metadata in a metadata store.