Re: a path towards replacing GEQO with something better

On Mon, Jun 14, 2021 at 12:10 PM Tomas Vondra <tomas(dot)vondra(at)enterprisedb(dot)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