Merging partial query results into a single result
AssigneeSap SE
InventorsJens-Peter Dittrich, Olaf Meincke, Guenter Radestock, Andrew Ross
Life of this patent
Estimating the term…
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.
Claims5
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.
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.
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.
Dependencies are inferred from the claim text.