# US 2021/0240670 A1 · Efficient database query evaluation

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

- Number: US 2021/0240670 A1
- Document ID: US20210240670A1
- Status: Published application
- Kind: A1
- Application number: 16/779,366
- Filed: 2020-01-31
- Published: 2021-08-05
- Earliest claimed: 2020-01-31
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc
- Inventors: Selcuk Aya; Bowei Chen; Florian Andreas Funke
- Web page: https://patentgrep.com/patent/US20210240670A1

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Data in a micro-partition of a table is stored in a compressed form. In response to a database query on the table comprising a filter, the portion of the data on which the filter operates is decompressed, without decompressing other portions of the data. Using the filter on the decompressed portion of the data, the portions of the data that are responsive to the filter are determined and decompressed. The responsive data is returned in response to the database query. When a query is run on a table that is compressed using dictionary compression, the uncompressed data may be returned along with the dictionary look-up values. The recipient of the data may use the dictionary look-up values for memoization, reducing the amount of computation required to process the returned data.

## Claims

### Claim 1

A system comprising:
a memory that stores instructions; and
one or more processors configured by the instructions to perform operations comprising:
accessing an operation for a table of a database, the operation for the table comprising a filter on a first column of the table, the table being stored in a plurality of micro-partitions, a micro-partition of the plurality of micro-partitions being compressed;
decompressing, in the micro-partition, the first column of the table without decompressing other columns of the table in the micro-partition;
decompressing, based on the filter on the first column, rows of the micro-partition of the table that contains data responsive to the filter without decompressing other rows of the micro-partition of the table that contains data not responsive to the filter; and
providing, in response to the operation for the table, the decompressed rows of the micro-partition.

### Claim 2 (depends on 1)

The system of claim 1, wherein each micro-partition of the plurality of micro-partitions is a file on a file system.

### Claim 3 (depends on 1)

The system of claim 1, wherein the filter comprises a value for the first column.

### Claim 4 (depends on 1)

The system of claim 1, wherein decompressing the first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining an uncompressed value for each compressed value of the entries in the micro-partition.

### Claim 5 (depends on 4)

The system of claim 4, wherein the operations further comprise:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition.

### Claim 6 (depends on 5)

The system of claim 5, wherein the operations further comprise:
accessing a second operation for the table, the second operation comprising determining a computation result on the first column of the table;
computing, for a first entry in the rows of the micro-partition, the computation result on a value of the first column of the first entry;
storing the computation result for the first entry in conjunction with the compressed value for the first entry; and
based on the compressed value for a second entry of the table being identical to the compressed value for the first entry, accessing the stored computation result for the first entry instead of computing the computation result on the value for the second entry.

### Claim 7 (depends on 1)

The system of claim 1, wherein the operations further comprise:
performing an aggregation operation on the table by performing operations comprising:
aggregating entries in the table to create a first aggregated data structure comprising aggregated entries;
based on a predetermined threshold and a number of entries in the first aggregated data structure:
transferring the aggregated entries from the first aggregated data structure to a second aggregated data structure; and
clearing the aggregated entries in the first aggregated data structure; and
resuming aggregating the entries in the table in the first aggregated data structure.

### Claim 8 (depends on 7)

The system of claim 7, wherein decompressing the first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining the uncompressed value for each compressed value of the entries in the micro-partition;
the operations further comprise:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition; and
wherein the aggregating of the entries in the table to create the first aggregated data structure determines to combine a first entry with a second entry based on the compressed value of the first entry being identical to the compressed value of the second entry.

### Claim 9 (depends on 1)

The system of claim 1, wherein:
a second micro-partition of the plurality of micro-partitions is compressed using compression different from the compression of the micro-partition;
the operations further comprise:
decompressing a first column in the second micro-partition without decompressing other columns of the table in the second micro-partition; and
decompressing, based on the filter on the first column, rows of the second micro-partition containing data responsive to the filter without decompressing other rows of the second micro-partition containing data not responsive to the filter; and
combining the decompressed rows of the micro-partition with the decompressed rows of the second micro-partition for provision in response to the operation for the table.

### Claim 10

A non-transitory machine-readable medium that stores instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
accessing an operation for a table of a database, the operation for the table comprising a filter on a first column of the table, the table being stored in a plurality of micro-partitions, a micro-partition of the plurality of micro-partitions being compressed;
decompressing, in the micro-partition, the first column of the table without decompressing other columns of the table in the micro-partition;
decompressing, based on the filter on the first column, rows of the micro-partition of the table that contains data responsive to the filter without decompressing other rows of the micro-partition of the table that contains data not responsive to the filter; and
providing, in response to the operation for the table, the decompressed rows of the micro-partition.

### Claim 11 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein each micro-partition of the plurality of micro-partitions is a file on a file system.

### Claim 12 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the filter comprises a value for the first column.

### Claim 13 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein decompressing first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining an uncompressed value for each compressed value of the entries in the micro-partition.

### Claim 14 (depends on 13)

The non-transitory machine-readable medium of claim 13, wherein the operations further comprise:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition.

### Claim 15 (depends on 14)

The non-transitory machine-readable medium of claim 14, wherein the operations further comprise:
accessing a second operation for the table, the second operation comprising determining a computation result on the first column of the table;
computing, for a first entry in the rows of the micro-partition, the computation result on the first column of the table;
storing the computation result for the first entry in conjunction with the compressed value for the first column; and
based on the compressed value for a second entry of the table being identical to the compressed value for the first entry, accessing the stored computation result for the first entry instead of computing the computation result for the second entry.

### Claim 16 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein the operations further comprise:
performing an aggregation operation on the table by performing operations comprising:
aggregating entries in the table to create a first aggregated data structure comprising aggregated entries;
based on a predetermined threshold and a number of entries in the first aggregated data structure:
transferring the aggregated entries from the first aggregated data structure to a second aggregated data structure; and
clearing the aggregated entries in the first aggregated data structure; and
resuming aggregating the entries in the table in the first aggregated data structure.

### Claim 17 (depends on 16)

The non-transitory machine-readable medium of claim 16, wherein decompressing the first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining the uncompressed value for each compressed value of the entries in the micro-partition;
and wherein the operations further comprise:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition; and
wherein the aggregating of the entries in the table to create the first aggregated data structure determines to combine a first entry with a second entry based on the compressed value of the first entry being identical to the compressed value of the second entry.

### Claim 18 (depends on 10)

The non-transitory machine-readable medium of claim 10, wherein:
a second micro-partition of the plurality of micro-partitions is compressed using compression different from the compression of the micro-partition;
the operations further comprise:
decompressing a first column in the second micro-partition without decompressing other columns of the table in the second micro-partition; and
decompressing, based on the filter on the first column, rows of the second micro-partition containing data responsive to the filter without decompressing other rows of the second micro-partition containing data not responsive to the filter; and
combining the decompressed rows of the micro-partition with the decompressed rows of the second micro-partition for provision in response to the operation for the table.

### Claim 19

A method comprising:
accessing, by one or more processors, an operation for a table of a database, the operation comprising a filter on a first column of the table, the table being stored in a plurality of micro-partitions, a micro-partition of the plurality of micro-partitions being compressed;
decompressing, in the micro-partition, the first column of the table without decompressing other columns of the table in the micro-partition;
decompressing, based on the filter on the first column, rows of the micro-partition of the table that contains data responsive to the filter without decompressing other rows of the micro-partition of the table that contains data not responsive to the filter; and
providing, in response to the operation for the table, the decompressed rows of the micro-partition.

### Claim 20 (depends on 19)

The method of claim 19, wherein each micro-partition of the plurality of micro-partitions is a file on a file system.

### Claim 21 (depends on 19)

The method of claim 19, wherein the filter comprises a value for the first column.

### Claim 22 (depends on 19)

The method of claim 19, wherein decompressing the first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining an uncompressed value for each compressed value of the entries in the micro-partition.

### Claim 23 (depends on 22)

The method of claim 22, further comprising:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition.

### Claim 24 (depends on 23)

The method of claim 23, further comprising:
accessing a second operation for the table, the second operation comprising determining a computation result on the first column of the table;
computing, for a first entry in the rows of the micro-partition, the computation result on the first column of the table;
storing the computation result for the first entry in conjunction with the compressed value for the first column; and
based on the compressed value for a second entry of the table being identical to the compressed value for the first entry, accessing the stored computation result for the first entry instead of computing the computation result for the second entry.

### Claim 25 (depends on 19)

The method of claim 19, further comprising:
performing an aggregation operation on the table by performing operations comprising:
aggregating entries in the table to create a first aggregated data structure comprising aggregated entries;
based on a predetermined threshold and a number of entries in the first aggregated data structure:
transferring the aggregated entries from the first aggregated data structure to a second aggregated data structure; and
clearing the aggregated entries in the first aggregated data structure; and
resuming aggregating the entries in the table in the first aggregated data structure.

### Claim 26 (depends on 25)

The method of claim 25, wherein decompressing the first column comprises:
accessing a compressed value for each entry in the micro-partition for the first column;
accessing a dictionary that maps compressed values to uncompressed values; and
using the dictionary, determining the uncompressed value for each compressed value of the entries in the micro-partition;
further comprising:
providing, in response to the operation for the table, the compressed value for the first column for each entry in the decompressed rows of the micro-partition; and
wherein the aggregating of the entries in the table to create the first aggregated data structure determines to combine a first entry with a second entry based on the compressed value of the first entry being identical to the compressed value of the second entry.

### Claim 27 (depends on 19)

The method of claim 19, wherein:
a second micro-partition of the plurality of micro-partitions is compressed using compression different from the compression of the micro-partition; and
the method further comprises
decompressing a first column in the second micro-partition without decompressing other columns of the table in the second micro-partition; and
decompressing, based on the filter on the first column, rows of the second micro-partition containing data responsive to the filter without decompressing other rows of the second micro-partition containing data not responsive to the filter; and
combining the decompressed rows of the micro-partition with the decompressed rows of the second micro-partition for provision in response to the operation for the table.