The Actor, Company, and Movie entity tables are connected via the Produces and Stars relationship tables (e.g., via foreign keys). A version of this query in SQL might be:

Logically, we want to perform a simple join operation: Actor ⋈ Stars ⋈ Movie ⋈ Produces ⋈ Company. But physically, since each of these joins are commutative and associative, we have a lot of options. The query optimizer could choose to:

Which plan is optimal depends on the data: if Scarlett Johansson has starred in significantly fewer movies than Sony has produced, the first plan might be optimal. Unfortunately, estimating this quantity is as difficult as executing the query itself (in general). Even worse, there are normally far more than 3 plans to choose from, as the number of possible plans grows exponentially with the number of tables — and analytics queries regularly join 20-30 different tables.

How does join ordering work today? Traditional query optimizers solve this problem with three components: a cardinality estimator designed to quickly guess the size of subqueries (e.g., to guess how many movies Sony has produced), a cost model to compare different potential plans, and a search procedure that navigates the exponentially-large space. Cardinality estimation is especially difficult, and has led to a wide range of research seeking to improve estimation accuracy using a wide range of approaches [A].