# US 11,113,286 B2 · Generation of pruning index for pattern matching queries > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,286 B2 - Document ID: US11113286B2 - Status: Granted - Kind: B2 - Application number: 17/218,962 - Filed: 2021-03-31 - Published: 2021-07-15 - Granted: 2021-09-07 - Earliest claimed: 2019-12-26 - Assignees: Snowflake Inc. - Applicants: Snowflake Inc. - Inventors: Thierry Cruanes; Benoit Dageville; Ismail Oukid; Stefan Richter - Web page: https://patentgrep.com/patent/US11113286B2 ## CPC - G06F 16/221: {Column-oriented storage; Management thereof} - G06F 16/24557: {Efficient disk access during query execution} - G06F 16/2255: {Hash tables} - G06F 16/2272: {Management thereof} - G06F 16/283: {Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP} - G06F 16/9035: Filtering based on additional data, e.g. user or group profiles - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 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; generating a pruning index based on the source table, the pruning index comprising a set of filters that index distinct N-grams in each column of the source table, each filter in the set of filters corresponding to a batch unit in the set of batch units, the generating of the pruning index comprising generating the set of filters, the generating of the set of filters comprising populating a cell in a first filter with a fingerprint generated based on an N-gram of a data value in the source table; and storing, in a database, the pruning index with an association with the source table. ### Claim 2 (depends on 1) The system of claim 1, wherein the operations further comprise: preprocessing the data value, the preprocessing of the data value includes generating one or more preprocessed variants of the data value; and generating a set of N-grams for the data value based on the one or more preprocessed variant of the data value, the set of N-grams including the N-gram of the data value. ### Claim 3 (depends on 2) The system of claim 2, wherein the preprocessing of the data value includes generating a case-agnostic variant of the data value. ### Claim 4 (depends on 2) The system of claim 2, wherein the preprocessing of the data value includes generating one or more misspelled variants of the data value. ### Claim 5 (depends on 2) The system of claim 2, wherein the preprocessing of the data value includes generating one or more synonymous variants corresponding to synonyms of the data value. ### Claim 6 (depends on 2) The system of claim 2, wherein the preprocessing of the data value includes generating a variant with one or more special characters to mark a start and end of the data value. ### Claim 7 (depends on 1) The system of claim 1, wherein the generating of the set of filters further comprises generating the fingerprint by computing a hash of the N-gram. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 8) The system of claim 8, wherein identifying the subset of batch units comprises: generating a set of fingerprints based on N-grams of the search pattern; and comparing the set of fingerprints to the pruning index. ### Claim 10 (depends on 9) The system of claim 9, 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 set of fingerprints; and identifying the subset of batch units based on the one or more values. ### Claim 11 A method comprising: accessing a source table organized into a set of batch units; generating, using one or more hardware processors, a pruning index based on the source table, the pruning index comprising a set of filters that index distinct N-grams in each column of the source table, each filter in the set of filters corresponding to a batch unit in the set of batch units, the generating of the pruning index comprising generating the set of filters, the generating of the set of filters comprising populating a cell in a first filter with a fingerprint generated based on an N-gram of a data value in the source table; and storing, in a database, the pruning index with an association with the source table. ### Claim 12 (depends on 11) The method of claim 11, further comprising: preprocessing the data value, the preprocessing of the data value includes generating one or more preprocessed variants of the data value; and generating a set of N-grams for the data value based on the one or more preprocessed variant of the data value, the set of N-grams including the N-gram of the data value. ### Claim 13 (depends on 12) The method of claim 12, wherein the preprocessing of the data value includes generating a case-agnostic variant of the data value. ### Claim 14 (depends on 12) The method of claim 12, wherein the preprocessing of the data value includes generating one or more misspelled variants of the data value. ### Claim 15 (depends on 12) The method of claim 12, wherein the preprocessing of the data value includes generating one or more synonymous variants corresponding to synonyms of the data value. ### Claim 16 (depends on 12) The method of claim 12, wherein the preprocessing of the data value includes generating a variant with one or more special characters to mark a start and end of the data value. ### Claim 17 (depends on 11) The method of claim 11, wherein the generating of the set of filters further comprises generating the fingerprint by computing a hash of the N-gram. ### Claim 18 (depends on 11) The method of claim 11, 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 matching data; and processing the query by scanning the subset of batch units. ### Claim 19 (depends on 18) The method of claim 18, wherein identifying the subset of batch units comprises: generating a set of fingerprints based on N-grams of the search pattern; and comparing the set of fingerprints to the pruning index. ### Claim 20 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 pruning index based on the source table, the pruning index comprising a set of filters that index distinct N-grams in each column of the source table, each filter in the set of filters corresponding to a batch unit in the set of batch units, the generating of the pruning index comprising generating the set of filters, the generating of the set of filters comprising populating a cell in a first filter with a fingerprint generated based on an N-gram of a data value in the source table; and storing, in a database, the pruning index with an association with the source table. ### Claim 21 (depends on 20) The computer-storage medium of claim 20, wherein the operations further comprise: preprocessing the data value, the preprocessing of the data value includes generating one or more preprocessed variants of the data value; and generating a set of N-grams for the data value based on the one or more preprocessed variant of the data value, the set of N-grams including the N-gram of the data value. ### Claim 22 (depends on 21) The computer-storage medium of claim 21, wherein the preprocessing of the data value includes at least one of: generating a case-agnostic variant of the data value; generating one or more misspelled variants of the data value; generating one or more synonymous variants corresponding to synonyms of the data value; and generating a variant with one or more special characters to mark a start and end of the data value. ### Claim 23 (depends on 21) The computer-storage medium of claim 21, wherein generating of the set of filters further comprises generating the fingerprint by computing a hash of the N-gram. ### Claim 24 (depends on 21) The computer-storage medium of claim 21, 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.