Parallelization contract - Revision history

Baldy Bill: Successfully de-orphaned! Wikiproject Orphanage: You can help!

2023-09-09T16:26:14Z

Successfully de-orphaned! Wikiproject Orphanage: You can help!

← Previous revision		Revision as of 16:26, 9 September 2023
Line 1:		Line 1:
	{{Orphan\|date=December 2013}}
	{{original research\|date=May 2023}}		{{original research\|date=May 2023}}

Hellacioussatyr: article written by source too close to subject matter

2023-05-09T00:52:48Z

article written by source too close to subject matter

← Previous revision		Revision as of 00:52, 9 May 2023
Line 1:		Line 1:
	{{Orphan\|date=December 2013}}		{{Orphan\|date=December 2013}}
			{{original research\|date=May 2023}}

	The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.		The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.
Line 22:		Line 23:

	Optionally, the user code can be annotated with additional information. These annotations disclose some information on the behavior of the black-box user function. The [[PactCompiler\|PACT Compiler]] can utilize the information to obtain more efficient execution plans. However, while a missing annotation will not change the result of the execution, an incorrect Output Contract produces wrong results.		Optionally, the user code can be annotated with additional information. These annotations disclose some information on the behavior of the black-box user function. The [[PactCompiler\|PACT Compiler]] can utilize the information to obtain more efficient execution plans. However, while a missing annotation will not change the result of the execution, an incorrect Output Contract produces wrong results.


	The currently supported Input Contracts and annotation are presented and discussed in the following.		The currently supported Input Contracts and annotation are presented and discussed in the following.
Line 37:		Line 37:
	== MAP ==		== MAP ==

	The Map Input Contract works in the same way as in MapReduce. It has a single input and assigns each input record to its own subset. Hence, all records are processed independently from each other. \\		The Map Input Contract works in the same way as in MapReduce. It has a single input and assigns each input record to its own subset. Hence, all records are processed independently from each other.



	== REDUCE ==		== REDUCE ==

	The Reduce Input Contract has the same semantics as the reduce function in MapReduce. It has a single input and groups together all records that have identical key fields. Each of these groups is handed as a whole to the user code and processed by it (see figure below). The PACT Programming Model does also support optional Combiners, e.g. for partial aggregations. \\		The Reduce Input Contract has the same semantics as the reduce function in MapReduce. It has a single input and groups together all records that have identical key fields. Each of these groups is handed as a whole to the user code and processed by it (see figure below). The PACT Programming Model does also support optional Combiners, e.g. for partial aggregations.


	== CROSS ==		== CROSS ==

	The Cross Input Contract works on two inputs. It builds the Cartesian product of the records of both inputs. Each element of the Cartesian product (pair of records) is handed to the user code. \\		The Cross Input Contract works on two inputs. It builds the Cartesian product of the records of both inputs. Each element of the Cartesian product (pair of records) is handed to the user code.



	== MATCH ==		== MATCH ==

	The Match Input Contract works on two inputs. From both inputs it matches those records that are identical on their key fields come from different inputs. Hence, it resembles an equality join where the keys of both inputs are the attributes to join on. Each matched pair of records is handed to the user code. \\		The Match Input Contract works on two inputs. From both inputs it matches those records that are identical on their key fields come from different inputs. Hence, it resembles an equality join where the keys of both inputs are the attributes to join on. Each matched pair of records is handed to the user code.


	== COGROUP ==		== COGROUP ==
Line 76:		Line 70:
	== Constant Fields ==		== Constant Fields ==

	The Constant Fields annotation marks fields that are not modified by the user code function. Note that for every input record a constant field may not change its content and position in any output record! In case of binary second-order functions such as Cross, Match, and CoGroup, the user can specify one annotation per input.		The '''Constant Fields''' annotation marks fields that are not modified by the user code function. Note that for every input record a constant field may not change its content and position in any output record! In case of binary second-order functions such as Cross, Match, and CoGroup, the user can specify one annotation per input.

	== Constant Fields Except ==		== Constant Fields Except ==

	The Constant Fields Except annotation is inverse to the Constant Fields annotation. It annotates all fields which might be modified by the annotated user-function, hence the optimizer considers any not annotated field as constant. This annotation should be used very carefully! Again, for binary second-order functions (Cross, Match, CoGroup), one annotation per input can be defined. Note that either the Constant Fields or the Constant Fields Except annotation may be used for an input.		The '''Constant Fields Except''' annotation is inverse to the Constant Fields annotation. It annotates all fields which might be modified by the annotated user-function, hence the optimizer considers any not annotated field as constant. This annotation should be used very carefully! Again, for binary second-order functions (Cross, Match, CoGroup), one annotation per input can be defined. Note that either the Constant Fields or the Constant Fields Except annotation may be used for an input.

	=== PACT Programs ===		=== PACT Programs ===

	PACT programs are constructed as data flow graphs that consist of data sources, PACTs, and data sinks. One or more data sources read files that contain the input data and generate records from those files. Those records are processed by one or more PACTs, each consisting of an Input Contract, user code, and optional code annotations. Finally, the results are written back to output files by one or more data sinks. In contrast to the MapReduce programming model, a PACT program can be arbitrary complex and has no fixed structure. \\		PACT programs are constructed as data flow graphs that consist of data sources, PACTs, and data sinks. One or more data sources read files that contain the input data and generate records from those files. Those records are processed by one or more PACTs, each consisting of an Input Contract, user code, and optional code annotations. Finally, the results are written back to output files by one or more data sinks. In contrast to the MapReduce programming model, a PACT program can be arbitrary complex and has no fixed structure.

	The figure below shows a PACT program with two data sources, four PACTs, and one data sink. Each data source reads data from a specified location in the file system. Both sources forward the data to respective PACTs with Map Input Contracts. The user code is not shown in the figure. The output of both Map PACTs streams into a PACT with a Match Input Contract. The last PACT has a Reduce Input Contract and forwards its result to the data sink.		The figure below shows a PACT program with two data sources, four PACTs, and one data sink. Each data source reads data from a specified location in the file system. Both sources forward the data to respective PACTs with Map Input Contracts. The user code is not shown in the figure. The output of both Map PACTs streams into a PACT with a Match Input Contract. The last PACT has a Reduce Input Contract and forwards its result to the data sink.

Luamssuk: Wikilink: Volker Markl

2021-11-30T16:01:20Z

Wikilink: Volker Markl

← Previous revision		Revision as of 16:01, 30 November 2021
Line 104:		Line 104:

	{{reflist}}		{{reflist}}
	* [https://web.archive.org/web/20120424184436/http://www.stratosphere.eu/files/NephelePACTs_10.pdf "Nephele/PACTs: A Programming Model and Execution Framework for Web-Scale Analytical Processing"]—paper by D. Battré, S. Ewen, F. Hueske, O. Kao, V. Markl, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of ACM SoCC 2010. The paper introduces the PACT programming model, a generalization of MapReduce, developed in the [http://www.stratosphere.eu Stratosphere] research project.		* [https://web.archive.org/web/20120424184436/http://www.stratosphere.eu/files/NephelePACTs_10.pdf "Nephele/PACTs: A Programming Model and Execution Framework for Web-Scale Analytical Processing"]—paper by D. Battré, S. Ewen, F. Hueske, O. Kao, [[Volker Markl\|V. Markl]], and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of ACM SoCC 2010. The paper introduces the PACT programming model, a generalization of MapReduce, developed in the [http://www.stratosphere.eu Stratosphere] research project.
	* [https://web.archive.org/web/20120424184448/http://www.stratosphere.eu/files/ComparingMapReduceAndPACTs_11.pdf "MapReduce and PACT - Comparing Data Parallel Programming Models"]—paper by A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of BTW 2011.		* [https://web.archive.org/web/20120424184448/http://www.stratosphere.eu/files/ComparingMapReduceAndPACTs_11.pdf "MapReduce and PACT - Comparing Data Parallel Programming Models"]—paper by A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of BTW 2011.

Physikerwelt: Remove dead links

2021-01-09T16:37:07Z

Remove dead links

← Previous revision		Revision as of 16:37, 9 January 2021
Line 23:		Line 23:
	Optionally, the user code can be annotated with additional information. These annotations disclose some information on the behavior of the black-box user function. The [[PactCompiler\|PACT Compiler]] can utilize the information to obtain more efficient execution plans. However, while a missing annotation will not change the result of the execution, an incorrect Output Contract produces wrong results.		Optionally, the user code can be annotated with additional information. These annotations disclose some information on the behavior of the black-box user function. The [[PactCompiler\|PACT Compiler]] can utilize the information to obtain more efficient execution plans. However, while a missing annotation will not change the result of the execution, an incorrect Output Contract produces wrong results.

	{{:wiki:pact.png?nolink&600\|}}

	The currently supported Input Contracts and annotation are presented and discussed in the following.		The currently supported Input Contracts and annotation are presented and discussed in the following.
Line 38:		Line 37:
	== MAP ==		== MAP ==

	The Map Input Contract works in the same way as in MapReduce. It has a single input and assigns each input record to its own subset. Hence, all records are processed independently from each other ~~(see figure below)~~. \\		The Map Input Contract works in the same way as in MapReduce. It has a single input and assigns each input record to its own subset. Hence, all records are processed independently from each other. \\


	{{:wiki:map.png?nolink&100\|}}

	== REDUCE ==		== REDUCE ==
Line 46:		Line 45:
	The Reduce Input Contract has the same semantics as the reduce function in MapReduce. It has a single input and groups together all records that have identical key fields. Each of these groups is handed as a whole to the user code and processed by it (see figure below). The PACT Programming Model does also support optional Combiners, e.g. for partial aggregations. \\		The Reduce Input Contract has the same semantics as the reduce function in MapReduce. It has a single input and groups together all records that have identical key fields. Each of these groups is handed as a whole to the user code and processed by it (see figure below). The PACT Programming Model does also support optional Combiners, e.g. for partial aggregations. \\

	{{:wiki:reduce.png?nolink&100\|}}

	== CROSS ==		== CROSS ==
Line 52:		Line 50:
	The Cross Input Contract works on two inputs. It builds the Cartesian product of the records of both inputs. Each element of the Cartesian product (pair of records) is handed to the user code. \\		The Cross Input Contract works on two inputs. It builds the Cartesian product of the records of both inputs. Each element of the Cartesian product (pair of records) is handed to the user code. \\


	{{:wiki:cross.png?nolink&160\|}}

	== MATCH ==		== MATCH ==
Line 58:		Line 56:
	The Match Input Contract works on two inputs. From both inputs it matches those records that are identical on their key fields come from different inputs. Hence, it resembles an equality join where the keys of both inputs are the attributes to join on. Each matched pair of records is handed to the user code. \\		The Match Input Contract works on two inputs. From both inputs it matches those records that are identical on their key fields come from different inputs. Hence, it resembles an equality join where the keys of both inputs are the attributes to join on. Each matched pair of records is handed to the user code. \\

	{{:wiki:match.png?nolink&160\|}}

	== COGROUP ==		== COGROUP ==

	The CoGroup Input Contract works on two inputs as well. It can be seen as a Reduce on two inputs. On each input, the records are grouped by key (such as Reduce does) and handed to the user code. In contrast to Match, the user code is also called for a key if only one input has a pair with it ~~(see blue key in example below)~~.		The CoGroup Input Contract works on two inputs as well. It can be seen as a Reduce on two inputs. On each input, the records are grouped by key (such as Reduce does) and handed to the user code. In contrast to Match, the user code is also called for a key if only one input has a pair with it.

	{{:wiki:cogroup.png?nolink&200\|}}

	=== Pact Record Data Model ===		=== Pact Record Data Model ===

John of Reading: Resolved {{Empty section}} problem by removing the redundant "See also" heading

2020-03-02T15:29:15Z

Resolved {{Empty section}} problem by removing the redundant "See also" heading

← Previous revision		Revision as of 15:29, 2 March 2020
Line 104:		Line 104:

	For a more detailed comparison of the MapReduce and PACT programming models you can read our paper //"MapReduce and PACT - Comparing Data Parallel Programming Models"// (see our [https://www.stratosphere.eu/index.php?q=publications\|publications page]).		For a more detailed comparison of the MapReduce and PACT programming models you can read our paper //"MapReduce and PACT - Comparing Data Parallel Programming Models"// (see our [https://www.stratosphere.eu/index.php?q=publications\|publications page]).

	== See also ==

	{{Empty section\|date=December 2013}}

	== References ==		== References ==

InternetArchiveBot: Rescuing 2 sources and tagging 0 as dead. #IABot (v1.6.4)

2018-03-12T07:34:16Z

Rescuing 2 sources and tagging 0 as dead. #IABot (v1.6.4)

← Previous revision		Revision as of 07:34, 12 March 2018
Line 112:		Line 112:

	{{reflist}}		{{reflist}}
	* [http://stratosphere.eu/files/NephelePACTs_10.pdf "Nephele/PACTs: A Programming Model and Execution Framework for Web-Scale Analytical Processing"]—paper by D. Battré, S. Ewen, F. Hueske, O. Kao, V. Markl, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of ACM SoCC 2010. The paper introduces the PACT programming model, a generalization of MapReduce, developed in the [http://www.stratosphere.eu Stratosphere] research project.		* [https://web.archive.org/web/20120424184436/http://www.stratosphere.eu/files/NephelePACTs_10.pdf "Nephele/PACTs: A Programming Model and Execution Framework for Web-Scale Analytical Processing"]—paper by D. Battré, S. Ewen, F. Hueske, O. Kao, V. Markl, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of ACM SoCC 2010. The paper introduces the PACT programming model, a generalization of MapReduce, developed in the [http://www.stratosphere.eu Stratosphere] research project.
	* [http://stratosphere.eu/files/ComparingMapReduceAndPACTs_11.pdf "MapReduce and PACT - Comparing Data Parallel Programming Models"]—paper by A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of BTW 2011.		* [https://web.archive.org/web/20120424184448/http://www.stratosphere.eu/files/ComparingMapReduceAndPACTs_11.pdf "MapReduce and PACT - Comparing Data Parallel Programming Models"]—paper by A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of BTW 2011.

	== Further reading ==		== Further reading ==

I dream of horses: /* Advantages of PACT over MapReduce */clean up, typo(s) fixed: straight-forward → straightforward using AWB

2016-05-31T06:38:04Z

Advantages of PACT over MapReduce: clean up, typo(s) fixed: straight-forward → straightforward using AWB

← Previous revision		Revision as of 06:38, 31 May 2016
Line 97:		Line 97:

	* The PACT programming model encourages a more modular programming style. Although the number of user functions is usually higher, they are more fine-grain and focus on specific problems. Hence, interweaving of functionality which is common for MapReduce jobs can be avoided.		* The PACT programming model encourages a more modular programming style. Although the number of user functions is usually higher, they are more fine-grain and focus on specific problems. Hence, interweaving of functionality which is common for MapReduce jobs can be avoided.
	* Data analysis tasks can be expressed as ~~straight-forward~~ data flows, especially when multiple inputs are required.		* Data analysis tasks can be expressed as straightforward data flows, especially when multiple inputs are required.
	* PACT has a record-based data model, which reduces the need to specify custom data types as not all data items need to be packed into a single value type.		* PACT has a record-based data model, which reduces the need to specify custom data types as not all data items need to be packed into a single value type.
	* PACT frequently eradicates the need for auxiliary structures, such as the distributed cache, which "break" the parallel programming model.		* PACT frequently eradicates the need for auxiliary structures, such as the distributed cache, which "break" the parallel programming model.

BG19bot: WP:CHECKWIKI error fix for #64. Do general fixes if a problem exists. - using AWB (11040)

2015-06-03T07:08:04Z

WP:CHECKWIKI error fix for #64. Do general fixes if a problem exists. - using AWB (11040)

← Previous revision		Revision as of 07:08, 3 June 2015
Line 1:		Line 1:
	{{Orphan\|date=December 2013}}		{{Orphan\|date=December 2013}}

	The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.		The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.

	== Overview ==		== Overview ==
Line 10:		Line 10:
	* Data Model: PACT's data model are records of arbitrary many fields of arbitrary types. MapReduce's KeyValue-Pairs can be considered as records with two fields.		* Data Model: PACT's data model are records of arbitrary many fields of arbitrary types. MapReduce's KeyValue-Pairs can be considered as records with two fields.

	[[~~Apache Flink\|~~Apache Flink]], an open-source parallel data processing platform has implemented '''PACT'''s. Flink allows users to specify user functions with annotations.		[[Apache Flink]], an open-source parallel data processing platform has implemented '''PACT'''s. Flink allows users to specify user functions with annotations.

	== Logical view ==		== Logical view ==
Line 119:		Line 119:

	== External links ==		== External links ==

	* [http://stratosphere.eu Stratosphere project home page]		* [http://stratosphere.eu Stratosphere project home page]
	* [http://www.hpts.ws/papers/2011/posters/Poster2011_06_Bodner.pdf Stratosphere slide presentation]		* [http://www.hpts.ws/papers/2011/posters/Poster2011_06_Bodner.pdf Stratosphere slide presentation]

91.66.63.236: Add link to Apache Flink.

2015-06-02T08:23:16Z

Add link to Apache Flink.

← Previous revision		Revision as of 08:23, 2 June 2015
Line 1:		Line 1:
	{{Orphan\|date=December 2013}}		{{Orphan\|date=December 2013}}

	The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.		The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function\|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.

	== Overview ==		== Overview ==
Line 9:		Line 9:
	* Program structure: PACT allows the composition of arbitrary acyclic data flow graphs. In contract, MapReduce programs have a static structure (Map -> Reduce).		* Program structure: PACT allows the composition of arbitrary acyclic data flow graphs. In contract, MapReduce programs have a static structure (Map -> Reduce).
	* Data Model: PACT's data model are records of arbitrary many fields of arbitrary types. MapReduce's KeyValue-Pairs can be considered as records with two fields.		* Data Model: PACT's data model are records of arbitrary many fields of arbitrary types. MapReduce's KeyValue-Pairs can be considered as records with two fields.

			[[Apache Flink\|Apache Flink]], an open-source parallel data processing platform has implemented '''PACT'''s. Flink allows users to specify user functions with annotations.

	== Logical view ==		== Logical view ==

Shenme: "exampe" -> "example"

2015-05-18T02:21:35Z

"exampe" -> "example"

← Previous revision		Revision as of 02:21, 18 May 2015
Line 68:		Line 68:
	In contrast to MapReduce, PACT uses a more generic data model of records ([[PactRecord\|Pact Record]]) to pass data between functions. The Pact Record can be thought of as a tuple with a free schema. The interpretation of the fields of a record is up to the user function. A Key/Value pair (as in MapReduce) is a special case of that record with only two fields (the key and the value).		In contrast to MapReduce, PACT uses a more generic data model of records ([[PactRecord\|Pact Record]]) to pass data between functions. The Pact Record can be thought of as a tuple with a free schema. The interpretation of the fields of a record is up to the user function. A Key/Value pair (as in MapReduce) is a special case of that record with only two fields (the key and the value).

	For input contracts that operate on keys (like //Reduce//, //Match//, or //CoGroup//, one specifies which combination of the record's fields make up the key. An arbitrary combination of fields may used. See the [https://github.com/stratosphere-eu/stratosphere/blob/master/pact/pact-examples/src/main/java/eu/stratosphere/pact/example/relational/TPCHQuery3.java\|TPCH Query ~~Exampe~~] on how programs defining //Reduce// and //Match// contracts on one or more fields and can be written to minimally move data between fields.		For input contracts that operate on keys (like //Reduce//, //Match//, or //CoGroup//, one specifies which combination of the record's fields make up the key. An arbitrary combination of fields may used. See the [https://github.com/stratosphere-eu/stratosphere/blob/master/pact/pact-examples/src/main/java/eu/stratosphere/pact/example/relational/TPCHQuery3.java\|TPCH Query Example] on how programs defining //Reduce// and //Match// contracts on one or more fields and can be written to minimally move data between fields.

	The record may be sparsely filled, i.e. it may have fields that have //null// values. It is legal to produce a record where for example only fields 2 and 5 are set. Fields 1, 3, 4 are interpreted to be //null//. Fields that are used by a contract as key fields may however not be null, or an exception is raised.		The record may be sparsely filled, i.e. it may have fields that have //null// values. It is legal to produce a record where for example only fields 2 and 5 are set. Fields 1, 3, 4 are interpreted to be //null//. Fields that are used by a contract as key fields may however not be null, or an exception is raised.