Performance of Basex 7.0 XQuery execution
Wednesday, 19 October 2011 · 6 messages · last reply 21 Oct 2011
CH
Constantine Hondros19 Oct 2011 16:15 #
Hi there,
I am running relatively simply XQuery over a Basex database read in from about 100 MB of XML.
While performance in general is fantastic, with most queries completing in a few seconds, I am getting worryingly slow performace on certain queries using XPath axes such as preceding-sibling.
For example, the following simple (if a bit silly) query takes over 30 minutes to execute:
/tns:pois/tns:poi[not(preceding-sibling::tns:poi)]
For what it's worth, there are only about 100,000 instances of the <tns:poi> element.
So the immediate question is whether this performance is to be expected. If not, what are the obvious things to look at in terms of performance tuning?
Thanks in advance,
Constantine
Constantine Hondros | Senior Data Engineer | TomTom Places | constantine.hondros at tomtom.com<mailto:constantine.hondros at tomtom.com> | +31 (0) 88 245 6239 office | +31 (0) 6 402 14838 mobile | places.tomtom.com<http://places.tomtom.com/>
CG
Christian Grün19 Oct 2011 20:56 #
Constantine,
thanks for the kudos.
Quoted text · Constantine Hondros · 1 line
> /tns:pois/tns:poi[not(preceding-sibling::tns:poi)]
If I get it right, you're trying to select the first <tns:poi/> element in your query. This can also be done via
/tns:pois/tns:poi[1]
After all, I still might have a deeper look at the performance of your query, as 30 minutes would of course be terribly slow.
Hope this helps, feel free to ask for more,
Christian
BaseX Team
Quoted text · Constantine Hondros · 17 lines
> So the immediate question is whether this performance is to be expected. If > not, what are the obvious things to look at in terms of performance tuning? > > Thanks in advance, > Constantine > > > Constantine Hondros | Senior Data Engineer | TomTom Places | > constantine.hondros at tomtom.com | +31 (0) 88 245 6239 office | +31 (0) 6 402 > 14838 mobile | places.tomtom.com > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk > >
CH
Constantine Hondros20 Oct 2011 09:44 #
Hi Christian,
The XPath I showed was just a simple example of using the preceding-sibling axis. Of course, I am really interested in more useful queries such as:
//tns:poi[not(tns:id = preceding-sibling::tns:poi/tns:id)]
I guess what I am asking is ... while most XPath queries I run are quick to resolve, anything using preceding::, preceding-sibling:: or following::, following-sibling:: essentially runs too slowly to be workable - at least, on my sample dataset with about 100K sibling children of the root element.
So is this any sort of known issue? Should I be looking at any sort of configuration options? Is there any way to profile the execution of the Xpath?
Cheers,
C.
Quoted text · Christian Grün · 33 lines
-----Original Message----- From: Christian Grün [mailto:christian.gruen at gmail.com] Sent: Wednesday, October 19, 2011 8:56 PM To: Constantine Hondros Cc: basex-talk at mailman.uni-konstanz.de Subject: Re: [basex-talk] Performance of Basex 7.0 XQuery execution Constantine, thanks for the kudos. > /tns:pois/tns:poi[not(preceding-sibling::tns:poi)] If I get it right, you're trying to select the first <tns:poi/> element in your query. This can also be done via /tns:pois/tns:poi[1] After all, I still might have a deeper look at the performance of your query, as 30 minutes would of course be terribly slow. Hope this helps, feel free to ask for more, Christian BaseX Team > So the immediate question is whether this performance is to be > expected. If not, what are the obvious things to look at in terms of performance tuning? > > Thanks in advance, > Constantine > > > Constantine Hondros | Senior Data Engineer | TomTom Places | > constantine.hondros at tomtom.com | +31 (0) 88 245 6239 office | +31 (0) > 6 402 > 14838 mobile | places.tomtom.com > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk > >
CG
Christian Grün20 Oct 2011 15:43 #
Hi Constantine,
Quoted text · Constantine Hondros · 1 line
> The XPath I showed was just a simple example of using the preceding-sibling axis.
I guessed so already.. Thanks for persisting ;)
Quoted text · Constantine Hondros · 3 lines
> I guess what I am asking is ... while most XPath queries I run are quick to resolve, anything using preceding::, preceding-sibling:: or following::, following-sibling:: essentially runs too slowly to be workable - at least, on my sample dataset with about 100K sibling children of the root element. > > So is this any sort of known issue? Should I be looking at any sort of configuration options? Is there any way to profile the execution of the Xpath?
It's true that BaseX is mostly optimized for descendant and ancestor operations. In particular, the preceding/preceding-sibling axes will always be slower, as our storage does not contain backward pointers to preceding nodes. I'm pretty sure, though, that there are ways to either optimize relevant queries or the internal optimizer strategies, but we'll probably have to spend some more time on analyzing the relevant bottlenecks..
Feel free to ask for more,
Christian
JC
Jan Vlčinský (CAD)20 Oct 2011 19:20 #
Hi Constantine
Just my side note.
As far as I remember, I found this sort of performance discussion with most the XQuery processors I have tested (Sedna, Zorba, Saxon, eXist...). Each time related to sibling, preceding etc. and each time explaining, that indices are not containing pointers for tracking this relationship. My feeling is, this could lead to much bigger index file and slower performance when adding documents and indexing.
My conlcusion is - optimizing this sort of queries has its cost and mostly it is better (and somehow possible) to avoid these constructions.
With best regards
Jan
*Ing. Jan Vlčinský*
CAD programy
Slunečnicová 338/3, 734 01 Karviná Ráj, Czech Republic
tel: +420-597 602 024; mob: +420-608 979 040
skype: janvlcinsky; GoogleTalk: jan.vlcinsky at gmail.com
http://cz.linkedin.com/in/vlcinsky
Quoted text · Christian Grün · 32 lines
On 20 October 2011 15:43, Christian Grün <christian.gruen at gmail.com> wrote: > Hi Constantine, > > > The XPath I showed was just a simple example of using the > preceding-sibling axis. > > I guessed so already.. Thanks for persisting ;) > > > I guess what I am asking is ... while most XPath queries I run are quick > to resolve, anything using preceding::, preceding-sibling:: or following::, > following-sibling:: essentially runs too slowly to be workable - at least, > on my sample dataset with about 100K sibling children of the root element. > > > > So is this any sort of known issue? Should I be looking at any sort of > configuration options? Is there any way to profile the execution of the > Xpath? > > It's true that BaseX is mostly optimized for descendant and ancestor > operations. In particular, the preceding/preceding-sibling axes will > always be slower, as our storage does not contain backward pointers to > preceding nodes. I'm pretty sure, though, that there are ways to > either optimize relevant queries or the internal optimizer strategies, > but we'll probably have to spend some more time on analyzing the > relevant bottlenecks.. > > Feel free to ask for more, > Christian > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >
LW
Dear Constantine,
Quoted text · Constantine Hondros · 4 lines
Am 20.10.2011 09:44, schrieb Constantine Hondros: > Of course, I am really interested in more useful queries such as: > > //tns:poi[not(tns:id = preceding-sibling::tns:poi/tns:id)]
this query basically compiles to two nested loops, the outer one iterating over //tns:poi and the inner one over all preceding-siblings. So it has an O(n^2) runtime.
Quoted text · Constantine Hondros · 1 line
> I guess what I am asking is ... while most XPath queries I run are quick to resolve, anything using preceding::, preceding-sibling:: or following::, following-sibling:: essentially runs too slowly to be workable - at least, on my sample dataset with about 100K sibling children of the root element.
Well, that's an extreme example, 100'000^2 is a huge number of nodes to traverse. I performed some tests with
a) 10'000 sibling elements inside the root:
<root>
<item id="1"/>
<item id="2"/>
[...]
<item id="10000"/>
</root>
and the query //item[not(preceding-sibling::*)]
b) 10'000 nested elements:
<root>
<item id="1">
<item id="2">
[...]
<item id="10000"/>
[...]
</item>
</item>
</root> and the query //item[not(ancestor::*)]
The timings I get are almost identical, replacing "preceding" with "following" or "ancestor" with "descendant" doesn't change much.
Quoted text · Constantine Hondros · 1 line
> So is this any sort of known issue? Should I be looking at any sort of configuration options? Is there any way to profile the execution of the Xpath?
My guess is that the number of nodes on the *-sibling-axes is usually much bigger than on the vertical axes, so an expensive algorithm gets unusable earlier.
To return to your example query, you could drastically reduce its runtime by only traversing the database once, comparing each node only to the nodes with unique tns:ids found before. I'll use a left fold [1][2]:
fold-left(
function($seq, $x) {
if($seq/tns:id = $x/tns:id) then $seq
else ($seq, $x)
},
(),
//tns:poi
)If you're OK with using not-yet-standard XQuery extensions, a map [3] instead of a sequence can potentially be even faster:
let $map :=
fold-left(
function($map, $x) {
let $key := $x/tns:id
return if(map:contains($map, $key)) then $map
else map:new(($map, map:entry($key, $x)))
},
map:new(),
//tns:poi
)
for $key in map:keys($map)
return $map($key)But this won't preserve the relative ordering of the results.
Hope that helped,
Cheers Leo
__________
[1] http://www.w3.org/TR/xpath-functions-30/#func-fold-left
[2] http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29 [3] http://docs.basex.org/wiki/Map_Functions
Written for BaseX 6.7, 7.0. BaseX may have changed since: please check the current documentation.
⚡Generated with XQuery