I'm glad you appreciated my comments and optimizations :-) But as you noticed, even if the neighborhood optimizations matter a lot for raw DPhyp speed, they really matter that much in practice (I implemented DPhyp once, mostly at a hotel room while on travel for a marathon, and then basically never touched it again); most of the time is spent scoring every subplan, with the O(mn) explosion of possible implementation strategies. I must admit I didn't read all of your caching details (there are many years since I wrote this code), but you're right in that it's a fascinating field. :-)
Apart from that, you've basically rediscovered a bunch of the problems that the papers never talk about, e.g. how to get consistent plan sizes between different join orders. The Postgres way of just locking in the first you find is kind of hackish IMO, but I guess it works. My opinion is that the best way probably is to fix the selectivities ahead of time; it's not easy, especially when dealing with cycles (that arise from multiple equalities), but you can find some help in academia with at least trying to reconcile multiple estimates on a single predicate into something reasonably consistent. The old (non-hypergraph) MySQL optimizer “solved” this problem by just ignoring it! So even t1 JOIN t2 ON t1.x=t2.x could get completely different estimated number of output rows depending on whether the scan on t2 used an index or not (not to mention which table came first in the join order), and this error/difference would ripple through to larger plans. (Indexes in MySQL have selectivity estimates, seqscans with filters have to rely on histograms which may not even exist. Yes, it's wild.)
Your specific case of a massive hyperedge has a completely different solution, though; the DPhyp paper mentions “generalized hypergraphs” with a free middle bucket on each edge (in addition to left and right), and in your case, basically all the tables should probably be put into that middle bin and thus be freely movable between both sides. (Optimal hypergraph construction in general is a bit tricky, and just reusing Postgres' structures where you break on every outer join is probably not going to give you the best possible outcome for DPhyp.) MySQL doesn't implement this because we had much bigger fish to fry (multijoins are rare), and I don't know if anyone ever actually did except the original paper authors. It is also possible to sometimes advantageously insert simple edges between tables even if they don't have any join predicate in common (which loosens up the allowed join orders somewhat), but again, we never did.
Oh, and I should add: The primary advantage with DPhyp as I see it (over DPsize) is that you get very cheap and natural handling of outer joins; you spend very little time enumerating subplans that you eventually have to throw away because they a
re illegal join reorderings, which can be a real issue for plain DPsize AIUI. (There is a fairly straightforward paper that shows how to construct hypergraphs for a pretty wide variety of different join types.) I'm honestly not sure if current Postgres can get all of these reorderings right; I know that since 8.x, it has some home-grown outer join reordering machinery but not really how it works or how efficient it is. But in any case, if you're only using DPhyp for the clusters of inner joins in a plan, you're really missing out on most of the advantage. :-)
FWIW, I don't think we would have gone all the way to implement DPhyp if we already had a working and good DPsize implementation, but we didn't (the old optimizer works only by prefix search, which cannot create bushy joins and thus not plan full outer joins at all), so it made sense for us. Of course, you also need all the other parts Postgres already has, like a cost model, handling of interesting orders/groupings (Postgres' is a bit primitive, though, in that it only handles equivalences, not functional dependencies), subquery rewrites etc. etc.. People walk around thinking that using one good algorithm will automatically give you a good optimizer, and life isn't that simple. :-)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
I'm glad you appreciated my comments and optimizations :-) But as you noticed, even if the neighborhood optimizations matter a lot for raw DPhyp speed, they really matter that much in practice (I implemented DPhyp once, mostly at a hotel room while on travel for a marathon, and then basically never touched it again); most of the time is spent scoring every subplan, with the O(mn) explosion of possible implementation strategies. I must admit I didn't read all of your caching details (there are many years since I wrote this code), but you're right in that it's a fascinating field. :-)
Apart from that, you've basically rediscovered a bunch of the problems that the papers never talk about, e.g. how to get consistent plan sizes between different join orders. The Postgres way of just locking in the first you find is kind of hackish IMO, but I guess it works. My opinion is that the best way probably is to fix the selectivities ahead of time; it's not easy, especially when dealing with cycles (that arise from multiple equalities), but you can find some help in academia with at least trying to reconcile multiple estimates on a single predicate into something reasonably consistent. The old (non-hypergraph) MySQL optimizer “solved” this problem by just ignoring it! So even t1 JOIN t2 ON t1.x=t2.x could get completely different estimated number of output rows depending on whether the scan on t2 used an index or not (not to mention which table came first in the join order), and this error/difference would ripple through to larger plans. (Indexes in MySQL have selectivity estimates, seqscans with filters have to rely on histograms which may not even exist. Yes, it's wild.)
Your specific case of a massive hyperedge has a completely different solution, though; the DPhyp paper mentions “generalized hypergraphs” with a free middle bucket on each edge (in addition to left and right), and in your case, basically all the tables should probably be put into that middle bin and thus be freely movable between both sides. (Optimal hypergraph construction in general is a bit tricky, and just reusing Postgres' structures where you break on every outer join is probably not going to give you the best possible outcome for DPhyp.) MySQL doesn't implement this because we had much bigger fish to fry (multijoins are rare), and I don't know if anyone ever actually did except the original paper authors. It is also possible to sometimes advantageously insert simple edges between tables even if they don't have any join predicate in common (which loosens up the allowed join orders somewhat), but again, we never did.
Oh, and I should add: The primary advantage with DPhyp as I see it (over DPsize) is that you get very cheap and natural handling of outer joins; you spend very little time enumerating subplans that you eventually have to throw away because they a
re illegal join reorderings, which can be a real issue for plain DPsize AIUI. (There is a fairly straightforward paper that shows how to construct hypergraphs for a pretty wide variety of different join types.) I'm honestly not sure if current Postgres can get all of these reorderings right; I know that since 8.x, it has some home-grown outer join reordering machinery but not really how it works or how efficient it is. But in any case, if you're only using DPhyp for the clusters of inner joins in a plan, you're really missing out on most of the advantage. :-)
FWIW, I don't think we would have gone all the way to implement DPhyp if we already had a working and good DPsize implementation, but we didn't (the old optimizer works only by prefix search, which cannot create bushy joins and thus not plan full outer joins at all), so it made sense for us. Of course, you also need all the other parts Postgres already has, like a cost model, handling of interesting orders/groupings (Postgres' is a bit primitive, though, in that it only handles equivalences, not functional dependencies), subquery rewrites etc. etc.. People walk around thinking that using one good algorithm will automatically give you a good optimizer, and life isn't that simple. :-)