> I have a question about the xsl:key implementation.
> I have tested the performance of combining two XML documents
> with/without xsl:key using saxon. That is for the purpose to
> know when we should use xsl:key or not.
> I define the xsl:key on an element whose key is unique.
> I varies the entry size (the number of key element) from 10k
> to 60k.
> As expected, without xsl:key, the result shows that the performance
> is linear to the entry size.
> With xsl:key, although the performance is better than without
> xsl:key, it is exponential to the entry size.
I very much hope that you don't really mean it is exponential, that is,
that the elapsed time is proportional to c**n, where n is the number of
elements, and c is a constant. This would be really bad news. I suspect
you mean rather than the performance is non-linear. I would be
interested how it actually varies. One would expect the time taken to
build the index to be proportional to (n log n), and the time taken to
retrieve from it to be proportional to (log n).
> I increase the entry size, the performance without xsl:key
> would become better than that with xsl:key.
> I suspect that there is a certain maximum size of the hash
> table size. Is that right? or are there any other reasons?
The question is, how many retrievals from the index are you doing? We
need to see what you are actually measuring.
What people sometimes fail to realise is that if you only use the index
once, then the cost of building the index is far greater than the cost
of scanning the document to find the value you are looking for. It's
only worth building an index if it is used sufficiently often to
amortize the cost of building it.