RANDOM NUMBER GENERATOR IN A PARALLEL PROCESSING DATABASE

• US 20150278309A1
• Filed: 09/28/2013
• Published: 10/01/2015
• Est. Priority Date: 09/29/2012
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Gopivotal, Inc. (Broadcom, Inc.)
• Inventors: Harada, Hitoshi, Welton, Caleb E., Schoppmann, Florian
• Granted Patent: US 10,061,562 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/582 Pseudo-random number generators

Abstract

A random number generation process generated uncorrelated random numbers from identical random number sequences on parallel processing database segments of an MPP database without communications between the segments by establishing a different starting position in the sequence on each segment using an identifier that is unique to each segment, query slice information and the number of segments. A master node dispatches a seed value to initialize the random number sequence generation on all segments, and dispatches the query slice information and information as to the number of segments, during a normal query plan dispatch process.

Claims

1. A method of generating random numbers on parallel processing segments of a massively parallel processing (MPP) database, comprising:

generating a same random number sequence on each segment;

establishing on each segment a different starting position in the random number sequence generated on said each segment;

calculating a step size that determines return positions in the random number sequence generated on said each segment at which random numbers are returned, the step size being the same on all segments, the step size corresponding to a number of query slices and a number of segments, wherein a larger number of query slices and a larger number of segments correspond to a large step size, wherein each query slice is a partition of a relational database query; and

returning uncorrelated random numbers at said return positions in the random number sequence at said segments.

2. The method of claim 1 further comprising dispatching a common seed value to each segment from a master node of said database, and wherein said generating comprises generating the same random number sequence at each segment.

3. The method of claim 2, wherein the relational database query is an incoming query received by said master node, and wherein said dispatching further comprises including with said seed value an identifier related to said relational database query.

4. The method of claim 1, wherein said establishing a different starting position in the random number sequence generated on each segment comprises establishing the starting position on each particular segment using an identifier that is unique to such segment.

5. The method of claim 4, wherein a master node subdivides the relational database query into the query slices, each query slice being dispatched to all segments for processing, and wherein said establishing a starting position further comprises using a slice identifier.

6. The method of claim 5, wherein the master node dispatches to the segments information as to the number of segments, and said establishing a starting position further comprises using said information as to the number of segments.

7. The method of claim 1, wherein calculating said step size comprises calculating a product of the number of segments in said database and the number of query slices and designating the product as the step size.

8. Computer readable non-transitory storage medium product embodying instructions for controlling the operation of a computer to generate random numbers on parallel processing segments of a massively parallel processing (MPP) database, comprising instructions for:

generating the same random number sequence on each segment;

establishing on each segment a different starting position in the random number sequence generated on said each segment;

calculating a step size that determines return positions in the random number sequence generated on said each segment at which random numbers are returned, the step size being the same on all segments, the step size corresponding to a number of query slices and a number of segments, wherein a larger number of query slices and a larger number of segments correspond to a large step size, wherein each query slice is a partition of a relational database query; and

returning uncorrelated random numbers at said return positions in the random number sequence at said segments.

9. The computer readable product of claim 8 further comprising instructions for dispatching a common seed value to each segment from a master node of said database, and wherein said generating comprises generating the same random number sequence at each segment.

10. The computer readable product of claim 9, wherein the relational database query is an incoming query received by said master node, and wherein said dispatching further comprises including with said seed value an identifier related to said relational database query.

11. The computer readable product of claim 8, wherein said establishing a different starting position in the random number sequence generated on each segment comprises establishing the starting position on each particular segment using an identifier that is unique to such segment.

12. The computer readable product of claim 11, wherein a master node subdivides the relational database query into the query slices, each query slice being dispatched to all segments for processing, and wherein said establishing a starting position further comprises using a slice identifier.

13. The computer readable product of claim 12, wherein the master node dispatches to the segments information as to the number of segments, and said establishing a starting position further comprises using said information as to the number of segments.

14. The computer readable product of claim 8, wherein calculating said step size comprises calculating a product of the number of segments in said database and the number of query slices and designating the product as the step size.

15. A system comprising:

a plurality of processors;

a non-transitory storage medium storing computer instructions operable to cause the processors to perform operations comprising;

generating a same random number sequence on each segment;

establishing on each segment a different starting position in the random number sequence generated on said each segment;

calculating a step size that determines return positions in the random number sequence generated on said each segment at which random numbers are returned, the step size being the same on all segments, the step size corresponding to a number of query slices and a number of segments, wherein a larger number of query slices and a larger number of segments correspond to a large step size, wherein each query slice is a partition of a relational database query; and

returning uncorrelated random numbers at said return positions in the random number sequence at said segments.

16. A method comprising:

receiving, by a computing device, a query plan, the query plan specifying that a relational database query is partitioned into one or more query slices, each query slice being a portion of operations of the query, each query slice being executable on one or more segment nodes independently of another query slice, each segment node being a node of a parallel processing database system comprising a plurality of nodes each having a processor that is independent of a processor of another node;

determining a partition plan of partitioning a master random number sequence to each of the segment nodes, wherein determining the partition plan comprises determining a step size based on a count of query slices and a count of segment nodes of the parallel processing database system, wherein the step size in the partition plan usable to specify uncorrelated subsets of the master random sequence for each different combination of a query slice and a segment node, and wherein a larger count of query slices and a larger count of segment nodes correspond to a larger step size;

dispatching each query slice to at least one of the segment nodes according to the partition plan, including designating a different subset of the master random sequence to each different query slice and segment node combination based on the step size and an offset, each offset corresponding to a position of a segment node in an ordered list of segment nodes and a position of the query slice in an order list of query slices; and

executing each query slice, including returning a random number in response to a call to a random function in the query slice, the random number being a number in the master random number sequence selected based on the step size and offset.

17. The method of claim 16, wherein determining the step size comprises designating a product of the count of query slices and the count of segment nodes of the parallel processing database system as the step size.

18. The method of claim 16, wherein each query slice is a singleton slice or a distributed slice, wherein the singleton slice is executable on one segment node of the parallel processing database system and the distributed slice is executable on each segment node of the parallel processing database system.

19. The method of claim 18, wherein the step size is determined based on calculations comprising:

multiplying the count of segment nodes by a number of distributed slices among the query slices; and

designating a sum of a count of singleton slices and a product of the multiplying as the step size.

20. The method claim 18, wherein dispatching each query slice to at least one of the segment nodes comprises:

dispatching each distributed slice to each segment node, and

dispatching each singleton slice to one of the segment nodes.

21. The method of claim 16, wherein:

a master node parallel processing database system dispatches a common seed value to each segment from a master node of said database, and

executing the query slices comprises generating the master random number sequence at each segment node using the common seed and selecting a subset of random numbers from the master random number sequence using the step size, the offset, and a position of each segment node in the ordered list of segment nodes.

22. The method of claim 16, wherein the list of query slices is ordered by identifier of each query slice, and the list of segment nodes is ordered by identifier of each segment node.

23. A non-transitory computer-readable medium storing instructions to cause a plurality of processors to perform operations comprising:

receiving a query plan, the query plan specifying that a relational database query is partitioned into one or more query slices, each query slice being a portion of operations of the query, each query slice being executable on a segment node independently of another portion of the query, the segment node being a node of a parallel processing database system comprising a plurality of nodes each having a processor that is independent of a processor of another node;

determining a partition plan of partitioning a master random number sequence to each of the segment nodes, wherein determining the partition plan comprises determining a step size based on a count of query slices and a count of segment nodes of the parallel processing database system, wherein the step size in the partition plan usable to specify uncorrelated subsets of the master random sequence for each different combination of a query slice and a segment node, and wherein a larger count of query slices and a larger count of segment nodes correspond to a larger step size;

dispatching each query slice to at least one of the segment nodes according to the partition plan, including designating a different subset of the master random sequence to each different query slice and segment node combination based on the step size and an offset, each offset corresponding to a position of a segment node in an ordered list of segment nodes and a position of the query slice in an order list of query slices; and

executing each query slice, including returning a random number in response to a call to a random function in the query slice, the random number being a number in the master random number sequence selected based on the step size and offset.

24. The non-transitory computer-readable medium of claim 23, wherein determining the step size comprises designating a product of the count of query slices and the count of nodes of the parallel processing database system as the step size.

25. The non-transitory computer-readable medium of claim 23, wherein each query slice is a singleton slice or a distributed slice, wherein the singleton slice is executable on one segment node of the parallel processing database system and the distributed slice is executable on each segment node of the parallel processing database system.

26. The non-transitory computer-readable medium of claim 25, wherein the step size is determined based on calculations comprising:

multiplying the count of segment nodes by a number of distributed slices among the query slices; and

designating a sum of a count of singleton slices and a product of the multiplying as the step size.

27. The non-transitory computer-readable medium claim 25, wherein dispatching each query slice to at least one of the segment nodes comprises:

dispatching each distributed slice to each segment node, and dispatching each singleton slice to one of the segment nodes.

28. The non-transitory computer-readable medium of claim 23, wherein:

a master node parallel processing database system dispatches a common seed value to each segment from a master node of said database, and

executing the query slices comprises generating the master random number sequence at each segment node using the common seed and selecting a subset of random numbers from the master random number sequence using the step size, the offset, and an identifier of a node on which the corresponding query slice executes.

29. The non-transitory computer-readable medium of claim 23, wherein the list of query slices is ordered by identifier of each query slice, and the list of segment nodes is ordered by identifier of each segment node.

30. A system comprising:

a plurality of processors; and

a non-transitory computer-readable medium storing instructions to cause the processors to perform operations comprising;

receiving, by a computing device, a query plan, the query plan specifying that a relational database query is partitioned into one or more query slices, each query slice being a portion of operations of the query, each query slice being executable on one or more segment nodes independently of another query slice, each segment node being a node of a parallel processing database system comprising a plurality of nodes each having a processor that is independent of a processor of another node;

determining a partition plan of partitioning a master random number sequence to each of the segment nodes, wherein determining the partition plan comprises determining a step size based on a count of query slices and a count of segment nodes of the parallel processing database system, wherein the step size in the partition plan usable to specify uncorrelated subsets of the master random sequence for each different combination of a query slice and a segment node, and wherein a larger count of query slices and a larger count of segment nodes correspond to a larger step size;

dispatching each query slice to at least one of the segment nodes according to the partition plan, including designating a different subset of the master random sequence to each different query slice and segment node combination based on the step size and an offset, each offset corresponding to a position of a segment node in an ordered list of segment nodes and a position of the query slice in an order list of query slices; and

executing each query slice, including returning a random number in response to a call to a random function in the query slice, the random number being a number in the master random number sequence selected based on the step size and offset.

31. The system of claim 30, wherein determining the step size comprises designating a product of the count of query slices and the count of segment nodes of the parallel processing database system as the step size.

32. The system of claim 30, wherein each query slice is a singleton slice or a distributed slice, wherein the singleton slice is executable on one segment node of the parallel processing database system and the distributed slice is executable on each segment node of the parallel processing database system.

33. The system of claim 32, wherein the step size is determined based on calculations comprising:

multiplying the count of segment nodes by a number of distributed slices among the query slices; and

designating a sum of a count of singleton slices and a product of the multiplying as the step size.

34. The system of claim 32, wherein dispatching each query slice to at least one of the segment nodes comprises:

dispatching each distributed slice to each segment node, and

dispatching each singleton slice to one of the segment nodes.

35. The system of claim 30, wherein:

a master node parallel processing database system dispatches a common seed value to each segment from a master node of said database, and

executing the query slices comprises generating the master random number sequence at each segment node using the common seed and selecting a subset of random numbers from the master random number sequence using the step size, the offset, and a position of each segment node in the ordered list of segment nodes.

36. The system of claim 30, wherein the list of query slices is ordered by identifier of each query slice, and the list of segment nodes is ordered by identifier of each segment node.