Mailing-List: contact mapreduce-issues-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mapreduce-issues@hadoop.apache.org
Date: Wed, 19 Oct 2011 22:25:12 +0000 (UTC)
From: "Arun C Murthy (Commented) (JIRA)" <jira@apache.org>
To: mapreduce-issues@hadoop.apache.org
Message-ID: 
 <1914849452.12762.1319063112110.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Commented] (MAPREDUCE-1639) Grouping using hashing instead
 of sorting
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Arun C Murthy commented on MAPREDUCE-1639:
------------------------------------------

This is a great candidate for MR2.

It's a new pipeline which would be the most efficient though:

The output collector would hash rather than sort and spill in order of keys, thus keeping the combiner optional.

The twist is that you wouldn't do a 2nd or 3rd or n-th level merge in the map. Just the segments out and get the reduce to think there are more segments than #maps (additional index at the top). Most of the times, each map-output fits in memory of the reduce and thus you wouldn't seek anymore than today. The 2+ level merges don't change in the reduce.

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