Selectivity estimation for conjunctive predicates in the presence of partial knowledge about multivariate data distributions
AssigneeInternational Business Machines Corporation
InventorsMarcel Kutsch, Volker Gerhard Markl, Nimrod Megiddo, Tam Minh Dai Tran
Life of this patent
Estimating the term…
Abstract
A method for consistent selectivity estimation based on the principle of maximum entropy (ME) is provided. The method efficiently exploits all available information and avoids the bias problem. In the absence of detailed knowledge, the ME approach reduces to standard uniformity and independence assumptions. The disclosed method, based on the principle of ME, is used to improve the optimizer's cardinality estimates by orders of magnitude, resulting in better plan quality and significantly reduced query execution times.
Claims9
A computer-based method implemented in a query optimizer to incorporate partial information about multivariate distributions in a constrained optimization form, said method comprising:
- modeling one or more multivariate distributions based on available statistical information in a probability space;
- modeling one or more multivariate distributions for which no statistical information is available via a constrained optimization approach and entropy maximization over said probability space;
- estimating cardinality based on all available statistical information and both of said modeled distributions during cardinality estimation, and
- outputting said estimated cardinality,
- wherein said method further comprises a preprocessing step, said preprocessing comprising:
- partitioning a predicate space into independent components of nonintersecting knowledge based on both available knowledge and additional information about relevance of selectivities within each component;
- identifying, a priori, one or more atoms b for which input knowledge T implies that selectivity xb is zero, and excluding such atoms in computations of said constrained optimization approach, wherein selectivity xb is deduced to be zero:
- only (a) when sx=0 for X∈T, then xb=0 for all atoms b∈C(X), where sx is the selectivity of predicate px and C(X) is the set of all atoms contributing to predicate px, or (b) when two sets of atoms A and B with B⊂A have the same selectivity, i.e., by utilizing the equation Σb∈B xb=Σb∈A xb, then xb=0 for b∈A\B.
An article of manufacture comprising a non-transitory computer useable medium having computer readable program code embodied therein which, when executed by a computer, implements a database query optimizer computing cardinalities of each partial query execution plan comprising, said computer usable medium comprising:
- computer readable program code implementing a selectivity computing unit to compute the selectivity of one or more predicates based on known statistical information in a given probability space;
- computer readable program code implementing a missing selectivity computing unit to compute missing selectivities using a constrained optimization approach and entropy maximization over said probability space, and
- wherein said computed selectivities based on statistical information and computed missing selectivities based on constrained optimization approach and entropy maximization are used to provide improved cardinality estimates and reduced query execution times,
- wherein said medium further comprises computer readable program code implementing a preprocessing step, said preprocessing comprising:
- partitioning a predicate space into independent components of nonintersecting knowledge based on both available knowledge and additional information about relevance of selectivities within each component;
- identifying, a priori, one or more atoms b for which input knowledge T implies that selectivity xb is zero, and excluding such atoms in computations of said constrained optimization approach, wherein selectivity xb is deduced to be zero:
- only (a) when sx=0 for X∈T, then xb=0 for all atoms bεC(X), where sx is the selectivity of predicate px and C(X) is the set of all atoms contributing to predicate px, or (b) when two sets of atoms A and B with B⊂A have the same selectivity, i.e., by utilizing the equation Σb∈B xb=Σb∈A xb, then xb=0 for b∈A\B.
An article of manufacture comprising a non-transitory computer useable medium having computer readable program code embodied therein which incorporates partial information about multivariate distributions in a constrained optimization, said medium comprising:
- computer readable program code modeling one or more multivariate distributions based on available statistical information in a probability space;
- computer readable program code modeling one or more multivariate distributions for which no statistical information is available via a constrained optimization approach and entropy maximization over said probability space;
- computer readable program code estimating cardinality based on all available statistical information and both of said modeled distributions during cardinality estimation, and
- computer readable program code outputting said estimated cardinality,
- wherein said medium further comprises computer readable program code implementing a preprocessing step, said preprocessing comprising:
- partitioning a predicate space into independent components of nonintersecting knowledge based on both available knowledge and additional information about relevance of selectivities within each component;
- identifying, a priori, one or more atoms b for which input knowledge T implies that selectivity xb is zero, and excluding such atoms in computations of said constrained optimization approach, wherein selectivity xb is deduced to be zero:
- only (a) when sx=0 for X∈T, then xb=0 for all atoms bεC(X), where sx is the selectivity of predicate px and C(X) is the set of all atoms contributing to predicate px, or (b) when two sets of atoms A and B with B⊂A have the same selectivity, i.e., by utilizing the equation Σb∈B xb=Σb∈A xb, then xb=0 for b∈A\B.
Dependencies are inferred from the claim text.