On Mon, Jun 14, 2021 at 12:10 PM Tomas Vondra <tomas.von...@enterprisedb.com> wrote:
> >> I haven't read the [Kossmann & Stocker, 2000] paper yet, but the > >> [Neumann, 2018] paper seems to build on it, and it seems to work with > >> much larger subtrees of the join tree than k=5. > > > > Right, in particular it builds on "IDP-2" from Kossmann & Stocker. Okay, > > so Neumann's favorite algorithm stack "Adaptive" is complex, and I > > believe you are referring to cases where they can iteratively improve up > > to 100 rels at a time because of linearization. That's a separate > > algorithm (IKKBZ) that complicates the cost model and also cannot have > > outer joins. If it has outer joins, they use regular DP on subsets of > > size up to 10. It's not substantively different from IDP-2, and that's > > the one I'd like to try to gracefully fall back to. Or something similar. > > > > Yes, that's what I was referring to. You're right it's complex and we > don't need to implement all of that - certainly not on day one. The > linearization / IKKBZ seems interesting (even if just for inner joins), > but better to start with something generic. Update for future reference: The authors published a follow-up in 2019 in which they describe a way to allow non-inner joins to be considered during linearization. Their scheme also allows for incorporating a limited number of cross products into the search in a safe way. Unsurprisingly, these features add complexity, and I don't quite understand it yet, but it might be worth evaluating in the future. https://btw.informatik.uni-rostock.de/download/tagungsband/B2-1.pdf -- John Naylor EDB: http://www.enterprisedb.com
