Performance Issue of a Join in Xquery

Question

I have a strange performance issue while performing joins at multiple levels, say I have a huge xml out of which I need to perform joins(on the records inside that huge xml, approx few thousands) and define 4 hierarchy levels (Parent/Child relatioships). However, joins at three levels(one join at each level) work fine but join at 4th level takes couple of hours to complete. Any inputs and guidance is much appreciated. Thanks. Eg: Source XML

<items>
<item>
<level>1</level>
<parentref></parentref>
<parentitem></parentitem>
<itemno>123</itemno>
<itemname>Laptop</itemname>
</item>
<item>
<level>2</level>
<parentref>1</parentref>
<parentitem>123</parentitem>
<itemno>111</itemno>
<itemname>Keyboard</itemname>
</item>
<item>
<level>2</level>
<parentref>1</parentref>
<parentitem>123</parentitem>
<itemno>112</itemno>
<itemname>Mouse</itemname>
</item>
<item>
<level>3</level>
<parentref>2</parentref>
<parentitem>112</parentitem>
<itemno>112-1</itemno>
<itemname>Fiber Mouse</itemname>
</item>
<item>
<level>4</level>
<parentref>3</parentref>
<parentitem>112-1</parentitem>
<itemno>112-2</itemno>
<itemname>Mouse Pad and USB</itemname>
</item>
</items>

Expected Output:

<items>
<item>
<itemno>123</itemno>
<itemname>Laptop</itemname> -- Level 1 ( Top level always be one record)
<accessories>               ------------------------------- 
    <itemno>111</itemno>
    <itemname>Keyboard</itemname>  -- Both accessories belong to Level 2 ( can be any number of records)
</accessories>                        one of the accessories has two levels ( can be any number of records) 
<accessories>
    <itemno>112</itemno>
    <itemname>Mouse</itemname>
    <addons>
        <itemno>112-1</itemno>
        <itemname>Fiber Mouse</itemname>
        <moreaddons>                             --- Performance issue is at this level of join
            <itemno>112-2</itemno>                    For 500 addons records, I have almost 5000 moreaddons to match in my source xml.
            <itemname>Mouse Pad and USB</itemname>
        </moreaddons>
    </addons>
</accessories>          
</item>

Sample Join Code that I have used below:

Level 1: To get the base item

for $x in input xml
where $x/level=1

Level 2: To get the accosories for a given base item

for $y in $x
for $i in input xml
where $i/level=2
and $y/itemno = $i/parentitem 

Level 3: To get the addons for a given accesories

let $p := (for $bv in $i return $bv)
let $lst := (for $id in input xml
             where $ids/level=3 return $id)
return for-each($p,function($p){
if(for-each($lst,function($lst){$p/itemno=$lst/parentitem})=true()
then for $av in input xml
     where $av/level = 3
     and $av/parentitem=$p/itemno

 

Level 4: To get the moreaddons for a given addons

let $q := (for $cv in $av return $cv)
let $lsts := (for $ids in input xml
             where $ids/level=4 return $ids)
return for-each($q,function($q){
if(for-each($lsts,function($lsts){$q/itemno=$lsts/parentitem})=true()
then for $dv in input xml
     where $dv/level = 4
     and $dv/parentitem=$q/itemno

Answer 1

A straight-forward nested for..return approach would look like

<items>
{
    for $level1-item in /items/item[level = 1]
    return
        <item>
        {
            $level1-item!(itemno, itemname),
            for $level2-item in /items/item[level = 2 and parentitem = $level1-item/itemno]
            return
                <accessories>
                {
                    $level2-item!(itemno, itemname),
                    for $level3-item in /items/item[level = 3 and parentitem = $level2-item/itemno]
                    return
                        <addons>
                        {
                            $level3-item!(itemno, itemname),
                            for $level4-item in /items/item[level = 4 and parentitem = $level3-item/itemno]
                            return
                                <moreaddons>
                                {
                                    $level4-item!(itemno, itemname)
                                }
                                </moreaddons>
                        }
                        </addons>
                }
                </accessories>
        }
        </item>
}
</items>

In the end the nesting asks for a function taking a level:

declare variable $names as xs:string* external := ('item', 'acessories', 'addons', 'moreaddons');

declare function local:nest($root as document-node()) as element()*
{
    let $level := 1
    for $item in $root/items/item[level = $level]
    return 
        element { $names[$level] } {
           $item/itemno,
           $item/itemname,
           local:nest($root, $item, $level + 1)
        }
};

declare function local:nest($root as document-node(), $parent as element(item), $level as xs:integer) as element()*
{
    for $item in $root/items/item[level = $level and parentitem = $parent/itemno]
    return
        element { $names[$level] } {
           $item/itemno,
           $item/itemname,
           local:nest($root, $item, $level + 1)
        }
};

<items>
{
    local:nest(/)

}
</items>