Random number generator in a parallel processing database

Patent metadata

Field	Value
Publication number	US-10922053-B2
Application number	US-201916667706-A
Country	US
Kind code	B2
Filing date	Oct 29, 2019
Priority date	Sep 29, 2012
Publication date	Feb 16, 2021
Grant date	Feb 16, 2021

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.

First claim

What is claimed is:

1. A system comprising:
a massively parallel processing database system comprising a master node and a plurality of segment nodes, the master node and each of the plurality of segment nodes comprising one or more respective computers; and
one or more non-transitory computer storage media encoded with computer program instructions that when executed by computers of the massively parallel processing database system cause the computers to perform operations comprising:
receiving, by the master node, a query that specifies a random number operator that, when executed on a database relation, specifies the generation of a respective random number for each row of the database relation;
computing by each segment node of the plurality of segment nodes, a respective step value that specifies how many values in a master sequence of random numbers to skip when selecting random numbers for the random number operator;
computing, by each segment node of the plurality of segment nodes, a respective offset that specifies a starting position in the master sequence of random numbers; and
generating, by each segment node of the plurality of segment nodes for one or more rows of a respective partition of the database relation assigned to the segment node, respective random numbers from the master sequence of random numbers starting from the respective offset computed by the segment node and repeatedly skipping a number of random numbers in the master sequence specified by the step value computed by the segment node.

2. The system of claim 1 , wherein computing the respective step value comprises designating the number of the plurality of segments nodes as the step value.

3. The system of claim 1 , wherein computing the respective offset comprises determining a position of the respective segment node in an ordered list of the plurality of segment nodes and designating the position as the respective offset.

4. The system of claim 1 , further comprising:
providing, by the master node to each segment node of the plurality of segment nodes, a starting seed value for a random number generation procedure that is configured to generate a same master sequence of random numbers when started from a same starting seed value, wherein the starting seed value is generated using an identifier associated with the query, and wherein different queries are associated with different identifiers.

5. The system of claim 1 , further comprising:
providing, by the master node to each segment node of the plurality of segment nodes, a starting seed value for a random number generation procedure that is configured to generate a same master sequence of random numbers when started from a same starting seed value, wherein the starting seed value is generated using an identifier associated with the query, and wherein same queries are associated with same identifiers.

6. The system of claim 1 , wherein the query is divided by the master node into two or more query slices, wherein each query slice computes a portion of the output of the random number operator.

7. The system of claim 6 , wherein computing the respective step value comprises multiplying the number of the query slices with the number of the segment nodes.

8. A method comprising:
maintaining a massively parallel processing database system comprising a master node and a plurality of segment nodes, the master node and each of the plurality of segment nodes comprising one or more respective computers;
receiving, by the master node, a query that specifies a random number operator that, when executed on a database relation, specifies the generation of a respective random number for each row of the database relation;
computing by each segment node of the plurality of segment nodes, a respective step value that specifies how many values in a master sequence of random numbers to skip when selecting random numbers for the random number operator;
computing, by each segment node of the plurality of segment nodes, a respective offset that specifies a starting position in the master sequence of random numbers; and
generating, by each segment node of the plurality of segment nodes for one or more rows of a respective partition of the database relation assigned to the segment node, respective random numbers from the master sequence of random numbers starting from the respective offset computed by the segment node and repeatedly skipping a number of random numbers in the master sequence specified by the step value computed by the segment node.

9. The method of claim 8 , wherein computing the respective step value comprises designating the number of the plurality of segments nodes as the step value.

10. The method of claim 8 , wherein computing the respective offset comprises determining a position of the respective segment node in an ordered list of the plurality of segment nodes and designating the position as the respective offset.

11. The method of claim 8 , further comprising:
providing, by the master node to each segment node of the plurality of segment nodes, a starting seed value for a random number generation procedure that is configured to generate a same master sequence of random numbers when started from a same starting seed value, wherein the starting seed value is generated using an identifier associated with the query, and wherein different queries are associated with different identifiers.

12. The method of claim 8 , further comprising:
providing, by the master node to each segment node of the plurality of segment nodes, a starting seed value for a random number generation procedure that is configured to generate a same master sequence of random numbers when started from a same starting seed value, wherein the starting seed value is generated using an identifier associated with the query, and wherein same queries are associated with same identifiers.

13. The method of claim 8 , wherein the query is divided by the master node into two or more query slices, wherein each query slice computes a portion of the output of the random number operator.

14. The method of claim 13 , wherein computing the respective step value comprises multiplying the number of the query slices with the number of the segment nodes.

15. A non-transitory computer storage medium encoded with a computer program, the computer program storing instructions that when executed by one or more computers causes the one or more computers to perform operations comprising:
maintaining a massively parallel processing database system comprising a master node and a plurality of segment nodes, the master node and each of the plurality of segment nodes comprising one or more respective computers;
receiving, by the master node, a query that specifies a random number operator that, when executed on a database relation, specifies the generation of a respective random number for each row of the database relation;
computing by each segment node of the plurality of segment nodes, a respective step value that specifies how many values in a master sequence of random numbers to skip when selecting random numbers for the random number operator;
computing, by each segment node of the plurality of segment nodes, a respective offset that specifies a starting position in the master sequence of random numbers; and
generating, by each segment node of the plurality of segment nodes for one or more rows of a respective partition of the database relation assigned to the segment node, respective random numbers from the master sequence of random numbers starting from the respective offset computed by the segment node and repeatedly skipping a num

Assignees

• Pivotal Software Inc

Inventors

• Harada Hitoshi
• Welton Caleb E
• Schoppmann Florian

Classifications

• G06F7/58

  Random or pseudo-random number generators · CPC title

• G06F16/2471

  Distributed queries · CPC title

• G06F7/582 Primary

  Pseudo-random number generators · CPC title