Workload-based sampling

Patent metadata

Field	Value
Publication number	US-11455307-B2
Application number	US-202016797106-A
Country	US
Kind code	B2
Filing date	Feb 21, 2020
Priority date	Feb 21, 2020
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

Abstract

A system includes determination of a plurality of queries of a workload, determination of a data source comprising a plurality of data rows, and determination of a sample data source based on a cardinality of each of the plurality of queries with respect to the data source and an estimated cardinality of each of the plurality of queries with respect to the data source, wherein the estimated cardinality of a query with respect to the data source is determined based on the sample data source.

First claim

What is claimed is:

1. A system comprising:
a memory storing processor-executable program code; and
a processing unit to execute the processor-executable program code in order to cause the system to:
determine a plurality of queries of a workload;
determine a data source comprising a plurality of data rows; and
determine a sample data source based on a cardinality of each of the plurality of queries with respect to the data source and an estimated cardinality of each of the plurality of queries with respect to the data source by:
for each of the plurality of queries, determining a decrease in a cardinality estimation error associated with addition of each of candidate rows of the data source to the sample data source; and
selecting a candidate row to add to the sample data source based on the determined decreases,

wherein the estimated cardinality of a query with respect to the data source is determined based on the sample data source.

2. A system according to claim 1 , the processing unit to execute the processor-executable program code in order to cause the system to:
receive a runtime query on the data source;
determine an estimated cardinality of the runtime query with respect to the data source based on the sample data source; and
determine a query execution plan for the runtime query based on the estimated cardinality of the runtime query with respect to the data source.

3. A system according to claim 1 , wherein each of the plurality of queries is associated with one or more predicates, and
wherein the candidate rows associated each one of the plurality of queries are rows of the data source selected by the one or more predicates of the query.

4. A system according to claim 3 , wherein determination, for one of the plurality of queries, of a decrease in a cardinality estimation error associated with addition of a candidate row comprises:
determination of a true cardinality of the query with respect to the data source by execution of the query on the data source;
determination of a current estimated cardinality of the query with respect to the data source by execution of the query on the sample data source not including the candidate row;
determination of a current cardinality estimation error based on the true cardinality and the current estimated cardinality;
determination of a new estimated cardinality of the query with respect to the data source by execution of the query on the sample data source including the candidate row;
determination of a new cardinality estimation error based on the true cardinality and the new estimated cardinality; and
determination of the decrease in the cardinality estimation error based on the current cardinality estimation error and the new cardinality estimation error.

5. A system according to claim 1 , wherein determination, for one of the plurality of queries, of a decrease in a cardinality estimation error associated with addition of a candidate row comprises:
determination of a true cardinality of the query with respect to the data source by execution of the query on the data source;
determination of a current estimated cardinality of the query with respect to the data source by execution of the query on the sample data source not including the candidate row;
determination of a current cardinality estimation error based on the true cardinality and the current estimated cardinality;
determination of a new estimated cardinality of the query with respect to the data source by execution of the query on the sample data source including the candidate row;
determination of a new cardinality estimation error based on the true cardinality and the new estimated cardinality; and
determination of the decrease in the cardinality estimation error based on the current cardinality estimation error and the new cardinality estimation error.

6. A computer-implemented method, comprising:
determining a plurality of queries;
determining a data source comprising a plurality of data rows; and
determining a sample data source comprising a plurality of the plurality of data rows based on a cardinality of each of the plurality of queries with respect to the data source and an estimated cardinality of each of the plurality of queries with respect to the data source by:
for each of the plurality of queries, determining a decrease in a cardinality estimation error associated with addition of each of candidate rows of the data source to the sample data source; and
selecting a candidate row to add to the sample data source based on the determined decreases,

wherein the estimated cardinality of a query with respect to the data source is determined based on data rows of the sample data source.

7. A method according to claim 6 , further comprising:
receiving a runtime query on the data source;
determining an estimated cardinality of the runtime query with respect to the data source based on the sample data source; and
determining a query execution plan for the runtime query based on the estimated cardinality of the runtime query with respect to the data source.

8. A method according to claim 6 , wherein each of the plurality of queries is associated with one or more predicates, and
wherein the candidate rows associated each one of the plurality of queries are rows of the data source selected by the one or more predicates of the query.

9. A method according to claim 8 , wherein determining, for one of the plurality of queries, of a decrease in a cardinality estimation error associated with addition of a candidate row comprises:
determining a true cardinality of the query with respect to the data source by execution of the query on the data source;
determining a current estimated cardinality of the query with respect to the data source by execution of the query on the sample data source not including the candidate row;
determining a current cardinality estimation error based on the true cardinality and the current estimated cardinality;
determining a new estimated cardinality of the query with respect to the data source by execution of the query on the sample data source including the candidate row;
determining a new cardinality estimation error based on the true cardinality and the new estimated cardinality; and
determining the decrease in the cardinality estimation error based on the current cardinality estimation error and the new cardinality estimation error.

10. A method according to claim 6 , wherein determining, for one of the plurality of queries, of a decrease in a cardinality estimation error associated with addition of a candidate row comprises:
determining a true cardinality of the query with respect to the data source by execution of the query on the data source;
determining a current estimated cardinality of the query with respect to the data source by execution of the query on the sample data source not including the candidate row;
determining a current cardinality estimation error based on the true cardinality and the current estimated cardinality;
determining a new estimated cardinality of the query with respect to the data source by execution of the query on the sample data source including the candidate row;
determining a new cardinality estimation error based on the true cardinality and the new estimated cardinality; and
determining the decrease in the cardinality estimation error based on the current cardinality estimation error and the new cardinality estimation error.

11. A non-transitory computer-readable medium storing program code executable by a processing unit to:
determine a plurality of queries of a workload; and
determine a sample data source based on a cardinality of each of the pluralit

Assignees

• Sap Se

Inventors

• Hertzschuch Axel
• May Norman
• Fricke Lars
• Wolf Florian
• Moerkotte Guido
• Lehner Wolfgang

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F16/24549 Primary

  Run-time optimisation · CPC title

• G06N7/005

  Physics · mapped topic