Regular expression search query processing using pruning index
A query directed at a source table organized into a set of batch units is received. The query comprises a regular expression search pattern. The regular expression search pattern is converted to a pruning index predicate comprising a set of substring literals extracted from the regular expression search pattern. A set of N-grams is generated based on the set of substring literals extracted from the regular expression search pattern. A pruning index associated with the source table is accessed. The pruning index indexes distinct N-grams in each column of the source table. A subset of batch units to scan for data matching the query are identified based on the pruning index and the set of N-grams. 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:
receiving a query directed at a source table organized into a set of batch units, the query comprising a regular expression search pattern;
converting the regular expression search pattern to a pruning index predicate, the converting of the regular expression search pattern to the pruning index predicate comprising:
generating an expression tree comprising a tree data structure that includes a set of substring literals extracted from the regular expression search pattern; and
removing, from the expression tree, a node corresponding to a substring literal that does not produce an N-gram;
generating a set of N-grams based on the expression tree;
identifying, using a pruning index, a subset of batch units to scan for data matching the query based on the set of N-grams, the pruning index indexing distinct N-grams in each column of the source table; and
processing the query by scanning the subset of batch units.
2. The system of claim 1 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises interpreting a metacharacter in the regular expression search pattern according to a specific meaning of the metacharacter.
3. The system of claim 1 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises replacing a metacharacter with an OR predicate.
4. The system of claim 1 , wherein the expression tree comprises a Boolean expression of the set of substring literals.
5. The system of claim 1 , wherein:
the expression tree comprises a binary tree; and
the converting of the regular expression search pattern to the pruning index predicate comprises flattening the expression tree by converting the binary tree to an ordinal tree.
6. The system of claim 1 , wherein:
the expression tree comprises an AND node representing an AND predicate, the AND node including a first child leaf node representing a first substring literal and a second child leaf node representing a second substring literal; and
the converting of the regular expression search pattern to the pruning index predicate comprises merging the first child leaf node and the second child leaf node of the AND node in a single node comprising a combination of the first substring literal and the second substring literal.
7. The system of claim 1 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises concatenating a first substring literal of an OR predicate with an adjacent second substring literal.
8. The system of claim 1 , wherein the operations further comprise generating one or more fingerprints based on the set of N-grams, wherein identifying the subset of batch units to scan for data matching the query comprises identifying one or more values in the pruning index that match the one or more fingerprints.
9. A method comprising:
receiving a query directed at a source table organized into a set of batch units, the query comprising a regular expression search pattern;
converting the regular expression search pattern to a pruning index predicate, the converting of the regular expression search pattern to the pruning index predicate comprising:
generating an expression tree comprising a tree data structure that includes a set of substring literals extracted from the regular expression search pattern; and
removing, from the expression tree, a node corresponding to a substring literal that does not produce an N-gram;
generating a set of N-grams based on the expression tree;
identifying, using a pruning index, a subset of batch units to scan for data matching the query based on the set of N-grams, the pruning index indexing distinct N-grams in each column of the source table; and
processing the query by scanning the subset of batch units.
10. The method of claim 9 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises interpreting a metacharacter in the regular expression search pattern according to a specific meaning of the metacharacter.
11. The method of claim 9 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises replacing a metacharacter with an OR predicate.
12. The method of claim 9 , wherein the expression tree comprises a Boolean expression of the set of substring literals.
13. The method of claim 9 , wherein:
the expression tree comprises a binary tree; and
the converting of the regular expression search pattern to the pruning index predicate comprises flattening the expression tree by converting the binary tree to an ordinal tree.
14. The method of claim 9 , wherein:
the expression tree comprises an AND node representing an AND predicate, the AND node including a first child leaf node representing a first substring literal and a second child leaf node representing a second substring literal; and
the converting of the regular expression search pattern to the pruning index predicate comprises merging the first child leaf node and the second child leaf node of the AND node in a single node comprising a combination of the first substring literal and the second substring literal.
15. The method of claim 9 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises concatenating a first substring literal of an OR predicate with an adjacent second substring literal.
16. The method of claim 9 , further comprising generating one or more fingerprints based on the set of N-grams, wherein identifying the subset of batch units to scan for data matching the query comprises identifying one or more values in the pruning index that match the one or more fingerprints.
17. A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:
receiving a query directed at a source table organized into a set of batch units, the query comprising a regular expression search pattern;
converting the regular expression search pattern to a pruning index predicate, the converting of the regular expression search pattern to the pruning index predicate comprising:
generating an expression tree comprising a tree data structure that includes a set of substring literals extracted from the regular expression search pattern; and
removing, from the expression tree, a node corresponding to a substring literal that does not produce an N-gram;
generating a set of N-grams based on the expression tree;
identifying, using a pruning index, a subset of batch units to scan for data matching the query based on the set of N-grams, the pruning index indexing distinct N-grams in each column of the source table; and
processing the query by scanning the subset of batch units.
18. The computer-storage medium of claim 17 , wherein:
the expression tree comprises an AND node representing an AND predicate, the AND node including a first child leaf node representing a first substring literal and a second child leaf node representing a second substring literal; and
the converting the regular expression search pattern to the pruning index predicate further comprises
merging the first child leaf node and the second child leaf node of the AND node in a single node comprising a combination of the first substring literal and the second substring literal.
19. The computer-storage medium of claim 17 , wherein:
the expression tree comprises a binary tree; and
the converting of the regular expression search pattern to the pruning index predicate comprises flattening the expression tree by converting the binary tree to an ordinal tree.
20. The computer-storage medium of claim 17 , wherein the converting of the regular expression search pattern to the pruning index predicate comprises concatenating a first substring literal of an OR predicate with an adjacent second substring literal.