# US 2015/0106397 A1 · System and Method for Optimizing Queries

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

- Number: US 2015/0106397 A1
- Document ID: US20150106397A1
- Status: Published application
- Kind: A1
- Application number: 14/577,611
- Filed: 2014-12-19
- Published: 2015-04-16
- Earliest claimed: 2009-08-31
- Assignees: Hewlett-Packard Development Company, L.P.
- Applicants: Hewlett-Packard Development Company, L.P.
- Inventors: Roger Mitchell; Renu Varshneya; Awny K. Al-Omari
- Web page: https://patentgrep.com/patent/US20150106397A1

## CPC

- G06F 16/2433: {Query languages}
- G06F 16/2453: Query optimisation
- G06F 16/24534: {Query rewriting; Transformation}
- G06F 16/2455: Query execution
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

There is provided a computer-implemented method of optimizing a query. An exemplary method retrieves a subset of rows from a sample table based on a query for a table associated with the sample table. The query specifies the table. The sample table is generated in a previous optimization of the query. The sample table includes a scrambled, random selection of rows from the table. A cardinality of the table is determined based on the subset. A query plan is generated based on the query and the cardinality.

## Claims

### Claim 1

A computer-implemented method of optimization, comprising:
retrieving a subset of rows from a sample table based on a query for a table associated with the sample table, the sample table being generated in a previous optimization, the sample table comprising a scrambled, random selection of rows from the table;
determining a cardinality of the table based on the subset; and
generating a query plan based on the query and the cardinality.

### Claim 2 (depends on 1)

The method of claim 1, the query specifying a sample size smaller than or equal to a number of rows in the sample table, the sample size being based on a margin of error for estimating the cardinality.

### Claim 3 (depends on 2)

The method of claim 2, wherein a number of rows of the subset equals the sample size.

### Claim 4 (depends on 1)

The method of claim 1, the subset of rows being retrieved by performing a single disk head seek and a sequential scan.

### Claim 5 (depends on 1)

The method of claim 1, wherein the sample table comprises a subset of columns of the table.

### Claim 6 (depends on 5)

The method of claim 5, wherein the sample table comprises a clustering key, and wherein the sample table is scrambled based on the clustering key.

### Claim 7 (depends on 1)

The method of claim 1, wherein the query specifies a predicate that does not comprise a range or equality comparison.

### Claim 8

A computer system for optimization in a database management system (DBMS), the computer system comprising:
a processor that executes stored instructions; and
a memory device that stores instructions and data, the memory device comprising:
a sample table generated in a previous optimization, the sample table comprising a scrambled, random subset of the rows of a source table, wherein the source table is associated with the sample table;
computer-implemented code that determines the sample table is to be replaced based on metadata and a specified threshold;
computer-implemented code that deletes the sample table;
computer-implemented code that generates a new sample table comprising:
all columns of the sample table; and
a new scrambled, random subset of rows from the source table;
computer-implemented code that retrieves a subset of rows from the new sample table based on a query;
computer-implemented code that determines a cardinality of the table based on the subset; and
computer-implemented code that generates a query plan based on the query and the cardinality.

### Claim 9 (depends on 8)

The computer system of claim 8, wherein the query specifies the threshold as a sample size based on a margin of error for the cardinality, the metadata comprises a number of rows of the sample table, and wherein the threshold indicates the sample table has fewer rows than the sample size.

### Claim 10 (depends on 8)

The computer system of claim 8, wherein the metadata specifies a number of row deletes, updates, and insertions to the source table, and wherein the threshold indicates the sample table is no longer current.

### Claim 11 (depends on 8)

The computer system of claim 8, the subset of rows being retrieved by performing a single disk head seek and a sequential scan.

### Claim 12 (depends on 8)

The computer system of claim 8, wherein the sample table and the new sample table comprise a subset of columns of the table.

### Claim 13 (depends on 12)

The computer system of claim 12, wherein the new sample table comprises a clustering key, and wherein the new sample table is scrambled based on the clustering key.

### Claim 14 (depends on 8)

The computer system of claim 8, wherein the query specifies a predicate that does not comprise a range or equality comparison.

### Claim 15

A tangible, machine-readable medium that stores machine-readable instructions executable by a processor for optimization in a database management system (DBMS), the tangible, machine-readable medium comprising:
a sample table generated in a previous optimization in the DBMS, the sample table comprising a scrambled, random subset of the rows of a source table associated with the sample table;
machine-readable instructions that, when executed by the processor, determines the sample table is to be replaced based on a specified threshold and metadata;
machine-readable instructions that, when executed by the processor, deletes the sample table;
machine-readable instructions that, when executed by the processor, generates a new sample table comprising:
all columns of the sample table; and
a scrambled, random selection of rows from the source table;
machine-readable instructions that, when executed by the processor, retrieves a subset of rows from the new sample table based on a query;
machine-readable instructions that, when executed by the processor, determines a cardinality of the table based on the subset; and
machine-readable instructions that, when executed by the processor, generates a query plan based on the query and the cardinality.

### Claim 16 (depends on 15)

The tangible, machine-readable medium of claim 15 wherein the query specifies the threshold as a sample size based on a margin of error for the cardinality, the metadata comprises a number of rows of the sample table, and wherein the threshold indicates the sample table has fewer rows than the sample size.

### Claim 17 (depends on 15)

The tangible, machine-readable medium of claim 15, wherein the metadata specifies a number of row deletes, updates, and insertions to the source table, and wherein the threshold indicates the sample table is no longer current.

### Claim 18 (depends on 15)

The tangible, machine-readable medium of claim 15, the subset of rows being retrieved by performing a single disk head seek and a sequential scan.

### Claim 19 (depends on 15)

The tangible, machine-readable medium of claim 15, wherein the sample table and the new sample table comprise a subset of columns of the table.

### Claim 20 (depends on 19)

The tangible, machine-readable medium of claim 19, wherein the new sample table comprises a clustering key, and wherein the new sample table is scrambled based on the clustering key.
