US 7,249,120 B2Granted

Method and apparatus for selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression in optimize queries based on a set of predicates that each reference a set of relational database tables

AssigneeMicrosoft Corporation

InventorsNicolas Bruno, Surajit Chaudhuri

Life of this patent

Estimating the term…

Loading patent…

Abstract

By transforming a query into a product of conditional selectivity expressions, an existing set of statistics on query expressions can be used more effectively to estimate cardinality values. Conditional selectivity values are progressively separated according to rules of conditional probability to yield a set of non-separable decompositions that can be matched with the stored statistics on query expressions. The stored statistics are used to estimate the selectivity of the query and the estimated selectivity can be multiplied by the Cartesian product of referenced tables to yield a cardinality value.

Claims53

Dependent claims

A computer implemented method for approximating a number of tuples returned by a database query to optimize queries on a computerized database that comprises a set of predicates that each reference a set of database tables, the method comprising the steps of:

a) determining whether a first estimated selectivity value of the query is stored and returning the stored first estimated selectivity value to approximate the number of tuples returned by the query;
b) if a first estimated selectivity value of the query is not stored, expressing the query as an input selectivity value;
c) determining if the query is separable based on properties of the input selectivity value;
d) if the query is separable:
separating the input selectivity value to form a product of query selectivity factors;
recursively determining a selectivity value for each query selectivity factor;
combining the selectivity values for each query selectivity factor to determine a second estimated selectivity value of the query;
e) if the query is not separable:
atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression, wherein the atomically decomposing step is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions;
for each of the plurality of alternative products, matching a corresponding conditional selectivity expression with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression by:
compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression;
selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria;
and
using the statistics to obtain an estimated selectivity value of the conditional selectivity expression;
and
combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a third estimated selectivity value of the query;
f) storing in memory either the second or third estimated selectivity value of the query based on whether the query is separable.

14 more elements

For use with a database system, a computer readable storage medium having computer executable instructions stored thereon for performing method steps to approximate a number of tuples returned by a database query to optimize queries on the database system that comprises a set of predicates that each reference a set of database tables, the method comprising the steps of:

a) determining whether a first estimated selectivity value of the query is stored and returning the stored first estimated selectivity value to approximate the number of tuples returned by the query;
b) if a first estimated selectivity value of the query is not stored, expressing the query as an input selectivity value;
c) determining if the query is separable based on properties of the input selectivity value;
d) if the query is separable:
separating the input selectivity value to form a product of query selectivity factors;
recursively determining a selectivity value for each query selectivity factor;
combining the selectivity values for each query selectivity factor to determine a second estimated selectivity value of the query;
e) if the query is not separable:
atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression, wherein the atomically decomposing step is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions;
for each of the plurality of alternative products, matching a corresponding conditional selectivity expression with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression by:
compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression;
selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria;
and
using the statistics to obtain an estimated selectivity value of the conditional selectivity expression;
and
combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a third estimated selectivity value of the query;
and
f) storing in memory either the second or third estimated selectivity value of the query based on whether the query is separable.

15 more elements

a) expressing the query as an input selectivity value;
b) determining if the query is separable based on properties of the input selectivity value;
c) if the query is separable:
separating the input selectivity value by separating the predicates that reference different sets of database tables to form a product of query selectivity factors that reference different sets of database tables;
recursively determining a selectivity value for each query selectivity factor;
combining the selectivity values for each query selectivity factor to determine a first estimated selectivity value of the query;
d) if the query is not separable:
atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression, wherein the atomically decomposing step is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions;
for each of the plurality of alternative products, matching a corresponding conditional selectivity expression with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression by:
compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression;
selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria;
and
using the statistics to obtain an estimated selectivity value of the conditional selectivity expression;
and
combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a second estimated selectivity value of the query;
and
e) storing in memory either the first or second estimated selectivity value of the query based on whether the query is separable.

14 more elements

a) expressing the query as an input selectivity value;
b) determining if the query is separable based on properties of the input selectivity value;
c) if the query is separable:
separating the input selectivity value by separating the predicates that reference different sets of database tables to form a product of query selectivity factors that reference different sets of database tables;
recursively determining a selectivity value for each query selectivity factor;
combining the selectivity values for each query selectivity factor to determine a first estimated selectivity value of the query;
d) if the query is not separable:
atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression, wherein the atomically decomposing step is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions;
for each of the plurality of alternative products, matching a corresponding conditional selectivity expression with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression by:
compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression;
selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria;
and
using the statistics to obtain an estimated selectivity value of the conditional selectivity expression;
and
combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a second estimated selectivity value of the query;
and
e) storing in memory either the first or second estimated selectivity value of the query based on whether the query is separable.

14 more elements

A computer system comprising one or more processors and memory for approximating a number of tuples returned by a database query to optimize queries on a computerized database that comprises a set of predicates that each reference a set of database tables comprising:

a) means for determining whether a first estimated selectivity value of the query is stored and means for returning the stored first estimated selectivity value to approximate the number of tuples returned by the query;
b) means for expressing the query as an input selectivity value if a first estimated selectivity value of the query is not stored;
c) means for determining if the query is separable based on properties of the input selectivity value;
d) means for separating the input selectivity value to form a product of query selectivity factors if the query is separable, further comprising:
means for recursively determining a selectivity value for each query selectivity factor;
means for combining the selectivity values for each query selectivity factor to determine a second estimated selectivity value of the query;
e) means for atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression if the query is not separable, wherein the atomically decomposing is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions, further comprising;
means for matching a corresponding conditional selectivity expression for each of the plurality of alternative products with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression, comprising:
means for compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression;
means for selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria;
and
means for using the statistics to obtain an estimated selectivity value of the conditional selectivity expression;
and
means for combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a third estimated selectivity value of the query;
and
f) means for storing in memory either the second or third estimated selectivity value of the query based on whether the query is separable.

13 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/608,083Filed 27 Jun 2003
Published: US 2005/0004907 A16 Jan 2005
Granted: 24 Jul 2007
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 16/2462
Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries: approximate or statistical queries
G06F 16/24545
Plan optimisation: selectivity estimation or determination
Y10S 707/99932
Database or file accessing: access augmentation or optimizing
Y10S 707/99933
Database or file accessing: query processing, i.e. searching