Estimating the compilation time of a query optimizer

• US 7,356,526 B2
• Filed: 09/30/2003
• Issued: 04/08/2008
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ilyas, Ihab F., Lohman, Guy Maring, Gao, Dengfeng, Lin, Eileen Tien, Rao, Jun
• Primary Examiner(s): Alam; Shahid
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US10/673,433
• Publication Number:
  US 20050071331A1
• Time in Patent Office: 1,652 Days
• Field of Search: 707/3, 707/4, 707/5, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A compilation time estimator provides a quantified estimate of the optimizer compilation time for a given query optimizer. The estimator automates the optimizer to choose the right level of optimization in commercial database systems. The estimator reuses an optimizer'"'"'s join enumerator to obtain actual number of joins, but bypasses plan generation to save estimation overhead, and maintains a small number of interesting physical properties to estimate the number of plans by using a linear regression model. The estimator uses the number of generated plans to estimate query compilation time.

Claims

1. A computer-based method for estimating a query compilation time of a query optimizer, said computer-based method implemented in computer readable program code stored in computer memory, said computer-based method comprising the steps of:

(a) receiving a query;

(b) iterating through possible join pairs for said query;

(c) for each join pair, identifying a set of differentiating properties and using said identified set of differentiating properties to calculate number of join plans;

(d) estimating the compilation time from said calculated number of join plans for each type of join method, said compilation time estimated via running regression of the following model;

T=T_inst×

Σ

(C_t×

P_t)

wherein T is a machine-dependent parameter representing time per instruction, C_t is a constant representing number of instructions to generate a join plan of type t, and P_t is an estimated number of join plans of type t; and

(e) outputting the estimated compilation time.

2. A computer-based method as per claim 1, wherein said join pairs are iterated by reusing existing join enumerator in said query optimizer.

3. A computer-based method as per claim 1, wherein plan generation in said query optimizer is bypassed.

4. A computer-based method as per claim 1, wherein said set of differentiating properties comprises any of, or a combination of the following:

order, data partition, pipelineability, data source, and presence of expensive predicates.

5. A computer-based method as per claim 1, wherein said query is an SQL query.

6. A computer-based method as per claim 1, wherein said estimation is performed via a regression model.

7. A computer-based method as per claim 1, wherein said differentiating properties are generated in any of the following policies:

a lazy policy in which said differentiating properties are generated naturally or an eager policy in which said differentiating properties are forcibly generated via an optimizer.

8. A computer-based method as per claim 1, wherein compilation time for multiple optimization levels are estimated in a single pass.

9. A compilation time estimator (COTE) implemented in computer readable program code stored in computer memory, said COTE bypassing plan generation in a query optimizer and reusing a join enumerator to estimate compilation time of said query optimizer, said join enumerator iterating through possible join pairs for a query, and, for each join pair, said COTE identifying a set of differentiating properties and using said identified set of differentiating properties to calculate number of join plans, and estimating compilation time from said calculated and outputting number of join plans for each type of join method via a regression model as follows,

T=T_inst×

Σ

(C_t×

P_t)

wherein T is a machine-dependent parameter representing time per instruction, C_t is a constant representing number of instructions to generate a join plan of type t, and P_t is an estimated number of join plans of type t.

10. A compilation time estimator (COTE), as per claim 9, wherein said set of differentiating properties comprises any of, or a combination of the following:

order, data partition, pipelineability, data source, and presence of expensive predicates.

11. A compilation time estimator (COTE), as per claim 9, wherein said differentiating properties are generated in any of the following policies:

a lazy policy in which said differentiating properties are generated naturally or an eager policy in which said differentiating properties are forcibly generated via a optimizer.

12. A compilation time estimator (COTE), as per claim 9, wherein said number of join plans are calculated for any join type selected from a group consisting of:

nested loops join (NLJN), sort merge join (MGJN), and hash join (HSJN).

13. A compilation time estimator (COTE), as per claim 9, wherein said query is an SQL query.

14. A computer-based system for estimating query compilation time via reusing a join enumerator in a query optimizer, said system comprising:

(a) said system implemented in computer readable program stored in computer memory;

(b) an interface to receive a query;

(c) a join enumerator to iterate through possible join pairs for said query, said iteration performed via reusing said join enumerator in said query optimizer;

(d) a property identifier to identify, for each join pair, a set of differentiating properties and use said identified set of differentiating properties to calculate number of join plans; and

(e) a compilation time estimator to estimate and output compilation time from said calculated number of join plans for each type of join method, wherein said number of join plans are calculated for any join type selected from a group consisting of;

nested loops, sort merge, and hash, said compilation time is estimated via running regression of the following model;

T=T_inst×

Σ

(C_t×

P_t)

wherein T is a machine-dependent parameter representing time per instruction, C_t is a constant representing number of instructions to generate a join plan of type t, and P_t is an estimated number of join plans of type t.

15. A computer-based system as per claim 14, wherein said set of differentiating properties comprises any of, or a combination of the following:

order, data partition, pipelineability, data source, and presence of expensive predicates.

16. A computer-based system as per claim 14, wherein said compilation time estimator uses a regression model to estimate said compilation time.

17. A computer-based system as per claim 14, wherein said differentiating properties are generated in any of the following policies:

a lazy policy in which said differentiating properties are generated naturally or an eager policy in which said differentiating properties are forcibly generated via a optimizer.

18. A computer-based system as per claim 14, wherein said query is an SQL query.

19. An article of manufacture comprising computer storage medium having computer readable program code embodied therein estimating a query compilation time of a query optimizer via reusing an existing join enumerator in said query optimizer, said medium comprising:

(a) computer readable program code aiding in receiving a query;

(b) computer readable program code iterating through possible join pairs for said query;

(c) for each join sequence, computer readable program code identifying a set of differentiating properties and using said identified set of differentiating properties to calculate number of join plans;

(d) computer readable program code estimating compilation time from said calculated number of join plans for each type of join method, said compilation time is estimated via running regression of the following model;

T=T_inst×

Σ

(C_t×

P_t)

wherein T is a machine-dependent parameter representing time per instruction, C_t is a constant representing number of instructions to generate a join plan of type t, and P_t is an estimated number of join plans of type; and

(e) computer readable program code outputting said estimated compilation time.

20. An article of manufacture as per claim 19, wherein said estimation of compilation time is performed via a regression model.

21. An article of manufacture as per claim 19, wherein said set of differentiating properties comprises any of, or a combination of the following:

order, data partition, pipelineability, data source, and presence of expensive predicates.

22. An article of manufacture as per claim 19, wherein said differentiating properties are generated in any of the following policies:

a lazy policy in which said differentiating properties are generated naturally or a eager policy in which said differentiating properties are forcibly generated via a optimizer.

23. An article of manufacture as per claim 19, wherein said number of join plans are calculated for any join type selected from a group consisting of:

nested loops join (NLJN), sort merge join (MGJN), and hash join (HSJN).

24. A computer-based method for estimating query compilation time in a query optimizer, said method implemented in computer readable program code stored in computer memory, said computer-based method comprising the steps of:

bypassing plan generation and reusing a join enumerator of said query optimizer to identify number of joins;

iterating through possible pairs for a query;

for each join, accumulating a set of differentiating properties during enumeration and using said identified set of differentiating properties to calculate number of join plans;

estimating compilation time from said calculated number of join plans for each type of join method via a regression model, wherein said compilation time is estimated via running regression of the following model;

T=T_inst×

Σ

(C_t×

P_t)

wherein T is a machine-dependent parameter representing time per instruction, C_t is a constant representing number of instructions to generate a join plan of type t, and P_t is an estimated number of join plans of type t; and

outputting said estimated compilation time.

25. A computer-based method as per claim 24, wherein said set of differentiating properties comprises any of, or a combination of the following:

order, data partition, pipelineability, data source, and presence of expensive predicates.

26. A computer-based method as per claim 24, wherein said query is an SQL query.

27. A computer-based method as per claim 24, wherein said differentiating properties are generated in any of the following policies:

a lazy policy in which said differentiating properties are generated naturally or an eager policy in which said differentiating properties are forcibly generated via a optimizer.

28. A computer-based method as per claim 24, wherein said number of join plans are calculated for any join type selected from a group consisting of:

nested loops join (NLJN), sort merge join (MGJN), and hash join (HSJN).