Prefix n-gram indexing

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;
• 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.

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;
• 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.