Patent Description:
As technologies advance, the amount of information stored in electronic form and the desire for real-time or pseudo real-time ability to search such information is ever increasing. Database management systems are designed to organize data in a form that facilitates efficient search and retrieval of select information. Typical database management systems allow a user to submit a "query" in a query language for retrieving information that satisfies particular search parameters.

In known database management systems, a particular query may be processed against data within a database, utilizing a static algorithm or process that is based on the query, without regard for particular features of the query. Because the data against which the query is processed may be extremely large, e.g., hundreds of millions or billions of individual entries, such a static algorithm or process typically takes one or more orders of magnitude more clock cycles than there are individual entries to return a result to the query, making query response time unacceptably large. Accordingly, it would be advantageous to reduce the time required to return results of user queries against database management systems.

<NPL> provides an overview of the differences between column store and row store databases. <NPL> provides applying compression schemes on column-oriented systems.

One aspect provides a method for causing a processor to perform a query on a column-store table of encoded values. The method includes 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, the first column vector comprising a plurality of contiguous segments, each segment being encoded separately from segments of another column vector of the column-store table. The method includes configuring the processor to process the query for a batch of encoded values in a segment in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter. The method includes configuring the processor to determine, from the first vector, a selectivity indicator of the filter for the encoded values in the batch, the selectivity indicator indicating encoded values passing the filter relative to the encoded values in the batch of the segment of the first column vector or encoded values failing the filter relative to the encoded values in the batch of the segment of the first column vector. The method includes configuring the processor to determine a bit length for encoding of the encoded values in the segment of the first column vector. The method includes configuring the processor to, for the batch of the encoded values, select an algorithm from a plurality of algorithms for processing the query based on the selectivity indicator and the determined bit length of the encoded values in the segment of the first column vector.

Another aspect provides 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, the first column vector comprising a plurality of contiguous segments, each segment being encoded separately from segments of another column vector of the column-store table. The code, when executed, causes the processor to process the query for a batch of encoded values in a segment in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter. The code, when executed, causes the processor to determine, from the first vector, a selectivity indicator of the filter for the encoded values in the batch, the selectivity indicator indicating encoded values passing the filter relative to the encoded values in the batch of the segment of the first column vector or encoded values failing the filter relative to the encoded values in the batch of the segment of the first column vector. The code, when executed, causes the processor to determine a bit length for encoding of the encoded values in the segment of the first column vector. The code, when executed, causes the processor to for the batch of encoded values, select an algorithm from a plurality of algorithms for processing the query based on the selectivity indicator and the determined bit length of the encoded values in the segment of the first column vector.

Another aspect provides a system configured to perform a query on a column-store table of encoded values. The system includes at least one register configured to hold one or more values. The system includes at least one processor. The system includes 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, the first column vector comprising a plurality of contiguous segments, each segment being encoded separately from segments of another column vector of the column store table. The code, when executed, causes the processor to process the query for a batch of encoded values in a segment in the first column vector, whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter. The code, when executed, causes the processor to determine, from the first vector, a selectivity indicator of the filter for the encoded values in the batch, the selectivity indicator indicating encoded values passing the filter relative to the encoded values in the batch of the segment of the first column vector or encoded values failing the filter relative to the encoded values in the batch of the segment of the first column vector. The code, when executed, causes the processor to determine a bit length for encoding of the encoded values in the first column vector. The code, when executed, causes the processor to, for the batch of encoded values , select an algorithm from a plurality of algorithms for processing the query based on the selectivity indicator and the determined bit length of the encoded values in the segment of the first column vector.

The scope of the invention is defined by the independent claims. In the following description, for purposes of explanation rather than limitation, specific details are set forth such as the particular architecture, interfaces, techniques, etc., in order to provide a thorough understanding of the concepts described herein. However, it will be apparent to those skilled in the art that the other embodiments may be practiced, which depart from these specific details. Similarly, the present application is directed to example embodiments as illustrated in the FIGs. , and is not intended as limiting beyond the terms expressly included in the claims. For purposes of simplicity and clarity, detailed descriptions of well-known devices and methods are omitted so as not to obscure the description with unnecessary detail. However, the lack of any description for any particular device or method does not necessarily indicate that it or its function are well-known.

describe example query processing systems using the paradigm of a database query system that processes queries formed using the operations and format of the standard Structured Query Language (SQL). One of skill in the art will recognize, however, that the principles described herein may be applied for the processing of queries in other programming and query languages as well.

<FIG> is a block diagram illustrating a system <NUM> for executing a query made against a collection of data, in accordance with some embodiments. System <NUM> includes a central processing unit (CPU) <NUM>, memory <NUM>, and storage <NUM>. CPU <NUM> includes a processor <NUM>, at least one cache <NUM>, a clock <NUM> and a plurality of registers 104a, 104b. 104n (104a-104n). In some embodiments, one or more registers, including registers 104a-104n, described herein may be single instruction multiple data (SIMD) registers. However, the present disclosure contemplates the use of any type of data register having capacities of any number of bits.

Each of registers 104a-104n may be configured to hold data received from one another and/or from one or more of processor <NUM>, cache <NUM>, memory <NUM>, or storage <NUM>. Each of registers 104a-104n may be a <NUM>-bit register, configured to store up to <NUM> bits of data on which one or more operations are simultaneously conducted by, e.g., processor <NUM>. However, registers 104a-104n are not so limited and may have any other number of bits and/or may be any other type of register.

Processor <NUM> is configured to perform one or more operations or instructions for processing a query on data held in at least one of registers 104a-104n, ultimately retrieved from one or more of cache <NUM>, memory <NUM> or storage <NUM>, or data while held in one or more of cache <NUM>, memory <NUM> or storage <NUM>. In some embodiments, such instructions may be single input multiple data (SIMD) instructions compatible with advanced vector extensions (AVX) such as AVX2, which expands most integer commands to <NUM> bits, AVX512, which expands most integer commands to <NUM> bits, or any other extension of integer commands to any number of bits.

Clock <NUM> is configured to provide a train of clock signals for timing, controlling, and conducting computer operations within system <NUM>.

Cache <NUM> may comprise a data store located physically closer to processor <NUM> than either memory <NUM> or storage <NUM>. In some embodiments, cache <NUM> may have a smaller storage capacity than either memory <NUM> or storage <NUM>, but particular data may be read from or written to cache <NUM> in a shorter period of time than that particular data could otherwise be read from or written to either memory <NUM> or storage <NUM>.

Memory <NUM> may comprise a data store separate from cache <NUM> and storage <NUM>, such as random-access memory (RAM), from which data stored thereon may be accessed. In some embodiments, memory <NUM> may have a greater storage capacity than cache <NUM> and a smaller storage capacity than storage <NUM>. In some embodiments, particular data may be read from or written to memory <NUM> in a shorter period of time than that particular data could otherwise be read from or written to storage <NUM>, but may take a longer period of time to read from or write to than that particular data could otherwise be read from or written to cache <NUM>.

Storage <NUM> may comprise a data store separate from cache <NUM> and memory <NUM>, such as a hard drive or database server, from which data stored thereon may be accessed. In some embodiments, storage <NUM> may have a greater storage capacity than either cache <NUM> or memory <NUM>, however, particular data may take a longer period of time to read from or write to storage <NUM> than that particular data could otherwise be read from or written to either cache <NUM> or memory <NUM>.

Although CPU <NUM> is illustrated as having one processor <NUM>, cache <NUM>, clock <NUM> and set of registers 104a-104n, the present disclosure is not so limited, and a plurality of such features may be present in each of one or more CPUs, e.g., providing one or more multi-core processors for system <NUM>. Moreover, any discussion of operations performed by processor <NUM> may indicate operations performed by a single processor <NUM>, or operations performed by different processors of a plurality of similar processors.

<FIG> is a block diagram illustrating <NUM> including several modules or engines, which may be incorporated into system <NUM> of <FIG>, in accordance with some embodiments.

Diagram <NUM> includes a decoding engine <NUM> configured to decode one or more items of encoded data. Diagram <NUM> further includes a filtering engine <NUM> configured to filter one or more sets of data according to a set of filter parameters defined by a query <NUM>. Diagram <NUM> further includes a groupID mapping engine <NUM> configured to map one or more group IDs from one or more sets of data that are to be to be grouped according to the set of parameters defined by query <NUM>. Diagram <NUM> further includes an aggregating engine <NUM> configured to aggregate one or more data values to provide a resulting output <NUM> based on the set of parameters defined by query <NUM>. In some embodiments, one or more of decoding engine <NUM>, filtering engine <NUM>, groupID mapping engine <NUM>, and aggregating engine <NUM> may be embodied by at least a portion of processor <NUM> (see <FIG>) and/or another processor similar to processor <NUM> of system <NUM>.

In some embodiments, a table <NUM> comprises data against which query <NUM> is performed. Table <NUM> may comprise encoded data stored in a column-store format. For example, in column-store format, each of one or more columns <NUM> of encoded data hold values for a particular field and are stored in a corresponding location in memory, e.g., in memory <NUM> and/or storage <NUM> (see <FIG>). In some embodiments, columns <NUM> may each comprise billions of rows of encoded data, or more. Accordingly, each column <NUM> is divided into a plurality of contiguous segments <NUM> of, e.g., <NUM> million (M) rows of encoded data. Each segment <NUM> of a given column <NUM> is encoded separately from each other segment <NUM> of another column <NUM>, utilizing encoding techniques such as dictionary encoding, run length encoding, or integer value encoding, though other encoding techniques are also contemplated.

Dictionary encoding comprises mapping instances of identical recurring bits within raw data to corresponding integers within a corresponding dictionary, and then replacing the recurring bits with the corresponding integers, thereby decreasing the number of bits required to describe the raw data. A dictionary may be taken to mean a collection of objects that maps in one or both directions between raw data values and integer serial numbers for those values. An example unencoded table is shown in Table <NUM> below.

Since each segment <NUM> of each column <NUM> ("division", "state", "sale_amt") may be encoded utilizing its own dictionary of values, Table <NUM> shows an example dictionary for the "division" column, Table <NUM> shows an example dictionary for the "state" column, and Table <NUM> shows an example dictionary for the "sale_amt" column.

The dictionary of Table <NUM> has two different raw values (east / west) and so encoding may be accomplished using <NUM> bit. The dictionary of Table <NUM> has <NUM> different raw values (New York / California / Florida / Washington / Nevada) and so encoding may be accomplished using <NUM> bits. The dictionary of Table <NUM> has <NUM> raw values (<NUM>,<NUM> / <NUM>,<NUM> / <NUM>,<NUM> / <NUM>,<NUM>) and so encoding may be accomplished using <NUM> bits. Accordingly, using the dictionaries of Tables <NUM>-<NUM>, the data shown in Table <NUM> may be dictionary encoded as shown in Table <NUM>. Such Dictionary encoding may be utilized for any data type, e.g. integer, string, etc..

Run length encoding comprises indicating a plurality of repeating values by indicating the smallest unit of the repeating digits followed by an integer number indicating the number of times the smallest unit is consecutively repeated. For example, WWWWWWWWWWWWBBBBBBBBBBBB would be encoded as W12B12, reducing <NUM> characters to <NUM>. Similarly, WWBWWBWWBWWB would be encoded as WWB4, reducing <NUM> characters to <NUM>. Although this example of run length encoding is shown utilizing ASCII characters, such data may also, typically, ultimately be stored in binary form.

For purposes of the present disclosure, queries <NUM> performed against encoded data in table <NUM> are performed by evaluating the encoded data in segments <NUM> of columns <NUM> of table <NUM> in batches <NUM>. For example, batch <NUM> may comprises a moving window of a fixed number of rows, e.g. up to <NUM> rows, of each column <NUM>. Each batch is processed entirely before advancing to the next batch of rows and previously processed batches are not revisited during processing of the same query or subquery.

Accordingly, one or more of decoding engine <NUM>, filtering engine <NUM>, groupID mapping engine <NUM>, and aggregating engine <NUM> may process each batch <NUM> sequentially according to the parameters of the particular query or subquery <NUM>. In some embodiments, such processing may include loading encoded data from each batch <NUM> into registers 104a-104n and processing that data at least in part as described below in connection with any of the figures herein. However, any operation described herein having data of any type loaded and/or manipulated in a register may alternatively operate on the data while stored in an array or other type of data structure, such as cache <NUM>, memory <NUM> or storage <NUM>.

In performing such processing, one or more of decoding engine <NUM>, filtering engine <NUM>, groupID mapping engine <NUM>, and aggregating engine <NUM> may utilize a set of functions, e.g. C programming language functions within vector toolbox <NUM>, configured to simultaneously carry out particular operations on all data held in one or more column vectors, associated dictionaries, and aggregation dictionaries at a particular time. In some embodiments, portions of data in one or more column vectors may optionally be stored and manipulated in registers, such as registers 104a-104n (<FIG>). In some embodiments, such functions may include selection functions, which gather values according to parameters of query or subquery <NUM> while preserving their encoding, as will be described below. Such functions may further include concatenation functions, which may concatenate data from more than one column of table <NUM>, as will be described below. Such concatenation may, in some cases, combine data encoded utilizing different encoding schemes, e.g. RLE and dictionary encoding. Such functions may further include aggregation functions, which may include grouping data based on one or more parameters of query or subquery <NUM> and/or performing an operation that requires aggregating multiple values, e.g. determining a count, sum, average, minimum, maximum, standard deviation, median, mode, etc., of items passing a particular filter and belonging to a particular group, as will be described below. Such functions may further include dictionary encoding and decoding functions, e.g. generating and utilizing dictionaries.

<FIG> illustrates a flowchart <NUM> of a process for performing a query <NUM> on a table <NUM> of encoded values, in accordance with some embodiments. Although certain steps or actions are described in connection with <FIG>, a process for performing a query <NUM> on a table <NUM> of encoded values may include fewer than all steps described, and/or additional or alternative steps to those described.

In some embodiments, flowchart <NUM> may be utilized to process a query or subquery <NUM> that includes both a selection, e.g., selecting a subset of values in one or more columns <NUM> of table <NUM> based on one or more parameters of the query or subquery <NUM>, and a grouping and aggregation of the subset of values identified by the selection, e.g. sorting and performing an aggregating operation such as sum, minimum, maximum, average, standard deviation, median, mode, etc., on the selected subset of values based on one or more parameters of the query or subquery <NUM>.

Block <NUM> includes receiving a query, the query including a filter to be applied to at least a first column vector of encoded values. For example, processor <NUM> (<FIG>) may receive query <NUM> (<FIG>). Query <NUM> may include a filter to be applied to at least one column vector of encoded values of columns <NUM> of table <NUM>. A non-limiting example of such a query is shown below:
Select state, sum(sale_amt)
From table_of_sales
Where division=='east'
Group by state
This example query selects entries from the table "table_of_sales" where the division is "east" and indicates the output result should be the sum of "sale_amt" for each "state", grouped by "state". Thus, in such an example query where division==' east' would be the filter or selection, sum (sale_amt) would be the aggregation (a sum), and Group by state would be the indication of how the result should be grouped, or sorted.

Block <NUM> includes processing 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. For example, processor <NUM> (<FIG>) may be configured to generate a first vector (alternatively described herein as a selection byte vector) that indicates whether each row in batch <NUM> satisfies the filter parameters via a first value (e.g. 0x00 or all bits not set), or does not satisfy the filter parameters via a second value (e.g. 0xFF or all bits set). Such a selection byte vector may have entries with a length of <NUM> byte (<NUM> bits), consistent with how AVX2 comparison instructions store the output for single byte elements. Since encoded data of table <NUM> is processed in batches <NUM>, such a selection byte vector may have a number of rows equal to a number of rows of table <NUM> processed in batch <NUM> (e.g. <NUM> rows). A non-limiting example of a portion of such a selection byte vector is shown in Table <NUM> below, corresponding to the portion of table_of_sales of Table <NUM> and utilizing the example dictionary encoding previously described in connection with Tables <NUM>-<NUM> for the query shown in the preceding paragraphs:.

Block <NUM> includes determining, 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. For example, processor <NUM> (<FIG>) may be configured to 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. Such an indicator may indicate a selectivity of the filter defined by the parameters of query <NUM> on the portion of table <NUM> included in the current batch <NUM>. Using Table <NUM> as an example, such an indicator of selectivity may indicate that the filter passed <NUM> of the <NUM> rows, corresponding to a selectivity of <NUM>% or <NUM>. In this example, the filter or selection eliminated <NUM> of <NUM> rows. However, depending on the parameters of the particular filter used, selectivity may range from <NUM>% (<NUM>) to <NUM>% (<NUM>), inclusive.

Block <NUM> includes determining a bit length of the encoded values in the first column vector. For example, processor <NUM> (see <FIG>) may be configured to determine a bit length of the encoded values in the column vector being evaluated, e.g., for the example query indicated above, the column vector for sale_amt of Table <NUM> having a bit length of <NUM> bits.

Block <NUM> includes, for a subset of the encoded values in the first column vector, selecting an algorithm from a plurality of algorithms for processing the query based on the indicator and the determined bit length of the encoded values. For example, several processes or algorithms are described below for carrying out the selection, grouping, and/or aggregation of encoded values to generate output <NUM> (see <FIG>). However, some of these processes or algorithms are more efficient than others, in terms of clock cycles required to perform query <NUM>, depending on the selectivity of the filter defined by query <NUM> and the bit lengths of encoded values. For example, as will be described below, between selection by compacting, gather selection and selection by special group assignment, at a selectivity of <NUM>% and a bit width of <NUM> bits, some embodiments may choose selection by compacting as the preferred selection process.

The vector operation of compacting takes two inputs: the selection byte vector (first vector) previously described in connection with block <NUM> of <FIG>, and an input column vector with arbitrary numeric elements from which an output column vector may be generated. Element size for the input column vector may be any of <NUM> byte, <NUM> bytes, <NUM> bytes, or <NUM> bytes. The result of compacting is an output column vector having all entries of the input column vector indicated by the selection byte vector to have been passed (e.g. having a corresponding row entry of 0xFF) by the filter defined by query <NUM>. A description of selection by compacting follows with reference to <FIG>, which illustrates a process for performing selection by compacting for a query <NUM>, in accordance with some embodiments, and <FIG>, which is a block diagram illustrating certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing selection by compacting for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Block <NUM> includes adding 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. The same length may be one byte, two bytes, four bytes or eight bytes. For example, with reference to <FIG>, encoded values of a given first column vector <NUM> are not necessarily encoded in whole-byte lengths. Thus, to ensure maximum usage of registers 104a-104n (see <FIG>) and to ensure encoded values of first column vector <NUM> each fit completely within a given register 104a, processor <NUM> (<FIG>) may unpack encoded values of first column vector <NUM> to the next largest size of <NUM> byte, <NUM> bytes, <NUM> bytes, or <NUM> bytes, utilizing an unpacking operation <NUM>, to generate a corresponding first column vector <NUM> of unpacked encoded values. <NUM>n byte sizes, where n = <NUM>, <NUM>, <NUM> or <NUM>, provides such assurances.

Block <NUM> includes loading a first subset of values into respective lanes of a first register, the first subset comprising the unpacked encoded values. For example, with reference to <FIG>, processor <NUM> (<FIG>) may load a first subset of unpacked encoded values from unpacked first column vector <NUM>, now having whole-byte lengths, into respective lanes of register 104a utilizing a load operation <NUM>. In <FIG>, lanes are indicated by individual boxes, having <NUM> byte length, although lanes may be any length based on the data being loaded.

Block <NUM> includes loading 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may perform a loading operation <NUM> to load a second subset of values of selection byte vector <NUM> (first vector) into respective lanes of register 104b. The second subset of values <NUM> correspond to the first subset of values of unpacked first column vector <NUM> and are loaded into register 104b. Since the values of selection byte vector <NUM> (first vector) each have a length of <NUM> byte, a whole number of unpacked encoded values may be loaded into register 104b. Since the second subset of values of the selection byte vector loaded into register 104b correspond to the first subset of unpacked encoded values loaded into register 104a, a same number of values of second byte vector <NUM> are loaded into register 104b as unpacked encoded values are loaded into register 104a, and in the same order.

Block <NUM> includes utilizing a single instruction to output unpacked encoded values passing the filter from the first register into a filtered first column vector based on the values in the second subset. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize a single instruction, outputting operation <NUM>, to output unpacked encoded values passing the filter from register 104a into a filtered first column vector <NUM> based on the values of the selection byte vector <NUM> (first vector) loaded into register 104b. In some embodiments, such an operation may be an AND operation between corresponding lanes of registers 104a and 104b (e.g., between unpacked encoded values from unpacked first column vector <NUM> loaded into register 104a and corresponding values from selection byte vector <NUM> (first vector) loaded into register 104b).

The vector operation of gather selection utilizes some steps previously described for the selection by compacting process, while introducing additional and/or alternative steps. A description of gather selection follows with reference to <FIG>, which illustrates a process for performing gather selection for a query <NUM>, in accordance with some embodiments, and <FIG>, which illustrate block diagrams of certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing gather selection for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Block <NUM> includes generating a second vector comprising a plurality of consecutive integer values. In some embodiments, the integer values may be one byte, two bytes, four bytes or eight bytes in length. For example, with reference to <FIG>, processor <NUM> may be configured to generate a second vector <NUM> having entries that are consecutive integer values. In some embodiments, the consecutive integers start with zero, and second vector <NUM> may have as many entries as the previously-described selection index vector <NUM>.

Block <NUM> includes loading a first subset of values into respective lanes of a first register, the first subset comprising the consecutive integer values of the second vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may load a first subset of consecutive integer values from second vector <NUM> into respective lanes of register 104a utilizing a loading operation <NUM>.

Block <NUM> includes loading a second subset of values into respective lanes of a second register, the second subset comprising values of the first vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may perform a loading operation <NUM> to load a second subset of values of selection byte vector <NUM> into respective lanes of register 104b. The first subset of values are those values at same positions within second vector <NUM> as the positions of the second subset of values within selection byte vector <NUM>, and in the same order. Thus, when corresponding lanes of registers 104a and 104b are compared, the values in register 104b may act as a mask for values in register 104a.

Block <NUM> includes utilizing a single instruction to output integer values from the first register into an index vector based on the values in the second subset. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize a single AVX2 SIMD instruction, outputting operation <NUM>, to output each integer value from register 104a into a third vector <NUM> where a respective lane of register 104b holds a value of the selection byte vector <NUM> indicating filter passing, and not output each integer value from register 104a into third vector <NUM> where a respective lane of register 104b holds a value of the selection byte vector <NUM> indicating filter not passing. In some embodiments, such an operation may be an AND operation between corresponding lanes of registers 104a and 104b (e.g., between integer values from second vector <NUM> loaded into register 104a and corresponding values from selection byte vector <NUM> loaded into register 104b). Third vector <NUM> may be known as a "selection index vector" and may indicate the ordinal positions of the rows of selection byte vector <NUM> which hold values indicating a filter pass.

Block <NUM> includes matching the integer values of the third vector with indices of the first column vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize AVX2 SIMD instructions to compare the integer values of third vector <NUM> with indices of first column vector <NUM>.

Block <NUM> includes, based on the match, retrieving and decoding encoded values of the first column vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize AVX2 SIMD instructions to perform a retrieve or gather operation <NUM> that retrieves encoded values of column vector <NUM> that are stored at indices within column vector <NUM> that match the integer values of selection index vector <NUM>. These retrieved encoded values may be directly loaded into corresponding lanes of one of registers 104a-104n. Processor <NUM> may perform a decoding operation <NUM> on the retrieved encoded values by looking up the decoded value mapped to the retrieved encoded values in an appropriate encoding dictionary to generate a decoded column vector <NUM>. In some embodiments, such a decoding operation may utilize AVX2 SIMD instructions to operate on multiple retrieved encoded values simultaneously.

Gather selection effectively combines bit unpacking and removing filtered out rows of an encoded column vector. At least block <NUM> may be repeated for each column <NUM> of table <NUM> for which query <NUM> defines a "group by" parameter and for each column <NUM> of table <NUM> for which query <NUM> defines an aggregation parameter.

Selection by special group assignment is to be used in combination with the "group by" aggregation that follows this type of selection. Selection by special group assignment is an optimization that may be viewed as pushing grouping and aggregation ahead of portions of the selection operation in the processing pipeline.

A description of selection by special group assignment follows with reference to <FIG>, which illustrates a process for performing selection by special group assignment for a query <NUM>, in accordance with some embodiments, and <FIG>, which is a block diagram illustrating certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing selection by special group assignment for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Block <NUM> includes adding bits to encoded values in a second column vector by which the query indicates the result is to be grouped, thereby generating unpacked encoded values of the second column vector, each unpacked encoded value having a same length. The same length may be one byte, two bytes, four bytes or eight bytes. Such encoded values may be considered group IDs, since each different encoded value represents a different entry by which a result may be grouped. For example, query <NUM> (<FIG>) may comprise an indication of a second column vector having encoded values by which a result is to be grouped. Such an indication in query <NUM> may have the general form "group by" followed by the identifier of one or more columns <NUM> of table <NUM>, e.g., "state". With reference to <FIG>, encoded values of the second column vector <NUM> are not necessarily encoded in whole-byte lengths (e.g. <NUM> bits as shown in <FIG>). Thus, to ensure maximum usage of registers 104a-104n (see <FIG>) and to ensure encoded values of second column vector <NUM> each fit completely within a given register 104a, processor <NUM> (<FIG>) may unpack encoded values of second column vector <NUM> to the next largest size of <NUM> byte, <NUM> bytes, <NUM> bytes, or <NUM> bytes, utilizing unpacking operation <NUM>, to generate a corresponding second column vector <NUM> of unpacked encoded values.

Block <NUM> includes loading 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 example, with reference to <FIG>, processor <NUM> (<FIG>) may load a first subset of unpacked encoded values from unpacked second column vector <NUM>, now having whole-byte lengths, into respective lanes of register 104a using a loading operation <NUM>.

Block <NUM> includes loading 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may perform loading operation <NUM> to load a second subset of values of selection byte vector <NUM> into respective lanes of register 104b. A same number of values of selection byte vector <NUM> are loaded into register 104b as unpacked encoded values are loaded into register 104a, and in the same order.

Block <NUM> includes utilizing 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize a single AVX2 SIMD instruction, updating operation <NUM>, to update, to a constant value (e.g., 0x04), unpacked encoded values in lanes of register 104a that correspond to lanes of register 104b comprising an indication of failing the filter (e.g., 0x00), thereby generating updated second column vector <NUM>. In some embodiments, the constant value may be a first unused value of unpacked second column vector <NUM> (e.g., 0x04 is shown in <FIG> as the first unused value). However, any unused value of unpacked second column vector <NUM> may also be utilized. Such an updating operation may be, for example, a NOT AND operation between corresponding lanes of registers 104a and 104b (e.g., between unpacked encoded values from unpacked second column vector <NUM> loaded into register 104a and corresponding values from selection byte vector <NUM> loaded into register 104b).

Block <NUM> includes executing 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may execute query <NUM> on column-store table <NUM>, without regard to the filter defined by query <NUM>, utilizing updated second column vector <NUM> that now includes the constant value in updated rows. Accordingly, by updating the entries in second column vector <NUM> for rows not passing the filter defined by query <NUM>, the disqualified rows are effectively grouped into the constant value's group and may be discarded before outputting the result of query <NUM> without fully processing the filter. Performing the query may include executing any "group by" and any "aggregation" operation as defined by query <NUM>.

In general, gather selection would be best suited for filters having low selectivity (where a relatively small proportion of rows in batch <NUM> of table <NUM> pass or satisfy the conditions of the filter of query <NUM>), selection by compacting would be best suited for filters having intermediate selectivity, and selection by special group assignment would be best suited for filters having selectivity close to <NUM> (where nearly all rows in batch <NUM> of table <NUM> pass or satisfy the conditions of the filter or query <NUM>).

Per-row costs of running queries for all <NUM> of these methods may be expressed as ccompact, cgather, and cspecial, respectively. If the cost of aggregating a result (e.g., calculating a sum, min, max, avg, standard deviation, etc.) is expressed as caggregate and filter selectivity is expressed as α, gather selection will outperform selection by compaction when α < ccompact / cgather and selection by compaction will outperform selection by special group assignment when α < (cspecial + caggregate - ccompact ) / caggregate. Accordingly, for each bit width of encoded data there is a fixed filter selectivity beyond which selection by compacting starts to outperform gather selection. For example, it has been determined that, for <NUM> bit widths, selection by compacting outperforms gather selection for filter selectivity of ≥~<NUM>% (at least <NUM> percent of rows pass the filter), for <NUM> bit widths, selection by compacting outperforms gather selection for filter selectivity of ≥~<NUM>%, for <NUM> bit widths, selection by compacting outperforms gather selection for filter selectivity of ≥~<NUM>%, and for <NUM> bit widths, selection by compacting outperforms gather selection for filter selectivity of ≥~<NUM>%.

Sort based group by sum operations using SIMD sort row indices within each batch <NUM> of rows into groups based on the indications of how results are to be grouped in query <NUM>.

A description of sort based group by sum follows with reference to <FIG>, which illustrates a process for performing sort based group by sum for a query <NUM>, in accordance with some embodiments, and <FIG>, which illustrate certain data vectors, registers, and operations that are the subject of the process of <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing sort based group by sum for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Block <NUM> includes, for each unique encoded value in the second column vector, determining a count of the unique encoded values in the second column vector. For example, query <NUM> (<FIG>) may comprise an indication of a second column vector having encoded values by which a result is to be grouped. Such an indication in query <NUM> may have the general form "group by" followed by an indication of one or more columns <NUM> of table <NUM>, e.g., "state". With reference to <FIG>, processor <NUM> may be configured to perform a group by count(*) operation <NUM> on second column vector <NUM>, which returns a respective count <NUM> for each unique encoded value in second column vector <NUM>. In some embodiments, having the same encoded value occurring in consecutive rows of second column vector <NUM> may cause write conflicts in single counters utilized to track the count of each group indicated by second column vector <NUM>. Accordingly, in some embodiments, to avoid such write conflicts, two or more counters may be utilized for tracking the count of each group and partial sums from each counter for a given group may be added together at the end of the counting process.

Block <NUM> includes generating 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 example, with reference to <FIG>, processor <NUM> (<FIG>) may generate a plurality of subarrays <NUM>, <NUM>, <NUM>, <NUM>. Each subarray <NUM>, <NUM>, <NUM>, <NUM> has a length based on respective count <NUM> of the corresponding unique encoded value in second column vector <NUM>.

Block <NUM> includes, for each row of the second column vector, inserting an indication of the row into one of the plurality of subarrays based on the encoded value at the row. For example, with reference to <FIG>, processor <NUM> (<FIG>) may perform an inserting operation <NUM> for each index of second column vector <NUM>, by inserting the indication of the row into one of the plurality of subarrays <NUM>, <NUM>, <NUM>, <NUM> based on the encoded value in the row.

Block <NUM> includes concatenating each of the plurality of subarrays to generate a first array. For example, with reference to <FIG>, processor <NUM> (<FIG>) may perform a concatenating operation <NUM> to concatenate each of the plurality of subarrays <NUM>, <NUM>, <NUM>, <NUM> to generate a first array <NUM> of sorted rows for the second column vector. First array <NUM> contains indications of all rows within a batch <NUM> that fall into that group. Utilizing such an array, sums of the encoded values at the row of one or more columns may then be computed. In some embodiments, the concatenating step of block <NUM> may be optional. For example, such a concatenation may instead comprise a logical operation in which the plurality of subarrays <NUM>, <NUM>, <NUM>, <NUM>, which may be physically stored adjacent to one another in memory, are not actually concatenated to form first array <NUM> but instead are alternatively interpreted, together, as first array <NUM>.

Block <NUM> includes, for one of the subarrays of the first array, matching the indications of the rows in the subarray with rows of the first column vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform a matching operation <NUM> that matches indications of the rows in subarray <NUM> of first array <NUM> with rows of first column vector <NUM>.

Block <NUM> includes, based on the match, retrieving and decoding encoded values of the first column vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to, based on the match at block <NUM>, retrieve, via a retrieving operation <NUM>, and decode, via a decoding operation <NUM>, encoded values of first column vector <NUM>. Accordingly, processor <NUM> may retrieve encoded values located at rows of first column vector <NUM> that match the indications of the rows in subarray <NUM> of first array <NUM>. Processor <NUM> may utilize the encoded values to perform a lookup in the encoding dictionary corresponding to the encoded values and return the decoded values <NUM>. In some embodiments, the decoding portion of block <NUM> may be optional. For example, in some cases, for numeric columns having encoded values small enough to fit within <NUM>-bit registers, for example, where a range of small integers (e.g., <NUM>-<NUM>) are encoded utilizing a smallest number of bits that may uniquely represent each of the small numbers, decoding may not be necessary as the encoded values may still be added without decoding to larger, expanded byte-level lengths. For example, where the numbers <NUM>-<NUM> are encoded utilizing <NUM> bits (e.g., the integer <NUM> is represented as <NUM>, the integer <NUM> is represented as <NUM>, the integer <NUM> is represented as <NUM>, etc.), the encoded <NUM>-bit values may be added without decoding to larger, expanded byte-level sizes. In such embodiments, block <NUM> may comprise, based on the match, retrieving the encoded values from the first column vector.

Block <NUM> includes loading the decoded values of the first column vector into respective lanes of a first register. For example, with reference to <FIG>, processor <NUM> may be configured to load the decoded values <NUM> of first column vector <NUM> into respective lanes of register 104a. Although only two values are shown as being loaded into register 104a, this is merely an example and any number of qualifying values may be loaded into register 104a. In embodiments where the decoding portion of block <NUM> is not performed, as described above, block <NUM> may instead operate utilizing the encoded values of the first column vector.

Block <NUM> includes utilizing 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. For example, with reference to <FIG>, processor <NUM> may be configured to utilize a single instruction, e.g., a SIMD instruction, to add the decoded values in each lane of register 104a to a corresponding lane in register 104f, thereby generating, in the corresponding lanes of register 104f, sums of decoded values from corresponding lanes of register 104a. The loading step of block <NUM> and the operations of block <NUM> may be repeated until all values for the particular column and particular group have been processed. Then, processor <NUM> may determine a sum <NUM> for a group, as indicated by query <NUM>, by utilizing a summing operation <NUM>, sometimes also referred to as "reducing," that adds all running sums in the lanes of register 104f to obtain a sum <NUM> of the lanes of register 104f. Sum <NUM> may comprise a sum indicated by query <NUM>.

Processor <NUM> may carry out this matching, retrieval, decoding, loading and summing operation for each column, and for each group, for which a sum is indicated by query <NUM>.

In some embodiments, computing aggregates with grouping may be based on keeping intermediate results entirely in CPU registers instead of in memory <NUM>. Some such embodiments may be utilized where a number of groups by which results are to be grouped is approximately <NUM> or less. Each aggregate (sum, minimum, maximum, etc.) may be processed separately.

A description of in-register group by count and group by sum follows with reference to <FIG>, which illustrates a process for performing in-register group by count and group by sum for a query <NUM>, in accordance with some embodiments, and <FIG>, which is a block diagram illustrating certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing in-register group by count and group by sum for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Query <NUM> further comprises an indication of a second column vector <NUM> having encoded values by which a result of query <NUM> is to be grouped. As an example, assume query <NUM> defines a result as a number of rows of a column that correspond to each group, as identified by <NUM>-byte encoded values within the column (e.g., group by count).

Block <NUM> includes adding 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. The same length may be one byte, although any other whole-byte length is contemplated. Such encoded values may be considered group IDs, since each different encoded value represents a different entry by which a result may be grouped. For example, query <NUM> (<FIG>) may comprise an indication of second column vector <NUM> having encoded values by which a result is to be grouped. Such an indication in query <NUM> may have the general form "group by" followed by the identifier of one or more columns <NUM> of table <NUM>, e.g., "state". With reference to <FIG>, encoded values of the second column vector <NUM> are not necessarily encoded in whole-byte lengths (e.g. <NUM> bits as shown in <FIG>). Thus, to ensure maximum usage of register 104a (see <FIG>) and to ensure encoded values of second column vector <NUM> each fit completely within a given register 104a, processor <NUM> (<FIG>) may unpack encoded values of second column vector <NUM> to the next largest size of <NUM> byte, utilizing unpacking operation <NUM>, to generate a corresponding second column vector <NUM> of unpacked encoded values.

Block <NUM> includes loading 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 example, with reference to <FIG>, processor <NUM> (<FIG>) may load each of a first subset of unpacked encoded values from unpacked second column vector <NUM>, now having whole-byte lengths, into respective lanes of register 104a utilizing load operation <NUM>.

Block <NUM> includes, for each lane of the first register, initializing 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 example, with reference to <FIG>, processor <NUM> (<FIG>) may initialize a partial counter in a corresponding lane of each of a plurality of registers 104b, 104c, 104d, such that each of the plurality of registers 104b-104e holds a respective partial counter for each lane of first register 104a and all partial counters in a register 104b, 104c, 104d, 104e correspond to a unique unpacked encoded value of second column vector <NUM>. For example, register 104b may hold partial counters for group "<NUM>", register 104c may hold partial counters for group "<NUM>", register 104d may hold partial counters for group "<NUM>" and register 104e may hold partial counters for group "<NUM>". Although only <NUM> registers 104b-104e are shown, such an implementation would have N-<NUM> registers holding partial counters for N-<NUM> of N unique unpacked encoded values in column vector <NUM>. As will be described in more detail below, one less register than there are groups N can be utilized since the last group count can be obtained by subtracting all other group counts from the total number of rows in second column vector <NUM>.

Block <NUM> includes, for each lane of the first register, incrementing 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 example, with reference to <FIG>, processor <NUM> (<FIG>) may proceed, lane by lane for register 104a, to increment the partial counter in the corresponding lane of one of the plurality of registers 104b-104e that corresponds to the unpacked encoded value in the lane of first register 104a. For example, working from the right to the left, the first lane of register 104a holds the unpacked encoded value "<NUM>". Thus, the partial counter in the corresponding lane of register 104b, which holds partial counters for group "<NUM>", is incremented, e.g., its value is changed to 0xFF or <NUM>. The second lane of register 104a also holds the unpacked encoded value "<NUM>". Thus, the partial counter in the corresponding lane of register 104b is incremented, e.g., its value is changed to 0xFF or <NUM>. The third and fifth lanes of register 104a hold the unpacked encoded value "<NUM>". Thus, the partial counters in the corresponding lanes of register 104c, which holds counters for group "<NUM>", are incremented, e.g., its value is changed to 0xFF or <NUM>. The fourth and seventh lanes of register 104a hold the unpacked encoded value "<NUM>". Thus, the partial counters in the corresponding lanes of register 104d, which holds counters for group "<NUM>", are incremented, e.g., its value is changed to 0xFF or <NUM>. As may be appreciated, only one lane across registers 104b-104d will be incremented for any corresponding unpacked encoded value in the corresponding lane of register 104a, each time register 104a is loaded with subsequent sets of unpacked encoded values from second column vector <NUM>.

Block <NUM> includes, for each of the plurality of further registers, summing first counters in the further register and adding the sum to a corresponding second counter for the corresponding unique unpacked encoded value. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform a summing operation <NUM> that, for each register 104b-104d, sums all partial counters in a particular register 104b, for example, and adds the result to a corresponding total counter in second array <NUM>. As shown, register 104b has two lanes (the first and second lanes) with values of <NUM>, which may be summed and added to the corresponding total counter C<NUM> in second array <NUM>. Similarly, the two <NUM> valued lanes of each of registers 104c and 104d may be summed and added to corresponding total counters C<NUM> and C<NUM>, respectively, in second array <NUM>. Accordingly, registers 104b-104d may hold partial counters for occurrences of unique unpacked encoded values in each loading of register 104a, while second array <NUM> holds total counters for occurrences of the unique unpacked encoded values across all loadings of register 104a described in this section.

In embodiments where the incremented value of partial counters in registers 104b-104d is 0xFF, such summing operation may include negating the incremented value 0xFF (since 0xFF means subtracting <NUM> for signed <NUM>-bit integers) and merging each value into the counters in second array <NUM>. In some embodiments, the actions of block <NUM> may be carried out utilizing a single set of SIMD instructions for registers 104a-104d.

Block <NUM> includes determining 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to determine a last total counter C<NUM> in second array <NUM> by subtracting all the corresponding total counters C<NUM>, C<NUM>, C<NUM> in the second array from a total number of rows of second column vector <NUM>. The last total counter value C<NUM> corresponds to a last of the unique unpacked encoded values, e.g., value "<NUM>", in second column vector <NUM>.

In some embodiments, query <NUM> may require determination of multiple sums across multiple columns. Whereas previous embodiments utilize data level parallelism vertically, embodiments utilizing this multi-aggregate group by sum process may utilize data level parallelism horizontally, meaning multiple aggregates across multiple columns for a same input row are summed instead of multiple input rows for the same aggregate column. In some embodiments, row-at-a-time aggregation for multiple sums may be faster than column-at-a-time aggregation. Further improvement may be obtained by loading inputs for multiple sums for the same row into one register and execute only one set of load-add-store instructions for all of them. As previously stated, column-store tables store values column-wise in memory. Accordingly, values from columns to be summed are reorganized via matrix transposing, as described in more detail below.

A description of multi-aggregate group by sum follows with reference to <FIG>, which illustrates a process for performing multi-aggregate group by sum for a query <NUM>, in accordance with some embodiments, and <FIG>, which is a block diagram illustrating certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for performing multi-aggregate group by sum for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Referring to <FIG>, query <NUM> (<FIG>) may comprise an indication of a plurality of column vectors <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (see <FIG>), each having encoded values that are to be summed and by which a result of the query is to be grouped. Encoded values of column vectors <NUM>, <NUM>, <NUM>, <NUM> are not shown in <FIG>, and are instead indicated as A1-A4, B1-B4, C1-C4, D1-D4 and E1-E4 for simplicity.

Now referring to <FIG>, block <NUM> includes, for each column vector of the plurality of column vectors, loading 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform a loading operation <NUM> that loads respective first subsets of encoded values A1-A4, B <NUM>-B4, C1-C4, D1-D4 and E1-E4 from respective column vectors <NUM>, <NUM>, <NUM>, <NUM>, <NUM> into respective registers 104a, 104b, 104c, 104d, 104e. Thus, a third array <NUM> comprises the encoded values in registers 104a-104e as shown in the middle of <FIG>. As a non-limiting example, encoded values A1-A4 have a length of <NUM>-bits (<NUM> bytes), encoded values B1-B4 and E1-E4 have a length of <NUM>-bits (<NUM> bytes), encoded values C1-C4 and D1-D4 have a length of <NUM>-bits (<NUM> bytes), and registers 104a-104e are <NUM>-bit (<NUM> byte) registers. In some embodiments, loading operation <NUM> may comprise AVX2 SIMD instructions that allow a single instruction to gather and load multiple rows of data into registers 104a-104e simultaneously.

Block <NUM> includes adding 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. A challenging aspect of converting columns to rows efficiently is that, in general, there can be different numbers of input columns and they may store elements of different byte sizes. A composition of template functions may be used to create specialized SIMD implementations where processor <NUM> (<FIG>) may be configured to unpack encoded values A1-A4, B1-B4, C1-C4, D1-D4 and E1-E4 to either <NUM>-byte lengths (e.g., a first length) or <NUM>-byte lengths (e.g., a second length) by adding padding zeros such that <NUM>- or <NUM>-byte length encoded values are unpacked to <NUM> bytes and encoded values having a greater length are unpacked to <NUM> bytes utilizing unpacking operation <NUM>. This ensures that up to <NUM>,<NUM> rows can be summed using, e.g., <NUM>-bit additions in SIMD lanes of registers 104a-104e without an overflow for input values of up to <NUM>-bytes. Such embodiments support arbitrary number and combinations of sizes of input columns so long as, after expansion, all elements for a single row can fit into a <NUM>-bit SIMD register with <NUM>-bit expanded elements being <NUM>-bit aligned and <NUM>-bit elements <NUM>-bit aligned.

Block <NUM> includes transposing the third array such that unpacked encoded values previously loaded into a single respective register are now loaded in corresponding lanes across each of the respective registers. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform transposing operation <NUM>, which may realign all entries within registers 104a-104e such that unpacked encoded values, e.g., A1-A4, previously loaded into a single respective register, e.g., 104a, are now loaded in corresponding lanes of the respective registers 104a-104d. For example, unpacked encoded values C1-C4 are shown as being transposed from lanes in only register 104c to the first <NUM>-bit lane of each of registers 104a-104d; unpacked encoded values D1-D4 are shown as being transposed from lanes in only register 104d to the second <NUM>-bit lane of each of registers 104a-104d; and each of unpacked encoded values A1-A4, B <NUM>-B4, and E1-E4, are shown as being transposed from lanes in registers 104a, 104b and 104e to respective <NUM>-bit lanes in each of registers 104a-104d.

Block <NUM> includes 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. For example, with reference to <FIG>, processor <NUM> (<FIG>) may utilize a single AVX2 SIMD instruction for each register 104a-104d to add the unpacked encoded value in each lane of the respective register to a corresponding lane in further register 104f. In further example, one instruction may add C1, D1, A1, B1 and C1 to the respective values CT, DT, AT, BT and ET in register 104f. For the first addition, each of CT, DT, AT, BT and ET may have a value of zero. Another instruction may add C2, D2, A2, B2 and C2 to the respective values CT, DT, AT, BT and ET in register 104f. Another instruction may add C3, D3, A3, B3 and C3 to the respective values CT, DT, AT, BT and ET in register 104f, and yet another instruction may add C4, D4, A4, B4 and C4 to the respective values CT, DT, AT, BT and ET in register 104f. Accordingly, running sums (e.g., CT, DT, AT, BT and ET) of unpacked encoded values from corresponding lanes of each respective register 104a-104d are held in the corresponding lanes of register 104f. Such transposing of array <NUM>, comprising originally loaded registers 104a-104e, allows encoded entries from multiple columns to be regrouped into registers as if they were originally entries within a single column, allowing them to be summed in single operations.

It is further possible to improve the performance for group by count (*) on bit packed columns having encoded values by which a result of the query is to be grouped. Such a process may be particularly useful where the number of groups (e.g., the number of unique encoded values, and therefore the bit length of the encoded values) are relatively small. A description for such fast group by count(*) using bit-level logic follows with reference to <FIG>, which illustrates a process for performing fast group by count(*) using bit-level logic for a query <NUM>, in accordance with some embodiments, and <FIG>, which is a block diagram illustrating certain data vectors, registers, and operations described by <FIG>.

Although certain steps or actions are described in connection with <FIG>, a process for fast group by count(*) using bit-level logic for query <NUM> may include fewer than all steps described, and/or additional or alternative steps to those described.

Referring to <FIG>, query <NUM> (<FIG>) may comprise an indication of second column vector <NUM> having encoded values by which a result of query <NUM> is to be grouped.

Referring to <FIG>, block <NUM> includes loading each of a first subset of values into a plurality of registers, the first subset comprising the encoded values of the second column vector. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform a loading operation <NUM> that loads respective first subsets of encoded values from second column vector <NUM> into registers 104a, 104b, and 104c. In some embodiments, registers 104a-104c are <NUM>-bit registers, though only shown to have <NUM> bits for ease of explanation. Thus, in some embodiments, the first subset of values may comprise <NUM> values from second column vector <NUM>, although only <NUM> are shown for ease of explanation. Second column vector <NUM> is shown to comprise <NUM>-bit encoded values. Thus, the first subset of values may be loaded into a same number of registers as the number of bits in the encoded values, e.g., <NUM> in this example.

Block <NUM> includes separating and reloading 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 example, processor <NUM> (<FIG>) may be configured to perform a separating and reloading operation <NUM> where a first bit of each encoded value (shown in bold in <FIG> for ease of reference only) may be separated and loaded into register 104a, a second bit of each encoded value may be separated and loaded into register 104b, and a third bit of each encoded value may be separated and loaded into register 104c, as partially indicated by the dotted circles and arrows. Although bits from encoded values of second column vector <NUM> may be separated and reloaded into the registers 104a-104c in any order, that order must be the same for each register 104a-104c.

Block <NUM> includes, for at least some of the unique encoded values of the second column vector, comparing bits of each encoded value in the plurality of registers with corresponding bits of the unique encoded value.

Block <NUM> includes, based on the comparison, setting a further bit for each encoded value having all bits matching the unique encoded value. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform an operation <NUM> that compares the bit in each of registers 104a-104c for each encoded value with the corresponding bits of the unique encoded value and then, based on the comparison, generate a fourth vector having a corresponding bit set for each encoded value having all bits matching the unique encoded value. For example, for the unique encode value "<NUM>", processor <NUM> may be configured to generate bit vector <NUM> utilizing the comparison function Z = NOT (A OR B OR C), where A, B and C are the respective ith bits in registers 104a, 104b, 104c for each bit in registers 104a, 104b, 104c. Similarly, for the unique encoded value "<NUM>", processor <NUM> may be configured to generate bit vector <NUM> utilizing the comparison function Z = NOT (A OR B) AND C.

Block <NUM> includes, for each further bit set, incrementing a fourth counter for the unique encoded value in a third array. For example, with reference to <FIG>, processor <NUM> (<FIG>) may be configured to perform an incrementing operation <NUM> on each of total counters C<NUM>, C<NUM> and C<NUM> by <NUM> based on each respective bit vector <NUM>, <NUM>, <NUM> having two bits set.

Block <NUM> includes determining a fifth counter value 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. For example, with reference to <FIG>, once all encoded values of second column vector <NUM> have been processed through block <NUM>, processor <NUM> (<FIG>) may be configured to subtract total counts C<NUM>, C<NUM> and C<NUM> from a total number of rows of second column vector <NUM> to determine total count C<NUM> corresponding to the final unique encoded value in second column vector <NUM>.

The process described in connection with <FIG> and <FIG> can also be applied to filters, where such filters are in the form of a bit vector similar to bit vectors <NUM>, <NUM>, <NUM>. For example, filter bit vectors may be ANDed with the separated and reloaded bits in registers 104a-104c shown after operation <NUM> in <FIG>. This may be equivalent to assigning all filtered rows to group zero, and this group can be skipped while updating counters as previously described in connection with block <NUM>. Thus, this group zero may be selected as the skipped group. The count for group zero, or filtered out rows, may be determined by subtracting the number of rows passing the filter (e.g., the number of bits set in the filter bit vector) from the total number of rows in second column vector <NUM>.

The process described in connection with <FIG> and <FIG> can also be applied to multiple grouping columns, so long as they all utilize bit packing with relatively small bit widths and the sum of all bit widths is also relatively small (e.g., <NUM> bits). For example, in such embodiments, query <NUM> (<FIG>) may comprise an indication of a plurality of column vectors (e.g., two or more) having encoded values by which a result of query <NUM> is to be grouped. In such embodiments, a separate set of bit vectors (similar to bit vectors <NUM>, <NUM>, <NUM>) may be generated for each column vector by which query <NUM> indicates results are to be grouped. Then, blocks <NUM> and <NUM> may be carried out utilizing union of all sets of bit vectors for the plurality of grouping column vectors as if all bits came from a single column. Logically, this corresponds to concatenating bits of values from all grouping columns for the same row.

In some embodiments, queries may include one or more expressions that require repetitive evaluation in order to return a result. An example of such a query may be:
Select substr(<NUM>,<NUM>,s), count(*)
From t
Group by substr(<NUM>,<NUM>,s).

Such a query asks for substrings that span the first through third character of all entries in a column "s" of a table "t" and to group the results by unique substrings. Thus, in order to return a result, the expression "substr (<NUM>, <NUM>, s) " must be evaluated. Rather than evaluating the expression outright each time, a two-level dictionary may be employed that allows a lookup of a previously mapped evaluation for a particular expression. Where inputs to the expression are repetitive, such lookups can save considerable processing cycles compared with re-evaluating an expression each time it is encountered. For example, consider an example column s in Table <NUM> below and the result of evaluation of the expression "substr (<NUM>, <NUM>, s) " in Table <NUM>.

As the expression "s ub s t r (<NUM>, <NUM>, s)" is evaluated for column "s" a first map or hash table may be generated such that each time a new input from column "s" is encountered, the input is mapped to an encoded value for that entry in a first table, as shown in Table <NUM> below. Likewise, each time an output of the expression is generated, the output is mapped to an encoded value for that output in a second table, as shown in Table <NUM>. Similarly, the encoded values of the first table may then be further mapped to the encoded values of the second table, as shown in Table <NUM>.

Accordingly, as each row of column "s" is evaluated, processor <NUM> (<FIG>) may first determine whether the string appearing in column "s" has already been mapped to an encoded value in the first map. If so, rather than re-evaluating the expression "substr (<NUM>,<NUM>,s)", processor <NUM> may, instead, use the corresponding encoded value, e.g., "<NUM>", from the first map to look up the output value in the second map utilizing the mapped correspondence in the third map. In this way, by using this multilevel dictionary, expressions may be evaluated in far fewer CPU cycles than if the expressions were re-evaluated each time.

In yet other embodiments where results are grouped by multiple columns, hash tables for encoding of each of the multiple columns may be merged into a single hash table and utilized to group results, as though results were grouped by only a single column, according to any method discussed above. For example, recall Table <NUM> and assume the following query:
Select division, state,sum(sale_amt)
From table_of_sales
Group by division, state
This query asks for the sum of sale_amt from the table table_of_sales and asks that the resulting sums be grouped by division and state, thus, requiring group by operations based on entries in both the "division" column and the "state" column.

Instead of evaluating the query by each group by column individually, according to some embodiments, the encoded values in corresponding rows of the "division" and "state" columns may be concatenated to form a single encoded column by which output results may be grouped, in accordance with any process previously described.

Accordingly, a hash table may be generated that maps each concatenated encoded entry to the decoded values for each encoded column value, as shown in Table <NUM> below. The key for the hash table of Table <NUM> has a number of bits that is the sum of the number of bits for the original encoded "division" and "state" columns, e.g., <NUM> bit + <NUM> bits = <NUM> bits. Accordingly, grouping by the concatenated column of encoded values allows the avoidance of multiple iterations through the group by process because the sorting or grouping operation operates on the concatenated column of encoded values, treating each concatenated encoded value as if it were a single encoded value. This drastically reducing the number of CPU cycles required to generate a result of the query.

Claim 1:
A method (<NUM>) for causing a processor to perform a query on a column-store table (<NUM>) comprising one or more column vectors of encoded values, the method comprising configuring the processor to:
receive (<NUM>) the query, the query comprising a filter to be applied to at least a first column vector (<NUM>) of the encoded values, wherein the first column vector (<NUM>) comprises a plurality of contiguous segments (<NUM>), each segment (<NUM>) being encoded separately from segments of another column vector of the column-store table (<NUM>);
process (<NUM>) the query for a batch (<NUM>) of the encoded values in a segment (<NUM>) of the first column vector (<NUM>), whereby to generate a first vector indicative of respective encoded values passing the filter or failing the filter;
determine (<NUM>), from the first vector, a selectivity indicator of the filter for the encoded values in the batch (<NUM>), the selectivity indicator indicating encoded values passing the filter relative to the encoded values in the batch of the segment of the first column vector (<NUM>) or encoded values failing the filter relative to the encoded values in the batch of the segment of the first column vector (<NUM>);
determine (<NUM>) a bit length for encoding of the encoded values in the segment of the first column vector (<NUM>); and
for the batch (<NUM>) of the encoded values, select (<NUM>) an algorithm from a plurality of algorithms for further processing the query, the algorithm being selected based on the selectivity indicator for the batch (<NUM>) and the determined bit length of the encoded values in the segment of the first column vector (<NUM>).