Patent ID: 7502778

Claim:
A computer program product comprising a computer readable storage medium having computer usable program code executed by at least one processor for loading an input data stream into a data structure containing data that is clustered along one or more dimensions, the operations of the computer program product when executing the computer usable program code comprising: generating a hint-key for each of one or more records in the input data stream, wherein the hint-key is a hash value generated using a cell value of each of the one or more records, the cell value comprising a dimension by which the records are to be clustered; ordering the one or more records in a first-level clustering agent to generate one or more record lists ordered by the hint-key of the one or more records; processing one or more record lists in a second-level clustering agent, the second level-clustering agent configured to: process the one or more record lists simultaneously; wherein processing the one or more record lists simultaneously comprises: polling the first record of each of the one or more record lists; selecting the polled first record with the smallest hint-key; removing the selected first record and each record with an equivalent hint-key clustered with the selected first record on the same record list; adding the removed records to a return list; polling again the first record of each of the one or more record lists; comparing the hint-key of the again polled first records to the hint-key of the removed records; processing the return list in response to no polled first records having an equivalent hint-key to the hint-key of the removed records, processing the return list comprising outputting a plurality of partial blocks to a partial block cache; comparing a cell-key of a polled first record to a cell-key of the removed records in response to the hint-key of the polled first record being equivalent to the hint-key of the removed records; selecting the polled first record in response to the cell-key of the polled first record being equivalent to the cell-key of the removed records; removing the selected first record and each record with an equivalent hint-key clustered with the selected first record on the same record list; and adding the removed records to the return list; output the one or more records of the one or more record lists clustered by the hint-key of the one or more records; storing, in the partial block cache, the plurality of partial blocks that are output by the second-level clustering agent, wherein each partial block is associated with a distinct logical cell; and storing, in a partial page cache, a plurality of last partial pages of the partial blocks that have been victimized from the partial block cache.