DETAILED ACTION
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 .
Claims 1-20 are presented for examination.
The claims and only the claims form the metes and bounds of the invention. “Office personnel are to give claims their broadest reasonable interpretation in light of the supporting disclosure. In re Morris, 127 F.3d 1048, 1054-55, 44 USPQ2d 1023, 1027-28 (Fed. Cir. 1997). Limitations appearing in the specification but not recited in the claim are not read into the claim. In re Prater, 415 F.2d 1393, 1404-05, 162 USPQ 541, 550-551 (CCPA 1969)” (MPEP p 2100-8, c 2, I 45-48; p 2100-9, c 1, l 1-4). The Examiner has full latitude to interpret each claim in the broadest reasonable sense. The Examiner will reference prior art using terminology familiar to one of ordinary skill in the art. Such an approach is broad in concept and can be either explicit or implicit in meaning.
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claims 1-2, 4-8, 10-11, 13-17 and 19 are rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-2 and 5-8 of U.S. Patent No. 12,118,041.
Although the claims at issue are not identical, they are not patentably distinct from each other because following the rationale in In re Goodman, cited above, where applicant has once been granted a patent containing a claim for the specific or narrower invention, applicant may not then obtain a second patent with a claim for the generic or broader invention without first submitting an appropriate terminal disclaimer.
Instant Application
US Patent No. 12,118,041
1. A database system comprising: memory; and a processor configured to execute instructions stored in the memory to: execute a database query, wherein, to execute the database query the processor executes the instructions to:
in response to the database query, allocate a portion of the memory for decompression of a table stored as compressed table data; determine whether the table is a fact table;
in response to a determination that the table is a fact table, decompress the compressed table data into the portion of the memory to obtain uncompressed table data; and
access a portion of the uncompressed table data from the portion of the memory to generate results data responsive to the database query;
in response to the generation of the results data, deallocate the portion of the memory; and output the results data.
1. An apparatus for query execution on compressed in-memory data, comprising: a processor of an instance of a distributed in-memory database, the processor configured to: receive a query for data from a table stored in the distributed in-memory database as compressed table data; obtain results data responsive to the query from the table by:
subsequent to receiving the query, allocating memory for decompressing the compressed table data;
obtaining uncompressed table data by decompressing the compressed table data into the allocated memory based on a database schema of the distributed in-memory database by decompressing the compressed table data in response to a determination that the database schema indicates that the compressed table data corresponds to a fact table, wherein, to obtain the uncompressed table data, the processor is configured to decompress at least a subset of the compressed table data into a first temporary buffer of the allocated memory; and obtaining the results data from the uncompressed table data, wherein to obtain the results data, the processor is configured to access the first temporary buffer; and
in response to obtaining the results data, deallocate the allocated memory; and output the results data for presentation to a user.
2. The apparatus of claim 1, wherein: the table comprises a set of rows within a column; the compressed table data comprises compressed table data portions, wherein a respective compressed table data portion comprises a proper subset of the set of rows compressed independently of other compressed table data portions.
2. The apparatus of claim 1, wherein: the table comprises a set of rows within a column, the compressed table data comprises multiple compressed table data portions, each of the multiple compressed table data portions comprises a proper subset of the set of rows, and each proper subset is compressed independently of each other.
4. The apparatus of claim 3, wherein, to decompress the compressed table data, the processor executes the instructions to decompress the compressed table data using at least one of dictionary coding or variable-length coding.
6. The apparatus of claim 4, wherein the processor is configured to decompress the compressed table data by: decompressing the data values using at least one of dictionary coding or variable-length coding based on the data type.
5. The apparatus of claim 4, wherein, to decompress the compressed table data, the processor executes the instructions to: determine whether the data type is a measure data type or a string data type.
5. The apparatus of claim 4, wherein the processor is further configured to identify the data type based on a column type of the respective column, wherein the column type of a respective column comprises one of a measure column or a string column.
6. The apparatus of claim 5, wherein, to decompress the compressed table data, the processor executes the instructions to: in response to a determination that the data type is the measure data type, decompress the compressed table data of the column using variable-length coding.
7. The apparatus of claim 5, wherein, to decompress the compressed table data, the processor executes the instructions to: in response to a determination that the data type is the string data type, decompress the compressed table data of the column using dictionary coding.
7. The apparatus of claim 1, wherein the processor is configured to decompress the compressed table data by: decompressing data values of the compressed table data that have a data type of measure data using variable-length coding; and
decompressing data values of the compressed table data that have a data type of string data using at least one of dictionary coding or variable-length coding.
8. The apparatus of claim 7, wherein, to decompress the compressed table data of the column using dictionary coding, processor executes the instructions to decompress a dictionary for the dictionary coding using variable-length coding.
8. The apparatus of claim 7, wherein the processor is configured to decompress a dictionary for the dictionary coding using variable-length coding.
Claim 10 (a method claim) corresponds in scope to Claim 1, and is similarly rejected.
Claim 19 (a storage medium claim) corresponds in scope to Claim 1, and is similarly rejected.
Claim 11 (a method claim) corresponds in scope to Claim 2, and is similarly rejected.
Claim 13 (a method claim) corresponds in scope to Claim 4, and is similarly rejected.
Claim 14 (a method claim) corresponds in scope to Claim 5, and is similarly rejected.
Claim 15 (a method claim) corresponds in scope to Claim 6, and is similarly rejected.
Claim 16 (a method claim) corresponds in scope to Claim 7, and is similarly rejected.
Claim 17 (a method claim) corresponds in scope to Claim 8, and is similarly rejected.
Claim Objection
Claims 18 and 20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Claim Rejections - 35 USC § 103
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.
Claims 1-3, 10-12 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over US PGPUB 2016/0350347 by Das et al. (“Das”) in view of US PGPUB 2013/0031139 by Chen et al. (“Chen”), and further in view of NPL “Integrating Compression and Execution in Column-Oriented Database Systems” by Abadi et al. (“Abadi”).
As to Claim 1, Das teaches a database system comprising: memory; and a processor configured to execute instructions stored in the memory to: execute a database query (Das: at least ¶0054; “Query execution is starts with scan operations on the necessary data followed by subsequent database operations (joins, aggregates, etc.)”), wherein, to execute the database query the processor executes the instructions to: in response to the database query (Das: at least 0054; “Query execution is starts with scan operations on the necessary data followed by subsequent database operations (joins, aggregates, etc.) For in-memory scans, IMCUs are decompressed”; note: query would be received for execution), allocate a portion of the memory for decompression of a table stored as compressed table data (Das: at least ¶0054; “IMCUs are decompressed, scanned CU by CU, and then the data items are stitched together to form rows. These rows are served to the query execution engine, so the query execution engine may perform”; ¶0008 further discloses “in-memory scan involves scanning blocks of columnar units, decompressing the columnar units, and then stitching the columnar units back into rows” and ¶0134 discloses “data from the second table is only decompressed, stitched, and transferred to other nodes in the cluster if the data passes through the join filter in addition to any other filters”; note: memory to stored decompressed data are allocated); decompress the compressed table data into the portion of the memory to obtain uncompressed table data (Das: at least ¶0054; “IMCUs are decompressed, scanned CU by CU, and then the data items are stitched together to form rows. These rows are served to the query execution engine, so the query execution engine may perform”; ¶0008 further discloses “in-memory scan involves scanning blocks of columnar units, decompressing the columnar units, and then stitching the columnar units back into rows” and ¶0134 discloses “data from the second table is only decompressed, stitched, and transferred to other nodes in the cluster if the data passes through the join filter in addition to any other filters”); and
access a portion of the uncompressed table data from the portion of the memory to generate results data responsive to the database query (Das: at least ¶0103; “CU may need to be decompressed in order to evaluate the condition of the predicate against the data items in the CU. Consider a predicate with the condition c BETWEEN(2,10). The data items are decompressed, and the condition is then applied to each data item in CU c1 to determine if the condition c BETWEEN(2, 10) is met”; ¶0105 also discloses “data items from CU a1, b1, and d1 that are in the same rows as the data items that meet the condition for c1 are decompressed, and these data items are stitched with their corresponding data items in the IMCU” and “R6 is the only row that needs to be stitched together because all other rows have been filtered”); and
output the results data (Das: at least ¶0105; “evaluating complex predicates against decompressed rows that are stitched together”; ¶0113 then discloses “results 306 that meet the predicate's conditions are aggregated in a single node 102 and sent back to the requesting application”; ¶0006 also discloses “returning data items from a table to the requesting user or application”).
Das does not explicitly disclose, but Chen discloses in response to the generation of the results data, deallocate the portion of the memory (Chen: at least ¶0022; “returns the last result to the query processor in step 430 before terminating” and “the query processor receives the last result, deallocates the memory buffers, and deconfigures anything else configured by the query processor”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Chen’s feature of in response to the generation of the results data, deallocate the portion of the memory (Chen: at least ¶0022) with the apparatus disclosed by Das.
The suggestion/motivation for doing so would have been to reclaim memory resources used during query execution (Chen: at least Abstract; “uses three different memory buffers, the contents of which are maintained for three different time periods, to compute and return to the database-query processor multiple outputs in response to at least one of the multiple inputs”; ¶0022 also discloses “two memory buffers used by the UDF for storing information, including storing relational-table tuples or other” and “deallocates the memory buffers” after ““receives the last result”).
Das and Chen do not explicitly disclose, but Abadi discloses determine whether the table is a fact table; and in response to a determination that the table is a fact table, decompress the compressed table data into the portion of the memory to obtain uncompressed table data (Abadi: at least 6. Experimental Results on left column of pg. 677; “we used columns from the lineitem fact table at scale 10 which consists of just under 60,000,000 lineitems” and “in the first variation, we required the column to be decompressed as it was brought off disk. In the second variation, we lazily decompressed the data and allowed operators to apply optimizations to compressed data”; para. 2 on left column of pg. 681 further discloses “assume for this query that CSTORE P1 is a projection from the fact table and that CSTORE P2 is a projection from a dimension table that contains its primary key (which is the common join case in star schema queries)”; note: decompressing based on queries on star schema).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Abadi’s features of determine whether the table is a fact table; and in response to a determination that the table is a fact table, decompress the compressed table data into the portion of the memory to obtain uncompressed table data (Abadi: at least 6. Experimental Results on left column of pg. 677, para. 2 on left column of pg. 681) with the apparatus disclosed by Das and Chen.
The suggestion/motivation for doing so would have been to implement column-oriented database storage that “greatly increases the similarity of adjacent records on disk and thus opportunities for compression” (Abadi: at least Abstract).
Claim 10 (a method claim) corresponds in scope to Claim 1, and is similarly rejected.
Claim 19 (a storage medium claim) corresponds in scope to Claim 1, and is similarly rejected.
As to Claim 2, Das, Chen and Abadi teach the apparatus of claim 1, wherein: the table comprises a set of rows within a column (Das: at least ¶0035; “IMCUs 114, 119 contain items extracted from a set of rows of table 164”); the compressed table data comprises compressed table data portions (Das: at least ¶0007; “in-memory copies of the tables, or portions thereof, are organized into “in-memory compression units” (IMCUs)”; ¶¶0040-0041 further discloses “items from each column of table 164 are stored separately and contiguously as columnar units (CUs)” and “each column may be compressed at different compression levels”), wherein a respective compressed table data portion comprises a proper subset of the set of rows (Das: at least ¶0040 further discloses “items from each column of table 164 are stored separately and contiguously as columnar units (CUs)” and “each group of CUs from an IMCU respectively contains items of table 164 from columns “C1”, “C2”, “C3”, and “C4””; note: each CU as subset of set of rows that make up a table) compressed independently of other compressed table data portions (Das: at least ¶0041; “each column may be compressed at different compression levels. For example, CU a1 may be compressed at a compression level CL1, while CU b1 is compressed at a compression level CL2”).
Claim 11 (a method claim) corresponds in scope to Claim 2, and is similarly rejected.
As to Claim 3, Das, Chen and Abadi teach the apparatus of claim 2, wherein, to decompress the compressed table data, the processor executes the instructions to decompress the compressed table data corresponding to the column in accordance with a data type of the column (Das: at least ¶¶0104-0105; “If CU c1 does not have any data elements that can satisfy a predicate's condition, then the IMCU 114 may be filtered from further scanning. In this case, CU c1 has two data items that meet the condition: R2C3 and R6C3” and “the data items from CU a1, b1, and d1 that are in the same rows as the data items that meet the condition for c1 are decompressed”; note: data satisfying condition(s) as one type, data not satisfying condition(s) as another type).
Claim 12 (a method claim) corresponds in scope to Claim 3, and is similarly rejected.
As to Claim 9, Das, Chen and Abadi teach the apparatus of claim 1, wherein: the apparatus is a first instance of a distributed database; and to execute the database query the processor executes the instructions to: access the portion of the uncompressed table data from the portion of the memory to generate first intermediate results data responsive to the database query (Das: at least ¶0105; “data items from CU a1, b1, and d1 that are in the same rows as the data items that meet the condition for c1 are decompressed, and these data items are stitched with their corresponding data items in the IMCU. Once the rows are stitched, the entire complex predicate may be evaluated against the filtered rows. FIG. 3C illustrates evaluating complex predicates against decompressed rows that are stitched together”; ¶0114 further discloses “distributed database cluster” and “three nodes 102, 122 and 142”; ¶¶0144-0145 also disclose “filter predicates are evaluated against individual CUs” and “the filtered data items are then stitched together into rows”); receive second intermediate results data responsive to the database query from a second instance of the distributed database (Das: at least ¶0105; “data items from CU a1, b1, and d1 that are in the same rows as the data items that meet the condition for c1 are decompressed, and these data items are stitched with their corresponding data items in the IMCU. Once the rows are stitched, the entire complex predicate may be evaluated against the filtered rows. FIG. 3C illustrates evaluating complex predicates against decompressed rows that are stitched together”; ¶0114 further discloses “distributed database cluster” and “three nodes 102, 122 and 142”; ¶¶0144-0145 also disclose “filter predicates are evaluated against individual CUs” and “the filtered data items are then stitched together into rows”); and generate the results data by combining the first intermediate results data and the second intermediate results data (Das: at least ¶0054; “IMCUs are decompressed, scanned CU by CU, and then the data items are stitched together to form rows“; ¶0105 further discloses “FIG. 3C illustrates evaluating complex predicates against decompressed rows that are stitched together”).
Claims 4 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over US PGPUB 2016/0350347 by Das et al. (“Das”) in view of US PGPUB 2013/0031139 by Chen et al. (“Chen”), and further in view of NPL “Integrating Compression and Execution in Column-Oriented Database Systems” by Abadi et al. (“Abadi”), and further in view of US PGPUB 2016/0006454 by Kataoka et al. (“Kataoka”).
As to Claim 4, Das, Chen and Abadi teach the apparatus of claim 3.
Das, Chen and Abadi do not explicitly disclose, but Kataoka wherein, to decompress the compressed table data, the processor executes the instructions to decompress the compressed table data using at least one of dictionary coding or variable-length coding (Kataoka: at least ¶0057; “when compressed data that has been compressed through the above-described compression processing is to be decompressed, the number of target compressed codes is small, so that the decompression speed is expected to be improved”; ¶0098; “when the decompression function is called, the controlling unit 121 executes preprocessing of the decompression processing … and further secures a storage area for the decompression dictionary D3”; ¶0103 further discloses “the decompression dictionary D3 is used to read the fixed length data from the compressed data on which variable length coding is performed” and “decompression dictionary D3 is a decompression dictionary used for such decompression processing”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Kataoka’s feature of wherein, to decompress the compressed table data, the processor executes the instructions to decompress the compressed table data using at least one of dictionary coding or variable-length coding (Kataoka: at least ¶¶0057, 0103) with the apparatus disclosed by Das, Chen and Abadi.
The suggestion/motivation for doing so would have been to speed up decompression processing (Kataoka: at least ¶0057; “when compressed data that has been compressed through the above-described compression processing is to be decompressed, the number of target compressed codes is small, so that the decompression speed is expected to be improved”).
Claim 13 (a method claim) corresponds in scope to Claim 4, and is similarly rejected.
Claims 5-7 and 14-16 are rejected under 35 U.S.C. 103 as being unpatentable over US PGPUB 2016/0350347 by Das et al. (“Das”) in view of US PGPUB 2013/0031139 by Chen et al. (“Chen”), and further in view of NPL “Integrating Compression and Execution in Column-Oriented Database Systems” by Abadi et al. (“Abadi”), and further in view of US PGPUB 2016/0006454 by Kataoka et al. (“Kataoka”), and further in view of US PGPUB 2017/0024421 by Kim et al. (“Kim”).
As to Claim 5, Das, Chen, Abadi and Kataoka teach the apparatus of claim 4.
Das, Chen, Abadi and Kataoka do not explicitly disclose, but Kim discloses wherein, to decompress the compressed table data, the processor executes the instructions to: determine whether the data type is a measure data type or a string data type (Kim: at least ¶0006; “method performed by one or more processors of a web server, comprises the steps of identifying columns of a source table having entries of data type “real” as measure column candidates”; ¶0040 further discloses “… the data type of the data in each column in the source table is examined and columns having data type real number are identified as candidates for being measures in a fact table”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Kim’s feature of wherein, to decompress the compressed table data, the processor executes the instructions to: determine whether the data type is a measure data type or a string data type (Kim: at least ¶¶0006, 0040) with the apparatus disclosed by Das, Chen, Abadi and Kataoka.
The suggestion/motivation for doing so would have been to execute an “algorithm for modeling a denormalized table into a star schema” (Kim: at least ¶0038) that “(1) provide a direct and intuitive mapping between the business entities being analyzed by end users and the schema design; and (2) provide highly optimized performance for typical data warehouse queries” (Kim: at least ¶0036).
Claim 14 (a method claim) corresponds in scope to Claim 5, and is similarly rejected.
As to Claim 6, Das, Chen, Abadi, Kataoka and Kim teach the apparatus of claim 5, wherein, to decompress the compressed table data, the processor executes the instructions to: in response to a determination that the data type is the measure data type (Das: at least ¶0120; “each group of CUs from these IMCUs respectively contains items of table 400 from columns … “retailValue””), decompress the compressed table data of the column (Das: at least ¶0103 ; “the CU may need to be decompressed in order to evaluate the condition of the predicate against the data items in the CU”).
Das, Chen and Abadi do not explicitly disclose, but Kataoka discloses said decompress the compressed table data of the column using variable-length coding (Kataoka: at least ¶0098; “when the decompression function is called, the controlling unit 121 executes preprocessing of the decompression processing … and further secures a storage area for the decompression dictionary D3”; ¶0103 further discloses “the decompression dictionary D3 is used to read the fixed length data from the compressed data on which variable length coding is performed” and “decompression dictionary D3 is a decompression dictionary used for such decompression processing”) in order to speed up decompression processing (Kataoka: at least ¶0057; “when compressed data that has been compressed through the above-described compression processing is to be decompressed, the number of target compressed codes is small, so that the decompression speed is expected to be improved”).
Claim 15 (a method claim) corresponds in scope to Claim 6, and is similarly rejected.
As to Claim 7, Das, Chen, Abadi, Kataoka and Kim teach the apparatus of claim 5, wherein, to decompress the compressed table data, the processor executes the instructions to: in response to a determination that the data type is the string data type (Das: at least ¶0120; “each group of CUs from these IMCUs respectively contains items of table 400 from columns “productID”, “orderID””), decompress the compressed table data of the column (Das: at least ¶0103; “the CU may need to be decompressed in order to evaluate the condition of the predicate against the data items in the CU”).
Das, Chen and Abadi do not explicitly disclose, but Kataoka discloses said decompress the compressed table data of the column using dictionary coding (Kataoka: at least ¶0103; “decompression dictionary D3 is a decompression dictionary used for such decompression processing”) in order to speed up decompression processing (Kataoka: at least ¶0057; “when compressed data that has been compressed through the above-described compression processing is to be decompressed, the number of target compressed codes is small, so that the decompression speed is expected to be improved”).
Claim 16 (a method claim) corresponds in scope to Claim 7, and is similarly rejected.
Conclusion
Any inquiry concerning this communication or earlier communications from the Examiner should be directed to Huen Wong whose telephone number is (571) 270-3426. The examiner can normally be reached on Monday - Friday (10:30AM EST - 6:30PM EST). If attempts to reach the examiner by telephone are unsuccessful, the Examiner's supervisor, Charles Rones can be reached on (571) 272-4085. The fax phone number for the organization where this application or proceeding is assigned is (571) 273-8300 for regular communications and after final communications.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/H.W/Examiner, Art Unit 2168 15 February 2026
/CHARLES RONES/Supervisory Patent Examiner, Art Unit 2168