Can PostgreSQL optimizer carry `ORDER BY` out of `JOIN` subquery?

There is a "theoretical" query:

SELECT * FROM a
JOIN (
    SELECT b.pk, b.not_pk
    FROM b
    ORDER BY b.not_pk
) AS b2
USING (pk)

and EXPLAIN shows Sort on the whole b.

Can it be carried out of the join (by the optimizer), theoretically? If so, why it isn't?

Can it be carried out of the join, theoretically?

It cannot.

If it could, it would have to consider resolving it against any order by the outer query may have. It would also break limit/fetch first in subqueries, or examples like this: _{demo at db<>fiddle}

select array_agg(x)
from(select x from t order by x)_;

Which is currently equivalent to this

select array_agg(x order by x) from t

Unless you're really using it with something order-dependent, sorting inside CTEs and subqueries doesn't make much sense, because the final, outermost, top-level query is free to rearrange its results arbitrarily, or according to a completely different order by.

From the rewriter/planner/optimiser point of view it could even make sense to completely ignore and discard all inner order bys in the absence of order-dependent features. I don't think it's currently done, and I'd assume that's precisely because someone could reasonably expect that inner sorting to drive something further up, like the array_agg() above.

In your case, you should see that order by goes to waste because it pulls the data, sorts it, then discards that order and sorts it again by the pk you're joining on, like join operations do.

I think what you might've had in mind, or what's a logical extension of this idea, is whether the a.pk=b.pk (resulting from using(pk)) condition can be pushed down into the subquery, to reduce the set prior to sorting.

That would be a good idea and something like this is in fact done by most planners, not just Postgres, and usually referred to as "condition pushdown" which you can see in the example below.

explain analyze verbose
SELECT * FROM a
JOIN (
    SELECT b.pk, b.not_pk
    FROM b
    ORDER BY b.not_pk
) AS b2
USING (pk)
WHERE b2.not_pk<>0;--this will get pushed down