Count of Distinct elements performance problem

[Michael Kay]

Did you tell us what product you are using?
 
As I mentioned, the recursive code depends heavily on optimization in the
processor - as indeed does everything, with the kind of data volumes you are
dealing with.
 
Michael Kay
http://www.saxonica.com/


  _____  

From: http://xquery.com/mailman/listinfo/talk [mailto:http://xquery.com/mailman/listinfo/talk] On Behalf Of
Kusunam, Srinivas
Sent: 23 August 2006 19:47
To: http://xquery.com/mailman/listinfo/talk
Subject: RE:  Count of Distinct elements performance problem


Mike,
 
          Thanks for the code for grouping. I have fixed this Xquery and now
i am getting "java.lang.StackOverflowError" with this approach even on half
file (with 222500 Model Years). Is there anything wrong with this XQuery or
222500 is too much for it?
 
Here is the XQuery:
 
declare function local:groups($seq as xs:string*, $s as xs:string, $count as
xs:integer) {
   if (empty($seq))
   then <gp value="{$s}" count="{$count}"/>
   else
     if ($seq[1] eq $s)
     then local:groups($seq[position() > 1], $s, $count+1)
     else 
 (<gp value="{$s}" count="{$count}"/>, local:groups($seq[position() > 1],
$seq[1], 1)) 
 };
 
let $mdoc := doc('sampleXML.xml')/Body
let $sourModelYear := $mdoc/Title/Group/ModelYear
return
<Elements>
    <Element name="ModelYear"> 
        <frequencyDistribution>
        {
          let $sortedYears :=  
                         for $dvalue in $sourModelYear
                       order by $dvalue
                       return string($dvalue)
         return   
             local:groups($sortedYears[position()>1], $sortedYears[1], 1)
        }
        </frequencyDistribution>
    </Element>      
 </Elements>
 

  _____  

From: Michael Kay [mailto:http://xquery.com/mailman/listinfo/talk]
Sent: Tue 8/22/2006 4:14 PM
To: Kusunam, Srinivas; http://xquery.com/mailman/listinfo/talk
Subject: RE:  Count of Distinct elements performance problem



Something like this:

let $sortedYears :=
  for $dvalue in $sourModelYear
  order by $dvalue
  return string($dvalue)

(: use string() rather than /text() - strings are simpler and likely to be
smaller, and /text() is fragile in the face of comments :)

return
  f:groups($sortedYears[position()>1], $sortedYears[1], 1);


declare function f:groups($seq as xs:string()*, $s as xs:string, $count as
xs:integer)
as xs:integer {
  if (empty($seq))
  then ()
  else
    if ($seq[1] eq $s)
    then f:count-group($seq[position() > 1], $s, $count+1)
    else (<gp value="{$s}" count="{$count}"/>,
        f:count-group($seq[position() > 1], $s, 1))
}

Not tested.

This is likely to perform well if there are a small number of large groups,
less well if there's a large number of small groups - but it depends on how
good the implementation is at recursion.

Michael Kay
http://www.saxonica.com/

> -----Original Message-----
> From: Kusunam, Srinivas [mailto:http://xquery.com/mailman/listinfo/talk]
> Sent: 22 August 2006 20:44
> To: Michael Kay; http://xquery.com/mailman/listinfo/talk
> Subject: RE:  Count of Distinct elements
> performance problem
>
> Michael,
>          Thanks a lot for your reply.
>
>          I understand what you are suggesting and it is a
> good idea. But I am not clear about doing positional
> grouping. Here is how I am assuming my modified XQuery would like:
>
> let $mdoc := doc('input.xml')/Body
> let $sourModelYEAR := $mdoc/Title/ModelYear return <Elements>
>    <Element name="ModelYear">
>         <Distribution>
>         {
>           for $dvalue in $sourModelYEAR/text()    ------ Extract
>           order by $dvalue                        ------ Sort
>           ............
>               How do we do Grouping of $dvalue i.e.
> ModelYear's (1991, 1992, 1995, 1997 etc)????????
>           .............      
>           return 
>               <distribution>
>                 <value>{ $dvalue }</value>
>                 <count>{ $eachcount }</count>
>               </distribution>
>         }
>         </Distribution>
>     </Element>     
>  </Elements>
>
> Thanks,
> Srinivas
>
> -----Original Message-----
> From: Michael Kay [mailto:http://xquery.com/mailman/listinfo/talk]
> Sent: Tuesday, August 22, 2006 2:20 PM
> To: Kusunam, Srinivas; http://xquery.com/mailman/listinfo/talk
> Subject: RE:  Count of Distinct elements
> performance problem
>
> A performance question like this can only be answered with
> respect to a specific product.
>
> There aren't many XQuery engines that will handle an 8Gb
> file, so you're doing quite well.
>
> You might find that a multi-pass approach works faster:
>
> (a) extract the values
>
> (b) sort them
>
> (c) use a recursive scan to do positional grouping - depends
> on your product supporting tail call optimization
>
>
> That's likely to have O(n*log(n)) performance rather than O(n^2).
>
> Michael Kay
> http://www.saxonica.com/
>
>
>
> > -----Original Message-----
> > From: http://xquery.com/mailman/listinfo/talk
> > [mailto:http://xquery.com/mailman/listinfo/talk] On Behalf Of Kusunam, Srinivas
> > Sent: 22 August 2006 18:36
> > To: http://xquery.com/mailman/listinfo/talk
> > Subject:  Count of Distinct elements
> performance problem
> >
> > I am trying to find count of distinct elements (Model Year).
> > Here is my XQuery. It takes 4 hrs to get the count from 8GB file.
> > There are around 3000 distinct Model years in this file.
> >
> > let $mdoc := doc('input.xml')/Body
> > let $sourModelYEAR := $mdoc/Title/ModelYear return <Elements>
> >     <Element name="ModelYear">
> >         <Distribution>
> >         {
> >           for $dvalue in fn:distinct-values($sourModelYEAR)
> >           let $eachcount := count($mdoc/Title[ModelYear=$dvalue])
> >           return 
> >               <distribution>
> >                 <value>{ $dvalue }</value>
> >                 <count>{ $eachcount }</count>
> >               </distribution>
> >         }
> >         </Distribution>
> >     </Element>     
> >  </Elements>
> >
> > This Query seems to loop through the document for each value i.e.
> > overall 3000 times. I know this should be easily achievable
> if we have
> > Group-by in XQuery. Do any XQuery engine supports
> > (custom) Group-By now?
> > Or is there any other way to make this query efficient?
> >
> > Where as if I add one more element to find the pattern of
> the data it
> > finishes the job within 40 minutes? Why is this odd behavior?
> >
> > let $mdoc := doc('input.xml')/Body
> > let $sourModelYEAR := $mdoc/Title/ModelYear return <Elements>
> >     <Element name="ModelYear">
> >         <Distribution>
> >         {
> >           for $dvalue in fn:distinct-values($sourModelYEAR)
> >           let $eachcount := count($mdoc/Title[ModelYear=$dvalue])
> >           return 
> >               <distribution>
> >                 <value>{ $dvalue }</value>
> >                 <count>{ $eachcount }</count>
> >               </distribution>
> >         }
> >         </Distribution>
> >         <PatternDistribution>
> >         {
> >             for $phonenum in
> > distinct-values($sourModelYEAR/translate(.,
> > '0123456789','9999999999'))
> >             return
> >                 <pattern>
> >                     <type>{ $phonenum }</type>
> >                     <count>{count($sourModelYEAR[translate(.,
> > '0123456789', '9999999999') eq $phonenum])}</count>
> >                 </pattern>
> >         }
> >         </PatternDistribution>
> >     </Element>     
> > </Elements>
> >
> >
> > Thanks,
> > Srini
> > *****************************************************************
> > This message has originated from RLPTechnologies,
> > 26955 Northwestern Highway, Southfield, MI 48033.
> >
> > RLPTechnologies sends various types of email communications. 
> > If this email message concerns the potential licensing of an RLPT
> > product or service, and you do not wish to receive further emails
> > regarding Polk products, forward this email to http://xquery.com/mailman/listinfo/talk
> > with the word "remove" in the subject line.
> >
> > The email and any files transmitted with it are confidential and
> > intended solely for the individual or entity to whom they are
> > addressed.
> >
> > If you have received this email in error, please delete
> this message
> > and notify the Polk System Administrator at http://xquery.com/mailman/listinfo/talk
> > *****************************************************************
> >
> >
> > _______________________________________________
> > http://xquery.com/mailman/listinfo/talk
> > http://xquery.com/mailman/listinfo/talk
>
> *****************************************************************
> This message has originated from RLPTechnologies,
> 26955 Northwestern Highway, Southfield, MI 48033.
>
> RLPTechnologies sends various types of email
> communications.  If this email message concerns the
> potential licensing of an RLPT product or service, and
> you do not wish to receive further emails regarding Polk
> products, forward this email to http://xquery.com/mailman/listinfo/talk
> with the word "remove" in the subject line.
>
> The email and any files transmitted with it are confidential
> and intended solely for the individual or entity to whom they
> are addressed.
>
> If you have received this email in error, please delete this
> message and notify the Polk System Administrator at
> http://xquery.com/mailman/listinfo/talk
> *****************************************************************
>
>



*****************************************************************

This message has originated from RLPTechnologies,

26955 Northwestern Highway, Southfield, MI 48033.



RLPTechnologies sends various types of email

communications.  If this email message concerns the

potential licensing of an RLPT product or service, and

you do not wish to receive further emails regarding Polk

products, forward this email to http://xquery.com/mailman/listinfo/talk

with the word "remove" in the subject line.



The email and any files transmitted with it are confidential

and intended solely for the individual or entity to whom they

are addressed.



If you have received this email in error, please delete this

message and notify the Polk System Administrator at

http://xquery.com/mailman/listinfo/talk

*****************************************************************



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://x-query.com/pipermail/talk/attachments/20060823/3a1496d9/attachment-0001.htm