Sorting by permutation
AssigneeAmazon Technologies, Inc.
InventorsTerence Kelly, Andrew Edward Caldwell, Carlos Garcia-Alvarado, Vijairam Parasuraman
Life of this patent
Estimating the term…
Abstract
A system such as a database management system determines a rule to impose sorted order upon a column without applying a sorting algorithm to the column and stores the rule to be applied to sort the column. In an embodiment, a permutation is the rule. The column, in an embodiment, is a column of a database table. In some cases, the rule is used to efficiently impose a correct sorted order on a subset of unsorted columns without the use of a sorting algorithm. In some cases, the rule is generated based at least in part on another column that is sorted using a sorting algorithm such as quicksort.
Claims19
A computer-implemented method, comprising:
- without sorting a second column of a database table, using a sorting algorithm to sort a first column of the database table that comprises multiple rows such that a value in a row indicated by a row index of the first column is stored in a different row of the first column;
- generating a permutation column resulting from sorting the first column to track a new sort order for ordering the second column, wherein the permutation column, for a first row of the database table, stores a first index value that indicates an index of the different row of the database table where a second value stored in a second column of the first row should be placed to order the second column;
- storing the permutation column in association with the database table, a mapping table indicating the association, wherein the mapping table is stored separately from the database table;
- and
- in response to an application programming interface (API) request to access ordered data in the second column:
- obtaining the permutation column based on the mapping table;
- ordering an unsorted array of the second column of the database table based, at least in part, on the API request and the permutation column;
- and
- providing access to the ordered data in the second column.
A system, comprising one or more non-transitory machine-readable media having stored thereon a set of instructions, which, if performed by one or more processors, cause the system to at least:
- without sorting a second column of a database table, sort at least a portion of a first column of the database table such that a value in a row indicated by a row index of the first column is stored in a different row of the first column;
- generate a permutation rule to track a new sort order for ordering the second column by at least storing, in a permutation column at the row index, an index to the different row as the permutation rule at the row index;
- store the permutation column in association with the database table, wherein the permutation column and the database table are associated in a mapping table, and wherein the mapping table is stored separately from the database table;
- and
- in response to an application programming interface (API) request to access ordered data in the second column:
- obtain the permutation column based on the mapping table;
- order the second column of the database table based on the API request and the permutation column;
- and
- provide access to the ordered data in the second column.
A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
- sort at least a portion of a first column of a database, without sorting a second column of the database, by at least storing a value indicated by a row index of the first column in a different row of the first column;
- determine, based at least in part on sorting the first column, a permutation rule, wherein:
- the permutation rule tracks a new sort order for ordering the second column;
- a first value of the permutation rule corresponds to a first row of the database;
- the first value indicates an index of a different row of the database;
- and
- the different row of the database is where a second value, stored in the first row at the second column, should be placed in the second column to order the second column;
- store the permutation rule in a permutation column, in association with the database according to a mapping table, to be applied to impose the new sort order upon the second column, wherein the mapping table is stored separately from the database;
- and
- in response to an application programming interface (API) request, order an unsorted array of the second column of the database, based on the API request and the permutation column associated with the second column in the mapping table.
Dependencies are inferred from the claim text.