Séminaire MIDI : Vasile-Radu Ciucanu

Titre du séminaire et orateur

Worst-Case Optimal Join at a Time.

Vasile-Radu Ciucanu (postdoctoral researcher at Oxford University).

Date et lieu

Lundi 7 mars 2016, 10h.

Université de Cergy-Pontoise, site de St-Martin 1, locaux ETIS (bât. A, 5ème étage) salle 570.


Join processing is core to database systems research. Recently, there has been a revival of this topic with exciting new results on the worst-case optimality of computing join queries. At the outset of this effort is the observation that the classical join evaluation approaches, which rely on query plans that are evaluated one join at a time, are suboptimal in the sense that intermediate results of a join query may be larger than the final result. Recent efforts distilled two messages that are essential for worst-case optimality of relational join processing: the entire join query needs to be evaluated as one monolith and without intermediate results; and special care is needed when handling skew.

In this talk, I will argue that the aforementioned monolithic recipe for join processing is an artefact of the tabular data representation and not necessary for achieving worst-case optimality. I will also present an effective procedure that achieves optimality with multiway join-at-a-time query plans by employing succinct representations of the intermediate results and a new join operator that works on such succinct representations. I will conclude with the applications of the developed techniques to massive data analytics.

Joint work with Dan Olteanu and Joe Kirk.