Database system with methods for optimizing performance of correlated subqueries by reusing invariant results of operator tree

• US 6,341,281 B1
• Filed: 04/02/1999
• Issued: 01/22/2002
• Est. Priority Date: 04/14/1998
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: MacNicol, Roger Dermot, Bello, Randall George, Yang, Katherine Tsouya, Rao, Jun, Kirk, Steven A.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/285,408
• Time in Patent Office: 1,026 Days
• Field of Search: 707/1-10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Database system and methods are described for improving execution speed of database queries (e.g., for decision support) by optimizing execution of nested queries or “subqueries,” which are commonly used in client/server database environments. In particular, the basic approach employed is to recognize the part of the subquery that is not related to the outer references and cache the result of that part after its first execution. Later, the result can be reused and combined with the result of the rest of the subquery that is changing for each iteration. Methods are employed to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. An efficient method is used to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. When query rewriting is not possible, therefore, the invariant technique provides significantly better performance than the traditional nested iteration method.

Claims

1. In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising database tables, each table comprising rows of data records, each data record storing information in database columns, a method for executing a correlated database query for selecting particular ones of said data records, the method comprising:

(a) receiving a database query specifying selection of particular ones of said data records, said database query comprising inner and outer query blocks, said inner query block comprising a subquery nested within the database query, wherein said at least one subquery references information from said outer query block;

(b) determining at least one correlated part and at least one uncorrelated part of said subquery, wherein only said correlated part is capable of being affected by changing values of the outer query block during execution of the database query;

(c) creating a cache in said memory for at least storing a result computed for said uncorrelated part after said subquery has been executed for the first time; and

(d) executing said database query, including evaluating said expression of the subquery by;

(i) computing a result for the correlated part of said subquery,

(ii) retrieving the cached result for the uncorrelated part of said subquery, and

(iii) computing a value for said subquery by combining said computed result with said retrieved cached result.

2. The method of claim 1, wherein said database query comprises a Structured Query Language (SQL) command.

3. The method of claim 2, wherein said SQL command specifies selection of particular ones of said data records according to data records satisfying an SQL “

WHERE”

clause.

4. The method of claim 3, wherein said subquery expression is nested within said SQL “

WHERE”

clause of said SQL command.

5. The method of claim 1, wherein said correlated part is computed for each database record being scanned during query execution.

6. The method of claim 1, wherein said uncorrelated part is computed only once during query execution.

7. The method of claim 1, wherein said outer block includes host variables, for receiving information provided in conjunction with the database query.

8. The method of claim 1, wherein said database query is executed using a query plan comprising a data flow tree of operators, where each operator is represented as a node of the tree, and wherein said determining correlated and uncorrelated parts of said subquery includes marking each node as variant or invariant, accordingly.

9. The method of claim 8, wherein each node marked as invariant is without any reference to the outer block.

10. The method of claim 8, wherein each node marked as variant includes at least one reference to the outer block.

11. The method of claim 1, wherein said database query comprises a non-rewriteable correlated query.

12. The method of claim 1, wherein said database query comprises a rewriteable correlated query.

13. The method of claim 12, wherein said method first determines from a cost estimate calculation whether query execution should instead be optimized by rewriting the database query.

14. The method of claim 1, wherein said database query comprises a Decision Support System (DSS) type query.

15. The method of claim 1, wherein said database query comprises a join query, specifying a join operation of two or more database tables.

16. In a database system comprising a processor, a memory, and a storage device, said storage device storing a database comprising database tables, each table comprising rows of data records, each data record storing information in database columns, an improved query execution system comprising:

means for receiving a database query having an expression that includes a subquery nested within the database query, said subquery itself comprising an expression specifying a subquery result which is determined before evaluation of the expression for the database query is completed, wherein said subquery includes a variant portion that is dependent upon at least one value computed from a portion of the database query outside said subquery;

a cache in said memory for storing a result computed for an invariant portion of the subquery, wherein said invariant portion is not dependent upon computation of values from a portion of the database query outside said subquery;

means for executing said database query, including means for evaluating said expression of the subquery by;

(i) computing a result for the variant portion of said subquery,

(ii) retrieving the cached result for the invariant portion of said subquery, and

(ii) computing a value for said expression of the subquery by combining said computed result with said retrieved cached result.

17. The system of claim 16, wherein said database query comprises a Structured Query Language (SQL) command.

18. The system of claim 17, wherein said SQL command specifies selection of particular ones of said data records according to data records satisfying an SQL “

WHERE”

clause.

19. The system of claim 18, wherein said subquery expression is nested within said SQL “

WHERE”

clause of said SQL command.

20. The system of claim 16, wherein said variant portion is computed for each database record being scanned.

21. The system of claim 16, wherein said invariant portion is computed only once during query execution.

22. The system of claim 16, wherein said outer block includes host variables, for receiving information provided in conjunction with said database query.

23. The system of claim 16, wherein said database query is executed using a query plan comprising a data flow tree of operators, where each operator is represented as a node of the tree, and wherein said system marks each node for said subquery as variant or invariant, accordingly.

24. The system of claim 23, wherein each node marked as invariant cannot include a reference to the outer block.

25. The system of claim 23, wherein each node marked as variant includes at least one reference to the outer block.

26. The system of claim 16, wherein said database query comprises a non-rewriteable correlated query.

27. The system of claim 16, wherein said database query comprises a rewriteable correlated query.

28. The system of claim 27, wherein said system first determines from a cost estimate calculation whether query execution may be optimized without rewriting the database query.

29. The system of claim 16, wherein said database query comprises a Decision Support System (DSS) query.

30. The system of claim 16, wherein said database query comprises a join query, specifying a join operation of two or more database tables.

31. In a client/server database system, an improved method for executing a query submitted by a client to a database server, said query including a subquery having variant and invariant portions, the method comprising:

dividing the subquery into variant and invariant portions;

creating a cache for caching an intermediate result computed from the portion of the subquery that is invariant from one iteration of the query to another;

executing the query for providing a query result to the client; and

while executing the query, computing a query result at least in part by retrieving said intermediate result for the invariant portion from said cache and combining it with a result computed from said variant portion of said subquery.

32. The method of claim 31, wherein said variant portion is computed for each database record being scanned during execution of said query.

33. The method of claim 31, wherein said invariant portion is computed only once during query execution.

34. The method of claim 31, wherein said variant portion references an outer block of said database query.

35. The method of claim 31, wherein said database query is executed using a query plan comprising a data flow tree of operators, where each operator is represented as a node of the tree, and wherein each node for said subquery is marked as variant or invariant, accordingly.