On Mon, Jun 14, 2021 at 12:10 PM Tomas Vondra <
tomas.vondra@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.