[0]: https://wiki.postgresql.org/wiki/Todo#Optimizer_.2F_Executor. Search for CTE.
Consider for example this:
WITH x AS (SELECT a, b FROM t) SELECT * FROM x x1 JOIN x x2 ON (x1.a = x2.b);
Now, had this been evaluated using a merge join, the "x" CTE would have to be sorted first by "a" or "b" (for either side of the join). Well, that can't really happen.
Another issue is locking - consider this version, for example:
WITH x AS (SELECT a, b FROM t FOR UPDATE) SELECT * FROM x x1 JOIN x x2 ON (x1.a = x2.b);
In other words, it's way more complicated than it might seem, especially if you can't break existing uses (e.g. the locking).
Not disputing what you're saying, but I swear I read something the other day recommending being careful using CTE's as they are re-executed once for every reference in the query (or something to that effect).
So the statement that "a CTE is only evaluated once" should not be part of any specification for the language. And I would not expect two different executions of a query to maintain that invariant if the optimizer finds it better not to.
The problem is we currently have an implementation that behaves as explained above (planned in isolation, evaluated once), and there are applications relying on that behaviour. We can't just change that without breaking them.
I'm not arguing for just abruptly reverse the design, but that the aim should be to reverse in an orderly manner with suitable deprecations and migration paths in place.
But don't forget: CTEs can be recursive.
I've been recently running TPC-DS on PostgreSQL 9.5 (alpha1 IIRC), to see how we're doing (I'm one of the contributors). Thanks to the grouping sets, we're now able to execute all 99 queries in the benchmark, which is awesome. Regarding performance, I've expected grouping sets to be a performance issue as the current implementation is rather simple. But to my mild surprise that's not the case - CTEs are the main problem.
On 100GB data set some queries took hours to complete (well, I interrupted them so I'm not sure how long it'd actually take). After a rewrite (replace CTE with a subquery), the query took a a minute or so.