Data pruning based on metadata

• US 10,678,753 B2
• Filed: 11/19/2019
• Issued: 06/09/2020
• 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:
  US16/688,888
• Publication Number:
  US 20200089655A1
• Time in Patent Office: 203 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 and method for pruning data based on metadata. The method may include receiving a query that includes a plurality of predicates and identifying one or more applicable files including database data satisfying at least one of the plurality of predicates. The identifying the one or more applicable files including reading metadata stored in a metadata store that is separate from the database data. The method further includes pruning inapplicable files comprising database data that does not satisfy at least one of the plurality of predicates to create a reduced set of files and reading the reduced set of files to execute the query.

Claims

1. A system comprising:

a metadata store to store metadata; and

a processor, operatively coupled with the metadata store, to;

receive a query comprising a plurality of predicates;

determine whether each of a plurality of files that comprises database data satisfies at least one of the plurality of predicates, wherein identifying the one or more applicable files comprises reading the metadata stored in the metadata store that is separate from the database data;

prune inapplicable files from the plurality of files that does not satisfy at least one of the plurality of predicates to create a reduced set of files; and

read the reduced set of files to execute the query.

2. The system of claim 1, wherein the processor to identify based on the metadata store one or more predicates of the query that do not fully match any file comprising database data.

3. The system of claim 2, the processor to remove from the query the one or more predicates that do not fully match any file in the plurality of files to create a modified query.

4. The system of claim 1, wherein the processor to store the database data in the plurality of files, wherein each file of the plurality of files comprises a discrete selection of the database data.

5. The system of claim 4, wherein the processor further to:

generate a metadata file comprising information about a discrete selection of database data stored in a file; and

store the metadata file in the metadata store separate from the discrete selection of the database data.

6. The system of claim 1, wherein to prune the inapplicable files, the processor to:

identify the inapplicable files without accessing the inapplicable files; and

remove from consideration the inapplicable files such that the inapplicable files are not read during execution of the query.

7. The system of claim 6, wherein to identify the inapplicable files, the processor to:

read metadata pertaining to each of the inapplicable files, the metadata stored in the metadata store;

or

identify all other files comprising database data not including the applicable files identified by the identifying of the one or more applicable files.

8. The system of claim 1, wherein to read the metadata, the processor to:

determine, based on the metadata, a range of values of database data stored in a certain file; and

determine whether any data within the range of values of database data stored in the certain file satisfies at least one of the plurality of predicates.

9. The system of claim 8, wherein to determine whether each of the plurality of files, the processor to determine that a certain file satisfies at least one of the plurality of predicates based on at least a determination that some data within the range of values stored in the certain file satisfies at least one of the plurality of predicates.

10. The system of claim 1, wherein the processor further to identify at least one applicable column within each of the plurality of files that comprises database data satisfying at least one of the plurality of predicates.

11. The system of claim 1, wherein the processor further to execute the query.

12. The system of claim 1, wherein the processor further to:

identify, based on the metadata, one or more predicates of the query that do not fully match any file comprising database data; and

remove from the query the one or more predicates that do not fully match any file comprising database data to create a modified query.

13. A method comprising:

receiving a query comprising a plurality of predicates;

determining, by a processor, whether each of a plurality of files comprises database data satisfies at least one of the plurality of predicates, wherein the identifying the one or more applicable files comprises reading metadata stored in a metadata store that is separate from the database data;

pruning one or more inapplicable files from the plurality of files that does not satisfy at least one of the plurality of predicates to create a reduced set of files; and

reading the reduced set of files to execute the query.

14. The method of claim 13, further comprising identifying, based on the metadata, one or more predicates of the query that do not fully match any file comprising database data.

15. The method of claim 14, further comprising removing from the query the one or more predicates that do not fully match any file in the plurality of files to create a modified query.

16. The method of claim 13, further comprising storing the database data in the plurality of files, wherein each file of the plurality of files comprises a discrete selection of the database data.

17. The method of claim 13, wherein pruning the inapplicable files comprises:

identifying the inapplicable files without accessing the inapplicable files; and

removing from consideration the inapplicable files such that the inapplicable files are not read during execution of the query.

18. The method of claim 17, wherein reading the metadata comprises:

determining, based on the metadata, a range of values of database data stored in a certain file; and

determining whether any data within the range of values of database data stored in the certain file satisfies at least one of the plurality of predicates.

19. The method of claim 18, wherein identifying the one or more applicable files comprises identifying the certain file as being an applicable file in response to a determination that some data within the range of values stored in the certain file satisfies at least one of the plurality of predicates.

20. The method of claim 13, further comprising executing the query.

21. The method of claim 13, further comprising:

generating a metadata file comprising information about a discrete selection of database data stored in a file; and

storing the metadata file in the metadata store separate from the discrete selection of the database data.

22. The method of claim 13, further comprising identifying at least one applicable column within each of the one or more applicable files that comprises database data satisfying at least one of the plurality of predicates.

23. A non-transitory computer readable storage media, programmable to execute instructions that, when executed by a processor, cause the processor to:

receive a query comprising a plurality of predicates;

determining whether each of a plurality of files comprises database data satisfies at least one of the plurality of predicates, wherein to identify the one or more applicable files, the processor to read metadata stored in a metadata store that is separate from the database data;

prune, by the processor, one or more inapplicable files from the plurality of files that does not satisfy at least one of the plurality of predicates to create a reduced set of files; and

read the reduced set of files to execute the query.

24. The non-transitory computer readable storage media of claim 23, the instructions further to cause the processor to:

identify, based on the metadata, one or more predicates of the query that do not fully match any file comprising database data; and

remove from the query the one or more predicates that do not fully match any file comprising database data to create a modified query.

25. The non-transitory computer readable storage media of claim 23, the instructions further to cause the processor to store the database data in the plurality of files, wherein each file of the plurality of files comprises a discrete selection of the database data.

26. The non-transitory computer readable storage media of claim 24, wherein to read the metadata, the processor to:

determine, based on the metadata, a range of values of database data stored in a certain file; and

determine whether any data within the range of values of database data stored in the certain file satisfies at least one of the plurality of predicates.

27. The non-transitory computer readable storage media of claim 26, wherein determining whether each of the plurality of files comprises determine that a certain file satisfies at least one of the plurality of predicates based on at least a determination that some data within the range of values stored in the certain file satisfies at least one of the plurality of predicates.

28. The non-transitory computer readable storage media of claim 23, wherein to prune the inapplicable files the processor to:

identify the inapplicable files without accessing the inapplicable files; and

remove from consideration the inapplicable files such that the inapplicable files are not read during execution of the query.

29. The non-transitory computer readable storage media of claim 23, the instructions further to cause the processor to execute the query.

30. The non-transitory computer readable storage media of claim 23, the instructions further to cause the processor to:

generate a metadata file comprising information about a discrete selection of database data stored in a file; and

store the metadata file in the metadata store separate from the discrete selection of the database data.