3 ms·

C++ is probably the slowest programming language in terms of development speed there is, but even if it takes you 3 months to build something like that from scr

by j-pb 4y ago

C++ is probably the slowest programming language in terms of development speed there is, but even if it takes you 3 months to build something like that from scratch it'll still be an order of magnitude less time than building a clone of another SQL database. `WHERE, GROUP BY and ORDER BY` are relatively straightforward to tack on into the variable ordering. Having written a sat solver would kinda help you, because modern sat solving algorithms are fundamentally very similar to worst case optimal join algorithms. 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. If you're fine throwing all that complexity onto your problem to generate sub-par query plans, be my guest.

thesz 4y ago
>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?
- 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!
thesz 4y ago
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?
- j-pb 4y ago
  DPLL, see https://arxiv.org/pdf/1912.12747.pdf https://arxiv.org/pdf/1912.12747.pdf
  - thesz 4y ago
    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 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.

by j-pb 4y ago

thesz 4y ago

>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?

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!

thesz 4y ago

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?

j-pb 4y ago
DPLL, see https://arxiv.org/pdf/1912.12747.pdf https://arxiv.org/pdf/1912.12747.pdf
- thesz 4y ago
  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 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.