Estimating the compilation time of a query optimizer
First Claim
1. A method for estimating a query compilation time of a query optimizer 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; and
(d) estimating the compilation time from said calculated number of join plans for each type of join method.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
33 Claims
-
1. A method for estimating a query compilation time of a query optimizer 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; and
(d) estimating the compilation time from said calculated number of join plans for each type of join method. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A compilation time estimator (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 number of join plans for each type of join method via a regression model as follows,
T=Tisnt×- (Ct×
Pt)wherein T is a machine-dependent parameter representing time per instruction, Ct is a constant representing number of instructions to generate a join plan of type t, and Pt is an estimated number of join plans of type t. - View Dependent Claims (12, 13, 14, 15)
- (Ct×
-
16. A system for estimating query compilation time via reusing a join enumerator in a query optimizer, said system comprising:
-
(a) an interface to receive a query;
(b) a join enumerator to iterate through possible join pairs for said query, said iteration performed via reusing said join enumerator in said query optimizer;
(c) 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
(d) a compilation time estimator to estimate 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. - View Dependent Claims (17, 18, 19, 20, 21)
-
-
22. An article of manufacture comprising computer usable 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; and
(d) computer readable program code estimating compilation time from said calculated number of join plans for each type of join method. - View Dependent Claims (23, 24, 25, 26, 27)
-
-
28. A method for estimating query compilation time in a query optimizer, said 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; and
estimating compilation time from said calculated number of join plans for each type of join method via a regression model. - View Dependent Claims (29, 30, 31, 32, 33)
-
Specification