US 10,872,086 B2Granted

Selectivity estimation for database query planning

AssigneeSap SE

InventorsGuido Moerkotte, Alexander Boehm, Norman May

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system for cardinality estimation for database query planning is provided. In some implementations, the system performs operations comprising determining, based on a first bounds and a second bounds for a combination of query predicates, whether a solution for the combination of the query predicates exists which includes both the first and second bounds. When the solution is determined to exist, the operations can further comprise determining at least one selectivity estimate for the combination of the query predicates. A query plan for execution of a database query comprising the query predicates can be generated based on the at least one selectivity estimate, and the database query can be executed through execution of the query plan. Related systems, methods, and articles of manufacture are also described.

Claims17

Dependent claims

A system comprising:

at least one processor;
and
at least one memory storing instructions which, when executed by the at least one processor, cause operations comprising:
determining that a solution is consistent for a combination of query predicates, wherein determining that the solution is consistent comprises determining that a solution set is non-empty, wherein the solution set includes a first selectivity of the combination of query predicates and a second selectivity of the combination of query predicates, wherein the first selectivity is between a first lower bound and a first upper bound, and wherein the second selectivity is between a second lower bound and a second upper bound;
in response to the first lower bound being a predetermined distance from the first upper bound and/or the second lower bound being a predetermined distance from the second upper bound, determining at least one selectivity estimate for the combination of the query predicates, wherein the at least one selectivity estimate is determined based on a geometric mean of the first lower bound and the first upper bound and/or a geometric mean of the second lower bound and the second upper bound;
generating, based on the at least one selectivity estimate, a query plan for execution of a database query comprising the query predicates;
and
executing the database query through execution of the query plan.

5 more elements

A method comprising:

determining that a solution is consistent for a combination of query predicates, wherein determining that the solution is consistent comprises determining that a solution set is non-empty, wherein the solution set includes a first selectivity of the combination of query predicates and a second selectivity of the combination of query predicates, wherein the first selectivity is between a first lower bound and a first upper bound, and wherein the second selectivity is between a second lower bound and a second upper bound;
in response to the first lower bound being a predetermined distance from the first upper bound and/or the second lower bound being a predetermined distance from the second upper bound, determining at least one selectivity estimate for the combination of the query predicates, wherein the at least one selectivity estimate is determined based on a geometric mean of the first lower bound and the first upper bound and/or a geometric mean of the second lower bound and the second upper bound;
generating, based on the at least one selectivity estimate, a query plan for execution of a database query comprising the query predicates;
and
executing the database query through execution of the query plan.

2 more elements

A non-transitory computer-readable medium comprising instructions which, when executed by at least one processor, result in operations comprising:

determining that a solution is consistent for a combination of query predicates, wherein determining that the solution is consistent comprises determining that a solution set is non-empty, wherein the solution set includes a first selectivity of the combination of query predicates and a second selectivity of the combination of query predicates, wherein the first selectivity is between a first lower bound and a first upper bound, and wherein the second selectivity is between a second lower bound and a second upper bound;
in response to the first lower bound being a predetermined distance from the first upper bound and/or the second lower bound being a predetermined distance from the second upper bound, determining at least one selectivity estimate for the combination of the query predicates, wherein the at least one selectivity estimate is determined based on a geometric mean of the first lower bound and the first upper bound and/or a geometric mean of the second lower bound and the second upper bound;
generating, based on the at least one selectivity estimate, a query plan for execution of a database query comprising the query predicates;
and
executing the database query through execution of the query plan.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/603,325Filed 23 May 2017
Published: US 2018/0341679 A129 Nov 2018
Granted: 22 Dec 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 16/24545
Plan optimisation: selectivity estimation or determination
G06F 16/24535
Query rewriting; Transformation: of sub-queries or views
G06F 16/2455
Query processing: query execution
G06F
Computing and data processing

Family

US 2018/0341679 A1Pre-grant publication · published 29 Nov 2018
US 10,872,086 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key