DETAILED ACTION
Claims 1-5 and 8-20 are pending.
Claims 6-7 are canceled, relevant limitations incorporated into the independent claims.
Independent claims 1, 17, and 19 are amended.
Claims 1-5 and 8-20 are rejected.
Notice of 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 .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 04/06/2026 has been entered.
Statutory Review under 35 USC § 101
Claims 1-16 are directed towards a method and have been reviewed.
Claims 1-16 appear to now be directed to patent-eligible subject matter as they comprise an abstract idea integrated into a practical application.
Claims 17-18 are directed toward a system and have been reviewed.
Claims 17-18 initially appear to be statutory as the system appears to contains hardware. Claims 17-18 also perform the method of claims 1-2 and are directed to patent-eligible subject matter as they comprise an abstract idea integrated into a practical application.
Claims 19-20 are directed toward an article of manufacture and have been reviewed.
Claims 19-20 initially appear to be statutory, as the article of manufacture can be interpreted to exclude non-statutory subject matter (i.e., transitory propagating signals).
Claims 19-20 also perform the method of claims 1-2 and are directed to patent-eligible subject matter as they comprise an abstract idea integrated into a practical application.
Response to Arguments
35 U.S.C. 101
Applicant’s arguments, see pp8-11, filed 04/06/2026, with respect to the 35 U.S.C. 101 rejection of claims 1-20 being directed to an abstract idea without significantly more have been fully considered and are persuasive. The 35 U.S.C. 101 rejection of claims 1-20 has been withdrawn.
35 U.S.C. 102/35 US.C. 103
Applicant’s arguments, see pp12-15, filed 04/06/2026, with respect to the rejection(s) of claim(s) 1, 17, and 19 under 35 U.S.C. 103 have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made under 35 U.S.C. 103.
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, 5, 12-16; 17; and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Alpers et al., U.S. Patent Application Publication No. 2017/0249360 (hereinafter Alpers) in view of Zhang et al., U.S. Patent Application Publication No. 2009/0299989 (hereinafter Zhang) in further view of Han et al., U.S. Patent Application Publication No. 2009/0292714 (hereinafter Han) in further view of Krauthgamer et al., U.S. Patent Application Publication No. 2009/0113309 (hereinafter Krauthgamer).
Regarding claim 1, Alpers teaches:
A computer-implemented method comprising: receiving, at a database system, a query for a database table, wherein the query includes a set of parameter values for a set of … predicates; (Alpers FIG. 1, ¶ 0019: In diagram 100, a relational database management system (RDBMS) is provided with a structure query language (SQL) statement 110. The SQL statement 110 includes a predicate 112 (referred to as a join predicate) with a table join 114 and a column of one of the tables constrained to a variable 116)
identifying a query plan for the query that includes a previously-determined predicate evaluation order for the set of … predicates and a predicate evaluation strategy for each predicate in the set of … predicates, (Alpers shows 'predicate evaluation order' in ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information) [shows previously-determined]; Alpers shows 'predicate evaluation strategy' through its access paths; see Alpers ¶ 0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path; Alpers ¶ 0006: If the estimated quantity of records is greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a first access path. If the estimated quantity of records is not greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a second access path. The first access path and the second access path produce functionally equivalent results while having disparate computational speeds to produce the equivalent results; see also Alpers ¶ 0022-0023: the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) [shows the claimed evaluation strategy involving predicates])
…
determining runtime estimated selectivities by determining a … runtime estimated selectivity for … the set of … predicates based on respective parameter values in the set of parameter values; (Alpers introduces estimated selectivities of predicates as claimed in FIG. 3, ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0032-0033: the query optimizer 312 estimates selectivity across a predicate to pick a better plan than possible if this estimate were not performed … The first time a join occurs on a particular column across two tables, a onetime small overhead estimate for optimization purposes can be performed. The skew estimator 322 performs this estimate, and saves results in the data store 318 for future use by the query optimizer 312. In one embodiment, as records within the respective database repository 330 change over time, skew can change and the estimate for a join predicate can be re-executed [shows being based on 'respective parameter values' as claimed])
determining matching value counts by determining a … matching value count for … the set of … predicates, wherein each matching value count indicates a count of distinct values that match a respective predicate; (Alpers FIG. 1, ¶ 0021-0023, see first ¶ 0021: Diagram 100 estimates the join predicate record return by conducting a query localized to T2 (or to one of the tables of the join predicate) ... A count query 132 is conducted local to table two (T2) where the T2.Col1 is set to the high skew value 127, and where any other local variables (T2.C3) are set to the proper values consistent with the SQL query 110; see also Alpers ¶ 0022: After the SQL count query 132 is executed to estimate the join predicate 120 record quantity, the estimated number of records can be compared against a predefined quantity (e.g., a threshold), as shown by decision block 140. As shown, the count results (from query 132) are compared against a threshold value of fifty)
…modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities or the matching value counts, to generate a modified query plan, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022 showing the claimed 'matching value counts': the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner ... If the count result does not exceed the threshold (in decision block 140), the query optimizer 120 can optimize the RDBMS query 110 using a different access path, as shown by block 144; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) [also shows 'matching value counts'] is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path [shows 'modifying' of a query plan] ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate) [shows being 'with respect to at least one predicate']; see Alpers ¶ 0033 showing involvement of the claimed 'runtime estimated selectivities': The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate))
wherein modifying the query plan … comprises changing … based on at least one runtime estimated predicate selectivity being more than a threshold, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate); see Alpers ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information))
executing the query, by a database execution engine in the database system, according to the modified query plan. (Alpers FIG. 2, step 255, ¶ 0027: In step 255, the RDBMS query can execute using the query optimizer determined access path (access path one or access path two depending on results from step 240 as shown); see Alpers ¶ 0006: a computer program product for skew-sensitive query optimization across join predicates in a relational database management system (RDMBS). In this aspect, a RDBMS query can be received at a query optimizer)
Alpers does not expressly disclose a set of multiple predicates.
Alpers further does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values;
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates,
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Zhang addresses this by teaching the following.
Zhang teaches “a set of multiple predicates” and further teaches “wherein the query includes a set of parameter values for a set of multiple predicates.” (Zhang pp4-5, ¶ 0052-0054: a query optimizer calculates the selectivity of each of order key predicate separately and subsequently multiplies them together … In SQL Statement Example 1, there are two path identifier predicates (lines 4-5) and three order key predicates (lines 6-8))
Zhang further teaches:
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values; (Zhang pp4-5, ¶ 0058-0061: In SQL Statement Example 1, the selectivity of the predicate at line 4 may be determined using Synopsis Example 1 … the selectivity of predicate P1.pathid=PATHTOID(`/A/B`) is 4/14 … Similarly, the selectivity of the predicate at line 5 (P2.pathid=PATHTOID(`/A/B/D`)) may be determined from Synopsis Example 1. The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates, (Zhang pp4-5, ¶ 0058-0061: From Synopsis Example 1, it is determined that the number of elements in XML Document Example 1 is 14 (e.g., "count" of element A+"descendants_cnt" of element A). Also from Synopsis Example 1, it is determined that the number of elements under the path/A/B is four (4) (e.g., "count" of element B) ... The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers with the query planning of Zhang.
In addition, both of the references (Alpers and Zhang) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to optimize queries executed by a database system as seen in Zhang ¶ 0002.
Alpers in view of Zhang does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Han teaches:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates; (Han FIGs. 15, ¶ 0180-0181: For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities [shows worst-case selectivities]. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [shows determination of order])
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and (Han ¶ 0005-0006: the performance is sensitive to the order in which RIDlists are intersected together, and to treating the right predicates as residuals. If the optimizer chooses a wrong order or a wrong residual, due to a poor cardinality estimate, the resulting plan can run orders of magnitude slower than expected [shows changing order to avoid query performance degradation]; Han ¶ 0043-0044: The performance of index anding is very sensitive to two optimizer decisions operator order in the AND-tree and choice of residuals ... With respect to choice of residuals, segment formation and merging is especially slow for poorly selective predicates that have lots of matching RIDs. This situation can arise if the optimizer does a bad job of choosing residual predicates; Han FIGs. 15, ¶ 0181:For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [also shows changing order to query performance degradation])
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query plan optimization of Han.
In addition, both of the references (Alpers as modified and Han) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Han also involving query plan strategies but with the improvement of processing time cost benefits as seen in Han ¶ 0010.
Alpers in view of Zhang and Han does not expressly disclose dynamically modifying the query plan.
However, Krauthgamer addresses this by teaching dynamically modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities… (Krauthgamer ¶ 0038: The lists are ordered not by their marginal (singlepredicate) selectivities, but rather by their conditional selectivities with respect to the portion of the intersection that has already been computed … A sampling procedure is also provided that computes these conditional selectivities at query run time; see also Krauthgamer ¶ 0050: AND-tree is determined only on-the-fly as the intersection proceeds. But this style of progresively building a plan fits well in current query processors)
Krauthgamer also teaches executing the query, by a database execution engine in the database system… (Krauthgamer ¶ 0038: A sampling procedure is also provided that computes these conditional selectivities at query run time [shows execution]; see also Krauthgamer ¶ 0005: Correlation is a persistent problem for the query processors of database systems)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query optimization of Krauthgamer.
In addition, both of the references (Alpers as modified and Krauthgamer) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query optimization.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to implement improved query optimization as seen in Krauthgamer ¶ 0027.
Regarding claim 17, Alpers teaches:
A system comprising: one or more computers; and a computer-readable media coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising: (Alpers ¶ 0016-0018: These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner; ¶ 0028: a network 302 communicatively links one or more computing devices 340)
receiving, at a database system, a query for a database table, wherein the query includes a set of parameter values for a set of … predicates; (Alpers FIG. 1, ¶ 0019: In diagram 100, a relational database management system (RDBMS) is provided with a structure query language (SQL) statement 110. The SQL statement 110 includes a predicate 112 (referred to as a join predicate) with a table join 114 and a column of one of the tables constrained to a variable 116)
identifying a query plan for the query that includes a previously-determined predicate evaluation order for the set of … predicates and a predicate evaluation strategy for each predicate in the set of … predicates, (Alpers shows 'predicate evaluation order' in ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information) [shows previously-determined]; Alpers shows 'predicate evaluation strategy' through its access paths; see Alpers ¶ 0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path; Alpers ¶ 0006: If the estimated quantity of records is greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a first access path. If the estimated quantity of records is not greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a second access path. The first access path and the second access path produce functionally equivalent results while having disparate computational speeds to produce the equivalent results; see also Alpers ¶ 0022-0023: the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) [shows the claimed evaluation strategy involving predicates])
…
determining runtime estimated selectivities by determining a … runtime estimated selectivity for … the set of … predicates based on respective parameter values in the set of parameter values; (Alpers introduces estimated selectivities of predicates as claimed in FIG. 3, ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0032-0033: the query optimizer 312 estimates selectivity across a predicate to pick a better plan than possible if this estimate were not performed … The first time a join occurs on a particular column across two tables, a onetime small overhead estimate for optimization purposes can be performed. The skew estimator 322 performs this estimate, and saves results in the data store 318 for future use by the query optimizer 312. In one embodiment, as records within the respective database repository 330 change over time, skew can change and the estimate for a join predicate can be re-executed [shows being based on 'respective parameter values' as claimed])
determining matching value counts by determining a … matching value count for … the set of … predicates, wherein each matching value count indicates a count of distinct values that match a respective predicate; (Alpers FIG. 1, ¶ 0021-0023, see first ¶ 0021: Diagram 100 estimates the join predicate record return by conducting a query localized to T2 (or to one of the tables of the join predicate) ... A count query 132 is conducted local to table two (T2) where the T2.Col1 is set to the high skew value 127, and where any other local variables (T2.C3) are set to the proper values consistent with the SQL query 110; see also Alpers ¶ 0022: After the SQL count query 132 is executed to estimate the join predicate 120 record quantity, the estimated number of records can be compared against a predefined quantity (e.g., a threshold), as shown by decision block 140. As shown, the count results (from query 132) are compared against a threshold value of fifty)
…modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities or the matching value counts, to generate a modified query plan, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022 showing the claimed 'matching value counts': the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner ... If the count result does not exceed the threshold (in decision block 140), the query optimizer 120 can optimize the RDBMS query 110 using a different access path, as shown by block 144; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) [also shows 'matching value counts'] is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path [shows 'modifying' of a query plan] ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate) [shows being 'with respect to at least one predicate']; see Alpers ¶ 0033 showing involvement of the claimed 'runtime estimated selectivities': The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate))
wherein modifying the query plan … comprises changing … based on at least one runtime estimated predicate selectivity being more than a threshold, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate); see Alpers ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information))
executing the query, by a database execution engine in the database system, according to the modified query plan. (Alpers FIG. 2, step 255, ¶ 0027: In step 255, the RDBMS query can execute using the query optimizer determined access path (access path one or access path two depending on results from step 240 as shown); see Alpers ¶ 0006: a computer program product for skew-sensitive query optimization across join predicates in a relational database management system (RDMBS). In this aspect, a RDBMS query can be received at a query optimizer)
Alpers does not expressly disclose a set of multiple predicates.
Alpers further does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values;
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates,
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Zhang addresses this by teaching the following.
Zhang teaches “a set of multiple predicates” and further teaches “wherein the query includes a set of parameter values for a set of multiple predicates.” (Zhang pp4-5, ¶ 0052-0054: a query optimizer calculates the selectivity of each of order key predicate separately and subsequently multiplies them together … In SQL Statement Example 1, there are two path identifier predicates (lines 4-5) and three order key predicates (lines 6-8))
Zhang further teaches:
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values; (Zhang pp4-5, ¶ 0058-0061: In SQL Statement Example 1, the selectivity of the predicate at line 4 may be determined using Synopsis Example 1 … the selectivity of predicate P1.pathid=PATHTOID(`/A/B`) is 4/14 … Similarly, the selectivity of the predicate at line 5 (P2.pathid=PATHTOID(`/A/B/D`)) may be determined from Synopsis Example 1. The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates, (Zhang pp4-5, ¶ 0058-0061: From Synopsis Example 1, it is determined that the number of elements in XML Document Example 1 is 14 (e.g., "count" of element A+"descendants_cnt" of element A). Also from Synopsis Example 1, it is determined that the number of elements under the path/A/B is four (4) (e.g., "count" of element B) ... The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers with the query planning of Zhang.
In addition, both of the references (Alpers and Zhang) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to optimize queries executed by a database system as seen in Zhang ¶ 0002.
Alpers in view of Zhang does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Han teaches:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates; (Han FIGs. 15, ¶ 0180-0181: For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities [shows worst-case selectivities]. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [shows determination of order])
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and (Han ¶ 0005-0006: the performance is sensitive to the order in which RIDlists are intersected together, and to treating the right predicates as residuals. If the optimizer chooses a wrong order or a wrong residual, due to a poor cardinality estimate, the resulting plan can run orders of magnitude slower than expected [shows changing order to avoid query performance degradation]; Han ¶ 0043-0044: The performance of index anding is very sensitive to two optimizer decisions operator order in the AND-tree and choice of residuals ... With respect to choice of residuals, segment formation and merging is especially slow for poorly selective predicates that have lots of matching RIDs. This situation can arise if the optimizer does a bad job of choosing residual predicates; Han FIGs. 15, ¶ 0181:For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [also shows changing order to query performance degradation])
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query plan optimization of Han.
In addition, both of the references (Alpers as modified and Han) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Han also involving query plan strategies but with the improvement of processing time cost benefits as seen in Han ¶ 0010.
Alpers in view of Zhang and Han does not expressly disclose dynamically modifying the query plan.
However, Krauthgamer addresses this by teaching dynamically modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities… (Krauthgamer ¶ 0038: The lists are ordered not by their marginal (singlepredicate) selectivities, but rather by their conditional selectivities with respect to the portion of the intersection that has already been computed … A sampling procedure is also provided that computes these conditional selectivities at query run time; see also Krauthgamer ¶ 0050: AND-tree is determined only on-the-fly as the intersection proceeds. But this style of progresively building a plan fits well in current query processors)
Krauthgamer also teaches executing the query, by a database execution engine in the database system… (Krauthgamer ¶ 0038: A sampling procedure is also provided that computes these conditional selectivities at query run time [shows execution]; see also Krauthgamer ¶ 0005: Correlation is a persistent problem for the query processors of database systems)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query optimization of Krauthgamer.
In addition, both of the references (Alpers as modified and Krauthgamer) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query optimization.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to implement improved query optimization as seen in Krauthgamer ¶ 0027.
Regarding claim 19, Alpers teaches:
A computer program product encoded on a non-transitory storage medium, the product comprising non-transitory, computer readable instructions for causing one or more processors to perform operations comprising: (Alpers ¶ 0016-0018: These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner)
receiving, at a database system, a query for a database table, wherein the query includes a set of parameter values for a set of … predicates; (Alpers FIG. 1, ¶ 0019: In diagram 100, a relational database management system (RDBMS) is provided with a structure query language (SQL) statement 110. The SQL statement 110 includes a predicate 112 (referred to as a join predicate) with a table join 114 and a column of one of the tables constrained to a variable 116)
identifying a query plan for the query that includes a previously-determined predicate evaluation order for the set of … predicates and a predicate evaluation strategy for each predicate in the set of … predicates, (Alpers shows 'predicate evaluation order' in ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information) [shows previously-determined]; Alpers shows 'predicate evaluation strategy' through its access paths; see Alpers ¶ 0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path; Alpers ¶ 0006: If the estimated quantity of records is greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a first access path. If the estimated quantity of records is not greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a second access path. The first access path and the second access path produce functionally equivalent results while having disparate computational speeds to produce the equivalent results; see also Alpers ¶ 0022-0023: the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) [shows the claimed evaluation strategy involving predicates])
…
determining runtime estimated selectivities by determining a … runtime estimated selectivity for … the set of … predicates based on respective parameter values in the set of parameter values; (Alpers introduces estimated selectivities of predicates as claimed in FIG. 3, ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0032-0033: the query optimizer 312 estimates selectivity across a predicate to pick a better plan than possible if this estimate were not performed … The first time a join occurs on a particular column across two tables, a onetime small overhead estimate for optimization purposes can be performed. The skew estimator 322 performs this estimate, and saves results in the data store 318 for future use by the query optimizer 312. In one embodiment, as records within the respective database repository 330 change over time, skew can change and the estimate for a join predicate can be re-executed [shows being based on 'respective parameter values' as claimed])
determining matching value counts by determining a … matching value count for … the set of … predicates, wherein each matching value count indicates a count of distinct values that match a respective predicate; (Alpers FIG. 1, ¶ 0021-0023, see first ¶ 0021: Diagram 100 estimates the join predicate record return by conducting a query localized to T2 (or to one of the tables of the join predicate) ... A count query 132 is conducted local to table two (T2) where the T2.Col1 is set to the high skew value 127, and where any other local variables (T2.C3) are set to the proper values consistent with the SQL query 110; see also Alpers ¶ 0022: After the SQL count query 132 is executed to estimate the join predicate 120 record quantity, the estimated number of records can be compared against a predefined quantity (e.g., a threshold), as shown by decision block 140. As shown, the count results (from query 132) are compared against a threshold value of fifty)
…modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities or the matching value counts, to generate a modified query plan, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022 showing the claimed 'matching value counts': the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner ... If the count result does not exceed the threshold (in decision block 140), the query optimizer 120 can optimize the RDBMS query 110 using a different access path, as shown by block 144; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) [also shows 'matching value counts'] is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path [shows 'modifying' of a query plan] ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate) [shows being 'with respect to at least one predicate']; see Alpers ¶ 0033 showing involvement of the claimed 'runtime estimated selectivities': The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate))
wherein modifying the query plan … comprises changing … based on at least one runtime estimated predicate selectivity being more than a threshold, (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate); see Alpers ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information))
executing the query, by a database execution engine in the database system, according to the modified query plan. (Alpers FIG. 2, step 255, ¶ 0027: In step 255, the RDBMS query can execute using the query optimizer determined access path (access path one or access path two depending on results from step 240 as shown); see Alpers ¶ 0006: a computer program product for skew-sensitive query optimization across join predicates in a relational database management system (RDMBS). In this aspect, a RDBMS query can be received at a query optimizer)
Alpers does not expressly disclose a set of multiple predicates.
Alpers further does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values;
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates,
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Zhang addresses this by teaching the following.
Zhang teaches “a set of multiple predicates” and further teaches “wherein the query includes a set of parameter values for a set of multiple predicates.” (Zhang pp4-5, ¶ 0052-0054: a query optimizer calculates the selectivity of each of order key predicate separately and subsequently multiplies them together … In SQL Statement Example 1, there are two path identifier predicates (lines 4-5) and three order key predicates (lines 6-8))
Zhang further teaches:
determining runtime estimated selectivities by determining a respective runtime estimated selectivity for each predicate in the set of multiple predicates based on respective parameter values in the set of parameter values; (Zhang pp4-5, ¶ 0058-0061: In SQL Statement Example 1, the selectivity of the predicate at line 4 may be determined using Synopsis Example 1 … the selectivity of predicate P1.pathid=PATHTOID(`/A/B`) is 4/14 … Similarly, the selectivity of the predicate at line 5 (P2.pathid=PATHTOID(`/A/B/D`)) may be determined from Synopsis Example 1. The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
determining matching value counts by determining a respective matching value count for each predicate in the set of multiple predicates, (Zhang pp4-5, ¶ 0058-0061: From Synopsis Example 1, it is determined that the number of elements in XML Document Example 1 is 14 (e.g., "count" of element A+"descendants_cnt" of element A). Also from Synopsis Example 1, it is determined that the number of elements under the path/A/B is four (4) (e.g., "count" of element B) ... The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers with the query planning of Zhang.
In addition, both of the references (Alpers and Zhang) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to optimize queries executed by a database system as seen in Zhang ¶ 0002.
Alpers in view of Zhang does not expressly disclose:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates;
dynamically modifying the query plan…
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and
However, Han teaches:
wherein the previously-determined predicate evaluation order was determined using worst-case selectivities for predicates in the set of multiple predicates; (Han FIGs. 15, ¶ 0180-0181: For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities [shows worst-case selectivities]. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [shows determination of order])
wherein modifying the query plan based on the runtime estimated selectivities comprises changing the previously-determined predicate evaluation order … to avoid query performance degradation scenarios that may occur with the previously-determined predicate evaluation order determined using worst-case selectivities; and (Han ¶ 0005-0006: the performance is sensitive to the order in which RIDlists are intersected together, and to treating the right predicates as residuals. If the optimizer chooses a wrong order or a wrong residual, due to a poor cardinality estimate, the resulting plan can run orders of magnitude slower than expected [shows changing order to avoid query performance degradation]; Han ¶ 0043-0044: The performance of index anding is very sensitive to two optimizer decisions operator order in the AND-tree and choice of residuals ... With respect to choice of residuals, segment formation and merging is especially slow for poorly selective predicates that have lots of matching RIDs. This situation can arise if the optimizer does a bad job of choosing residual predicates; Han FIGs. 15, ¶ 0181:For each query, the embodiments produce the best AND-tree and the worst AND-tree query plan based on the selectivities. Then the embodiments run the 100 queries under four intersection scenarios, 1) best AND-tree intersection, 2) worst AND-tree intersection, 3) round-robin intersection using the worst AND-tree, and 4) probabilistic round-robin using the worst AND-tree ... for some queries, the elapsed time for the worst AND-tree plan is 100 times the elapsed time for the best AND-tree plan. That means these queries are very sensitive to the order of the AND-tree; if the optimizer chooses the wrong order, the queries will be up to 100 times slower [also shows changing order to query performance degradation])
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query plan optimization of Han.
In addition, both of the references (Alpers as modified and Han) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Han also involving query plan strategies but with the improvement of processing time cost benefits as seen in Han ¶ 0010.
Alpers in view of Zhang and Han does not expressly disclose dynamically modifying the query plan.
However, Krauthgamer addresses this by teaching dynamically modifying the query plan with respect to at least one predicate based on at least one of the runtime estimated selectivities… (Krauthgamer ¶ 0038: The lists are ordered not by their marginal (singlepredicate) selectivities, but rather by their conditional selectivities with respect to the portion of the intersection that has already been computed … A sampling procedure is also provided that computes these conditional selectivities at query run time; see also Krauthgamer ¶ 0050: AND-tree is determined only on-the-fly as the intersection proceeds. But this style of progresively building a plan fits well in current query processors)
Krauthgamer also teaches executing the query, by a database execution engine in the database system… (Krauthgamer ¶ 0038: A sampling procedure is also provided that computes these conditional selectivities at query run time [shows execution]; see also Krauthgamer ¶ 0005: Correlation is a persistent problem for the query processors of database systems)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query optimization of Krauthgamer.
In addition, both of the references (Alpers as modified and Krauthgamer) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query optimization.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to implement improved query optimization as seen in Krauthgamer ¶ 0027.
Regarding claim 3, Alpers in view of Zhang teaches:
wherein a predicate evaluation strategy for a second predicate comprises an index lookup strategy. (Alpers ABST: A query optimizer receives a relational database management system (RDBMS) query having a join predicate with a join between a first and a second table; Alpers ¶ 0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path; Alpers ¶ 0006: If the estimated quantity of records is greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a first access path. If the estimated quantity of records is not greater than a previously determined threshold, the query optimizer optimizes the RDBMS query using a second access path. The first access path and the second access path produce functionally equivalent results while having disparate computational speeds to produce the equivalent results; see also Alpers ¶ 0022-0023: the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120))
Regarding claim 5, Alpers in view of Zhang teaches all the features with respect to claim 1.
Alpers teaches:
wherein the predicate evaluation order was previously determined during query compilation based at least on compile-time estimated selectivities of predicates in the set of … predicates determined from a previously-received first set of parameter values. (Alpers introduces estimated selectivities of predicates as claimed in FIG. 3, ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0032-0033: the query optimizer 312 estimates selectivity across a predicate to pick a better plan than possible if this estimate were not performed … The first time a join occurs on a particular column across two tables, a onetime small overhead estimate for optimization purposes can be performed. The skew estimator 322 performs this estimate, and saves results in the data store 318 for future use by the query optimizer 312 [shows having been 'previously-received]. In one embodiment, as records within the respective database repository 330 change over time, skew can change and the estimate for a join predicate can be re-executed)
Zhang teaches estimated selectivities of predicates in the set of multiple predicates. (Zhang pp4-5, ¶ 0058-0061: In SQL Statement Example 1, the selectivity of the predicate at line 4 may be determined using Synopsis Example 1 … the selectivity of predicate P1.pathid=PATHTOID(`/A/B`) is 4/14 … Similarly, the selectivity of the predicate at line 5 (P2.pathid=PATHTOID(`/A/B/D`)) may be determined from Synopsis Example 1. The selectivity of this predicate is 2/14 because there are two (2) elements under the path/A/BID)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers with the query planning of Zhang.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to optimize queries executed by a database system as seen in Zhang ¶ 0002.
Regarding claim 12, Alpers in view of Zhang teaches:
wherein a runtime estimated selectivity of a first predicate corresponds to a percentage of table rows of the database table that are estimated to match the first predicate with respect to a first parameter value in the set of parameters. (Alpers FIG. 3, ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0020: T1 statistics 126 can be available. These statistics 126, as shown, indicate one thousand distinct values for Col1 are present, but that twenty percent of the rows (e.g., records) have a value of “1” for T1.Col1; Alpers ¶ 0022: the relatively high records can result from a high skew (using the value of “1”, which represent 20 percent of the rows from T1.Col1 per statistics 126) which cannot be determined without the estimate from the records returned from the table join 114 further conditioned by a table two column equaling a value (116); Alpers ¶ 0025: In step 220, a value for the join column (e.g., T1.Col1 and/or T2.Col2) can be determined that has a high skew ... in a sales database for a company that sells products in one hundred countries but sells fifty percent of products in the “United States” there would be a high skew. The construction of the able structure of the RDBMS can determine which of the tables is searched for the “high skew” at the join column)
Regarding claim 13, Alpers in view of Zhang teaches:
wherein a runtime estimated selectivity of a first predicate is determined based on locating a first parameter value of the set of parameter values in frequency statistic metadata for the database table. (Alpers ¶ 0019-0020: a query optimizer 120 is sensitive to skew occurring within a join predicate ... T1 statistics 126 can be available. These statistics 126, as shown, indicate one thousand distinct values for Col1 are present, but that twenty percent of the rows (e.g., records) have a value of “1” for T1.Col1 … Therefore, the query optimizer will assume that each value exists 1/1000 times—since there are 1000 distinct values, and each join is searching for one of those 1000 values)
Regarding claim 14, Alpers in view of Zhang teaches:
wherein a runtime estimated selectivity of a first predicate is determined based on sampling the database table and determining how many sampled rows of the database table match the first predicate with respect to a first parameter value of the set of parameters. (Alpers FIG. 1, ¶ 0021-0023, see first ¶ 0021: Diagram 100 estimates the join predicate record return by conducting a query localized to T2 (or to one of the tables of the join predicate) ... A count query 132 is conducted local to table two (T2) where the T2.Col1 is set to the high skew value 127, and where any other local variables (T2.C3) are set to the proper values consistent with the SQL query 110; see also Alpers ¶ 0022: After the SQL count query 132 is executed to estimate the join predicate 120 record quantity, the estimated number of records can be compared against a predefined quantity (e.g., a threshold), as shown by decision block 140. As shown, the count results (from query 132) are compared against a threshold value of fifty; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245)
Regarding claim 15, Alpers in view of Zhang teaches:
wherein a runtime estimated selectivity of a first predicate is determined by: determining that a column referenced in the first predicate stores unique values; and (Alpers ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; Alpers ¶ 0025: The construction of the able structure of the RDBMS can determine which of the tables is searched for the “high skew” at the join column. For example, if the RDBMS is in third normal form (3NF), T1.Col1 can be a primary key or a foreign key (values unique) for country code)
determining the runtime estimated selectivity of the first predicate by dividing a value of one by a row count of the database table. (Alpers ¶ 0010: compute an estimate of records returned for a join predicate to estimate selectively (i.e., inverse of amount of record skew) during query optimization; see Alpers ¶ 0003: Record skew is a measurement of asymmetry within a distribution of data in a table. Another related term is “selectivity” which is the measure of the filtering in that a query is highly selective if it results in a minimal number of records being returned and has low selectively if it results in a large quantity of records being returned)
Regarding claim 16, Alpers in view of Zhang and Han and Krauthgamer teaches all the features with respect to claim 1 above including:
wherein the set of multiple predicates are included in a conjunction. (Han ¶ 0196: FIG. 20 illustrates a query processing method to intersect two or more unsorted lists based on a conjunction of predicates)
Claims 2, 8-9, 11; 18; and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Alpers in view of Zhang and Han and Krauthgamer in further view of Merker et al., U.S. Patent No. 11,016,973 (published May 25, 2021; hereinafter Merker).
Regarding claims 2, 18, and 20, Alpers in view of Zhang and Han and Krauthgamer teaches all the features with respect to claims 1, 17, and 19 above respectively including wherein a predicate evaluation strategy for a first predicate comprises a … strategy.
Alpers in view of Zhang and Han and Krauthgamer does not expressly disclose a data vector scan strategy.
However, Merker addresses this by teaching a data vector scan strategy. (Merker col. 9, lines 45-61: the table adapter 250/252 may each include one or more of the following types of metadata to enable access to, and/or, preparation of a table object for the execution engine … one or more query execution hints about execution strategies that may be beneficial for the table (e.g., for a given table whether a full indexvector scan or a single docid lookup is optimum))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the access paths and query plans of Alpers as modified with the query plan execution of Merker.
In addition, both of the references (Alpers as modified and Merker) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Merker also involving query strategies but further including metadata to enable access to and/or preparation of data for query execution including execution strategies beneficial for the table (Merker col. 9, lines 45-61).
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to reduce or eliminate the need for specialized execution engines for each type of database as seen in Merker col. 3, lines 61-67.
Regarding claim 8, Alpers in view of Zhang and Han and Krauthgamer teaches all the features with respect to claim 1 above including:
wherein modifying the query plan comprises changing a predicate evaluation strategy for a first predicate from an index lookup strategy to a … strategy based on a matching value count for the first predicate being more than a second threshold. (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate); see Alpers ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate))
Alpers teaches an index lookup strategy. (Alpers ¶ 0001-0002, see first ¶ 0001: database query optimization and, more particularly, to skew sensitive estimating of record cardinality of a join predicate for optimizer access path (e.g., query plan) selection; see then Alpers ¶ 0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path. In a table scan, the query optimizer sequentially reads all rows of a table and compares each row with the search criteria in the WHERE clause, which is called a predicate in a SQL query)
Alpers in view of Zhang and Han and Krauthgamer does not expressly disclose a data vector scan strategy.
However, Merker addresses this by teaching a data vector scan strategy. (Merker col. 9, lines 45-61: the table adapter 250/252 may each include one or more of the following types of metadata to enable access to, and/or, preparation of a table object for the execution engine … one or more query execution hints about execution strategies that may be beneficial for the table (e.g., for a given table whether a full indexvector scan or a single docid lookup is optimum))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the access paths and query plans of Alpers with the query plan execution of Merker.
In addition, both of the references (Alpers and Merker) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would be to improve the functioning of Alpers and its various query plan strategies with the functioning of similar reference Merker also involving query strategies but further including metadata to enable access to and/or preparation of data for query execution including execution strategies beneficial for the table (Merker col. 9, lines 45-61).
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to reduce or eliminate the need for specialized execution engines for each type of database as seen in Merker col. 3, lines 61-67.
Regarding claim 9, Alpers in view of Zhang and Han and Krauthgamer and Merker teaches all the features with respect to claim 8 above including:
wherein the predicate evaluation strategy for the first predicate is changed from the index lookup strategy to the … strategy to avoid multiple index lookups of multiple different values. (Alpers ¶ 0001-0002: Two access paths available to a query optimizer that produces equivalent results include a table scan access path and an index access path. In a table scan, the query optimizer sequentially reads all rows of a table and compares each row with the search criteria in the WHERE clause, which is called a predicate in a SQL query ... Generally, when a number of records being considered is high, the table scan access path is faster)
Merker teaches the data vector scan strategy. (Merker col. 9, lines 45-61: the table adapter 250/252 may each include one or more of the following types of metadata to enable access to, and/or, preparation of a table object for the execution engine … one or more query execution hints about execution strategies that may be beneficial for the table (e.g., for a given table whether a full indexvector scan or a single docid lookup is optimum))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the access paths and query plans of Alpers as modified with the query plan execution of Merker.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Merker also involving query strategies but further including metadata to enable access to and/or preparation of data for query execution including execution strategies beneficial for the table (Merker col. 9, lines 45-61).
Regarding claim 11, Alpers in view of Zhang and Han and Krauthgamer teaches all the features with respect to claim 1 above including:
wherein modifying the query plan comprises changing a predicate evaluation strategy for a first predicate from an index lookup strategy to a … strategy based on the first predicate … in the predicate evaluation order. (Alpers ¶ 0032-0033, see first ¶ 0032: the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders; see then Alpers ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate). The access path or query plan as used herein represents an ordered set of steps used to access data in a SQL RDBMS (e.g., database repository 330 information); Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the query optimizer 120 can optimize the RDBMS query 110 using a different access path, as shown by block 144; see also Alpers FIG. 2, step 255, ¶ 0027: step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate))
Han teaches the first predicate no longer being positioned first in the predicate evaluation order. (Han FIGs. 1-3, ¶ 0041-0044: Residuals are shown as item 206, where these fetched rows are joined with all the remaining dimension tables (residual tables), to get any remaining columns and evaluate any residual predicates … The performance of index anding is very sensitive to two optimizer decisions operator order in the AND-tree and choice of residuals. With respect to operator order in the AND-tree, since the cost of a pairwise AND is related to the input sizes, it is important to AND early those pairs of legs that have small intersections.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query plans of Alpers as modified with the query plan optimization of Han.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Han also involving query plan strategies but with the improvement of processing time cost benefits as seen in Han ¶ 0010.
Alpers in view of Zhang and Han and Krauthgamer does not expressly disclose the data vector scan strategy.
However, Merker addresses this by teaching data vector scan strategy. (Merker col. 9, lines 45-61: the table adapter 250/252 may each include one or more of the following types of metadata to enable access to, and/or, preparation of a table object for the execution engine … one or more query execution hints about execution strategies that may be beneficial for the table (e.g., for a given table whether a full indexvector scan or a single docid lookup is optimum))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the access paths and query plans of Alpers as modified with the query plan execution of Merker.
In addition, both of the references (Alpers as modified and Merker) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query plan management and execution.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Merker also involving query strategies but further including metadata to enable access to and/or preparation of data for query execution including execution strategies beneficial for the table (Merker col. 9, lines 45-61).
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to reduce or eliminate the need for specialized execution engines for each type of database as seen in Merker col. 3, lines 61-67.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Alpers in view of Zhang and Han and Krauthgamer and Merker in further view of Cain et al., U.S. Patent Application Publication No. 2009/0182720 (hereinafter Cain).
Regarding claim 10, Alpers in view of Zhang and Han and Krauthgamer in further view of Merker teaches all the features with respect to claim 8 above including:
wherein the predicate evaluation strategy for the first predicate is changed from the index lookup strategy to the … strategy… (Alpers FIG. 1, ¶ 0021-0023, see mostly ¶ 0022: the count results (from query 132) are compared against a threshold value of fifty. If the estimate is greater than the threshold, the query optimizer executes (142) an access path for the SQL query 110, which is designed to handle a relatively large number of records (in the join predicate 120) in an optimal manner; see also Alpers FIG. 2, step 255, ¶ 0027: In step 240, if the quantity of records (estimated per step 235) is greater than a previously determined threshold, the process can continue to step 245, where the query optimizer can optimize the query per a first access path ... step 250 can execute where the query optimizer selects a second access path (optimized for a relatively low quantity of records resulting from the join predicate); see Alpers ¶ 0033: The access path selector 324 selects one of the query plans available to the query optimizer 312 given the estimate (which has estimated selectively of the join predicate))
Alpers in view of Zhang and Han and Krauthgamer and Merker does not expressly disclose doing so to enable data vector scan parallelism.
However, Cain teaches changing strategies “to enable data vector scan parallelism.” (Cain ¶ 0004: encoded vector index ("EVI"). An EVI is a data structure that is made up of two primary components: a symbol table and a vector … Because of their compact size and relative simplicity, EVIs provide for faster scans of a table that may also be processed in parallel; Cain shows involvement of predicates in at least ¶ 0008: Determining if a predicate structure is a good candidate for a symbol table only data structure, for some embodiments, includes analyzing a grouping, ordering, and distincting of the database query and system generated lookahead predicates. Generation of the symbol table only data structure may be triggered)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the access paths and query plans of Alpers as modified with the database query optimization of Cain.
In addition, both of the references (Alpers as modified and Cain) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as query management and execution.
Motivation to do so would be to improve the functioning of Alpers as modified and its various query plan strategies with the functioning of similar reference Cain also involving query strategies but further including vector techniques and symbol techniques.
Claim 13 is rejected under 35 U.S.C. 103 as being unpatentable over Alpers in view of Zhang and Han and Krauthgamer and Su et al., U.S. Patent Application Publication No. 2014/0095475 (hereinafter Su).
Regarding claim 13, Alpers and Zhang and Han and Krauthgamer teaches all the features with respect to claim 1 above including:
wherein a runtime estimated selectivity of a first predicate is determined based on locating a first parameter value of the set of parameter values in … statistic metadata for the database table. (Zhang ¶ 0058: SQL Statement Example 1, the selectivity of the predicate at line 4 may be determined...; see then Zhang ¶ 0061: Each of these selectivity values may be calculated using statistics (e.g., from Synopsis Example 1) on the PATHID and ORDER_KEY columns)
Alpers and Zhang and Han and Krauthgamer does not expressly disclose frequency statistic metadata.
However, Su addresses this by teaching determin[ing] based on locating a first parameter value of the set of parameter values in frequency statistic metadata for the database table. (Su FIG. 6A, ¶ 0187-0196; see ¶ 0187: The accuracy of a histogram is important for selectivity estimation. If a query optimizer checks a histogram to determine a selectivity of a particular value in a query and the histogram is not accurate regarding the frequency of the particular value, then the query optimizer might select a suboptimal execution plan; see ¶ 0188: One type of histogram is a "frequency" histogram that indicates, for each distinct value in a set, a frequency of that distinct value)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the functioning of the query optimizer and selectivity determination of Alpers as modified with the selectivity histograms of Su.
In addition, both of the references (Alpers as modified and Su) disclose features that are directed to analogous art, and they are directed to the same field of endeavor, such as selectivity determination.
Motivation to do so would be to improve the functioning of Alpers as modified and its query optimizer deriving statistics associated with tables to determine cost with the functioning of similar reference Su also deriving statistics associated with tables but with added histogram techniques.
Motivation to do so would also be the teaching, suggestion, or motivation for a person of ordinary skill in the art to gather information for automatic reoptimization of queries as seen in Su ¶ 0023.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Bruno et al., U.S. Patent Application Publication No. 2005/0004907, "Method And Apparatus For Using Conditional Selectivity As Foundation For Exploiting Statistics On Query Expressions"; see Bruno FIG. 4, ¶ 0053-0054 describing selectivity estimation and worst-case complexity of function getSelectivity, relevant to at least the independent claim limitations involving worst-case selectivities.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JEDIDIAH P FERRER whose telephone number is (571)270-7695. The examiner can normally be reached Monday-Friday 12:00pm-8:00pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kavita Stanley can be reached at (571)272-8352. 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.
/J.P.F/Examiner, Art Unit 2153 April 17, 2026
/KAVITA STANLEY/Supervisory Patent Examiner, Art Unit 2153
Prosecution Insights