# US 10,769,150 B1 · Pruning indexes to enhance database query processing

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

- Number: US 10,769,150 B1
- Document ID: US10769150B1
- Status: Granted
- Kind: B1
- Application number: 16/727,315
- Filed: 2019-12-26
- Granted: 2020-09-08
- 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/US10769150B1

## 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 network-based data warehouse system comprising:
at least one hardware processor; and
a memory storing instructions that cause the at least one hardware processor to perform operations comprising:
accessing a source table organized into a set of micro-partitions;
generating a pruning index based on the source table, the pruning index comprising a set of filters that index distinct values in each column of the source table, the generating of the pruning index comprising generating the set of filters, each filter in the set of filters corresponding to a micro-partition in the set of micro-partitions and being represented as a two-dimensional array in the pruning index;
receiving a query directed to the source table; and
processing the query using the pruning index, the processing of the query comprising pruning the set of micro-partitions of the source table to scan for data matching the query, the pruning of the set of micro-partitions comprising identifying, using the pruning index, a sub-set of micro-partitions to scan for the data matching the query.

### Claim 2 (depends on 1)

The network-based data warehouse system of claim 1, wherein the generating of the pruning index comprises:
generating a first filter for a first micro-partition of the set of micro-partitions in the source table, the first filter indexing distinct values in each column of the first micro-partition.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 3)

The network-based data warehouse system of claim 3, wherein the generating of the first filter further comprises:
merging one or more rows of the first filter based on a target false positive rate.

### Claim 6 (depends on 1)

The network-based data warehouse 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 micro-partition identifier column, a slice number column, and the set of bloom filters.

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 1)

The network-based data warehouse system of claim 1, wherein:
each filter of the set of filters comprises multiple bloom filters, a number of bloom filters in each blocked bloom filter being based on a false positive rate constraint.

### Claim 9 (depends on 1)

The network-based data warehouse system of claim 1, 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 micro-partitions that potentially satisfy the equality predicate based on the one or more values in the pruning index that match the hash value.

### Claim 10 (depends on 1)

The network-based data warehouse system of claim 1, 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 number.

### Claim 11 (depends on 1)

The network-based data warehouse system of claim 1, wherein the operations further comprise:
scanning the sub-set of micro-partitions of the source table to identify data matching the query.

### Claim 12 (depends on 11)

The network-based data warehouse system of claim 11, wherein the identifying of the sub-set of micro-partitions to scan for the data matching the query comprises identifying one or more micro-partitions in which data matching the query is potentially stored.

### Claim 13

A method comprising:
accessing a source table organized into a set of micro-partitions;
generating, by one or more hardware processors of a computer, a pruning index based on the source table, the pruning index comprising a set of filters that index distinct values in each column of the source table, the generating of the pruning index comprising generating the set of filters, each filter in the set of filters corresponding to a micro-partition in the set of micro-partitions and being represented as a two-dimensional array in the pruning index;
receiving a query directed to the source table; and
processing the query using the pruning index, the processing of the query comprising pruning the set of micro-partitions of the source table to scan for data matching the query, the pruning of the set of micro-partitions comprising identifying, using the pruning index, a sub-set of micro-partitions to scan for the data matching the query.

### Claim 14 (depends on 13)

The method of claim 13, wherein the generating of the pruning index comprises:
generating a first filter for a first micro-partition in the set of micro-partitions of the source table, the first filter indexing distinct values in each column of the first micro-partition.

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 15)

The method of claim 15, wherein the generating of the pruning index comprises:
computing a number of levels in the first filter;
wherein the identifying of the cell comprises:
identifying a slice in the first filter based on the data value and the number of levels in the first filter; and
identifying a filter column based on the data value and a predetermined number of filter columns in the first filter.

### Claim 17 (depends on 16)

The method of claim 16, wherein the generating of the first filter further comprises:
merging one or more rows of the first filter based on a target false positive rate.

### Claim 18 (depends on 13)

The method of claim 13, wherein:
each filter in the set of filters comprises a set of bloom filters;
the pruning index further comprises a plurality of columns, the plurality of columns comprising a micro-partition identifier column, a slice number column, and the set of bloom filters; and
the pruning index is clustered on the slice number columns.

### Claim 19 (depends on 13)

The method of claim 13, wherein each filter of the set of filters comprises multiple bloom filters, a number of bloom filters in each blocked bloom filter being based on a false positive rate constraint.

### Claim 20 (depends on 13)

The method of claim 13, 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 micro-partitions that potentially satisfy the equality predicate based on the one or more values in the pruning index that match the hash value.

### Claim 21 (depends on 13)

The method of claim 13, 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 number.

### Claim 22 (depends on 13)

The method of claim 13, further comprising:
scanning the sub-set of micro-partitions of the source table to identify data matching the query.

### Claim 23 (depends on 22)

The method claim 22, wherein the identifying of the sub-set of micro-partitions to scan for the data matching the query comprises identifying one or more micro-partitions in which data matching the query is potentially stored.

### Claim 24

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 micro-partitions;
generating a pruning index based on the source table, the pruning index comprising a set of filters that index distinct values in each column of the source table, the generating of the pruning index comprising generating the set of filters, each filter in the set of filters corresponding to a micro-partition in the set of micro-partitions and being represented as a two-dimensional array in the pruning index;
receiving a query directed to the source table; and
processing the query using the pruning index, the processing of the query comprising pruning the set of micro-partitions of the source table to scan for data matching the query, the pruning of the set of micro-partitions comprising identifying, using the pruning index, a sub-set of micro-partitions to scan for the data matching the query.

### Claim 25 (depends on 24)

The computer-storage medium of claim 24, wherein the generating of the pruning index comprises:
generating a first filter for a first micro-partition in the set of micro-partitions of the source table, the first filter indexing distinct values in each column of the first micro-partition.

### Claim 26 (depends on 24)

The computer-storage medium of claim 24, wherein the generating of the first filter comprises:
for a given data value,
identifying a cell within the first filter based on the data value;
generating a hash value based on the data value; and
populating the cell in the first filter using the hash value.

### Claim 27 (depends on 26)

The computer-storage medium of claim 26, wherein the generating of the pruning index comprises:
computing a number of levels in the first filter;
wherein the identifying of the cell comprises:
identifying a slice in the first filter based on the data value and the number of levels in the first filter; and
identifying a filter column based on the data value and a number of filter columns in the first filter.

### Claim 28 (depends on 24)

The computer-storage medium of claim 24, wherein:
each filter in the set of filters comprises a set of bloom filters;
the pruning index further comprises a plurality of columns, the plurality of columns comprising a micro-partition identifier column, a slice number column, and the set of bloom filters; and
the pruning index is clustered on the slice number columns.

### Claim 29 (depends on 24)

The computer-storage medium of claim 24, 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 micro-partitions that potentially satisfy the equality predicate based on the one or more values in the pruning index that match the hash value.

### Claim 30 (depends on 24)

The computer-storage medium of claim 24, 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 number.