You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@pig.apache.org by "Amir Youssefi (JIRA)" <ji...@apache.org> on 2008/03/28 05:00:24 UTC
[jira] Created: (PIG-171) Top K
Top K
-----
Key: PIG-171
URL: https://issues.apache.org/jira/browse/PIG-171
Project: Pig
Issue Type: New Feature
Reporter: Amir Youssefi
Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
The same idea is applicable to solve variants of this problem:
- An Algebraic Function for 'Top K Rows'
- An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
- TOP K ORDER BY.
Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Commented: (PIG-171) Top K
Posted by Ted Dunning <te...@gmail.com>.
If I want to do a sample, I will typically filter by a uniform random
number, not take the top k.
And if I do take the top K, K is usually fairly small so sorting it by
conventional mechanisms later is fine by me.
On Sun, Jun 8, 2008 at 4:05 AM, Pi Song (JIRA) <ji...@apache.org> wrote:
>
> [
> https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12603362#action_12603362]
>
> Pi Song commented on PIG-171:
> -----------------------------
>
> Ted (From mailing-list):
> bq. An efficient implementation of top K without full histogramming would
> still be very, very useful.
>
> Logically (not by experience) I still concern about TOP K without order.
> Does this thing really have a good use? The formal definition of TOP K
> always goes with scoring function. Naturally, we also say we want TOP K
> order by something.
>
> The only use case that I would think people might be doing TOP K without
> order is just to work with sample data. But then doing TOP K is not gonna
> give a statistically good representation. My idea is that it should be
> better if we design the language by not allowing people to do the wrong
> thing.
>
> If people want to do approximate queries I think we'd better provide a
> proper way like adding:-
>
> {code}
> X = SAMPLE 10% OF A ;
> Y = SAMPLE 100 OF B ;
> {code}
>
> What do you think?
>
> > Top K
> > -----
> >
> > Key: PIG-171
> > URL: https://issues.apache.org/jira/browse/PIG-171
> > Project: Pig
> > Issue Type: New Feature
> > Reporter: Amir Youssefi
> > Assignee: Amir Youssefi
> >
> > Frequently, users are interested on Top results (especially Top K rows) .
> This can be implemented efficiently in Pig /Map Reduce settings to deliver
> rapid results and low Network Bandwidth/Memory usage.
> >
> > Key point is to prune all data on the map side and keep only small set
> of rows with Top criteria . We can do it in Algebraic function (combiner)
> with multiple value output. Only a small data-set gets out of mapper node.
> > The same idea is applicable to solve variants of this problem:
> > - An Algebraic Function for 'Top K Rows'
> > - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense
> Rank K')
> > - TOP K ORDER BY.
> > Another words implementation is similar to combiners for aggregate
> functions but instead of one value we get multiple ones.
> > I will add a sample implementation for Top K Rows and possibly TOP K
> ORDER BY to clarify details.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
--
ted
Re: [jira] Commented: (PIG-171) Top K
Posted by Ted Dunning <te...@gmail.com>.
An efficient implementation of top K without full histogramming would still
be very, very useful.
On Sat, Jun 7, 2008 at 5:35 PM, Pi Song (JIRA) <ji...@apache.org> wrote:
>
> [
> https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12603350#action_12603350]
>
> Pi Song commented on PIG-171:
> -----------------------------
>
> Seems like all efficient histogram generation algorithms are probabilistic
> so my optimization idea wouldn't work.
>
> > Top K
> > -----
> >
> > Key: PIG-171
> > URL: https://issues.apache.org/jira/browse/PIG-171
> > Project: Pig
> > Issue Type: New Feature
> > Reporter: Amir Youssefi
> > Assignee: Amir Youssefi
> >
> > Frequently, users are interested on Top results (especially Top K rows) .
> This can be implemented efficiently in Pig /Map Reduce settings to deliver
> rapid results and low Network Bandwidth/Memory usage.
> >
> > Key point is to prune all data on the map side and keep only small set
> of rows with Top criteria . We can do it in Algebraic function (combiner)
> with multiple value output. Only a small data-set gets out of mapper node.
> > The same idea is applicable to solve variants of this problem:
> > - An Algebraic Function for 'Top K Rows'
> > - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense
> Rank K')
> > - TOP K ORDER BY.
> > Another words implementation is similar to combiners for aggregate
> functions but instead of one value we get multiple ones.
> > I will add a sample implementation for Top K Rows and possibly TOP K
> ORDER BY to clarify details.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
--
ted
RE: [jira] Commented: (PIG-171) Top K
Posted by Haijun Cao <ha...@kindsight.net>.
Yes, I agree. TOP and SAMPLE are different operators.
Haijun
-----Original Message-----
From: Daniel Dai (JIRA) [mailto:jira@apache.org]
Sent: Thursday, June 19, 2008 12:20 PM
To: pig-dev@incubator.apache.org
Subject: [jira] Commented: (PIG-171) Top K
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12606518#action_12606518 ]
Daniel Dai commented on PIG-171:
--------------------------------
If we use "SAMPLE" instead of "LIMIT" for first k output, people will expect this is a fairly random sample. They may not notice that the sample they've got is just a "first k". To me, it seems to be more confusing. What Pi suggested is a dedicated "SAMPLE" operator. It should be a random sample and should have a different implementation. How do you think?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alan Gates updated PIG-171:
---------------------------
Resolution: Fixed
Status: Resolved (was: Patch Available)
Checked into types branch, thanks Daniel for all your work on this.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12609291#action_12609291 ]
Daniel Dai commented on PIG-171:
--------------------------------
Debugging now, should be finished by this week.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12600228#action_12600228 ]
Alan Gates commented on PIG-171:
--------------------------------
Pi, I don't follow your last comment. How does knowing the number of records help us? We still have to sort all the records in order to get the first x number of records correctly.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amir Youssefi updated PIG-171:
------------------------------
Assignee: (was: Amir Youssefi)
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12623540#action_12623540 ]
Amir Youssefi commented on PIG-171:
-----------------------------------
Daniel,
Thanks for the patches. Going back to single reducer over-load issue I mentioned in May 21st comment:
https://issues.apache.org/jira/browse/PIG-171?focusedCommentId=12598862#action_12598862
We can now consider having multiple MR steps. I was avoiding it because of logic complexity. Having more MR steps is rather cheap and cluster is already allocated for us.
To address this, instead of sending map results to one reducer,
Solutions A (constant number of MR jobs): we can use many reducers to do in-memory merge LIMIT between output of multiple maps. Results will hit the disk and second MR job does the same task but this time sends all to single reducer. This way we have greatly reduced load on a single reducer (it has to merge far less rows).
Solution B (merge degree / fan-out): We use multiple MR jobs and in each step map/reduce task merge (does in-memory LIMIT) between D (degree) number of inputs. With each set of tasks we divide number of inputs to be merged by D till it becomes 1. That is when we finish.
Set of tasks above can be both Map and Reduce side. We can skip map side for simplicity (no multi input format). We use identity mappers and each reducer merges D to 1.
We can discuss detecting when we hit 1. One ways is to assume reducers with no output row don't create a part file and number of input files gets reduced in each step and eventually we stop when only one input file exists.
There is a JIRA for makings sure reducers with not output don't create a file.
There may be better ways to do this e.g. any new MR job uses reducer 0 to r and in each step we divide r by D (just like number in PARALLEL command) till we hit 1.
Thoughts?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Johannes Zillmann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12609177#action_12609177 ]
Johannes Zillmann commented on PIG-171:
---------------------------------------
Hi Daniel, how is the status with "limited sort" ?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Olga Natkovich (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12609661#action_12609661 ]
Olga Natkovich commented on PIG-171:
------------------------------------
It is ok to have additional syntax for testing. I don't think we want to add new syntax to Pig. Lets keep things orthogonal.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598862#action_12598862 ]
Amir Youssefi commented on PIG-171:
-----------------------------------
As Pi Song mentioned LIMIT n,m (or LIMIT n TO m) doesn't show many optimization opportunities on map side. We have to send all top m rows from mapper to reducer.
Now consider we have those sent to one reducer. Next step is to run BOTTOM (m-n+1) function over results of maps already sent to reducer. We can have a BOTTOM AWARE MERGER (which is reverse of results on one node and we are done.
I don't recommend making it more complicated but if somebody is concerned about chocking one reducer with large m row data-sets we can send results of the first step to multiple reducers and then running a second Map Reduce job with TOP (m-n+1) with comparator of -1 * MY_COMPARATOR() and single reducer to get the final results.
I suggest we think about LIMIT n,m as extension of LIMIT n and do that later.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12609580#action_12609580 ]
Pi Song commented on PIG-171:
-----------------------------
SAMPLE should be real random sampling.
Looking forward to seeing the full patch.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12603350#action_12603350 ]
Pi Song commented on PIG-171:
-----------------------------
Seems like all efficient histogram generation algorithms are probabilistic so my optimization idea wouldn't work.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12585114#action_12585114 ]
Pi Song commented on PIG-171:
-----------------------------
Small interesting bit here:-
- For TOPK, you keep K rows in first level aggregation.
- For LIMIT N to M, you keep M rows in first level aggregation.
- If M-N = 1 and M is really big, the amount of data kept for doing LIMIT can be ridiculously too much.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12600517#action_12600517 ]
Pi Song commented on PIG-171:
-----------------------------
So, by implementation we always calculate n-tiles before doing real sort, right? If say we are interested in Top 1000 out of 10000 inputs, that means we can discard all the records below 90th percentile in the map phase.
However, in order to do this, we will need a deterministic way to calculate n-tiles (The current way is apparently probabilistic).
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alan Gates updated PIG-171:
---------------------------
Fix Version/s: types_branch
Affects Version/s: types_branch
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alan Gates updated PIG-171:
---------------------------
Issue Type: Sub-task (was: New Feature)
Parent: PIG-157
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Haijun Cao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12606489#action_12606489 ]
Haijun Cao commented on PIG-171:
--------------------------------
To me, LIMIT is little vague, can we have two different keywords: TOP and SAMPLE like Pi suggested?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12617023#action_12617023 ]
daijy edited comment on PIG-171 at 7/25/08 12:37 PM:
----------------------------------------------------------
Some explanation on output of first n sample:
1. The output is not always the first n records in input file
2. The output set could be
* Take first n records from each map, then top n records among those records, if there is limit operator on map side
* Top n records globally, otherwise
3. The output set is sorted by hadoop before presenting to the user
Here "first n" means the unsorted result come directly from input, "top n" means sorted result, the sort order is defined by hadoop sort key.
If limit is combined with other operator, the order could be more complex, here is just a simplified guildline.
was (Author: daijy):
Some explanation on output of first n sample:
1. The output is not always the first n records in input file
2. The output set could be
* Take first n records from each map, then top n records among those records, if there is limit operator on map side
* Top n records globally, otherwise
2. The output set is sorted by hadoop before presenting to the user
Here "first n" means the unsorted result come directly from input, "top n" means sorted result, the sort order is defined by hadoop sort key.
If limit is combined with other operator, the order could be more complex, here is just a simplified guildline.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12583106#action_12583106 ]
Alan Gates commented on PIG-171:
--------------------------------
A few questions/comments:
1) In your example of TOP(123, A) rows, what does the A mean?
2) I don't understand the differentiation between the three bullet points you give in the description. Could you elaborate and give examples of how each would be used?
3) You propose doing this as a UDF, but that only gives you some of what we really want. This will allow pig to use the combiner. Eventually, to offer full functionality, we'll want to be able to do this on non-grouped/ordered data (just being able to see the first X records of a file is great for expirementation and development). This doesn't mean we can't support as a UDF for now, and promote it later. But it does mean we need to think carefully about how we want to do it.
4) You're counting on using the combiner to make this efficient. But in the current implementation the combiner won't be used except in very specific circumstances (a group by followed by a foreach that includes the group). General use of the combiner won't be in place until the pipeline rework is ready.
5) Syntax question, do we want to use TOPK or LIMIT? I tend to think of TOPK as implying top results of an aggregation, vs LIMIT just meaning a certain number of rows, not necessarily implying any grouping. Maybe others don't use this distinction. LIMIT also allows an offset (give me rows 10000-20000) in addition to allowing just the first X rows. I don't care which we use, but it seems like we ought to discuss it in case some people have strong views one way or another.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12606518#action_12606518 ]
Daniel Dai commented on PIG-171:
--------------------------------
If we use "SAMPLE" instead of "LIMIT" for first k output, people will expect this is a fairly random sample. They may not notice that the sample they've got is just a "first k". To me, it seems to be more confusing. What Pi suggested is a dedicated "SAMPLE" operator. It should be a random sample and should have a different implementation. How do you think?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12600960#action_12600960 ]
Pi Song commented on PIG-171:
-----------------------------
We need an n-tile calculation which is:-
- Cheap
- Deterministic
I couldn't think of any except relying on histograms
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alan Gates updated PIG-171:
---------------------------
Status: Patch Available (was: Open)
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12600814#action_12600814 ]
Alan Gates commented on PIG-171:
--------------------------------
So are you suggesting that by doing the sampling correctly we could distribute the data in a such a way that we could throw away all but a few maps output? That seems doable, but also like a big change. I would be inclined to leave that for later.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12609678#action_12609678 ]
Daniel Dai commented on PIG-171:
--------------------------------
I agree, this syntax is only for test purpose. Will remove it when optimizer is ready.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12606136#action_12606136 ]
Daniel Dai commented on PIG-171:
--------------------------------
I am working on the implementation of "LIMIT". There are two usecases for "LIMIT": sampling and top k. We can leave "LIMIT" as a "quick and dirty" approach to get sample. Although this sample is not perfect, it is cheaper. We can treat a dedicated "SAMPLE" statement as a seperate case if people ask for it.
Current design of "LIMIT" is:
# There is a single interface to the user, eg,
B = limit A 100;
We generate LOLimit for this statement
# Logical layer optimizor will try to push LOLimit up, if there is a LOSort in front of LOLimit, then merge LOLimit into LOSort, put a hint to LOSort. LOSort will do a "limited sort" in this case
# In physical layer, we have LOLimit->POLimit and LOSort->POSort relating to this new operation
#* POLimit will retrieve first k samples
#* POSort will do a limited sort if there is a "limit" hint, optimize the internal process of sorting
# In map-reduce
#* POLimit can be put in
\* Reduce plan, or
\* Both map plan and reduce plan to speed up more
If map plan is done, simply put POLimit into reduce plan. If not, add POLimit into map plan, close map plan, and then put another POLimit into reduce plan. If this is the case, we could increase the number of map-reduce operations by 1
#* POSort is compiled into two map-reduce operations: getQuantile and sort. There is no change in the first map-reduce, for the second, we will:
\* Keep top k records in each mapper. We should put this code in the combine-plan, and
\* Put POLimit in the reduce plan
Also we need to take the new hadoop 18 combiner behavior into account (https://issues.apache.org/jira/browse/PIG-274)
How are others thinking?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598851#action_12598851 ]
Amir Youssefi commented on PIG-171:
-----------------------------------
OK, it's time to move this topic forward. Here are more details and response to comments:
My original idea was to implement this as a combiner (algebraic function). Just like SUM or MAX etc. , we develop a combiner which gets top K rows (by some comparator) on each map node and passes those rows to reducer. Reducer gets m*K rows (m being number of mappers) and only keeps Top K rows (using the same comparator) and gives it as output. Idea is to use following optimization opportunities:
A) Limit number of rows sent from mapper to reducer to K instead of all map output rows.
B) In mapper, since we know that intention is using only Top K rows then we can do very good optimizations e.g. in case of sort (ORDER BY) we just keep top K rows (say having 100 sorted rows in memory and comparing new rows with those 100 as we read/stream new rows). Let's call this TOP/LIMIT aware implementation.
C) Implementation of the part which combines results in reducer is similar to item 2 above.
Since we last discussed the issue, users/dev members have gotten more interested in this and feature found it's way into Pig Road Map. So we can upgrade idea from UDF to core built-in functionality.
Now to answer Alan's comments:
5) Name doesn't really matter MS SQL Server uses TOP, My SQL uses LIMIT, Oracle users rownum, row_number(partition by order by), rank() and dense_rank(). Academics use Top N, Top K in somewhat similar context. LIMIT sounds good to me as well. Especially if we want to have a range LIMIT n,m
4) That's correct. So one workaround was grouping by all columns and using "group" in foreach to have combiner kick-in. It's easy. Pipeline rework is nearby so we can skip workaround and use new things.
3) Now that we have attention of people/developers, we can upgrade idea from UDF to core built-in functionality.
2) It's about what we define as top rows. We can say top 100 rows according to a sequence number (equivalent of Oracle row_number() , rownum). But in many scenarios, user is interested in top values not just number of rows (similar to oracle: rank()) or dense_rank()). Let's skip details of handling equal values for now and implement simples ones ten revisit when we have forged main issues.
1) I had to do that for UDF. Now that we are upgrading to Pig built-in we can use something like ORDER BY $0 using MY_COMPARATOR in one line then use LIMIT 100 on second line and expect Pig to optimize implementation of ORDER taking into account that we care about 100 rows only. See item B above which means implementation of sort in a way that we just keep 100 rows (LIMIT/TOP aware implementation as opposed to sorting the whole data-set then keep 100 rows of it). Another way of design might be having both generic LIMIT that can be used on every variable and a LIMIT used on the same line of ORDER i.e. ORDER by $0 using MY_COMPARATOR LIMIT 100. This may trigger LIMIT AWARE ORDER easier. I leave this to Alan.
We can consider above as our road-map but implement things step-by-step. First LIMIT K on one line pushing the row dropping to mappers. Then optimization of implementing LIMIT aware sort and such. A UDF can do both A and B.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611703#action_12611703 ]
Alan Gates commented on PIG-171:
--------------------------------
Daniel, the patch looks good. A few small comments:
1) in LOLimit, I think Santhosh has gone back and changed all the schema getSchema calls to just check mIsSchemaComputed, removing the check whether mSchema is null.
2) in POLimit, it's swallowing nulls. I don't think it should. Nulls should be returned and counted as one of the returns records.
This patch also makes use of the combiner. I want to add general combiner functionality next week, so I'm going to hold off applying this until I've figured out in general how I want to push things into the combiner.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amir Youssefi reassigned PIG-171:
---------------------------------
Assignee: Amir Youssefi
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12598862#action_12598862 ]
amirhyoussefi edited comment on PIG-171 at 5/21/08 4:46 PM:
------------------------------------------------------------
As Pi Song mentioned LIMIT n,m (or LIMIT n TO m) doesn't show many optimization opportunities on map side. We have to send all top m rows from mapper to reducer.
Now consider we have those sent to one reducer. Next step is to run TOP (m-n+1) function over results of maps already sent to reducer. We can use the same MERGER as we had in simple LIMIT but this time make it keep only TOP (m-n+1) while it merges locally and we are done.
I don't recommend making it more complicated but if somebody is concerned about chocking one reducer with large m row data-sets we can write a custom version that combines partial results of the first step to multiple reducers creating TOP (m-n+1). A second Map Reduce job gets TOP (m-n+1) with single reducer and writes final results.
I suggest we think about LIMIT n,m as extension of LIMIT n and do that later.
was (Author: amirhyoussefi):
As Pi Song mentioned LIMIT n,m (or LIMIT n TO m) doesn't show many optimization opportunities on map side. We have to send all top m rows from mapper to reducer.
Now consider we have those sent to one reducer. Next step is to run BOTTOM (m-n+1) function over results of maps already sent to reducer. We can have a BOTTOM AWARE MERGER (which is reverse of results on one node and we are done.
I don't recommend making it more complicated but if somebody is concerned about chocking one reducer with large m row data-sets we can send results of the first step to multiple reducers and then running a second Map Reduce job with TOP (m-n+1) with comparator of -1 * MY_COMPARATOR() and single reducer to get the final results.
I suggest we think about LIMIT n,m as extension of LIMIT n and do that later.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12603362#action_12603362 ]
Pi Song commented on PIG-171:
-----------------------------
Ted (From mailing-list):
bq. An efficient implementation of top K without full histogramming would still be very, very useful.
Logically (not by experience) I still concern about TOP K without order. Does this thing really have a good use? The formal definition of TOP K always goes with scoring function. Naturally, we also say we want TOP K order by something.
The only use case that I would think people might be doing TOP K without order is just to work with sample data. But then doing TOP K is not gonna give a statistically good representation. My idea is that it should be better if we design the language by not allowing people to do the wrong thing.
If people want to do approximate queries I think we'd better provide a proper way like adding:-
{code}
X = SAMPLE 10% OF A ;
Y = SAMPLE 100 OF B ;
{code}
What do you think?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12617023#action_12617023 ]
Daniel Dai commented on PIG-171:
--------------------------------
Some explanation on output of first n sample:
1. The output is not always the first n records in input file
2. The output set could be
* Take first n records from each map, then top n records among those records, if there is limit operator on map side
* Top n records globally, otherwise
2. The output set is sorted by hadoop before presenting to the user
Here "first n" means the unsorted result come directly from input, "top n" means sorted result, the sort order is defined by hadoop sort key.
If limit is combined with other operator, the order could be more complex, here is just a simplified guildline.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12599367#action_12599367 ]
Pi Song commented on PIG-171:
-----------------------------
One more thing. When we do sort, we start with generating percentile ranks. If we could count the number of records at the same time here, there is another opportunity to get rid of unneeded data.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12625601#action_12625601 ]
Daniel Dai commented on PIG-171:
--------------------------------
Hi, Amir,
Thanks for your suggestion. Here is my concern:
1. To find an optimal setting automatically, we need to do experiments with different settings on various clusters. Seems not possible for now. So currently, we will take the parameter from user. User has to tell pig if they wish to use multi-stage, and number of stages / fan-out. Since we do not have pig.property now, shall we put it on command line?
2. It sounds to me this issue is more general in nature. Many map-reduce can be divided into multi-stages. So to which layer should this issue to be addressed? In limit operator, pig layer or map-reduce layer?
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: Sub-task
> Affects Versions: types_branch
> Reporter: Amir Youssefi
> Fix For: types_branch
>
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Alan Gates (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12599042#action_12599042 ]
Alan Gates commented on PIG-171:
--------------------------------
Here's an initial stab at a design for LIMIT.
To begin with we will implement LIMIT n, where n is the number of rows to return. If users ask for an offset capability in the future (LIMIT m, n where m is
an offset and n number of rows) it's easy enough to add.
Limit will be implemented in the new pipeline rework, as the framework is in place there to more easily add it and to allow the optimizer to work with it.
The following areas will need to be changed to work with LIMIT:
1) Syntax in QueryParser.jjt. LIMIT will need to be supported as statement in the language. So it should now be possible to say:
B = limit A 100;
...
Unit tests for this should be added to TestLogicalPlanBuilder.
2) Add LOLimit operator to logical operators. This should be straight forward, as limit will not modify the schema of its input relation.
3) Add POLimit operator to physical operators. getNext() will need to keep a count of the number of times it's been called. Once that count exceeds the
provided limit, it will simply return END_OF_PROCESSING instead of calling getNext on it's predecessor. A new set of unit tests will need to be added for
this operator.
4) LogToPhyTranslationVisitor and MRCompiler will need be changed to handle translation of LOLimit and POLimit. Unit tests should be added to
TestLogToPhyCompiler and TestMRCompiler.
5) The logical optimizer (not yet built) will need to include rules for handling pushing of Limit to the extent possible. The rules should look like:
Limit cannot be pushed in front of:
LOCogroup
LOFilter
LOLoad
LOSort
LOSplit
LOSplitOutput
LOStream (once that is in)
Limit can be pushed in front of:
LOForEach, if it does not have a flatten.
Limit can be duplicated, and the new instance pushed in front of an operator for the following operators (that is, if you have X->limit, you can transform
that to limit->X->limit):
LOCross
LODistinct
LOForEach when it has a flatten
LOUnion
6) The MRCompiler will need to know that it can move limit into the combiner in certain cases. If limit is the first operation in the reduce, then it can be
replicated and placed in the combine in addition to being in the reduce.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Daniel Dai updated PIG-171:
---------------------------
Attachment: limit3.patch
Thanks Alan. I changed patch according to the comments.
Also limit3.patch include LOLimit optimizer. This patch includes optimizer patch ([PIG-262|https://issues.apache.org/jira/browse/PIG-262]). I am still testing on it while some simple cases are working now.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch, limit3.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Daniel Dai updated PIG-171:
---------------------------
Attachment: limit2.patch
Attached patch for both "first k sample" and "limited sort". I am still working on an optimizer to push "POLimit" upward, merge "POLimit" and "POSort" into a "limited sort".
I also add a syntax "A = ORDER B BY $0 LIMIT 100", so we can test "limited sort" without the optimizer.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch, limit2.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Amir Youssefi (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12582919#action_12582919 ]
Amir Youssefi commented on PIG-171:
-----------------------------------
Usage:
C = FOREACH B GENERATE TOP(123,A) -- For Top 123 rows
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (PIG-171) Top K
Posted by "Daniel Dai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Daniel Dai updated PIG-171:
---------------------------
Attachment: limit1.patch
Patch for "first k" sample. Still working on "limited sort".
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Attachments: limit1.patch
>
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (PIG-171) Top K
Posted by "Pi Song (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/PIG-171?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12599362#action_12599362 ]
Pi Song commented on PIG-171:
-----------------------------
The optimization idea looks interesting!
More on implementation level:-
1. Start from the original LOLimit. Walk in reverse depth-first search order. There might be a number of branches that we have to go.
2. In each branch, until the next operator in the path is not qualified for
- The operator doesn't reduce the number of rows
- The operator is not LOSort or LOLoad
We stop and create a new LOLimit next to it.
> Top K
> -----
>
> Key: PIG-171
> URL: https://issues.apache.org/jira/browse/PIG-171
> Project: Pig
> Issue Type: New Feature
> Reporter: Amir Youssefi
> Assignee: Amir Youssefi
>
> Frequently, users are interested on Top results (especially Top K rows) . This can be implemented efficiently in Pig /Map Reduce settings to deliver rapid results and low Network Bandwidth/Memory usage.
>
> Key point is to prune all data on the map side and keep only small set of rows with Top criteria . We can do it in Algebraic function (combiner) with multiple value output. Only a small data-set gets out of mapper node.
> The same idea is applicable to solve variants of this problem:
> - An Algebraic Function for 'Top K Rows'
> - An Algebraic Function for 'Top K' values ('Top Rank K' and 'Top Dense Rank K')
> - TOP K ORDER BY.
> Another words implementation is similar to combiners for aggregate functions but instead of one value we get multiple ones.
> I will add a sample implementation for Top K Rows and possibly TOP K ORDER BY to clarify details.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.