When you flatten your BAG all your segments are within a single tuple. Something like
((tag, ipstart, ipend, loc), (tag, ipstart, ipend, loc)...(tagN, ipstartN, ipendN, locN)) You can access the inner tuples positionally. Sent from my iPhone On Dec 14, 2011, at 6:28 PM, "唐亮" <[email protected]> wrote: > Now the question is: > How should I put all the "IP Segments" in one TUPLE? > > Please help me! > > > 2011/12/15 Prashant Kommireddi <[email protected]> > >> Michael, >> >> This would have no benefit over using a DistributedCache. For a large >> cluster this would mean poor performance. If the file is static and needs >> to be looked-up across the cluster, DistributedCache would be a better >> approach. >> >> Thanks, >> Prashant >> >> On Wed, Dec 14, 2011 at 11:18 AM, jiang licht <[email protected]> >> wrote: >> >>> If that list of ip pairs is pretty static most time and will be used >>> frequently, maybe just copy it in hdfs with a high replication factor. >> Then >>> use it as a look up table or some binary tree or treemap kind of thing by >>> reading it from hdfs instead of using distributed cache if that sounds an >>> easier thing to do. >>> >>> >>> Best regards, >>> Michael >>> >>> >>> ________________________________ >>> From: Dmitriy Ryaboy <[email protected]> >>> To: [email protected] >>> Sent: Wednesday, December 14, 2011 10:28 AM >>> Subject: Re: Implement Binary Search in PIG >>> >>> hbase has nothing to do with distributed cache. >>> >>> >>> 2011/12/14 唐亮 <[email protected]> >>> >>>> Now, I didn't use HBase, >>>> so, maybe I can't use DistributedCache. >>>> >>>> And if FLATTEN DataBag, the results are Tuples, >>>> then in UDF I can process only one Tuple, which can't implement >>>> BinarySearch. >>>> >>>> So, please help and show me the detailed solution. >>>> Thanks! >>>> >>>> 在 2011年12月14日 下午5:59，唐亮 <[email protected]>写道： >>>> >>>>> Hi Prashant Kommireddi， >>>>> >>>>> If I do 1. and 2. as you mentioned， >>>>> the schema will be {tag, ipStart, ipEnd, locName}. >>>>> >>>>> BUT, how should I write the UDF, especially how should I set the type >>> of >>>>> the input parameter? >>>>> >>>>> Currently, the UDF codes are as below, whose input parameter is >>> DataBag: >>>>> >>>>> public class GetProvinceNameFromIPNum extends EvalFunc<String> { >>>>> >>>>> public String exec(Tuple input) throws IOException { >>>>> if (input == null || input.size() == 0) >>>>> return UnknownIP; >>>>> if (input.size() != 2) { >>>>> throw new IOException("Expected input's size is 2, but is: " + >>>>> input.size()); >>>>> } >>>>> >>>>> Object o1 = input.get(0); * // This should be the IP you want >>> to >>>>> look up* >>>>> if (!(o1 instanceof Long)) { >>>>> throw new IOException("Expected input 1 to be Long, but >>> got " >>>>> + o1.getClass().getName()); >>>>> } >>>>> Object o2 = input.get(1); *// This is the Bag of IP segs* >>>>> if (!(o2 instanceof *DataBag*)) { //* Should I change it to >>> "(o2 >>>>> instanceof Tuple)"?* >>>>> throw new IOException("Expected input 2 to be DataBag, >> but >>>> got >>>>> " >>>>> + o2.getClass().getName()); >>>>> } >>>>> >>>>> ........... other codes ........... >>>>> } >>>>> >>>>> } >>>>> >>>>> >>>>> >>>>> 在 2011年12月14日 下午3:16，Prashant Kommireddi <[email protected]>写道： >>>>> >>>>> Seems like at the end of this you have a Single bag with all the >>>> elements, >>>>>> and somehow you would like to check whether an element exists in it >>>> based >>>>>> on ipstart/end. >>>>>> >>>>>> >>>>>> 1. Use FLATTEN >> http://pig.apache.org/docs/r0.9.1/basic.html#flatten- >>>>>> this will convert the Bag to Tuple: to_tuple = FOREACH >>> order_ip_segs >>>>>> GENERATE tag, FLATTEN(order_seq); ---- This is O(n) >>>>>> 2. Now write a UDF that can access the elements positionally for >> the >>>>>> BinarySearch >>>>>> 3. Dmitriy and Jonathan's ideas with DistributedCache could >> perform >>>>>> better than the above approach, so you could go down that route >> too. >>>>>> >>>>>> >>>>>> 2011/12/13 唐亮 <[email protected]> >>>>>> >>>>>>> The detailed PIG codes are as below: >>>>>>> >>>>>>> raw_ip_segment = load ... >>>>>>> ip_segs = foreach raw_ip_segment generate ipstart, ipend, name; >>>>>>> group_ip_segs = group ip_segs all; >>>>>>> >>>>>>> order_ip_segs = foreach group_ip_segs { >>>>>>> order_seg = order ip_segs by ipstart, ipend; >>>>>>> generate 't' as tag, order_seg; >>>>>>> } >>>>>>> describe order_ip_segs >>>>>>> order_ip_segs: {tag: chararray,order_seg: {ipstart: long,ipend: >>>>>> long,poid: >>>>>>> chararray}} >>>>>>> >>>>>>> Here, the order_ip_segs::order_seg is a BAG, >>>>>>> how can I transer it to a TUPLE? >>>>>>> >>>>>>> And can I access the TUPLE randomly in UDF? >>>>>>> >>>>>>> 在 2011年12月14日 下午2:41，唐亮 <[email protected]>写道： >>>>>>> >>>>>>>> Then how can I transfer all the items in Bag to a Tuple? >>>>>>>> >>>>>>>> >>>>>>>> 2011/12/14 Jonathan Coveney <[email protected]> >>>>>>>> >>>>>>>>> It's funny, but if you look wayyyy in the past, I actually >> asked >>> a >>>>>> bunch >>>>>>>>> of >>>>>>>>> questions that circled around, literally, this exact problem. >>>>>>>>> >>>>>>>>> Dmitriy and Prahsant are correct: the best way is to make a UDF >>>> that >>>>>> can >>>>>>>>> do >>>>>>>>> the lookup really efficiently. This is what the maxmind API >> does, >>>> for >>>>>>>>> example. >>>>>>>>> >>>>>>>>> 2011/12/13 Prashant Kommireddi <[email protected]> >>>>>>>>> >>>>>>>>>> I am lost when you say "If enumerate every IP, it will be >> more >>>> than >>>>>>>>>> 100000000 single IPs" >>>>>>>>>> >>>>>>>>>> If each bag is a collection of 30000 tuples it might not be >> too >>>>>> bad on >>>>>>>>> the >>>>>>>>>> memory if you used Tuple to store segments instead? >>>>>>>>>> >>>>>>>>>> (8 bytes long + 8 bytes long + 20 bytes for chararray ) = 36 >>>>>>>>>> Lets say we incur an additional overhead 4X times this, which >>> is >>>>>> ~160 >>>>>>>>> bytes >>>>>>>>>> per tuple. >>>>>>>>>> Total per Bag = 30000 X 160 = ~5 MB >>>>>>>>>> >>>>>>>>>> You could probably store the ipsegments as Tuple and test it >> on >>>>>> your >>>>>>>>>> servers. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Tue, Dec 13, 2011 at 8:39 PM, Dmitriy Ryaboy < >>>>>> [email protected]> >>>>>>>>>> wrote: >>>>>>>>>> >>>>>>>>>>> Do you have many such bags or just one? If one, and you >> want >>> to >>>>>> look >>>>>>>>> up >>>>>>>>>>> many ups in it, might be more efficient to serialize this >>>>>> relation >>>>>>> to >>>>>>>>>> hdfs, >>>>>>>>>>> and write a lookup udf that specifies the serialized data >> set >>>> as >>>>>> a >>>>>>>>> file >>>>>>>>>> to >>>>>>>>>>> put in distributed cache. At init time, load up the file >> into >>>>>>> memory, >>>>>>>>>> then >>>>>>>>>>> for every ip do the binary search in exec() >>>>>>>>>>> >>>>>>>>>>> On Dec 13, 2011, at 7:55 PM, 唐亮 <[email protected]> >> wrote: >>>>>>>>>>> >>>>>>>>>>>> Thank you all! >>>>>>>>>>>> >>>>>>>>>>>> The detail is: >>>>>>>>>>>> A bag contains many "IP Segments", whose schema is >>>>>> (ipStart:long, >>>>>>>>>>>> ipEnd:long, locName:chararray) and the number of tuples >> is >>>>>> about >>>>>>>>> 30000, >>>>>>>>>>>> and I want to check wheather an IP is belong to one >> segment >>>> in >>>>>> the >>>>>>>>> bag. >>>>>>>>>>>> >>>>>>>>>>>> I want to order the "IP Segments" by (ipStart, ipEnd) in >>> MR, >>>>>>>>>>>> and then binary search wheather an IP is in the bag in >> UDF. >>>>>>>>>>>> >>>>>>>>>>>> If enumerate every IP, it will be more than 100000000 >>> single >>>>>> IPs, >>>>>>>>>>>> I think it will also be time consuming by JOIN in PIG. >>>>>>>>>>>> >>>>>>>>>>>> Please help me how can I deal with it efficiently! >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> 2011/12/14 Thejas Nair <[email protected]> >>>>>>>>>>>> >>>>>>>>>>>>> My assumption is that 唐亮 is trying to do binary search >> on >>>> bags >>>>>>>>> within >>>>>>>>>>> the >>>>>>>>>>>>> tuples in a relation (ie schema of the relation has a >> bag >>>>>>> column). >>>>>>>>> I >>>>>>>>>>> don't >>>>>>>>>>>>> think he is trying to treat the entire relation as one >> bag >>>>>> and do >>>>>>>>>> binary >>>>>>>>>>>>> search on that. >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> -Thejas >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> On 12/13/11 2:30 PM, Andrew Wells wrote: >>>>>>>>>>>>> >>>>>>>>>>>>>> I don't think this could be done, >>>>>>>>>>>>>> >>>>>>>>>>>>>> pig is just a hadoop job, and the idea behind hadoop is >>> to >>>>>> read >>>>>>>>> all >>>>>>>>>> the >>>>>>>>>>>>>> data in a file. >>>>>>>>>>>>>> >>>>>>>>>>>>>> so by the time you put all the data into an array, you >>>> would >>>>>>> have >>>>>>>>>> been >>>>>>>>>>>>>> better off just checking each element for the one you >>> were >>>>>>> looking >>>>>>>>>> for. >>>>>>>>>>>>>> >>>>>>>>>>>>>> So what you would get is [n + lg (n)], which will just >> be >>>> [n] >>>>>>>>> after >>>>>>>>>>>>>> putting >>>>>>>>>>>>>> that into an array. >>>>>>>>>>>>>> Second, hadoop is all about large data analysis, >> usually >>>> more >>>>>>> than >>>>>>>>>>> 100GB, >>>>>>>>>>>>>> so putting this into memory is out of the question. >>>>>>>>>>>>>> Third, hadoop is efficient because it processes this >>> large >>>>>>> amount >>>>>>>>> of >>>>>>>>>>> data >>>>>>>>>>>>>> by splitting it up into multiple processes. To do an >>>>>> efficient >>>>>>>>> binary >>>>>>>>>>>>>> search, you would need do this in one mapper or one >>>> reducer. >>>>>>>>>>>>>> >>>>>>>>>>>>>> My opinion is just don't fight hadoop/pig. >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> On Tue, Dec 13, 2011 at 1:56 PM, Thejas Nair< >>>>>>>>> [email protected]> >>>>>>>>>>>>>> wrote: >>>>>>>>>>>>>> >>>>>>>>>>>>>> Bags can be very large might not fit into memory, and >> in >>>> such >>>>>>>>> cases >>>>>>>>>>> some >>>>>>>>>>>>>>> or all of the bag might have to be stored on disk. In >>> such >>>>>>>>> cases, it >>>>>>>>>>> is >>>>>>>>>>>>>>> not >>>>>>>>>>>>>>> efficient to do random access on the bag. That is why >>> the >>>>>>> DataBag >>>>>>>>>>>>>>> interface >>>>>>>>>>>>>>> does not support it. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> As Prashant suggested, storing it in a tuple would be >> a >>>> good >>>>>>>>>>> alternative, >>>>>>>>>>>>>>> if you want to have random access to do binary search. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> -Thejas >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> On 12/12/11 7:54 PM, 唐亮 wrote: >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Hi all, >>>>>>>>>>>>>>>> How can I implement a binary search in pig? >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> In one relation, there exists a bag whose items are >>>> sorted. >>>>>>>>>>>>>>>> And I want to check there exists a specific item in >> the >>>>>> bag. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> In UDF, I can't random access items in DataBag >>> container. >>>>>>>>>>>>>>>> So I have to transfer the items in DataBag to an >>>> ArrayList, >>>>>>> and >>>>>>>>>> this >>>>>>>>>>> is >>>>>>>>>>>>>>>> time consuming. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> How can I implement the binary search efficiently in >>> pig? >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> >>>>>> >>>>> >>>>> >>>> >>> >>
