<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
tt
{mso-style-priority:99;
font-family:"Courier New";}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body bgcolor=white lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>That's nice clean syntax, cant wait until I get my hands on XQuery 3 in the HE version of Saxon (hint hint).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>< Enter processor specific comments -- probably off-list ><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Performance wise I tested my code (XQuery 1) vs XSLT 2 code doing the same thing (using for-each-group) using Saxon 9.3 HE<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>This was using a 200MB XML file with about 17,000 ungrouped elements and 4,000 grouped elements.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>XSLT2 took about 6 seconds<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>XQuery took about 4 minutes.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>(Both took about 1 G of JVM).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>I'm hopeful XQuery 3.0 will optimize group-by so that I dont have to switch to xslt for these kinds of simple things.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><br><br><o:p></o:p></span></p><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D'>----------------------------------------</span><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>David A. Lee<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><a href="mailto:dlee@calldei.com">dlee@calldei.com</a><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><a href="http://www.xmlsh.org">http://www.xmlsh.org</a><o:p></o:p></span></p></div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext'> talk-bounces@x-query.com [mailto:talk-bounces@x-query.com] <b>On Behalf Of </b>Oliver Hallam<br><b>Sent:</b> Tuesday, March 01, 2011 7:23 PM<br><b>To:</b> talk@x-query.com<br><b>Subject:</b> Re: [xquery-talk] Optimal expression for gathering related elements<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>This really is the best way to do this in XQuery 1.0, and is a common pattern; this is why the "group by" clause was added to XQuery 3.0<br><br>In XQuery 3.0 this would be as simple as:<o:p></o:p></p><pre><o:p> </o:p></pre><pre><tt>for $drugs in /all/drug</tt><o:p></o:p></pre><pre><tt>let $id := $drugs/@id</tt><o:p></o:p></pre><pre><tt>group-by $id</tt><o:p></o:p></pre><pre><tt>return</tt><o:p></o:p></pre><pre><tt> <unique_drug id="{$id[1]}"></tt><o:p></o:p></pre><pre><tt> {</tt><o:p></o:p></pre><pre><tt> for $drug in $drugs</tt><o:p></o:p></pre><pre><tt> return</tt><o:p></o:p></pre><pre><tt> <drug>{$drug/*}</drug></tt><o:p></o:p></pre><pre><tt> }</tt><o:p></o:p></pre><pre><tt></unique_drug></tt><o:p></o:p></pre><pre><o:p> </o:p></pre><p class=MsoNormal style='margin-bottom:12.0pt'><br>Performance in XQuery 1.0 may not be as bad as you fear though. I can't <br>vouch for other processors, but this particular pattern is one that we <br>have put a great deal of effort in to spotting in XQSharp.<br><br><br>When I put your query through our processor I get the following query plan:<br><tt><span style='font-size:10.0pt'>let $:temp:41 :=</span></tt><br><tt><span style='font-size:10.0pt'> step</span></tt><br><tt><span style='font-size:10.0pt'> $fs:dot_0/child::all</span></tt><br><tt><span style='font-size:10.0pt'> child::drug</span></tt><br><tt><span style='font-size:10.0pt'>left outer hash join</span></tt><br><tt><span style='font-size:10.0pt'> for $id in</span></tt><br><tt><span style='font-size:10.0pt'> <a href="http://www.w3.org/2005/xpath-functions:distinct-values(">http://www.w3.org/2005/xpath-functions:distinct-values(</a></span></tt><br><tt><span style='font-size:10.0pt'> <a href="http://www.w3.org/2005/xpath-functions:data(">http://www.w3.org/2005/xpath-functions:data(</a></span></tt><br><tt><span style='font-size:10.0pt'> step</span></tt><br><tt><span style='font-size:10.0pt'> $:temp:41</span></tt><br><tt><span style='font-size:10.0pt'> attribute::id</span></tt><br><tt><span style='font-size:10.0pt'> )</span></tt><br><tt><span style='font-size:10.0pt'> ,</span></tt><br><tt><span style='font-size:10.0pt'> <a href="http://www.w3.org/2005/xpath-functions/collation/codepoint">"http://www.w3.org/2005/xpath-functions/collation/codepoint"</a></span></tt><br><tt><span style='font-size:10.0pt'> )</span></tt><br><tt><span style='font-size:10.0pt'>to</span></tt><br><tt><span style='font-size:10.0pt'> for $drug in $:temp:41</span></tt><br><tt><span style='font-size:10.0pt'>on</span></tt><br><tt><span style='font-size:10.0pt'>fs:convert-operand-to-atomic-type[<a href="http://www.w3.org/2001/XMLSchema:string">http://www.w3.org/2001/XMLSchema:string</a>]($id) = fs:convert-operand-to-atomic-type[<a href="http://www.w3.org/2001/XMLSchema:string">http://www.w3.org/2001/XMLSchema:string</a>](cardinality-check[?] </span></tt><br><tt><span style='font-size:10.0pt'>{ <a href="http://www.w3.org/2005/xpath-functions:data($drug/attribute::id)">http://www.w3.org/2005/xpath-functions:data($drug/attribute::id)</a> })</span></tt><br><tt><span style='font-size:10.0pt'>aggregate</span></tt><br><tt><span style='font-size:10.0pt'> element {drug} { </span></tt><br><tt><span style='font-size:10.0pt'>fs:item-sequence-to-node-sequence($drug/child::element()) }</span></tt><br><tt><span style='font-size:10.0pt'>as</span></tt><br><tt><span style='font-size:10.0pt'> $:temp:42</span></tt><br><tt><span style='font-size:10.0pt'>return</span></tt><br><tt><span style='font-size:10.0pt'> element {unique_drug} { (attribute {id} { $id cast as </span></tt><br><tt><span style='font-size:10.0pt'><a href="http://www.w3.org/2001/XMLSchema:untypedAtomic*">http://www.w3.org/2001/XMLSchema:untypedAtomic*</a> } , </span></tt><br><tt><span style='font-size:10.0pt'>fs:item-sequence-to-node-sequence($:temp:42)) }</span></tt><br><br><br><br>The key thing to note here is the "left outer hash join". This should <br>perform in linear time. What is in fact happening here is that an index <br>is first built for the right hand input to the join (in this case the <br>values of @id for each /all/drug node), and then for each distinct value <br>of /all/drug/@id all matching nodes are selected and the <unique_drug> <br>element is returned.<br><br>XQSharp should be smart enough to spot that the join is joining the keys <br>on the right hand side to their own distinct values. The query plan <br>should have looked something like this:<br><br><tt><span style='font-size:10.0pt'> for $drug in /all/drug</span></tt><span style='font-size:10.0pt;font-family:"Courier New"'><br><tt>group by</tt><br><tt> data($drug/@id)</tt><br><tt>aggregate</tt><br><tt> <drug>{$drug/*}</drug></tt><br><tt>as</tt><br><tt> $:temp</tt><br><tt>return</tt><br><tt> <unique_drug id="{$id}">{$:temp}</unique_drug></tt></span><br><br>If this optimization had kicked in correctly then the whole query would <br>have been performed in a single pass of the document. In this case an <br>index is built for the /all/drug elements (keyed on data(@id)) and then <br>the index is iterated. Performance should be about as fast as it <br>possibly could be!<br><br>It seems though that this optimization hasn't happened with the lates <br>build of XQSharp; I have filed a bug report and will investigate why <br>this is the case with your query.<br><br>Even without this final optimization though the query does perform in <br>linear time; it just builds two indexes of the data rather than one (one <br>during the computation of the distinct values, and one to perform the join).<br><br>If you are interested, I have written a more detailed analysis of the <br>different join optimizations performed by XQSharp here: <br><a href="http://xqsharp.blogspot.com/2010/05/join-optimizations-in-xqsharp.html">http://xqsharp.blogspot.com/2010/05/join-optimizations-in-xqsharp.html</a><br><br><br><br>Oliver Hallam<br>XQSharp<br><br>On 01/03/2011 15:33, David Lee wrote:<br>> I find I use this pattern frequently when I need to group multiple elements<br>> associated with some shared identifier (say @id)<br>> Suppose I have something like<br>><br>> <all><br>> <drug @id="1"><text>texta</text></drug><br>> <drug @id="2"> <text>textb</text></drug><br>> <drug @id="3"> <text>textc</text></drug><br>> <drug @id="1"> <text>textd</text></drug><br>> <drug @id="2"> <text>texte</text></drug><br>> ...<br>><br>><br>> And I want to create a set of combined entries<br>> like<br>> <all><br>> <unique_drug @id="1"><br>> <drug><text>texta</text></drug><br>> <drug> <text>textd</text></drug><br>> </unique_drug><br>> <unique_drug @id="2"><br>> <drug><text>textb</text></drug><br>> <drug> <text>texte</text></drug><br>> </unique_drug><br>><br>> ..<br>><br>><br>> What I do is something like this :<br>> ( typed into email, not tested ...)<br>><br>> for $id in distinct-values(/all/drug/@id)<br>> return<br>> <unique_drug id="{$id}"><br>> {<br>> for $drug in /all/drug[@id eq $id]<br>> return<br>> <drug>{$drug/*}</drug><br>> }<br>> </unique_drug><br>><br>><br>> What I was offhand wondering, is if there isnt something more direct (in<br>> XQuery 1).<br>> It seems both verbose and inefficient, although of course efficiency is a<br>> processor issue. (maybe it makes indexes ...)<br>> But still ... it seems it has to scan all elements to get the unique id's<br>> then re-scan them N times to get the matching elements,<br>> when I can imagine a syntax which would do both at once in linear time as<br>> opposed to (presumably) exponential time.<br>> It seems like something a declarative expression should be able to state<br>> succinctly.<br>><br>> Any suggestions ? Or am I just fantasizing<br>><br>> -David<br>><br>><br>><br>><br>> <br>><br>><br>> ----------------------------------------<br>> David A. Lee<br>> <a href="mailto:dlee@calldei.com">dlee@calldei.com</a><br>> <a href="http://www.xmlsh.org">http://www.xmlsh.org</a><br>><br>><br>> _______________________________________________<br>> <a href="mailto:talk@x-query.com">talk@x-query.com</a><br>> <a href="http://x-query.com/mailman/listinfo/talk">http://x-query.com/mailman/listinfo/talk</a><o:p></o:p></p></div></body></html>