You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@pig.apache.org by "Aneesh Sharma (JIRA)" <ji...@apache.org> on 2012/06/28 02:03:44 UTC
[jira] [Created] (PIG-2774) Fix merge join to work with many
duplicate left keys
Aneesh Sharma created PIG-2774:
----------------------------------
Summary: Fix merge join to work with many duplicate left keys
Key: PIG-2774
URL: https://issues.apache.org/jira/browse/PIG-2774
Project: Pig
Issue Type: Bug
Reporter: Aneesh Sharma
A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
1. Serialize the accumulated tuples to disk if they exceed a certain size.
2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (PIG-2774) Fix merge join to work with many
duplicate left keys
Posted by "Thejas M Nair (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-2774?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13403480#comment-13403480 ]
Thejas M Nair commented on PIG-2774:
------------------------------------
bq. we might have other operations queued up after the join
In 2nd approach, the operations within map task don't complicate things. But to handle a reduce after the merge-join, we would need to introduce another map task that does a union of merge-join results. For example, if the merge-join is followed by a group+agg , then the follow transformation to plan would be needed.
Map(Merge-join + group+agg ops) + Reduce(group+agg ops)
=> Map (merge-join wave 1 + group+agg ops) + Map (merge-join wave 2 + group+agg opps) + Map(union of 1st 2 maps) + Reduce(group+agg ops)
This transformation can't happen dynamically - we can't decide to skip the reduce while in the map phase.
To handle this case dynamically, looks like the first approach is one that actually would work! The user or a metadata system possibly identify the skew problem and recommend using a 'skew-merge' join next time query is run on similar data.
> Fix merge join to work with many duplicate left keys
> ----------------------------------------------------
>
> Key: PIG-2774
> URL: https://issues.apache.org/jira/browse/PIG-2774
> Project: Pig
> Issue Type: Bug
> Reporter: Aneesh Sharma
>
> A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
> 1. Serialize the accumulated tuples to disk if they exceed a certain size.
> 2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (PIG-2774) Fix merge join to work with many
duplicate left keys
Posted by "Thejas M Nair (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-2774?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13402722#comment-13402722 ]
Thejas M Nair commented on PIG-2774:
------------------------------------
If the left side relations tuples for a value of join key are serialized to disk, then for ever value of join key in right relation, it will hit the disk. That will perform very poorly.
Looks like what we need is something like a merge-skew join. Ie, similar to skew join, sample left side, and partition the splits for map tasks based on sampled information.
> Fix merge join to work with many duplicate left keys
> ----------------------------------------------------
>
> Key: PIG-2774
> URL: https://issues.apache.org/jira/browse/PIG-2774
> Project: Pig
> Issue Type: Bug
> Reporter: Aneesh Sharma
>
> A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
> 1. Serialize the accumulated tuples to disk if they exceed a certain size.
> 2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (PIG-2774) Fix merge join to work with many
duplicate left keys
Posted by "Dmitriy V. Ryaboy (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-2774?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13402923#comment-13402923 ]
Dmitriy V. Ryaboy commented on PIG-2774:
----------------------------------------
Generating non-standard splits can get tricky in the solution Thejas proposed.. Also I'd like to avoid having the user encode these details in the pig script.
> Fix merge join to work with many duplicate left keys
> ----------------------------------------------------
>
> Key: PIG-2774
> URL: https://issues.apache.org/jira/browse/PIG-2774
> Project: Pig
> Issue Type: Bug
> Reporter: Aneesh Sharma
>
> A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
> 1. Serialize the accumulated tuples to disk if they exceed a certain size.
> 2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (PIG-2774) Fix merge join to work with many
duplicate left keys
Posted by "Thejas M Nair (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-2774?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13403461#comment-13403461 ]
Thejas M Nair commented on PIG-2774:
------------------------------------
bq. I'd like to avoid having the user encode these details in the pig script.
Floating some more ideas -
A more performant way of doing this would be to stop accumulating tuples for a join key value from left relation into memory when a certain memory threshold is exceeded. Once join of these tuples against the right relation is done, discard the accumulated left rel tuples for the join key and and load a new set, go back to the start of relations with this join key in right relation and continue.
To go back more efficiently to the start of join key in right relation we can keep track of its record offset. This approach will have no additional writes and have less IO overall. The right relation block hopefully gets in to OS cache.
But this approach can result in some map tasks being much slower than others.
Another option is to write the left side join key values that didn't fit into memory onto hdfs in separate files, one file for each chunch that is expected to fit into memory, and have another round of MR job do merge join on these files. ( I think hive has a skew join impl on similar lines). This would involve changing the MR plan at runtime.
> Fix merge join to work with many duplicate left keys
> ----------------------------------------------------
>
> Key: PIG-2774
> URL: https://issues.apache.org/jira/browse/PIG-2774
> Project: Pig
> Issue Type: Bug
> Reporter: Aneesh Sharma
>
> A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
> 1. Serialize the accumulated tuples to disk if they exceed a certain size.
> 2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (PIG-2774) Fix merge join to work with many
duplicate left keys
Posted by "Dmitriy V. Ryaboy (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-2774?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13403468#comment-13403468 ]
Dmitriy V. Ryaboy commented on PIG-2774:
----------------------------------------
I like the first paragraph of what you said; the second is more applicable to skew join (reduce side) than map join (map side), I think. With a mapside join, we might have other operations queued up after the join happening on the same mapper, and tracing through separate split files will get unnecessarily complicated.
> Fix merge join to work with many duplicate left keys
> ----------------------------------------------------
>
> Key: PIG-2774
> URL: https://issues.apache.org/jira/browse/PIG-2774
> Project: Pig
> Issue Type: Bug
> Reporter: Aneesh Sharma
>
> A merge join can throw an OOM error if the number of duplicate left tuples is large as it accumulates all of them in memory. There are two solutions around this problem:
> 1. Serialize the accumulated tuples to disk if they exceed a certain size.
> 2. Spit out join output periodically, and re-seek on the right hand side index.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira