Optimizing database queries using reusable subqueries

• US 9,582,539 B1
• Filed: 03/13/2013
• Issued: 02/28/2017
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Paraccel Incorporated (Actian Corporation)
• Original Assignee: Paraccel Incorporated (Actian Corporation)
• Inventors: Cole, Richard L., Chen, Yijou, McKenna, William J., Perfilov, Sergei, Sinha, Aman, Szedenits, Eugene Jr.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): May, Robert F
• Application Number:
  US13/799,051
• Time in Patent Office: 1,448 Days
• Field of Search: 707/718, 707/999.004
• US Class Current: 1/1
• 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 database queries, the method comprising:

receiving, by a database system, a database query for optimization, the database query comprising a first subquery and a second subquery, the first subquery specifying a first where clause comprising a first condition and the second subquery specifying a second where clause comprising a second condition, wherein the first where clause is distinct from the second where clause and wherein the first condition evaluates to true for a first set of input rows and the second condition evaluates to true for a second set of input rows;

comparing the first subquery and the second subquery based on input tables processed by each of the first and second subqueries;

responsive to determining that the first subquery and the second subquery match based on the comparison;

generating a first database query specifying a where clause comprising a condition that evaluates to true for a superset of the first set of input rows and the second set of input rows;

generating a statement comprising the first database query, the statement storing result of execution of the first database query in a result table;

generating a first expression equivalent to the first subquery and a second expression equivalent to the second subquery, the first and the second expressions based on the result table;

modifying the database query to use the result table, the modifying comprising, replacing the first subquery with the first expression and the second subquery with the second expression; and

replacing an execution of the database query with an execution of the statement followed by an execution of the modified database query.

2. The method of claim 1, wherein the first subquery returns a first set of columns and the second subquery returns a second set of columns, wherein the first database query returns a union of the first and second set of columns.

3. The method of claim 1, wherein the first subquery includes a group by clause based on a first set of columns and the second subquery includes a group by clause based on a second set of columns, wherein generating the statement comprises:

determining a union of the first set of columns and the second set of columns; and

adding a group by clause to the first database query to group the result of the first database query by the union of the first and second set of columns.

4. The method of claim 3, wherein the first expression is a query with the result table as input and a group by clause based on the first set of columns and the second expression is a query with the result table as input and a group by clause based on the second set of columns.

5. The method of claim 1, wherein the first expression is a query with the result table as input and the first where clause and the second expression is a query with the result table as input and the second where clause.

6. The method of claim 1, wherein the first subquery specifies an order by clause and the second subquery also specifies the order by clause, wherein generating the statement comprises generating a query having the order by clause.

7. The method of claim 1, further comprising:

identifying a third subquery matching a fourth subquery;

determining that the result of the third subquery is consumed by the first subquery and the result of the fourth subquery is consumed by the second subquery; and

responsive to determining that the result of the third subquery is consumed by the first subquery and the result of the fourth subquery is consumed by the second subquery, excluding the third subquery and the fourth subquery from subqueries rewritten using reusable queries.

8. The method of claim 1, further comprising:

performing statistical analysis of the result table to determine statistical information describing the result table; and

using the statistical information of the result table to optimize the database query execution.

9. The method of claim 1, wherein the database system is a parallel system, further comprising:

specifying a distribution of the result table based on a distribution of input tables of the database query.

10. A non-transitory computer-readable 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 a database query for optimization, the database query comprising a first subquery and a second subquery, the first subquery specifying a first where clause comprising a first condition and the second subquery specifying a second where clause comprising a second condition, wherein the first where clause is distinct from the second where clause and wherein the first condition evaluates to true for a first set of input rows and the second condition evaluates to true for a second set of input rows;

compare the first subquery and the second subquery based on input tables processed by each of the first and second subqueries;

responsive to determining that the first subquery and the second subquery match based on the comparison;

generate a first database query specifying a where clause comprising a condition that evaluates to true for a superset of the first set of input rows and the second set of input rows;

generate a statement comprising the first database query, the statement storing result of execution of the first database query in a result table;

generate a first expression equivalent to the first subquery and a second expression equivalent to the second subquery, the first and the second expressions based on the result table;

modify the database query to use the result table, the modifying comprising, replacing the first subquery with the first expression and the second subquery with the second expression; and

replace an execution of the database query with an execution of the statement followed by an execution of the modified database query.

11. The computer-readable storage medium of claim 10, wherein the first subquery returns a first set of columns and the second subquery returns a second set of columns, wherein the first database query returns a union of the first and second set of columns.

12. The computer-readable storage medium of claim 10, wherein the first subquery includes a group by clause based on a first set of columns and the second subquery includes a group by clause based on a second set of columns, wherein generating the statement comprises:

determining a union of the first set of columns and the second set of columns; and

adding a group by clause to a query of the statement to group the result of the query by the union of the first and second set of columns.

16. The non-transitory computer-readable storage medium of claim 10, wherein the first expression is a query with the result table as input and the first where clause and the second expression is a query with the result table as input and the second where clause.

17. The non-transitory computer-readable storage medium of claim 10, wherein the first subquery specifies an order by clause and the second subquery also specifies the order by clause, wherein generating the statement comprises generating a query having the order by clause.

18. The non-transitory computer-readable storage medium of claim 10, the code further causing the processor to:

identify a third subquery matching a fourth subquery;

determine that the result of the third subquery is consumed by the first subquery and the result of the fourth subquery is consumed by the second subquery; and

responsive to determining that the result of the third subquery is consumed by the first subquery and the result of the fourth subquery is consumed by the second subquery, exclude the third subquery and the fourth subquery from subqueries rewritten using reusable queries.

19. The non-transitory computer-readable storage medium of claim 10, the code further causing the processor to:

perform statistical analysis of the result table to determine statistical information describing the result table; and

use the statistical information of the result table to optimize the database query execution.

20. The non-transitory computer-readable storage medium of claim 10, the code further causing the processor to:

specify a distribution of the result table based on a distribution of input tables of the database query.

13. A computer-implemented system for optimizing queries, the system comprising:

a computer processor; and

a non-transitory computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising;

an optimizer module configured to;

receive a database query for optimization, the database query comprising a first subquery and a second subquery, the first subquery specifying a first where clause comprising a first condition and the second subquery specifying a second where clause comprising a second condition, wherein the first where clause is distinct from the second where clause and wherein the first condition evaluates to true for a first set of input rows and the second condition evaluates to true for a second set of input rows;

compare the first subquery and the second subquery based on input tables processed by each of the first and second subqueries;

responsive to determining that the first subquery and the second subquery match based on the comparison;

generate a first database query specifying a where clause comprising a condition that evaluates to true for a superset of the first set of input rows and the second set of input rows;

generate a statement comprising the first database query, the statement storing result of execution of the first database query in a result table;

generate a first expression equivalent to the first subquery and a second expression equivalent to the second subquery, the first and the second expressions based on the result table;

modify the database query to use the result table, the modifying comprising, replacing the first subquery with the first expression and the second subquery with the second expression; and

replace an execution of the database query with an execution of the statement followed by an execution of the modified database query.

14. The computer-implemented system of claim 13, wherein the first subquery returns a first set of columns and the second subquery returns a second set of columns, wherein the first database query returns a union of the first and second set of columns.

15. The computer-implemented system of claim 13, wherein the first subquery includes a group by clause based on a first set of columns and the second subquery includes a group by clause based on a second set of columns, wherein generating the statement comprises:

determining a union of the first set of columns and the second set of columns; and

adding a group by clause to a query of the statement to group the result of the query by the union of the first and second set of columns.