Optimizing database queries using subquery composition

• US 9,665,619 B1
• Filed: 09/18/2015
• Issued: 05/30/2017
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Paraccel Incorporated (Actian Corporation)
• Original Assignee: Actian Corporation
• Inventors: Szedenits, Jr., Eugene, Cole, Richard L., Chen, Yijou, McKenna, William J., Sinha, Aman, Perfilov, Sergei
• Primary Examiner(s): Rostami, Mohammad S
• Assistant Examiner(s): May, Robert F
• Application Number:
  US14/858,957
• Time in Patent Office: 620 Days
• Field of Search: 707718
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24535 of sub-queries or views

Abstract

A database system optimizes database queries that comprise subqueries. The database system factors out computation from two or more subqueries to a reusable subquery. The reusable subquery returns a result set. The subqueries are rewritten to use the result set and the database query modified to use the rewritten subqueries. The modified database query performs efficiently since the result set is computed only once for each subquery that uses the reusable query. The database system also composes nested subqueries that compute aggregate values. The database system identifies an inner subquery nested within an outer subquery, each subquery computing an aggregate value. The database system determines a new aggregate function corresponding to a composition of aggregate functions of the inner and the outer queries. The database system determines a composed query using the inner query with the outer query. The composed query uses the new aggregate function.

Claims

1. A computer implemented method for optimizing a database queries, the method comprising:

Receiving, by a database system, a request to optimize a database query, the database query configured to process a plurality of records of a database table stored in the database system

Identifying an inner subquery and an outer subquery in the database query, the inner subquery nested within the outer subquery, wherein each of the inner subquery and the out subquery specifies one or more expression representing results of the subquery;

Identifying an inner aggregate function in the one or more expressions representing results of the inner subquery and an outer aggregate function in the one or more expressions representing results of the outer subquery, wherein each aggregate function receives a plurality of input values and determines a numeric results by aggregating the plurality of input values;

Determining if the result of the inner aggregate function is provided as an input to the outer aggregate function;

Selecting a new aggregate function based on the inner aggregate function and the outer aggregate function if the result of the inner aggregate function is determined to be provided as an input to the outer aggregate function

Generating a combined database query based on the outer subquery and the inner subquery, the combined database query specifying the new aggregate function; and

Storing the combined database query.

2. The method of claim 1, further comprising:

maintaining a mapping table from a first aggregate function and a second aggregate function to a third aggregate function; and

wherein determining the new aggregate function comprises looking up the mapping table.

3. The method of claim 1, further comprising:

determining that the inner aggregate function determines sum of input values;

determining that the outer aggregate function determines count of input values; and

responsive to determining that the inner aggregate function determines a sum of values and the outer aggregate function determines a count of values, selecting the new aggregate function that determines a count of input values.

4. The method of claim 1, further comprising:

determining that the inner aggregate function determines sum of input values;

determining that the outer aggregate function determines sum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a sum of values, selecting the new aggregate function that determines sum of input values.

5. The method of claim 1

determining that the inner aggregate function determines maximum of input values;

determining that the outer aggregate function determines maximum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a maximum of values, selecting the new aggregate function that determines maximum of input values.

6. The method of claim 1,

determining that the inner aggregate function determines minimum of input values;

determining that the outer aggregate function determines minimum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a minimum of values, selecting the new aggregate function that determines minimum of input values.

7. The method of claim 1, further comprising:

responsive to determining that at least one of the inner subquery or the outer subquery specifies a distinct clause, determining that the inner subquery and the outer subquery cannot be composed.

8. A non-transitory computer-readable storage medium storing instructions for:

Receiving, by a database system, a request to optimize a database query, the database query configured to process a plurality of records of a database table stored in the database system;

identifying an inner subquery and an outer subquery in the database query, the inner subquery nested within the outer subquery, wherein each of the inner subquery and the outer subquery specifies one or more expressions representing results of the subquery;

identifying an inner aggregate function in the one or more expressions representing results of the inner subquery and an outer aggregate function in the one or more expressions representing results of the outer subquery, wherein each aggregate function receives a plurality of input values and determines a numeric result by aggregating the plurality of input values;

determining if the result of the inner aggregate function is provided as an input to the outer aggregate function;

selecting a new aggregate function based on the inner aggregate function and the outer aggregate function if the result of the inner aggregate function is determined to be provided as an input to the outer aggregate function;

generating a combined database query based on the outer subquery and the inner subquery, the combined database query specifying the new aggregate function; and

storing the combined database query.

9. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

maintaining a mapping table from a first aggregate function and a second aggregate function to a third aggregate function; and

wherein determining the new aggregate function comprises looking up the mapping table.

10. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

determining that the inner aggregate function determines sum of input values;

determining that the outer aggregate function determines count of input values; and

responsive to determining that the inner aggregate function determines a sum of values and the outer aggregate function determines a count of values, selecting the new aggregate function that determines a count of input values.

11. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

determining that the inner aggregate function determines sum of input values;

determining that the outer aggregate function determines sum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a sum of values, selecting the new aggregate function that determines sum of input values.

12. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

determining that the inner aggregate function determines maximum of input values;

determining that the outer aggregate function determines maximum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a maximum of values, selecting the new aggregate function that determines maximum of input values.

13. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

determining that the inner aggregate function determines minimum of input values;

determining that the outer aggregate function determines minimum of input values; and

responsive to determining that both the inner aggregate function and the outer aggregate function determine a minimum of values, selecting the new aggregate function that determines minimum of input values.

14. The non-transitory computer-readable storage medium of claim 8, further storing instructions for:

responsive to determining that at least one of the inner subquery or the outer subquery specifies a distinct clause, determining that the inner subquery and the outer subquery cannot be composed.

15. A computer-implemented system, comprising:

a computer processor; and

a non-transitory computer-readable storage medium storing instructions for;

receiving, by a database system, a request to optimize a database query, the database query configured to process a plurality of records of a database table stored in the database system;

identifying an inner subquery and an outer subquery in the database query, the inner subquery nested within the outer subquery, wherein each of the inner subquery and the outer subquery specifies one or more expressions representing results of the subquery;

identifying an inner aggregate function in the one or more expressions representing results of the inner subquery and an outer aggregate function in the one or more expressions representing results of the outer subquery, wherein each aggregate function receives a plurality of input values and determines a numeric result by aggregating the plurality of input values;

determining if the result of the inner aggregate function is provided as an input to the outer aggregate function;

selecting a new aggregate function based on the inner aggregate function and the outer aggregate function if the result of the inner aggregate function is determined to be provided as an input to the outer aggregate function;

generating a combined database query based on the outer subquery and the inner subquery, the combined database query specifying the new aggregate function; and

storing the combined database query.

16. The computer-implemented system of claim 15, wherein the non-transitory computer-readable storage medium further stores instructions for:

maintaining a mapping table from a first aggregate function and a second aggregate function to a third aggregate function; and

wherein determining the new aggregate function comprises looking up the mapping table.

17. The computer-implemented system of claim 15, wherein the non-transitory computer-readable storage medium further stores instructions for:

determining that the inner aggregate function determines sum of input values;

determining that the outer aggregate function determines count of input values; and

responsive to determining that the inner aggregate function determines a sum of values and the outer aggregate function determines a count of values, selecting the new aggregate function that determines a count of input values.

18. A computer-readable non-transitory storage medium storing computer-executable code for optimizing queries of a database system, the code, when executed by a processor, causing the processor to:

receive, by a database system, a request to optimize a database query;

identify an inner subquery and an outer subquery in the database query, the inner subquery nested within the outer subquery;

determine that the inner subquery specifies a first where clause that computes a first set of values;

determine that the outer subquery specifies a second where clause that computes a second set of values;

compare the first set of values with the second set of values; and

determine that the second set of values is a subset of the first set of values;

determine whether a result of the inner subquery is provided as an input to the outer subquery;

generate a combined database query corresponding to a composition of the outer subquery and the inner subquery if the result of the inner subquery is determined to be an input to the outer subquery and the second set of values is determined to be a subset of the first set of values, the combined database query having the second where clause; and

store the combined database query.

19. The computer-readable non-transitory storage medium of claim 18, wherein the code further causes the processor to:

identify an inner aggregate function specified in the inner subquery and an outer aggregate function specified in the outer subquery;

determine whether a result of the inner aggregate function is provided as an input to the outer aggregate function;

responsive to determining that the result of the inner aggregate function is provided as the input to the outer aggregate function, determine a new aggregate function corresponding to a composition of the inner aggregate function and the outer aggregate function; and

wherein the combined database query specifies the new aggregate function.

20. The computer-readable non-transitory storage medium of claim 19, wherein the code further causes the processor to:

maintain a mapping table from a first type of aggregate function and a second type of aggregate function to a type of composed aggregate function obtained by composing an aggregate function of the first type with an aggregate function of the second type; and

wherein determining the new aggregate function comprises looking up the mapping table.