Integrating map-reduce into a distributed relational database

• US 9,514,188 B2
• Filed: 04/28/2014
• Issued: 12/06/2016
• Est. Priority Date: 04/02/2009
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Cohen, Jeffrey Ira, Lonergan, Luke, Welton, Caleb E.
• Primary Examiner(s): Waldron, Scott A
• Application Number:
  US14/263,641
• Publication Number:
  US 20160224630A1
• Time in Patent Office: 953 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A computer readable storage medium includes executable instructions to define a map-reduce document that coordinates processing of data in a distributed database. The map-reduce document complies with a map-reduce specification that integrates map-reduce functions with queries in a query language. The operations specified by the map-reduce document are executed in the distributed database.

Claims

1. A distributed database comprising:

a plurality of segment hosts each comprising one or more processors; and

a master host comprising one or more processors, wherein;

the master host is programmed to perform operations comprising;

submitting a map-reduce document as an input to a map-reduce program executing on the master host, the map-reducing program configured to cause operations specified in the map-reduce document to be executed in the distributed database system in parallel, wherein the map-reduce document includes comprises an input source and a map-reduce function definition, wherein;

the input source includes a query in Structured Query Language (SQL), and

the map-reduce function definition defines, in a scripting language that is different from SQL, a map function to be performed on the input source and a reduce function to be performed on results of the map function; and

distributing, using the map-reduce program, the map function and reduce function to the segment hosts as tasks; and

each of the segment hosts is programmed to perform the tasks, including executing, as SQL queries, both the map function and reduce function defined in the map-reduce function definition and the query of the input source.

2. The distributed database system of claim 1, wherein the scripting language is PERL or Python.

3. The distributed database system of claim 1, wherein the input source further includes at least one of a file, a table stored in the database system, or an operating system command.

4. The distributed database system of claim 1, wherein the map-reduce program is a parallel file distribution program.

5. The distributed database system of claim 1, wherein the map-reduce function definition comprises executable instructions to process a list of input parameters from the input source to generate a list of output parameters, each of the output parameters having a respective SQL data type and a respective key.

6. The distributed database system of claim 5, wherein the reduce function comprises a transition function with executable instructions to process the list of output parameters into an intermediate state output, the intermediate state output comprising accumulated state values associated with a key.

7. The distributed database system of claim 1, wherein the master host is configured to receive the map-reduce document are received from a client device.

8. A method comprising:

submitting, by a master host of a distributed database system, a map-reduce document as an input to a map-reduce program executing on the master host, the map-reducing program configured to cause operations specified in the map-reduce document to be executed in the distributed database system in parallel, wherein the map-reduce document comprises an input source and a map-reduce function definition, wherein;

the input source includes a query in Structured Query Language (SQL), and

the map-reduce function definition defines, in a scripting language that is different from SQL, a map function to be performed on the input source and a reduce function to be performed on results of the map function; and

distributing, by the master host using the map-reduce program, the map function and reduce function to a plurality of segment hosts of the distributed database system as tasks; and

performing the tasks by the segment hosts, including executing, as SQL queries, both the map function and reduce function defined in the map-reduce function definition and the query of the input source, wherein each host of the distributed database system includes one or more processors.

9. The method of claim 8, wherein the input source further includes at least one of a file, a table stored in the database system, or an operating system command.

10. The method of claim 8, wherein the map-reduce program is a parallel file distribution program.

11. The method of claim 8, wherein the map-reduce function definition comprises executable instructions to process a list of input parameters from the input source to generate a list of output parameters, the output parameters having a SQL data type and a key.

12. The method of claim 11, wherein the reduce function comprises a transition function with executable instructions to process the list of output parameters into an intermediate state output, the intermediate state output comprising accumulated state values associated with a key.

13. A computer readable non-transitory storage medium storing instructions that, when executed by a distributed database system, causes the distributed database system to perform operations comprising:

submitting, by a master host of a distributed database system, a map-reduce document as an input to a map-reduce program executing on the master host, the map-reducing program configured to cause operations specified in the map-reduce document to be executed in the distributed database system in parallel, wherein the map-reduce document comprises an input source and a map-reduce function definition, wherein;

the input source includes a query in Structured Query Language (SQL), and

the map-reduce function definition defines, in a scripting language that is different from SQL, a map function to be performed on the input source and a reduce function to be performed on results of the map function; and

distributing, by the master host using the map-reduce program, the map function and reduce function to a plurality of segment hosts of the distributed database system as tasks; and

performing the tasks by the segment hosts, including executing, as SQL queries, both the map function and reduce function defined in the map-reduce function definition and the query of the input source, wherein each host of the distributed database system includes one or more processors.

14. The computer readable non-transitory storage medium of claim 13, wherein the input source further includes at least one of a file, a table stored in the database system, or an operating system command.

15. The computer readable non-transitory storage medium of claim 13, wherein the map-reduce program is a parallel file distribution program.

16. The computer readable non-transitory storage medium of claim 13, wherein the map-reduce function definition comprises executable instructions to process a list of input parameters from the input source to generate a list of output parameters, the output parameters having a SQL data type and a key.

17. The computer readable non-transitory storage medium of claim 16, wherein the reduce function comprises a transition function with executable instructions to process the list of output parameters into an intermediate state output, the intermediate state output comprising accumulated state values associated with a key.

18. The computer readable non-transitory storage medium of claim 13, wherein the map-reduce document and the map-reduce program are received by the master host from a client device.