Compression-aware partial sort of streaming columnar data

A computer program product for sorting data records comprising:

• a computer readable storage medium having computer readable program code embodied therewith for execution on a processing system, the computer readable program code comprising computer readable program code configured to:
• generate a plurality of data structures, each of which is associated with a different corresponding record field used to sort the data records, and insert values of the record fields into the corresponding data structures, the values of the record fields being received in a plurality of streams, each of the plurality of streams corresponding to a different respective record field and including a sequence of chunks, each of the chunks including values of a record field corresponding to the stream including the chunk;
• insert values of the record fields into corresponding data structures, the values being inserted such that the values are in an order in the corresponding data structures, the inserting comprising:
• for each respective value of each chunk of each stream of the plurality of streams, perform:
• receiving a respective value and an instruction for a respective entry of a respective stream,
• updating the data structure for the respective stream according to the respective value and the instruction, and
• generating an instruction for a corresponding entry of a next stream;
• and
• emit a top predetermined number of the sorted data records, the emitting including reading out the inserted values stored in the plurality of data structures, wherein:
• each of the data structures comprises one or more ordered parts;
• each inserted value is inserted into a corresponding ordered part of the corresponding data structure, the corresponding ordered part further including a count of occurrences of the value;
• and
• each ordered part of a data structure corresponding to a record field having a sort priority immediately below another record field corresponds to a distinct value inserted into an ordered part of the data structure corresponding to the another record field.