5 ms·

The intuition is that if your join is a triangle you might be forced to join every relation only to discover that the result is empty on the last join, which re

by j-pb 4y ago

The intuition is that if your join is a triangle you might be forced to join every relation only to discover that the result is empty on the last join, which requires m^n intermediary results, where m is the size of the relations and n is the number of relations. A WCO join algorithm will figure out quite quickly that the output is empty and is in practice much more dependent on the actual output size, than the size of the input relations. See: https://www.cs.stanford.edu/people/chrismre/papers/paper49.Ngo.pdf https://www.cs.stanford.edu/people/chrismre/papers/paper49.N... https://justinjaffray.com/a-gentle-ish-introduction-to-worst-case-optimal-joins/ https://justinjaffray.com/a-gentle-ish-introduction-to-worst...

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 ago
  That 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 ago
    Exactly 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!

by j-pb 4y ago

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 ago
That 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 ago
  Exactly 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!