And how modern SAT solving algorithms are fundamentally very similar to worst case optimal join algorithms?

There are at least two different types of them, conflict-derived clause learning and variants and stochastic search and variants.

Which one is more similar to WCO join algorithm?

DPLL, see https://arxiv.org/pdf/1912.12747.pdf

The paper you provided has two important omissions: 1) it does not mention Tseitin transformation to encode Disjunctive Normal Form into a Conjunctive Normal Form and 2) does not look at decision diagrams, especially, zero-suppressed decision diagrams for set representation.

Tseitin transformation prevents exponential expansion in conversion from DNF to CNF.

The fact that paper's algorithm employs disjunctive normal form suggests the use of binary decision diagrams. ROBDDs represent DNFs naturally, for one example. ZDDs represent sets of sets and were relatively successfully used in non-trivial approaches to the SAT solving problem like [1].

[1] https://web.eecs.umich.edu/~imarkov/pubs/book/b002.pdf

Also, the paper you mentioned has this right in abstract: "However, there is still the quest of making the new worst-case optimal join algorithms truly practical in terms of (1) ease of implementation and (2) secondary index efficiency in terms of number of indexes created to answer a query."

WCO is hard to implement and it might be computation-wise prohibitive.

Yet, it's quite interesting, thank you very much.

>The query plan produced by combining binary joins is always going to be off by up to an exponential factor when compared to a WCO join.

Citation greatly needed. Why is it so?

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.N...

https://justinjaffray.com/a-gentle-ish-introduction-to-worst...

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.

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)

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

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!