Patent ID: 7133858

Claim:
A method, implemented by a computing device, for processing a database query, comprising: partially pre-aggregating records in a database to provide a result that contains at least two records having like grouping column values; aggregating records derived from the result that contains at least two records having like grouping column values to provide a result that contains records having unique grouping column values; and partially pre-aggregating the records in the database only if an estimation, based on a calculation of a probability that a record will be absorbed by a group of records already in memory, indicates that a number of records in the result that contains at least two records having like grouping column values is significantly less than a number of records in the database, wherein the estimation is based on factors comprising: a number of output records, T(N); a number of input records, N; and a relationship T ( N )= M +( N−M )(1− A ( R ( M )))= M +( N−M )Σ i=1 D (1− p i ) R(M) ; wherein M records can fit into memory.