Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating query plans for queries that include common table expressions. One of the methods includes receiving a query that includes a common table expression (CTE), wherein the CTE signifies that a system can compute a result for the query using a query plan that includes a CTE producer operator and a corresponding CTE consumer operator. A first query plan that includes a CTE producer operator and a corresponding CTE consumer operator and a second query plan that inlines an instance of the CTE consumer operator are generated. Respective costs are computed for the first query plan and the second query plan, and a result for the query is computed using the second query plan if the second query plan has a lower cost.