# US 2022/0277013 A1 · Pruning index generation and enhancement

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0277013 A1
- Document ID: US20220277013A1
- Status: Published application
- Kind: A1
- Application number: 17/654,887
- Filed: 2022-03-15
- Published: 2022-09-01
- 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/US20220277013A1

## CPC

- G06F 16/24557: {Efficient disk access during query execution}
- G06F 16/221: {Column-oriented storage; Management thereof}
- 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 source table organized into a set of micro-partitions is accessed by a network-based data warehouse. A pruning index is generated based on the source table. The pruning index comprises a set of filters that indicate locations of distinct values in each column of the source table. A query directed at the source table is received at the network-based data warehouse. The query is processed using the pruning index. The processing of the query comprises pruning the set of micro-partitions of the source table to scan for data matching the query, the pruning of the plurality of micro-partitions comprising identifying, using the pruning index, a sub-set of micro-partitions to scan for the data matching the query.

## 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:
generating a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:
generating a filter corresponding to a batch unit in the set of batch units; and
merging two or more rows of the filter based on a density threshold, 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 filter is represented as an array with multiple dimensions in the pruning index.

### Claim 3 (depends on 1)

The system of claim 1, wherein the generating of the filter comprises:
for a given data value,
identifying a cell within the filter based on the data value;
generating a hash value based on the data value; and
populating the cell in the filter using the hash value.

### Claim 4 (depends on 3)

The system of claim 3, wherein the operations further comprise computing a number of levels in the filter;
wherein the identifying of the cell comprises:
identifying a slice in the filter based on the data value and the number of levels in the filter; and
identifying a filter column based on the data value and a number of filter columns in the filter.

### Claim 5 (depends on 1)

The system of claim 1, wherein:
each filter of the set of filters comprises multiple bloom filters, a number of bloom filters in each filter being based on a target false positive rate.

### Claim 6 (depends on 1)

The system of claim 1, wherein:
each filter in the set of filters comprises a set of bloom filters; and
the pruning index further comprises a plurality of columns, the plurality of columns comprising a batch unit identifier column, a slice number column, and the set of bloom filters.

### Claim 7 (depends on 6)

The system of claim 6, further comprising:
clustering the pruning index based on the slice number column.

### Claim 8 (depends on 7)

The system of claim 7, wherein the operations further comprise:
detecting a change to the source table;
generating one or more additional rows for the pruning index based on the change to the source table; and
reclustering the pruning index based on slice numbers.

### Claim 9 (depends on 1)

The system of claim 1, wherein the operations further comprise:
processing a query using the pruning index, the processing of the query comprising:
identifying, using the pruning index, a sub-set of batch units to scan for data matching the query; and
scanning only the sub-set of batch units of the source table to identify data matching the query.

### Claim 10 (depends on 9)

The system of claim 9, wherein the processing of the query using the pruning index comprises:
generating a hash value based on an equality predicate included in the query;
identifying one or more values in the pruning index that match the hash value; and
identifying one or more batch units that potentially satisfy the equality predicate based on the one or more values in the pruning index that match the hash value.

### Claim 11 (depends on 9)

The system of claim 9, wherein the identifying of the sub-set of batch units to scan for the data matching the query comprises identifying one or more batch units in which data matching the query is not stored.

### Claim 12 (depends on 9)

The system of claim 9, wherein the identifying of the sub-set of batch units to scan for the data matching the query comprises identifying one or more batch units in which data matching the query is potentially stored.

### Claim 13

A method comprising:
generating, by at least one hardware processor, a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:
generating a filter corresponding to a batch unit in the set of batch units; and
merging two or more rows of the filter based on a density threshold; and
storing, in a database, the pruning index with an association with the source table.

### Claim 14 (depends on 13)

The method of claim 13, wherein the filter is represented as an array with multiple dimensions in the pruning index.

### Claim 15 (depends on 13)

The method of claim 13, wherein the generating of the filter comprises:
for a given data value,
identifying a cell within the filter based on the data value;
generating a hash value based on the data value; and
populating the cell in the filter using the hash value.

### Claim 16 (depends on 13)

The method of claim 13, wherein:
each filter in the set of filters comprises a set of bloom filters; and
the pruning index further comprises a plurality of columns, the plurality of columns comprising a batch unit identifier column, a slice number column, and the set of bloom filters; and
the method further comprises clustering the pruning index based on the slice number column.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
detecting a change to the source table;
generating one or more additional rows for the pruning index based on the change to the source table; and
reclustering the pruning index based on slice numbers.

### Claim 18 (depends on 17)

The method of claim 17, wherein detecting the change to the source table comprises at least one of:
detecting a new row being added to the source table, and
detecting an existing row being removed from the source table.

### Claim 19 (depends on 13)

The method of claim 13, further comprising:
processing a query using the pruning index, the processing of the query comprising:
identifying, using the pruning index, a sub-set of batch units to scan for data matching the query; and
scanning only the sub-set of batch units of the source table to identify data matching the query.

### 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:
generating a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:
generating a filter corresponding to a batch unit in the set of batch units; and
merging two or more rows of the filter based on a density threshold; and
storing, in a database, the pruning index with an association with the source table.
