You are viewing a plain text version of this content. The canonical link for it is here.
Posted to mapreduce-issues@hadoop.apache.org by "anty.rao (Created) (JIRA)" <ji...@apache.org> on 2012/03/20 08:59:45 UTC
[jira] [Created] (MAPREDUCE-4039) Sort Avoidance
Sort Avoidance
--------------
Key: MAPREDUCE-4039
URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
Project: Hadoop Map/Reduce
Issue Type: New Feature
Components: mrv2
Affects Versions: 0.23.2
Reporter: anty.rao
Priority: Minor
Fix For: 0.23.2
Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
{quote}*Sort Avoidance*. Certain operators such as hash join
and hash aggregation require shuffling, but not sorting. The
MapReduce API was enhanced to automatically turn off
sorting for these operations. When sorting is turned off, the
mapper feeds data to the reducer which directly passes the
data to the Reduce() function bypassing the intermediate
sorting step. This makes many SQL operators significantly
more ecient.{quote}
There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
the following is the main points of sort avoidance implementation
# add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
# key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
# map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which currently version incurs.
# reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
# map output in memory can be directly consumed by reduce.When reduce can catch up with the speed of incoming map output, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
# sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
anty.rao updated MAPREDUCE-4039:
--------------------------------
Attachment: MAPREDUCE-4039-branch-0.23.2.patch
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
anty.rao updated MAPREDUCE-4039:
--------------------------------
Attachment: IndexedCountingSortable.java
the missing file.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Arun C Murthy (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13238135#comment-13238135 ]
Arun C Murthy commented on MAPREDUCE-4039:
------------------------------------------
bq. Can someone shed light on me?
Anty - IFile.Reader in hadoop-0.23 uses IFileInputStream which does the 'full' read into a in-memory buffer similar to what was happening in IFile.Reader in hadoop-0.20.xxx and should give similar characteristics. Makes sense?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Ahmed Radwan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13425952#comment-13425952 ]
Ahmed Radwan commented on MAPREDUCE-4039:
-----------------------------------------
Hi Anty, Do you think you'll be able to update the patch and add the unit tests? With a new feature like that, unit tests are essential. Please let us know if you need any help.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Assigned] (MAPREDUCE-4039) Sort Avoidance
Posted by "Arun C Murthy (Assigned) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Arun C Murthy reassigned MAPREDUCE-4039:
----------------------------------------
Assignee: anty
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "longfei (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13291599#comment-13291599 ]
longfei commented on MAPREDUCE-4039:
------------------------------------
The patch Did not give the class org.apache.hadoop.util.IndexedCountingSortable.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13426275#comment-13426275 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
Hi Ahmed
{quote}Sure Anty, are you already working on updating the patch with pluggable MapOutputBuffer and Shuffle then?{quote}
No, the sort plugin feature seems not completed, So i don't start out
{quote}Hi Anty, Do you think you'll be able to update the patch and add the unit tests? With a new feature like that, unit tests are essential. Please let us know if you need any help.{quote}
I will add some unit tests.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Ahmed Radwan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13424741#comment-13424741 ]
Ahmed Radwan commented on MAPREDUCE-4039:
-----------------------------------------
bq. when sort plugin is finished, this patch will need be modified.
Sure Anty, are you already working on updating the patch with pluggable MapOutputBuffer and Shuffle then?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Arun C Murthy (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13233351#comment-13233351 ]
Arun C Murthy commented on MAPREDUCE-4039:
------------------------------------------
+1, looks like a good addition.
We should be careful to ensure we document this adequately.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Ahmed Radwan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418727#comment-13418727 ]
Ahmed Radwan commented on MAPREDUCE-4039:
-----------------------------------------
Thanks Anty! a couple of initial comments:
* IndexedCountingSortable.java doesn't compile (seems the the same class contents are pasted twice). I think you want to add this file to the location: hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/IndexedCountingSortable.java. It'll be easier to create a new diff including this new file and upload an updated patch.
* The patch also doesn't include any new or updated unit tests.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13238190#comment-13238190 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
{quote}We could consider making the MapOutputBuffer pluggable for a start so we can split the 'full sort' and the 'hash sort' implementations. Similarly, we could implement a pluggable Shuffle to not block until outputs of all maps are not available.
This way we can cleanly layer the necessary features.
Thoughts?{quote}
Arun, I like the idea of making MapOutputBuffer and Shuffle pluggable.I will take a crack at it, and give the feedback.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Ahmed Radwan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13423639#comment-13423639 ]
Ahmed Radwan commented on MAPREDUCE-4039:
-----------------------------------------
Thanks Anty! I'll be happy to review your patch. I have noticed that the updated patch still have no unit tests, are you planning to add them? Also, will you be providing a corresponding patch for branch-1?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
anty.rao updated MAPREDUCE-4039:
--------------------------------
Attachment: MAPREDUCE-4039-branch-0.23.2.patch
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13420640#comment-13420640 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
@Ahmed Radwan
Sorry for the delay
Submit a new batch.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Mariappan Asokan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13430587#comment-13430587 ]
Mariappan Asokan commented on MAPREDUCE-4039:
---------------------------------------------
Hi Anty,
I have submitted a patch for MAPREDUCE-2454 to support a pluggable sort for MR. I have some ideas on implementing a NullSortPlugin which will be a special sort plugin that avoids sorting. The NullSortPlugin can live outside the Hadoop MR code. I can share my thoughts if you are interested.
Thanks.
-- Asokan
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
anty.rao updated MAPREDUCE-4039:
--------------------------------
Description:
Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
{quote}*Sort Avoidance*. Certain operators such as hash join
and hash aggregation require shuffling, but not sorting. The
MapReduce API was enhanced to automatically turn off
sorting for these operations. When sorting is turned off, the
mapper feeds data to the reducer which directly passes the
data to the Reduce() function bypassing the intermediate
sorting step. This makes many SQL operators significantly
more ecient.{quote}
There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
the following is the main points of sort avoidance implementation
# add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
# key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
# map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
# reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
# map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
# sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
was:
Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
{quote}*Sort Avoidance*. Certain operators such as hash join
and hash aggregation require shuffling, but not sorting. The
MapReduce API was enhanced to automatically turn off
sorting for these operations. When sorting is turned off, the
mapper feeds data to the reducer which directly passes the
data to the Reduce() function bypassing the intermediate
sorting step. This makes many SQL operators significantly
more ecient.{quote}
There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
the following is the main points of sort avoidance implementation
# add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
# key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
# map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which currently version incurs.
# reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
# map output in memory can be directly consumed by reduce.When reduce can catch up with the speed of incoming map output, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
# sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Schubert Zhang (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13233334#comment-13233334 ]
Schubert Zhang commented on MAPREDUCE-4039:
-------------------------------------------
Nice summary Anty, and expect your patch on 0.23.
The more detailed description and benchmark on this feature, you can refer to http://www.slideshare.net/hanborq/hanborq-optimizations-on-hadoop-mapreduce-20120216a or http://www.slideshare.net/schubertzhang/hanborq-optimizations-on-hadoop-map-reduce-20120221a
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Arun C Murthy (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13238138#comment-13238138 ]
Arun C Murthy commented on MAPREDUCE-4039:
------------------------------------------
Anty - I spent a bit of time thinking of this.
Some early thoughts... seems to me that we are better of doing a bit of surgery on the MR runtime before we do this.
We could consider making the MapOutputBuffer pluggable for a start so we can split the 'full sort' and the 'hash sort' implementations. Similarly, we could implement a pluggable Shuffle to not block until outputs of all maps are not available.
This way we can cleanly layer the necessary features.
Thoughts?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Mariappan Asokan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13445328#comment-13445328 ]
Mariappan Asokan commented on MAPREDUCE-4039:
---------------------------------------------
Hi Anty,
Sorry, I did not get back to you. Please take a look at the patch for MAPREDUCE-2454. I added a test that has a very simple implementation of NullSortPlugin. You can take a look at the code there.
-- Asokan
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13238165#comment-13238165 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
Arun, Thanks for you reply!
{quote}Anty - IFile.Reader in hadoop-0.23 uses IFileInputStream which does the 'full' read into a in-memory buffer similar to what was happening in IFile.Reader in hadoop-0.20.xxx and should give similar characteristics. Makes sense?{quote}
IFileInputStream only do data checksum not data buffering . Data buffering is enforced on IFile.Reader level in hadoop-0.20.xxx
1. In hadoop-0.20.xxx, a bunch of data is first read into a byte array
{code} byte[] buffer = null;{code}the initial size of this buffer is controlled by the parameter _io.file.buffer.size_. Then key/value pair is read from this in-memory buffer.
2. In hadoop-0.23, this variable _buffer_ still exist ,but isn't in use actually. So, each key/value pair is read directly from the underling IFileInputStream.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13437682#comment-13437682 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
Hi: Asokan
Of course,i'm interested.Glad that you can share your thoughts!
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Schubert Zhang (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13238028#comment-13238028 ]
Schubert Zhang commented on MAPREDUCE-4039:
-------------------------------------------
Patch is available by Anty, someone to have a review?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13234174#comment-13234174 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
I am a little confused about the implementation of Reader of IFile.
In previous hadoop version, IFile reader will read in a bunch of key/value pairs from the disk one time, then serve it directly from in memory.I think this strategy is common and good.However, in yarn for each requested key/value pairs reader will go hit the disk(though pre-read will do some help). Am i miss something？Can someone shed light on me?
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Priority: Minor
> Fix For: 0.23.2
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "Kang Xiao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13395855#comment-13395855 ]
Kang Xiao commented on MAPREDUCE-4039:
--------------------------------------
@Schubert, could you give some typical applications that benefit from sort avoidance? It seems that using this feature simple aggregation app such as wordcount will use more memory to wait for all keys processed.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "Robert Joseph Evans (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Joseph Evans updated MAPREDUCE-4039:
-------------------------------------------
Target Version/s: 2.0.0, 3.0.0 (was: 0.23.2)
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13395916#comment-13395916 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
@Kang
Yes, you are right.
Using merge-sort to achieve aggregation maybe don't use so much memory as hash aggregation with this feature.But the process of merge-sort require much useless work to done, consume more resources, e.g. CPU, disk, network.
it's just a tradeoff according to your usecase, latency requirement, etc.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13424660#comment-13424660 ]
anty.rao commented on MAPREDUCE-4039:
-------------------------------------
Ahmed,thank you for spacing time to review this patch.
But, when sort plugin is finished, this patch will need be modified.
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAPREDUCE-4039) Sort Avoidance
Posted by "anty.rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-4039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
anty.rao updated MAPREDUCE-4039:
--------------------------------
Attachment: MAPREDUCE-4039-branch-0.23.2.patch
> Sort Avoidance
> --------------
>
> Key: MAPREDUCE-4039
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-4039
> Project: Hadoop Map/Reduce
> Issue Type: New Feature
> Components: mrv2
> Affects Versions: 0.23.2
> Reporter: anty.rao
> Assignee: anty
> Priority: Minor
> Fix For: 0.23.2
>
> Attachments: IndexedCountingSortable.java, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch, MAPREDUCE-4039-branch-0.23.2.patch
>
>
> Inspired by [Tenzing|http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//pubs/archive/37200.pdf], in 5.1 MapReduce Enhanceemtns:
> {quote}*Sort Avoidance*. Certain operators such as hash join
> and hash aggregation require shuffling, but not sorting. The
> MapReduce API was enhanced to automatically turn off
> sorting for these operations. When sorting is turned off, the
> mapper feeds data to the reducer which directly passes the
> data to the Reduce() function bypassing the intermediate
> sorting step. This makes many SQL operators significantly
> more ecient.{quote}
> There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.
> the following is the main points of sort avoidance implementation
> # add a configuration parameter ??mapreduce.sort.avoidance??, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
> # key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
> # map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
> # reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
> # map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
> # sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.
> I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to [https://github.com/hanborq/hadoop] for details. Now,I'm willing to port it into yarn. Welcome for commenting.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira