Nie jesteś zalogowany | Zaloguj się

How Hard Is Join Ordering, Really?

Prelegent(ci)
Jerzy Tyszkiewicz
Afiliacja
MIMUW
Język referatu
angielski
Termin
3 listopada 2026 11:00
Pokój
p. 4060
Seminarium
Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

I will present the proof of the fact, that finding an optimal left-deep plan for a multiway join is NP-hard.

This result was claimed by Cluet and Moerkotte, who provided a sketch of the proof, with no details. We fill the missing elements. Neither the resulting theorem nor the proof exactly follow the outline in the above paper, but the principal idea is the same.

We will also indicate the shortcomings of the theorem, which does not necessarily correspond to the practical issue of optimizing large joins.