Inverse distribution function operations in a parallel relational database
View Patent ↗Inverse distribution operations are performed on a large distributed parallel database comprising a plurality of distributed data segments to determine a data value at a predetermined percentile of a sorted dataset formed on one segment. Data elements from across the segments may be first grouped, either by partitioning keys or by hashing, the groups are sorted into a predetermined order, and data values corresponding to the desired percentile are picked up at a row location of the corresponding data element of each group. For a global dataset that is spread across the database segments, a local sort of data elements is performed on each segment, and the data elements from the local sorts are streamed in overall sorted order to one segment to form the sorted dataset.
1. A method, comprising:
receiving a query that identifies a percentile value, information identifying a dataset stored in a database system, and one or more groups of a plurality of data elements included in the dataset, wherein each data element includes a data value, and wherein the database system comprises a plurality of segment nodes each storing a segment of the dataset and each networked to a master node, wherein each node comprises a computer system;
for each group identified by the query:
sorting data elements in the group in each segment node in parallel to generate a respective sorted segment dataset in each segment node,
storing the sorted dataset segment from each segment node in a respective container on a same segment node,
determining a count of the number of data elements in the group,
at the same segment node, streaming one data element at a time from any of the sorted dataset segments in order of data value of each data element, and
picking the data value corresponding to the percentile value from the streaming data elements using the count; and
providing the picked data value from each group to the master node.
2. The method of claim 1 , further comprising:
grouping the plurality of data elements in each segment node comprising:
hashing the plurality of data elements into hash buckets, wherein each hash bucket identifies a group.
3. The method of claim 1 , further comprising:
grouping the plurality of data elements by querying the plurality of data elements included in the plurality of segment nodes using partitioning keys to partition the plurality of data elements into the one or more groups identified by the query.
4. The method of claim 1 , wherein determining a count comprise:
sorting, in each segment node, the plurality of data elements included in each dataset segment in parallel and determining a segment count of the sorted plurality of data elements included in each dataset segment; and
providing the segment counts to the same segment node and computing, at the same segment node, an addition of each segment count.
5. The method of claim 1 further comprising performing a de-duplication process on data elements in the one or more groups, wherein the process comprises determining counts of same data elements.
6. The method of claim 1 , further comprising:
for each group:
determining that the percentile value is greater than fifty percentile and identifying a particular number of data elements to stream by computing a subtraction of the count from a product of the percentile value times the count; and
at the same segment node, streaming one data element at a time from any of the sorted dataset segments in descending order of data value of each data element.
7. The method of claim 6 , further comprising:
terminating the streaming of data elements upon streaming the particular number of data elements.
8. The method of claim 1 , further comprising:
for each group:
determining that the percentile value is less than fifty percentile and identifying a particular number of data elements to stream by computing a product of the percentile value times the count; and
at the master node, streaming one data element at a time from any of the sorted dataset segments in ascending order of data value of each data element.
9. The method of claim 8 , further comprising:
terminating the streaming of data elements upon streaming the particular number of data elements.
10. A method comprising:
receiving a query that identifies a percentile value, information identifying a dataset stored in a database system that comprises a plurality of data elements, wherein each data element includes a data value, and wherein the database system comprises a plurality of segment nodes each storing a dataset segment of the dataset and each networked to a master node;
sorting the plurality of data elements included in each dataset segment in parallel to generate a respective sorted dataset segment included in each segment node;
storing the respective sorted dataset segments from each segment node on the master node and determining a count
of all the plurality of data elements;
at the master node, streaming one data element at a time from any of the sorted dataset segments in order of data value of each data element; and
picking the data value corresponding to the percentile value from the streaming data elements using the count.
11. The method of claim 10 further comprising:
determining that the percentile value is less than fifty percentile and identifying a particular number of data elements to stream by computing a product of the percentile value times the count; and
at the master node, streaming one data element at a time from any of the sorted dataset segments in ascending order of data value of each data element.
12. The method of claim 11 further comprising:
terminating the streaming of data elements upon streaming the particular number of data elements.
13. The method of claim 10 further comprising performing a de-duplication process on the data elements, wherein the process comprises determining counts of same data elements.
14. The method of claim 10 further comprising:
determining that the percentile value is greater than fifty percentile and identifying a particular number of data elements to stream by computing a subtraction of the count from a product of the percentile value times the count; and
at the master node, streaming one data element at a time from any of the sorted dataset segments in descending order of data value of each data element.
15. The method of claim 14 further comprising:
terminating the streaming of data elements upon streaming the particular number of data elements.
16. The method of claim 10 , wherein determining a count of all the plurality of data elements comprises:
sorting, in each segment node, the plurality of data elements included in each dataset segment in parallel and determining a segment count of the sorted plurality of data elements included in each dataset segment; and
providing the segment counts to the master node and computing, at the master node, an addition of each segment count.
17. Computer readable non-transitory storage medium embodying instructions for controlling the operation of a database system comprising instructions for:
receiving a query that identifies a percentile value, information identifying a dataset stored in a database system, and one or more groups of a plurality of data elements included in the dataset, wherein each data element includes a data value, and wherein the database system comprises a plurality of segment nodes each storing a segment of the dataset and each networked to a master node, wherein each node comprises a computer system;
for each group identified by the query:
sorting data elements in the group in each segment node in parallel to generate a respective sorted segment dataset in each segment node,
storing the sorted dataset segment from each segment node in a respective container on a same segment node,
determining a count of the number of data elements in the group,
at the same segment node, streaming one data element at a time from any of the sorted dataset segments in order of data value of each data element, and
picking the data value corresponding to the percentile value from the streaming data elements using the count; and
providing the picked data value from each group to the master node.
18. Computer readable medium of claim 17 further comprising instructions for performing a de-duplication process on the data elements, wherein the process comprises determining counts of same data elements.
19. Computer readable medium of claim 17 , further comprising instructions for:
for each group:
determining that the percentile value is greater than fifty percentile and identifying a particular number of data elements to stream by computing a subtraction of the count from a product of the percentile value times the count; and
at the same segment node, streaming one data element at a time from any of the sorted dataset segments in descending order of data value of each data element.
20. Computer readable medium of claim 17 , further comprising instructions for:
for each group:
determining that the percentile value is less than fifty percentile and identifying a particular number of data elements to stream by computing a product of the percentile value times the count; and
at the master node, streaming one data element at a time from any of the sorted dataset segments in ascending order of data value of each data element.