# US 2012/0254171 A1 · Exploitation of Correlation Between Original and Desired Data Sequences During Run Generation

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

- Number: US 2012/0254171 A1
- Document ID: US20120254171A1
- Status: Published application
- Kind: A1
- Application number: 13/075,570
- Filed: 2011-03-30
- Published: 2012-10-04
- Earliest claimed: 2011-03-30
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Goetz Graefe; Harumi Kuno
- Web page: https://patentgrep.com/patent/US20120254171A1

## CPC

- G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor
- G06F 7/24: Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer executed method of exploiting correlations between original and desired data sequences during run generation comprises, with a processor, adding a number of data values from a data source to a first memory device, the first memory device defining a workspace, determining whether the data values within the workspace should be output in ascending or descending order for a number of runs, and writing a number of the data values as a run to a second memory device in the determined order.

## Claims

### Claim 1

A computer executed method of exploiting correlations between original and desired data sequences during run generation comprising:
with a processor:
adding a number of data values from a data source to a first memory device, the first memory device defining a workspace;
determining whether the data values within the workspace should be output in ascending or descending order for a number of runs; and
writing a number of the data values as a run to a second memory device in the determined order.

### Claim 2 (depends on 1)

The method of claim 1, further comprising determining whether or not to truncate each run based on the distribution of data values read from the data source.

### Claim 3 (depends on 1)

The method of claim 1, in which determining whether the data values within the workspace should be added to a run in ascending or descending order comprises switching the order every k number of runs, in which k is a positive integer.

### Claim 4 (depends on 1)

The method of claim 1, in which determining whether the data values within the workspace should be added to a run in ascending or descending order comprises switching the order based on analysis of data values already added to the workspace.

### Claim 5 (depends on 1)

The method of claim 1, in which determining whether the data values within the workspace should be added to a run in ascending or descending order comprises switching the order based on the order in which values were added to a previous run.

### Claim 6 (depends on 1)

The method of claim 1, in which determining whether the data values within the workspace should be added to a run in ascending or descending order comprises switching the order based on the analysis of data values remaining to be added to the workspace.

### Claim 7 (depends on 2)

The method of claim 2, in which truncating the run based on the distribution of data values read from the database comprises determining if the data values contained in the workspace lie at the opposite end of a series of data values within the data source as compared to the data values previously emitted to the current run.

### Claim 8 (depends on 7)

The method of claim 7, in which, if the run is truncated, then opening a new run and switching the sort order of the new run relative to the previous run.

### Claim 9 (depends on 1)

The method of claim 1, in which a number of runs are generated, and in which the number of runs are merged into a one ordered run.

### Claim 10 (depends on 1)

The method of claim 1, in which a number of runs are generated, and in which the number of runs are used to implement a database join operation.

### Claim 11

A system for exploiting an incidental sort order of data during run generation comprising:
a first memory device, the first memory device defining a workspace;
a second memory device that stores generated runs; and
a processor that:
retrieves data values from a data source communicatively coupled to the system and adds the data values to the workspace;
determines whether the data values within the workspace should be sorted in ascending or descending order; and
writes a number of the data values as a run to the second memory device in the determined order.

### Claim 12 (depends on 11)

The system of claim 11, in which the processor further truncates the run based on the distribution of data values read from the data source.

### Claim 13 (depends on 11)

The system of claim 11, further comprising an output device that outputs a representation of sorted data values to a user.

### Claim 14

A computer executed method of exploiting correlation between requested and on-disk data sequence during a disk scan operation comprising:
with a processor:
scanning a number of data values from a disk in response to a number of requests for data values;
determining whether the order in which data values are being requested correlate to the order in which data values are being scanned from the disk; and
determining whether to reverse the order of the disk scan based on the distribution of data values being requested.

### Claim 15 (depends on 14)

The method of claim 14, in which the order of the disk scan is reversed if the data values on the disk are sorted in a first order and the requests for data are accessing data on the disk in an opposite order.
