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 .
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1 ,11, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591) in view of Stolze et al. (US Publication No. 2026/0119495).
As to claim 1, Du teaches a system comprising:
at least one hardware processor [CPU] (see e.g., col. 1, lines 47-62 for each computer site having its own CPU (central processing unit)); and
a memory [local storage] storing instructions that cause the at least one hardware processor to perform operations (see e.g., col. 1, lines 47-62 for each computer site having a DBMS in its own right: it having its own terminals and users, its own local storage and CPU (central processing unit), running its own database and database administration functions (i.e. a local DBMS)) comprising:
receiving an initial query plan [left deep join plan] (see e.g., col. 4, lines 30-43 for a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage and col. 18, lines 4-18 for obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach. A left deep join plan is received.);
performing a bottom-up plan reconstruction process on the initial query plan, the bottom-up plan reconstruction process generating a transformed query plan (see e.g., col. 4, lines 30-43 for then, the plan being improved (with respect to response time) using the proposed transformations, col. 7, lines 44-60 for the preferred transformation methods including bottom-up processes, col. 14, lines 20-24 for a left deep join tree being balanced by calling Bottom-Up(N), where N is the root of the join tree, and col. 18, lines 4-18 for the subplan being then balanced using the proposed transformations. The left deep join plan is reconstructed using a bottom-up transformation.); and
providing the transformed query plan to an execution node for executing the transformed query plan (see e.g., abstract for the query being executed in a relational database to retrieve data responsive to the query in accordance with an execution plan operating according to the balanced query tree, col. 5, lines 16-33 for finally, the query being executed in a relational database, and col. 7, lines 43-60 for the restructured query being then executed within the global relational database 168).
Du does not specifically disclose receiving a directive specifying a join order hint; and performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive. However, Stolze teaches
receiving a directive specifying a join order hint [user-configured join order parameter data] (see e.g., [0456] for FIGS. 28A-28E illustrating embodiments where a query expression that indicates joining of a plurality of input row sets via executing a plurality of corresponding join operations in an ordering specified by a join tree generated based on user-configured join order parameter data in generating a corresponding query operator execution flow. User-configured join order parameter data is received from a user.); and
performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive (see e.g., [0417] for in the example of FIG. 27J, an initial join tree 3010.0 in a left-deep tree configuration being rearranged as an updated join tree 3010.1 in a bushy tree configuration and [0457] for in addition to automatically selecting join order via an optimization process as discussed in conjunction with FIGS. 27E-27H, the corresponding topology of join tree 3010 being partially or entirely dictated by user-configured join order parameter data 3015. A left-deep tree is transformed into a bushy tree based on user-configured join order parameter data.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du to receive a directive specifying a join order hint; and perform a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive, as taught by Stolze, for the benefit of the user specifying the order in which tables shall be jointed (see e.g., Stolze, [0460]).
As to claim 11, Du teaches a method comprising:
receiving an initial query plan [left deep join plan] (see e.g., col. 4, lines 30-43 for a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage and col. 18, lines 4-18 for obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach. A left deep join plan is received.);
performing a bottom-up plan reconstruction process on the initial query plan, the bottom-up plan reconstruction process generating a transformed query plan (see e.g., col. 4, lines 30-43 for then, the plan being improved (with respect to response time) using the proposed transformations, col. 7, lines 44-60 for the preferred transformation methods including bottom-up processes, col. 14, lines 20-24 for a left deep join tree being balanced by calling Bottom-Up(N), where N is the root of the join tree, and col. 18, lines 4-18 for the subplan being then balanced using the proposed transformations. The left deep join plan is reconstructed using a bottom-up transformation.); and
providing the transformed query plan to an execution node for executing the transformed query plan (see e.g., abstract for the query being executed in a relational database to retrieve data responsive to the query in accordance with an execution plan operating according to the balanced query tree, col. 5, lines 16-33 for finally, the query being executed in a relational database, and col. 7, lines 43-60 for the restructured query being then executed within the global relational database 168).
Du does not specifically disclose receiving a directive specifying a join order hint; and performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive. However, Stolze teaches
receiving a directive specifying a join order hint [user-configured join order parameter data] (see e.g., [0456] for FIGS. 28A-28E illustrating embodiments where a query expression that indicates joining of a plurality of input row sets via executing a plurality of corresponding join operations in an ordering specified by a join tree generated based on user-configured join order parameter data in generating a corresponding query operator execution flow. User-configured join order parameter data is received from a user.); and
performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive (see e.g., [0417] for in the example of FIG. 27J, an initial join tree 3010.0 in a left-deep tree configuration being rearranged as an updated join tree 3010.1 in a bushy tree configuration and [0457] for in addition to automatically selecting join order via an optimization process as discussed in conjunction with FIGS. 27E-27H, the corresponding topology of join tree 3010 being partially or entirely dictated by user-configured join order parameter data 3015. A left-deep tree is transformed into a bushy tree based on user-configured join order parameter data.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du to receive a directive specifying a join order hint; and perform a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive, as taught by Stolze, for the benefit of the user specifying the order in which tables shall be jointed (see e.g., Stolze, [0460]).
As to claim 20, Du teaches a non-transitory computer storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:
receiving an initial query plan [left deep join plan] (see e.g., col. 4, lines 30-43 for a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage and col. 18, lines 4-18 for obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach. A left deep join plan is received.);
performing a bottom-up plan reconstruction process on the initial query plan, the bottom-up plan reconstruction process generating a transformed query plan (see e.g., col. 4, lines 30-43 for then, the plan being improved (with respect to response time) using the proposed transformations, col. 7, lines 44-60 for the preferred transformation methods including bottom-up processes, col. 14, lines 20-24 for a left deep join tree being balanced by calling Bottom-Up(N), where N is the root of the join tree, and col. 18, lines 4-18 for the subplan being then balanced using the proposed transformations. The left deep join plan is reconstructed using a bottom-up transformation.); and
providing the transformed query plan to an execution node for executing the transformed query plan (see e.g., abstract for the query being executed in a relational database to retrieve data responsive to the query in accordance with an execution plan operating according to the balanced query tree, col. 5, lines 16-33 for finally, the query being executed in a relational database, and col. 7, lines 43-60 for the restructured query being then executed within the global relational database 168).
Du does not specifically disclose receiving a directive specifying a join order hint; and performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive. However, Stolze teaches
receiving a directive specifying a join order hint [user-configured join order parameter data] (see e.g., [0456] for FIGS. 28A-28E illustrating embodiments where a query expression that indicates joining of a plurality of input row sets via executing a plurality of corresponding join operations in an ordering specified by a join tree generated based on user-configured join order parameter data in generating a corresponding query operator execution flow. User-configured join order parameter data is received from a user.); and
performing a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive (see e.g., [0417] for in the example of FIG. 27J, an initial join tree 3010.0 in a left-deep tree configuration being rearranged as an updated join tree 3010.1 in a bushy tree configuration and [0457] for in addition to automatically selecting join order via an optimization process as discussed in conjunction with FIGS. 27E-27H, the corresponding topology of join tree 3010 being partially or entirely dictated by user-configured join order parameter data 3015. A left-deep tree is transformed into a bushy tree based on user-configured join order parameter data.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du to receive a directive specifying a join order hint; and perform a reconstruction process based on the directive, the reconstruction process generating a transformed query plan that conforms to the join order hint specified in the directive, as taught by Stolze, for the benefit of the user specifying the order in which tables shall be jointed (see e.g., Stolze, [0460]).
Claims 2-4, 6, 7, 12-14, 16, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591) in view of Stolze et al. (US Publication No. 2016/0119495) as applied to claims 1 ,11, and 20 above, and further in view of Nica (US Publication No. 2004/0006561).
As to claim 2, the limitations of parent claim 1 have been discussed above. Du teaches
analyzing the initial query plan to identify a set of logical query blocks [UANs] where at least one join operator can be reordered (see e.g., col. 4, lines 30-43 for first, a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations, col. 9, lines 56-65 for UAN being upper anchor node, and col. 14, lines 20-24 for the bottom-up approach balancing UANs after their child subtrees have been balanced and a left deep join tree being balanced by calling Bottom-Up(N), where N is the root of the join tree. The left deep join execution plan is analyzed to identify a set of UANs, which represent joins and are reordered to obtain balance.)
Du in view of Stolze does not specifically disclose performing a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments. However, Nica teaches
performing a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments [plan nodes] ( see e.g., [0027] for a query block referring to an atomic portion or block of a query that has more than one block because the query contains derived tables, views, and/or subqueries, [0068] for Query Optimization Graph (QOG) being the internal representation of a query block, FIGS. 5A-5D, and [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. Each query block is decomposed into a set of plan nodes during optimization in order to generate a QOG.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to perform a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 3, the limitations of parent claims 1 and 2 have been discussed above. Du in view of Stolze does not specifically disclose wherein the dismantle process, for each logical query block, generates a mapping of aliases to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side fragments of each non-inner join. However, Nica teaches
wherein the dismantle process, for each logical query block, generates a mapping of aliases [S, q, p] to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side [null-supplying side] fragments of each non-inner join (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, and [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan. Plan nodes include subplans and quantifiers. For each query block, subplans are mapped to alias S and quantifiers are mapped to alias q. Inner joins are represented by undirected edges and predicates from the undirected edges are mapped to alias p. Non-inner joins are represented by directed edges. Null-supplying subplans of each directed edge are mapped to alias S.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze wherein the dismantle process, for each logical query block, generates a mapping of aliases to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side fragments of each non-inner join, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 4, the limitations of parent claims 1-3 have been discussed above. Du teaches
performing a reconstruction process to generate a transformed query plan (see e.g., col. 4, lines 30-43 for first, a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations and col. 18, lines 4-17 for first obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach and the subplan then being balanced using the proposed transformations).
Du in view of Stolze does not specifically disclose using at least the set of plan fragments to generate the query plan. However, Nica teaches
using at least the set of plan fragments to generate the query plan [QOG] (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. The plan nodes are used to generate the QOG).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to use at least the set of plan fragments to generate the query plan, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 6, the limitations of parent claims 1-3 have been discussed above. Du in view of Stolze does not specifically disclose wherein the dismantle process further comprises: storing a set of non-inner join keys separately from the join keys from the inner joins. However, Nica teaches wherein the dismantle process further comprises:
storing a set of non-inner join keys separately from the join keys from the inner joins (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan and the ON condition being part of the definition of the subplan S, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Non-inner join predicates are stored as part of the null-supplying subplan definition. Inner join predicates are stored as part of the undirected edge definition. Join predicates include join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze wherein the dismantle process further comprises: storing a set of non-inner join keys separately from the join keys from the inner joins, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 7, the limitations of parent claims 1-3 have been discussed above. Du in view of Stolze does not specifically disclose placing a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment. However, Nica teaches
placing a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan and the ON condition being part of the definition of the subplan S, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Null-supplying predicates are placed in a QOG by looking up the mapping of null-supplying subplans with a particular null-supplying subplan. Null-supplying predicates include join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to place a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 12, the limitations of parent claim 11 have been discussed above. Du teaches
analyzing the initial query plan to identify a set of logical query blocks [UANs] where at least one join operator can be reordered (see e.g., col. 4, lines 30-43 for first, a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations, col. 9, lines 56-65 for UAN being upper anchor node, and col. 14, lines 20-24 for the bottom-up approach balancing UANs after their child subtrees have been balanced and a left deep join tree being balanced by calling Bottom-Up(N), where N is the root of the join tree. The left deep join execution plan is analyzed to identify a set of UANs, which represent joins and are reordered to obtain balance.)
Du in view of Stolze does not specifically disclose performing a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments. However, Nica teaches
performing a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments [plan nodes] ( see e.g., [0027] for a query block referring to an atomic portion or block of a query that has more than one block because the query contains derived tables, views, and/or subqueries, [0068] for Query Optimization Graph (QOG) being the internal representation of a query block, FIGS. 5A-5D, and [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. Each query block is decomposed into a set of plan nodes during optimization in order to generate a QOG.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to perform a dismantle process to decompose each logical query block of the set of logical query blocks into a set of plan fragments, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 13, the limitations of parent claims 11 and 12 have been discussed above. Du in view of Stolze does not specifically disclose wherein the dismantle process, for each logical query block, generates a mapping of aliases to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side fragments of each non-inner join. However, Nica teaches
wherein the dismantle process, for each logical query block, generates a mapping of aliases [S, q, p] to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side [null-supplying side] fragments of each non-inner join (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, and [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan. Plan nodes include subplans and quantifiers. For each query block, subplans are mapped to alias S and quantifiers are mapped to alias q. Inner joins are represented by undirected edges and predicates from the undirected edges are mapped to alias p. Non-inner joins are represented by directed edges. Null-supplying subplans of each directed edge are mapped to alias S.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze wherein the dismantle process, for each logical query block, generates a mapping of aliases to particular plan fragments from the set of plan fragments, a set of predicates from inner joins or filter nodes, and a mapping of non-preserved side fragments of each non-inner join, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 14, the limitations of parent claims 11-13 have been discussed above. Du teaches
performing a reconstruction process to generate a transformed query plan (see e.g., col. 4, lines 30-43 for first, a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations and col. 18, lines 4-17 for first obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach and the subplan then being balanced using the proposed transformations).
Du in view of Stolze does not specifically disclose using at least the set of plan fragments to generate the query plan. However, Nica teaches
using at least the set of plan fragments to generate the query plan [QOG] (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. The plan nodes are used to generate the QOG).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to use at least the set of plan fragments to generate the query plan, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 16, the limitations of parent claims 11-13 have been discussed above. Du in view of Stolze does not specifically disclose storing a set of non-inner join keys separately from the join keys from the inner joins. However, Nica teaches
storing a set of non-inner join keys separately from the join keys from the inner joins (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan and the ON condition being part of the definition of the subplan S, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Non-inner join predicates are stored as part of the null-supplying subplan definition. Inner join predicates are stored as part of the undirected edge definition. Join predicates include join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to store a set of non-inner join keys separately from the join keys from the inner joins, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
As to claim 17, the limitations of parent claims 11-13 have been discussed above. Du in view of Stolze does not specifically disclose placing a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment. However, Nica teaches
placing a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0086]-[0087] for subplans being defined for the following table expressions: (a) null-supplying side of an outer join, called a "null-supplying" subplan, [0091] for each subplan S being a tuple S=(PNS, pS, ES) where PNS is the set of subplan's plan nodes, pS is a predicate and ES is a set of edges defined for the plan nodes in PNS, for each subplan, Quantifiers(S) denoting all quantifiers used by the subplan S or by any nested subplan, and if q is a quantifier then Quantifiers(q) being defined as the set {q}, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan and the ON condition being part of the definition of the subplan S, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Null-supplying predicates are placed in a QOG by looking up the mapping of null-supplying subplans with a particular null-supplying subplan. Null-supplying predicates include join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to place a set of non-inner join keys by looking up the mapping of non-preserved side fragments with a particular non-preserved side fragment, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
Claims 5, 8, 15, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591) and Stolze et al. (US Publication No. 2016/0119495) in view of Nica (US Publication No. 2004/0006561) as applied to claims 2-4, 6, 7, 12-14, 16, and 17 above, and further in view of Adams et al. (US Patent No. 11,100,105).
As to claim 5, the limitations of parent claims 1-4 have been discussed above. Du teaches wherein the reconstruction process comprises:
performing a query plan shape construction process (see e.g., col. 18, lines 4-17 for first obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach and the subplan then being balanced using the proposed transformations. A plan in a left deep join shape is transformed to a balanced shape.), the query plan shape construction process comprising:
generating a semantically equivalent intermediate plan (see e.g., col. 4, lines 30-43 for a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations, and further, basic transformations and processes being described which effectively apply the transformations to a left deep join tree and col. 10, lines 17-27 for for a given query tree, there being many possible applicable basic transformations, only those transformations which are both valid and cost improving being of interest, a basic transformation being valid if it preserves the semantics of the original query tree, and in other words, the transformed query tree evaluating the same query as the original one. The balanced plan is semantically equivalent to the left deep join plan.).
Du does not specifically disclose reassambling the query plan based on the directive. However, Stolze teaches
reassambling the query plan based on the directive (see e.g., [0417] for in the example of FIG. 27J, an initial join tree 3010.0 in a left-deep tree configuration being rearranged as an updated join tree 3010.1 in a bushy tree configuration and [0457] for in addition to automatically selecting join order via an optimization process as discussed in conjunction with FIGS. 27E-27H, the corresponding topology of join tree 3010 being partially or entirely dictated by user-configured join order parameter data 3015. A left-deep tree is transformed into a bushy tree based on user-configured join order parameter data.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du to reassamble the query plan based on the directive, as taught by Stolze, for the benefit of the user specifying the order in which tables shall be jointed (see e.g., Stolze, [0460]).
Du in view of Stolze does not specifically disclose the query plan comprising the set of plan fragments; and constructing a set of new inner join nodes. However, Nica teaches
the query plan comprising the set of plan fragments (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. The plan nodes are used to generate the QOG); and
constructing a set of new inner join nodes (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, and [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan. Inner joins are represented by undirected edges connecting plan nodes.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to include the query plan comprising the set of plan fragments and constructing a set of new inner join nodes, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
Du and Stolze in view of Nica does not specifically disclose constructing a set of new join nodes as cartesian joins; and placing collected join keys and join filters as a filter node above a topmost join node. However, Adams teaches
constructing a set of new join nodes as cartesian joins (see e.g., col. 4, line 64 - col. 5, line 27 for with respect to query processing, it occurring that a join operator (also referred to as a join) in a query-execution plan includes a join predicate that itself contains a complex geospatial function such as ST_Contains, in the present disclosure, a join that includes such a join predicate being referred to as a geospatial-function join, and the corresponding join predicate being referred to as a geospatial-function predicate, in some current implementations of database platforms, in order to perform a geospatial-function join, an operation that is known as a cross join being performed, which involves generating what is referred to as the “Cartesian product” of the left-side relation and the right-side relation of the join, and the Cartesian product of a given left-side relation and a given right-side relation including rows that are every possible combination of one row from the given left-side relation and one row from the given right-side relation. A set of geospatial function join nodes is constructed as cartesian joins.); and
placing collected join keys [geography-data-object join keys] and join filters [complex geospatial function] as a filter node above a topmost join node [cartesian product] (see e.g., col. 4, line 64 - col. 5, line 27 for the two relevant geography data objects-referred to herein as the geography-data-object join keys, one originally from the given left-side relation and the other originally from the given right-side relation—from each and every row of this Cartesian product being then input into a filter that implements the complex geospatial function, and those rows for which the geospatial function returns TRUE are included in the output of this filter whereas those rows for which the geospatial function returns FALSE are not included in the output of this filter. The geography-data-object join keys and complex geospatial function are placed as a filter node above the cartesian product.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du and Stolze in view of Nica to construct a set of new join nodes as cartesian joins; and place collected join keys and join filters as a filter node above a topmost join node, as taught by Adams, for the benefit of performing a join predicate that contains a complex function (see e.g., Adams, col. 4, line 64 - col. 5, line 27).
As to claim 8, the limitations of parent claims 1-5 have been discussed above. Du in view of Stolze does not specifically disclose deriving a set of optimal join keys from a set of constructed nodes from the semantically equivalent intermediate plan. However, Nica teaches
deriving a set of optimal join keys from a set of constructed nodes [plan nodes, access methods, join methods] from the semantically equivalent intermediate plan [candidate plan segment] (see e.g., [0032] for candidate plan segments representing candidate plan nodes, access methods and join methods for inclusion in the access plans, the plan nodes representing subplans and quantifiers, and for each query block comprising an atomic portion of the query, determining an optimal access plan by performing the substeps of: placing a candidate plan segment in a partial access plan being generated for the query block; evaluating the partial access plan including the candidate plan segment; if the partial access plan is less favorable than a complete access plan previously identified for said query block, pruning said candidate plan segment; otherwise, adding an additional candidate plan segment to the partial access plan and repeating the above substeps until a complete access plan for the query block is generated, retaining a complete access plan if it is more favorable than other complete access plans previously generated for the query block; and otherwise pruning a complete access plan which is less favorable than other complete access plans, [0156] for the current partial access plan 620 being shown at the right hand side of FIG. 6, each pni being a plan node that belongs to the subplan and can represent another subplan or a quantifier, and a candidate access method of the plan node pnj being denoted as amj, while jmj represents a candidate join method that can be used to join pnj<amj> with the prefix of the plan, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Optimal plan segments are derived from a set of plan nodes, access methods, and join methods from the candidate plan segments. Optimal plan segments include optimal join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to derive a set of optimal join keys from a set of constructed nodes from the semantically equivalent intermediate plan, as taught by Nica, for the benefit of enabling queries to be effectively optimized while requiring a minimal amount of memory for generating the search space and for storing the information required for query optimization (see e.g., Nica, [0023]).
As to claim 15, the limitations of parent claims 11-14 have been discussed above. Du teaches wherein the reconstruction process comprises:
performing a query plan shape construction process (see e.g., col. 18, lines 4-17 for first obtaining the optimal (left deep join) subplan (with respect to total resource usage) using the traditional approach and the subplan then being balanced using the proposed transformations. A plan in a left deep join shape is transformed to a balanced shape.), the query plan shape construction process comprising:
generating a semantically equivalent intermediate plan (see e.g., col. 4, lines 30-43 for a traditional cost-based (e.g., System R style) optimization process being employed to obtain a left deep join execution plan which is optimal with respect to total resource usage; then, the plan being improved (with respect to response time) using the proposed transformations, and further, basic transformations and processes being described which effectively apply the transformations to a left deep join tree and col. 10, lines 17-27 for for a given query tree, there being many possible applicable basic transformations, only those transformations which are both valid and cost improving being of interest, a basic transformation being valid if it preserves the semantics of the original query tree, and in other words, the transformed query tree evaluating the same query as the original one. The balanced plan is semantically equivalent to the left deep join plan.).
Du does not specifically disclose reassambling the query plan based on the directive. However, Stolze teaches
reassambling the query plan based on the directive (see e.g., [0417] for in the example of FIG. 27J, an initial join tree 3010.0 in a left-deep tree configuration being rearranged as an updated join tree 3010.1 in a bushy tree configuration and [0457] for in addition to automatically selecting join order via an optimization process as discussed in conjunction with FIGS. 27E-27H, the corresponding topology of join tree 3010 being partially or entirely dictated by user-configured join order parameter data 3015. A left-deep tree is transformed into a bushy tree based on user-configured join order parameter data.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du to reassamble the query plan based on the directive, as taught by Stolze, for the benefit of the user specifying the order in which tables shall be jointed (see e.g., Stolze, [0460]).
Du in view of Stolze does not specifically disclose the query plan comprising the set of plan fragments; and constructing a set of new inner join nodes. However, Nica teaches
the query plan comprising the set of plan fragments (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes. The plan nodes are used to generate the QOG); and
constructing a set of new inner join nodes (see e.g., [0072] for building of the Query Optimization Graph (QOG) for each query block and the main objects defined in the QOG and manipulated during optimization being "subplans" and "quantifiers", called plan nodes, [0092] for E being a set of directed and undirected hyperedges, there being several types of edges defined in a QOG, [0093] for Ej: an undirected edge (or join edge) among plan nodes, an undirected edge being represented as (U, p) where U is a subset of V, UV and p is a predicate referring to all quantifiers of U, and in other words, the schema of p and V having in common the quantifiers defined by U, and [0094] for Eo: directed edges (or outerjoin edges) being defined for each null-supplying subplan. Inner joins are represented by undirected edges connecting plan nodes.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to include the query plan comprising the set of plan fragments and constructing a set of new inner join nodes, as taught by Nica, for the benefit of building a Query Optimization Graph (QOG) (see e.g., Nica, [0068]).
Du and Stolze in view of Nica does not specifically disclose constructing a set of new join nodes as cartesian joins; and placing collected join keys and join filters as a filter node above a topmost join node. However, Adams teaches
constructing a set of new join nodes as cartesian joins (see e.g., col. 4, line 64 - col. 5, line 27 for with respect to query processing, it occurring that a join operator (also referred to as a join) in a query-execution plan includes a join predicate that itself contains a complex geospatial function such as ST_Contains, in the present disclosure, a join that includes such a join predicate being referred to as a geospatial-function join, and the corresponding join predicate being referred to as a geospatial-function predicate, in some current implementations of database platforms, in order to perform a geospatial-function join, an operation that is known as a cross join being performed, which involves generating what is referred to as the “Cartesian product” of the left-side relation and the right-side relation of the join, and the Cartesian product of a given left-side relation and a given right-side relation including rows that are every possible combination of one row from the given left-side relation and one row from the given right-side relation. A set of geospatial function join nodes is constructed as cartesian joins.); and
placing collected join keys [geography-data-object join keys] and join filters [complex geospatial function] as a filter node above a topmost join node [cartesian product] (see e.g., col. 4, line 64 - col. 5, line 27 for the two relevant geography data objects-referred to herein as the geography-data-object join keys, one originally from the given left-side relation and the other originally from the given right-side relation—from each and every row of this Cartesian product being then input into a filter that implements the complex geospatial function, and those rows for which the geospatial function returns TRUE are included in the output of this filter whereas those rows for which the geospatial function returns FALSE are not included in the output of this filter. The geography-data-object join keys and complex geospatial function are placed as a filter node above the cartesian product.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du and Stolze in view of Nica to construct a set of new join nodes as cartesian joins; and place collected join keys and join filters as a filter node above a topmost join node, as taught by Adams, for the benefit of performing a join predicate that contains a complex function (see e.g., Adams, col. 4, line 64 - col. 5, line 27).
As to claim 18, the limitations of parent claims 11-15 have been discussed above. Du in view of Stolze does not specifically disclose deriving a set of optimal join keys from a set of constructed nodes from the semantically equivalent intermediate plan. However, Nica teaches
deriving a set of optimal join keys from a set of constructed nodes [plan nodes, access methods, join methods] from the semantically equivalent intermediate plan [candidate plan segment] (see e.g., [0032] for candidate plan segments representing candidate plan nodes, access methods and join methods for inclusion in the access plans, the plan nodes representing subplans and quantifiers, and for each query block comprising an atomic portion of the query, determining an optimal access plan by performing the substeps of: placing a candidate plan segment in a partial access plan being generated for the query block; evaluating the partial access plan including the candidate plan segment; if the partial access plan is less favorable than a complete access plan previously identified for said query block, pruning said candidate plan segment; otherwise, adding an additional candidate plan segment to the partial access plan and repeating the above substeps until a complete access plan for the query block is generated, retaining a complete access plan if it is more favorable than other complete access plans previously generated for the query block; and otherwise pruning a complete access plan which is less favorable than other complete access plans, [0156] for the current partial access plan 620 being shown at the right hand side of FIG. 6, each pni being a plan node that belongs to the subplan and can represent another subplan or a quantifier, and a candidate access method of the plan node pnj being denoted as amj, while jmj represents a candidate join method that can be used to join pnj<amj> with the prefix of the plan, and [0159] for s2 = ({qt, qp}, O_OrderKey = L_Orderkey AND P_Type='%TIN%', . . . ), s1=({qo}, C_Custkey = O_Custkey, . . .), and s0=({qN, qC, s1, s2}, C_Nationkey = N_Nationkey AND C_Acctbal >700 AND N_Name = 'Egypt', . . . ). Optimal plan segments are derived from a set of plan nodes, access methods, and join methods from the candidate plan segments. Optimal plan segments include optimal join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du in view of Stolze to derive a set of optimal join keys from a set of constructed nodes from the semantically equivalent intermediate plan, as taught by Nica, for the benefit of enabling queries to be effectively optimized while requiring a minimal amount of memory for generating the search space and for storing the information required for query optimization (see e.g., Nica, [0023]).
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591), Stolze et al. (US Publication No. 2016/0119495), and Nica (US Publication No. 2004/0006561) in view of Adams et al. (US Patent No. 11,100,105) as applied to claims 5, 8, 15, and 18 above, and further in view of Bakulina et al. (US Publication No. 2019/0311059).
As to claim 9, the limitations of parent claims 1-5 and 8 have been discussed above. Du, Stolze, and Nica in view of Adams does not specifically disclose pushing at least one filter through join nodes. However, Bakulina teaches
pushing at least one filter through join nodes (see e.g., [0054] for the filter specified by the query being pushed down in the calculation scenario model from an upper request node to one of the join nodes).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du, Stolze, and Nica in view of Adams to push at least one filter through join nodes, as taught by Bakulina, for the benefit of reducing the amount of data to be joined to increase processing speeds and/or decrease required computational power (see e.g., Bakulina, [0059]).
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591), Stolze et al. (US Publication No. 2016/0119495), and Nica (US Publication No. 2004/0006561) in view of Adams et al. (US Patent No. 11,100,105) as applied to claims 5, 8, 15, and 18 above, and further in view of Yu et al. (US Publication No. 2025/0181584).
As to claim 10, the limitations of parent claims 1-5 and 8 have been discussed above. Du, Stolze, and Nica in view of Adams does not specifically disclose converting at least one filter conjunct to a set of join keys. However, Yu teaches
converting at least one filter conjunct [incoming filter] to a set of join keys [outgoing join keys] (see e.g., [0031] for when transferring a filter across edges that have different join keys, the filter being transformed, [0032] for when an incoming filter is received, an empty outgoing filter being created, columns for both incoming and outgoing join keys in the nation table 204 being scanned (e.g., assuming columnar store; otherwise, scan the entire table), inherent filters of nation table 204 being applied during the scan, for each row, the incoming join key being used to probe the incoming filter, if a match occurs, the outgoing join key being added to the outgoing filter, and at the end of the scan, the outgoing filter being sent to downstream tables (i.e., supplier table 208 and customer table 212), and [0034] for if one node has one or more incoming edges, the node collecting all the incoming filters before performing the transformation to produce outgoing filters. An incoming filter is transformed to outgoing join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du, Stolze, and Nica in view of Adams to convert at least one filter conjunct to a set of join keys, as taught by Yu, for the benefit of achieving the theoretically maximum filtering selectivity (see e.g., Yu, [0020]).
Claim 19 is rejected under 35 U.S.C. 103 as being unpatentable over Du et al. (US Patent No. 5,694,591), Stolze et al. (US Publication No. 2016/0119495), and Nica (US Publication No. 2004/0006561) in view of Adams et al. (US Patent No. 11,100,105) as applied to claims 5, 8, 15, and 18 above, and further in view of Bakulina et al. (US Publication No. 2019/0311059) and Yu et al. (US Publication No. 2025/0181584).
As to claim 19, the limitations of parent claims 11-15 and 18 have been discussed above. Du, Stolze, and Nica in view of Adams does not specifically disclose pushing at least one filter through join nodes. However, Bakulina teaches
pushing at least one filter through join nodes (see e.g., [0054] for the filter specified by the query being pushed down in the calculation scenario model from an upper request node to one of the join nodes).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du, Stolze, and Nica in view of Adams to push at least one filter through join nodes, as taught by Bakulina, for the benefit of reducing the amount of data to be joined to increase processing speeds and/or decrease required computational power (see e.g., Bakulina, [0059]).
Du, Stolze, Nica, and Adams in view of Bakulina does not specifically disclose converting at least one filter conjunct to a set of join keys. However, Yu teaches
converting at least one filter conjunct [incoming filter] to a set of join keys [outgoing join keys] (see e.g., [0031] for when transferring a filter across edges that have different join keys, the filter being transformed, [0032] for when an incoming filter is received, an empty outgoing filter being created, columns for both incoming and outgoing join keys in the nation table 204 being scanned (e.g., assuming columnar store; otherwise, scan the entire table), inherent filters of nation table 204 being applied during the scan, for each row, the incoming join key being used to probe the incoming filter, if a match occurs, the outgoing join key being added to the outgoing filter, and at the end of the scan, the outgoing filter being sent to downstream tables (i.e., supplier table 208 and customer table 212), and [0034] for if one node has one or more incoming edges, the node collecting all the incoming filters before performing the transformation to produce outgoing filters. An incoming filter is transformed to outgoing join keys.).
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to modify the database management system of Du, Stolze, Nica, and Adams in view of Bakulina to convert at least one filter conjunct to a set of join keys, as taught by Yu, for the benefit of achieving the theoretically maximum filtering selectivity (see e.g., Yu, [0020]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Ahmed (US Publication No. 2009/0112793) for “transforming a query to simulate a bushy tree execution plan for queries containing joins in series” (see abstract).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DARA J GLASSER whose telephone number is (571)270-3666. The examiner can normally be reached Monday-Thursday, 10:00am-2:00pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Apu Mofiz can be reached at (571)272-4080. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
07-28-2026
/DARA J GLASSER/Examiner, Art Unit 2161
/APU M MOFIZ/Supervisory Patent Examiner, Art Unit 2161
Prosecution Insights