[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead of sorting

["Owen O'Malley (JIRA)" <ji...@apache.org>]

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

Owen O'Malley commented on MAPREDUCE-1639:
------------------------------------------

Three comments spring to mind:
  1. A completely new data path is very expensive.
  2. A much easier way to achieve their result is to include the hash in the key as the first 4 bytes of the serialization, then have a comparator that uses the first 4 bytes as memcmp before it uses the dispatched raw compare method.
  3. Having a library of memcmp'able keys would be even better. Basically, you'd need to implement org.apache.hadoop.io.memcmp.(Int|Long|String|Array) that implemented Writable and a marker interface.

> 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.
-
You can reply to this email to add a comment to the issue online.