Method for estimating the cost of query processing

• US 7,636,735 B2
• Filed: 08/19/2005
• Issued: 12/22/2009
• Est. Priority Date: 08/19/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Chun, Josifovski, Vanja, Lohman, Guy Maring, Haas, Peter Jay
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US11/206,978
• Publication Number:
  US 20070043696A1
• Time in Patent Office: 1,586 Days
• Field of Search: 707/104.1, 707/2, 707/100, 707/1, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8365 Query optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Provided is a method for modeling the cost of XML as well as relational operators. As with traditional relational cost estimation, a set of system catalog statistics that summarizes the XML data is exploited; however, the novel use of a set of simple path statistics is also proposed. A new statistical learning technique called transform regression is utilized instead of detailed analytical models to predict the overall cost of an operator. Additionally, a query optimizer in a database is enabled to be self-tuning, automatically adapting to changes over time in the query workload and in the system environment.

Claims

1. A computer-based method of determining a cost model, said cost model modeling the cost of executing a query operator, said query operator in a user query to be executed against a database, said method comprising:

a. determining at least one input feature of a plurality of training queries, said at least one input feature, for which values are either known or unknown, which is assumed to be relevant to said cost model, said input features automatically determined using profiling techniques and said at least one input feature either derived or observed from statistics obtained by traversing a tree representation of data stored in said database;

b. estimating values for said at least one input feature based on statistics Sp stored by said database, and

when values for said at least one input feature are unknown;

said Sp is a function of a cardinality of a path query p under said tree T, number of p'"'"'s children under T;

number of p'"'"'s descendants under T; and

number of pages requested in order to answer said path query p, and said statistics Sp stored by said database are simple path statistics comprising the cardinality of a simple path under an XML tree, the number of simple path children under an XML tree, the number of simple path descendants under an XML tree, and the number of pages requested in order to answer a simple path query, said simple path expressions defining a linear chain of node tests that are connected by child axes;

c. executing said plurality of training queries containing said query operator and said at least one input feature and determining whether cost of executing said query operator changes as values of said at least one input feature are varied and if so, statistically fitting a model to correlate observed costs of executing said query operator with said at least one input feature; and

d. estimating, based on said model and said at least one input feature, a cost for executing said query operator in said user query.

2. The computer-based method of claim 1, wherein said query is any of:

an XML or XPATH query and wherein said database stores XML data.

3. The computer-based method of claim 1, wherein a subset of said input features are posterior features.

4. The computer-based method of claim 1, wherein said input features are determined on the basis of affecting the cost of executing said query operator.

5. The computer-based method of claim 1, wherein said model is fitted by any of:

regression, neural network, or nearest neighbor approaches.

6. The computer-based method of claim 5, wherein said regression is any of:

a linear, nonlinear, transform, or piecewise linear regression.

7. The computer-based method of claim 1, wherein said method further comprises iteratively repeating step a through step d to increase the accuracy of said model.

8. The computer-based method of claim 1, wherein said method is implemented by remote autonomous database systems in a multi-database setting.

9. An article of manufacture comprising a computer usable medium having computer readable program code embodied therein which implements the determination of a cost model, said cost model modeling the cost of executing a query operator, said query operator in a user query to be executed against a database, said medium comprising modules implementing:

a. determining at least one input feature of a plurality of training queries, said at least one input feature, for which values are either known or unknown, which is assumed to be relevant to said cost model, said input features automatically determined using profiling techniques and said at least one input feature either derived or observed from statistics obtained by traversing a tree representation of data stored in said database;

b. estimating values for said at least one input feature based on statistics Sp stored by said database, and

when values for said at least one input feature are unknown;

said Sp is a function of a cardinality of a path query p under a tree T, number of p'"'"'s children under T;

number of p'"'"'s descendants under T; and

number of pages requested in order to answer said path query p, said statistics Sp stored by said database are simple path statistics comprising the cardinality of a simple path under an XML tree, the number of simple path children under an XML tree, the number of simple path descendants under an XML tree, and the number of pages requested in order to answer a simple path query, said simple path expressions defining a linear chain of node tests that are connected by child axes;

c. executing said plurality of training queries containing said query operator and said at least one input feature and determining whether cost of executing said query operator changes as values of said at least one input feature are varied and if so, statistically fitting a model to correlate observed costs of executing said query operator with said at least one input feature; and

d. estimating, based on said model and said at least one input feature, a cost for executing said query operator in said user query.

10. The article of manufacture of claim 9, wherein said method further comprises iteratively repeating step a through step d to increase the accuracy of said model.

11. The article of manufacture of claim 9, wherein said query is any of:

an XML or XPATH query and wherein said database stores XML data.

12. The article of manufacture of claim 9, wherein a subset of said input features are posterior features.

13. The article of manufacture of claim 9, wherein said input features are determined on the basis of affecting the cost of executing said query operator.

14. The article of manufacture of claim 9, wherein said model is fitted by any of:

regression, neural network, or nearest neighbor approaches.

15. The article of manufacture of claim 14, wherein said regression is any of:

a linear, nonlinear, transform, or piecewise linear regression.