# US 2012/0254199 A1 · Merge optimization system

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

- Number: US 2012/0254199 A1
- Document ID: US20120254199A1
- Status: Published application
- Kind: A1
- Application number: 13/077,460
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Inventors: Harumi Kuno; Goetz Graefe
- Web page: https://patentgrep.com/patent/US20120254199A1

## CPC

- G06F 7/32: Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A merge optimization system to optimize a run merge process for runs including keys from a data source. The system may include a run generation module to generate a run of the keys in a predetermined order. The system may further include a key characterization module to characterize a distribution of the keys across the run at run generation time, and a run merge module executed by a computer system to selectively associate the runs based on the characterization.

## Claims

### Claim 1

A merge optimization system to optimize a run merge process for runs including keys from a data source, the system comprising:
a run generation module to generate a run of the keys in a predetermined order;
a key characterization module to characterize a distribution of the keys across the run at run generation time; and
a run merge module, executed by a computer system, to selectively associate the runs based on the characterization.

### Claim 2 (depends on 1)

The system of claim 1, wherein the run includes the keys in a predetermined sorted order.

### Claim 3 (depends on 1)

The system of claim 1, wherein the key characterization module includes a histogram generation module to generate a histogram characterizing the distribution of the keys across the run at the run generation time.

### Claim 4 (depends on 3)

The system of claim 3, wherein the histogram includes subranges of the keys and a number of the keys in each subrange.

### Claim 5 (depends on 3)

The system of claim 3, wherein the histogram is associated with a plurality of the runs based on a shape of the runs.

### Claim 6 (depends on 1)

The system of claim 1, wherein the key characterization module includes an order of the keys in the run, compared to key positions in the data source.

### Claim 7 (depends on 1)

The system of claim 1, wherein the key characterization module includes a bitmap index generation module to generate a bitmap index characterizing the distribution of the keys across the run at the run generation time.

### Claim 8 (depends on 1)

The system of claim 1, wherein the run merge module selectively merges the runs based on the characterization.

### Claim 9 (depends on 1)

The system of claim 1, wherein the run merge module selectively concatenates the runs based on the characterization.

### Claim 10 (depends on 1)

The system of claim 1, wherein the run merge module selectively associates at least one of ranges and subranges of at least one of the runs and sub-runs based on the characterization.

### Claim 11 (depends on 1)

The system of claim 1, wherein the run generation module generates the run based on a replacement selection sort.

### Claim 12

A method for merge optimization for a run merge process for runs including keys from a data source, the method comprising:
generating a run of the keys in a predetermined order;
characterizing a distribution of the keys across the run at run generation time; and
selectively associating, by a computer, the runs based on the characterization.

### Claim 13 (depends on 12)

The method of claim 12, wherein characterizing the distribution further comprising generating a histogram characterizing the distribution of the keys across the run at the run generation time.

### Claim 14 (depends on 13)

The method of claim 13, wherein the histogram includes subranges of the keys and a number of the keys in each subrange.

### Claim 15 (depends on 12)

The method of claim 12, wherein characterizing the distribution further comprising including an order of the keys in the run and comparing the order to key positions in the data source.

### Claim 16 (depends on 12)

The method of claim 12, wherein characterizing the distribution further comprising generating a bitmap index characterizing the distribution of the keys across the run at the run generation time.

### Claim 17 (depends on 12)

The method of claim 12, wherein selectively associating further comprising selectively merging the runs based on the characterization.

### Claim 18 (depends on 12)

The method of claim 12, wherein selectively associating further comprising selectively concatenating the runs based on the characterization.

### Claim 19 (depends on 12)

The method of claim 12, wherein selectively associating further comprising selectively associating at least one of ranges and subranges of at least one of the runs and sub-runs based on the characterization.

### Claim 20

A non-transitory computer readable medium storing machine readable instructions, that when executed by a computer system, perform a method for merge optimization for a run merge process for runs including keys from a data source, the method comprising:
generating a run of the keys in a predetermined order;
characterizing a distribution of the keys across the run at run generation time; and
selectively associating, by a computer, the runs based on the characterization.
