US 11,113,286 B2Granted

Generation of pruning index for pattern matching queries

AssigneeSnowflake Inc.

InventorsThierry Cruanes, Benoit Dageville, Ismail Oukid, Stefan Richter

Life of this patent

Estimating the term…

Loading patent…

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.

Claims24

Dependent claims

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.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/218,962Filed 31 Mar 2021 · continuation
Priority: 26 Dec 2019
Published: US 2021/0216555 A115 Jul 2021
Granted: 7 Sep 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 16/221
Indexing; Data structures therefor; Storage structures: column-oriented storage; Management thereof
G06F 16/24557
Unary operations; Data partitioning operations: efficient disk access during query execution
G06F 16/2255
Indexing structures: hash tables
G06F 16/2272
Indexing structures: management thereof

Family

Application16/727,315Parent of this continuation · filed 26 Dec 2019
Application16/932,462Parent of this continuation-in-part · filed 17 Jul 2020
Application63/084,394Us provisional application · filed 28 Sep 2020
Application17/086,228Parent of this continuation · filed 30 Oct 2020
US 2021/0216555 A1Pre-grant publication · published 15 Jul 2021
US 10,997,179 B1Parent of this continuation
US 10,942,925 B1Parent of this continuation-in-part
Application17/086,228Parent of this continuation-in-part
US 10,769,150 B1Parent of this continuation
Application16/932,462Parent of this continuation
US 11,113,286 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key