Query Optimizer

• US 20080033914A1
• Filed: 08/02/2006
• Published: 02/07/2008
• Est. Priority Date: 08/02/2006
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lawande, Shilpa, Cherniack, Mitch, Tran, Nga
• Granted Patent: US 8,671,091 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

For a database query that defines a plurality of separate snowflake schemas, a query optimizer computes separately for each of the snowflake schemas a logical access plan for obtaining from that schema'"'"'s tables a respective record set that includes the data requested from those tables by that query. The query optimizer also computes a logical access plan for obtaining the query'"'"'s results from the record sets in which execution of the logical access plans thus computed will result.

Claims

1. For employing a computer system to execute a query on a database, a method comprising:

A) providing inputs to the computer system that represent a query that, applied to the database, defines a plurality of independent snowflake schemas; and

B) employing the computer system to;

i) compute, separately for each of the snowflake schemas, an access plan for obtaining from that schema'"'"'s tables a record set that includes the data requested by the query from those tables;

ii) compute an access plan for obtaining the query'"'"'s results from the record sets in which execution of the access plans thus computed will result;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output that represents the query results thus obtained.

2. A method as defined by claim 1 wherein, for at least one said independent snowflake schema, the access plan computed for that independent snowflake schema is computed by computing, separately for each table whose snowflake degree in that independent snowflake schema exceeds zero, a respective access plan for obtaining a record set that includes the data requested by the query from that table and the tables reachable therefrom, that access plan being computed by treating that table as the fact table of a star schema and treating as a dimension table of that star schema:

A) any snowflake-degree-zero table directly reachable from that table; and

B) any record set that will result from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from that table.

3. A method as defined in claim 1 wherein the database is a column store.

4. For executing a queries on a database, a computer system configured to:

A) maintain a database;

B) accept input signals that represent a query that, applied to the database, defines a plurality of independent snowflake schemas; and

C) in response thereto;

i) compute, separately for each of the snowflake schemas, an access plan for obtaining from that schema'"'"'s tables a record set that includes the data requested by the query from those tables;

ii) compute an access plan for obtaining the query'"'"'s results from the record sets in which execution of the access plans thus computed will result;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output that represents the query results thus obtained.

5. A computer system as defined in claim 4 wherein, for at least one said independent snowflake schema, the access plan computed for that independent snowflake schema is computed by computing, separately for each table whose snowflake degree in that independent snowflake schema exceeds zero, a respective access plan for obtaining a record set that includes the data requested by the query from that table and the tables reachable therefrom, that access plan being computed by treating that table as the fact table of a star schema and treating as a dimension table of that star schema:

A) any snowflake-degree-zero table directly reachable from that table; and

B) any record set that will result from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from that table.

6. A computer system as defined in claim 4 wherein the database is a column store.

7. A storage medium containing machine instruction readable by a computer system to configure the computer system to:

A) maintain a database;

B) accept input signals that represent a query that, applied to the database, defines a plurality of independent snowflake schemas; and

C) in response thereto;

i) compute, separately for each of the snowflake schemas, an access plan for obtaining from that schema'"'"'s tables a record set that includes the data requested by the query from those tables;

ii) compute an access plan for obtaining the query'"'"'s results from the record sets in which execution of the access plans thus computed will result;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output that represents the query results thus obtained.

8. A storage medium as defined in claim 7 wherein, for at least one said independent snowflake schema, the access plan computed for that independent snowflake schema is computed by computing, separately for each table whose snowflake degree in that independent snowflake schema exceeds zero, a respective access plan for obtaining a record set that includes the data requested by the query from that table and the tables reachable therefrom, that access plan being computed by treating that table as the fact table of a star schema and treating as a dimension table of that star schema:

A) any snowflake-degree-zero table directly reachable from that table; and

B) any record set that will result from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from that table.

9. A storage medium as defined in claim 7 wherein the database is a column store.

10. For employing a computer system to execute a query on a database that contains a plurality of base tables that have primary-key/foreign-key relationships, a method comprising:

A) providing input signals to the computer system that represent a query to be applied to the database; and

B) employing the computer system to;

i) choose a set of access plans in accordance with the primary-key/foreign-key relationships among tables in the query;

ii) select an access plan from among the chosen access plans in accordance with predetermined selection criteria;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output indicative of the query results thus obtained.

11. For executing queries on a database, a computer system configured to:

A) maintain a database that contains a plurality of tables that have primary-key/foreign-key relationships among them;

B) accept input signals that represent a query; and

C) in response thereto;

i) choose a set of access plans in accordance with the primary-key/foreign-key relationships among tables in the query;

ii) select an access plan from among the chosen access plans in accordance with predetermined selection criteria;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output indicative of the query results thus obtained.

12. A storage medium containing machine instruction readable by a computer system to configure the computer system to:

A) maintain a database that contains a plurality of tables that have primary-key/foreign-key relationships among them;

B) accept input signals that represent a query; and

C) in response thereto;

i) choose a set of access plans in accordance with the primary-key/foreign-key relationships among tables in the query;

ii) select an access plan from among the chosen access plans in accordance with predetermined selection criteria;

iii) obtain the query'"'"'s results by executing the access plan; and

iv) generate an output indicative of the query results thus obtained.