How Hard Is Join Ordering, Really?
- Speaker(s)
- Jerzy Tyszkiewicz
- Affiliation
- MIMUW
- Language of the talk
- English
- Date
- Nov. 3, 2026, 11 a.m.
- Room
- room 4060
- Seminar
- 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.
You are not logged in |