A method for execution by a record processing and storage system includes assigning each of a plurality of key space sub-intervals of a cluster key domain to a corresponding one of a plurality of processing core resources, and generating a plurality of segments from the set of records via the plurality of processing core resources. Each processing core resource in the plurality of processing core resources generates a subset of the plurality of segments by identifying a proper subset of the set of records based on having cluster key values included in a corresponding one of the plurality of key space sub-intervals, and by generating the subset of the plurality of segments to include the proper subset of the set of records.