# US 2016/0253384 A1 · Estimating data

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

- Number: US 2016/0253384 A1
- Document ID: US20160253384A1
- Status: Published application
- Kind: A1
- Application number: 15/032,977
- Filed: 2013-11-14
- Published: 2016-09-01
- Earliest claimed: 2013-11-14
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Harumi Kuno; Goetz Graefe
- Web page: https://patentgrep.com/patent/US20160253384A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein are a system, non transitory computer-readable medium, and method for estimating database performance. A request for an estimate of data is read. The estimate is calculated based at least partially on a node located in a data structure.

## Claims

### Claim 1

A system comprising:
a database comprising an index, the index comprising a hierarchical data structure of interlinked nodes;
an estimator which upon execution instructs at least one processor to:
read a request to estimate an amount of data that would fall within a scope of a criteria in a predicate without executing the predicate;
locate a node in the data structure whose child nodes or content fall within the scope of the criteria; and
calculate the estimate based at least partially on the located node.

### Claim 2 (depends on 1)

The system of claim 1, wherein the estimator upon execution instructs at least one processor to determine a level in a hierarchy of the data structure that corresponds to the scope of the criteria.

### Claim 3 (depends on 2)

The system of claim 2, wherein the node of the data structure is located at the level in the hierarchy of the data structure that corresponds to the scope of the criteria.

### Claim 4 (depends on 2)

The system of claim 2, wherein the estimator upon execution instructs at least one processor to determine a new level in the hierarchy of the data structure that corresponds to the scope with enhanced precision.

### Claim 5 (depends on 1)

The system of claim 1, wherein the estimator upon execution locates a second node in a second data structure whose child nodes or content fall within the scope of the criteria and to further calculate the estimate based at least partially on the child nodes or the content of the second node.

### Claim 6

A non-transitory computer readable medium having instructions therein which, if executed, cause at least one processor to:
read a request to estimate an amount of data in a B-tree data structure that would fall within a scope of criteria in a predicate without executing the predicate;
determine a level in the B-tree that corresponds to the scope;
locate a node in the B-tree data structure at the determined level whose child nodes or content fall within the scope of the criteria; and
estimate the amount of data based at least partially on the located node.

### Claim 7 (depends on 6)

The non-transitory computer readable medium of claim 6, wherein the instructions therein upon execution instruct at least one processor to determine a new level in a hierarchy of the B-tree that corresponds to the scope with enhanced precision.

### Claim 8 (depends on 6)

The non-transitory computer readable medium of claim 6, wherein the instructions therein upon execution instruct at least one processor to locate a second node in a second data structure whose child nodes or content fall within the scope of the criteria and to further calculate the estimate based at least partially on the second node.

### Claim 9 (depends on 6)

The non-transitory computer readable medium of claim 6, wherein the estimate comprises a cardinality estimate.

### Claim 10 (depends on 6)

The non-transitory computer readable medium of claim 6, wherein the estimate comprises a predicate selectivity estimate.

### Claim 11

A method comprising
reading, using at least one processor, a request to estimate an amount of data in a data structure that falls within a scope of criteria in a predicate without executing the predicate;
determining, using at least one processor, a level in the data structure that corresponds to the scope;
if the level is not a leaf level, locating, using at least one processor, an interior node at the determined level whose child nodes fall within the scope of the criteria;
if the level is the leaf level, locating, using at least one processor, a leaf node at the leaf level whose content falls within the scope of the criteria; and
estimating, using at least one processor, the amount of data based at least partially on the interior node or the leaf node.

### Claim 12 (depends on 11)

The method of claim 11, wherein the estimate comprises a cardinality estimate.

### Claim 13 (depends on 11)

The method of claim 11, wherein the estimate comprises a predicate selectivity estimate.

### Claim 14 (depends on 11)

The method of claim 11, locating, using at least one processor, a second interior node in a second data structure whose child nodes fall within the scope of the criteria and to further calculate the estimate based at least partially on the second interior node.

### Claim 15 (depends on 11)

The method of claim 11, locating, using at least one processor, a second leaf node in a second data structure whose content falls within the scope of the criteria and to further calculate the estimate based at least partially on the second leaf node.