Pruning index generation for pattern matching queries
A query directed at a source table organized into a set of batch units is received. The query includes a pattern matching predicate that specifies a search pattern. A set of N-grams are generated based on the search pattern. A pruning index associated with the source table is accessed. The pruning index comprises a set of filters that index distinct N-grams in each column of the source table. The pruning index is used to identify a subset of batch units to scan for matching data based on the set of N-grams generated for the search pattern. The query is processed by scanning the subset of batch units.
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:
generating a pruning index based on a source table that is organized into a set of batch units, the pruning index indexing distinct N-grams in each column of the source table, the generating of the pruning index comprising:
generating a variant of a data value in the source table, the variant comprising one or more special characters to mark a start and an end of the data value; and
generating a set of fingerprints based on the data value and the variant of the data value; and
storing, in a database, the pruning index with an association with the source table.
2. The system of claim 1 , wherein the operations further comprise:
generating a set of N-grams for the data value based on the variant of the data value, the set of N-grams including an N-gram of the data value, wherein the set of fingerprints are generated based on the set of N-grams.
3. The system of claim 1 , wherein the generating of the pruning index further comprises generating a case-agnostic variant of the data value.
4. The system of claim 1 , wherein the generating of the pruning index further comprises generating one or more misspelled variants of the data value.
5. The system of claim 1 , wherein the generating of the pruning index further comprises generating a synonymous variant corresponding to a synonym of the data value.
6. The system of claim 1 , wherein the generating the set of fingerprints includes computing a hash of an N-gram of the variant of the data value.
7. The system of claim 1 ; wherein the operations further comprise:
receiving a query directed at the source table, the query including a pattern matching predicate specifying a search pattern;
identifying, using the pruning index, a subset of batch units to scan for matching data; and
processing the query by scanning the subset of batch units.
8. The system of claim 7 , wherein:
the set of fingerprints is a first set of fingerprints; and
the identifying the subset of batch units comprises:
generating a second set of fingerprints based on N-grams of the search pattern; and
comparing the second set of fingerprints to the pruning index.
9. The system of claim 8 , wherein identifying the subset of batch units further comprises:
identifying one or more values in the pruning index that match one or more fingerprints in the second set of fingerprints; and
identifying the subset of batch units based on the one or more values.
10. A method comprising:
generating, by one or more hardware processors, a pruning index based on a source table that is organized into a set of batch units, the pruning index indexing distinct N-grams in each column of the source table, the generating of the pruning index comprising:
generating a variant of a data value in the source table, the variant comprising one or more special characters to mark a start and an end of the data value;
generating a set of fingerprints based on Rail the data value in the source table and the variant of the data value; and
storing, in a database, the pruning index with an association with the source table.
11. The method of claim 10 , further comprising:
generating a set of N-grams for the data value based on the variant of the data value, the set of N-grams including an N-gram of the data value, wherein the set of fingerprints are generated based on the set of N-grams.
12. The method of claim 11 , wherein the generating of the pruning index further comprises generating a case-agnostic variant of the data value.
13. The method of claim 12 , wherein the generating of the pruning index further comprises generating one or more misspelled variants of the data value.
14. The method of claim 12 , wherein the generating of the pruning index further comprises generating a synonymous variant corresponding to a synonym of the data value.
15. The method of claim 10 , wherein the generating the set of fingerprints includes computing a hash of an N-gram of the variant of the data value.
16. The method of claim 10 , further comprising:
receiving a query directed at the source table, the query including a pattern matching predicate specifying a search pattern;
identifying, using the pruning index, a subset of batch units to scan for snatching data; and
processing the query by scanning the subset of batch units.
17. The method of claim 16 , wherein:
the set of fingerprints is a first set of fingerprints; and
the identifying the subset of batch units comprises:
generating a second set of fingerprints based on N-grams of the search pattern; and
comparing the second set of fingerprints to the pruning index.
18. A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:
generating a pruning index based on a source table that is organized into a set of batch units, the pruning index indexing distinct N-grams in each column of the source table, the generating of the pruning index comprising:
generating a variant of a data value in the source table, the variant comprising one or more special characters to mark a start and an end of the data value;
generating a set of fingerprints based on the data value in the source tab and the variant of the data value; and
storing, in a database, the pruning index with an association with the source table.
19. The computer-storage medium of claim 18 , wherein the operations further comprise:
generating a set of N-grams for the data value based on the variant of the data value, the set of N-grams including an N-gram of the data value, wherein the set of fingerprints are generated based on the set of N-grams.
20. The computer-storage medium of claim 18 , wherein the generating of the pruning index further comprises generating a case-agnostic variant of the data value.
21. The computer-storage medium of claim 18 , wherein the generating of the pruning index further comprises generating one or more misspelled variants of the data value.
22. The computer-storage medium of claim 18 , wherein the generating of the pruning index further comprises generating a synonymous variant corresponding to a synonym of the data value.
23. The computer-storage medium of claim 18 , wherein the generating the set of fingerprints includes computing a hash of an N-gram of the variant of the data value.
24. The computer-storage medium of claim 18 , wherein the operations further comprise:
receiving a query directed at the source table, the query including a pattern matching predicate specifying a search pattern;
identifying, using the pruning index, a subset of batch units to scan for matching data; and
processing the query by scanning the subset of batch units.