Pruning using prefix indexing
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.
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;
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;
generating an index for the source table based on the set of fingerprints; and
receiving a query directed at the source table, the query specifying a search pattern;
identifying, based on the index, a subset of batch units to scan for data matching the query; and
processing the query by scanning the subset of batch units.
2. The system of claim 1 , wherein the generating of the set of fingerprints comprises:
generating the first fingerprint based on the root segment; and
generating the second fingerprint based on the child segment and the first fingerprint.
3. The system of claim 2 , wherein:
generating the first fingerprint comprises computing a first hash over the root segment; and
generating the second fingerprint comprises computing a second hash over the child segment using the first hash as a seed for a hashing function used to compute the second hash.
4. The system of claim 3 , wherein:
the child segment is a first child segment;
the multiple segments further comprise a second child segment; and
the generating of the set of fingerprints for the data item further comprises generating a third fingerprint based on the second child segment and the second fingerprint.
5. The system of claim 4 , wherein the generating of the third fingerprint comprises computing a third hash over the second child segment using the second hash as a seed for a hashing function used to compute the third hash.
6. The system of claim 3 , wherein:
the index comprises a set of filters; and
the operations further comprise determining, based on the first hash, a filter from the set of filters to populate using the set of fingerprints.
7. The system of claim 6 , wherein generating the index comprises populating the filter using the first fingerprint and second fingerprint.
8. The system of claim 7 , wherein:
populating the filter using the first fingerprint comprises populating the filter with a first number of bits, and
populating the filter using the second fingerprint comprises populating the filter with a second number of bits.
9. The system of claim 1 , wherein the root segment and the child segment of the data item have a hierarchical relationship.
10. The system of claim 1 , wherein identifying of the subset of batch units comprises:
generating one or more fingerprints based on the search pattern; and
identifying one or more values in the index that match the one or more fingerprints.
11. 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;
generating an index for the source table based on the set of fingerprints;
receiving a query directed at the source table, the query specifying a search pattern;
identifying, based on the index, a subset of batch units to scan for data matching the query; and
processing the query by scanning the subset of batch units.
12. The method of claim 11 , wherein the generating of the set of fingerprints comprises:
generating the first fingerprint based on the root segment; and
generating the second fingerprint based on the child segment and the first fingerprint.
13. The method of claim 12 , wherein:
generating the first fingerprint comprises computing a first hash over the root segment; and
generating the second fingerprint comprises computing a second hash over the child segment using the first hash as a seed for a hashing function used to compute the second hash.
14. The method of claim 13 , wherein:
the child segment is a first child segment;
the multiple segments further comprise a second child segment; and
the generating of the set of fingerprints for the data item further comprises generating a third fingerprint based on the second child segment and the second fingerprint.
15. The method of claim 14 , wherein the generating of the third fingerprint comprises computing a third hash over the second child segment using the second hash as a seed for a hashing function used to compute the third hash.
16. The method of claim 13 , wherein:
the index comprises a set of filters; and
the method further comprises determining, based on the first hash, a filter from the set of filters to populate using the set of fingerprints.
17. The method of claim 16 , wherein generating the index comprises populating the filter using the first fingerprint and second fingerprint.
18. The method of claim 17 , wherein:
populating the filter using the first fingerprint comprises populating the filter with a first number of bits, and
populating the filter using the second fingerprint comprises populating the filter with a second number of bits.
19. The method of claim 18 , wherein the first number of bits is greater than the second number of bits.
20. The method of claim 11 , wherein the identifying of the subset of batch units comprises:
generating one or more fingerprints based on the search pattern; and
identifying one or more values in the index that match the one or more fingerprints.
21. 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;
generating an index for the source table based on the set of fingerprints;
receiving a query directed at the source table, the query specifying a search pattern;
identifying, based on the index, a subset of batch units to scan for data matching the query; and
processing the query by scanning the subset of batch units.
22. The computer-storage medium of claim 21 , wherein the generating of the set of fingerprints comprises:
generating the first fingerprint based on the root segment; and
generating the second fingerprint based on the child segment and the first fingerprint.
23. The computer-storage medium of claim 22 , wherein:
generating the first fingerprint comprises computing a first hash over the root segment; and
generating the second fingerprint comprises computing a second hash over the child segment using the first hash as a seed for a hashing function used to compute the second hash.
24. The computer-storage medium of claim 23 , wherein:
the child segment is a first child segment;
the multiple segments further comprise a second child segment; and
the generating of the set of fingerprints for the data item further comprises generating a third fingerprint based on the second child segment and the second fingerprint.
25. The computer-storage medium of claim 24 , wherein the generating of the third fingerprint comprises computing a third hash over the second child segment using the second hash as a seed for a hashing function used to compute the third hash.
26. The computer-storage medium of claim 23 , wherein:
the index comprises a set of filters; and
the operations further comprise determining, based on the first hash, a filter from the set of filters to populate using the set of fingerprints.
27. The computer-storage medium of claim 26 , wherein generating the index comprises the populating the filter using the first fingerprint and second fingerprint.
28. The computer-storage medium of claim 26 , wherein:
populating the filter using the first fingerprint comprises populating the filter with a first number of bits, and
populating the filter using the second fingerprint comprises populating the filter with a second number of bits.
29. The computer-storage medium of claim 28 , wherein the first number of bits is greater than the second number of bits.
30. The computer-storage medium of claim 21 , wherein the root segment and the child segment of the data item have a hierarchical relationship.