[xquery-talk] outer join between 2 sequences

[Ihe Onwuka]

I have sequence A consisting of the numbers 0 to 4000000 and sequnce B
consisting of about 100k random I numbers within the range of sequence A
and I want the outer join where sequence B is "null".

Should one expect bad performance in sequence B is not sorted and can one
expect reasonable performance if it is?

I am guessing that performance will vary by implemetation.

[Adam Retter]

Post by Ihe Onwuka
I have sequence A consisting of the numbers 0 to 4000000 and sequnce B
consisting of about 100k random I numbers within the range of sequence A and
I want the outer join where sequence B is "null".

There is no 'null' in XQuery, so I am not quite sure what you mean
here. If you ware looking for all values that appear in sequence A and
sequence B, then you can do the following -

$a[. = $b]

Post by Ihe Onwuka
Should one expect bad performance in sequence B is not sorted and can one
expect reasonable performance if it is?

I think that question is very implementation specific. If all of your
data is in RAM, as your dataset is relatively small and these are just
numbers, I would expect performance to be excellent. I am not sure
that sorting will make much of a difference, but it depends on the
implementation and how it initiates the search for a false comparison
in a large sequence.

Post by Ihe Onwuka
I am guessing that performance will vary by implemetation.

Of course!

Post by Ihe Onwuka
_______________________________________________
http://x-query.com/mailman/listinfo/talk

[Ihe Onwuka]

Post by Adam Retter

Post by Ihe Onwuka
I have sequence A consisting of the numbers 0 to 4000000 and sequnce B
consisting of about 100k random I numbers within the range of sequence A

and

Post by Ihe Onwuka
I want the outer join where sequence B is "null".

There is no 'null' in XQuery, so I am not quite sure what you mean
here. If you ware looking for all values that appear in sequence A and
sequence B, then you can do the following -
$a[. = $b]

I meant null in the SQL sense of outer join - sorry.

I want to drop the things that are in B from A where both B and A are just
sequences of integers. In other words, don't fetch what I've already got.

Post by Adam Retter

Post by Ihe Onwuka
Should one expect bad performance in sequence B is not sorted and can one
expect reasonable performance if it is?

I think that question is very implementation specific. If all of your
data is in RAM, as your dataset is relatively small and these are just
numbers, I would expect performance to be excellent.

I am not sure

Post by Adam Retter
that sorting will make much of a difference, but it depends on the
implementation and how it initiates the search for a false comparison
in a large sequence.

that's good - the nightmare scenario is a O^n2 algorithm if B is not sorted

[Ihe Onwuka]

PPS

Post by Adam Retter

Post by Ihe Onwuka
I have sequence A consisting of the numbers 0 to 4000000 and sequnce B
consisting of about 100k random I numbers within the range of sequence

A and

Post by Ihe Onwuka
I want the outer join where sequence B is "null".

There is no 'null' in XQuery, so I am not quite sure what you mean
here. If you ware looking for all values that appear in sequence A and
sequence B, then you can do the following -
$a[. = $b]

Of course that would be $a[not(. = $b)] maybe even $a except $b, I was
asking more on what the performance expectation would be.

Pleased that it reasonable to expect it to be fast.

[Ihe Onwuka]

Post by Ihe Onwuka

Post by Adam Retter

Post by Ihe Onwuka
I have sequence A consisting of the numbers 0 to 4000000 and sequnce B
consisting of about 100k random I numbers within the range of sequence

A and

Post by Ihe Onwuka
I want the outer join where sequence B is "null".

There is no 'null' in XQuery, so I am not quite sure what you mean
here. If you ware looking for all values that appear in sequence A and
sequence B, then you can do the following -
$a[. = $b]

I meant null in the SQL sense of outer join - sorry.
I want to drop the things that are in B from A where both B and A are just
sequences of integers. In other words, don't fetch what I've already got.

Pah... incorrect snippage in the last post.


Of course that would be $a[not(. = $b)] maybe even $a except $b, I was
asking more on what the performance expectation would be.

Pleased that it reasonable to expect it to be fast.

[Adam Retter]

Post by Ihe Onwuka
I want to drop the things that are in B from A where both B and A are just
sequences of integers. In other words, don't fetch what I've already got.

(1,2,3)[fn:not(. = (2,4))]

[Adam Retter]

Post by Adam Retter
I think that question is very implementation specific. If all of your
data is in RAM, as your dataset is relatively small and these are just
numbers, I would expect performance to be excellent. I am not sure
that sorting will make much of a difference, but it depends on the
implementation and how it initiates the search for a false comparison
in a large sequence.

I retract any previous statements that may have alluded to good
performance. A quick test on Saxon and eXist shows that this is a very
slow problem. I am trying to see if there is not a short-cut that
could be taken, I will come back to you...

[Adam Retter]

So after a bit more coffee and a bit of research it seems to me that
the only way you are going to get this to be fast would be if you used
a hash based looked for one of your sequences. Something like a
HashMap or BloomFilter would do the job, see:
http://stackoverflow.com/questions/4261619/fastest-set-operations-in-the-west

I have made some experimentations with the above in Scala, a HashMap
works nicely here in-terms of performance because it is simple and
available, and in your case with Integers you do not need to worry
about duplicates because the value of a number is it's identity.

So, if you don't want to implement a HashMap or BloomFilter in XQuery,
what is one to do? Well XQuery 3.1 will introduce the Map data-type
and some implementations already have done this. If you understand the
implementation (or even hazard a guess), there is a good chance that
that XQuery map may in-fact under the covers be a HashMap.

I won't say too much more about this as I have been discussing it with
Wolfgang this morning, and I think he will shortly post you a very
fast example when using XQuery 3.1 Maps in eXist...

Post by Adam Retter

Post by Adam Retter
I think that question is very implementation specific. If all of your
data is in RAM, as your dataset is relatively small and these are just
numbers, I would expect performance to be excellent. I am not sure
that sorting will make much of a difference, but it depends on the
implementation and how it initiates the search for a false comparison
in a large sequence.

I retract any previous statements that may have alluded to good
performance. A quick test on Saxon and eXist shows that this is a very
slow problem. I am trying to see if there is not a short-cut that
could be taken, I will come back to you...
--
Adam Retter
skype: adam.retter
tweet: adamretter
http://www.adamretter.org.uk

[w***@exist-db.org]

Post by Adam Retter
I won't say too much more about this as I have been discussing it with
Wolfgang this morning, and I think he will shortly post you a very
fast example when using XQuery 3.1 Maps in eXist…

Well, Michael already posted something along those lines, but here’s my solution based on the public 3.1 draft:

xquery version "3.0";

let $a := 1 to 1000000
let $b := map:new((1 to 100) ! map:entry(xs:int(util:random() * 100000), 0))
return
$a[map:contains($b, .)]

Wolfgang

[Ihe Onwuka]

Post by Adam Retter
I won't say too much more about this as I have been discussing it with
Wolfgang this morning, and I think he will shortly post you a very
fast example when using XQuery 3.1 Maps in eXist

Well, Michael already posted something along those lines, but here’s my
xquery version "3.0";
let $a := 1 to 1000000
let $b := map:new((1 to 100) ! map:entry(xs:int(util:random() * 100000), 0))
return
$a[map:contains($b, .)]
Wolfgang

Would this not be $a[not(map:contains($b, .))] since I want the ones for
which there is no matching sequence B.

[Ihe Onwuka]

Post by Adam Retter
So after a bit more coffee and a bit of research it seems to me that
the only way you are going to get this to be fast would be if you used
a hash based looked for one of your sequences. Something like a
http://stackoverflow.com/questions/4261619/fastest-set-operations-in-the-west

Hmmmmm well I have already committed myself before your retraction and the
thing is running now so am just going to leave it.

This is only the tip of the problem because each integer that survives
selection generates an HTTP request that either returns a 404 or leads to
an HTTP Put into eXist. So if I was really in a hurry I'd have to start
looking at mapReducing the keys. I'm not even sure that is the answer as
all the mapreduce jobs would be pounding the same server (mind you the
site may load balance to mitigate that).

Another alternative solution is to just export sequence B into SQLite,
index both sequences (now they are tables) and do it in SQL.

[Michael Kay]

Note that maps give you the opportunity to hand-optimize things like this if your product's optimizer doesn't find a way to do it automatically.

let $A := a set of numbers
let $B := another set of numbers
let $map := fold-left($B, map{}, map:put(?, ?, true()))
return $A[empty($map(.))]

Michael Kay
Saxonica
***@saxonica.com
[phone]

I have sequence A consisting of the numbers 0 to 4000000 and sequnce B consisting of about 100k random I numbers within the range of sequence A and I want the outer join where sequence B is "null".
Should one expect bad performance in sequence B is not sorted and can one expect reasonable performance if it is?
I am guessing that performance will vary by implemetation.
_______________________________________________
http://x-query.com/mailman/listinfo/talk