Maintaining sort order of data in databases

• US 9,251,155 B1
• Filed: 03/15/2013
• Issued: 02/02/2016
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Paraccel Incorporated (Actian Corporation)
• Original Assignee: Paraccel Incorporated (Actian Corporation)
• Inventors: Galimberti, David Benedict, Chu, Brian Pak-ning
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US13/835,892
• Time in Patent Office: 1,054 Days
• Field of Search: 707/807, 707/752, 707/753, 707/803, 707/756
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

A database system maintains table data in sorted order. The table data becomes unsorted over time due to add, delete, and update operations. These operations are performed such that the table comprises an initial sorted region followed by an unsorted region. The database system performs an incremental operation to rewrite the table in sorted order. The database system partitions the unsorted region into a plurality of partitions comprising sorted rows within each partition. The database system iteratively merges rows from the partitions to the sorted region of the table. The database system selects a set of lowest tanked rows from the partitions. The database system merges these lowest ranked rows with the sorted region while maintaining the sort order of the sorted region. The database system repeats these steps until all the partitions are processed. The database may store data in columnar fashion.

Claims

1. A computer implemented method for maintaining sort order of data in a database, the method comprising:

storing 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;

partitioning 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 merging data from the unsorted set of rows to the sorted set of rows, the incremental merging comprising, iteratively;

selecting 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, identifying a block corresponding to a last row of the selected set of rows being merged; and

for each column, storing 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

merging the selected set of rows with the sorted set of rows.

2. The method of claim 1, further comprising:

receiving a request to modify the input table; and

adding a row to the unsorted set of rows based on the request to modify the input table.

3. The method of claim 1, further comprising:

receiving a request to add a new row to the input table; and

adding the new row to the unsorted set of rows.

4. The method of claim 1, further comprising:

receiving a request to delete a row from the sorted set of rows of the input table; and

marking a storage space of each column of the deleted row in the sorted set of rows as unused.

5. The method of claim 1, further comprising:

receiving a request to update a row from the sorted set of rows of the input table;

deleting the row from the sorted set of rows, the deleting comprising, marking a storage space of each column of the deleted row in the sorted set of rows as unused; and

adding the updated row to the unsorted set of rows.

6. The method of claim 1, further comprising:

storing the merged sorted set of rows in a staging table, wherein responsive to verifying that there are no rows remaining in the plurality of subsets of rows, indicating that the staging table comprises data of the input table in sorted order.

7. The method of claim 1, wherein merging the selected set of rows with the sorted set of rows comprises ignoring any deleted rows in the input table while storing the merged sorted set of rows.

8. 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.

9. The computer-readable storage medium of claim 8, wherein the code further causes the processor to:

receive a request to modify the input table; and

add a row to the unsorted set of rows based on the request to modify the input table.

10. The computer-readable storage medium of claim 8, wherein the code further causes the processor to:

receive a request to update a row from the sorted set of rows of the input table;

delete the row from the sorted set of rows, the deleting comprising, marking a storage space of each column of the deleted row in the sorted set of rows as unused; and

add the updated row to the unsorted set of rows.

11. 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.

12. The computer-implemented system of claim 11, wherein the vacuum process manager is further configured to:

receive a request to modify the input table; and

add a row to the unsorted set of rows based on the request to modify the input table.

13. The computer-implemented system of claim 11, wherein the vacuum process manager is further configured to:

receive a request to update a row from the sorted set of rows of the input table;

delete the row from the sorted set of rows, the deleting comprising, marking a storage space of the deleted row in the sorted set of rows as unused; and

add the updated row to the unsorted set of rows.