Push down optimization in a distributed, multi-database system

Claim 2

In a heterogeneous, distributed database system having a plurality of database instances, a computer-based method of optimizing performance of the database system by determining whether a query can be pushed down to a single database instance, comprising the steps of: (1) evaluating the query for data coverage by determining whether all data referenced in the query is located within a single database instance; (2) evaluating the query for capability coverage by determining whether all capabilities referenced in the query can be performed by said single database instance; and (3) pushing down the query to the single database instance if said data coverage and said capability coverage are satisfied.

Claim 3

The method of claim 1, further comprising the step of receiving the query from a host computer that permits a user to access data in the heterogeneous, distributed database system using Structured Query Language (SQL).

Claim 4

The method of claim 2, further comprising the step of performing steps (1) through (3) on subqueries within the query.

Claim 5

A computer-based method for optimizing performance of a heterogeneous, distributed database system comprising a plurality of heterogeneous database instances, wherein data associated with a client is distributed among said heterogeneous database instances, comprising the steps of: (1) receiving a query from a host computer, wherein said query has one or more subqueries contained therein; (2) evaluating said query bottom-up to determine whether each of said one or more subqueries satisfies a data coverage criteria and a capability coverage criteria, wherein said data coverage criteria requires all data referenced in a particular subquery to be located within a single database instance and said capability coverage criteria requires that said single database instance perform all capabilities referenced in said particular subquery; (3) marking said one or more subqueries as push down-able if said data coverage criteria and said capability coverage criteria are satisfied; and (4) evaluating said query top-down to determine which subqueries have been marked by step (3) in order to determine whether said query in its entirety or said one or more subqueries can be pushed down to said single database instance, whereby said top down evaluation of said query ensures that the highest push down-able ancestor subquery will get pushed down together with all enclosed push down-able subqueries.

Claim 6

A computer-based method for optimizing performance of a heterogeneous, distributed database system comprising a plurality of heterogeneous database instances, wherein data associated with a client is distributed among said heterogeneous database instances, comprising the steps of: (1) receiving a query from a host computer, wherein said query has one or more subqueries contained therein; (2) evaluating said query bottom-up to determine whether each of said one or more subqueries satisfies a data coverage criteria and a capability coverage criteria, wherein said data coverage criteria requires all data referenced in a particular subquery to be located within a single database instance and said capability coverage criteria requires that said single database instance perform all capabilities referenced in said particular subquery; (3) marking said one or more subqueries as push down-able if said data coverage criteria and said capability coverage criteria are satisfied; and (4) evaluating said query top-down to determine which subqueries have been marked by step (3) in order to determine whether said query in its entirety or said one or more subqueries can be pushed down to said single database instance, whereby said top down evaluation of said query ensures that the highest push down-able ancestor subquery will get pushed down together with all enclosed push down-able subqueries.

Claim 7

The method of claim 4, further comprising the step of generating a set of execution commands to be forwarded to the heterogeneous, distributed database system, wherein said set of execution commands include a first subset of commands directed to said query or said one or more subqueries that can be pushed down and a second subset of commands directed to said one or more subqueries that cannot be pushed down.

Claim 8

The method of claim 4, further comprising the step of decomposing said one or more subqueries that cannot be pushed down into manageable execution commands that can be executed by said plurality of heterogeneous database instances.

Claim 9

A computer-based system for optimizing performance of a heterogeneous, distributed database system, comprising: a plurality of heterogeneous database management systems, wherein data associated with a client is distributed among said heterogeneous database management systems; an interface module configured to receive a query from a host computer and to translate said query for transfer to said heterogeneous database management systems, said query having one or more subqueries contained therein, wherein said interface module is configured to provide a host computer with transparent access to the heterogeneous database management systems, said interface module comprising, means for performing a bottom-up evaluation of said query to determine whether each of said one or more subqueries satisfies a data coverage criteria and a capability coverage criteria, wherein said data coverage criteria requires all data referenced in a particular subquery to be located within a single database instance and said capability coverage criteria requires that said single database instance perform all capabilities referenced in said particular subquery; means for marking said one or more subqueries as push down-able if said data coverage and said capability coverage are satisfied; and means for performing a top-down evaluation of said query to determine which subqueries have been marked push down-able in order to determine whether said query in its entirety or said one or more subqueries can be pushed down to said single database instance, whereby said top down evaluation of said query ensures that the highest push down-able ancestor subquery will get pushed down together with all enclosed push down-able subqueries.

Claim 10

A computer-based system for optimizing performance of a heterogeneous, distributed database system, comprising: a plurality of heterogeneous database management systems, wherein data associated with a client is distributed among said heterogeneous database management systems; an interface module configured to receive a query from a host computer and to translate said query for transfer to said heterogeneous database management systems, said query having one or more subqueries contained therein, wherein said interface module is configured to provide a host computer with transparent access to the heterogeneous database management systems, said interface module comprising, means for performing a bottom-up evaluation of said query to determine whether each of said one or more subqueries satisfies a data coverage criteria and a capability coverage criteria, wherein said data coverage criteria requires all data referenced in a particular subquery to be located within a single database instance and said capability coverage criteria requires that said single database instance perform all capabilities referenced in said particular subquery; means for marking said one or more subqueries as push down-able if said data coverage and said capability coverage are satisfied; and means for performing a top-down evaluation of said query to determine which subqueries have been marked push down-able in order to determine whether said query in its entirety or said one or more subqueries can be pushed down to said single database instance, whereby said top down evaluation of said query ensures that the highest push down-able ancestor subquery will get pushed down together with all enclosed push down-able subqueries.