A record processing and storage system is operable to receive a set of records for storage. The set of records are included in a plurality of pages stored by a page storage system, and each page of the plurality of pages includes a plurality of records in the set of records. Key value-based record distribution data is generated for the set of records based on a plurality of cluster key values of the set of records. A cluster key domain spanned by the plurality of cluster key values is divided into a plurality of key space sub-intervals based on the key value-based record distribution data. The set of records are segregated into a plurality of row subsets corresponding to the plurality of key space sub-intervals. A plurality sets of segments are generated by processing the plurality of row subsets in parallel.