Data pruning based on metadata

Patent metadata

Field	Value
Publication number	US-11163724-B2
Application number	US-202016861516-A
Country	US
Kind code	B2
Filing date	Apr 29, 2020
Priority date	Jul 14, 2016
Publication date	Nov 2, 2021
Grant date	Nov 2, 2021

Abstract

A system and method for pruning data based on metadata. The method may include receiving a query comprising a plurality of predicates and identifying one or more applicable files comprising 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.

First claim

What is claimed is:

1. A system comprising:
a metadata store to store metadata; and
a processor, operatively coupled with the metadata store, to:
receive a query with a plurality of predicates, wherein there is a first number of predicates in the plurality of predicates and the query to be applied to a plurality of files that comprise the database data;
determine whether each of a plurality of predicates originally included in the query partially match at least one of the plurality of files using the metadata stored in the metadata store;
for each predicate in the plurality of predicates that does not partially match at least one of the plurality of files, remove that predicate from the plurality of predicates to create a reduced set of predicates;
modify the query to use the reduced set of predicates, the reduced set of predicates having a second number of predicates that is smaller than the first number of predicates; and
process the modified query using the reduced set of predicates and the plurality of files.

2. The system of claim 1 , wherein the processor further to read the plurality of files to execute the query using at least the reduced set of predicates.

3. 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.

4. The system of claim 3 , 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.

5. The system of claim 1 , wherein to partially match at least one of a plurality of files, 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 matches at least one of the plurality of predicates.

6. The system of claim 5 , wherein to determine whether any data within the range of values of database data, the processor to determine that a certain file matches 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 matches at least one of the plurality of predicates.

7. 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 partially matching at least one of the plurality of predicates.

8. The system of claim 1 , wherein the processor further to receive a query comprising a plurality of predicates and each of the plurality of predicates is a condition expression that evaluates to a Boolean value.

9. The system of claim 1 , wherein the metadata store is separate from the database data and wherein the processor further to prune another inapplicable predicate from the plurality of predicates that matches all of the plurality of files by removing that inapplicable predicate from the query.

10. The system of claim 1 , wherein the metadata for one of the plurality of files includes at least one of a minimum value, a maximum value, a number of values, and a number of null values.

11. A method comprising:
receiving a query with a plurality of predicates, wherein there is a first number of predicates in the plurality of predicates and the query to be applied to a plurality of files that comprise the database data;
determining, by a processor, whether each of a plurality of predicates originally included in the query partially match at least one of the plurality of files using the metadata stored in the metadata store;
for each predicate in the plurality of predicates that does not partially match at least one of the plurality of files, removing that predicate from the plurality of predicates to create a reduced set of predicates;
modifying the query to use the reduced set of predicates, the reduced set of predicates having a second number of predicates that is smaller than the first number of predicates; and
processing the modified query using the reduced set of predicates and the plurality of files.

12. The method of claim 11 , further comprising reading the plurality of files to execute the query using at least the reduced set of predicates.

13. The method of claim 11 , 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.

14. 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.

15. The method of claim 11 , wherein the partially match at least one of a plurality of files 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.

16. The method of claim 15 , wherein to determine whether any data within the range of values of database data 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 matches at least one of the plurality of predicates.

17. The method of claim 11 , further comprising identifying at least one applicable column within each of the plurality of files that comprises database data partially matching at least one of the plurality of predicates.

18. The method of claim 11 , wherein the processor further to receive a query comprising a plurality of predicates and each of the plurality of predicates is a condition expression that evaluates to a Boolean value.

19. The method of claim 11 , wherein the metadata store is separate from the database data and wherein the processor further to prune another inapplicable predicate from the plurality of predicates that matches all of the plurality of files by removing that inapplicable predicate from the query.

20. The method of claim 11 , wherein the metadata for one of the plurality of files includes at least one of a minimum value, a maximum value, a number of values, and a number of null values.

21. A non-transitory computer readable storage media, programmable to execute instructions that, when executed by a processor, cause the processor to:
receive a query with a plurality of predicates, wherein there is a first number of predicates in the plurality of predicates and the query to be applied to a plurality of files that comprise the database data;
determine whether each of a plurality of predicates originally included in the query partially match at least one of the plurality of files using the metadata stored in the metadata store;
for each predicate in the plurality of predicates that does not partially match at least one of the plurality of files, remove, by the processor, that predicate from the plurality of predicates to create a reduced set of predicates;
modify the query to use the reduced set of predicates, the reduced set of predicates having a second number of predicates that is smaller than the first number of predicates; and
process the modified query using the reduced set of predic

Assignees

• Snowflake Inc

Inventors

• Cruanes Thierry
• Dageville Benoit
• Motivala Ashish
• Zukowski Marcin

Classifications

• G06F16/215

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F16/162 Primary

  Delete operations (erasing in storage systems G06F3/0652) · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title