Granted Patent B2

US 11,275,738 · App. 17/484,817 · Granted Mar 15, 2022

Inventors: Ismail Oukid (Berlin, DE); Stefan Richter (Berlin, DE)

Assignee: Snowflake Inc.

G06F16/24557G06F16/2272G06F16/283G06F16/9035G06F17/18

Abstract

Claims (81)

1. A system comprising:

at least one hardware processor; and

at least one memory storing instructions that cause the at least one hardware processor to perform operations comprising:

accessing a source table organized into a set of batch units;

generating a set of N-grams for a data value in the source table, the set of N-grams comprising a first N-gram of a first length and a second N-gram of a second length, the first N-gram corresponding to a prefix of the second N-gram;

generating a set of fingerprints for the data value based on the set of N-grams, the set of fingerprints comprising a first fingerprint generated based on the first N-gram and a second fingerprint generated based on the second N-gram and the first fingerprint; and

generating a pruning index that indexes distinct N-grams in each column of the source table, the generating of the pruning index comprising generating a set of filters, the generating of the set of filters comprising populating a filter using the first and second fingerprint;

receiving a query directed at the source table, the query specifying a search pattern;

pruning the set of batch units to scan for data matching the search pattern using the pruning index, the pruning of the set of batch units comprising identifying a subset of batch units to scan for matching data; and

processing the query by scanning the subset of batch units.

2. The system of claim 1 , wherein the generating of the set of N-grams comprises:

generating the first N-gram using a first value of N; and

generating the second N-gram using a second value of N.

3. The system of claim 1 , wherein the generating of the set of fingerprints comprises:

generating the first fingerprint based on the first N-gram; and

generating the second fingerprint based on the second N-gram and the first fingerprint.

4. The system of claim 3 , wherein:

generating the first fingerprint comprises computing a hash over the first N-gram; and

generating the second fingerprint comprises computing a hash over a portion of the second N-gram that excludes the first N-gram using the first fingerprint as a seed for a hashing function used to compute the hash.

5. The system of claim 3 , wherein:

the generating of the set of N-grams for the data value further comprises generating a third N-gram for the data value using a third value of N, and

the generating of the set of fingerprints for the data value based on the set of N-grams further comprises generating a third fingerprint based on the third N-gram and the second fingerprint.

6. The system of claim 5 , wherein the generating of the third fingerprint comprises computing a hash over a portion of the third N-gram that excludes the second N-gram using the second fingerprint as a seed for a hashing function used to compute the hash.

7. The system of claim 4 , wherein the operations further comprise determining, based on the hash computed over the first N-gram, the filter from the set of filters to populate using the set of fingerprints.

8. The system of claim 1 , wherein the operations further comprise storing, in a database, the pruning index with an association with the source table.

9. The system of claim 1 , wherein the pruning of the set of batch units includes:

generating one or more fingerprints based on the search pattern; and

identifying one or more values in the pruning index that match the one or more fingerprints.

10. A method comprising:

accessing a source table organized into a set of batch units;

generating a set of N-grams for a data value in the source table, the set of N-grams comprising a first N-gram of a first length and a second N-gram of a second length, the first N-gram corresponding to a prefix of the second N-gram;

generating a set of fingerprints for the data value based on the set of N-grams, the set of fingerprints comprising a first fingerprint generated based on the first N-gram and a second fingerprint generated based on the second N-gram and the first fingerprint;

generating a pruning index that indexes distinct N-grams in each column of the source table, the generating of the pruning index comprising generating a set of filters, the generating of the set of filters comprising populating a filter using the first and second fingerprint;

receiving a query directed at the source table, the query specifying a search pattern;

pruning the set of batch units to scan for data matching the search pattern using the pruning index, the pruning of the set of batch units comprising identifying a subset of batch units to scan for matching data; and

processing the query by scanning the subset of batch units.

11. The method of claim 10 , wherein the generating of the set of N-grams comprises:

generating the first N-gram using a first value of N; and

generating the second N-gram using a second value of N.

12. The method of claim 10 , wherein the generating of the set of fingerprints comprises:

generating the first fingerprint based on the first N-gram; and

generating the second fingerprint based on the second N-gram and the first fingerprint.

13. The method of claim 12 , wherein:

generating the first fingerprint comprises computing a hash over the first N-gram; and

generating the second fingerprint comprises computing a hash over a portion of the second N-gram that excludes the first N-gram using the first fingerprint as a seed for a hashing function used to compute the hash.

14. The method of claim 12 , wherein:

the generating of the set of N-grams for the data value further comprises generating a third N-gram for the data value using a third value of N, and

the generating of the set of fingerprints for the data value based on the set of N-grams further comprises generating a third fingerprint based on the third N-gram and the second fingerprint.

15. The method of claim 14 , wherein the generating of the third fingerprint comprises computing a hash over a portion of the third N-gram that excludes the second N-gram using the second fingerprint as a seed for a hashing function used to compute the hash.

16. The method of claim 13 , further comprising:

determining, based on the hash computed over the first N-gram, the filter from the set of filters to populate using the set of fingerprints.

17. The method of claim 10 , further comprising storing, in a database, the pruning index with an association with the source table.

18. The method of claim 10 , wherein the pruning of the set of batch units includes:

generating one or more fingerprints based on the search pattern; and

identifying one or more values in the pruning index that match the one or more fingerprints.

19. A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:

accessing a source table organized into a set of batch units;

generating a set of N-grams for a data value in the source table, the set of N-grams comprising a first N-gram of a first length and a second N-gram of a second length, the first N-gram corresponding to a prefix of the second N-gram;

generating a set of fingerprints for the data value based on the set of N-grams, the set of fingerprints comprising a first fingerprint generated based on the first N-gram and a second fingerprint generated based on the second N-gram and the first fingerprint;

generating a pruning index that indexes distinct N-grams in each column of the source table, the generating of the pruning index comprising generating a set of filters, the generating of the set of filters comprising populating a filter using the first and second fingerprint;

receiving a query directed at the source table, the query specifying a search pattern;

pruning the set of batch units to scan for data matching the search pattern using the pruning index, the pruning of the set of batch units comprising identifying a subset of batch units to scan for matching data; and

processing the query by scanning the subset of batch units.

20. The computer-storage medium of claim 19 , wherein the generating of the set of N-grams comprises:

generating the first N-gram using a first value of N; and

generating the second N-gram using a second value of N.

21. The computer-storage medium of claim 19 , wherein the generating of the set of fingerprints comprises:

generating the first fingerprint based on the first N-gram; and

generating the second fingerprint based on the second N-gram and the first fingerprint.

22. The computer-storage medium of claim 21 , wherein:

generating the first fingerprint comprises computing a hash over the first N-gram; and

generating the second fingerprint comprises computing a hash over a portion of the second N-gram that excludes the first N-gram using the first fingerprint as a seed for a hashing function used to compute the hash.

23. The computer-storage medium of claim 21 , wherein:

the generating of the set of N-grams for the data value further comprises generating a third N-gram for the data value using a third value of N, and

the generating of the set of fingerprints for the data value based on the set of N-grams further comprises generating a third fingerprint based on the third N-gram and the second fingerprint.

24. The computer-storage medium of claim 23 , wherein the generating of the third fingerprint comprises computing a hash over a portion of the third N-gram that excludes the second N-gram using the second fingerprint as a seed for a hashing function used to compute the hash.

25. The computer-storage medium of claim 22 , wherein the operations further comprise determining, based on the hash computed over the first N-gram, the filter from the set of filters to populate using the set of fingerprints.

26. The computer-storage medium of claim 19 , wherein the operations further comprise storing, in a database, the pruning index with an association with the source table.

27. The computer-storage medium of claim 19 , wherein the pruning of the set of batch units includes:

generating one or more fingerprints based on the search pattern; and

identifying one or more values in the pruning index that match the one or more fingerprints.

Assignments (1)

Continuity (8)