# US 2021/0263935 A1 · Workload-based sampling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0263935 A1
- Document ID: US20210263935A1
- Status: Published application
- Kind: A1
- Application number: 16/797,106
- Filed: 2020-02-21
- Published: 2021-08-26
- Earliest claimed: 2020-02-21
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Axel Hertzschuch; Norman May; Lars Fricke; Florian Wolf; Guido Moerkotte; Wolfgang Lehner
- Web page: https://patentgrep.com/patent/US20210263935A1

## CPC

- G06F 16/24549: {Run-time optimisation}
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## 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.

## Claims

### Claim 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,
wherein the estimated cardinality of a query with respect to the data source is determined based on the sample data source.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

A system according to claim 1, wherein determination of the sample data source comprises:
for each of the plurality of queries, determination of 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
selection of a candidate row to add to the sample data source based on the determined decreases.

### Claim 4 (depends on 3)

A system according to claim 3, 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.

### Claim 5 (depends on 4)

A system according to claim 4, 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.

### Claim 6 (depends on 1)

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.

### Claim 7

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,
wherein the estimated cardinality of a query with respect to the data source is determined based on data rows of the sample data source.

### Claim 8 (depends on 7)

A method according to claim 7, 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.

### Claim 9 (depends on 7)

A method according to claim 7, wherein determining the sample data source comprises:
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.

### Claim 10 (depends on 9)

A method according to claim 9, 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.

### Claim 11 (depends on 10)

A method according to claim 10, 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.

### Claim 12 (depends on 7)

A method according to claim 7, 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.

### Claim 13

A database node comprising:
a data source comprising a plurality of data rows; and
a query optimizer to:
determine a plurality of queries of a workload; 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,
wherein the estimated cardinality of a query with respect to the data source is determined based on the sample data source.

### Claim 14 (depends on 13)

A database node according to claim 13, the query optimizer 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.

### Claim 15 (depends on 13)

A database node according to claim 13, wherein determination of the sample data source comprises:
for each of the plurality of queries, determination of 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
selection of a candidate row to add to the sample data source based on the determined decreases.

### Claim 16 (depends on 15)

A database node according to claim 15, 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.

### Claim 17 (depends on 16)

A database node according to claim 16, 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.

### Claim 18 (depends on 13)

A database node according to claim 13, 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.
