# US 11,308,089 B2 · Pruning index maintenance

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

- Number: US 11,308,089 B2
- Document ID: US11308089B2
- Status: Granted
- Kind: B2
- Application number: 17/358,154
- Filed: 2021-06-25
- Published: 2021-10-14
- Granted: 2022-04-19
- 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/US11308089B2

## 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:
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 values in each column of the source table, the set of filters being represented as an array with multiple dimensions in the pruning index, the pruning index being organized into a plurality of rows and a plurality of columns;
clustering the plurality of rows in the pruning index based on values in a column of the plurality of columns;
detecting a change to the source table;
generating one or more new rows in the pruning index based on the change to the source table; and
based on generating the one or more rows, reclustering the pruning index based on the values in the column of the plurality of columns.

### Claim 2 (depends on 1)

The system of claim 1, wherein the plurality of columns comprise a batch unit identifier column, a slice number column, and a set of bloom filters.

### Claim 3 (depends on 2)

The system of claim 2, wherein the clustering of the pruning index is based on the slice number column.

### Claim 4 (depends on 3)

The system of claim 3, wherein the reclustering of the pruning index is based on the slice number column.

### Claim 5 (depends on 4)

The system of claim 4, wherein the reclustering of the pruning index is in response to determining a threshold number of rows have been added to the pruning index.

### Claim 6 (depends on 4)

The system of claim 4, wherein the reclustering of the pruning index is performed at a regular interval.

### Claim 7 (depends on 1)

The system of claim 1, 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 8 (depends on 1)

The system of claim 1, wherein:
the generating of the pruning index comprises generating the set of filters, each filter in the set of filters corresponding to a batch unit in the set of batch units,
the generating of the set of filters comprises generating a first filter for a first batch unit of the set of batch units in the source table, and
the first filter indexes distinct values in each column of the first batch unit.

### Claim 9 (depends on 8)

The system of claim 8, 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 10 (depends on 9)

The system of claim 9, wherein:
the operations further comprise computing a number of levels in the first filter; and
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 11 (depends on 1)

The system of claim 1, wherein the operations further comprise storing, in a database, the pruning index with an association with the source table.

### Claim 12 (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 13 (depends on 12)

The system of claim 12, 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 14

A method 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 values in each column of the source table, the set of filters being represented as an array with multiple dimensions in the pruning index, the pruning index being organized into a plurality of rows and a plurality of columns;
clustering the plurality of rows in the pruning index based on values in a column of the plurality of columns;
detecting a change to the source table;
generating one or more new rows in the pruning index based on the change to the source table; and
based on generating the one or more rows, reclustering the pruning index based on the values in the column of the plurality of columns.

### Claim 15 (depends on 14)

The method of claim 14, wherein the plurality of columns comprise a batch unit identifier column, a slice number column, and a set of bloom filters.

### Claim 16 (depends on 15)

The method of claim 15, wherein the clustering of the pruning index is based on the slice number column.

### Claim 17 (depends on 16)

The method of claim 16, wherein the reclustering of the pruning index is based on the slice number column.

### Claim 18 (depends on 17)

The method of claim 17, wherein the reclustering of the pruning index is in response to determining a threshold number of rows have been added to the pruning index.

### Claim 19 (depends on 17)

The method of claim 17, wherein the reclustering of the pruning index is performed at a regular interval.

### Claim 20 (depends on 14)

The method of claim 14, 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 21

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 values in each column of the source table, the set of filters being represented as an array with multiple dimensions in the pruning index, the pruning index being organized into a plurality of rows and a plurality of columns;
clustering the plurality of rows in the pruning index based on values in a column of the plurality of columns;
detecting a change to the source table;
generating one or more new rows in the pruning index based on the change to the source table; and
based on generating the one or more rows, reclustering the pruning index based on the values in the column of the plurality of columns.

### Claim 22 (depends on 21)

The computer-storage medium of claim 21, wherein the plurality of columns comprises a batch unit identifier column, a slice number column, and a set of bloom filters.

### Claim 23 (depends on 22)

The computer-storage medium of claim 22, wherein the clustering of the pruning index is based on the slice number column.

### Claim 24 (depends on 23)

The computer-storage medium of claim 23, wherein the reclustering of the pruning index is based on the slice number column.

### Claim 25 (depends on 24)

The computer-storage medium of claim 24, wherein the reclustering of the pruning index is in response to determining a threshold number of rows have been added to the pruning index.

### Claim 26 (depends on 24)

The computer-storage medium of claim 24, wherein the reclustering of the pruning index is performed at a regular interval.