×

Sorting large data sets

  • US 8,478,755 B2
  • Filed: 04/20/2006
  • Issued: 07/02/2013
  • Est. Priority Date: 04/20/2006
  • Status: Active Grant
First Claim
Patent Images

1. A method for sorting a data set, the method performed on a computing device, the method comprising:

  • first processing all of a plurality of portions that make up the data set, the first processing comprising performing, for each portion of the plurality of portions, the following;

    determining usable physical memory of the computing device, where the usable physical memory is system memory of the computing device that is not virtual memory and that is also not processor cache memory, and where the usable physical memory is determined based on a total amount of the system memory that is currently in-use and a total amount of the system memory;

    reading the each portion into the determined usable physical memory, where a size of the each portion comprises a number of records of the data set that fit into the usable physical memory without requiring use of the virtual memory;

    second processing all of a plurality of sub-portions of the each portion, the second processing comprising performing, for each sub-portion of the plurality of sub-portions, the following;

    determining usable processor cache memory of a processor of the computing device, where the usable processor cache memory is determined based on a total amount of the processor cache memory that is currently in-use and a total amount of the processor cache memory;

    sorting, by the processor, the each sub-portion within the determined usable processor cache memory, where the each sub-portion fits entirely in the determined usable processor cache memory, and where the sorted sub-portion is reflected in the determined usable physical memory based on normal operations of the processor cache memory;

    merging the first-processed portions and second-processed sub-portions resulting in the entire data set being sorted where all the sorting was performed within processor cache memory and without making use of virtual memory.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×