Links between Join Processing and Convex Geometry

This talk will survey some results on join processing that use inequalities from convex geometry. Recently, Ngo, Porat, Rudra, and Re ́ (NPRR) discovered the first relational join algorithm with worst-case optimal run-ning time [8]. Since the seminal System R project [12], the dominant database optimizer paradigm optimizes a join query by examining each pair of joins and then combining these estimates using dynamic programming. In contrast, NPRR examines all relations at the same time. This change to the “one-join-at-a-time ” dogma is important for performance: there are classes of queries for which any join-project plan is destined to be slower than the best possible run time by a polynomial factor in size of the data. NPRR’s analysis makes a link from database theory to a pair of beautiful inequalities: on