# US 7,412,494 B2 · Merging partial query results into a single result

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

- Number: US 7,412,494 B2
- Document ID: US7412494B2
- Status: Granted
- Kind: B2
- Application number: 10/789,812
- Filed: 2004-02-27
- Published: 2005-09-01
- Granted: 2008-08-12
- Earliest claimed: 2004-02-27
- Assignees: Sap SE
- Inventors: Jens-Peter Dittrich; Olaf Meincke; Guenter Radestock; Andrew Ross
- Web page: https://patentgrep.com/patent/US7412494B2

## CPC

- G06F 16/2471: {Distributed queries}
- G06F 16/2456: {Join operations}
- Y10S 707/99933: Query processing, i.e. searching
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method and system for executing an information retrieval query in a multiserver computing environment is disclosed. The method and system employ a technique in which the query is distributed among each of a plurality of partial index servers in the multiserver environment, and a subset of results is calculated for each of the plurality of partial index servers. Then, the subset of results are merged in one logical index server to generate a merged result.

## Claims

### Claim 1

A method of executing an information retrieval query in a multiserver computing environment, the method comprising:
requesting N unsorted results with an offset M from a first of a plurality of partial index servers in the multiserver computing environment,
receiving the N unsorted results, the N unsorted results having keys K1, . . . , KN;
requesting M unsorted results from each other of the plurality of partial index servers, the request for the M unsorted results defining that each of the N unsorted results has the same keys Kj of the respective N unsorted results requested from the first of the plurality of partial index servers, and wherein (1≦j≦N);
calculating a subset of results for each of the plurality of partial index servers; and
merging the subset of results in one logical index server to generate a merged result.

### Claim 2 (depends on 1)

A method in accordance with claim 1, further comprising receiving the query from a frontend computer system.

### Claim 3 (depends on 2)

A method in accordance with claim 2, further comprising sending the merged result to the frontend computer system.

### Claim 4

A method of executing an information retrieval query in a multiserver computing environment, the method comprising:
distributing the query among each of a plurality of partial index servers in the multiserver environment by:
requesting N sorted results with an offset M from each of the plurality of partial index servers;
merging C results from each of the plurality of partial index servers in one logical index server, wherein C is much greater than N and represents an upper bound on the number of results that needs to be considered in order to obtain the N results required, the value C being determined by:
first determining a sum G of the Cth aggregate values for the plurality of partial index servers; and
second determining a value H representing the (N+M)th aggregate value; and if G≦H, resetting C to a new value;
obtaining missing aggregate values from each partial server that did not send particular keys using the new value of C to generate supplemental results; and
merging the C results and the supplemental results by the logical index server.

### Claim 5

A method of executing a query in a multiserver computing environment for N sorted results with offset M, the method comprising:
initiating a query on each of a plurality of partial index servers;
evaluating results of the query in parallel on each of the plurality of partial index servers;
sending a predefined number of top partial results from each of the partial index servers to a logical server;
merging the sent top partial results from the respective partial index servers by the logical server;
determining whether the predefined number is sufficiently large to return results from one or more of the partial index servers for one or more keys;
finding deltas for keys missing on one or more of the partial index servers;
discarding merged aggregate values below the predefined number on the logical server;
selecting missing aggregate values from the partial index servers having missing keys; and
merging all obtained results.