Maintaining sort order of data in databases

A non-transitory computer-readable storage medium storing computer-executable code for maintaining sort order of data in a database, the code, when executed by a processor, causing the processor to:

• store an input table in columnar fashion, wherein the input table is stored as a sorted set of rows followed by an unsorted set of rows;
• partition the unsorted set of rows into a plurality of subsets of rows wherein each subset of rows comprises data stored in sorted order within the subset of rows;
• and
• incrementally merge data from the unsorted set of rows to the sorted set of rows, the incremental merging comprising, iteratively:
• select a set of rows from the plurality of subsets of rows, wherein the selected set of rows comprises rows with lowest rank in the sort order across the plurality of subsets of rows;
• for each column, identify a block corresponding to a last row of the selected set of rows being merged;
• and
• for each column, store the rows following the last row of the set of rows from the identified block in a new block, wherein the new block for each column is for processing in the next iteration;
• and
• merge the selected set of rows with the sorted set of rows.

A computer-implemented system for maintaining sort order of data in a database, the system comprising:

• a computer processor;
• and
• a non-transitory computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising:
• a vacuum process manager configured to:
• store an input table in columnar fashion, wherein the input table is stored as a sorted set of rows followed by an unsorted set of rows region;
• partition the unsorted set of rows into a plurality of subsets of rows wherein each subset of rows comprises data stored in sorted order within the subset of rows;
• and
• incrementally merge data from the unsorted set of rows to the sorted set of rows, the incremental merging comprising, iteratively:
• select a set of rows from the plurality of subsets of rows, wherein the selected set of rows comprises rows with lowest rank in the sort order across the plurality of subsets of rows;
• for each column, identify a block corresponding to a last row of the selected set of rows being merged;
• and
• for each column, store the rows following the last row of the set of rows from the identified block in a new block, wherein the new block for each column is for processing in the next iteration;
• and
• merge the selected set of rows with the sorted set of rows.