# US 2019/0171634 A1 · Accelerated filtering, grouping and aggregation in a database system

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

- Number: US 2019/0171634 A1
- Document ID: US20190171634A1
- Status: Published application
- Kind: A1
- Application number: 16/206,364
- Filed: 2018-11-30
- Published: 2019-06-06
- Earliest claimed: 2017-12-01
- Assignees: MemSQL, Inc.
- Applicants: MemSQL, Inc.
- Inventors: Michal NOWAKIEWICZ; Eric BOUTIN
- Web page: https://patentgrep.com/patent/US20190171634A1

## CPC

- G06F 16/244: {Grouping and aggregation}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/2453: Query optimisation
- G06F 16/2455: Query execution
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for causing a processor to perform a query on a column-store table of encoded values is provided. The method includes configuring the processor to receive the query, comprising a filter to be applied to at least a first column vector of the encoded values. The processor processes the query for the encoded values in the first column vector, to generate a first vector indicative of respective encoded values passing or failing the filter. The processor determines, from the first vector, an indicator of encoded values passing the filter and encoded values failing the filter, relative to the encoded values in the first column vector. The processor determines a bit length of the encoded values. The processor selects an algorithm for processing the query based on the indicator and the determined bit length of the encoded values. A system and a non-transitory, computer-readable medium are also provided.

## Claims

### Claim 1

A method for causing a processor to perform a query on a column-store table of encoded values, the method comprising configuring the processor to:
receive the query, the query comprising a filter to be applied to at least a first column vector of the encoded values;
process the query for each of the encoded values in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter;
determine, from the first vector, an indicator of encoded values passing the filter and encoded values failing the filter, relative to the encoded values in the first column vector;
determine a bit length of the encoded values in the first column vector; and
for at least a subset of the encoded values in the first column vector, select an algorithm from a plurality of algorithms for processing the query based on the indicator and the determined bit length of the encoded values.

### Claim 2 (depends on 1)

The method of claim 1, wherein the selected algorithm causes the processor to:
add bits to each of at least the subset of the encoded values in the first column vector thereby generating unpacked encoded values of the first column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector that correspond to the first subset of values; and
utilize a single instruction to output unpacked encoded values passing the filter from the first register into a filtered column vector based on the values in the second subset.

### Claim 3 (depends on 1)

The method of claim 1, wherein the selected algorithm causes the processor to:
generate a second vector comprising a plurality of consecutive integer values;
load a first subset of values into respective lanes of a first register, the first subset comprising the consecutive integer values of the second vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector;
utilize a single instruction to output integer values from the first register into a third vector based on the values in the second subset;
match the integer values of the third vector with indices of the first column vector; and
based on the match, retrieve and decode encoded values of the first column vector.

### Claim 4 (depends on 1)

The method of claim 1, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector that correspond to the first subset of values;
utilize a single instruction to update, to a constant value, unpacked encoded values in lanes of the first register that correspond to lanes of the second register that comprise an indication of failing the filter, thereby generating an updated second column vector; and
execute the query on the column-store table utilizing the updated second column vector, thereby generating a result of the query, the result including results for all groups except the group corresponding to the constant value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each unique encoded value in the second column vector, determine a count of the unique encoded value in the second column vector;
generate a plurality of subarrays, each subarray being associated with a different unique encoded value in the second column vector and having a length based on the count corresponding to the unique encoded value;
for each row of the second column vector, insert an indication of the row into one of the plurality of subarrays based on the encoded value at the row;
concatenate each of the plurality of subarrays to generate a first array;
for one of the subarrays of the first array:
match the indications of the rows in the subarray with rows of the first column vector;
based on the match, retrieve and decode encoded values of the first column vector; and
load the decoded values of the first column vector into respective lanes of a first register;
utilize a single instruction to add the decoded values in each lane of the first register to a corresponding lane in a further register, thereby generating, in the corresponding lanes of the further register, sums of decoded values from corresponding lanes of the first register.

### Claim 6 (depends on 1)

The method of claim 1, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load each of a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
for each lane of the first register, initialize a first counter in a corresponding lane of each of a plurality of further registers, such that each of the plurality of further registers holds a respective first counter for each lane of the first register and all first counters in each further register correspond to a unique unpacked encoded value of the second column vector;
for each lane of the first register, increment the first counter in the corresponding lane of one of the plurality of further registers that corresponds to the unpacked encoded value in the lane of the first register;
for each of the plurality of further registers, sum first counters in the further register and add the sum to a corresponding second counter for the corresponding unique unpacked encoded value; and
determine a third counter by subtracting the corresponding second counters from a total number of rows of the second column vector, the third counter value corresponding to a last of the unique unpacked encoded values in the second column vector.

### Claim 7 (depends on 1)

The method of claim 1, wherein the query further comprises an indication of a plurality of column vectors having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each column vector of the plurality of column vectors, load a first subset of encoded values of the column vector into respective lanes of a respective register, thereby forming a third array comprising the respective registers;
add bits to encoded values in each of the respective registers, thereby generating unpacked encoded values of the plurality of column vectors, each unpacked encoded value having a first length or a second length;
transpose the third array such that unpacked encoded values previously loaded into a single respective register are now loaded in corresponding lanes of the respective registers; and
for each respective register, utilizing a single instruction to add the unpacked encoded value in each lane of the respective register to a corresponding lane in a further register, thereby generating, in the corresponding lanes of the further register, sums of unpacked encoded values from corresponding lanes of each respective register.

### Claim 8 (depends on 1)

The method of claim 1, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
load each of a first subset of values into a plurality of registers, the first subset comprising the encoded values of the second column vector;
separate and reload bits of the encoded values in the plurality of registers such that the ith bit of each encoded value is stored in the ith register of the plurality of registers;
for at least some of the unique encoded values of the second column vector:
compare bits of each encoded value in the plurality of registers with corresponding bits of the unique encoded value;
based on the comparison, set a further bit for each encoded value having all bits matching bits of the unique encoded value;
for each further bit set, increment a fourth counter for the unique encoded value in a third array; and
determine a fifth counter in the third array by subtracting fourth counters in the third array from a total number of rows of the second column vector, the fifth counter corresponding to a last of the unique encoded values in the second column vector.

### Claim 9

A non-transitory, computer readable medium comprising code that, when executed, causes a processor to:
receive the query, the query comprising a filter to be applied to at least a first column vector of the encoded values;
process the query for each of the encoded values in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter;
determine, from the first vector, an indicator of encoded values passing the filter and encoded values failing the filter, relative to the encoded values in the first column vector;
determine a bit length of the encoded values in the first column vector; and
for at least a subset of the encoded values in the first column vector, select an algorithm from a plurality of algorithms for processing the query based on the indicator and the determined bit length of the encoded values.

### Claim 10 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the selected algorithm causes the processor to:
add bits to each of at least the subset of the encoded values in the first column vector thereby generating unpacked encoded values of the first column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector that correspond to the first subset of values; and
utilize a single instruction to output unpacked encoded values passing the filter from the first register into a filtered column vector based on the values in the second subset.

### Claim 11 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the selected algorithm causes the processor to:
generate a second vector comprising a plurality of consecutive integer values;
load a first subset of values into respective lanes of a first register, the first subset comprising the consecutive integer values of the second vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector;
utilize a single instruction to output integer values from the first register into a third vector based on the values in the second subset;
match the integer values of the third vector with indices of the first column vector; and
based on the match, retrieve and decode encoded values of the first column vector.

### Claim 12 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector that correspond to the first subset of values;
utilize a single instruction to update, to a constant value, unpacked encoded values in lanes of the first register that correspond to lanes of the second register that comprise an indication of failing the filter, thereby generating an updated second column vector; and
execute the query on the column-store table utilizing the updated second column vector, thereby generating a result of the query, the result including results for all groups except the group corresponding to the constant value.

### Claim 13 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each unique encoded value in the second column vector, determine a count of the unique encoded value in the second column vector;
generate a plurality of subarrays, each subarray being associated with a different unique encoded value in the second column vector and having a length based on the count corresponding to the unique encoded value;
for each row of the second column vector, insert an indication of the row into one of the plurality of subarrays based on the encoded value at the row;
concatenate each of the plurality of subarrays to generate a first array;
for one of the subarrays of the first array:
match the indications of the rows in the subarray with rows of the first column vector;
based on the match, retrieve and decode encoded values of the first column vector; and
load the decoded values of the first column vector into respective lanes of a first register;
utilize a single instruction to add the decoded values in each lane of the first register to a corresponding lane in a further register, thereby generating, in the corresponding lanes of the further register, sums of decoded values from corresponding lanes of the first register.

### Claim 14 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load each of a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
for each lane of the first register, initialize a first counter in a corresponding lane of each of a plurality of further registers, such that each of the plurality of further registers holds a respective first counter for each lane of the first register and all first counters in each further register correspond to a unique unpacked encoded value of the second column vector;
for each lane of the first register, increment the first counter in the corresponding lane of one of the plurality of further registers that corresponds to the unpacked encoded value in the lane of the first register;
for each of the plurality of further registers, sum first counters in the further register and add the sum to a corresponding second counter for the corresponding unique unpacked encoded value; and
determine a third counter by subtracting the corresponding second counters from a total number of rows of the second column vector, the third counter value corresponding to a last of the unique unpacked encoded values in the second column vector.

### Claim 15 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the query further comprises an indication of a plurality of column vectors having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each column vector of the plurality of column vectors, load a first subset of encoded values of the column vector into respective lanes of a respective register, thereby forming a third array comprising the respective registers;
add bits to encoded values in each of the respective registers, thereby generating unpacked encoded values of the plurality of column vectors, each unpacked encoded value having a first length or a second length;
transpose the third array such that unpacked encoded values previously loaded into a single respective register are now loaded in corresponding lanes of the respective registers; and
for each respective register, utilizing a single instruction to add the unpacked encoded value in each lane of the respective register to a corresponding lane in a further register, thereby generating, in the corresponding lanes of the further register, sums of unpacked encoded values from corresponding lanes of each respective register.

### Claim 16 (depends on 9)

The non-transitory, computer-readable medium of claim 9, wherein the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
load each of a first subset of values into a plurality of registers, the first subset comprising the encoded values of the second column vector;
separate and reload bits of the encoded values in the plurality of registers such that the ith bit of each encoded value is stored in the ith register of the plurality of registers;
for at least some of the unique encoded values of the second column vector:
compare bits of each encoded value in the plurality of registers with corresponding bits of the unique encoded value;
based on the comparison, set a further bit for each encoded value having all bits matching bits of the unique encoded value;
for each further bit set, increment a fourth counter for the unique encoded value in a third array; and
determine a fifth counter in the third array by subtracting fourth counters in the third array from a total number of rows of the second column vector, the fifth counter corresponding to a last of the unique encoded values in the second column vector.

### Claim 17

A system configured to perform a query on a column-store table of encoded values, the system comprising:
at least one register configured to hold one or more values;
at least one processor;
and a computer readable medium comprising code that, when executed, causes the processor to:
receive the query, the query comprising a filter to be applied to at least a first column vector of the encoded values;
process the query for each of the encoded values in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter;
determine, from the first vector, an indicator of encoded values passing the filter and encoded values failing the filter, relative to the encoded values in the first column vector;
determine a bit length of the encoded values in the first column vector; and
for at least a subset of the encoded values in the first column vector, select an algorithm from a plurality of algorithms for processing the query based on the indicator and the determined bit length of the encoded values.

### Claim 18 (depends on 17)

The system of claim 17, wherein the at least one register comprises a first register and a second register, the selected algorithm causing the processor to:
add bits to each of at least the subset of the encoded values in the first column vector thereby generating unpacked encoded values of the first column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of the first register, the first subset comprising the unpacked encoded values;
load a second subset of values into respective lanes of the second register, the second subset comprising values of the first vector that correspond to the first subset of values; and
utilize a single instruction to output unpacked encoded values passing the filter from the first register into a filtered column vector based on the values in the second subset.

### Claim 19 (depends on 17)

The system of claim 17, wherein the at least one register comprises a first register and a second register, the selected algorithm causing the processor to:
generate a second vector comprising a plurality of consecutive integer values;
load a first subset of values into respective lanes of a first register, the first subset comprising the consecutive integer values of the second vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector;
utilize a single instruction to output integer values from the first register into a third vector based on the values in the second subset;
match the integer values of the third vector with indices of the first column vector; and
based on the match, retrieve and decode encoded values of the first column vector.

### Claim 20 (depends on 17)

The system of claim 17, wherein the at least one register comprises a first register and a second register, and the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
load a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector that correspond to the first subset of values;
utilize a single instruction to update, to a constant value, unpacked encoded values in lanes of the first register that correspond to lanes of the second register that comprise an indication of failing the filter, thereby generating an updated second column vector; and
execute the query on the column-store table utilizing the updated second column vector, thereby generating a result of the query, the result including results for all groups except the group corresponding to the constant value.

### Claim 21 (depends on 17)

The system of claim 17, wherein the at least one register comprises a first register and a further register, and the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each unique encoded value in the second column vector, determine a count of the unique encoded value in the second column vector;
generate a plurality of subarrays, each subarray being associated with a different unique encoded value in the second column vector and having a length based on the count corresponding to the unique encoded value;
for each row of the second column vector, insert an indication of the row into one of the plurality of subarrays based on the encoded value at the row;
concatenate each of the plurality of subarrays to generate a first array;
for one of the subarrays of the first array:
match the indications of the rows in the subarray with rows of the first column vector;
based on the match, retrieve and decode encoded values of the first column vector; and
load the decoded values of the first column vector into respective lanes of the first register;
utilize a single instruction to add the decoded values in each lane of the first register to a corresponding lane in the further register, thereby generating, in the corresponding lanes of the further register, sums of decoded values from corresponding lanes of the first register.

### Claim 22 (depends on 17)

The system of claim 17, wherein the at least one register comprises a first register and a plurality of further registers, and the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
add bits to encoded values in the second column vector, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length;
load each of a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values of the second column vector;
for each lane of the first register, initialize a first counter in a corresponding lane of each of the plurality of further registers, such that each of the plurality of further registers holds a respective first counter for each lane of the first register and all first counters in each further register correspond to a unique unpacked encoded value of the second column vector;
for each lane of the first register, increment the first counter in the corresponding lane of one of the plurality of further registers that corresponds to the unpacked encoded value in the lane of the first register;
for each of the plurality of further registers, sum first counters in the further register and add the sum to a corresponding second counter for the corresponding unique unpacked encoded value; and
determine a third counter by subtracting the corresponding second counters from a total number of rows of the second column vector, the third counter value corresponding to a last of the unique unpacked encoded values in the second column vector.

### Claim 23 (depends on 17)

The system of claim 17, wherein the at least one register comprises a plurality of respective registers and a further register, and the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
for each column vector of the plurality of column vectors, load a first subset of encoded values of the column vector into respective lanes of a respective register, thereby forming a third array comprising the respective registers;
add bits to encoded values in each of the respective registers, thereby generating unpacked encoded values of the plurality of column vectors, each unpacked encoded value having a first length or a second length;
transpose the third array such that unpacked encoded values previously loaded into a single respective register are now loaded in corresponding lanes of the respective registers; and
for each respective register, utilizing a single instruction to add the unpacked encoded value in each lane of the respective register to a corresponding lane in the further register, thereby generating, in the corresponding lanes of the further register, sums of unpacked encoded values from corresponding lanes of each respective register.

### Claim 24 (depends on 17)

The system of claim 17, wherein the at least one register comprises a plurality of registers, and the query further comprises an indication of a second column vector having encoded values by which a result of the query is to be grouped, the selected algorithm causing the processor to:
load each of a first subset of values into a plurality of registers, the first subset comprising the encoded values of the second column vector;
separate and reload bits of the encoded values in the plurality of registers such that the ith bit of each encoded value is stored in the ith register of the plurality of registers;
for at least some of the unique encoded values of the second column vector:
compare bits of each encoded value in the plurality of registers with corresponding bits of the unique encoded value;
based on the comparison, set a further bit for each encoded value having all bits matching bits of the unique encoded value;
for each further bit set, increment a fourth counter for the unique encoded value in a third array; and
determine a fifth counter in the third array by subtracting fourth counters in the third array from a total number of rows of the second column vector, the fifth counter corresponding to a last of the unique encoded values in the second column vector.
