Multiple pass sort with subset splitting
A system for multipass sort with subsplitting includes a communication interface and a processor. The communication interface is configured to receive from a client device a request to sort a dataset that includes a plurality of rows, where the size of the dataset is greater than a threshold size. The processor is configured to: subdivide the dataset into a plurality of data subsets; sort each of the plurality of data subsets; merge the plurality of sorted data subsets utilizing a binary merge tree to generate a sorted dataset; and provide the sorted dataset to the client device.
1. A method, comprising:
receiving from a client device a request to sort a dataset that includes a plurality of rows, the request specifying a sorting order for the plurality of rows;
subdividing the dataset into a plurality of data subsets, each data subset comprising one or more of the plurality of rows;
performing, in a memory of a database system, an in-cache sort on each of the plurality of data subsets, each sorted data subset comprising sorted rows in the sorting order;
merging the plurality of sorted data subsets utilizing a binary merge tree to generate a sorted dataset, wherein the binary merge tree includes at least a root node and a plurality of leaf nodes, each leaf node corresponding to a respective sorted data subset, and utilizing the binary merge tree to generate the sorted dataset comprises:
merging the sorted data subsets from the plurality of leaf nodes to the root node comprising merging a first plurality of rows associated with a first sorted subset corresponding to a first leaf node with a second plurality of rows associated with a second sorted subset corresponding to a second leaf node into merged rows represented by an interior node of the binary merge tree, and
generating the sorted dataset with the merged rows in the sorting order; and
providing the sorted dataset to the client device.
2. The method of claim 1 , wherein the dataset is subdivided into an even number of data subsets.
3. The method of claim 1 , wherein the dataset is subdivided into an odd number of data subsets.
4. The method of claim 1 , wherein the interior node of the binary merge tree includes a fixed-sized buffer to store a plurality of rows merged from the first subset and the second subset.
5. The method of claim 1 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree includes comparing a row referenced by a first pointer associated with the first sorted subset with a row referenced by a second pointer associated with the second sorted subset.
6. The method of claim 5 , wherein the row referenced by the first pointer associated with the first sorted subset is compared with the row referenced by the second pointer associated with the second sorted subset using corresponding prefixes.
7. The method of claim 5 , wherein the row referenced by the first pointer associated with the first sorted subset is compared with the row referenced by the second pointer associated with the second sorted subset using corresponding offset value codes.
8. The method of claim 5 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes determining a winning pointer and a losing pointer based on the comparison.
9. The method of claim 8 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes comparing a number of wins associated with the winning pointer to a consecutive win threshold.
10. The method of claim 9 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes copying a row referenced by the winning pointer is copied to the interior node and advancing the winning pointer to reference a next row in a subset associated with the winning pointer in response to determining that the number of wins associated with the winning pointer is less than the consecutive win threshold.
11. The method of claim 9 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes increasing a pointer stride length for the winning pointer according to a pattern in response to a determination that the number of wins associated with the winning pointer is equal to the consecutive win threshold.
12. The method of claim 11 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes comparing a row associated with the increased stride length pointed by the winning pointer to a row pointed by the losing pointer.
13. The method of claim 12 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes determining whether the winning pointer is still the winning pointer.
14. The method of claim 13 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes copying the row pointed by the losing pointer into the interior node in response to determining that the winning pointer is no longer the winning pointer.
15. The method of claim 13 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes copying the row associated with the increased stride length pointed by the winning pointer into the interior node in response to determining that the winning pointer is still the winning pointer.
16. The method of claim 13 , wherein merging the first plurality of rows associated with the first sorted subset corresponding to the first leaf node with the second plurality of rows associated with the second sorted subset corresponding to the second leaf node into the interior node of the binary merge tree further includes copying the row associated with the increased stride length pointed by the winning pointer and/or the one or more rows skipped as a result of increasing the pointer stride length associated with the winning pointer into the interior node in response to determining that the winning pointer is still the winning pointer.
17. A system, comprising:
a communication interface configured to receive from a client device a request to sort a dataset that includes a plurality of rows, the request specifying a sorting order for the plurality of rows;
a processor coupled to the communication interface and configured to:
subdivide the dataset into a plurality of data subsets, each data subset comprising one or more of the plurality of rows;
perform, in a memory of a database system, an in-cache sort on each of the plurality of data subsets, each sorted data subset comprising sorted rows in the sorting order;
merge the plurality of sorted data subsets utilizing a binary merge tree to generate a sorted dataset, wherein the binary merge tree includes at least a root node and a plurality of leaf nodes, each leaf node corresponding to a respective sorted data subset, and utilizing the binary merge tree to generate the sorted dataset comprises:
merging the sorted data subsets from the plurality of leaf nodes to the root node comprising merging a first plurality of rows associated with a first sorted subset corresponding to a first leaf node with a second plurality of rows associated with a second sorted subset corresponding to a second leaf node into merged rows represented by an interior node of the binary merge tree, and
generating the sorted dataset with the plurality of merged rows in the sorting order; and
provide the sorted dataset to the client device.
18. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:
receiving from a client device a request to sort a dataset that includes a plurality of rows, the request specifying a sorted order for the plurality of rows;
subdividing the dataset into a plurality of data subsets, each data subset comprising one or more of the plurality of rows;
performing, in a memory of a database system, an in-cache sort on each of the plurality of data subsets, each sorted data subset comprising sorted rows in the sorted order;
merging the plurality of sorted data subsets utilizing a binary merge tree to generate a sorted dataset wherein the binary merge tree includes a root node and a plurality of leaf nodes, each leaf node corresponding to a sorted data subset, and utilizing the binary merge tree to generate the sorted dataset comprises:
merging the sorted data subsets from the plurality of leaf nodes to the root node comprising merging a first plurality of rows associated with a first sorted subset corresponding to a first leaf node with a second plurality of rows associated with a second sorted subset corresponding to a second leaf node into merged rows represented by an interior node of the binary merge tree, and
generating the sorted dataset with the merged rows in the sorting order; and
providing the sorted dataset to the client device.