3 ms·
Thank you, second link of yours starts with the explanation of benefits expected, which is great. The difference is not exponential, if I may nitpick. It is su
by thesz 4y ago
Thank you, second link of yours starts with the explanation of benefits expected, which is great.
The difference is not exponential, if I may nitpick. It is sublinear in the case of the "triangles example" - WCO would produce O(n^(1.5)), binary join will produce O(n^2), the difference is O(n^(0.5)) or O(sqrt(n)). The difference is big, but not exponential.
- j-pb 4y agoThat blogpost is a godsend, it provides a great explanation and intuition, and resolved a few questions that I was left with after reading a lot of WCO join papers. Good nitpick, I think you can construct larger rings where the difference becomes larger than one, but I might be wrong. The dynamic variable ordering trick makes a huge difference in practice, especially when skew is in play. (https://arxiv.org/pdf/1310.3314.pdf https://arxiv.org/pdf/1310.3314.pdf) In general you're right, WCO joins are a relatively young field of study and sometimes struggle with large constant factors, but they are maturing quickly and in a limited (triple) setting like the one OP "wished for", a lot more feasible than for the general case. Thanks for the interesting discussions, looking forward to reading the references you provided in depth! Edit: I just remembered this paper, which might be of interest to you. They seem to recover WCO bounds in a pairwise setting, by choosing very smart intermediary join representations: http://www.cs.ox.ac.uk/dan.olteanu/papers/co-tr16.pdf http://www.cs.ox.ac.uk/dan.olteanu/papers/co-tr16.pdf
- thesz 4y agoExactly what I needed, thank you again very much! My old idea was to perform planning after some of the work has been done, because remaining statistics can be different. These papers are of great help!