DETAILED ACTION
This communication is a Final Action in response to correspondence filed on March 20, 2026. Claims 1-20 are pending in the application.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1, 4-11, and 14-20 are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (US Publication No. 2018/0089261) in view of Chavan et al. (NPL entitled “Accelerating Joins and Aggregations on the Oracle In-Memory Database,” dated 2018).
As to claim 1, Li teaches a method comprising:
retrieving a database query comprising an aggregate function of a selected column [measure key] from a database table, wherein the aggregate function is grouped by a plurality of columns [group-by keys] from the database table (see e.g., [0124] for a DBMS receiving a query specifying a “group-by” clause for the queried data set to be split based on the values of one or more columns specified in the group by clause, the “group-by key” term referring to a column of a table specified in the group-by clause of the query, the query also specifying one or more aggregate functions for aggregating columns that are selected but are not used for splitting the selected data set, aggregate functions including minimum, maximum, percentile, average and median among other aggregate functions, the “measure key” term referring to a column which is referenced by an aggregate function in the received query, and the values of the measure key being aggregated using the aggregate function of the received query);
maintaining a plurality of mappings [column dictionaries], respectively for each of the plurality of columns, that map column values to grouping keys [group-by key encoded values] and identify a maximum grouping key [maximum encoded value] (see e.g., [0065] for the column dictionaries arranging the mappings in many different ways using various dictionary encodings and in an embodiment, a dictionary encoded value in a cell element being an index to an entry in a column dictionary that contains the corresponding database object value and [0134] for column dictionary containing the mapping of every unique value in the column mapped to the corresponding encoding of the value and each group-by key having a column dictionary. A plurality of column dictionaries are maintained, respectively for each of the plurality of group-by keys. Since the column dictionaries identify each group-by key encoded value, a maximum encoded value is necessarily identified, such as the highest index value.);
storing the maximum grouping key, within a combined index value [grouping index value] (see e.g., [0129] for in an embodiment, in which multiple group-by keys are specified by the query, the DBMS combining the group-by keys into a grouping index and [0135] for in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values. The grouping index value may include group-by key encoded values, including the maximum grouping key.);
allocating a result array [payload array] sized according to a combined count of grouping keys (see e.g., [0133] for the payload array being initialized based on the group-by key column dictionary of a data portion being scanned and [0134] for in an embodiment in which multiple group-by keys are specified by the query, the payload array being initialized to the length of all possible permutations of group-by key column dictionary values, which is the multiplication of the length of each group-by key's column dictionary length (which, itself, is the number of grouping index values) and entries of the payload array being initialized to zero or empty (NULL). A payload array is allocated and sized according to a combine count of group-by key encoded values.); and
for each row in the database table [data portion]:
determining the combined index value based on grouping keys looked up in the plurality of mappings via field values from said each row in the respective plurality of columns (see e.g., [0033] for each dictionary encoded column (or the portion thereof) being produced as a column vector of the dictionary codes which are mapped to the corresponding unencoded values using the dictionary data structure and the term “column dictionary” also referring herein to such a dictionary data structure and [0135] for the DBMS scanning a data portion loaded into the main memory to process the one or more vectors and column dictionaries contained in the data portion for the group-by operation of the received query, the DBMS selecting a row from the row set of the loaded data portion, for the selected row, the DBMS retrieving the encoded group-by key value of the group-by key vector, and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array. For each row in the data portion, the grouping index value is determined based on group-by key encoded values looked up in the column dictionaries using field values from the row for the respective group-by keys.); and
applying the aggregate function on the selected column for said each row and storing a result [partial aggregate value] in the result array at the combined index value (see e.g., [0135] for the group-by key being used as an index into the payload array to retrieve the previous partial aggregate value and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array, [0136] for the DBMS applying an aggregate function to the measure key unencoded value and the previous aggregate value to determine the new aggregate value, and [0137] for after application of the new measure key unencoded value, one or more of the values of the payload array entry being updated accordingly. The aggregate function is applied on the measure key for the row. A partial aggregate value is stored in the payload array at the grouping index value.).
Li does not specifically disclose wherein the plurality of mappings comprise a plurality of hash tables. However, Chavan teaches
wherein the plurality of mappings comprise a plurality of hash tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assign each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell. A hash table maps column values to codes representing grouping keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the mappings of Li wherein the plurality of mappings comprise a plurality of hash tables, as taught by Chavan, for the benefit of more efficient retrieval (see e.g., Chavan, p. 1443).
Li does not specifically disclose updating a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key bit positions, capable of storing the maximum grouping key; wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks; and for each row in the database table: determining the combined index value by applying the plurality of bitmasks to grouping keys. However, Chavan teaches
updating a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key [DGK] bit positions, capable of storing the maximum grouping key (see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. For each group-by column, if the width of the DGKs is not a multiple of a byte, a bitmask is set. The bit mask defines bit positions of the DGKs expanded to the nearest byte. The DGK key bit positions defined by the mask are capable of storing the maximum grouping key, which had already been accommodated by the bit width prior to the expansion.);
wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks (see e.g., p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. Since DGKs are filtered based on the bit count set in the plurality of bitmasks results, the number of DGKs are determined according to the bit counts.); and
for each row in the database table:
determining the combined index value by applying the plurality of bitmasks to grouping keys (see e.g., p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out, once the DGKs have been retrieved, Oracle DBIM starting to accumulate the results, this operation consisting of scanning a DGK array and aggregating into the array cells indexed by the DGKs., and since the first two DGKs are 0, the corresponding amounts are accumulated into the first cell of the accumulation array. After the bitmasks are applied to DGKs to filter the DGKs, the remaining may be used to index into the accumulation array.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li to update a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key bit positions, capable of storing the maximum grouping key; wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks; and for each row in the database table: determine the combined index value by applying the plurality of bitmasks to grouping keys, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 4, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein applying the aggregate function utilizes one or more SIMD instructions. However, Chavan teaches
wherein applying the aggregate function utilizes one or more SIMD instructions (see e.g., abstract for passing rows are then aggregated directly on compressed codes into DGK-indexed result buffers using SIMD and other novel aggregation techniques).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregation of Li wherein applying the aggregate function utilizes one or more SIMD instructions, as taught by Chavan, for the benefit of faster aggregation (see e.g., Chavan, abstract).
As to claim 5, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value being unable to support a cardinality of the plurality of columns of the database table. However, Chavan teaches
wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value [DGK] being unable to support a cardinality of the plurality of columns of the database table (see e.g., 1441 for filtered rows being discarded and distinct groups being identified from the remaining passing rows, a unique value called a Dense Grouping Key (DGK) being assigned to each distinct group if the grouping key columns are A and B, and the cardinality for these columns being 1000 and 2000, respectively, the max possible number of distinct groups being 1000 × 2000 = 2M, however, the passing rows identifying 100 distinct groups, and so we assign DGK values to them, where DGKs range from 0 to 99 and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out, once the DGKs have been retrieved, Oracle DBIM starting to accumulate the results, this operation consisting of scanning a DGK array and aggregating into the array cells indexed by the DGKs., and since the first two DGKs are 0, the corresponding amounts are accumulated into the first cell of the accumulation array. In response to implementing a technique that assigns the DGK values unable to support a cardinality of the plurality of columns (e.g., fewer than 2M), rows must be filtered out. Filtering may include updating bitmasks to extend the bitmasks towards a most significant bit beyond the bits of the DGK in order to extend the DGK to the nearest byte for comparison to NULL values.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value being unable to support a cardinality of the plurality of columns of the database table, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 6, the limitations of parent claim 1 have been discussed above. Li teaches
wherein at least one of the plurality of columns from the database table is dictionary compressed (see e.g., [0065] for the column dictionaries arranging the mappings in many different ways using various dictionary encodings and in an embodiment, a dictionary encoded value in a cell element being an index to an entry in a column dictionary that contains the corresponding database object value and [0134] for column dictionary containing the mapping of every unique value in the column mapped to the corresponding encoding of the value and each group-by key having a column dictionary. The group-by keys are dictionary-encoded.), and wherein decompressing the at least one of the plurality of columns is omitted when maintaining the plurality of mappings (see e.g., [0135] for the DBMS selecting a row from the row set of the loaded data portion, for the selected row, the DBMS retrieving the encoded group-by key value of the group-by key vector, the group-by key being used as an index into the payload array to retrieve the previous partial aggregate value, and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array. The encoded group-by keys do not need to be decompressed to be combined or used as an index into the payload array.).
Li does not specifically disclose wherein the plurality of mappings comprise a plurality of hash tables. However, Chavan teaches
wherein the plurality of mappings comprise a plurality of hash tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assign each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell. A hash table maps column values to codes representing grouping keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the mappings of Li wherein the plurality of mappings comprise a plurality of hash tables, as taught by Chavan, for the benefit of more efficient retrieval (see e.g., Chavan, p. 1443).
As to claim 7, the limitations of parent claim 1 have been discussed above. Li teaches
wherein the aggregate function comprises one of: sum, count, minimum, maximum, or average (see e.g., [0124] for aggregate functions including minimum, maximum, percentile, average and median among other aggregate functions).
As to claim 8, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein the database table is generated by a join operation on a plurality of database of database tables. However, Chavan teaches
wherein the database table is generated by a join operation on a plurality of database of database tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assigning each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, the food table containing a surrogate key f_id which is a unique join key as well as three attributes - Dept, Category, and Item, these being used for grouping columns, as Category is in the example query above, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell and p. 1444 for the Food dimension joining with a fact table named Sales using the join column f_id. The food table is joined to the sales table.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the table of Li wherein the database table is generated by a join operation on a plurality of database of database tables, as taught by Chavan, for the benefit of optimizing OLAP style queries (see e.g., Chavan, 1442).
As to claim 9, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein the plurality of bitmasks is configured with an initial default number of set bits. However, Chavan teaches
wherein the plurality of bitmasks is configured with an initial default number of set bits (see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. The bitmasks are set to a fixed number of bits.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein the plurality of bitmasks is configured with an initial default number of set bits, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 10, the limitations of parent claim 1 have been discussed above. Li teaches
wherein the combined count of grouping keys is configured not to exceed an upper bound [pre-defined threshold] (see e.g., [0131] for the DBMS performing a data-portion based partial aggregation only when the number of unique combination of group-by key values does not exceed a preconfigured threshold, the number of unique combination of group-by key values being determined by the dictionary(s) of the group-by keys, and for multiple group-by keys specified by the query, the multiplicative product of the lengths of the group-by key dictionaries (which is the number of grouping index values) being used for the comparison with the pre-defined threshold)).
Li does not specifically disclose wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys. However, Chavan teaches
wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys [maximum DGK value] (see e.g., see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. Since the bits set in the bitmasks are supposed to expand the DGK to the nearest byte, the bit count of the bits set in the bitmasks is limited by the count of the grouping keys, which is the maximum DGK.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 11, Li teaches one or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
retrieving a database query comprising an aggregate function of a selected column [measure key] from a database table, wherein the aggregate function is grouped by a plurality of columns [group-by keys] from the database table (see e.g., [0124] for a DBMS receiving a query specifying a “group-by” clause for the queried data set to be split based on the values of one or more columns specified in the group by clause, the “group-by key” term referring to a column of a table specified in the group-by clause of the query, the query also specifying one or more aggregate functions for aggregating columns that are selected but are not used for splitting the selected data set, aggregate functions including minimum, maximum, percentile, average and median among other aggregate functions, the “measure key” term referring to a column which is referenced by an aggregate function in the received query, and the values of the measure key being aggregated using the aggregate function of the received query);
maintaining a plurality of mappings [column dictionaries], respectively for each of the plurality of columns, that map column values to grouping keys [group-by key encoded values] and identify a maximum grouping key [maximum encoded value] (see e.g., [0065] for the column dictionaries arranging the mappings in many different ways using various dictionary encodings and in an embodiment, a dictionary encoded value in a cell element being an index to an entry in a column dictionary that contains the corresponding database object value and [0134] for column dictionary containing the mapping of every unique value in the column mapped to the corresponding encoding of the value and each group-by key having a column dictionary. A plurality of column dictionaries are maintained, respectively for each of the plurality of group-by keys. Since the column dictionaries identify each group-by key encoded value, a maximum encoded value is necessarily identified, such as the highest index value.);
storing the maximum grouping key, within a combined index value [grouping index value] (see e.g., [0129] for in an embodiment, in which multiple group-by keys are specified by the query, the DBMS combining the group-by keys into a grouping index and [0135] for in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values. The grouping index value may include group-by key encoded values, including the maximum grouping key.);
allocating a result array [payload array] sized according to a combined count of grouping keys (see e.g., [0133] for the payload array being initialized based on the group-by key column dictionary of a data portion being scanned and [0134] for in an embodiment in which multiple group-by keys are specified by the query, the payload array being initialized to the length of all possible permutations of group-by key column dictionary values, which is the multiplication of the length of each group-by key's column dictionary length (which, itself, is the number of grouping index values) and entries of the payload array being initialized to zero or empty (NULL). A payload array is allocated and sized according to a combine count of group-by key encoded values.); and
for each row in the database table [data portion]:
determining the combined index value based on grouping keys looked up in the plurality of mappings via field values from said each row in the respective plurality of columns (see e.g., [0033] for each dictionary encoded column (or the portion thereof) being produced as a column vector of the dictionary codes which are mapped to the corresponding unencoded values using the dictionary data structure and the term “column dictionary” also referring herein to such a dictionary data structure and [0135] for the DBMS scanning a data portion loaded into the main memory to process the one or more vectors and column dictionaries contained in the data portion for the group-by operation of the received query, the DBMS selecting a row from the row set of the loaded data portion, for the selected row, the DBMS retrieving the encoded group-by key value of the group-by key vector, and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array. For each row in the data portion, the grouping index value is determined based on group-by key encoded values looked up in the column dictionaries using field values from the row for the respective group-by keys.); and
applying the aggregate function on the selected column for said each row and storing a result [partial aggregate value] in the result array at the combined index value (see e.g., [0135] for the group-by key being used as an index into the payload array to retrieve the previous partial aggregate value and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array, [0136] for the DBMS applying an aggregate function to the measure key unencoded value and the previous aggregate value to determine the new aggregate value, and [0137] for after application of the new measure key unencoded value, one or more of the values of the payload array entry being updated accordingly. The aggregate function is applied on the measure key for the row. A partial aggregate value is stored in the payload array at the grouping index value.).
Li does not specifically disclose wherein the plurality of mappings comprise a plurality of hash tables. However, Chavan teaches
wherein the plurality of mappings comprise a plurality of hash tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assign each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell. A hash table maps column values to codes representing grouping keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the mappings of Li wherein the plurality of mappings comprise a plurality of hash tables, as taught by Chavan, for the benefit of more efficient retrieval (see e.g., Chavan, p. 1443).
Li does not specifically disclose updating a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key bit positions, capable of storing the maximum grouping key; wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks; and for each row in the database table: determining the combined index value by applying the plurality of bitmasks to grouping keys. However, Chavan teaches
updating a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key [DGK] bit positions, capable of storing the maximum grouping key (see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. For each group-by column, if the width of the DGKs is not a multiple of a byte, a bitmask is set. The bit mask defines bit positions of the DGKs expanded to the nearest byte. The DGK key bit positions defined by the mask are capable of storing the maximum grouping key, which had already been accommodated by the bit width prior to the expansion.);
wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks (see e.g., p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. Since DGKs are filtered based on the bit count set in the plurality of bitmasks results, the number of DGKs are determined according to the bit counts.); and
for each row in the database table:
determining the combined index value by applying the plurality of bitmasks to grouping keys (see e.g., p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out, once the DGKs have been retrieved, Oracle DBIM starting to accumulate the results, this operation consisting of scanning a DGK array and aggregating into the array cells indexed by the DGKs., and since the first two DGKs are 0, the corresponding amounts are accumulated into the first cell of the accumulation array. After the bitmasks are applied to DGKs to filter the DGKs, the remaining may be used to index into the accumulation array.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li to update a plurality of bitmasks, respectively for each of the plurality of columns, that define grouping key bit positions, capable of storing the maximum grouping key; wherein the combined count of grouping keys is based on a combined bit count set in the plurality of bitmasks; and for each row in the database table: determine the combined index value by applying the plurality of bitmasks to grouping keys, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 14, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein applying the aggregate function utilizes one or more SIMD instructions. However, Chavan teaches
wherein applying the aggregate function utilizes one or more SIMD instructions (see e.g., abstract for passing rows are then aggregated directly on compressed codes into DGK-indexed result buffers using SIMD and other novel aggregation techniques).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregation of Li wherein applying the aggregate function utilizes one or more SIMD instructions, as taught by Chavan, for the benefit of faster aggregation (see e.g., Chavan, abstract).
As to claim 15, the limitations of parent claim 1 have been discussed above. Li does not specifically disclose wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value being unable to support a cardinality of the plurality of columns of the database table. However, Chavan teaches
wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value [DGK] being unable to support a cardinality of the plurality of columns of the database table (see e.g., 1441 for filtered rows being discarded and distinct groups being identified from the remaining passing rows, a unique value called a Dense Grouping Key (DGK) being assigned to each distinct group if the grouping key columns are A and B, and the cardinality for these columns being 1000 and 2000, respectively, the max possible number of distinct groups being 1000 × 2000 = 2M, however, the passing rows identifying 100 distinct groups, and so we assign DGK values to them, where DGKs range from 0 to 99 and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out, once the DGKs have been retrieved, Oracle DBIM starting to accumulate the results, this operation consisting of scanning a DGK array and aggregating into the array cells indexed by the DGKs., and since the first two DGKs are 0, the corresponding amounts are accumulated into the first cell of the accumulation array. In response to implementing a technique that assigns the DGK values unable to support a cardinality of the plurality of columns (e.g., fewer than 2M), rows must be filtered out. Filtering may include updating bitmasks to extend the bitmasks towards a most significant bit beyond the bits of the DGK in order to extend the DGK to the nearest byte for comparison to NULL values.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein updating the plurality of bitmasks extends the plurality of bitmasks towards a most significant bit in response to the combined index value being unable to support a cardinality of the plurality of columns of the database table, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 16, the limitations of parent claim 11 have been discussed above. Li teaches
wherein at least one of the plurality of columns from the database table is dictionary compressed (see e.g., [0065] for the column dictionaries arranging the mappings in many different ways using various dictionary encodings and in an embodiment, a dictionary encoded value in a cell element being an index to an entry in a column dictionary that contains the corresponding database object value and [0134] for column dictionary containing the mapping of every unique value in the column mapped to the corresponding encoding of the value and each group-by key having a column dictionary. The group-by keys are dictionary-encoded.), and wherein decompressing the at least one of the plurality of columns is omitted when maintaining the plurality of mappings (see e.g., [0135] for the DBMS selecting a row from the row set of the loaded data portion, for the selected row, the DBMS retrieving the encoded group-by key value of the group-by key vector, the group-by key being used as an index into the payload array to retrieve the previous partial aggregate value, and in an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values being combined to generate grouping index values for referencing the corresponding entries in the payload array. The encoded group-by keys do not need to be decompressed to be combined or used as an index into the payload array.).
Li does not specifically disclose wherein the plurality of mappings comprise a plurality of hash tables. However, Chavan teaches
wherein the plurality of mappings comprise a plurality of hash tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assign each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell. A hash table maps column values to codes representing grouping keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the mappings of Li wherein the plurality of mappings comprise a plurality of hash tables, as taught by Chavan, for the benefit of more efficient retrieval (see e.g., Chavan, p. 1443).
As to claim 17, the limitations of parent claim 11 have been discussed above. Li teaches
wherein the aggregate function comprises one of: sum, count, minimum, maximum, or average (see e.g. [0124] for aggregate functions including minimum, maximum, percentile, average and median among other aggregate functions).
As to claim 18, the limitations of parent claim 11 have been discussed above. Li does not specifically disclose wherein the database table is generated by a join operation on a plurality of database of database tables. However, Chavan teaches
wherein the database table is generated by a join operation on a plurality of database of database tables (see e.g., p. 1443 for identifying unique combinations of grouping keys and assigning each a surrogate code, these codes being called Dense Grouping Keys, Group-by using the DGK as an efficient substitute for the original grouping key, the food table containing a surrogate key f_id which is a unique join key as well as three attributes - Dept, Category, and Item, these being used for grouping columns, as Category is in the example query above, once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated, indexing into the array being performed using the join-keys of the corresponding dimension table, if the join-keys are integers, the index range of the Key Vector being determined by subtracting the smallest integer join-key from the largest join-key, then the DGK that corresponds with each join-key being written into the corresponding cell of the Key-Vector, and if the join-keys are non-integers, a hash-table being used instead of an array and the DGK is stored as the value of each hash cell and p. 1444 for the Food dimension joining with a fact table named Sales using the join column f_id. The food table is joined to the sales table.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the table of Li wherein the database table is generated by a join operation on a plurality of database of database tables, as taught by Chavan, for the benefit of optimizing OLAP style queries (see e.g., Chavan, 1442).
As to claim 19, the limitations of parent claim 11 have been discussed above. Li does not specifically disclose wherein the plurality of bitmasks is configured with an initial default number of set bits. However, Chavan teaches
wherein the plurality of bitmasks is configured with an initial default number of set bits (see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. The bitmasks are set to a fixed number of bits.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein the plurality of bitmasks is configured with an initial default number of set bits, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
As to claim 20, the limitations of parent claim 11 have been discussed above. Li teaches
wherein the combined count of grouping keys is configured not to exceed an upper bound [pre-defined threshold] (see e.g., [0131] for the DBMS performing a data-portion based partial aggregation only when the number of unique combination of group-by key values does not exceed a preconfigured threshold, the number of unique combination of group-by key values being determined by the dictionary(s) of the group-by keys, and for multiple group-by keys specified by the query, the multiplicative product of the lengths of the group-by key dictionaries (which is the number of grouping index values) being used for the comparison with the pre-defined threshold)).
Li does not specifically disclose wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys. However, Chavan teaches
wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys [maximum DGK value] (see e.g., see e.g., p. 1443 for once the DGKs have been determined, an in-memory array called a Key Vector (KV) being allocated and the size of each cell being the bit-width of the maximum DGK value and p. 1447 for DGK filtering being a simple operation that requires reading a join key, indexing into an array Key Vector to retrieve the corresponding DGK, and comparing the DGK against the null token to see if the row has been filtered out, loading a join key and converting it into an offset to index into a Key Vector, gathering the corresponding DGK from the Key Vector and applying a bitmask if the bit-width of the DGK is not a multiple of a byte, comparing the DGK against the null token, and if the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector being set to indicate that the row has been filtered out. Since the bits set in the bitmasks are supposed to expand the DGK to the nearest byte, the bit count of the bits set in the bitmasks is limited by the count of the grouping keys, which is the maximum DGK.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the grouping index value of Li wherein the combined bit count set in the plurality of bitmasks is limited by the combined count of grouping keys, as taught by Chavan, for the benefit of filtering grouping keys (see e.g., Chavan, p. 1447).
Claims 2, 3, 12, and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (US Publication No. 2018/0089261) in view of Chavan et al. (NPL entitled “Accelerating Joins and Aggregations on the Oracle In-Memory Database,” dated 2018) as applied to claims 1, 4-11, and 14-20 above, and further in view of Attaluri et al. (US Publication No. 2017/0344621).
As to claim 2, the limitations of parent claim 1 have been discussed above. Li in view of Chavan does not specifically disclose wherein applying the aggregate function for each row in the database table is performed by parallel threads. However, Attaluri teaches
wherein applying the aggregate function for each row in the database table is performed by parallel threads (see e.g., [0024] for the example being a 2-parallel-element case with a table T, which has a definition of (G integer, A integer, B integer) and has 9 rows: (10, 13, 1), (1, 3, 2), (10, 2, 2), (1, 4, 20), (3, 1, 4), (1, 3, 3), (5, 6, 1), (1, 4, 4), (3, 5, 1) and the query to be processed being “select G, count (distinct A), sum (B) from T group by G” and [0034] for at this point, local aggregations of multiple groups having a same grouping key being performed and results saved in the hash table (act 322), locally aggregating (10, 13, 1) and (10, 2, 2) from the first thread results in G:10, count distinct A set (A:13, A:2), sum B:3=G:10, count distinct A:2, sum B:3, locally aggregating (1, 3, 2) and (1, 4, 20) from the first thread resulting in G:1, count distinct A set{A:3, A:4}, sum B:22 =G:1, count distinct A:2, sum B:22, local aggregation of (1, 3, 3) and (1, 4, 4) from the second thread resulting in G:1, count distinct A set (A:3, A:4), sum B:7=G:1, count distinct A:2, sum B:7, the partial aggregation for grouping key 1 of the first thread being G:1, count distinct A set{A:3, A:4}, sum B:22=G:1, count distinct A:2, sum B:22 and the partial aggregation for group ID 1 of the second thread being G:1, count distinct A set (A:3, A:4), sum B:7=G.1, count distinct A:2, sum B:7, merging the two partial aggregations resulting in G:1, count distinct A set {A:3, A:4}, sum B:29 =G:1, count distinct A:2, sum B:29, and merging the single occurrence of group ID 3 of the first thread, (3, 1, 4) with the single occurrence of group ID 3 in the second thread, (3, 5, 1) resulting in G:3, distinct A set{1, 5}, sum B:5=G:3, distinct A:2, sum B:5).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregating of Li in view of Chavan wherein applying the aggregate function for each row in the database table is performed by parallel threads, as taught by Attaluri, for the benefit of increasing efficiency and reducing costs (see e.g., Attaluri, [0003]-[0006] and [0031]).
As to claim 3, the limitations of parent claim 1 have been discussed above. Li in view of Chavan does not specifically disclose wherein applying the aggregate function for each row in the database table is performed by coalescing and queuing the aggregate function in parallel for independent indexes in the result array. However, Attaluri teaches
wherein applying the aggregate function for each row in the database table is performed by coalescing and queuing the aggregate function in parallel for independent indexes [grouping keys] in the result array (see e.g., [0024] for the example being a 2-parallel-element case with a table T, which has a definition of (G integer, A integer, B integer) and has 9 rows: (10, 13, 1), (1, 3, 2), (10, 2, 2), (1, 4, 20), (3, 1, 4), (1, 3, 3), (5, 6, 1), (1, 4, 4), (3, 5, 1) and the query to be processed being “select G, count (distinct A), sum (B) from T group by G” and [0034] for at this point, local aggregations of multiple groups having a same grouping key being performed and results saved in the hash table (act 322), locally aggregating (10, 13, 1) and (10, 2, 2) from the first thread results in G:10, count distinct A set (A:13, A:2), sum B:3=G:10, count distinct A:2, sum B:3, locally aggregating (1, 3, 2) and (1, 4, 20) from the first thread resulting in G:1, count distinct A set{A:3, A:4}, sum B:22 =G:1, count distinct A:2, sum B:22, local aggregation of (1, 3, 3) and (1, 4, 4) from the second thread resulting in G:1, count distinct A set (A:3, A:4), sum B:7=G:1, count distinct A:2, sum B:7, the partial aggregation for grouping key 1 of the first thread being G:1, count distinct A set{A:3, A:4}, sum B:22=G:1, count distinct A:2, sum B:22 and the partial aggregation for group ID 1 of the second thread being G:1, count distinct A set (A:3, A:4), sum B:7=G.1, count distinct A:2, sum B:7, merging the two partial aggregations resulting in G:1, count distinct A set {A:3, A:4}, sum B:29 =G:1, count distinct A:2, sum B:29, and merging the single occurrence of group ID 3 of the first thread, (3, 1, 4) with the single occurrence of group ID 3 in the second thread, (3, 5, 1) resulting in G:3, distinct A set{1, 5}, sum B:5=G:3, distinct A:2, sum B:5).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregating of Li in view of Chavan wherein applying the aggregate function for each row in the database table is performed by coalescing and queuing the aggregate function in parallel for independent indexes in the result array, as taught by Attaluri, for the benefit of increasing efficiency and reducing costs (see e.g., Attaluri, [0003]-[0006] and [0031]).
As to claim 12, the limitations of parent claim 11 have been discussed above. Li in view of Chavan does not specifically disclose wherein applying the aggregate function for each row in the database table is performed by parallel threads. However, Attaluri teaches
wherein applying the aggregate function for each row in the database table is performed by parallel threads (see e.g., [0024] for the example being a 2-parallel-element case with a table T, which has a definition of (G integer, A integer, B integer) and has 9 rows: (10, 13, 1), (1, 3, 2), (10, 2, 2), (1, 4, 20), (3, 1, 4), (1, 3, 3), (5, 6, 1), (1, 4, 4), (3, 5, 1) and the query to be processed being “select G, count (distinct A), sum (B) from T group by G” and [0034] for at this point, local aggregations of multiple groups having a same grouping key being performed and results saved in the hash table (act 322), locally aggregating (10, 13, 1) and (10, 2, 2) from the first thread results in G:10, count distinct A set (A:13, A:2), sum B:3=G:10, count distinct A:2, sum B:3, locally aggregating (1, 3, 2) and (1, 4, 20) from the first thread resulting in G:1, count distinct A set{A:3, A:4}, sum B:22 =G:1, count distinct A:2, sum B:22, local aggregation of (1, 3, 3) and (1, 4, 4) from the second thread resulting in G:1, count distinct A set (A:3, A:4), sum B:7=G:1, count distinct A:2, sum B:7, the partial aggregation for grouping key 1 of the first thread being G:1, count distinct A set{A:3, A:4}, sum B:22=G:1, count distinct A:2, sum B:22 and the partial aggregation for group ID 1 of the second thread being G:1, count distinct A set (A:3, A:4), sum B:7=G.1, count distinct A:2, sum B:7, merging the two partial aggregations resulting in G:1, count distinct A set {A:3, A:4}, sum B:29 =G:1, count distinct A:2, sum B:29, and merging the single occurrence of group ID 3 of the first thread, (3, 1, 4) with the single occurrence of group ID 3 in the second thread, (3, 5, 1) resulting in G:3, distinct A set{1, 5}, sum B:5=G:3, distinct A:2, sum B:5).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregating of Li in view of Chavan wherein applying the aggregate function for each row in the database table is performed by parallel threads, as taught by Attaluri, for the benefit of increasing efficiency and reducing costs (see e.g., Attaluri, [0003]-[0006] and [0031]).
As to claim 13, the limitations of parent claim 11 have been discussed above. Li in view of Chavan does not specifically disclose wherein applying the aggregate function for each row in the database table is performed by parallel threads. However, Attaluri teaches
wherein applying the aggregate function for each row in the database table is performed by parallel threads (see e.g., [0024] for the example being a 2-parallel-element case with a table T, which has a definition of (G integer, A integer, B integer) and has 9 rows: (10, 13, 1), (1, 3, 2), (10, 2, 2), (1, 4, 20), (3, 1, 4), (1, 3, 3), (5, 6, 1), (1, 4, 4), (3, 5, 1) and the query to be processed being “select G, count (distinct A), sum (B) from T group by G” and [0034] for at this point, local aggregations of multiple groups having a same grouping key being performed and results saved in the hash table (act 322), locally aggregating (10, 13, 1) and (10, 2, 2) from the first thread results in G:10, count distinct A set (A:13, A:2), sum B:3=G:10, count distinct A:2, sum B:3, locally aggregating (1, 3, 2) and (1, 4, 20) from the first thread resulting in G:1, count distinct A set{A:3, A:4}, sum B:22 =G:1, count distinct A:2, sum B:22, local aggregation of (1, 3, 3) and (1, 4, 4) from the second thread resulting in G:1, count distinct A set (A:3, A:4), sum B:7=G:1, count distinct A:2, sum B:7, the partial aggregation for grouping key 1 of the first thread being G:1, count distinct A set{A:3, A:4}, sum B:22=G:1, count distinct A:2, sum B:22 and the partial aggregation for group ID 1 of the second thread being G:1, count distinct A set (A:3, A:4), sum B:7=G.1, count distinct A:2, sum B:7, merging the two partial aggregations resulting in G:1, count distinct A set {A:3, A:4}, sum B:29 =G:1, count distinct A:2, sum B:29, and merging the single occurrence of group ID 3 of the first thread, (3, 1, 4) with the single occurrence of group ID 3 in the second thread, (3, 5, 1) resulting in G:3, distinct A set{1, 5}, sum B:5=G:3, distinct A:2, sum B:5).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the aggregating of Li in view of Chavan wherein applying the aggregate function for each row in the database table is performed by parallel threads, as taught by Attaluri, for the benefit of increasing efficiency and reducing costs (see e.g., Attaluri, [0003]-[0006] and [0031]).
Response to Arguments
Applicant's arguments filed March 20, 2026 have been fully considered but they are not persuasive.
On pages 7-8 of Applicant’s Response, Applicant argues:
Applicant respectfully disagrees. The Office Action appears to interpret the cited portions
of Chavan and Li as teaching that hash tables should be maintained for each of the plurality of
columns. However, the teachings of Chavan are contrary to this interpretation. For example, page
1442 of Chavan states that "A typical data warehouse's schema will have some number of small
dimension tables that have a numeric primary key" (emphasis added). Thus, Chavan establishes
that a typical dimension table used for aggregate joins stores a numeric primary key, such as an
integer. Page 1443 of Chavan further states that "If [and only if] the join-keys are non-integers, a hash table is used instead of an array" (emphasis added). Thus, only in the exceptional non-typical case where the primary key in the dimension table is a non-numeric data type, a hash table is used in that specific case only, whereas if the primary key is numeric, the "key vector (KV)" array without a hash table is used instead. Accordingly, the proposed combination of Li and Chavan fail to teach or suggest "maintaining a plurality of hash tables, respectively for each of the plurality of columns, that map column values to grouping keys and identify a maximum grouping key", as the proposed combination of Li and Chavan only suggests maintaining a hash table in the atypical case where the join-key is a non-integer data type, rather than unconditionally for every column of the plurality of columns as recited in Claim 1.
Examiner respectfully disagrees with Applicant’s arguments. Chavan’s disclosure of hash tables mapping column values to grouping keys may be applied to each of a plurality of columns, regardless of the hash table being one of Chavan’s multiple embodiments. According to a MPEP § 2123 (I), a reference may be relied upon for all that it would have reasonably suggested to one having ordinary skill in the art, including nonpreferred embodiments. Merck & Co. v. Biocraft Labs., Inc. 874 F.2d 804, 10 USPQ2d 1843 (Fed. Cir. 1989), cert. denied, 493 U.S. 975 (1989) (emphasis added). Chavan recites that “[i]f the join-keys are non-integers, a hash-table is used instead of an array and the DGK is stored as the value of each hash cell” (see p. 1443). Chavan’s limitation of using hash tables when join-keys are non-integers does not preclude Chavan from using hash tables for each of a plurality of columns. Chavan never limits the number of columns using non-integer join-keys. It would have been obvious to one of ordinary skill in the art that when multiple columns have non-integer join keys, a hash table for each of the columns may map the column values to DGKs, even if such a situation is not “typical.” Accordingly, Li in view of Chavan sufficiently teaches “maintaining a plurality of hash tables, respectively for each of the plurality of columns, that map column values to grouping keys,” as recited by claim 1.
On page 8 of Applicant’s Response, Applicant argues:
Yet further, Chavan teaches away from maintaining a plurality of hash tables for the plurality of columns for memory efficiency reasons, which are especially relevant for the in-memory databases that Chavan seeks to improve. For example, page 1443 of Chavan states: "For a dimension table with perfectly dense keys a Key Vector is commonly less than one byte per row. In contrast, a hash table must encode the full key value, as well as any grouping key values and necessary padding for efficient hash operations." Thus, Chavan states that maintaining the memory-efficient, or "commonly less than one byte per row" "Key Vector" array with no hash table is preferable in terms of memory footprint compared to using hash tables that need to (1) encode the full key value, (2) store grouping key values, and (3) add padding (e.g. to byte or word boundaries) for efficient hash table operations. Accordingly, a person of ordinary skill in the art would not combine Chavan and Li in the manner suggested by the Office Action.
Examiner respectfully disagrees with Applicant’s arguments. Chavan does not teach away from maintaining a plurality of hash tables for the plurality of columns. According to a MPEP § 2123 (II), disclosed examples and preferred embodiments do not constitute a teaching away from a broader disclosure or nonpreferred embodiments. In re Susi, 440 F.2d 442, 169 USPQ 423 (CCPA 1971). "A known or obvious composition does not become patentable simply because it has been described as somewhat inferior to some other product for the same use." In re Gurley, 27 F.3d 551, 554, 31 USPQ2d 1130, 1132 (Fed. Cir. 1994). Also according to MPEP § 2123 (II), furthermore, "[t]he prior art’s mere disclosure of more than one alternative does not constitute a teaching away from any of these alternatives because such disclosure does not criticize, discredit, or otherwise discourage the solution claimed…." In re Fulton, 391 F.3d 1195, 1201, 73 USPQ2d 1141, 1146 (Fed. Cir. 2004). Here, although a hash table is not Chavan’s preferred method for integer join-keys, Chavan explicitly encourages hash tables for columns with non-integer join-keys. Since hash tables are the preferred embodiment for certain situations, Chavan does not criticize, discredit, or otherwise discourage maintaining a plurality of hash tables for the plurality of columns. Despite their memory usage, one of ordinary skill in the art would have been motivated to combine Chavan’s hash tables with Li’s mappings for the benefit of time-efficient retrieval.
On page 10 of Applicant’s Response, Applicant argues:
Applicant respectfully disagrees. For example, page 1447 of Chavan states that "Once an offset has been computed, line 5 gathers the corresponding DGK from the Key Vector and applies a bitmask if the bit-width of the DGK is not a multiple of a byte. Line 6 compares the DGK against the null token [or all bits set, as per page 1443 of Chavan]. If the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector is set to indicate that the row has been filtered out" (emphasis added). Thus, the bitmask of Chavan is disclosed for the purpose of masking a DGK to its actual number of used bits, since the DGK is previously padded to the nearest word (or byte) as disclosed in page 1443 of Chavan, while reserving at least one bit if needed for the "null token", wherein all bits are set. This is precisely why the bitmask is not applied if the DGK is a multiple of a byte, since in that case no padding was previously added and no bitmask needs to be applied to obtain only the used bits of the DGK. Accordingly, it should be clear to one of ordinary skill in the art that the bitmask of Chavan is not used to define the "grouping key bit positions... within a combined index value" (emphasis added) as recited by Claim 1, but instead the bitmask of Chavan is only used to mask off unused padding bits.
Examiner respectfully disagrees with Applicant’s arguments. Li in view of Chavan teaches bitmasks that define grouping key bit positions within a combined index value. In response to Applicant's arguments against the references individually, one cannot show nonobviousness by attacking references individually where the rejections are based on combinations of references. See In re Keller, 642 F.2d 413, 208 USPQ 871 (CCPA 1981); In re Merck & Co., 800 F.2d 1091, 231 USPQ 375 (Fed. Cir. 1986). Li recites that “[i]n an embodiment, in which multiple group-by keys are specified by the query, . . . . the DBMS may combine the group-by keys into a grouping index” (see [0129]). Li’s “grouping index” may correspond to the claimed “combined index value.” However, Li does not disclose a bitmask defining grouping key bit positions. Chavan recites that “line 5 gathers the corresponding DGK from the Key Vector and applies a bitmask if the bit-width of the DGK is not a multiple of a byte. Line 6 compares the DGK against the null token. If the value of the DGK is equal to the value of the null token, the corresponding bit in the output bit-vector is set to indicate that the row has been filtered out” (p. 1447). Chavan does not explicitly teach that “the bitmask of Chavan is disclosed for the purpose of masking a DGK to its actual number of used bits,” as argued by Applicant on p. 10 of Applicant’s arguments. But even assuming that Applicant’s characterization of Chavan’s bitmask masking off padding bits were correct, which Examiner does not concede, then Chavan’s bitmask still identifies the grouping key bit positions that are not padding. One of ordinary skill in the art would be motivated to apply Chavan’s bitmask to Li’s combined grouping key for the purpose of filtering Li’s combined grouping keys in the manner taught by Chavan. Applying Chavan’s bitmask to Li’s grouping key would involve Chavan’s bitmask indicating the grouping key bit positions of Li’s combined grouping key similar to how Chavan’s bitmask indicates grouping key bit positions of Chavan’s DGK. Therefore, Li in view of Chavan sufficiently teaches “updating a plurality of bitmasks . . . that define grouping key bit positions . . . within a combined index value,” as recited by claim 1.
On pages 10-11 of Applicant’s Response, Applicant argues:
Further, as discussed in e.g. paragraph [0014] of the Specification, the claimed features, or the bitmasks that define bit positions within a combined index value enable the advantage of allowing any of the grouping keys to be dynamically and independently grown during a query, which allows existing keys to be used as-is without remapping. See, e.g. FIG. 4A and FIG. 4B and related text in the Specification; column "State" can be expanded from 5 bits to 6 bits by appending bits to bitmasks 152 while avoiding any remapping of existing entries in hash table 410A. On the other hand, the proposed combination of Li and Chavan is not understood to teach bitmasks that define bit positions within a combined index value, but only to suggest a combined index value that either (1) concatenates all of the word padded DGKs together, or (2) concatenates all of the bits of each DGK naively together. For case (1), a significant number of bits are wasted due to the padding, and growing any DGK (other than the last DGK) beyond a byte boundary requires a computationally expensive remapping procedure. For case (2), the remapping procedure is also required for every DGK that is grown (other than the last DGK). These inefficiencies in memory footprint and computational resource usage in the operation of a database system can be bypassed when using the novel features of the bitmasks recited in Claim 1.
Examiner respectfully disagrees with Applicant’s arguments. As discussed above, Li in view of Chavan teaches bitmasks that define grouping key bit positions within a combined index value. In response to Applicant's argument that the references fail to show certain features of the invention, it is noted that the features upon which applicant relies (i.e., “allowing any of the grouping keys to be dynamically and independently grown during a query, which allows existing keys to be used as-is without remapping”) are not recited in the rejected claim(s). Although the claims are interpreted in light of the specification, limitations from the specification are not read into the claims. See In re Van Geuns, 988 F.2d 1181, 26 USPQ2d 1057 (Fed. Cir. 1993). Here, claim 1 broadly recites “updating a plurality of bitmasks . . . that define grouping key bit positions . . . within a combined index value,” which does not recite sufficient detail to require the advantages argued by Applicant. For the reasons stated above, Li in view of Chavan sufficiently teach the broadly claimed limitations of claim 1.
On page 12 of Applicant’s Response, Applicant argues:
Applicant respectfully disagrees. As discussed above, the "bitmask" of Chavan is used for the purpose of masking unused bits, not defining bit positions within a combined index value. Accordingly, the "bitmask" of Chavan, by definition, cannot teach "determining the combined index value by applying the plurality of bitmasks to grouping keys", since the bitmasks of Chavan are understood to be silent with regards to the bit positions of keys within a combined index value.
Examiner respectfully disagrees with Applicant’s arguments. Li in view of Chavan teaches determining the combined index value by applying the plurality of bitmasks to grouping keys. In response to Applicant's arguments against the references individually, one cannot show nonobviousness by attacking references individually where the rejections are based on combinations of references. See In re Keller, 642 F.2d 413, 208 USPQ 871 (CCPA 1981); In re Merck & Co., 800 F.2d 1091, 231 USPQ 375 (Fed. Cir. 1986). Li teaches that “[i]n an embodiment in which the query specifies multiple group-by keys, the multiple group-by key encoded values are combined to generate grouping index values for referencing the corresponding entries in the payload array” (see [0135]). Since Li’s “group-by key encoded values” correspond to the claimed “grouping keys” and Li’s “grouping index value” corresponds to the claimed “combined index value,” Li teaches determining the combined index value based on grouping keys. However, Li does not teach applying bitmasks to the grouping keys. As detailed above, Chavan teaches applying bitmasks to DGKs. A person of ordinary skill in the art would have been motivated to apply the filtering process of Chavan to the group-by key encoded values constituting the combined index value of Li, which involves applying bitmasks to Li’s group-by key encoded values. By performing the filtering process to Li’s group-by key encoded values, the unfiltered remaining grouping index values would be determined. Since the combination of Li and Chavan teaches determining Li’s grouping index value by applying Chavan’s plurality of bitmasks to Li’s group-by encoded values, the combination also teaches “determining the combined index value by applying the plurality of bitmasks to grouping keys,” as recited by claim 1.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Ansberry et al. (US Patent No. 5,640,540) for “When looking up a keysym for a key code/modifier combination, an application uses the first group of keysyms unless the group modifier (in the modifier bitmask) is set to on, in which the case the second group of keysyms will be used” (see col. 4., line 15-22).
Hopeman et al. (US Publication No. 2018/0081939) for “a hash table is created that includes the join key value that is associated with more than one dense grouping key value and each of the corresponding dense grouping key values of the join key value as a DGK set” (see [0056]).
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DARA J GLASSER whose telephone number is (571)270-3666. The examiner can normally be reached Monday-Thursday, 10:00am-2:00pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Apu Mofiz can be reached at (571)272-4080. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
04-08-2026
/DARA J GLASSER/Examiner, Art Unit 2161
/APU M MOFIZ/Supervisory Patent Examiner, Art Unit 2161
Prosecution Insights