US 7,680,791 B2 · Method for sorting data using common prefix bytes

Abstract

Several techniques for sorting item are described, generally referred to as (1) common prefix skipping quicksort; (2) key substring caching; and (3) adaptive quicksort. With common prefix skipping quicksort, common prefix bytes among all key values for a partition are computed while performing a quicksort partitioning operation, and the known common bytes are skipped when comparing two key values in a recursive partitioning operation. With key substring caching, each item is represented in a cached array comprising a particular number of bytes for respective portions of key values (“key substring”), where the key substring cache is updated contain bytes beyond the known number of common prefix bytes. An adaptive quicksort routine is a hybrid of a quicksort function and most significant digit radix sort function, where the functions are mutually recursive.

Claims40

Dependent claims

A method for sorting a set of items, based on one or more sort keys, using a quicksort algorithm, wherein each item in the set of items has one or more key values that are represented by an array of one or more bytes, and wherein the set of items can be ordered based on the arrays, the method comprising the computer-implemented steps of:

while performing a first partitioning operation on the set of items to partition the set of items into subsets of items, based on a first comparison between (a) the key value for each item in the set of items and (b) a first pivot value associated with the first partitioning operation,
determining a total amount of common prefix bytes that exist among all key values for items partitioned into a first subset of items;
and
storing in computer memory a first number that indicates the total amount of common prefix bytes that exist among all key values for items partitioned into the first subset of items;
performing a second partitioning operation on the first subset of items to partition the first subset of items into second subsets of items, based on a second comparison between (a) the key value for each item in the first subset of items and (b) a second pivot value;
wherein, for each item in the first subset of items, the second comparison does not take into account the first number of common prefix bytes associated with the first subset of items;
wherein the method is performed by one or more computing devices.

4 more elements

A computer-readable storage medium that stores instructions for sorting a set of items, based on one or more sort keys, using a quicksort algorithm, wherein each item in the set of items has one or more key values that are represented by an array of one or more bytes, and wherein the set of items can be ordered based on the arrays, which, when executed by one or more processors, cause the one or more processors to perform the steps of:

while performing a first partitioning operation on the set of items to partition the set of items into subsets of items, based on a first comparison between (a) the key value for each item in the set of items and (b) a first pivot value associated with the first partitioning operation,
determining a total amount of common prefix bytes that exist among all key values for items partitioned into a first subset of items;
and
storing in computer memory a first number that indicates the total amount of common prefix bytes that exist among all key values for items partitioned into the first subset of items;
performing a second partitioning operation on the first subset of items to partition the first subset of items into second subsets of items, based on a second comparison between (a) the key value for each item in the first subset of items and (b) a second pivot value;
wherein, for each item in the first subset of items, the second comparison does not take into account the first number of common prefix bytes associated with the first subset of items.

3 more elements

A method for sorting a set of items, based on one or more sort keys, wherein each item in the set of items has one or more key values that are represented by an array of one or more bytes, and wherein the set of items can be ordered based on the arrays, the method comprising the computer-implemented steps of:

representing each item in the set of items with at least (a) a pointer to a location in memory at which the item is stored and (b) a key substring component comprising a respective value of each of a certain number of one or more bytes of the key value for the item, wherein the one or more bytes of the key value are subsequent in order to one or more known common prefix bytes among all key values for items in the set of items;
wherein the key substring component does not represent values of the one or more known common prefix bytes;
and
while performing a partitioning operation on the set of items to group the set of items into subsets of items, comparing (a) from the key substring component, the value of at least a first byte from the certain number of one or more bytes subsequent in order to the common prefix bytes and (b) a pivot value associated with the partitioning operation, to determine whether the key value is different than the pivot value;
wherein the method is performed by one or more computing devices.

2 more elements

A computer-readable storage medium for sorting a set of items, based on one or more sort keys, wherein each item in the set of items has one or more key values that are represented by an away of one or more bytes, and wherein the set of items can be ordered based on the arrays, which, when executed by one or more processors, cause the one or more processors to perform the steps of:

representing each item in the set of items with at least (a) a pointer to a location in memory at which the item is stored and (b) a key substring component comprising a respective value of each of a certain number of one or more bytes of the key value for the item, wherein the one or more bytes of the key value are subsequent in order to one or more known common prefix bytes among all key values for items in the set of items;
wherein the key substring component does not represent values of the one or more known common prefix bytes;
and
while performing a partitioning operation on the set of items to group the set of items into subsets of items, comparing (a) from the key substring component, the value of at least a first byte from the certain number of one or more bytes subsequent in order to the common prefix bytes and (b) a pivot value associated with the partitioning operation, to determine whether the key value is different from the pivot value.

1 more element

while performing a first partitioning operation on the set of items to partition the set of items into first subsets of items, based on a comparison between (a) the key value for each item in the set of items and (b) a first pivot value associated with the first partitioning operation,
computing a common prefix value that identifies a maximum number of one or more common prefix bytes among all key values for items partitioned into a particular first subset of items wherein the key values for the items partitioned into the particular first subset of items have at least one byte that is not in common;
and
determining whether the common prefix value associated with the particular first subset of items is greater than a common prefix value input to the first partitioning operation;
in response to determining that the common prefix value associated with the particular first subset of items is greater than the common prefix value input to the first partitioning operation, performing a second partitioning operation on the particular first subset of items to partition the particular first subset of items into second subsets of items, based on the value of a byte at a location, within the array for an item, that is immediately subsequent in order to the one or more common prefix bytes for items partitioned into the particular first subset of items;
wherein the first partitioning operation is a quicksort partitioning operation and the second partitioning operation is a radix sort partitioning operation;
and
wherein the method is performed by one or more computing devices.

5 more elements

A computer-readable storage medium that stores instructions for sorting a set of items, based on one or more sort keys, wherein each item in the set of items has one or more key values that are represented by an array of one or more bytes, and wherein the set of items can be ordered based on the arrays, which, when executed by one or more processors, cause the one or more processors to perform the steps of:

while performing a first partitioning operation on the set of items to partition the set of items into first subsets of items, based on a comparison between (a) the key value for each item in the set of items and (b) a first pivot value associated with the first partitioning operation,
computing a common prefix value that identifies a maximum number of one or more common prefix bytes among all key values for items partitioned into a particular first subset of items wherein the key values for the items partitioned into the particular first subset of items have at least one byte that is not in common;
and
determining whether the common prefix value associated with the particular first subset of items is greater than a common prefix value input to the first partitioning operation;
in response to determining that the common prefix value associated with the particular first subset of items is greater than the common prefix value input to the first partitioning operation, performing a second partitioning operation on the particular first subset of items to partition the particular first subset of items into second subsets of items, based on the value of a byte at a location, within the array for an item, that is immediately subsequent in order to the one or more common prefix bytes for items partitioned into the particular first subset of items;
wherein the first partitioning operation is a quicksort partitioning operation and the second partitioning operation is a radix sort partitioning operation.

3 more elements

Dependencies are inferred from the claim text.

Method for sorting data using common prefix bytes

Life of this patent

Method for sorting data using common prefix bytes

Life of this patent

Abstract

Claims40