Multi-range and runtime pruning

• US 10,545,917 B2
• Filed: 10/13/2015
• Issued: 01/28/2020
• Est. Priority Date: 02/19/2014
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: Snowflake, Inc.
• Inventors: Dageville, Benoit, Cruanes, Thierry, Zukowski, Marcin, Lee, Allison Waingold, Unterbrunner, Philipp Thomas
• Primary Examiner(s): Nguyen, Minh Chau
• Application Number:
  US14/882,024
• Publication Number:
  US 20160034486A1
• Time in Patent Office: 1,568 Days
• Field of Search: 709203, 709213
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A system, apparatus, and method for managing data storage and data access with querying data and filtering value ranges using only a constant amount of computer memory in the implementation of bloom filters based on a first consumption of a relation.

Claims

1. A method comprising:

storing a plurality of metadata items in a metadata store that is separate from a storage platform that stores a plurality of files, each file of the plurality of files comprising a block of database data;

determining a join operation to be performed on two or more files of the plurality of files, the join operation comprising a predicate indicating a first value;

scanning the plurality of metadata items without accessing the database data to identify the two or more files that are necessary to complete the join operation, wherein;

each metadata item corresponds to and comprises information about a file of the plurality of files; and

each metadata item indicates a minimum/maximum value range for its corresponding file;

identifying, from the plurality of metadata items, a first group of files whose minimum/maximum value ranges do not encompass the first value;

pruning the first group of files;

consuming, by a build operator of the join operation, database data in at least one file of the two or more files that are necessary to complete the join operation;

generating a vector summarizing the database data consumed by the build operator;

broadcasting the vector to at least one probe operator of the join operation; and

filtering rows from the one or more files that are necessary to complete the join operation based on the vector.

2. The method of claim 1, wherein the build operator is configured to build a hash table as part of the join operation and wherein the probe operator is configured to read streams of database data and probe the hash table to find matching rows as part of the join operation.

3. The method of claim 2, wherein the build operator is configured to build the hash table and further generate the vector.

4. The method of claim 1, wherein the vector holds a minimum and maximum value pair that describes a range of values present in the database data consumed by the build operator.

5. The method of claim 1, wherein pruning the first group of files comprises removing the first group of files from the join operation such that the first group of files is are not consumed by any build operator of the join operation.

6. The method of claim 1, wherein the vector is a bounded size hash map describing a range of values consumed by the build operator such that ranges of individual hash map entries are disjunct.

7. The method of claim 1, wherein the vector comprises a range bloom vector and is configured for gathering and querying information on value ranges using only a constant amount of memory.

8. The method of claim 1, further comprising inputting the vector into a corresponding local filter operator, wherein the local filter operator is a local access path to a second relation of the join operation.

9. The method of claim 1, wherein the determining the join operation comprises receiving a query comprising the predicate, wherein execution of the join operation is required to respond to the query.

10. A system comprising:

a memory to store one or more processing instructions;

a processing device, operatively coupled to the memory, to;

store a plurality of metadata items in a metadata store that is separate from a storage platform that stores a plurality of files, each file of the plurality of files comprising a block of database data;

determine a join operation to be performed on two or more files of the plurality of files, the join operation comprising a predicate indicating a first value;

scan the plurality of metadata items without accessing the database data to identify the two or more files that are necessary to complete the join operation, wherein;

each metadata item corresponds to and comprises information about a file of the plurality of files; and

each metadata item corresponding metadata for a file indicates a minimum/maximum value range for its corresponding file;

prune the first group of files;

consume, by a build operator of the join operation, database data in at least one file of the one or more files that are necessary to complete the join operation;

generate a vector summarizing the database data consumed by the build operator;

broadcast the vector to at least one probe operator of the join operation; and

filter rows from the one or more files that are necessary to complete the join operation based on the vector.

11. The system of claim 10, the processing device further to:

build a hash table as part of the join operation, and

probe the hash table to find matching rows as part of the join operation.

12. The system of claim 11, wherein the build operator builds the hash table and generates the vector.

13. The system of claim 10, wherein the vector holds a minimum and maximum value pair that describes a range of values present in the database data consumed by the build operator.

14. The system of claim 10, the processing device further to remove the first group of files from the join operation such that the first group of files are not consumed by any build operator of the join operation.

15. The system of claim 10, wherein the vector is a bounded size hash map describing a range of values consumed by the build operator such that ranges of individual hash map entries are disjunct.

16. The system of claim 10, wherein the vector comprises a range bloom vector, wherein the range bloom vector gathers and queries information on value ranges using only a constant amount of memory.

17. The system of claim 10, the processing device further to input the vector into a corresponding local filter operator, wherein the local filter operator is a local access path to a second relation of the join operation.

18. Non-transitory computer readable storage media storing instructions that, when executed by one or more processors, cause the one or more processors to:

store a plurality of metadata items in a metadata store that is separate from a storage platform that stores a plurality of files, each file of the plurality of files comprising a block of database data;

determine a join operation to be performed on two or more files of the plurality of files, the join operation comprising a predicate indicating a first value;

scan the plurality of metadata items without accessing the database data to identify the two or more files that are necessary to complete the join operation, wherein;

each metadata item corresponds to and comprises information about a file of the plurality of files; and

each metadata item indicates a minimum/maximum value range for its corresponding file;

identify, from the plurality of metadata items, a first group of files whose minimum/maximum value ranges do not encompass the first value;

prune the first group of files;

consume, by a build operator of the join operation, database data in at least one file of the two or more files that are necessary to complete the join operation;

generate a vector summarizing the database data consumed by the build operator;

broadcast the vector to at least one probe operator of the join operation; and

filter rows from the one or more files that are necessary to complete the join operation based on the vector.

19. The non-transitory computer readable storage media of claim 18, wherein the build operator is configured to build a hash table as part of the join operation and wherein the probe operator is configured to read streams of database data and probe the hash table to find matching rows as part of the join operation.

20. The non-transitory computer readable storage media of claim 19, wherein the build operator is configured to build the hash table and further generate the vector.

21. The non-transitory computer readable storage media of claim 18, wherein the vector holds a minimum and maximum value pair that describes a range of values present in the database data consumed by the build operator.

22. The non-transitory computer readable storage media of claim 18, wherein the instructions cause the one or more processors to prune the first group of files by removing the first group of files from the join operation such that the first group of files are not consumed by any build operator of the join operation.

23. The non-transitory computer readable storage media of claim 18, wherein the vector is a bounded size hash map describing a range of values consumed by the build operator such that ranges of individual hash map entries are disjunct.

24. The non-transitory computer readable storage media of claim 18, wherein the vector comprises a range bloom vector and is configured for gathering and querying information on value ranges using only a constant amount of memory.

25. The non-transitory computer readable storage media of claim 18, further comprising inputting the vector into a corresponding local filter operator, wherein the local filter operator is a local access path to a second relation of the join operation.

26. The non-transitory computer readable storage media of claim 18, wherein the determining the join operation comprises receiving a query comprising the predicate, wherein execution of the join operation is required to respond to the query.