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-12 are presented for examination (filed on 05 August 2025).
Priority
Acknowledgment is made of applicant's claim for foreign priority under 35 U.S.C. 119(a)-(d). Priority date of 7 March 2023 is given.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 25 August 2025 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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 filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual 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/apply/applying-online/eterminal-disclaimer.
Claims 1-12 rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-11 of U.S. Patent No. 12430334. Although the claims at issue are not identical, they are not patentably distinct from each other because:
Instant application:
Patent No.: 12430334
1. A database management apparatus, comprising:
a query reception unit configured to receive a query of a database stored in a storage apparatus;
a query execution unit configured to execute query processing as processing in response to the query; and a filter creation unit configured to create a filter as data representing a scanning range of an inner table, wherein the storage apparatus stores a range representing a range of values stored in a table or an index for each stored unit or file, the query processing is processing in which join processing including a join of multiple stages is performed, when a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing, the filter creation unit performs filter creation processing during the scan of the inner table in the join process at the current stage by query execution unit, the query execution unit scans only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, and the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage.
2. The database management apparatus according to claim 1, wherein:
when there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage, the filter creation processing additionally determines to implement scanning of an inner table related to a join of a next stage.
3. The database management apparatus according to claim 1, wherein:
a table in the database is configured from a plurality of segments;
each of the plurality of segments is a unit that is larger than a record, is configured from two or more records within the table, and includes a plurality of columns of the table;
the range of values stored in a table or an index exists for each segment;
each range of values stored in a table or an index is data representing a range of values stored in a column of a segment corresponding to the range of values stored in a table or an index; and
the filter creation processing additionally includes:
identifying a segment having a range that at least partially overlaps with a range of a segment including a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage; and
adding data representing the identified segment to the filter.
4. The database management apparatus according to claim 3, wherein:
the filter creation unit performs the filter creation processing when a segment includes a first hit record.
5. The database management apparatus according to claim 3, further comprising:
a creation determination unit configured to, when the query processing includes the join processing including the join of the multiple stages, perform creation determination where the query processing determines whether an overlap of ranges between segments in each column is small, or whether an application using the values stored in the database is a prescribed application,
wherein:
the filter creation unit performs the filter creation processing when a result of the creation determination is true.
6. The database management apparatus according to claim 3, wherein:
a table in the database is configured from a plurality of chunks;
each chunk is configured from two or more segments; and
the filter creation unit selects a scan unit to be a segment, a chunk or an overall inner table according to a number of the identified segments, and updates the filter or does not create the filter according to the selected scan unit.
7. The database management apparatus according to claim 6, wherein: the scan unit is a segment when a number of the identified segments satisfies a condition that a number of segments is small; the scan unit is a chunk when a number of the identified segments satisfies a condition that a number of segments is medium; and the scan unit is an overall inner table when a number of the identified segments satisfies a condition that a number of segments is large.
8. The database management apparatus according to claim 3, wherein: the join processing is recursive join processing; and the filter creation processing includes:
identifying a range of a segment including a hit record in an inner table related to a join of a current stage from a range of values stored in a table or an index corresponding to a join column of a next stage;
identifying a segment having a range that at least partially overlaps with the identified range from a range of values stored in a table or an index corresponding to a join column of a current stage; and
adding data representing the identified segment to the filter.
9. The database management apparatus according to claim 3, wherein:
the join processing is multistage join processing; and
the filter creation processing includes:
identifying a range of a segment including a hit record in an inner table related to a join of a current stage from a range of values stored in a table or an index corresponding to a join column of a current stage;
identifying a segment having a range that at least partially overlaps with the identified range from a range of values stored in a table or an index corresponding to a join column of a next stage; and
adding data representing the identified segment to the filter.
10. The database management apparatus according to claim 1, further comprising:
a creation determination unit which, when the query processing includes the join processing including the join of the multiple stages, performs creation determination of determining whether an application using the values stored in the database is a prescribed application,
wherein:
the filter creation unit performs the filter creation processing when a result of the creation determination is true.
11. A database management method, comprising:
when query processing as processing in response to a query of a database stored in a storage apparatus is processing in which join processing including a join of multiple stages and a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing,
a computer performs filter creation processing; and
a computer scans only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, wherein
the storage apparatus stores a range representing a range of values stored in a table or an index for each stored unit or file, the filter is data representing a scanning range of an inner table, and
the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage.
12. A non-transitory computer-readable medium storing a computer program for causing a computer,
when query processing as processing in response to a query of a database stored in a storage apparatus is processing in which join processing including a join of multiple stages and a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing,
performing filter creation processing; and
scanning only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, wherein
the storage apparatus stores a range as data representing a range of values stored in a table or an index for each stored unit or file,
the filter is data representing a scanning range of an inner table, and
the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage.
1. A database management apparatus, comprising:
a processor which when executing a program configures the processor to: receive a query of a database stored in a storage apparatus;
execute query processing as processing in response to the query; and
create a filter as data representing a scanning range of an inner table, wherein the storage apparatus stores a column range index as data representing a range of values stored in a table in the database, the query processing is processing in which join processing including a join of multiple stages is performed, when a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing, the processor performs filter creation processing, the processor scans only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage, the table in the database is configured from a plurality of segments, each of the plurality of segments is a unit that is larger than a record, is configured from two or more records within the table, and includes a plurality of columns of the table, the column range index exists for each segment, each column range index is data representing a range of values stored in a column of a segment corresponding to the column range index, and the filter creation processing additionally includes: identifying a segment having a range that at least partially overlaps with a range of a segment including a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage; and adding data representing the identified segment to the filter.
2. The database management apparatus according to claim 1, wherein:
when there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage, the filter creation processing additionally determines to implement scanning of an inner table related to a join of a next stage.
3. The database management apparatus according to claim 1, wherein: the processor is further configured to perform the filter creation processing when a segment includes a first hit record.
4. The database management apparatus according to claim 1, wherein the processor is further configured to:
when the query processing includes the join processing including the join of the multiple stages, perform creation determination where the query processing determines whether an overlap of ranges between segments in each column is small, or whether an application using the values stored in the database is a prescribed application; and
perform the filter creation processing when a result of the creation determination is true.
5. The database management apparatus according to claim 1, wherein:
the table in the database is configured from a plurality of chunks;
each chunk is configured from two or more of the plurality of segments; and
the processor is further configured to select a scan unit to be a segment, a chunk or an overall inner table according to a number of the identified segments, and update the filter or does not create the filter according to the selected scan unit.
6. The database management apparatus according to claim 5, wherein: the scan unit is a segment when a number of the identified segments satisfies a condition that a number of segments is small; the scan unit is a chunk when a number of the identified segments satisfies a condition that a number of segments is medium; and the scan unit is an overall inner table when a number of the identified segments satisfies a condition that a number of segments is large.
7. The database management apparatus according to claim 1, wherein: the join processing is recursive join processing; and the filter creation processing includes:
identifying a range of a segment including a hit record in an inner table related to a join of a current stage from a column range index corresponding to a join column of a next stage;
identifying a segment having a range that at least partially overlaps with the identified range from a column range index corresponding to a join column of a current stage; and adding data representing the identified segment to the filter.
8. The database management apparatus according to claim 1, wherein: the join processing is multistage join processing; and the filter creation processing includes:
identifying a range of a segment including a hit record in an inner table related to a join of a current stage from a column range index corresponding to a join column of a current stage;
identifying a segment having a range that at least partially overlaps with the identified range from a column range index corresponding to a join column of a next stage; and adding data representing the identified segment to the filter.
9. The database management apparatus according to claim 1, wherein the processor is further configured to: when the query processing includes the join processing including the join of the multiple stages, perform creation determination of determining whether an application using the values stored in the database is a prescribed application; and perform the filter creation processing when a result of the creation determination is true.
10. A database management method, comprising the steps of: when query processing as processing in response to a query of a database stored in a storage apparatus is processing in which join processing including a join of multiple stages and a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing, performing filter creation processing; and scanning only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, wherein the storage apparatus stores a column range index as data representing a range of values stored in a table in the database, the filter is data representing a scanning range of an inner table, the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage, the table in the database is configured from a plurality of segments, each of the plurality of segments is a unit that is larger than a record, is configured from two or more records within the table, and includes a plurality of columns of the table, the column range index exists for each segment, each column range index is data representing a range of values stored in a column of a segment corresponding to the column range index, and the filter creation processing additionally includes: identifying a segment having a range that at least partially overlaps with a range of a segment including a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage; and adding data representing the identified segment to the filter.
11. A non-transitory computer-readable medium storing a computer program for causing a computer to: when query processing as processing in response to a query of a database stored in a storage apparatus is processing in which join processing including a join of multiple stages and a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing, perform filter creation processing; and scan only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, wherein the storage apparatus stores a column range index as data representing a range of values stored in a table in the database, the filter is data representing a scanning range of an inner table, the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage, the table in the database is configured from a plurality of segments, each of the plurality of segments is a unit that is larger than a record, is configured from two or more records within the table, and includes a plurality of columns of the table, the column range index exists for each segment, each column range index is data representing a range of values stored in a column of a segment corresponding to the column range index, and the filter creation processing additionally includes: identifying a segment having a range that at least partially overlaps with a range of a segment including a hit record in an inner table related to a join of a current stage based on a column range index corresponding to a join column of a current stage and a column range index corresponding to a join column of a next stage; and adding data representing the identified segment to the filter.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
For claim 1, claim limitations, “1. A database management apparatus, comprising:
a query reception unit configured to receive a query of a database stored in a storage apparatus;
a query execution unit configured to execute query processing as processing in response to the query; and
a filter creation unit configured to create a filter as data representing a scanning range of an inner table…” have been evaluated under the three-prong test set forth in MPEP § 2181, subsection I, but the result is inconclusive. Thus, it is unclear whether this limitation should be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the disclosure is devoid of any structure that performs the function in the claim. The boundaries of this claim limitation are ambiguous; therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph. In response to this rejection, applicant must clarify whether this limitation should be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. Mere assertion regarding applicant’s intent to invoke or not invoke 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph is insufficient. Applicant may:
(a) Amend the claim to clearly invoke 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, by reciting “means” or a generic placeholder for means, or by reciting “step.” The “means,” generic placeholder, or “step” must be modified by functional language, and must not be modified by sufficient structure, material, or acts for performing the claimed function;
(b) Present a sufficient showing that 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, should apply because the claim limitation recites a function to be performed and does not recite sufficient structure, material, or acts to perform that function;
(c) Amend the claim to clearly avoid invoking 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, by deleting the function or by reciting sufficient structure, material or acts to perform the recited function; or
(d) Present a sufficient showing that 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, does not apply because the limitation does not recite a function or does recite a function along with sufficient structure, material or acts to perform that function.
Dependent claims 2-10 are rejected for fully incorporating the deficiencies of their respective base claims by dependency.
Claim Rejections - 35 USC § 103
The following is a quotation of pre-AIA 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made.
Claims 1, 2, 10, 11 and 12 are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Bear et al. (U.S. Pub. No.: US 20120317094, herein Bear), in view of Yoshida et al. (U.S. Pub. No.: U.S. 20160335321, hereinafter Yoshida), and further in view of Liu et al. (U.S. Patent No.: US 6185557, herein Liu).
For claim 1, Bear discloses a database management apparatus, comprising:
a query reception unit configured to receive a query of a database stored in a storage apparatus (Bear: paragraph [0003], “…actions of identifying a join clause in a query, the join clause specifying an outer table of tuples, to be joined with an inner table, the outer table having one or more attributes, each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored; and including, in a plan for the query, a filter that, when executed, causes selection of a proper subset of tuples of the outer table to serve as input to the join clause in place of the outer table, in which selection of the tuples comprises reading a plurality of portions of an attribute file for one of the attributes without reading other portions of the attribute file and identifying attribute values in the read portions that satisfy one or more predicates applied to the inner table. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.”
paragraph [0039], “…a query 440 and the direction of data flow during a query processing. An end-user or an executing software program submits the query 440 to the system 400. The query 440 is parsed by a SQL parser and provided to a query optimizer 414 which chooses the best projection(s) 424 for the query by referencing the catalog 408 of projections.”);
a query execution unit configured to execute query processing as processing in response to the query (Bear: paragraph [0003], “…actions of identifying a join clause in a query, the join clause specifying an outer table of tuples, to be joined with an inner table, the outer table having one or more attributes, each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored; and including, in a plan for the query, a filter that, when executed, causes selection of a proper subset of tuples of the outer table to serve as input to the join clause in place of the outer table, in which selection of the tuples comprises reading a plurality of portions of an attribute file for one of the attributes without reading other portions of the attribute file and identifying attribute values in the read portions that satisfy one or more predicates applied to the inner table. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.” paragraph [0039]); and
a filter creation unit configured to create a filter as data representing a scanning range of an inner table (Bear: paragraph [0003], “…actions of identifying a join clause in a query, the join clause specifying an outer table of tuples, to be joined with an inner table, the outer table having one or more attributes, each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored; and including, in a plan for the query, a filter that, when executed, causes selection of a proper subset of tuples of the outer table to serve as input to the join clause in place of the outer table, in which selection of the tuples comprises reading a plurality of portions of an attribute file for one of the attributes without reading other portions of the attribute file and identifying attribute values in the read portions that satisfy one or more predicates applied to the inner table. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.” paragraph [0039], where “create a filter” is broadly interpreted as “in a plan for the query, a filter that, when executed”), wherein
the storage apparatus stores a range representing a range of values stored in a table or an index for each stored unit or file (Bear: paragraph [0003], “…actions of identifying a join clause in a query, the join clause specifying an outer table of tuples, to be joined with an inner table, the outer table having one or more attributes, each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored; and including, in a plan for the query, a filter that, when executed, causes selection of a proper subset of tuples of the outer table to serve as input to the join clause in place of the outer table, in which selection of the tuples comprises reading a plurality of portions of an attribute file for one of the attributes without reading other portions of the attribute file and identifying attribute values in the read portions that satisfy one or more predicates applied to the inner table. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.”
paragraph [0030], “…Filters used to implement SIP can take advantage of this storage format by using the index range values to avoid reading blocks of the outer table that do not contain attribute values that are needed to evaluate the filter. For example, if the SIP filter needed to check for the existence of particular attribute values in an attribute file, the SIP filter could make use of the index range and the sort order of values in the attribute file in order to avoid reading portions of the attribute file that would not contain the given attribute values. By way of illustration, a binary search can be used on a sorted column to avoid fetching unnecessary blocks. This can work with a sideways information passing data structure that contains a list of all the join keys from the inner table (e.g., rather than the structure 106 of FIG. 1 which is a hash table). With such a list a binary search algorithm can be used on a sorted column--e.g., fetch the first, middle and last values of the column fk. Suppose the first value is 0, the middle value is 500, and last value is 1000. Then, since "fact.fk IN (5)" can never be true between the mid to last range (since "fk" values there are between 500 and 1000), the entire range can be skipped. No more blocks are fetched from that range. This process can be repeated recursively for the range first-mid (i.e., 0-500 of the fk column).”)
However, Bear does not explicitly disclose the query processing is processing in which join processing including a join of multiple stages is performed,
when a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing,
the filter creation unit performs filter creation processing during the scan of the inner table in the join process at the current stage by query execution unit,
the query execution unit scans only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage, and
the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage.
Yoshida discloses the query processing is processing in which join processing including a join of multiple stages is performed (Yoshida: paragraph [0032], “The DBMS 104 manages the DB 122. The DB 122 includes one or more tables 124 and may further include one or more indices 123. The table 124 is a set of one or more records, and a record includes one or more columns. The index 123 is a data structure that is created for one or more columns or the like of the table 124 as a target and is used to accelerate the access to the table 124 based on a selection condition including a target column or the like of the index 123…”
paragraph [0043], “[0043] The query execution plan generation part 107 generates a query execution plan illustrated in FIG. 4A from the first query illustrated in FIG. 2. According to the example of FIG. 4A, two join operations are illustrated. The join operations are nested loop join. Specifically, first nested loop join which uses the extraction result from a Part table as an outer table (join source) and uses the extraction result from a Lineitem table as an inner table (join destination) and second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated.”
WHERE “a join of multiple stages” is broadly interpreted as “second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated”),
when a join result of a current stage is an outer table related to a join of a next stage in a join of each stage of the join processing (Yoshida: paragraph [0043], “[0043] The query execution plan generation part 107 generates a query execution plan illustrated in FIG. 4A from the first query illustrated in FIG. 2. According to the example of FIG. 4A, two join operations are illustrated. The join operations are nested loop join. Specifically, first nested loop join which uses the extraction result from a Part table as an outer table (join source) and uses the extraction result from a Lineitem table as an inner table (join destination) and second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated.”
WHERE “a current stage” is broadly interpreted as “first nested loop join,”
WHERE “a next stage” is broadly interpreted as “second nested loop join,”),
the filter creation unit performs filter creation processing during the scan of the inner table in the join process at the current stage by query execution unit (Yoshida: paragraph [0032], “The DBMS 104 manages the DB 122. The DB 122 includes one or more tables 124 and may further include one or more indices 123. The table 124 is a set of one or more records, and a record includes one or more columns. The index 123 is a data structure that is created for one or more columns or the like of the table 124 as a target and is used to accelerate the access to the table 124 based on a selection condition including a target column or the like of the index 123…”
paragraph [0043], “[0043] The query execution plan generation part 107 generates a query execution plan illustrated in FIG. 4A from the first query illustrated in FIG. 2. According to the example of FIG. 4A, two join operations are illustrated. The join operations are nested loop join. Specifically, first nested loop join which uses the extraction result from a Part table as an outer table (join source) and uses the extraction result from a Lineitem table as an inner table (join destination) and second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated.”
paragraph [0044], “First, the query execution part 108 acquires a storage position of a part table record of which p_type is identical to “ECONOMY ANODIZED STEEL” using a p_type index according to the query execution plan of FIG. 4A and reads the part table record stored in the acquired storage position from the part table. Subsequently, the query execution part 108 acquires a storage position of a lineitem table record of which l_partkey is identical to p_partkey of the read part table record using an l_partkey index and reads the lineitem table record stored in the acquired storage position from the lineitem table. Subsequently, the query execution part 108 acquires a storage position of an orders table record of which o_orderkey is identical to l_orderkey of the read lineitem table record using an o_orderkey index and reads the orders table record stored in the acquired storage position from the orders table. Finally, the query execution part 108 joins all read records to sum up a total_profit for each p_name and sorts the generated summation result based on the value of the total_profit…”
paragraph [0047], “…The execution plan information is information indicating the configuration of a query execution plan, and includes, for each DB operation, “Operation” (for example, the name of a DB operation), “Source 1” (an outer table or information indicating a previous-stage DB operation), “Source 2” (an inner table or information indicating another previous-stage DB operation), and “Condition” (information indicating conditions), for example…,” Figs. 2, 3, 4B,
WHERE “filter” is broadly interpreted as “acquires a storage position of a part table record of which p_type is identical to “ECONOMY ANODIZED STEEL” using a p_type index” or “Condition” See Fig. 4B, column “Condition” in “Execution Plan”),
the query execution unit scans only a range represented with the filter created in the filter creation processing within an inner table related to the join of the next stage (Yoshida: paragraph [0032], “The DBMS 104 manages the DB 122. The DB 122 includes one or more tables 124 and may further include one or more indices 123. The table 124 is a set of one or more records, and a record includes one or more columns. The index 123 is a data structure that is created for one or more columns or the like of the table 124 as a target and is used to accelerate the access to the table 124 based on a selection condition including a target column or the like of the index 123…”
paragraph [0043], “[0043] The query execution plan generation part 107 generates a query execution plan illustrated in FIG. 4A from the first query illustrated in FIG. 2. According to the example of FIG. 4A, two join operations are illustrated. The join operations are nested loop join. Specifically, first nested loop join which uses the extraction result from a Part table as an outer table (join source) and uses the extraction result from a Lineitem table as an inner table (join destination) and second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated.”
paragraph [0044], “First, the query execution part 108 acquires a storage position of a part table record of which p_type is identical to “ECONOMY ANODIZED STEEL” using a p_type index according to the query execution plan of FIG. 4A and reads the part table record stored in the acquired storage position from the part table. Subsequently, the query execution part 108 acquires a storage position of a lineitem table record of which l_partkey is identical to p_partkey of the read part table record using an l_partkey index and reads the lineitem table record stored in the acquired storage position from the lineitem table. Subsequently, the query execution part 108 acquires a storage position of an orders table record of which o_orderkey is identical to l_orderkey of the read lineitem table record using an o_orderkey index and reads the orders table record stored in the acquired storage position from the orders table. Finally, the query execution part 108 joins all read records to sum up a total_profit for each p_name and sorts the generated summation result based on the value of the total_profit…”
paragraph [0047], “…The execution plan information is information indicating the configuration of a query execution plan, and includes, for each DB operation, “Operation” (for example, the name of a DB operation), “Source 1” (an outer table or information indicating a previous-stage DB operation), “Source 2” (an inner table or information indicating another previous-stage DB operation), and “Condition” (information indicating conditions), for example…,”
paragraph [0050], “The query execution information may include an estimated join rate of each join operation, the number of contexts managed for each specific node of the query execution plan, and memory reservation information. The memory reservation information includes at least the execution state information among the items of information illustrated in FIG. 4B, for example. The estimated join rate of each join operation (nested loop join) and the number of contexts managed for each specific node of the query execution plan are acquired through the query execution plan generation part 107, for example.” Figs. 2, 3, 4B
WHERE “scans only a range represented with the filter” is broadly interpreted as “index 123 is a data structure that is created for one or more columns or the like of the table 124 as a target and is used to accelerate the access to the table 124 based on a selection condition including a target column”), and
the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage (Yoshida: paragraph [0044], “First, the query execution part 108 acquires a storage position of a part table record of which p_type is identical to “ECONOMY ANODIZED STEEL” using a p_type index according to the query execution plan of FIG. 4A and reads the part table record stored in the acquired storage position from the part table. Subsequently, the query execution part 108 acquires a storage position of a lineitem table record of which l_partkey is identical to p_partkey of the read part table record using an l_partkey index and reads the lineitem table record stored in the acquired storage position from the lineitem table. Subsequently, the query execution part 108 acquires a storage position of an orders table record of which o_orderkey is identical to l_orderkey of the read lineitem table record using an o_orderkey index and reads the orders table record stored in the acquired storage position from the orders table. Finally, the query execution part 108 joins all read records to sum up a total_profit for each p_name and sorts the generated summation result based on the value of the total_profit…”
paragraph [0050], “The query execution information may include an estimated join rate of each join operation, the number of contexts managed for each specific node of the query execution plan, and memory reservation information. The memory reservation information includes at least the execution state information among the items of information illustrated in FIG. 4B, for example. The estimated join rate of each join operation (nested loop join) and the number of contexts managed for each specific node of the query execution plan are acquired through the query execution plan generation part 107, for example.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to improve upon “Sideways Information Passing” as taught by Bear by implementing “DATABASE MANAGEMENT SYSTEM, COMPUTER, AND DATABASE MANAGEMENT METHOD” as taught by Yoshida, because it would provide Bear’s apparatus with the enhanced capability of “…The query execution plan generation part 107 calculates an estimated join rate for each join operation during generation of the query execution plan and associates the calculated estimated join rate with a corresponding join operation...” (Yoshida: paragraph [0045]).
However, Bear and Yoshida do not explicitly disclose based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage.
Liu discloses the filter creation processing identifies whether there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage based on a range of values stored in a table or an index corresponding to a join column of a current stage and a range of values stored in a table or an index corresponding to a join column of a next stage (Liu: Abstract, “A merge join process combines rows from an inner and an outer table when the inner table is indexed on a data column that is common to both tables. The merge join process creates a set of rows from the outer table that satisfy a selection criteria and sorts the rows in the set on the common data column if necessary. The merge join process searches for a matching inner row for each outer row in sequence using the inner table indices until it finds a matching inner row on a data page. The data page is then repeatedly searched for matches on the successive outer rows in the set until the end of the data page is reached. The end of the data page is reached when the value of the common data column in an outer row is greater than a last key that represents the highest value of the common data column in a inner row stored on the data page. The merge join process also determines that a matching inner row does not exist in the inner table when the value of the common data column in an outer row is less than a next key that represents the lowest value of the common data column that has not yet been searched for a match. Thus, the next and last keys reduce the number of scans of the data page. All matching inner rows on the data page are marked as join rows; all outer rows with common data column values between the next and last keys but which did not have matching inner rows are discarded. When the end of the data page is reached, another data page is located and the search is repeated. The subsequent data page is located using the inner table indices or by traversing links between data pages…”
column 9, lines 30-40, “Procedure merge_join 300 calls procedure sort_outer_hit_records 301 to create a set of outer rows which satisfy a selection criteria and to sort the set on the join column. Procedure sort_outer_hit_records 301 calls procedure sort_fetch 303 to return the first outer row in the set.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to improve upon “Sideways Information Passing” as taught by Bear by implementing “Merge Join Process” as taught by Liu, because it would provide Bear’s modified apparatus with the enhanced capability of “…The combination of the next key and last key allows the merge join process of the present invention to determine that entire ranges of outer rows do not have matching inner rows, thus reducing or eliminating searches of the inner index records and/or the data pages…” (Liu: column 4, lines 25-30).
For claim 2, Bear, Yoshida and Liu disclose the database management apparatus according to claim 1, wherein:
when there is a possibility that an inner table related to a join of a next stage includes a hit record in an inner table related to a join of a current stage, the filter creation processing additionally determines to implement scanning of an inner table related to a join of a next stage (Liu: Abstract, “A merge join process combines rows from an inner and an outer table when the inner table is indexed on a data column that is common to both tables. The merge join process creates a set of rows from the outer table that satisfy a selection criteria and sorts the rows in the set on the common data column if necessary. The merge join process searches for a matching inner row for each outer row in sequence using the inner table indices until it finds a matching inner row on a data page. The data page is then repeatedly searched for matches on the successive outer rows in the set until the end of the data page is reached. The end of the data page is reached when the value of the common data column in an outer row is greater than a last key that represents the highest value of the common data column in a inner row stored on the data page. The merge join process also determines that a matching inner row does not exist in the inner table when the value of the common data column in an outer row is less than a next key that represents the lowest value of the common data column that has not yet been searched for a match. Thus, the next and last keys reduce the number of scans of the data page. All matching inner rows on the data page are marked as join rows; all outer rows with common data column values between the next and last keys but which did not have matching inner rows are discarded. When the end of the data page is reached, another data page is located and the search is repeated. The subsequent data page is located using the inner table indices or by traversing links between data pages…”
column 9, lines 30-40, “Procedure merge_join 300 calls procedure sort_outer_hit_records 301 to create a set of outer rows which satisfy a selection criteria and to sort the set on the join column. Procedure sort_outer_hit_records 301 calls procedure sort_fetch 303 to return the first outer row in the set.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to improve upon “Sideways Information Passing” as taught by Bear by implementing “Merge Join Process” as taught by Liu, because it would provide Bear’s modified apparatus with the enhanced capability of “…The combination of the next key and last key allows the merge join process of the present invention to determine that entire ranges of outer rows do not have matching inner rows, thus reducing or eliminating searches of the inner index records and/or the data pages…” (Liu: column 4, lines 25-30).
For claim 10, Bear, Yoshida and Liu disclose the database management apparatus according to claim 1, further comprising:
a creation determination unit which, when the query processing includes the join processing including the join of the multiple stages, performs creation determination of determining whether an application using the values stored in the database is a prescribed application, wherein: the filter creation unit performs the filter creation processing when a result of the creation determination is true (Bear: paragraph [0003], “…actions of identifying a join clause in a query, the join clause specifying an outer table of tuples, to be joined with an inner table, the outer table having one or more attributes, each of the attributes of the outer table having values stored in an attribute file that is distinct from attribute files in which the values of other attributes are stored; and including, in a plan for the query, a filter that, when executed, causes selection of a proper subset of tuples of the outer table to serve as input to the join clause in place of the outer table, in which selection of the tuples comprises reading a plurality of portions of an attribute file for one of the attributes without reading other portions of the attribute file and identifying attribute values in the read portions that satisfy one or more predicates applied to the inner table. Other embodiments of this aspect include corresponding systems, apparatus, and computer programs.”
paragraph [0039], “…a query 440 and the direction of data flow during a query processing. An end-user or an executing software program submits the query 440 to the system 400. The query 440 is parsed by a SQL parser and provided to a query optimizer 414 which chooses the best projection(s) 424 for the query by referencing the catalog 408 of projections.”).
Yoshida also discloses a creation determination unit which, when the query processing includes the join processing including the join of the multiple stages, performs creation determination of determining whether an application using the values stored in the database is a prescribed application, wherein: the filter creation unit performs the filter creation processing when a result of the creation determination is true (Yoshida: paragraph [0032], “The DBMS 104 manages the DB 122. The DB 122 includes one or more tables 124 and may further include one or more indices 123. The table 124 is a set of one or more records, and a record includes one or more columns. The index 123 is a data structure that is created for one or more columns or the like of the table 124 as a target and is used to accelerate the access to the table 124 based on a selection condition including a target column or the like of the index 123…”
paragraph [0043], “[0043] The query execution plan generation part 107 generates a query execution plan illustrated in FIG. 4A from the first query illustrated in FIG. 2. According to the example of FIG. 4A, two join operations are illustrated. The join operations are nested loop join. Specifically, first nested loop join which uses the extraction result from a Part table as an outer table (join source) and uses the extraction result from a Lineitem table as an inner table (join destination) and second nested loop join which uses the result of the first nested loop join as an outer table and the extraction result from an Orders table as an inner table are illustrated.”
paragraph [0044], “First, the query execution part 108 acquires a storage position of a part table record of which p_type is identical to “ECONOMY ANODIZED STEEL” using a p_type index according to the query execution plan of FIG. 4A and reads the part table record stored in the acquired storage position from the part table. Subsequently, the query execution part 108 acquires a storage position of a lineitem table record of which l_partkey is identical to p_partkey of the read part table record using an l_partkey index and reads the lineitem table record stored in the acquired storage position from the lineitem table. Subsequently, the query execution part 108 acquires a storage position of an orders table record of which o_orderkey is identical to l_orderkey of the read lineitem table record using an o_orderkey index and reads the orders table record stored in the acquired storage position from the orders table. Finally, the query execution part 108 joins all read records to sum up a total_profit for each p_name and sorts the generated summation result based on the value of the total_profit…”
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to improve upon “Sideways Information Passing” as taught by Bear by implementing “DATABASE MANAGEMENT SYSTEM, COMPUTER, AND DATABASE MANAGEMENT METHOD” as taught by Yoshida, because it would provide Bear’s apparatus with the enhanced capability of “…The query execution plan generation part 107 calculates an estimated join rate for each join operation during generation of the query execution plan and associates the calculated estimated join rate with a corresponding join operation...” (Yoshida: paragraph [0045]).
Liu also discloses a creation determination unit which, when the query processing includes the join processing including the join of the multiple stages, performs creation determination of determining whether an application using the values stored in the database is a prescribed application, wherein: the filter creation unit performs the filter creation processing when a result of the creation determination is true (Liu: Abstract, “A merge join process combines rows from an inner and an outer table when the inner table is indexed on a data column that is common to both tables. The merge join process creates a set of rows from the outer table that satisfy a selection criteria and sorts the rows in the set on the common data column if necessary. The merge join process searches for a matching inner row for each outer row in sequence using the inner table indices until it finds a matching inner row on a data page. The data page is then repeatedly searched for matches on the successive outer rows in the set until the end of the data page is reached. The end of the data page is reached when the value of the common data column in an outer row is greater than a last key that represents the highest value of the common data column in a inner row stored on the data page. The merge join process also determines that a matching inner row does not exist in the inner table when the value of the common data column in an outer row is less than a next key that represents the lowest value of the common data column that has not yet been searched for a match. Thus, the next and last keys reduce the number of scans of the data page. All matching inner rows on the data page are marked as join rows; all outer rows with common data column values between the next and last keys but which did not have matching inner rows are discarded. When the end of the data page is reached, another data page is located and the search is repeated. The subsequent data page is located using the inner table indices or by traversing links between data pages…”
column 9, lines 30-40, “Procedure merge_join 300 calls procedure sort_outer_hit_records 301 to create a set of outer rows which satisfy a selection criteria and to sort the set on the join column. Procedure sort_outer_hit_records 301 calls procedure sort_fetch 303 to return the first outer row in the set.”
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to improve upon “Sideways Information Passing” as taught by Bear by implementing “Merge Join Process” as taught by Liu, because it would provide Bear’s modified apparatus with the enhanced capability of “…The combination of the next key and last key allows the merge join process of the present invention to determine that entire ranges of outer rows do not have matching inner rows, thus reducing or eliminating searches of the inner index records and/or the data pages…” (Liu: column 4, lines 25-30).
For claim 11, it is a method claim having similar limitations as recited in claim 1. Thus, claim 11 is also rejected under the same rationale as cited in the rejection of rejected claim 1.
For claim 12, it is a computer product (non-transitory computer-readable medium) claim having similar limitations as recited in claim 1. Thus, claim 12 is also rejected under the same rationale as cited in the rejection of rejected claim 1.
Allowable Subject Matter
Claims 3-9 would be allowable if rewritten to overcome the rejection(s) under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), 2nd paragraph, set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to YU ZHAO whose telephone number is (571)270-3427. The examiner can normally be reached Monday-Friday 9AM-5PM.
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, Sherief Badawi can be reached at (571) 272-9782. 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.
/YU ZHAO/Primary Examiner, Art Unit 2169
Prosecution Insights