You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-dev@hadoop.apache.org by "Owen O'Malley (JIRA)" <ji...@apache.org> on 2006/08/26 09:52:22 UTC
[jira] Created: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
allow a different comparator for grouping keys in calls to reduce
-----------------------------------------------------------------
Key: HADOOP-485
URL: http://issues.apache.org/jira/browse/HADOOP-485
Project: Hadoop
Issue Type: New Feature
Affects Versions: 0.5.0
Reporter: Owen O'Malley
Assigned To: Owen O'Malley
Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
A1, V1
A2, V2
A3, V3
B1, V4
B2, V5
instead of getting calls to reduce that look like:
reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
you could define the grouping comparator to just compare the letters and end up with:
reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Runping Qi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12490071 ]
Runping Qi commented on HADOOP-485:
-----------------------------------
A real example is "session analysis" on the log data.
Let's say we have a data set containing a collection of records, each has a timestamp field and other fields.
We want to group the records by certain fields (the primary key fields), but we want the records within each group to be sorted by timestamps so that the user's reduce function can analyse the records in one pass. Otherwise, the user's code has to cache all the records within each group, sort them by the timestamps first
(this is effectively the common approach people take, but it will run out memory if the number of records per
group is very large).
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489986 ]
Tahir Hashmi commented on HADOOP-485:
-------------------------------------
Sameer, Devaraj, Arun and I had some involved discussions regarding this issue. The conclusions seem to be:
1. There's some degree of consensus that this problem can be solved entirely at the application layer but legacy applications might not have the luxury of modifiability
2. From the examples cited above, it seems like the end goal is really to sort the values. One of the approaches is to make the keys composite, where one part is used for sorting/partitioning the actual (primary) keys and the other part is used to order the values. This approach requires the framework to handle composite keys and group values by the primary subkey, sort them within a group by the secondary subkey and finally strip off the secondary subkey before calling reduce.
IMO, a better way to do this might be to support filter chains and map and reduce stages. The first step is that the user defined mapper emits intermediate K,V pairs and each of these pairs is passed through the map filter chain before being considered for sorting/spilling. Likewise, at the reduce end the reduce filters operate on K,[V] pairs and carry out necessary transformations before passing the output to user defined reducers. Additionally, we also support sorting of values through user defined comparators.
In this scheme of things, the application (as I understand it) would work as such:
* the mapper emits PK, V pairs
* a map filter transforms V to SK-V composite
* the pairs are sorted and partitioned on PK to generate PK, [SK-V] groups and within the [SK-V] sequence, the elements are sorted by the user defined value comparator.
* the reduce filter strips secondary keys from values and transforms each PK,[SK-V] to PK,[V]
* the user defined reducer finally processes the PK,[V] pairs.
An alternate solution might be to attach secondary key to the primary key instead of values, as in the original proposal, except that in this case the framework would have to run the equivalent of an intermediate reduce that takes PK-SK, V pairs, strips off SK from each composite key and groups the values together before calling the user defined reducer. To me this doesn't seem to be a very neat approach.
Before discussing this further, I'd like to know the specific real world application that triggered this requirement, along with the relevant operating constraints it has.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: Hadoop-485-pre.patch
Here's a proof-of-concept patch for this requirement. The intent is to get the approach reviewed. What's being done here is that instead of just comparing keys, we're now also comparing values if keys turn out to be equal. This is done both while doing sortAndSpillToDisk() in MapTask.java and while doing a merge in SequenceFile.java.
The trick is to alter the comparison functions in BasicTypeSorterBase.compare() and SequenceFile.MergeQueue.lessThan() to account for values as well. The attached patch has the code changes done for this.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Status: Patch Available (was: Open)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Status: Patch Available (was: Open)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: 485.patch
Here's a patch that includes a test case for this feature and also changes to the source code to make it work. Reviewers please also check adherence to naming conventions among other things.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12491694 ]
Hadoop QA commented on HADOOP-485:
----------------------------------
+1
http://issues.apache.org/jira/secure/attachment/12356251/485.patch applied and successfully tested against trunk revision r532083.
Test results: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/77/testReport/
Console output: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/77/console
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Doug Cutting updated HADOOP-485:
--------------------------------
Status: Open (was: Patch Available)
Javadoc generates warnings.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489829 ]
Doug Cutting commented on HADOOP-485:
-------------------------------------
Sorry for spamming this issue, but I finally remembered the discussion that spawned this issue last summer. The idea was that, when a compound key is used, one should be able to specify two comparators: one for sorting, and one for deciding how to group calls to reduce. The original request was *not* about considering values in sort. In the description above, the A1,V1 pairs are assumed to be compound keys, not key,value pairs. Normally, since A1,V1 does not equal A1,V2, these would be passed in separate calls to reduce. The goal of this issue is to permit one to specify a reduce key comparator that *would* make A1,V1 equal to A2,V1 and hence make only a single call to reduce. This would *only* be used when deciding how to break the stream of sorted keys into calls to reduce().
Note that this feature is required to implement something like the user-code ValueSorting described in the above comment.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Owen O'Malley (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12478179 ]
Owen O'Malley commented on HADOOP-485:
--------------------------------------
It is important and will get done. It is just a matter of when. It shouldn't be hard to do and shouldn't require any other outstanding patches.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Owen O'Malley
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12490119 ]
Doug Cutting commented on HADOOP-485:
-------------------------------------
> We just need to be able to load a different comparator.
Yes, that's it: we permit a different comparator to break the stream of sorted keys into calls to reduce.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Runping Qi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489837 ]
Runping Qi commented on HADOOP-485:
-----------------------------------
You want to control the partitioning as well.
For example, let's we have the following map output:
PK1, SK11, V1
PK1, SK12, V2
PK2, SK21, V3
PK2, SK22, V4
where PKi are primary keys and SKij are secondary keys.
What you want is that all the tuples with same primary keys will go to the same reducer.
Within the same reducer, the tuples are sorted by the primary/secondary keys.
When passing to reduce calls, you want the primary key wil be the key to reduce call, and the values with the same primary key
will be passed to the reduce call, in the sorted order by the secondary keys.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Doug Cutting updated HADOOP-485:
--------------------------------
Status: Open (was: Patch Available)
This patch no longer applies cleanly to trunk. Sorry! Can you please repair it? Thanks!
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Status: Patch Available (was: Open)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489835 ]
Tahir Hashmi commented on HADOOP-485:
-------------------------------------
Does the infrastructure for grouping to reduce based on some properties of reduce already exist? It's also not clear to me why a different comparator is needed for figuring out the grouping of values. The same comparator that works on keys can handle values as well, by implementing a secondary ordering on values where the keys are equal.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: 485.patch
Rebuilt against revision 534626. Hope this works!
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489822 ]
Doug Cutting commented on HADOOP-485:
-------------------------------------
Another simple approach to implementing this would be to, when a value comparator is configured, write map output as compound keys that include both the key and value. Then the normal sorting would consider values. Finally, the reducer would unpack the compound keys back to separate keys and values before calling reduce(). This could probably even be implemented entirely as user code:
ValueSorting.configure(job); // sets mapOutputKeyClass to compound, mapper & reducer
ValueSorting.setMapper(MyMapper.class);
ValueSorting.setMapper(MyReducer.class);
The ValueSorting mapper would wrap the original OutputCollector in a version that creates compound keys. The ValueSorting reducer would unwrap compound keys.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Updated: (HADOOP-485) allow a different comparator for grouping keys in calls to reduce
Posted by Nigel Daley <nd...@yahoo-inc.com>.
On Apr 30, 2007, at 7:11 AM, Tahir Hashmi (JIRA) wrote:
>
> [ https://issues.apache.org/jira/browse/HADOOP-485?
> page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>
> Tahir Hashmi updated HADOOP-485:
> --------------------------------
>
> Attachment: 485.patch
>
> Added javadoc documentation for get and set methods in JobConf.
It would be good to document what happens if null is passed into the
setter method and what happens if the getter method is called when no
comparator has been set. Also, if the
"mapred.output.value.groupfn.class" is intended to be a public
property, then I think the javadoc should mention that these methods
control the value of this property.
>> allow a different comparator for grouping keys in calls to reduce
>> -----------------------------------------------------------------
>>
>> Key: HADOOP-485
>> URL: https://issues.apache.org/jira/browse/HADOOP-485
>> Project: Hadoop
>> Issue Type: New Feature
>> Components: mapred
>> Affects Versions: 0.5.0
>> Reporter: Owen O'Malley
>> Assigned To: Tahir Hashmi
>> Attachments: 485.patch, 485.patch, 485.patch, Hadoop-485-
>> pre.patch, TestUserValueGrouping.java.patch
>>
>>
>> Some algorithms require that the values to the reduce be sorted in
>> a particular order, but extending the key with the additional
>> fields causes them to be handled by different calls to reduce.
>> (The user then collects the values until they detect a "real" key
>> change and then processes them.)
>> It would be much easier if the framework let you define a second
>> comparator that did the grouping of values for reduces. So your
>> reduce inputs look like:
>> A1, V1
>> A2, V2
>> A3, V3
>> B1, V4
>> B2, V5
>> instead of getting calls to reduce that look like:
>> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1,
>> {V4}); reduce(B2, {V5});
>> you could define the grouping comparator to just compare the
>> letters and end up with:
>> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
>> which is the desired outcome. Note that this assumes that the
>> "extra" part of the key is just for sorting because the reduce
>> will only see the first representative of each equivalence class.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: 485.patch
Added javadoc documentation for get and set methods in JobConf.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Runping Qi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12490080 ]
Runping Qi commented on HADOOP-485:
-----------------------------------
Excellent summary!
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Updated: (HADOOP-485) allow a different comparator for grouping keys in calls to reduce
Posted by Nigel Daley <nd...@yahoo-inc.com>.
FWIW, HADOOP-742 requests better javadoc for JobConf
On Apr 26, 2007, at 1:38 PM, Doug Cutting (JIRA) wrote:
>
> [ https://issues.apache.org/jira/browse/HADOOP-485?
> page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>
> Doug Cutting updated HADOOP-485:
> --------------------------------
>
> Status: Open (was: Patch Available)
>
> The new JobConf methods need javadoc. (Yes, the rest of JobConf is
> woefully undocumented, but that's a bug that we should work to fix.)
>
>
>> allow a different comparator for grouping keys in calls to reduce
>> -----------------------------------------------------------------
>>
>> Key: HADOOP-485
>> URL: https://issues.apache.org/jira/browse/HADOOP-485
>> Project: Hadoop
>> Issue Type: New Feature
>> Components: mapred
>> Affects Versions: 0.5.0
>> Reporter: Owen O'Malley
>> Assigned To: Tahir Hashmi
>> Attachments: 485.patch, 485.patch, Hadoop-485-pre.patch,
>> TestUserValueGrouping.java.patch
>>
>>
>> Some algorithms require that the values to the reduce be sorted in
>> a particular order, but extending the key with the additional
>> fields causes them to be handled by different calls to reduce.
>> (The user then collects the values until they detect a "real" key
>> change and then processes them.)
>> It would be much easier if the framework let you define a second
>> comparator that did the grouping of values for reduces. So your
>> reduce inputs look like:
>> A1, V1
>> A2, V2
>> A3, V3
>> B1, V4
>> B2, V5
>> instead of getting calls to reduce that look like:
>> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1,
>> {V4}); reduce(B2, {V5});
>> you could define the grouping comparator to just compare the
>> letters and end up with:
>> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
>> which is the desired outcome. Note that this assumes that the
>> "extra" part of the key is just for sorting because the reduce
>> will only see the first representative of each equivalence class.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Doug Cutting updated HADOOP-485:
--------------------------------
Status: Open (was: Patch Available)
The new JobConf methods need javadoc. (Yes, the rest of JobConf is woefully undocumented, but that's a bug that we should work to fix.)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: TestUserValueGrouping.java.patch
Here's a basic test for this requirement. The mapper generates a few random integer values for each integer key. The reducer checks whether the values for each key were received in sorted order. I've got it working for the default integer comparator as outlined in the previous attachment's description.
If the approach and test seems to be satisfactory, I'll work on building the provision for loading a user defined value comparison class.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489836 ]
Tahir Hashmi commented on HADOOP-485:
-------------------------------------
Sorry, read that as "...infrastructure for grouping to reduce based on some properties of keys..."
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12493480 ]
Tahir Hashmi commented on HADOOP-485:
-------------------------------------
Party time! :D
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Fix For: 0.13.0
>
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Sameer Paranjpye (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HADOOP-485?page=all ]
Sameer Paranjpye updated HADOOP-485:
------------------------------------
Component/s: mapred
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: http://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Owen O'Malley
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12493163 ]
Hadoop QA commented on HADOOP-485:
----------------------------------
+1
http://issues.apache.org/jira/secure/attachment/12356648/485.patch applied and successfully tested against trunk revision r534234.
Test results: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/103/testReport/
Console output: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/103/console
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: 485.patch
Sorry for the delayed turnaround. Had some painful issues with the build environment. Fixed javadoc warnings now.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12493233 ]
Hadoop QA commented on HADOOP-485:
----------------------------------
+1
http://issues.apache.org/jira/secure/attachment/12356672/485.patch applied and successfully tested against trunk revision r534624.
Test results: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/105/testReport/
Console output: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/105/console
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Attachment: 485.patch
This patch addresses Devaraj's comments. I could run the specific unit test for this feature successfully but I've got failures in DFS with revision 532317 and Java 6 even on a clean check-out.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12490078 ]
Tahir Hashmi commented on HADOOP-485:
-------------------------------------
Got a bit of enlightenment from Sameer on this and it turns out that the whole thing really is quite simple. As I understand, here's how things go:
* The intermediate K,V pairs are partitioned into buckets using a partitioning function that by default hashes keys into buckets. User defined partitioning functions are supported and they can basically hash on one part of the composite key. So we're cool here
* The K,V pairs are sorted within individual maps and across merges from different maps. This is done through a user defined comparator for keys. This comparator can sort on multiple parts of a composite key so we're cool here too.
* Before being passed to the user defined reducer, the K,V pairs are collated but this collation is based on the comparator used in the sort. This is where we're not cool. The sort comparator wants to look at more than one fields in the composite key, while the collation/grouping comparator should only look at the primary key part. We just need to be able to load a different comparator. This doesn't look like an overly complex change.
So for now, the filter chains shebang can be put in cold storage :)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Sameer Paranjpye (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sameer Paranjpye updated HADOOP-485:
------------------------------------
Comment: was deleted
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Owen O'Malley
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi updated HADOOP-485:
--------------------------------
Status: Patch Available (was: Open)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489818 ]
Doug Cutting commented on HADOOP-485:
-------------------------------------
First, I don't think we can assume that the key comparator will also work for values. We should permit specification of an additional comparator for values. (An Exception should be thrown if values are not WritableComparables.)
Second, this shouldn't be triggered for all jobs, but only those that specify a value comparator.
Third, this implementation seems inconsistent. You've changed some code paths, but not considered other code paths. For example, SequenceFile compares keys in lots of places. If we want to permit SequenceFile's sorting tools to consider values, then we should consistently modify all of SequenceFile's uses of comparators. Similarly, you've changed value sorting in one step of the sort, but there are many other places where sorting is done that I'm not sure are addressed by this patch.
I wonder if instead this might be more simply implemented at reduce time. ReduceTask could be modified to buffer and sort values. If there are more values for a key than fit in memory, then the values could be spilled to disk as a SequenceFile and sorted. Might that work?
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Sameer Paranjpye (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12467113 ]
Sameer Paranjpye commented on HADOOP-485:
-----------------------------------------
Is the topology persistence a consequence of us serializing Datanode descriptors to the image? This was implemented a while ago and has probably never made sense.
We should file a follow-on issue to not persist Datanode information in the image.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Owen O'Malley
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Doug Cutting (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Doug Cutting updated HADOOP-485:
--------------------------------
Resolution: Fixed
Fix Version/s: 0.13.0
Status: Resolved (was: Patch Available)
I just committed this. Thanks, Tahir!
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Fix For: 0.13.0
>
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Devaraj Das (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12491288 ]
Devaraj Das commented on HADOOP-485:
------------------------------------
Some comments:
You needn't explicitly do the 'null' check for the return value of getOutputValueGroupingComparator(). The getClass call within getOutputValueGroupingComparator could take the default value as getOutputKeyComparator().
Also, the testcase is difficult to read. Some comments should be put there.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Johan Oskarson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12477038 ]
Johan Oskarson commented on HADOOP-485:
---------------------------------------
I take it this is a low priority since northing's happened for a while.
I'm thinking about doing some changes in my map-reduce programs and unfortunately a few of them would require this to be implemented.
I don't know all that much about how this part of hadoop works, are there any outstanding tickets that need to be fixed before this can go ahead?
Thanks
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Owen O'Malley
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Owen O'Malley (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12489832 ]
Owen O'Malley commented on HADOOP-485:
--------------------------------------
Sorry, I wasn't tracking this discussion fast enough to stop the huge discussion.
As Doug said, the intent was always to compare keys. It is just that you want to control the grouping to the reduce.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12492678 ]
Hadoop QA commented on HADOOP-485:
----------------------------------
-1, new javadoc warnings
The javadoc tool appears to have generated warning messages when testing the latest attachment http://issues.apache.org/jira/secure/attachment/12356508/485.patch against trunk revision r533233.
Test results: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/93/testReport/
Console output: http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Patch/93/console
Please note that this message is automatically generated and may represent a problem with the automation system and not the patch.
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Attachments: 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Tahir Hashmi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tahir Hashmi reassigned HADOOP-485:
-----------------------------------
Assignee: Tahir Hashmi (was: Owen O'Malley)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HADOOP-485) allow a different comparator for
grouping keys in calls to reduce
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-485?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12493648 ]
Hadoop QA commented on HADOOP-485:
----------------------------------
Integrated in Hadoop-Nightly #78 (See http://lucene.zones.apache.org:8080/hudson/job/Hadoop-Nightly/78/)
> allow a different comparator for grouping keys in calls to reduce
> -----------------------------------------------------------------
>
> Key: HADOOP-485
> URL: https://issues.apache.org/jira/browse/HADOOP-485
> Project: Hadoop
> Issue Type: New Feature
> Components: mapred
> Affects Versions: 0.5.0
> Reporter: Owen O'Malley
> Assigned To: Tahir Hashmi
> Fix For: 0.13.0
>
> Attachments: 485.patch, 485.patch, 485.patch, 485.patch, 485.patch, Hadoop-485-pre.patch, TestUserValueGrouping.java.patch
>
>
> Some algorithms require that the values to the reduce be sorted in a particular order, but extending the key with the additional fields causes them to be handled by different calls to reduce. (The user then collects the values until they detect a "real" key change and then processes them.)
> It would be much easier if the framework let you define a second comparator that did the grouping of values for reduces. So your reduce inputs look like:
> A1, V1
> A2, V2
> A3, V3
> B1, V4
> B2, V5
> instead of getting calls to reduce that look like:
> reduce(A1, {V1}); reduce(A2, {V2}); reduce(A3, {V3}); reduce(B1, {V4}); reduce(B2, {V5});
> you could define the grouping comparator to just compare the letters and end up with:
> reduce(A1, {V1,V2,V3}); reduce(B1, {V4,V5});
> which is the desired outcome. Note that this assumes that the "extra" part of the key is just for sorting because the reduce will only see the first representative of each equivalence class.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.