RE: Performance degraded with grouping and sorting.

I hit a similar problem with scalability of Muenchian grouping recently. In
my case (my client's case, I should say) the number of grouping categories
remained fairly stable as the size of the data increased, and therefore the
number of items in each group increased almost linearly with the data size.
The overall result was that Muenchian grouping was exhibiting essentially
quadratic performance, with the key becoming less and less selective as the
data size increased. For that particular problem, switching to XSLT 2.0
for-each-group gave a dramatic improvement - a factor of about 100 for a
data file of 50Mb.

The other way of tackling this, if you can't move to 2.0, might be to do a
sort on the data first, and then do the grouping by means of a comparison
with the immediately preceding sibling.

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

> -----Original Message-----
> From: Geert Josten [mailto:Geert.Josten@xxxxxxxxxxx] 
> Sent: 30 October 2004 11:17
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: Re:  Performance degraded with grouping and sorting.
> 
> Oh wait, why not predict the performance myself..
> 
> In the original code the grouping algorithm starts with 
> picking the first of each ACCT_NBR:
> 
>    <xsl:for-each select="PROJECTION[count(. | 
> key('group-by-accountnbr', ACCT_NBR)[1]) = 1]">
> 
> Well, that is a *very* expensive operation. The index is 
> accessed for _each_ PROJECTION elements, so
> about 2000 times! And if each distinct ACCT_NBR 'contains' 
> about 10 PROJECTIONs, 9 out of 10 times
> the predicate gives the same result. Very inefficient... :-(
> 
> Unfortunatily, I can't think of any other way of determining 
> the first of a group other than
> variations on this theme or performing sorting in a previous 
> step and using the index on first items
> I suggested.
> 
> Anyone good ideas?
> 
> Grtz,
> Geert