Random Number Generator In A MPP Database

• US 20140095526A1
• Filed: 09/29/2012
• Published: 04/03/2014
• Est. Priority Date: 09/29/2012
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Harada, Hitoshi, Welton, Caleb, Schoppmann, Florian
• Granted Patent: US 8,874,602 B2
• Time in Patent Office: Days
• US Class Current: 707/764
• 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 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;

setting 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; 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 generates the same random number sequence at each segment.

3. The method of claim 2, wherein said master node receives an incoming query, and wherein said dispatching further comprises including with said seed value an identifier related to said 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 the master node subdivides an incoming query into slices, a 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 setting said step size comprises setting the step size using the number of segments in said database.

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;

setting 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; 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 generates the same random number sequence at each segment.

10. The computer readable product of claim 9, wherein said master node receives an incoming query, and wherein said dispatching further comprises including with said seed value an identifier related to said 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 the master node subdivides an incoming query into slices, a 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 setting said step size comprises setting the step size using the number of segments in said database.