tags: #joins #query-processing source: [[Skew-Strikes-Back]]\[Q_∆ = R(A,B) ⋈ S(B,C) ⋈ T(A,C)\]
Traditional join plan for the triangle query given above, the simplest cyclic query, involves determining the best pair-wise join plan among three.
Let us take an example of a family of instances for which any of the above three join plans must run in time \(Ω(N^2)\) because the intermediate relation P is too large.
|In the above instance, each relation has N = 2m + 1 tuples and $$||Q_∆||= 3m+1\(; however, any pair-wise join has size\) m^2 + m$$|
Thus, any of the three join plans will take \(Ω(N^2)\) time. This bound holds even if we allow projections.