<font class="Apple-style-span" face="georgia, serif">Sorry, I was abusing the term "binary merge". What I was actually thinking of was algorithms like the ones discussed in</font><div><h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<font class="Apple-style-span" face="georgia, serif" size="2">"<a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9963 ">Adaptive Set Intersections, Unions, and Differences</a>" (2000) and "</font><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.9365" style="font-family: georgia, serif; font-size: small; ">Faster Adaptive Set Intersections for Text Searching</a><span class="Apple-style-span" style="font-family: georgia, serif; font-size: small; ">" (2006).</span></h2>
<h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<font class="Apple-style-span" face="georgia, serif" style="font-size: small; ">The algorithm you describe is good for nrow(i) << nrow(x) </font><span class="Apple-style-span" style="font-size: small; font-family: georgia, serif; "> </span><span class="Apple-style-span" style="font-size: small; font-family: georgia, serif; ">(though not as good as the algorithms described above)</span><span class="Apple-style-span" style="font-size: small; font-family: georgia, serif; "> </span><span class="Apple-style-span" style="font-size: small; font-family: georgia, serif; ">, but as you say, not very good when nrow(i) ~ nrow(x), in which case it will be roughly log2(nrow(x))/2 times slower than simple linear merge. Of course, the detailed speed comparisons will depend on the distribution of values and the exact code in the inner loops.</span></h2>
<h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<span class="Apple-style-span" style="font-size: small; ">> By "preexisting keys" you do mean both tables have a key, right?</span></h2><h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<span class="Apple-style-span" style="font-family: georgia, serif; font-size: small; ">Yes.</span></h2><h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<span class="Apple-style-span" style="font-size: small; ">> I'd be very very interested to see a script and timing results. </span></h2><h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<span class="Apple-style-span" style="font-family: georgia, serif; font-size: small; ">I could take that on as a project this weekend. But is it worth it? The papers cited above have lots of performance tests showing that those algorithms are better than binary search merge or linear merge and everything in between.</span></h2>
<h2 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0.5em; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-weight: inherit; vertical-align: baseline; ">
<span class="Apple-style-span" style="font-family: georgia, serif; font-size: small; "> -s</span></h2></div><div><font class="Apple-style-span" face="georgia, serif"><br></font></div><div><div><div class="gmail_quote">
On Thu, Oct 27, 2011 at 03:55, Matthew Dowle <span dir="ltr"><<a href="mailto:mdowle@mdowle.plus.com">mdowle@mdowle.plus.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I think I know what you mean but just to first check a few things. This<br>
nestled deep in ?data.table :<br>
<br>
"If i also has a key, it is i's key columns that are used to match to<br>
x's key columns and a binary merge of the two tables is carried out."<br>
<br>
By 'binary merge', what ?data.table means is that each row of i isn't<br>
looked up in x using binary search from scratch. When i has a key (too)<br>
the lower bound of binary search is not reset to 0 after each row in i<br>
(as it is when i isn't keyed), it's left at the row in x matched by the<br>
previous row of i. The upper bound is reset to nrow(x) for each row of<br>
i, though. It's kind of a half-way approach. Yes, the assumption so far<br>
has been that nrow(i)<<nrow(x).<br>
<br>
By "preexisting keys" you do mean both tables have a key, right? Some<br>
(incorrectly) refer to the key columns as keys (plural). The terminology<br>
is that a data.table has at most one key (singular). A key has many<br>
columns. Just checking no confusion before proceeding ...<br>
<br>
I'd be very very interested to see a script and timing results. It would<br>
make sense to do a linear search where it makes more sense, no problem.<br>
That could be an internal switch (if we know what the rule should be)<br>
that could be overridden by user. The worst case is X[X], isn't it.<br>
<br>
Also, if you know x's key is unique then setting mult="first" may be<br>
faster. I'd be very interested in the difference that makes, perhaps on<br>
the worst case X[X] vs X[X,mult="first"].<br>
<font color="#888888"><br>
Matthew<br>
</font><div><div></div><div class="h5"><br>
<br>
On Wed, 2011-10-26 at 17:57 -0400, Stavros Macrakis wrote:<br>
> Some quick testing seems to show that the cost of joining table A to<br>
> table B (on preexisting keys) is proportional to<br>
> size(A)*log2(size(B)), that is, each element of table A is looked up<br>
> (using binary search) in table B. This is very efficient when size(A)<br>
> << size(B), but when they're of similar size, a linear merge can be<br>
> done in time size(A)+size(B), which can be several times faster.<br>
> Binary merge has a smooth transition from one regime to the other,<br>
> but a simple cross-over is pretty good already.<br>
><br>
><br>
> I would put together a nice script to show this explicitly, but that<br>
> will take some time, so I wanted to check whether this is a known<br>
> issue or if I need to demonstrate this issue in more detail. (Or if<br>
> I've made some stupid blunder.)<br>
><br>
><br>
> Thanks!<br>
><br>
><br>
> -s<br>
</div></div><div><div></div><div class="h5">> _______________________________________________<br>
> datatable-help mailing list<br>
> <a href="mailto:datatable-help@lists.r-forge.r-project.org">datatable-help@lists.r-forge.r-project.org</a><br>
> <a href="https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/datatable-help" target="_blank">https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/datatable-help</a><br>
<br>
<br>
</div></div></blockquote></div><br></div></div>