6 ms·

If you just pick a worst case optimal join algorithm with a limited table cardinality, i.e. triples like in the case of OP, so that you can materialise every po

by j-pb 4y ago

If you just pick a worst case optimal join algorithm with a limited table cardinality, i.e. triples like in the case of OP, so that you can materialise every possible index, you can perform a dynamic _instance optimal_ search (i.e. you can ignore skew), if you choose the best possible variable every time you have to pick a variable. This can be done by estimating the cardinality and jaccard index of the variables, which is pretty straightforward with the right datastructure. If you don't want to limit yourself to just three columns, you can also go for cutting edge succinct data-structure magic. https://aidanhogan.com/docs/wco-ring.pdf https://aidanhogan.com/docs/wco-ring.pdf Either way, using a WCO join combined with a data-structure that allows for efficient range estimate and dynamic variable ordering, completely obliviates the need for query planning.

thesz 4y ago
"Estimate the cardinality", "jaccard index", "succinct data structure" and, finally, some unknown abbreviation "WCO" (I guess, it stands for "worst case optimal"). Yes, of course, having implementation of all that completely obliviates the need for query planning. ;) I can't help being sarcastic for a moment, sorry. In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices. If what you described is simpler than query planning, then query planning is hard.
- j-pb 4y ago
  While the technical terms may be unfamiliar, it's all pretty straightforward, and requires between 1-4kloc depending on how fast and fancy you want things to be. (This includes everything from the basic copy on write data-structures to the query language.) Building an immutable path compressed radix tree is pretty straightforward and requires around 1-2kloc, and it's easy to keep track of the n-smallest hashes of leaf values, as well as the total count of leafs in the nodes. The sampling done by the min-hashes give you a good indication of two nodes overlap which the jaccard index is just a different name for. The query engine itself is like 0.5kloc, and is just walking the different radix-trie indices simultaneously. The basic insight of worst case optimal (WCO) joins, is that it's a lot cheaper to join everything at once and treat it as a constraint propagation problem. A LINQ style query parser takes up another 1-2kloc and is just a bunch of ol' boilerplate. In total that's about as much code as your average large C++ codebase CMake file. You could sketch the entire thing on a napkin and build it in a week if you've build something like it before.
  - thesz 4y ago
    "If you build something like that before". I think I can add that to the list of famous last words. ;) Please, excuse my sarcasm again. But, tell me what to do if I didn't built something like this before? What if I built something like equality saturation engine, pseudoboolean optimization using SAT solver and/or beam search? Will it help me somehow? You estimated code size at 4.5KLOC max. Given that C++ programmer delivers 20-25 debugged lines of code per hour in the long run (IBM's stats), it would take 225 hours of work. Given that PSP/TSP recommends planning for 4 hours-on-task per day, it will take 56 work days. My calculation suggests 2.5 work months to implement all that in the worst case of 4.5KLOC. Even the best case of 2.5KLOC would take a month and a half of work. Yours' proposition is not a week's project. Not at all, you can't squeeze it that much. Query planning is hard. Even if you try your best to avoid it. And we have not even started talking about WHERE, GROUP BY and ORDER BY clauses' optimizations. [1] shows the use of loop nest optimization combined with beam search. SQLite uses translation of joins into loop nests, and it transforms loop nests into a graph, the path in the graph represents a solution. The [1] shows simplified nesting graph that is linear, and in general it will be quadratic to the number of tables. [1] https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html I really like that approach. This is exactly an equality saturation [2] (saturate loop nesting through loop nesting commutativity) with the beam search as a selection phase. [2] https://rosstate.org/publications/eqsat/ https://rosstate.org/publications/eqsat/ I think that equality saturation with beam search is a week long project if you already have built something like that. The difference? It will work for arbitrary jons. Of course I am making fun of your statements. Equality saturation requires quite careful planning and will not work for couple of months, you will keep finding something that fails. Beam search is just as hard. You can encode optimal solution selection problem as a pseudoboolean optimization problem, which is more straightforward than beam search, and [2] shows that Pueblo is no slouch there. This is not to say that query planning is easy when you do it my way. Query planning is hard. NP-hard, actually. Sometimes you can get away with a simpler less general solution, but it will bite you sooner than you expect.
    - 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.

by j-pb 4y ago

thesz 4y ago

"Estimate the cardinality", "jaccard index", "succinct data structure" and, finally, some unknown abbreviation "WCO" (I guess, it stands for "worst case optimal"). Yes, of course, having implementation of all that completely obliviates the need for query planning. ;) I can't help being sarcastic for a moment, sorry. In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices. If what you described is simpler than query planning, then query planning is hard.

j-pb 4y ago
While the technical terms may be unfamiliar, it's all pretty straightforward, and requires between 1-4kloc depending on how fast and fancy you want things to be. (This includes everything from the basic copy on write data-structures to the query language.) Building an immutable path compressed radix tree is pretty straightforward and requires around 1-2kloc, and it's easy to keep track of the n-smallest hashes of leaf values, as well as the total count of leafs in the nodes. The sampling done by the min-hashes give you a good indication of two nodes overlap which the jaccard index is just a different name for. The query engine itself is like 0.5kloc, and is just walking the different radix-trie indices simultaneously. The basic insight of worst case optimal (WCO) joins, is that it's a lot cheaper to join everything at once and treat it as a constraint propagation problem. A LINQ style query parser takes up another 1-2kloc and is just a bunch of ol' boilerplate. In total that's about as much code as your average large C++ codebase CMake file. You could sketch the entire thing on a napkin and build it in a week if you've build something like it before.
- thesz 4y ago
  "If you build something like that before". I think I can add that to the list of famous last words. ;) Please, excuse my sarcasm again. But, tell me what to do if I didn't built something like this before? What if I built something like equality saturation engine, pseudoboolean optimization using SAT solver and/or beam search? Will it help me somehow? You estimated code size at 4.5KLOC max. Given that C++ programmer delivers 20-25 debugged lines of code per hour in the long run (IBM's stats), it would take 225 hours of work. Given that PSP/TSP recommends planning for 4 hours-on-task per day, it will take 56 work days. My calculation suggests 2.5 work months to implement all that in the worst case of 4.5KLOC. Even the best case of 2.5KLOC would take a month and a half of work. Yours' proposition is not a week's project. Not at all, you can't squeeze it that much. Query planning is hard. Even if you try your best to avoid it. And we have not even started talking about WHERE, GROUP BY and ORDER BY clauses' optimizations. [1] shows the use of loop nest optimization combined with beam search. SQLite uses translation of joins into loop nests, and it transforms loop nests into a graph, the path in the graph represents a solution. The [1] shows simplified nesting graph that is linear, and in general it will be quadratic to the number of tables. [1] https://www.sqlite.org/queryplanner-ng.html https://www.sqlite.org/queryplanner-ng.html I really like that approach. This is exactly an equality saturation [2] (saturate loop nesting through loop nesting commutativity) with the beam search as a selection phase. [2] https://rosstate.org/publications/eqsat/ https://rosstate.org/publications/eqsat/ I think that equality saturation with beam search is a week long project if you already have built something like that. The difference? It will work for arbitrary jons. Of course I am making fun of your statements. Equality saturation requires quite careful planning and will not work for couple of months, you will keep finding something that fails. Beam search is just as hard. You can encode optimal solution selection problem as a pseudoboolean optimization problem, which is more straightforward than beam search, and [2] shows that Pueblo is no slouch there. This is not to say that query planning is easy when you do it my way. Query planning is hard. NP-hard, actually. Sometimes you can get away with a simpler less general solution, but it will bite you sooner than you expect.
  - 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.