Prefix indexing
AssigneeSnowflake Inc.
InventorsIsmail Oukid, Stefan Richter
Life of this patent
Estimating the term…
Abstract
A table organized into a set of batch units is accessed. A set of N-grams are generated for a data value in the source table. The set of N-grams include a first N-gram of a first length and a second N-gram of a second length where the first N-gram corresponds to a prefix of the second N-gram. A set of fingerprints are generated for the data value based on the set of N-grams. The set of fingerprints include 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. A pruning index that indexes distinct values in each column of the source table is generated based on the set of fingerprints and stored in a database with an association with the source table.
Claims30
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;
- decomposing a data item from the source table into multiple segments, the multiple segments comprising a root segment and a child segment;
- generating a set of fingerprints for the data item based on the multiple segments, the set of fingerprints comprising a first fingerprint generated based on the root segment and a second fingerprint generated based on the child segment and the first fingerprint;
- and
- generating an index for the source table based on the set of fingerprints.
A method comprising:
- accessing a source table organized into a set of batch units;
- decomposing a data item from the source table into multiple segments, the multiple segments comprising a root segment and a child segment;
- generating a set of fingerprints for the data item based on the multiple segments, the set of fingerprints comprising a first fingerprint generated based on the root segment and a second fingerprint generated based on the child segment and the first fingerprint;
- and
- generating an index for the source table based on the set of fingerprints
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;
- decomposing a data item from the source table into multiple segments, the multiple segments comprising a root segment and a child segment;
- generating a set of fingerprints for the data item based on the multiple segments, the set of fingerprints comprising a first fingerprint generated based on the root segment and a second fingerprint generated based on the child segment and the first fingerprint;
- and
- generating an index for the source table based on the set of fingerprints.
Dependencies are inferred from the claim text.