# US 2018/0025056 A1 · Salient sampling for query size estimation

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

- Number: US 2018/0025056 A1
- Document ID: US20180025056A1
- Status: Published application
- Kind: A1
- Application number: 15/723,474
- Filed: 2017-10-03
- Published: 2018-01-25
- Earliest claimed: 2013-07-09
- Assignees: LogicBlox, Inc.
- Applicants: LogicBlox, Inc.
- Inventors: Todd L. Veldhuizen
- Web page: https://patentgrep.com/patent/US20180025056A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/2453: Query optimisation
- G06F 16/24535: {of sub-queries or views}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Salient sampling for query size estimation includes identifying two or more columns in a database table that have corresponding columns in one or more other tables. One or more hash functions are applied to domains of each of the identified columns. A first hash function is applied to a domain of the first column and a second hash function to a domain of the second column. A subset of the rows in the database table is selected. The selecting includes selecting rows in the database table where results of the first hash function meet a first numeric threshold and selecting rows in the database table where results of the second hash function meet a second numeric threshold. A sample database table corresponding to the database table is created. The sample database table includes the selected subset of the rows in the database table.

## Claims

### Claim 1

A system for creating samples of database tables, the system comprising:
at least one memory having computer readable computer instructions; and
at least one processor for executing the computer readable instructions to perform a method comprising:
identifying a first column and a second column in a first database table, each of the first and second columns having corresponding columns in one or more other database tables;
applying one or more hash functions to values in the first column and second column, the applying including applying a first hash function to the values of the first column and applying a second hash function to the values of the second column;
selecting a subset of the rows in the first database table where results of the first hash function meet a first numeric threshold, or where results of the second hash function meet a second numeric threshold;
creating a sample database table corresponding to the result of a join operation of the subset of rows of the first database table and the one or more other database tables; and
estimating a cardinality of a database query over the first database table by scaling the cardinality of the database query over the sample database table by a factor of 1/v where v is the volume of the selected subset of rows of the first database table relative to the first database table.

### Claim 2 (depends on 1)

The system of claim 1, wherein the first hash function is different than the second hash function.

### Claim 3 (depends on 1)

The system of claim 1, wherein the first hash function is the same as the second hash function.

### Claim 4 (depends on 1)

The system of claim 1, wherein the first numeric threshold is different than the second numeric threshold.

### Claim 5 (depends on 1)

The system of claim 1, wherein the first numeric threshold is the same as the second numeric threshold.

### Claim 6 (depends on 1)

The system of claim 1, wherein the one of the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns being joined in the database query.

### Claim 7 (depends on 1)

The system of claim 1, wherein the method further comprises computing the database query over the sample database table.

### Claim 8 (depends on 1)

The system of claim 1, wherein the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns mentioned in the database query.

### Claim 9 (depends on 1)

The system of claim 1, wherein one of the first hash function and second hash function is universal.

### Claim 10 (depends on 1)

The system of claim 1, wherein the system further comprises:
expressing the database query as the disjoint union of two or more subqueries; and
performing for each subquery:
computing the subquery over the sample database tables; and
estimating a cardinality of the database query as a cardinality of the subquery over the sample database tables divided by a volume of the selected subset of rows; and
adding the resulting estimates.

### Claim 11

A non-transitory computer readable storage media for creating samples of database tables, the non-transitory computer readable storage media having computer-readable program code embodied thereon, which when executed by a computer processor, causes the computer processor to implement a method, the method comprising:
identifying a first column and a second column in a first database table, each of the first and second columns having corresponding columns in one or more other database tables;
applying one or more hash functions to values in the first column and second column, the applying including applying a first hash function to the values of the first column and applying a second hash function to the values of the second column;
selecting a subset of the rows in the first database table where results of the first hash function meet a first numeric threshold, or where results of the second hash function meet a second numeric threshold;
creating a sample database table corresponding to the result of a join operation of the subset of rows of the first database table and the one or more other database tables; and
estimating a cardinality of a database query over the first database table by scaling the cardinality of the database query over the sample database table by a factor of 1/v where v is the volume of the selected subset of rows of the first database table relative to the first database table.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the first hash function is different than the second hash function.

### Claim 13 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the first hash function is the same as the second hash function.

### Claim 14 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the first numeric threshold is different than the second numeric threshold.

### Claim 15 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the first numeric threshold is the same as the second numeric threshold.

### Claim 16 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the one of the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns being joined in the database query.

### Claim 17 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the method further comprises computing the database query over the sample database table.

### Claim 18 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the one or more other database tables and the first and second columns are mentioned in a database query, and the identifying, applying, selecting and creating are performed for all of the database tables and columns mentioned in the database query.

### Claim 19 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein one of the first hash function and second hash function is universal.

### Claim 20 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the method further comprises:
expressing the database query as the disjoint union of two or more subqueries; and
performing for each subquery:
computing the subquery over the sample database tables; and
estimating a cardinality of the database query as a cardinality of the subquery over the sample database tables divided by a volume of the selected subset of rows; and
adding the resulting estimates.
