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 "Joydeep Sen Sarma (JIRA)" <ji...@apache.org> on 2010/03/27 14:58:27 UTC
[jira] Created: (MAPREDUCE-1639) Grouping using hashing instead of
sorting
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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "Luke Lu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850693#action_12850693 ]
Luke Lu commented on MAPREDUCE-1639:
------------------------------------
IMHO, it'd be easier to implement such grouping using a special group record reader (inputformat) and mapper (that uses a hash map to group things and walk the map to emit grouped key value pairs, where values can be counts or lists, at the end of the map method) than rearchitecting the current data path.
> 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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "Joydeep Sen Sarma (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850643#action_12850643 ]
Joydeep Sen Sarma commented on MAPREDUCE-1639:
----------------------------------------------
no - the number of reducers is determined by other criteria (people here are expert on determining how to come up with that). we obviously can't have millions of reducers. but we can have millions of hash buckets that are sent in (large) groups to a much much smaller number of reducers.
i explained in terms of larger number of reducers to explore similarities (if any) to current data path.
> 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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "Joydeep Sen Sarma (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850714#action_12850714 ]
Joydeep Sen Sarma commented on MAPREDUCE-1639:
----------------------------------------------
@Luke - like this line of thinking. I am familiar with Hive - it already does map side partial aggregates for (most) group-bys and emits them (what you mentioned). However - for (most) joins and cluster-by - it depends on the sorting provided by the map-reduce framework. We could alter the these query plans to execute this algorithm. the downside is pretty obvious: the benefits would only be available to Hive users (even as the cost of implementation remains fairly high). it would not be reusable by Pig for example - nor streaming users, etc.
extrapolating ur idea a bit - we could try to implement this as a library - something that intercepts the output of the mapper (and combiner) and the input to the reduce function (that could be inserted into the data path via config settings). (There's already a configurable output collector interface on the map output side. not sure about reducer input). We could turn off map-side sorting in the map-reduce framework itself. the main concern i would have is that it would seem too hard for these output collectors to implements spills (/merges) to (/from) disk. Perhaps if that functionality can be extracted out of the map-reduce core and provided as a library that these output collectors can use - then it's all feasible.
> 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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "Joydeep Sen Sarma (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850556#action_12850556 ]
Joydeep Sen Sarma commented on MAPREDUCE-1639:
----------------------------------------------
realize this is non-trivial.
> 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.
not sure about this. it doesn't change the fact that all keys are being compared against each other. just because we compare fewer bytes doesn't mean that the number of comparisons goes down. it's still n.logn. the cost of each comparison is lower though.
if we did a radix sort (first) on the leading 4 (hashed) bytes - then yeah - it changes things. but at that point we are taking (pretty much) the same approach as the paper and talking about a different data path.
> 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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "Joydeep Sen Sarma (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850562#action_12850562 ]
Joydeep Sen Sarma commented on MAPREDUCE-1639:
----------------------------------------------
following up on the previous comment - reading the paper again closely - it's no longer clear to me that the paper actually implements what i filed or whether it's closer to how Owen interpreted it. But i think it's true that sorting only within hash buckets only is fundamentally lower complexity than sorting everything together.
---
i am also wondering how different this is from current data path. today we anyway bucket map outputs into one bucket per reducer and sort therein. this is simply saying that we have lots of buckets per reducer (not one) - we are still sorting inside each of those - but because we are sorting much smaller sets - the complexity is lowered.
so on the mapper side - we can (sort of) just pretend that the number of reducers is much much higher. Except when it's time to send off the data to the reducer (or spill) - we send a bunch of buckets. but this is not transparent to the merge code - it now has to merge taking the bucketid into consideration. if we prefixed each map-output key with the bucketid - then it's transparent to the merge code. so definitely some changes required - but maybe tractable?
> 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.
[jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead
of sorting
Posted by "dhruba borthakur (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850632#action_12850632 ]
dhruba borthakur commented on MAPREDUCE-1639:
---------------------------------------------
So, then are you saying that thsi is equivalent to just increasing the number of reducers? And make each reducer receive the records from one bucket.
> 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.