hadoop-mapreduce-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Binglin Chang (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MAPREDUCE-1639) Grouping using hashing instead of sorting
Date Sat, 22 Oct 2011 09:48:33 GMT

    [ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13133329#comment-13133329
] 

Binglin Chang commented on MAPREDUCE-1639:
------------------------------------------

@YongQiang 
Thanks! 
Originally, I plan to support grouping in nativetask, but after optimizing sort, I found the
sort phrase no longer a bottleneck anymore, especially in large jobs with many reduce tasks.
In fact the current sort implementation is not optimized at all(just use stl::sort), so replacing
sort with grouping may not have a big effect after sort is optimized. Above all, I prefer
hash aggregation, the bad thing about it is it must change combiner/reducer api, this won't
be a problem for the under dev nativetask, but is much complicated in java, I will create
a issue for discussion.
I prefer sent to me offline, can't wait to see :)

                
> Grouping using hashing instead of sorting
> -----------------------------------------
>
>                 Key: MAPREDUCE-1639
>                 URL: https://issues.apache.org/jira/browse/MAPREDUCE-1639
>             Project: Hadoop Map/Reduce
>          Issue Type: New Feature
>            Reporter: Joydeep Sen Sarma
>
> most applications of map-reduce care about grouping and not sorting. Sorting is a (relatively
expensive) way to achieve grouping. In order to achieve just grouping - one can:
> - replace the sort on the Mappers with a HashTable - and maintain lists of key-values
against each hash-bucket.
> - key-value tuples inside each hash bucket are sorted - before spilling or sending to
Reducer. Anytime this is done - Combiner can be invoked.
> - HashTable is serialized by hash-bucketid. So merges (of either spills or Map Outputs)
works similar to today (at least there's no change in overall compute complexity of merge)
> Of course this hashtable has nothing to do with partitioning. it's just a replacement
for map-side sort.
> --
> this is (pretty much) straight from the MARS project paper: http://www.cse.ust.hk/catalac/papers/mars_pact08.pdf.
They report a 45% speedup in inverted index calculation using hashing instead of sorting (reference
implementation is NOT against Hadoop though).

--
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

        

Mime
View raw message