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.
Nie jesteś zalogowany |